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

《有序表的合并的标准实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、软件工程专业类课程实验报告课程名称：学院专业：学生姓名：学　　号：指导教师：日　　期：电子科技大学计算机学院实验中心电子科技大学实验报告一、实验室名称：二、实验项目名称：有序单链表的合并三、实验原理：合并单链表算法的思想描述，因这是本实验重点，这里老是就不写了。四、实验目的：1.掌握带头结点的单链表建立，插入，删除，查找等基本操作的设计与实现2.通过单链表的排序编程理解单链表与顺序表操作的区别与联系3.理解单链表对集合操作的实现4.掌握有序集合合并的算法设计与存储结构的关系，及时空复杂度与算法性能

2、的关系五、实验内容：1.编程实现建立单链表的操作2.编程实现单链表的排序3.编程实现用单链表合并有序表，使得合并结果有序，但是要求不额外增加内存空间存放合并后的数据，时间开销尽量少六、实验器材（设备、元器件）：电脑1台；XP或者windows7操作系统Visualstudio2010开发环境七、实验步骤：1.项目分析与概要设计（1）输入：第一个单链表长度第一个单链表的所有数据第二个单链表长度第二个单链表的所有数据（2）输出：2个有序单链表合并成一个有序表（3）算法分析与概要设计：a).实现两个有序

3、单链表的合并，首先要保证输入的单链表有序，因此要判断单链表是否有序，如果无序，要先重新对单链表进行排序，然后才能够做合并操作。b).因为单链表合并后不能增加额外空间，所以原来单链表的结点要串连到新的合并后的单链表中，原来的单链表合并后将不再存在。原来的单链表有2个头结点，合并后只有一个单链表，因此有一个头结点将被释放。这里选择A集合的头结点为合并后的头结点，而原来B集合的头结点将被释放。合并有序单链表的算法流程图见图1所示。2.数据结构与详细设计（1）数据结构采用带头结点的单链表存储数据，结点结构

4、如下：structnode{intvalue;structnode*next;};typedefstructnodeNode;typedefstructnode*ptrList,*List;（2）详细设计根据概要设计流程图，需要实现如下功能：建立带头结点的单链表；判断单链表是否有序；单链表排序；合并有序表使其仍然有序；打印输出单链表的所有数据。下面对这些功能进行详细设计（这里只演示判断单链表是否有序的详细设计过程，余下的请同学们自己完成）a).建立带头结点的单链表；b).判断单链表是否有序；输入：

5、带头结点的单链表输出：单链表有序，返回1；单链表无序，返回0算法思想描述：从第二个元素结点开始，与直接前趋比较，如果比直接前趋结点元素值小，则返回无序（0）；否则，访问下一个元素结点。如果直到单链表访问结束，所有元素都大于等于直接前趋，则该单链表是有序表，返回真（1）。算法详细设计流程图见图2所示。c).单链表排序；d).合并有序表使其仍然有序；e).打印输出单链表的所有数据3.源代码主程序和其他几个功能的源代码这里省略了，只演示如何根据图2的详细设计流程图写源代码b).判断单链表是否有序源代码；

6、intJudgeListSorted(Listheader){ptrListp,q;intbSorted=1;p=header->next;if(p==NULL)returnbSorted;q=p->next;while(q&&bSorted==1){if(p->datadata){p=q;q=q->next;}else{bSorted=0;}}returnbSorted;}八、实验数据及结果分析：程序测试输入数据分别为下面几种情况：1.2个链表都不空，但两个链表都有序2.至少有一个链表空

7、，且不空的链表有序4.两个链表都不空，且链表无序5.至少1个链表空，且不空的链表无序6.一个链表有序，一个链表无序针对上面6种情况，分别测试数据存在下列因素的情况：7.链表中的数据有负数，正数，08.链表中的数据有重复数据9.2个链表都没有重复数据，但是2个链表的交集不空最好通过表格的形式将测试情况都展示出来，并分析和总结你的程序是否能够正确处理这些情况九、总结及心得体会：十、对本实验过程及方法、手段的改进建议：报告评分：指导教师签字：