数据结构第一次实验报告.doc

《数据结构》实验报告 班级 姓 名:李维庭 学号:2011302550 E-mail:1510209219@ 日期:2012年10月9日 ◎实验题目: 合并两个链表 ◎实验目的：将给定的两个链表合并为一个链表 ◎实验内容：设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的头指针。请写出将这两个链表合并为一个带头结点的有序循环链表的算法。 一、需求分析 首先建立两个带有头结点的有序循环链表，list1和list2分别为链表的头指针。然后将两个链表合并为一个有序循环链表。 1、输入的形式和输入值的范围：输入值为一切正整数。 2、输出的形式：输出值为合并链表的顺序数据，全为正整数。 3、程序所能达到的功能：将两个有序循环链表合并为一个有序循环链表，并输出。 4、测试数据：根据面板提示输入程序首部定义的有序整数。输出依旧为有序整数。若输入数据为无序则可能出错。 二 概要设计 本程序中用到的抽象数据类型为线性链表。 主程序的流程为建立链表，合并链表以及输出链表。 各程序模块之间互不调用，统一由主函数调用。 三 详细设计 ??实现概要设计中定义的所有数据类型： 结点定义：typedef struct Lnode { int data; struct Lnode *next; //定义指针 }Lnode; //节点 具体操作有： 建立链表：int creat(Lnode *L,int j) { 初始条件：头指针L； 操作结果：以L为头结点的链表； } 合并链表：int add(Lnode *La,Lnode *Lb) { 初始条件：两个含有有序元素的链表； 操作结果：合并为一个有序链表； } 输出链表：int output(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》符合题目的要求。 (二) 概要设计 为了实现上述操作，应以单向循环链表为存储结构。 基本操作： int creat(Lnode *L,int j) { 初始条件：头指针L； 操作结果：以L为头结点的链表； } int add(Lnode *La,Lnode *Lb) { 初始条件：两个含有有序元素的链表； 操作结果：合并为一个有序链表； } int output(Lnode *L) { 初始条件：一个合成的有序链表； 操作结果：将链表元素输出到屏幕上； } 2．本程序包含三个模块： （1）主程序模块； （2）构造链表并输入每个人信息模块； （3）合并链表模块； （4）输出链表模块； （4）模块调用图： ?????????????????? 主程序模块 建立链表并输入每个人信息模块 合并链表模块 输出链表模块 ?(三) 详细设计 1．元素类型，结点类型和指针类型： ?typedef struct Lnode { int data; struct Lnode *next; }Lnode; ???? 2．每个模块的分