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

数据结构实验指导 实验二循环链表 双链表及链表应用实验 胡学钢张晶合肥工业大学计算机与信息学院 Jsjxhuxg 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