《语言数据结构实验报发告链表的合并.doc》由会员分享，可在线阅读，更多相关《语言数据结构实验报发告链表的合并.doc（8页珍藏版）》请在三一文库上搜索。
1、数据结构实验报告实验题目: 合并两个链表：设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的头指针。请写出将这两个链表合并为一个带头结点的有序循环链表的算法。实验目的：使用顺序表的创建、插入、删除、合并等操作编写关于数据结构的程序。实验内容：写出程序并上机调试、通过。一、需求分析1、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“Please input the first list”时输入第一个链表的元素个数和元素。当出现“Please input the second
2、list”时输入第二个链表的元素个数和元素。然后计算机终端输出合并后的链表。2、输出的形式为两个链表中的元素合并成一个链表并且其中元素按照递增的顺序排列。3、程序执行的命令包括：（1）构造含n个元素的循环链表；（2）输入数据；（3）将输入的数据作成循环链表；（4）合并；（5）输出；（6）结束。4、本程序能将两个链表合并成一个链表。并且合并后的链表中的元素是原来两个链表中的元素按照递增顺序的排列。5、输入及输出示例：例1：Please input the first list41 3 7 9Please input the second list51 2 5 6 8Output the merg
3、elist1 2 3 5 6 7 8 9Press any key to continue 例2：Please input the first list51 2 5 9 11Please input the second list31 2 8Output the mergelist1 2 5 8 9 11Press any key to continue 二 概要设计1基本操作本程序中，用单向有序循环链表作为存储结构。(1)、node *Creatlist (int n)操作结果：创建含有n个元素的有序循环链表。(2)、node* Mergelist(node*la,node*lb)初始条件：
4、循环链表A、B已存在。操作结果：归并递增的链表la和lb，得到链表lc，使lc也为递增循环链表。(3)、void Printlist(node* l)初始条件：链表l已存在操作结果：输出链表l中的元素。2、模块调用图主程序模块创建带头结点的循环链表模块将所有元素插入空链表表尾模块合并链表模块输出链表模块三 详细设计1、结点类型：typedef struct nodeint data;struct node *next;node;2、每个模块：(1) 创建含有n个元素的有序循环链表node *Creatlist (int n)/创建含有n个元素的有序循环链表int i,e;node *p,*l,
5、*list;list=(node*) malloc (sizeof(node);list-data=-1;list-next=list;l=list;/建立头结点并用list记录头结点的位for(i=n;i0;i-)p=(node*) malloc (sizeof(node);/生成新结点scanf(%d,&e);/输入元素值p-data=e;p-next=l-next;l-next=p;l=p;return(list);/返回头结点的位置(2) 归并递增的链表la和lb，得到链表lcnode* Mergelist(node*la,node*lb) /归并递增的链表la和lb，得到链表lc，使
6、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;list3=s;elseif(list1-data=list2-data) s=list1;list1=list1-next;s-next=list3-next;
7、list3-next=s;list3=s;p=list2;list2=list2-next;free(p); elseif(list1-datalist2-data) s=list2;list2=list2-next;s-next=list3-next;list3-next=s;list3=s;/根据元素大小将其依次插入lc中 while(list1!=la)list3-next=list1;list3=list1;list1=list1-next;while(list2!=lb)list3-next=list2;list3=list2;list2=list2-next;/将剩余元素插入lc中
8、list3-next=lc;/ 让lc的尾结点指向lc的头结点使其成为有序循环链表return(lc);/返回合并后的链表lc的头结点(3)、输出链表l中的元素void Printlist(node* l)/输出链表 node *p;p=l-next;while(p!=l)printf(%d ,p-data);p=p-next;printf(n);(4)主函数void main()node *Creatlist (int n);node *Mergelist(node*la,node*lb);void Printlist(node* l);int m,n;node *linklist1,*li
9、nklist2,*linklist3;printf(Please input the first listn);scanf(%d,&m);linklist1=Creatlist (m);printf(Please input the second listn);scanf(%d,&n);linklist2=Creatlist (n);linklist3=Mergelist(linklist1,linklist2);printf(Output the mergelistn);Printlist(linklist3);3、完整函数#include#includetypedef struct nod
10、eint data;struct node *next;node;void main()node *Creatlist (int n);node *Mergelist(node*la,node*lb);void Printlist(node* l);int m,n;node *linklist1,*linklist2,*linklist3;printf(Please input the first listn);scanf(%d,&m);linklist1=Creatlist (m);printf(Please input the second listn);scanf(%d,&n);link
11、list2=Creatlist (n);linklist3=Mergelist(linklist1,linklist2); printf(Output the mergelistn);Printlist(linklist3);node *Creatlist (int n)/创建含有n个元素的有序循环链表int i,e;node *p,*l,*list;list=(node*) malloc (sizeof(node);list-data=-1;list-next=list;l=list;/建立头结点并用list记录头结点的位for(i=n;i0;i-)p=(node*) malloc (siz
12、eof(node);/生成新结点scanf(%d,&e);/输入元素值p-data=e;p-next=l-next;l-next=p;l=p;return(list);/返回头结点的位置node* Mergelist(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
13、-datadata) s=list1;list1=list1-next;s-next=list3-next;list3-next=s;list3=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-datalist2-data) s=list2;list2=list2-next;s-next=list3-next;list3-next=s;list3=s;/根据元
14、素大小将其依次插入lc中 while(list1!=la)list3-next=list1;list3=list1;list1=list1-next;while(list2!=lb)list3-next=list2;list3=list2;list2=list2-next;/将剩余元素插入lc中list3-next=lc;/ 让lc的尾结点指向lc的头结点使其成为有序循环链表return(lc);/返回合并后的链表lc的头结点 void Printlist(node* l)/输出链表 node *p;p=l-next;while(p!=l)printf(%d ,p-data);p=p-next
15、;printf(n);四 使用说明、测试分析及结果1、运行界面：Microsoft Visual C/C+2、测试结果例1：Please input the first list41 3 7 9Please input the second list51 2 5 6 8Output the mergelist1 2 3 5 6 7 8 9Press any key to continue 例2：Please input the first list51 2 5 9 11Please input the second list31 2 8Output the mergelist1 2 5 8 9 11Press any key to continue 五、实验总结教师评语：实验成绩：指导教师签名： 批阅日期： 8