文档库

最新最全的文档下载
当前位置:文档库 > 两个有序链表的合并

两个有序链表的合并

《数据结构》实验报告

班级:JS001001 姓名:周卫华学号:2010300028 E-mail:770234417@http://www.wendangku.net/doc/52d32aa9284ac850ad024219.html

◎实验题目: 将两个带头结点的有序循环链表合并成一个带头结点的有序循环链表

◎实验目的: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() //主函数