有序表的合并的标准实验报告

软件工程专业类课程实验报告课程名称：学院专业： 学生姓名：学号：指导教师： 日期： 电子科技大学计算机学院实验中心 电 子 科 技 大 学实 验 报 告一、实验室名称：二、实验项目名称： 有序单链表的合并三、实验原理：合并单链表算法的思想描述，因这是本实验重点，这里老是就不写了。四、实验目的：1. 掌握带头结点的单链表建立，插入，删除，查找等基本操作的设计与实现2. 通过单链表的排序编程理解单链表与顺序表操作的区别与联系3. 理解单链表对集合操作的实现4. 掌握有序集合合并的算法设计与存储结构的关系，及时空复杂度与算法性能的关系五、实验内容：1. 编程实现建立单链表的操作2. 编程实现单链表的排序3. 编程实现用单链表合并有序表，使得合并结果有序，但是要求不额外增加内存空间存放合并后的数据，时间开销尽量少六、实验器材（设备、元器件）：电脑1台；XP或者windows 7操作系统Visual studio 2010开发环境七、实验步骤：1. 项目分析与概要设计（1）输入：第一个单链表长度 第一个单链表的所有数据 第二个单链表长度 第二个单链表的所有数据（2）输出：2个有序单链表合并成一个有序表（3）算法分析与概要设计：a). 实现两个有序单链表的合并，首先要保证输入的单链表有序，因此要判断单链表是否有序，如果无序，要先重新对单链表进行排序，然后才能够做合并操作。b). 因为单链表合并后不能增加额外空间，所以原来单链表的结点要串连到新的合并后的单链表中，原来的单链表合并后将不再存在。原来的单链表有2个头结点，合并后只有一个单链表，因此有一个头结点将被释放。这里选择A集合的头结点为合并后的头结点，而原来B集合的头结点将被释放。合并有序单链表的算法流程图见图1所示。2. 数据结构与详细设计（1）数据结构采用带头结点的单链表存储数据，结点结构如下：struct node int value;struct node * next;typedef struct node Node; typedef struct node *ptrList,*List; （2）详细设计根据概要设计流程图，需要实现如下功能：建立带头结点的单链表；判断单链表是否有序；单链表排序；合并有序表使其仍然有序；打印输出单链表的所有数据。下面对这些功能进行详细设计（这里只演示判断单链表是否有序的详细设计过程，余下的请同学们自己完成）a). 建立带头结点的单链表；b). 判断单链表是否有序；输入：带头结点的单链表输出：单链表有序，返回1；单链表无序，返回0算法思想描述：从第二个元素结点开始，与直接前趋比较，如果比直接前趋结点元素值小，则返回无序（0）；否则，访问下一个元素结点。如果直到单链表访问结束，所有元素都大于等于直接前趋，则该单链表是有序表，返回真（1）。算法详细设计流程图见图2所示。c). 单链表排序；d). 合并有序表使其仍然有序；e). 打印输出单链表的所有数据3. 源代码主程序和其他几个功能的源代码这里省略了，只演示如何根据图2的详细设计流程图写源代码b). 判断单链表是否有序源代码；int JudgeListSorted(List header)ptrList p,q;int bSorted=1;p=header-next;if(p=NULL)return bSorted;q=p-next;while(q & bSorted=1)if(p-datadata)p=q;q=q-next;elsebSorted=0;return bSorted;八、实验数据及结果分析：程序测试输入数据分别为下面几种情况：1. 2个链表都不空，但两个链表都有序2. 至少有一个链表空，且不空的链表有序4. 两个链表都不空，且链表无序5. 至少1个链表空，且不空的链表无序6. 一个链表有序，一个链表无序针对上面6种情况，分别测试数据存在下列因素的情况：7. 链表中的数据有负数，正数，08. 链表中的数据有重复数据9. 2个链表都没有重复数据，但是2个链表的交集