北理工数据结构上机实验报告2

数据结构上级实验报告1+——归并顺序表（选作）一实验目的归并顺序表二实验内容请按以下要求编程实现：①从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。②将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka和linkb为空表。输出linkc。③对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。例如：linka输入为：10203040500linkb输入为：15202530354045500归并后的linkc为：10152020253030354040455050删除重复后的linkc为：101520253035404550三程序设计(1)概要设计抽象数据类型：typedefstruct{int*elem;intlength;intlistsize;}SqList;宏：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10主函数流程与各函数模块调用关系：创建头结点=〉InitList初始化顺序表La，Lb=〉ListCreate建立顺序表La=〉OutPutList输出顺序表La=〉ListCreate建立顺序表Lb=〉OutPutList输出顺序表Lb=〉MergeList融合La，Lb为Lc=〉OutPutList输出顺序表Lc=〉ListDelete对Lc进行删除重复数据操作=〉OutPutList输出顺序表LcvoidMergeList(SqListLa,SqListLb,SqList&Lc)函数中调用intListInsert(SqList&L,inti,inte)实现插入数据的需求(2)详细设计初始化顺序表算法实现：intInitList(SqList&L){L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)exit(0);L.listsize=LIST_INIT_SIZE;L.length=0;printf(ListInitializedSucessfully!\n);return1;}创建顺序表算法实现：intListCreate(SqList&L){intinsert,i=0;int*newbase,*q;q=(int*)malloc(LIST_INIT_SIZE*sizeof(int));scanf(%d,&insert);for(;insert!=0;){if(L.length=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i]);*q=insert;++L.length;++i;scanf(%d,&insert);}printf(ListCreatedSucessfully!\n);return1;}删除顺序表重复数据算法实现：intListDelete(SqList&L){inti=0,j=1,*p,*q;while(i!=L.length-1){if(L.elem[i]==L.elem[j]){p=&(L.elem[j]);q=&(L.elem[L.length-1]);for(++p;p=q;++p){*(p-1)=*p;}--L.length;}else{i++;j++;}}return1;}插入顺序表算法实现：intListInsert(SqList&L,inti,inte){int*newbase,*q;if(i1||iL.length+1)return0;if(L.length=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);*q=e;++L.length;return1;}按升序合并顺序表算法实现：voidMergeList(SqListLa,SqListLb,SqList&Lc){InitList(Lc);inti=0,j=0,k=0,ai,bj;intLa_len,Lb_len;La_len=La.length;Lb_len=Lb.length;while((iLa_len)&&(jLb_len)){ai=La.elem[i];bj=Lb.elem[j];if(ai=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(iLa_len){ai=La.elem[i];ListInsert(Lc,++k,ai);i++;}while(jLb_len){bj=Lb.elem[j];ListInsert(Lc,++k,bj);j++;}Lc.length=k;}输出顺序表算法实现：voidOutPutList(SqListL){inti=0;while(iL.length){printf(%d-,L.elem[i]);i++;}printf(-end\n);}主函数代码实现：intmain(){SqListLa,Lb,Lc;printf(InitializedList!\n);InitList(La);InitList(Lb);printf(InputListA:\n);ListCreate(La);printf(\nCheckListA:\n);OutPutList(La);printf(\nInputListB:\n);ListCreate(Lb);printf(\nCheckListB:\n);OutPutList(Lb);MergeList(La,Lb,Lc);printf(\nThisistheListCwithoutchange:\n);OutPutList(Lc);ListDelete(Lc);printf(\nThisistheListCafterchange:\n);OutPutList(Lc);system(pause);}四程序调试分析1编写merge函数是，由于舍弃了书中的GetElem函数，转而直接使用L.elem[i]访问数据，导致计数器i以及j都没有进行自增操作，merge函数陷入死循环无法继续下一个函数的实现。2五用户使用说明双击exe程序后，软件提示La以及Lb已经初始化完成，并提示输入La的数据。数据个数无上限，数据与数据之间用空格分隔，数字0表示输入完毕，La数据必需按照升序排列；重复对Lb进行上述操作；软件输出单纯升序排列的Lc以及删除重复操作后的Lc。六程序运行结果七程序清单#includestdio.h#includestdlib.h#defineLIST_INIT_SIZE100//顺序表初始化值#defineLISTINCREMENT10//顺序表长度增量typedefstruct{//定义顺序表int*elem;intlength;intlistsize;}SqList;intInitList(SqList&L){//初始化顺序表L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)exit(0);L.listsize=LIST_INIT_SIZE;L.length=0;printf(ListInitializedSucessfully!\n);return1;}intListCreate(SqList&L){//顺序表的建立，数值的输入intinsert,i=0;int*newbase,*q;q=(int*)malloc(LIST_INIT_SIZE*sizeof(int));scanf(%d,&insert);for(;insert!=0;){if(L.length=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i]);*q=insert;++L.length;++i;scanf(%d,&insert);}printf(ListCreatedSucessfully!\n);return1;}intListDelete(SqList&L){//删除重复的数据元素inti=0,j=1,*p,*q;while(i!=L.length-1){if(L.elem[i]==L.elem[j]){p=&(L.elem[j]);q=&(L.elem[L.length-1]);for(++p;p=q;++p){*(p-1)=*p;}--L.length;}else{i++;j++;}}return1;}intListInsert(SqList&L,inti,inte)//在i前插入制定的数据元素e{int*newbase,*q;if(i1||iL.length+1)return0;if(L.length=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);L.elem=newbase;L.listsize+=LISTINCREMENT;}q=&(L.elem[i-1]);*q=e;++L.length;return1;}voidMergeList(SqListLa,SqListLb,SqList&Lc){//升序融合La，Lb为LcInitList(Lc);inti=0,j=0,k=0,ai,bj;intLa_len,Lb_len;La_len=La.length;Lb_len=Lb.length;while((iLa_len)&&(jLb_len)){ai=La.elem[i];bj=Lb.elem[j];if(ai=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(iLa_len){ai=La.elem[i];ListInsert(Lc,++k,ai);i++;}while(jLb_len){bj=Lb.elem[j];ListInsert(Lc,++k,bj);j++;}Lc.length=k;}voidOutPutList(SqListL){//输出顺序表inti=0;while(iL.length){printf(%d-,L.elem[i]);i++;}printf(-end\n);}intmain(){SqListLa,Lb,Lc;printf(InitializedList!\n);InitList(La);InitList(Lb);//初始化顺序表printf(InputListA:\n);ListCreate(La);//输入La表的数值printf(\nCheckListA:\n);OutPutList(La);//输出顺序表printf(\nInputListB:\n);ListCreate(Lb);//输入Lb表的数值printf(\nCheckListB:\n);OutPutList(Lb);//输出顺序表MergeList(La,Lb,Lc);//升序融合La