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

《数据结构》链表合并实验报告(一)需求分析1、输入的形式和输入值的范围：根据题目要求与提示输入两链表，且数与数之间用空格隔开，输入一行数后用0作为结束符。2、输出的形式：输出合并后的链表。

3、程序所能达到的功能：程序能合并两个有序链表为一个新的有序链表，并以从小到大的顺序输出。4、测试数据：输入一个链表，并用空格将数隔开，每个链表以0作为结束符，如：1390246100输出的链表为：12346910.(二)概要设计为了实现上述操作，应以链表为存储结构。1．基本操作：（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）

模块调用图：

主程序模块输入链表模块输出链表模块合并链表模块(三)详细设计1．存储类型，元素类型，结点类型：structnode{ //构造链表指针结构 intdata; structnode*next;}node,*lnode;元素类型为整形。2．每个模块的分析：（1）主程序模块：voidmain(){ structnode*ahead,*bhead,*abh; ahead=scanff();//调用scanff函数，输入表A bhead=scanff();//调用scanff函数，输入表B abh=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=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){ //定义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)||(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(structnode)structnode{ //构造链表指针结构 intdata; structnode*next;}node,*lnode;intn;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=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){ //定义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)||(pa1==NULL&&pb1!=NULL)); if((pb1!=NULL)&&(pb1->data>pa1->data)&&(pa1->next==NULL)) pa1->next=pb1; return(ah);}voidmain(){ structnode*ahead,*bhead,*abh; ahead=scanff();//调用scanff函数，输入表A bhead=scanff();//调用scanff函数，输入表B abh=insert(ahead,bhead);//调用insert函数，合并两链表 print(abh);//输出合并后的函数}(四)程序使用说明及测试结果1．程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：输入一有序链表，并以0作为结束符，回车；再同样输入另一链表，回车，即得结果2．测试结果：例如：输入：1378024590输出：123457893．调试中的错误及解决办法。(遇到时给出)调试过程中，遇到了许多的问题，如：开始没有设置好结束符，导致输出没结果；然后选定-1为结束符，结果输入的结果有错误；最终只有该0为结束符