数据结构上机题〃1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。

#i nclude"stdio.h"#i nclude"stdlib.h"#defi ne LIST_INIT_SIZE 100#defi ne LISTINCREMENT 10#defi ne OVERFLOW -2#defi ne OK 1typedef struct{ int *elem;int len gth;int listsize;}SqList;int In itList_Sq(SqList &L){L.elem=(i nt *)malloc(LIST_INIT_SIZE*sizeof(i nt)); if(!L.elem)exit(OVERFLOW);L.le ngth=O;L.listsize=LIST_INIT_SIZE;return OK;}void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){int *pa,*pa_last,*pb,*pb_last,*pc;pa=La.elem;pa_last=La.elem+La.le ngth-1;pb=Lb.elem;pb_last=Lb.elem+Lb .len gth-1;Lc」i stsize=Lc .len gth=La .len gth+Lb .len gth;pc=Lc.elem=(i nt*)malloc(Lc.listsize*sizeof(i nt)); if(!Lc.elem)exit(OVERFLOW); while(pa<=pa_last&&pb<=pb_last){if(*pa<=*pb)*pc++=*pa++;else *pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}int In put(SqList &L){ int i,j;int *pa=L.elem;printf("要输入的元素个数：”)；scan f("%d",&i);printf("输入有序序列：");{ scan f("%d",pa++);L.len gth=i;}prin tf("\n");return OK;}int Output(SqList &L){ printf("输出序列：");int i=0;while(i<L.le ngth)pri ntf("%d ", L.elem[i++]);prin tf("\n");return OK;}int mai n(){SqList La,Lb,Lc;In itList_Sq(La);In itList_Sq(Lb);In itList_Sq(Lc);In put(La);In put(Lb);MergeList_Sq(La,Lb,Lc);Output(Lc);return OK;}〃2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出"YSE";否则, 将它插入到序列中使它仍然有序，并输出排序后的序列。

#in clude <stdio.h>#in clude <stdlib.h>#defi ne OK 1#defi ne ERROR -1#defi ne OVERFLOW -2#defi ne LIST_INIT_SIZE 100typedef struct{int *elem;int len gth;int listsize;}SqList;in t In itList_Sq(SqList & L){L.elem=(i nt *)malloc(LIST_INIT_SIZE*sizeof(i nt));if(!L.elem) exit(OVERFLOW);L.le ngth=O;L.listsize=LIST_INIT_SIZE; return OK;}int ListInsert_Sq(SqList &L, int i,int e){if((i<1)||(i>L」e ngth+1)) return ERROR;int *q=&(L.elem[i-1]);for(i nt *p=&(L.elem[L.le ngth-1]);p>=q;--p)*(p+1)=*p;*q=e;++L .len gth;return OK;}int elemfi nd(SqList & L,i nt e){for(i nt i=0;i<L .len gth;i++){ if(e==L.elem[i]) retur n 1;if(i==0&&e<L.elem[i]) {ListI nsert_Sq(L,i+1,e);break;} if(i==L.length-1){ListInsert_Sq(L,i+2,e);break;} if(e>L.elem[i] &&e<L.elem[i+1]) {ListI nsert_Sq(L,i+2,e);break;} } return 0;}void mai n(){SqList L1;int a,i, n;In itList_Sq(L1);printf("输入序列的元素个数：”)；scan f("%d",&n);printf("请输入%d个有序元素：",n);for(i=1;i<=n; i++){sca nf("%d",&a);ListI nsert_Sq(L1,i,a);}printf("请输入要操作的元素:");scan f("%d",&a);if(elemfi nd(L1,a)==1) pri ntf("YES");elsefor(i=0;i<L1.le ngth;i++)prin tf("%d ", L1.elem[i]);prin tf("\n");}〃3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出"NO", 否则，将它从序列中删除它，并输出删除后的序列。

#i nclude"stdio.h"#i nclude"stdlib.h"#defi ne LIST_INIT_SIZE 100#defi ne LISTINCREMENT 10#defi ne OVERFLOW -2#defi ne OK 1typedef struct{ int *elem;int len gth;int listsize;}SqList;int In itList_Sq(SqList &L){ L.elem=(i nt *)malloc(LIST_INIT_SIZE*sizeof(i nt));if(!L.elem)exit(OVERFLOW);L.le ngth=O;L.listsize=LIST_INIT_SIZE;return OK;}int In put(SqList &L){ int i,j;int *pa=L.elem;printf("要输入的元素个数：”)；scan f("%d",&i);printf("输入有序序列：");for(j=0;j<i;j++){ scan f("%d",pa++);L.len gth=i;}prin tf("\n");return OK;}int Output(SqList &L){ printf("输出序列：");int i=0;while(i<L.le ngth)pri ntf("%d ", L.elem[i++]);prin tf("\n");return OK;}int Searcha nddelete(SqList &L,i nt e){ int i;for(i=0;i<L .len gth;i++){int j;for(j=i;j<=L」en gth;j++)L.elem[j]=L.elem[j+1];L.len gth-=1; return 0;}if(i==L.le ngth)pri ntf("No!\n");return 1;}int mai n(){SqList La;In itList_Sq(La);In put(La);int e;printf(”请输入一个数");scan f("%d", &e);Searcha nddelete(La,e);printf("操作后的数据：");Output(La);return OK;}〃4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果是有序的。

#i nclude"stdio.h"#i nclude"stdlib.h"#defi ne OK 1typedef struct LNode{int data;struct LNode* next;}LNode, *Li nkList;int CreateList_L(LinkList &L,int n)// 输入n个元素的值，建立带头结点的单链线性表{int i;Lin kList p,q;L=(L in kList)malloc(sizeof(LNode));L-> next=NULL;q=L;for(i=0;i< n;i++){p=(L in kList)malloc(sizeof(LNode));scan f("%d",&p->data);p-> next=NULL;q=q_>n ext;}return OK;}int outputLi nkList_L(Li nkList &L){Lin kList p;p=L-> next; 〃这里极容易出错写成：p=L，因为表的头指针是没有数据的！while(p){ pri ntf("%d ",p->data);p=p-> next;}prin tf("\n");return OK;}int SortLi nkList_L(Li nkList &L){ Lin kList p,q;q=L->n ext; int t;while(q){ p=q _>n ext;while(p){if((p_>data)<(q_>data)){t=q_>data;q_>data=p_>data;p_>data=t;}p=p->n ext;}q=q_>n ext;}return OK;}int mai n(){ Lin kList L, L2,Lc;int i,j;printf("输入要创建的链表的结点个数：\n");scan f("%d",&i);printf("输入数据：\n");CreateList_L(L,i);SortLi nkList_L(L);printf("排序后输出的数据是：\n");outputL in kList_L(L);return OK;}〃5、从键盘输入一组任意数据，建立一个包含所有输入数据的单向循环链表，并从链表的任意开始，依次输出该链表中的所有结点。