数据结构实验指导-合肥工业大学.ppt

数据结构实验指导,（实验二 循环链表、双链表及链表应用实验） 胡学钢 张晶 合肥工业大学计算机与信息学院 (J) 2009年3月,实验二 循环链表、双链表及链表应用实验,2.1 实验目的 (1)理解单循环链表及双循环链表的特点。 (2)掌握这两种结构的算法设计。 (3)运用链表存储数据并设计有关算法。 (4)理解头结点、头指针概念以及设置头结点的优点,实验二 循环链表、双链表及链表应用实验,2.2 实验任务 说明1：本次实验中的链表结构包括单循环链表和双链表两类。 说明2：为使实验程序简洁直观, 同样是将实验程序中将所需要的函数以调用库函数的形式给出, 并假设将库函数放在程序文件“linklist.h“中, 同时假设该库函数文件中定义了链表结构中的指针类型为link, 结点类型为node, 双链表中结点的类型为dunode, 其中有data、next和prior等字段, data的类型为int, 而next和prior分别为指示其下一个和前一个结点的指针, 类型为dulink（即dunode *）。类似地, 定义了部分常用运算, 如构建链表、显示链表等。各运算的名称较为直观, 并有相应的注释, 因而易于理解和实现。读者在上机实验时, 需要自己设计出所涉及到的库函数, 或者将函数放在实验程序中, 以方便实验程序的调试。如时间紧的话, 也可到作者的网站下载以供参考。,实验二 循环链表、双链表及链表应用实验,算法设计 设计算法依次访问无头结点的单循环链表的各结点。 实验测试数据基本要求： 第一组数据：链表元素为 （1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60） 第二组数据：链表元素为 （10, 20, 30, 40, 50, 60, 70, 80, 90, 100） 设计算法以判断一个带头结点的单循环链表是否满足这样的条件：其中每个结点的元素值与其序号的差的绝对值不大于。若成立, 返回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）,实验二 循环链表、双链表及链表应用实验,利用递增有序的单循环链表表示集合, 分别求两个链表表示的集合的交、并集所构成的链表。 实验测试数据基本要求： 第一组 第一个链表元素为 （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）,实验二 循环链表、双链表及链表应用实验,编写算法以构造带头结点的双循环链表。 实验测试数据基本要求： 第一组数据：链表元素为 （1, 2, 3, 4, 5, 6, 7, 8, 9, 10） 第二组数据：链表元素为 （10, 30, 40, 55, 60, 70, 88, 99, 100） 编写算法以判断一个带头结点的双循环链表是否是对称的, 若成立, 返回TRUE, 否则返回FALSE。 实验测试数据基本要求： 第一组数据：链表元素为 （1, 2, 3, 4, 5, 4, 3, 2, 1） 第二组数据：链表元素为 （1, 2, 3, 4, 5, 5, 4, 3, 2, 1） 第三组数据