数据结构程(2016)实验指导书课案

数据数据结结构构实验实验指指导书导书 一 一 实验实验目的目的 数据结构 是计算机专业一门重要的专业技术基础课程 是计算机专业的一门核 心的关键性课程 本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储 结构和实现算法 介绍了常用的多种查找和排序技术 并做了性能分析和比较 内容 非常丰富 本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基 础 由于以下原因 使得掌握这门课程具有较大的难度 1 内容丰富 学习量大 给学习带来困难 2 所用到的技术多 而在此之前的各门课程中所介绍的专业性知识又不多 因而 加大了学习难度 3 隐含在各部分的技术和方法丰富 也是学习的重点和难点 根据 数据结构 课程本身的技术特性 设置 数据结构课程实验 实践环节十分重 要 通过实验实践内容的训练 突出构造性思维训练的特征 目的是提高学生组织数 据及编写大型程序的能力 课程上机实验的目的 不仅仅是验证教材和讲课的内容 检查自己所编的程序是 否正确 课程安排的上机实验的目的可以概括为如下几个方面 1 加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练 是与课堂听讲 自学和练习相辅相成的必不 可少的一个教学环节 通常 实验题中的问题比平时的习题复杂得多 也更接近实际 实验着眼于原理与应用的结合点 使学生学会如何把书上学到的知识用于解决实际问 题 培养软件工作所需要的动手能力 另一方面 能使书上的知识变 活 起到深化理 解和灵活掌握教学内容的目的 不少学生在解答习题尤其是算法设计题时 觉得无从下手 做起来特别费劲 实 验中的内容和教科书的内容是密切相关的 解决题目要求所需的各种技术大多可从教 科书中找到 只不过其出现的形式呈多样化 因此需要仔细体会 在反复实践的过程 中才能掌握 2 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的 小 算法 而实验题是软件设计的综合 训练 包括问题分析 总体结构设计 用户界面设计 程序设计基本技能和技巧 多人 合作 以至一整套软件工作规范的训练和科学作风的培养 此外 还有很重要的一点 是 机器是比任何教师都严厉的检查者 通过实验使学生不仅能够深化理解教学内容 进一步提高灵活运用数据结构 算 法和程序设计技术的能力 而且可以在需求分析 总体结构设计 算法设计 程序设计 上机操作及程序调试等基本技能方面受到综合训练 实验着眼于原理与应用的结合点 使学生学会如何把书本上和课堂上学到的知识用于解决实际问题 从而培养计算机软 件工作所需要的动手能力 3 熟悉程序开发环境 学习上机调试程序 一个程序从编辑 编译 连接到运行 都要在一定的外部操作环境下才能进行 所 谓 环境 就是所用的计算机系统硬件 软件条件 只有学会使用这些环境 才能进行 程序开发工作 通过上机实验 熟练地掌握程序的开发环境 为以后真正编写计算机 程序解决实际问题打下基础 同时 在今后遇到其它开发环境时就会触类旁通 很快 掌握新系统的使用 完成程序的编写 决不意味着万事大吉 你认为万无一失的程序 实际上机运行 时可能不断出现麻烦 如编译程序检测出一大堆语法错误 有时程序本身不存在语法 错误 也能够顺利运行 但是运行结果显然是错误的 开发环境所提供的编译系统无 法发现这种程序逻辑错误 只能靠自己的上机经验分析判断错误所在 程序的调试是 一个技巧性很强的工作 尽快掌握程序调试方法是非常重要的 分析问题 选择算法 编好程序 只能说完成一半工作 另一半工作就是调试程序 运行程序并得到正确结 果 二 二 实验实验要求要求 常用的软件开发方法 是将软件开发过程划分为分析 设计 实现和维护四个阶 段 虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高 但为了 培养一个软件工作者所应具备的科学工作的方法和作风 也应遵循以下五个步骤来完 成实验题目 1 问题分析和任务定义 在进行设计之前 首先应该充分地分析和理解问题 明确问题要求做什么 限制条 件是什么 本步骤强调的是做什么 而不是怎么做 对问题的描述应避开算法和所涉及 的数据类型 而是对所需完成的任务作出明确的回答 例如 输入数据的类型 值的范 围以及输入的形式 输出数据的类型 值的范围及输出的形式 若是会话式的输入 则 结束标志是什么 是否接受非法的输入 对非法输入的回答方式是什么等 还应该为调 试程序准备好测试数据 包括合法的输入数据和非法形式的输入数据 2 逻辑设计和详细设计 在设计这一步骤中需分逻辑设计和详细设计两步实现 逻辑设计指的是 对问题 描述中涉及的操作对象定义相应的数据类型 并按照以数据结构为中心的原则划分模 块 定义主程序模块和各抽象数据类型 详细设计则为定义相应的存储结构并写出各 函数的伪码算法 在这个过程中 要综合考虑系统功能 使得系统结构清晰 合理 简 单和易于调试 抽象数据类型的实现尽可能做到数据封装 基本操作的规格说明尽可 能明确具体 作为逻辑设计的结果 应写出每个抽象数据类型的定义 包括数据结构的 描述和每个基本操作的功能说明 各个主要模块的算法 并画出模块之间的调用关系 图 详细设计的结果是对数据结构和基本操作作出进一步的求精 写出数据存储结构 的类型定义 写出函数形式的算法框架 在求精的过程中 应尽量避免陷入语言细节 不必过早表述辅助数据结构和局部变量 3 编码实现和静态检查 编码是把详细设计的结果进一步求精为程序设计语言程序 如果基于详细设计的 伪码算法就能直接在键盘上输入程序的话 则可以不必用笔在纸上写出编码 而将这 一步的工作放在上机准备之后进行 即在上机调试之前直接用键盘输入 然而 不管你是否写出编码的程序 在上机之前 认真的静态检查是必不可少的 静态检查主要有两种方法 一是用一组测试数据手工执行程序 通常应先分模块检查 二是通过对程序深入全面地理解程序逻辑 在这个过程中再加入一些注解和断言 如 果程序中逻辑概念清楚 后者将比前者有效 4 上机准备和上机调试 上机准备包括以下几个方面 1 注意同一高级语言文本之间的差别 2 熟悉机器的操作系统和语言集成环境的用户手册 尤其是最常用的命令操作 以便顺利进行上机的基本活动 3 掌握调试工具 考虑调试方案 设计测试数据并手工得出正确结果 应该能够 熟练运用高级语言的程序调试器 DBBUG 调试程序 4 上机调试程序时要带一本高级语言教材或手册 调试最好分模块进行 自底向 上 即先调试低层函数 在调试过程中可以不断借助 DEBUG 的各种功能 提高调试 效率 调试中遇到的各种异常现象往往是预料不到的 此时应动手确定疑点 通过修 改程序来证实它或绕过它 调试正确后 认真整理源程序及其注释 形成格式和风格 良好的源程序清单和结果 5 总结和整理实验报告 实验结束后 要整理实验结果并认真分析和总结 根据教师要求写出实验报告 实验报告一般包括如下内容 1 实验内容 2 实验目的 3 程序清单 4 调试步骤 5 运行结果 原始数据 相应的运行结果和必要的说明 6 分析与思考 调试过程及调试中遇到的问题及解决办法 调试程序的心得与体 会 其他算法的存在与实践等 若最终未完成调试 要认真找出错误并分析原因等 三 三 实验实验内容内容 实验实验一一 Joseph 问题问题求解算法的求解算法的设计设计与与实现实现 1 实验实验学学时时 2 学时 2 实验实验目的目的 掌握链表的基本操作 插入 删除 查找等运算 能够灵活应用链表这种数据结构 3 问题问题描述描述 约瑟夫 Joseph 问题的一种描述是 编号为 1 2 n 的 n 个人按顺时针方向围 坐一圈 每人持有一个密码 正整数 开始任选一个正整数作为报数上限值 m 从第 一个人开始按顺时针方向自 1 开始顺序报数 报到 m 时停止报数 报 m 的人出列 将 他的密码作为新的 m 值 从他在顺时针方向上的下一个人开始重新从 1 报数 如此下 去 直至所有人全部出列为止 试设计一个程序求出出列顺序 4 基本要求 基本要求 利用单向循环链表存储结构模拟此过程 按照出列的顺序印出各人的编号 5 测试测试数据数据 m 的初值为 20 n 7 7 个人的密码依次为 3 1 7 2 4 8 4 首先 m 值为 6 正 确的出列顺序应为 6 1 4 7 2 3 5 6 实现实现提示提示 程序运行后 首先要求用户指定初始报数上限值 然后读取各人的密码 可设 n 30 此题所用的循环链表中不需要 头结点 请注意空表和非空表的界限 7 选选作内容作内容 向上述程序中添加在顺序结构上实现的部分 实验实验二二 停停车场车场管理管理 1 实验实验学学时时 4 学时 2 实验实验目的目的 1 深入了解栈和队列的特性 掌握栈和队列的存储方法 2 掌握栈和队列的基本操作 如初始化 入栈 队列 出栈 队列 等 并能在实 际问题背景下灵活运用 3 问题问题描述描述 设停车场是一个可以停放 n 辆汽车的狭长通道 且只有一个大门可供汽车进出 汽车在停车场内按车辆到达时间的先后顺序 依次由北向南排列 大门在最南端 最先 到达的第一辆车停放在车场的最北端 若车场内已经停满 n 辆汽车 则后来的汽车只 能在门外的便道上等候 一旦有车开走 则排在便道上的第一辆车即可开入 当停车场 内某辆车要离开时 在它之后进入的车辆必须先退出场为它让路 待该辆车开出大门 外 其他车辆再按次序进入车场 每辆停放在车场的车在它离开停车场时必须按它停 留的时间长短交纳费用 试为停车场编制按上述要求进行管理的模拟程序 4 基本要求 基本要求 以栈模拟停车场 以队列模拟车场外的便道 按照从终端读入的输入数据序列进 行模拟管理 每一组输入数据包括三个数据项 汽车 到达 或 离去 信息 汽车牌照号 码以及到达或离去的时刻 对一组输入数据进行操作后的输出信息为 若是车辆到达 则输出汽车在停车场内或便道上的停车位置 若是车辆离去 则输出汽车在停车场内 停留的时间和应交纳的费用 在便道上停留的时间不收费 栈以顺序结构实现 队列 以链表结构实现 5 测试测试数据数据 设 n 2 输入数据为 A 1 5 A 2 10 D 1 5 A 3 20 A 4 25 A 5 30 D 2 35 D 4 40 E 0 0 其中 A 表示 到达 Arrival D 表示离去 Departure E 表示输入结束 End 6 实现实现提示提示 需另设一个栈 临时停放为给要离去的汽车让路而从停车场退出来的汽车 也用 顺序存储结构实现 输入数据按到达或离去的时刻有序 栈中每个元素表示一辆汽车 包含两个数据项 汽车的牌照号码和进入停车场的时刻 7 选选作内容作内容 1 两个栈共享空间 思考应开辟数组的空间是多少 2 汽车可以有不同种类 则他们的占地面积不同 收费标准也不同 如 1 辆客车 和 1 5 辆小汽车的占地面积相同 1 辆十轮卡车占地面积相当于 3 辆小汽车的占地面 积 3 汽车可以直接从便道上开走 此时排在它前面的汽车要先开走让路 然后再依 次排到队尾 4 停放在便道上的汽车业收费 收费标准比停放在停车场的车低 请思考如何修 改结构以满足这种要求 实验实验三三 基于哈夫曼基于哈夫曼编码编码的通信系的通信系统统的的设计设计与与实现实现 1 实验实验学学时时 5 学时 2 实验实验目的目的 1 掌握二叉树的存储结构及其相关操作 2 掌握构造哈夫曼树的基本思想 及其编码 译码过程 3 问题问题描述描述 利用哈夫曼编码进行通信可以大大提高信道利用率 缩短信息传输时间 降低传 输成本 但是 这要求在发送端通过一个编码系统对待传输数据预先编码 在接收端 将传来的数据进行译码 复原 对于双工信道 即可以双向传输信息的信道 每端都 需要一个完整的编 译码系统 试为这样的信息收发站设计一个基于哈夫曼编码的通 信系统 4 基本要求 基本要求 一个完整的系统应具有以下功能 1 初始化 初始化处处理 建立通信系理 建立通信系统统 1 建立有 100 句中文的信息集合 每个句子称为一条信息 2 输入编码参数 从终端输入编码字符集大小 n 字符编码长度 m 设 n 为 4 m 为 8 从终端输入编码字符 设为 A B C D 3 生成每条信息的字符编码 构造字符编码集合 4 计算每个字符在字符编码集合中出现的概率 5 根据字符概率构造哈夫曼树 求出每个字符的二进制编码 2 发发送端信息送端信息编码编码 1 用户从信息集合中选择一条信息 找到该信息对应的字符编码 2 根据该信息的字符编码 哈夫曼树求出的每个字符的二进制编码 构造出该信 息的二进制编码 记录该二进制编码 由于是软件模拟 没有发送设备 发送端的编码 工作完成 3 接受端信息 接受端信息译码译码 1 根据得到的信息的二进制编码 利用哈夫曼树求出的每个字符的二进制编码 还原出信息的字符编码 2 根据信息的字符编码 找到对应的信息 5 实现实现提示提示 1 本试验涉及到通讯学科的编码理论和信息学科的数据压缩技术 2 根据参数生成的通信系统的所有信息的有效存储问题 3 信息字符编码可参考随机数的方式生成 且要求保持唯一性 实验实验四四 基于二叉排序基于二叉排序树树的商品信息的商品信息查询查询算法的算法的设计设计与与实现实现 1 实验实验学学时时 6 学时 2 实验实验目的目的 熟练掌握顺序查找 折半查找及二叉排序树 平衡二叉树上的查找 插入和删除 的方法 3 问题问题描述描述 查找是数据处理的重要操作 请设计并实现基于二叉排序树的商品信息查询算法 完成信息的查询 插入 删除 查询频度的统计等功能 4 基本要求 基本要求 1 以链表作为存储结构 设计并实现基于二叉排序树的商品信息查询算法 2 根据二叉排序树的动态变化 进行二叉树的平衡化处理 3 实现信息的查询 插入 删除 查询频度的统计等功能 5 测试测试数据数据 随机生成 6 实现实现提示提示 1 初始化 以商品名称为关键字 建立二叉排序树 2 用户输入查询商品名称 在二叉排序树上查找 若找到 则显示商品的相关信 息 并在相应的表上的相关字段上增加该商品查找次数 若未找到 则显示未找到信 息给用户 并在相应的表上的相关字段上增加该商品查找次数 3 根据商品的查找次数 形成商场的经营决策信息 反馈给决策者 4 进行二叉树的平衡化处理 提高查找效率 实验实验五五 内部排序算法效率比内部排序算法效率比较较平台的平台的设计设计与与实现实现 1 实验实验学学时时 3 学时 2 实验实验目的目的 掌握多种排序方法的基本思想 如直接插入 起泡 简单选择 快速 堆 希尔排 序等排序方法