数据结构实验报告 合并链表

《数据结构实验报告 合并链表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验报告班级：10020801姓名：吴亮学号：2008302651电话：15191416617日期：2009.11.7(一)需求分析1、输入的形式和输入值的范围：根据题目要求与提示输入两链表，且数与数之间用空格隔开，输入一行数后用0作为结束符。2、输出的形式：输出合并后的链表。3、程序所能达到的功能：程序能合并两个有序链表为一个新的有序链表，并以从小到大的顺序输出。4、测试数据：输入一个链表，并用空格将数隔开，每个链表以0作为结束符，如：1390246100输出的链表为：12346910.(二)概要设计为了实现上述操作，应以链表为存储结构。1． 

2、 基本操作：（1）.structnode*scanff()初始条件：structnode*scanff形式的指针存在；操作结果：建立链表函数，返回建立好的链表的头结点head。（2）.voidprint(structnode*head)初始条件：structnode*head为一已知链表的头结点；操作结果：输出该链表。（3）.structnode*insert(structnode*ah,structnode*bh)初始条件：ah，bh两链表已知，且有序；操作结果：合并ah，bh为一新的有序链表。2．本程序包含二个模块：（1）        主程序模块；（2

3、）      输入，输出，合并链表函数模块（3）        模块调用图：                  主程序模块输入链表模块输出链表模块合并链表模块(三)详细设计1．  存储类型，元素类型，结点类型：structnode{//构造链表指针结构intdata;structnode*next;}node,*lnode;元素类型为整形。2．  每个模块的分析：（1）        主程序模块：voidmain(){structnode*ahead,*bhead,*abh;ahead=scanff();//调用scanff函数，输入表Abhead=scan

4、ff();//调用scanff函数，输入表Babh=insert(ahead,bhead);//调用insert函数，合并两链表print(abh);//输出合并后的函数}（2）输入函数模块structnode*scanff(){//建立链表函数，返回建立好的链表的头结点structnode*p1;structnode*head;n=0;structnode*p2;p1=p2=(structnode*)malloc(len);scanf("%d",&p1->data);head=NULL;while(p1->data!=0){n++;if(n==1)head

5、=p1;elsep2->next=p1;p2=p1;p1=(structnode*)malloc(len);scanf("%d",&p1->data);}p2->next=NULL;return(head);}输出函数模块voidprint(structnode*head){//建立输出函数structnode*p;p=head;if(p!=NULL)do{printf("%d",p->data);p=p->next;}while(p!=NULL);}合并链表函数模块structnode*insert(structnode*ah,structnode*bh)

6、{//定义insert函数，用来合并两个链表structnode*pa1,*pb1,*pa2,*pb2;pa2=pa1=ah;pb2=pb1=bh;do{while((pb1->data>pa1->data)&&(pa1->next!=NULL)){pa2=pa1;pa1=pa1->next;}if(pb1->data<=pa1->data){if(ah==pa1)ah=pb1;else{pa2->next=pb1;pb1=pb1->next;pb2->next=pa1;pa2=pb2;pb2=pb1;}}}while((pa1->next!=NULL)

7、

8、

9、(pa1==NULL&&pb1!=NULL));if((pb1!=NULL)&&(pb1->data>pa1->data)&&(pa1->next==NULL))pa1->next=pb1;return(ah);}3）        函数调用关系图main()structnode*scanff()structnode*insert(structnode*ah,structnode*bh)voidprint(structnode*head)3．  完整的程序：#include"stdio.h"#include"malloc.h"#definelensizeof

10、(structnode)structnode{//构