数据结构试验二最终报告

《数据结构试验二最终报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机与信息学院数据结构实验报告专业班级学生姓名及学号课程教学班号任课教师胡学钢实验指导教师张晶实验地点学年第二学期实验序号及名称：实验二循环链表、双链表及链表应用实验一、实验目的和要求∶(1)理解单循环链表及双循环链表的特点。(2)掌握这两种结构的算法设计。(3)运用链表存储数据并设计有关算法。(4)理解头结点、头指针概念以及设置头结点的优点二、实验环境和仪器设备∶WindowsxpDevC++/UbuntuGnuC++三、相关资料和参考文献(教材和实验指导书以外)∶（无）四、实验任务∶<1>设计算法依次访问无

2、头结点的单循环链表的各结点。<2>设计算法以判断一个带头结点的单循环链表是否满足这样的条件<3>利用递增有序的单循环链表表示集合，分别求两个链表表示的集合的交、并集所构成的链表。<4>编写算法以构造带头结点的双循环链表。<5>编写算法以判断一个带头结点的双循环链表是否是对称的。五、实验内容（步骤）∶<1>设计循环链表、双链表、链表的数据结构，并根据数据结构设计算法实现。<2>编写源代码<3>上机调试<4>总结六、完整的实验结果记录∶<1>设计算法依次访问无头结点的单循环链表的各结点。第一组数据：链表元素为（1，2

3、，3，4，5，6，7，8，9，10，20，30，40，50，60）第二组数据：链表元素为（10，20，30，40，50，60，70，80，90，100）<2>设计算法以判断一个带头结点的单循环链表是否满足这样的条件：其中每个结点的元素值与其序号的差的绝对值不大于３。若成立，返回TRUE，否则返回FALSE。第一组数据：链表元素为（1，2，3，4，5，6，7，8，9，10，12，13，15，16，18）第二组数据：链表元素为（1，2，3，4，5，6，7，8，9，10，11，12，13，15，20，18）<3>利用递

4、增有序的单循环链表表示集合，分别求两个链表表示的集合的交、并集所构成的链表。第一组第一个链表元素为（1，3，6，10，15，16，17，18，19，20）第二个链表元素为（1，2，3，4，5，6，7，8，9，10，18，20，30）第二组第一个链表元素为（1，3，6，10，15，16，17，18，19，20）第二个链表元素为（2，4，5，7，8，9，12，22）第三组第一个链表元素为（）第二个链表元素为（1，2，3，4，5，6，7，8，9，10）<4>编写算法以构造带头结点的双循环链表。第一组数据：链表元素为（1

5、，2，3，4，5，6，7，8，9，10）第二组数据：链表元素为（10，30，40，55，60，70，88，99，100）<5>编写算法以判断一个带头结点的双循环链表是否是对称的，若成立，返回TRUE，否则返回FALSE。第一组数据：链表元素为（1，2，3，4，5，4，3，2，1）第二组数据：链表元素为（1，2，3，4，5，5，4，3，2，1）第三组数据：链表元素为（1，2，3，4，5，6，3，2，1）第四组数据：链表元素为（1，2，3，4，5，5，6，4，3，2，1）七、实验结果分析∶任务一对于无头结点的循环链表

6、，通过设置计数器，来与链表结点数判断是否遍历完成。任务二对于有头结点的循环链表，直接判断当前结点指针是否指向了头结点即可。再遍历每一个结点，看是否满足条件。第一组数据返回True第二组数据返回False任务三交集：因为是递增有序的链表，所以去两个链表的第一个结点，比较，将值较小的往后移动，反复进行。并将值相同的剪切一个到新链表中。并集：先利用交集去除一个链表中的与另一个链表重复的结点，在将两个链表按递增顺序连接在一起。第一组数据交集是136101820并集是1234567891015161718192030第二组

7、数据交集是空并集是123456789101215161718192022第三组数据交集是空并集是12345678910任务四使用带头结点的双循环链表，遍历结束标志仍为是否指向头结点。任务五从双循环链表的两端同时访问结点，若遇到不相等的点返回false，否则返回true，当当前两个结点相邻或者相同时，访问结束；第一组数据满足第二组数据满足第三组数据的4与6不对称第四组的5与6不满足