循环单链表合并实验报告

实验题目：两个有序循环链表的顺序与逆序合并

实验目的: 掌握循环单链表的建立与输出，掌握循环单链表元素的删除与插入，熟悉C语言

函数调用的相关知识。

实验内容：将两个带头结点的有序循环链表（链表中的元素设为从小到大排列），分别按照

从小到大和从大到小的顺序合并成一个带头结点的有序循环链表并输出。

一．需求分析

1． 本演示程序中，分别要求输入两个链表的长度及每个节点的数据域（注：均要求是

整型数据），数据之间要求以空格分开，输入完毕后键入回车键（程序执行时均会

有输入提醒）。链表长度数据的输入范围为0—4294967295，链表节点数据域的数据

输入范围为-2147483648-2147483647。

2． 本演示程序以用户和计算机的对话方式执行，即在计算机终端显示“提示信息”之

后，由用户在键盘上输入相应的数据与操作。并在选择操作之后，最终输出两个链

表的合并结果，为了体现合并后的链表仍为循环单链表，在一次输出完毕遇到头结

点之后跳过头结点再多输出一位。

3． 程序所能达到的功能包括：

1） 构造循环链表 2）输出循环链表（跳过头结点之后多输出一位）

2） 两个循环链表的顺序合并 4）两个循环链表的逆序合并

4. 输入及输出结果：

链表长度： 4 6

两个链表的数据：1 5 12 78

6 12 56 99 120 156

顺序合并结果为：1 5 12 12 56 78 99 120 156 1

逆序合并结果为：156 120 99 78 56 12 12 5 1 156

二．概要设计

为实现以上操作，应采用循环单链表为存储结构

1本程序主要包括五个函数

1） 主函数

通过对其他各个函数的调用完成对两个循环单链表的初始化以及对两个链表的

顺序与逆序合并并输出。

2） 创建链表

首先创建一个空的循环单链表，然后用尾插法插入新的节点从而创建一个循环单

链表，最后返回头指针。

3） 输出链表

接收主函数传递的链表头指针之后，输出头结点之后的每个节点的数据域，当遇

到头结点之后，跳过头结点，后输出头结点之后的节点的数据。

4） 链表的顺序合并

先定义一个新的头结点，后比较两个链表的数据大小，未达到两个链表末尾时直

接把较小数据插入新合成的链表末尾，当有一个链表比较完之后，把另一个链表

的剩余部分直接插入到新合成的链表尾，并检测到这个剩余未比较完的表尾，让

其指向新合成链表的的头结点，从而构成一个循环链表，并返回头指针。

5） 链表的逆序合并

先创建一个新的空循环单链表，后比较两个链表的数据大小，未达到两个链表末

尾时直接把较小数据用头插法插入到新合成的循环单链表中，当有一个链表比较

完之后，用同样的方法把另一个链表的剩余元素插入到该循环链表中，并返回头

指针。

2.本程序包括三个主要模块

1）主程序模块

2）构造链表及链表的合并与输出模块

3）结点结构单元模块

3.各模块之间的调用关系

结点结构单元模块

三.详细设计

1.元素类型，结点类型和指针类型

typedef struct Lnode

{

int data;

struct Lnode *next;

}Lnode,*Linklist;

2.每个函数的具体分析

1）主函数

int main（）

{

list1=Createlist(n);

list2=Createlist(m);//调用函数创建两个循环单链表

lista=mergelist(list1,list2);

DispList(lista,n+m);

listb=mergelistoppose(list1,list2);

DispList(listb,n+m);//调用函数实现两个链表的顺序与逆序合并并输出

return 0;

}

2)创建循环链表

Createlist(int n)

{

L=(Linklist)malloc(sizeof(Lnode));

L->next=L; //构建一个空的循环单链表

p=(Linklist)malloc(sizeof(Lnode));

p=L;

for(;n>0;n--)

{

s=(Linklist)malloc(sizeof(Lnode));

scanf("%d",&s->data); //输入新建立的节点数据

s->next=p->next;

p->next=s;

} p=s; //尾插法插入新节点

}

3）输出循环链表

DispList(Linklist L,int n)

{

p=L->next;

while(p!=L)

{

printf("%d ",p->data);

p=p->next; //从第一个节点开始逐个输出每一个节点的数据域

}

p=p->next;

printf("%d",p->data); //遇到头结点时跳出，找到头结点之后的节点，并输出其数据 }

4）链表的顺序合并

mergelist(Linklist list1,Linklist list2)

{

p1=list1->next;

p2=list2->next;

while(p1!=list1&&p2!=list2)

{

if(p1->datadata)

q->next=p1,q=p1,p1=p1->next;

else

q->next=p2,q=p2,p2=p2->next; //未达到两个链表末尾时直接比较后把

较小数据插入新合成的链表

}

if(p1==list1)

{

q->next=p2;

while(p2->next!=list2)

p2=p2->next;

p2->next=p;//如果list1先比较完，把list2的剩余元素直接插入链表尾部

}

else

{

如果list2先比较完。把list1的剩余元素直接插入链表尾部，实现过程与if语

句类似

}

}

5）链表的逆序合并

mergelistoppose(Linklist list1,Linklist list2)

{

p=(Linklist)malloc(sizeof(Lnode));

p->next=p; //先建立一个循环单链表

p1=l1=list1，p2=l2=list2；

while(p1!=list1&&p2!=list2)//将两个链表比较后的较小元素头插法插入已建的循环链表中

{

if(p1->datadata)

{

l1=p1,p1=p1->next,l1->next=p->next,p->next=l1;

}

else

{

l2=p2,p2=p2->next,l2->next=p->next,p->next=l2;

}

}

while(p2!=list2)

{

l2=p2,p2=p2->next,l2->next=p->next;,p->next=l2;//如果list1先比较完，把list2的剩

余元素直接插入链表尾部

}

while(p1!=list1)

{

如果list2先比较完。把list1的剩余元素直接插入链表尾部，实现过程与if语句类似

}

}

3.函数调用关系

Createlist mergelist DispList

Mergelistoppose

4. 完整的程序：(见源文件).

四．程序使用说明及测试结果

1.程序使用说明

1）.本程序的执行环境为vc6.0

2）.进入演示程序后即显示提示信息

请分别输入两个链表的数据数目

输入两个链表的长度

请输入第一个链表的数据

输入第一个链表的数据

请输入第二个链表的数据

输入第二个链表的数据

请选择要实现的功能：1.链表的顺序合并 2.链表的逆序合并 选择1或者2

合并结果为：

输出最终结果

3测试结果

按要求分别输入以下数据

链表长度： 4 6

两个链表的数据：1 5 12 78

6 12 56 99 120 156

显示结果为

1.顺序合并结果为：1 5 12 12 56 78 99 120 156 1

2.逆序合并结果为：156 120 99 78 56 12 12 5 1 156

4.运行界面

1）顺序合并

2）逆序合并