两个有序链表的合并

《两个有序链表的合并》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》实验报告班级：JS001001姓名：周卫华学号：2010300028E-mail:770234417@qq.com◎实验题目:将两个带头结点的有序循环链表合并成一个带头结点的有序循环链表◎实验目的：1.掌握使用visualc++6.0上机调试程序的基本方法。2.掌握线性表的链式存储结构-循环链表的定义及C语言实现。3.掌握线性表在链式存储结构-循环链表中的基本操作如将两个循环链表合并为一个循环链表的操作。◎实验内容：设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不

2、妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的头指针。将这两个链表合并为一个带头结点的有序循环链表。一、需求分析本程序需要实现将两个有序循环链表合成一个有序循环链表的功能，即对这个程序输入两个有序循环链表，该程序输出一个有序循环链表。对于输入的两个循环链表要求是必须是有序非递减的，如1，2，3，5，7符合输入条件，但是3，5，4，7，2，9则不符合输入条件。输入值可以是任意实数。输出的有序循环链表依赖于输入的两个有序循环链表。如输入的两个链表为1，3，4，6，8；2，5，7，9则输出的链表

3、为1，2，3，4，5，6，7，8，9.上面展示了输入正确时的预期输出，当输入不正确时则不能得到正确的输出，如输入1，3，5，4，6；2，5，3，7时输出为1，2，3，5，4，5，3，6，7显然不正确。二、概要设计按照题意，本程序中使用单向循环链表作为存储结构，每一个节点为结构体类型，存放数据和下一个节点的地址。基本流程如下：定义三个该结构体类型的指针变量list1,list2,head；期中list1,list2用来构造存放输入数据的两个循环链表的头指针，head用来作为生成的第三个循环链表的头指针。接下来主函数调

4、用creat()函数并手工输入数据构成两个待合并链表。然后调用print()函数用来打印list1,list2来验证构造的链表正确。链表构造完成后调用mergell()函数来合并list1,list2并存放在head中，最后把head打印出来。本程序主要模块有：主程序模块，构造链表并输入数据模块，打印输出链表模块，合并链表模块。三、详细设计1.元素类型，节点类型和指针类型：元素类型：intnum;intlista=0,listb=0;节点类型：structlist{intnum;structlist*next;};

5、指针类型：structlist*head,*end;structlist*pa,*pb,*pc;structlist*list1,*list2,;2．每个模块的分析：（1）主程序模块：intmain()//主函数{printf("欢迎使用将两个有序循环链表合并成一个有序循环链表程序");structlist*list1,*list2,*head;//定义三个structlist类型的指针变量list1=(structlist*)malloc(sizeof(structlist));list2=(structlist

6、*)malloc(sizeof(structlist));head=(structlist*)malloc(sizeof(structlist));//为list1,list2,head申请空间printf("请按从小到大的顺序输入第一组有序循环链表，以0结束");list1=creat();//调用创建链表的函数printf("输入的这组链表是：");print(list1);//打印第一个链表printf("请按从小到大的顺序输入第二组有序循环链表，以0结束");list2=creat(

7、);//调用创建链表的函数printf("输入的这组链表是：");print(list2);//打印第二个循环链表mergell(list1,list2,head);//调用合并两个链表的函数printf("合并后的有序循环链表为：");print(head->next);//打印合并后的循环链表return0;}（2）构造链表并输入每个数据模块：structlist*creat()//定义创建链表的函数{structlist*p=NULL;structlist*q=NULL;//定义两个活动指针变

8、量head=NULL;intnum;scanf("%d",&num);while(num!=0){p=(structlist*)malloc(sizeof(structlist));//开辟空间p->num=num;if(head==NULL)head=p;elseq->next=p;q=p;scanf("%d",&num);}end=q;//将链表的结尾最