万字长文，整理不易。点赞加评论期末高分过！
文章内容较长，建议搭配目录使用
6-1 线性表元素的区间删除
给定一个顺序存储的线性表，请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储，并且相对位置不能改变。
函数接口定义：
List Delete( List L, ElementType minD, ElementType maxD );
其中List结构定义如下：
typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素在数组中的位置 */ };
L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较；minD和maxD分别为待删除元素的值域的下、上界。函数Delete应将Data[]中所有值大于minD而且小于maxD的元素删除，同时保证表中剩余元素保持顺序存储，并且相对位置不变，最后返回删除后的表。
裁判测试程序样例：
#include <stdio.h> #define MAXSIZE 20 typedef int ElementType; typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ }; List ReadInput(); /* 裁判实现，细节不表。元素从下标0开始存储 */ void PrintList( List L ); /* 裁判实现，细节不表 */ List Delete( List L, ElementType minD, ElementType maxD ); int main() { List L; ElementType minD, maxD; int i; L = ReadInput(); scanf("%d %d", &minD, &maxD); L = Delete( L, minD, maxD ); PrintList( L ); return 0; } /* 你的代码将被嵌在这里 */
输入样例：
10 4 -8 2 12 1 5 9 3 3 10 0 4
输出样例：
4 -8 12 5 9 10
解析：
List Delete(List L, ElementType minD, ElementType maxD) { int i, p = 0; for (i = 0; i <= L->Last; i++) { if (L->Data[i] <= minD || L->Data[i] >= maxD) { L->Data[p++] = L->Data[i]; } } L->Last = p - 1; return L; }
6-2 有序表的插入
设顺序表中的数据元素是按值非递减有序排列的，试编写一算法，将x插入到顺序表的适当位置上，以保持顺序表的有序性。
函数接口定义：
void ListInsertSort(SqList *L, DataType x);
其中 L 和 x 都是用户传入的参数。 L 表示顺序表， x 是要插入的元素。
裁判测试程序样例：
#include"stdio.h" #define LISTSIZE 100 typedef int DataType; typedef struct{ DataType items[LISTSIZE]; int length; }SqList; /* 本题要求函数 */ void ListInsertSort(SqList *L, DataType x); int InitList(SqList *L) {/*L为指向顺序表的指针*/ L->length=0; return 1; } int ListLength(SqList L) {/*L为顺序表*/ return L.length; } int ListInsert(SqList *L,int pos,DataType item) {/*L为指向顺序表的指针,pos为插入位置,item为待插入的数据元素*/ int i; if(L->length>=LISTSIZE){ printf("顺序表已满，无法进行插入操作！");return 0;} if(pos<=0 || pos>L->length+1){ printf("插入位置不合法，其取值范围应该是[1,length+1]"); return 0; } for(i=L->length-1; i>=pos-1; i--) /*移动数据元素*/ L->items[i+1]=L->items[i]; L->items[pos-1]=item; /*插入*/ L->length++; /*表长增一*/ return 1; } int TraverseList(SqList L) {/*L为顺序表*/ int i; for(i=0;i<L.length;i++) printf("%d ",L.items[i]); printf("\n"); return 1; } void main() { int i,input,x; SqList L1; //定义顺序表 InitList(&L1); //初始化建空表 for(i=0;;i++) { scanf("%d",&input); // 某些编译器要求此处改为scanf_s if(input==-1)break; ListInsert(&L1, i+1, input); //插入数据 } scanf("%d",&x); // 某些编译器要求此处改为scanf_s ListInsertSort(&L1, x); // 本题要求函数在主函数中的调用 TraverseList(L1); //遍历 } /* 请在这里填写答案 */
输入样例：
在这里给出一组输入。例如：
1 3 6 7 8 9 -1 3
输出样例：
在这里给出相应的输出。例如：
1 3 3 6 7 8 9
解析：
void ListInsertSort(SqList *L, DataType x) { int i, j; for (i = 0; i < L->length; i++) { if (x <= L->items[i]) { break; } } ListInsert(L, i + 1, x); }
6-3 合并两个有序数组
要求实现一个函数merge，将长度为m的升序数组a和长度为n的升序数组b合并到一个新的数组c，合并后的数组仍然按升序排列。
函数接口定义：
void printArray(int* arr, int arr_size); /* 打印数组,细节不表 */ void merge(int* a, int m, int* b, int n, int* c); /* 合并a和b为c */
其中a和b是按升序排列的数组，m和n分别为数组a、b的长度；c为合并后的升序数组。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> void printArray(int* arr, int arr_size); /* 打印数组,细节不表 */ void merge(int* a, int m, int* b, int n, int* c); /* 合并a和b为c */ int main(int argc, char const *argv[]) { int m, n, i; int *a, *b, *c; scanf("%d", &m); a = (int*)malloc(m * sizeof(int)); for (i = 0; i < m; i++) { scanf("%d", &a[i]); } scanf("%d", &n); b = (int*)malloc(n * sizeof(int)); for (i = 0; i < n; i++) { scanf("%d", &b[i]); } c = (int*)malloc((m + n) * sizeof(int)); merge(a, m, b, n, c); printArray(c, m + n); return 0; } /* 请在这里填写答案 */
输入样例：
输入包含两行。
第一行为有序数组a，其中第一个数为数组a的长度m，紧接着m个整数。
第二行为有序数组b，其中第一个数为数组b的长度n，紧接着n个整数。
7 1 2 14 25 33 73 84 11 5 6 17 27 68 68 74 79 80 85 87
输出样例：
输出为合并后按升序排列的数组。
1 2 5 6 14 17 25 27 33 68 68 73 74 79 80 84 85 87
解析
void merge(int *a, int m, int *b, int n, int *c) { int i, j, k; while (i < m && j < n) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < m) { c[k++] = a[i++]; } while (j < n) { c[k++] = b[j++]; } }
6-4 顺序表操作集
函数接口定义：
List MakeEmpty(); Position Find( List L, ElementType X ); bool Insert( List L, ElementType X, Position P ); bool Delete( List L, Position P );
其中List结构定义如下：
typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ };
各个操作函数的定义为：
List MakeEmpty()：创建并返回一个空的线性表；
Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR；
bool Insert( List L, ElementType X, Position P )：将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；
bool Delete( List L, Position P )：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 5 #define ERROR -1 typedef enum {false, true} bool; typedef int ElementType; typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */ }; List MakeEmpty(); Position Find( List L, ElementType X ); bool Insert( List L, ElementType X, Position P ); bool Delete( List L, Position P ); int main() { List L; ElementType X; Position P; int N; L = MakeEmpty(); scanf("%d", &N); while ( N-- ) { scanf("%d", &X); if ( Insert(L, X, 0)==false ) printf(" Insertion Error: %d is not in.\n", X); } scanf("%d", &N); while ( N-- ) { scanf("%d", &X); P = Find(L, X); if ( P == ERROR ) printf("Finding Error: %d is not in.\n", X); else printf("%d is at position %d.\n", X, P); } scanf("%d", &N); while ( N-- ) { scanf("%d", &P); if ( Delete(L, P)==false ) printf(" Deletion Error.\n"); if ( Insert(L, 0, P)==false ) printf(" Insertion Error: 0 is not in.\n"); } return 0; } /* 你的代码将被嵌在这里 */
输入样例：
6 1 2 3 4 5 6 3 6 5 1 2 -1 6
输出样例：
FULL Insertion Error: 6 is not in. Finding Error: 6 is not in. 5 is at position 0. 1 is at position 4. POSITION -1 EMPTY Deletion Error. FULL Insertion Error: 0 is not in. POSITION 6 EMPTY Deletion Error. FULL Insertion Error: 0 is not in.
解析
List MakeEmpty() { List list; list = (List) malloc(sizeof(struct LNode)); list->Last = -1; return list; } Position Find(List L, ElementType X) { int i; for (i = 0; i < MAXSIZE; i++) { if (L->Data[i] == X) return i; } return ERROR; } bool Insert(List L, ElementType X, Position P) { int i; if (L->Last == MAXSIZE - 1) { printf("FULL"); return false; } if (P < 0 || P > L->Last + 1) { printf("ILLEGAL POSITION"); return false; } for (i = L->Last; i >= P; i--) { L->Data[i + 1] = L->Data[i]; } L->Data[P] = X; L->Last++; return true; } bool Delete(List L, Position P) { int i; if (P < 0 || P > L->Last) { printf("POSITION %d EMPTY", P); return false; } for (i = P; i < L->Last; i++) { L->Data[i] = L->Data[i + 1]; } L->Last--; return true; }
6-5 递增的整数序列链表的插入
本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。
函数接口定义：
typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */
L是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Insert要将X插入L，并保持该序列的有序性，返回插入后的链表头指针。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List Read(); /* 细节在此不表 */ void Print( List L ); /* 细节在此不表 */ List Insert( List L, ElementType X ); int main() { List L; ElementType X; L = Read(); scanf("%d", &X); L = Insert(L, X); Print(L); return 0; } /* 你的代码将被嵌在这里 */
输入样例：
5 1 2 4 5 6 3
输出样例：
1 2 3 4 5 6
解析
List Insert(List L, ElementType X) { List p, s; p = L; s = (List) malloc(sizeof(struct Node)); s->Data = X; while (p->Next && p->Next->Data < X) { p = p->Next; } s->Next = p->Next; p->Next = s; return L; }
