【c语言《数据结构》实验报告】链表的合并

《【c语言《数据结构》实验报告】链表的合并》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》实验报告◎实验题目:合并两个链表：设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的头指针。请写出将这两个链表合并为一个带头结点的有序循环链表的算法。◎实验目的：使用顺序表的创建、插入、删除、合并等操作编写关于数据结构的程序。◎实验内容：写出程序并上机调试、通过。一、需求分析1、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“Pleaseinputthefirstlist”时输入第一个链表的元素个数和元素。当出现“Plea

2、seinputthesecondlist”时输入第二个链表的元素个数和元素。然后计算机终端输出合并后的链表。2、输出的形式为两个链表中的元素合并成一个链表并且其中元素按照递增的顺序排列。3、程序执行的命令包括：（1）构造含n个元素的循环链表；（2）输入数据；（3）将输入的数据作成循环链表；（4）合并；（5）输出；（6）结束。4、本程序能将两个链表合并成一个链表。并且合并后的链表中的元素是原来两个链表中的元素按照递增顺序的排列。5、输入及输出示例：例1：Pleaseinputthefirstlist41379Pleaseinputthesecondlist

3、512568Outputthemergelist12356789Pressanykeytocontinue例2：Pleaseinputthefirstlist5125911Pleaseinputthesecondlist31288Outputthemergelist1258911Pressanykeytocontinue二概要设计1．基本操作本程序中，用单向有序循环链表作为存储结构。(1)、node*Creatlist(intn)操作结果：创建含有n个元素的有序循环链表。(2)、node*Mergelist(node*la,node*lb)初始条件：循环

4、链表A、B已存在。操作结果：归并递增的链表la和lb，得到链表lc，使lc也为递增循环链表。(3)、voidPrintlist(node*l)初始条件：链表l已存在操作结果：输出链表l中的元素。2、模块调用图主程序模块创建带头结点的循环链表模块将所有元素插入空链表表尾模块合并链表模块输出链表模块三详细设计1、结点类型：typedefstructnode{intdata;structnode*next;}node;2、每个模块：(1)创建含有n个元素的有序循环链表node*Creatlist(intn)//创建含有n个元素的有序循环链表{inti,e;no

5、de*p,*l,*list;list=(node*)malloc(sizeof(node));list->data=-1;list->next=list;l=list;//建立头结点并用list记录头结点的位for(i=n;i>0;i--){p=(node*)malloc(sizeof(node));//生成新结点8scanf("%d",&e);//输入元素值p->data=e;p->next=l->next;l->next=p;l=p;}return(list);//返回头结点的位置}(2)归并递增的链表la和lb，得到链表lcnode*Mergeli

6、st(node*la,node*lb)//归并递增的链表la和lb，得到链表lc，使lc也为递增循环链表{node*list1,*list2,*list3,*lc,*s,*p;list1=la->next;list2=lb->next;lc=la;list3=lc;lc->next=lc;//将la的头结点作为lc的头结点while(list1!=la&&list2!=lb){if(list1->datadata){s=list1;list1=list1->next;s->next=list3->next;list3->next=s;li

7、st3=s;}elseif(list1->data==list2->data){s=list1;list1=list1->next;s->next=list3->next;list3->next=s;list3=s;p=list2;list2=list2->next;free(p);}elseif(list1->data>list2->data){s=list2;list2=list2->next;8s->next=list3->next;list3->next=s;list3=s;}}//根据元素大小将其依次插入lc中while(list1!=la){

8、list3->next=list1;list3=list1;list1=list