数据结构第一次实验报告

《数据结构》实验报告班级:10011107姓名:李维庭学号:2011302550E-mail:1510209219@日期:2012年10月9日◎实验题目:合并两个链表◎实验目的：将给定的两个链表合并为一个链表◎实验内容：设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的头指针。请写出将这两个链表合并为一个带头结点的有序循环链表的算法。一、需求分析首先建立两个带有头结点的有序循环链表，list1和list2分别为链表的头指针。然后将两个链表合并为一个有序循环链表。1、输入的形式和输入值的范围：输入值为一切正整数。2、输出的形式：输出值为合并链表的顺序数据，全为正整数。3、程序所能达到的功能：将两个有序循环链表合并为一个有序循环链表，并输出。4、测试数据：根据面板提示输入程序首部定义的有序整数。输出依旧为有序整数。若输入数据为无序则可能出错。二概要设计本程序中用到的抽象数据类型为线性链表。主程序的流程为建立链表，合并链表以及输出链表。各程序模块之间互不调用，统一由主函数调用。三详细设计

实现概要设计中定义的所有数据类型：结点定义：typedefstructLnode{ intdata; structLnode*next;//定义指针}Lnode;//节点具体操作有：建立链表：intcreat(Lnode*L,intj){初始条件：头指针L；操作结果：以L为头结点的链表；}合并链表：intadd(Lnode*La,Lnode*Lb){初始条件：两个含有有序元素的链表；操作结果：合并为一个有序链表；}输出链表：intoutput(Lnode*L){初始条件：一个合成的有序链表；合并链表主函数操作结果：将链表元素输出到屏幕上；主函数}画出函数的调用关系：

建立链表 输出链表四使用说明、测试分析及结果1、打开程序，编译，连接以及运行。之后根据提示输入数据，点击回车键。2、测试结果与分析：在输出的链表数据中可以看到输入两个链表的数据有序排列。3、调试过程中遇到的问题是如何解决提以及对设计与实现的回顾讨论和分析：在调试时出现该地址不能释放的信息，经检查是由于人为释放了定义的地址所致，之后便可以成功运行。4、运行界面：为c程序原始的运行界面。五、实验总结1、算法的时空分析和改进设想。示例：(一)需求分析1．本程序中，第一个链表的数据应为I个，第二个链表的数据是J个。输入后由循环依次连接到链表中。2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（每个链表的数据）由程序自动链接。合并之后输出结果。3．程序执行的命令包括：（1）建立链表；（2）输入数据；（3）合并链表；（4）输出链表；（5）结束。4．测试数据I=3，J=5时输入链表为数据为《1,3,5》，《2,3,4,6,9》输出结果为《1,2,3,3,4,5,6,9》符合题目的要求。(二)概要设计为了实现上述操作，应以单向循环链表为存储结构。基本操作：intcreat(Lnode*L,intj){初始条件：头指针L；操作结果：以L为头结点的链表；}intadd(Lnode*La,Lnode*Lb){初始条件：两个含有有序元素的链表；操作结果：合并为一个有序链表；}intoutput(Lnode*L){初始条件：一个合成的有序链表；操作结果：将链表元素输出到屏幕上；}2．本程序包含三个模块：（1）主程序模块；（2）构造链表并输入每个人信息模块；（3）合并链表模块；（4）输出链表模块；（4）模块调用图：

主程序模块建立链表并输入每个人信息模块合并链表模块输出链表模块

(三)详细设计1．元素类型，结点类型和指针类型：

typedefstructLnode{ intdata; structLnode*next;}Lnode;

2．每个模块的分析：（1）主程序模块：intmain(){ Lnode*La,*Lb; Lnodelist1,list2; La=&list1; Lb=&list2; printf("请输入链表La数据：\n"); creat(La,I);printf("请输入链表Lb数据：\n"); creat(Lb,J);printf("链表La数据：\n");printf("链表Lb数据：\n");add(La,Lb);printf("合成链表数据：\n"); output(La); return1;}（2）建立链表并输入每个人信息模块；intcreat(Lnode*L,intj){ inti; Lnode*p,*q; q=L; for(i=0;i<j;i++) {p=(Lnode*)malloc(sizeof(Lnode));if(!p)return0;scanf("%d",&p->data);q->next=p;q=p; } q->next=L; return1;}合并链表模块intadd(Lnode*La,Lnode*Lb){ Lnode*p,*q,*r; p=La->next; q=Lb->next; r=La; for(;(p!=La)&&(q!=Lb);) { if((p->data)<(q->data)) { r->next=p; r=p; p=p->next; } else { r->next=q; r=q; q=q->next; } } if(p!=La)r->next=p; else for(;q!=Lb;r=q,q=q->next) r->next=q; r->next=La; return1;}输出链表模块intoutput(Lnode*L){ Lnode*p; p=L->next; for(;p!=L;p=p->next) { printf("%d",p->data); } printf("\n"); return1;}（5）函数调用关系图main()creat()add（）output（）3．完整的程序：(见源文件).(四)程序使用说明及测试结果1．程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入3个链表La数据并按回车键结束：135请输入5个链表Lb数据并按回车键结束：234692．测试结果合成链表数据：12334569Pressanykeytocontinue3．VC6.0原始运行界面（五）、实验总结(实验心得)在本次试验中我总共花了2个小时来完成上机实验，其中有半个小时左右的时间在纸上设计