资源描述:
《北理工数据结构上机实验报告2》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、数据结构上级实验报告1+——归并顺序表(选作)一实验目的归并顺序表二实验内容请按以下要求编程实现:①从键盘输入两个升序排列的整数序列linka和linkb,每个序列以输入0为结束标记。②将链表linka和linkb归并为linkc,linkc仍然为升序排列。归并完成后,linka和linkb为空表。输出linkc。③对linkc进行处理,保持升序不变,删除其中重复的整数,对重复的整数只保留一个,输出删除重复整数后的链表。例如:linka输入为:10203040500linkb输入为:15202530354045500归并后的linkc为:1
2、0152020253030354040455050删除重复后的linkc为:101520253035404550三程序设计(1)概要设计抽象数据类型:typedefstruct{int*elem;intlength;intlistsize;}SqList;宏:#defineLIST_INIT_SIZE100#defineLISTINCREMENT10主函数流程与各函数模块调用关系:创建头结点=〉InitList初始化顺序表La,Lb=〉ListCreate建立顺序表La=〉OutPutList输出顺序表La=〉ListCreate建立顺序表
3、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*size
4、of(int));if(!L.elem)exit(0);L.listsize=LIST_INIT_SIZE;L.length=0;printf("ListInitializedSucessfully!");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.l
5、istsize){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!");return1;}删除顺序表重复数据算法实现:intListDelete
6、(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(i<1
7、
8、i>L.length+1)return0;if(L.le
9、ngth>=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=
10、0,ai,bj;intLa_len,Lb_len;La_len=La.length;Lb_len=Lb.length;while((i