1.（1）：编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。
实现代码：
#include#define MAXSIZE 100 typedef struct{ int data[MAXSIZE]; int last; }sequenlist; int main(){ sequenlist s = {{5,2,4,9,6,7,1},6}; printf("该顺序表中的所有元素为："); int i; for(i = 0;i <= s.last;i++){ printf("%d ",s.data[i]); } return 0; }
运行结果：
分析：
该程序建立了一个顺序表，其所有元素为{5,2,4,9,6,7,1}，并逐个输出了该顺序表中的所有元素。当该顺序表的last为n时，该程序的时间复杂度与空间复杂度均为线性阶O（n）。
（2）：编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。
实现代码：
#include#define MAXSIZE 100 typedef struct{ int data[MAXSIZE]; int last; }sequenlist; int search(sequenlist *l,int x){ int i,flag = -1; for(i = 0;i <= (*l).last;i++){ if((*l).data[i]==x){ flag = i; break; } } return flag; } int main(){ sequenlist s = {{5,2,2,4,6,7,5},6}; sequenlist *l = &s; printf("该顺序表中的所有元素为："); int i,x; for(i = 0;i <= s.last;i++){ printf("%d ",s.data[i]); } printf("n请输入想要查找的元素："); scanf("%d",&x); printf("%d",search(l,x)); return 0; }
运行结果：
分析：
该程序编写了一个顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果想要查找的元素存在，则返回顺序表中和x值相等的第1个数据元素的序号；如果不存在，返回－1。如上，输入2时，存在，返回第1个2的序号1，输入8时，不存在，返回-1。该定位操作的时间复杂度与空间复杂度均可看成线性阶O（n）。
（3）：在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。
解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。
实现代码：
#include#define MAXSIZE 100 typedef struct{ int data[MAXSIZE]; int last; }sequenlist; void insert(sequenlist *l,int x){ int i,j; for(i = 0;i <= (*l).last;i++){ if ((*l).data[i] > x){ break; } } for(j = (*l).last;j >= i;j--){ (*l).data[j+1] = (*l).data[j]; } (*l).data[i] = x; (*l).last++; } int main(){ sequenlist s = {{1,2,3,5,6,7},5}; sequenlist *l = &s; printf("该顺序表中的所有元素为："); int i,j,x; for(i = 0;i <= s.last;i++){ printf("%d ",s.data[i]); } printf("n请输入想要插入的元素："); scanf("%d",&x); insert(l,x); printf("插入新的元素后，该顺序表中的所有元素为："); for(i = 0;i <= s.last;i++){ printf("%d ",s.data[i]); } return 0; }
运行结果：
分析：
该程序按照解题思路在递增有序的顺序表中插入一个新结点x，并保持了顺序表的有序性。如上，插入顺序表中已存在的元素3时，正常插入，并且保持了顺序表的有序性，插入顺序表中不存在的元素4时，正常插入到应插入的位置，且插入后保持了顺序表的有序性。该插入操作的时间复杂度和空间复杂度均可看成线性阶O（n）。
（4）：删除顺序表中所有等于X的数据元素。
实现代码：
#include#define MAXSIZE 100 typedef struct{ int data[MAXSIZE]; int last; }sequenlist; int flag = 0; void delete(sequenlist *l,int x){ int i,j; for (i = 0;i <= (*l).last;i++){ if((*l).data[i] == x){ for (j = i + 1;j <= (*l).last;j++){ (*l).data[j-1] = (*l).data[j]; } (*l).last--; i--; flag = 1; } } } int main(){ sequenlist s = {{6,2,5,3,4,1,6,3,7,8,6,2,1,3},13}; sequenlist *l = &s; printf("该顺序表中的所有元素为："); int i,j,x; for(i = 0;i <= s.last;i++){ printf("%d ",s.data[i]); } printf("n请输入想要删除的元素："); scanf("%d",&x); delete(l,x); if(flag){ printf("删除相应元素后，该顺序表中的所有元素为："); for(i = 0;i <= (*l).last;i++){ printf("%d ",(*l).data[i]); } }else{ printf("所要删除的元素在顺序表中不存在！"); } return 0; }
运行结果：
分析：
该程序删除了顺序表中所有等于X的数据元素。如上，输入6时，删除了顺序表中的所有6这个元素，输入0时，由于0不存在于顺序表中，则输出其在顺序表中不存在。该删除操作的时间复杂度可看成平方阶O（n²），空间复杂度可看成线性阶O（n）。
2.已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。
实现代码：
#include#define MAXSIZE 100 typedef struct{ int data[MAXSIZE]; int last; }sequenlist; void MergeList(sequenlist *la,sequenlist *lb,sequenlist *lc){ int i = (*la).last,j = (*lb).last,k = 0; while(i!=-1&&j!=-1){ if((*la).data[i] >= (*lb).data[j]){ (*lc).data[k++]=(*la).data[i]; i--; }else{ (*lc).data[k++]=(*lb).data[j]; j--; } } while(i!=-1){ (*lc).data[k++] = (*la).data[i]; i--; } while(j!=-1){ (*lc).data[k++] = (*lb).data[j]; j--; } } int main(){ sequenlist a = {{1,2,3,5,7,8,9},6}; sequenlist b = {{2,3,4,6,8,9,10},6}; sequenlist c = {{0},a.last+b.last+1}; sequenlist *la = &a; sequenlist *lb = &b; sequenlist *lc = &c; int i; printf("顺序表a中的所有元素为："); for(i = 0;i <= a.last;i++){ printf("%d ",a.data[i]); } printf("n顺序表b中的所有元素为："); for(i = 0;i <= b.last;i++){ printf("%d ",b.data[i]); } MergeList(la,lb,lc); printf("n顺序表a和顺序表b归并成一个按元素值递减有序排列的顺序表后，所得顺序表中的所有元素为："); for(i = 0;i <= c.last;i++){ printf("%d ",c.data[i]); } return 0; }
运行结果：
分析：
该程序将两个按元素值递增有序排列的顺序表a和b归并成了一个按元素值递减有序排列的顺序表，且表中允许含有值相同的元素。如上结果所示，按元素值递增有序排列的顺序表a中的元素为{1,2,3,5,7,8,9},顺序表b中的元素为{2,3,4,6,8,9,10},两顺序表归并成了一个按元素值递减有序排列的顺序表后，其中元素为{10,9, 9,8,8,7,6,5,4,3,3,2,2,1}。该归并操作的时间复杂度可看成线性阶O（n），空间复杂度可看成O（n+m）。
