链表合并实验报告.pdf

《数据结构》实验报告

◎实验题目:实现两个有序循环链表的合并

◎实验目的：掌握链表的建立、遍历以及数据的插入，加深对链表的理解。

◎实验内容：设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数

据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个

链表的头指针。请写出将这两个链表合并为一个带头结点的有序循环链表的算法。

一、需求分析

1、输入：该实验需要建立循环链表，以及读入数据，输出数据，并实现合并。该链表输入

为整数形式，输入值的范围为整个整数域。

2、输出：而输出的形式为整数。

3、程序功能：该程序实现了循环链表的建立，读入和输出数据，主要功能为实现了两个有

序循环链表的合并。

4、程序执行命令：（1）创建链表（2）输入数据（3）合并链表（4）输出合并后链表（5）

结束

5、测试数据：假设第一个链表的输入数据个数为5，其分别为1、3、5、7、9，第二个链表

的输入数据个数为3个，其分别为7、9、10，则合并后应输出结果：135779910。

二概要设计

为了实现上述操作，应以单向循环链表为存储结构。

本程序的主程序的流程为：

输入第一个链表数

据个数，并输入数

据，做输出展示

输入第一个链表数

据个数，并输入数

据，做输出展示

合并两链表并将合并

后结果输出

本程序的调用函数有创建链表函数create,输出函数displist,以及合并函数add三个模块,

其中这三个函数都在主函数中被调用，三个调用函数为平行关系。

三详细设计

1．元素类型，结点类型和指针类型：

typedefintelemtype;

typedefstructlnode

{

elemtypedata;

structlnode*next;

}linklist;

linklist*s,*r;linklist*list1,*list2,*list3;

2．每个模块的分析：

（1）主程序模块：

main()

{

linklist*l1,*l2,*l3;

inti,x,n;

请输入要建立的链表节点个数：请输入要建立的链表节点个数：

create(l1,n);

displist(l1);

getch();

请输入要建立的链表节点个数：请输入要建立的链表节点个数：

create(l2,n);

displist(l2);

getch();

add(l1,l2,l3);

合并后链表合并后链表

displist(l3);

getch();

return0;

}

（2）链表创建并输入数据

create(linklist*l,intn)

{

linklist*s,*r;

inti;

l=(linklist*)malloc(sizeof(linklist));

l-next=NULL;

r=l;

for(i=0;in;i++)

{

s=(linklist*)malloc(sizeof(linklist));

请输入新节点数据请输入新节点数据

r-next=s;

r=s;