《数据结构》实验报告班级：JS001001 姓名：周卫华学号：2010300028E-mail:****************◎实验题目: 将两个带头结点的有序循环链表合并成一个带头结点的有序循环链表◎实验目的：1.掌握使用visual c++6.0上机调试程序的基本方法。
2.掌握线性表的链式存储结构-循环链表的定义及C语言实现。
3.掌握线性表在链式存储结构-循环链表中的基本操作如将两个循环链表合并为一个循环链表的操作。
◎实验内容：设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的头指针。
将这两个链表合并为一个带头结点的有序循环链表。
一、需求分析本程序需要实现将两个有序循环链表合成一个有序循环链表的功能，即对这个程序输入两个有序循环链表，该程序输出一个有序循环链表。
对于输入的两个循环链表要求是必须是有序非递减的，如1，2，3，5，7符合输入条件，但是3，5，4，7，2，9则不符合输入条件。
输入值可以是任意实数。
输出的有序循环链表依赖于输入的两个有序循环链表。
如输入的两个链表为1，3，4，6，8；2，5，7，9则输出的链表为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 用来作为生成的第三个循环链表的头指针。
接下来主函数调用creat()函数并手工输入数据构成两个待合并链表。
然后调用print()函数用来打印list1,list2来验证构造的链表正确。
链表构造完成后调用mergell()函数来合并list1,list2并存放在head中，最后把head打印出来。
本程序主要模块有：主程序模块，构造链表并输入数据模块，打印输出链表模块，合并链表模块。
三、详细设计1.元素类型，节点类型和指针类型：元素类型：int num;int lista=0,listb=0;节点类型： struct list{int num;struct list *next;};指针类型：struct list *head,*end;struct list *pa,*pb,*pc; struct list*list1,*list2,;2．每个模块的分析：（1）主程序模块：int main() //主函数printf(" 欢迎使用将两个有序循环链表合并成一个有序循环链表程序");struct list*list1,*list2,*head;//定义三个struct list类型的指针变量 list1=(struct list *)malloc(sizeof(struct list));list2=(struct list *)malloc(sizeof(struct list));head=(struct list *)malloc(sizeof(struct list));//为list1,list2,head 申请空间printf("\n请按从小到大的顺序输入第一组有序循环链表，以0结束\n"); list1=creat(); //调用创建链表的函数printf("输入的这组链表是：\n");print(list1); //打印第一个链表printf("\n\n请按从小到大的顺序输入第二组有序循环链表，以0结束\n"); list2=creat(); //调用创建链表的函数printf("输入的这组链表是：\n");print(list2); //打印第二个循环链表mergell (list1,list2,head) ; //调用合并两个链表的函数printf("\n\n合并后的有序循环链表为：\n");print(head->next);//打印合并后的循环链表return 0;}（2）构造链表并输入每个数据模块：struct list *creat() //定义创建链表的函数{struct list*p=NULL;struct list*q=NULL; //定义两个活动指针变量head=NULL;int num;scanf("%d",&num);while(num!=0){p=(struct list *)malloc(sizeof (struct list)); //开辟空间p->num=num;if(head==NULL)head=p;elseq->next=p;q=p;scanf("%d",&num);}end=q; //将链表的结尾最后一个结点赋给endend->next=head; //让最后一个结点的的下个结点的地址不为空而指向头指针return(head); //返回新建链表的头指针}（3）打印已经构造完成的链表模块void print(struct list*head) //定义打印循环链表的函数{struct list*r=head; //定义活动指针变量以输出各节点数据do{printf("%d ",r->num);r=r->next;}while(r!=head); //当活动指针重新指向头结点时，循环结束}（4）合并两个有序循环链表模块struct list *mergell(struct list *la,struct list *lb,struct list * lc) //定义合并函数{struct list *pa,*pb,*pc; //定义三个活动指针变量分别指向la,lb,lcint lista=0,listb=0;pc=lc;pa=la;pb=lb; //为pa,pb,pc赋值while(((pa!=la)||(lista==0))&&((pb!=lb)||(listb==0)))//使用while循环语句{if(pa->num<=pb->num){pc->next=pa;pc=pa;pa=pa->next;lista=1;}else{pc=pb;pb=pb->next;listb=1;}}if(pa!=la) //如果lb数据已经完成排序而la还有数据未排，则把la未排数据插入到lc后面{while(pa!=la){pc->next=pa;pc=pa;pa=pa->next;}pc->next=lc->next;}else //如果la数据已经完成排序而lb还有数据未排，则把lb未排数据插入到lc后面{while(pb!=lb){pc->next=pb;pc=pb;pb=pb->next;}pc->next=lc->next;}}函数调用关系如下所示：main(){creat();print();creat();print();mergell();print();}3.完整的程序见附件。
四、程序使用说明及测试结果1.程序使用说明（1）本程序的运行环境是codeblocks(2)当程序运行后，界面出现“请按从小到大的顺序输入第一组有序循环链表，以0结束”字样，这时，将第一组有序循环链表输入，并在有效数据后面添加0作为结束标志。
接着界面出现“请按从小到大的顺序输入第二组有序循环链表，以0结束”按照同样的方法输入即可。
输入完毕后程序会自动输出合并后的有序循环链表。
2.测试结果当第一组链表为：1，3，5，6，9第二组链表为3，4，5，7，8时，该程序输出为1，3，3，4，5，5，6，7，8，93调试过程中遇到的问题及解决办法在调试发现输出有乱数的问题，后来发现当定义一个结构体指针变量时必须给它申请一个空间才能实际应用，即struct list*list1,*list2,*head;//定义三个struct list类型的指针变量list1=(struct list *)malloc(sizeof(struct list));list2=(struct list *)malloc(sizeof(struct list));head=(struct list *)malloc(sizeof(struct list));另外我对循环结构的应用不够灵活，尤其对循环终止条件的确定比较弱。
4运行界面如下所示五、实验总结在刚开始进行编程时，由于大脑中没有形成具体的思路，导致思维比较混乱，到后来我静下心来，采用从上到下的编程方法，将一个大问题分解成几个小问题进行逐一突破，例如我编写了creat（）函数，print()函数，mergell（）函数供main()函数调用，然后对具体的每一个函数进行构思，这样一来我的思路就明确了。
不过在这种情况下必须要对函数调用，数据传输，形参实参关系比较理解。
以前总是觉得编程算法知道就行了，上机只不过是将它代码化，可是当真的做实验的时候，才发现任何事情都是说起来容易做起来难，不过我相信只要肯下工夫，肯练，肯思考，一定会编出优秀的程序！。