2022年《数据结构与算法》实验指导书 .pdf

I 算法与数据结构实验指导书.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - I 目录第一部分算法与数据结构课程实验概述. 1一实验目的. 1二实验要求. 12.1 实验步骤 . 12.2 实验报告格式 . 2第二部分上机实验内容. 3实验一迷宫问题 . 3实验二锦标赛问题 . 4实验三 Kruskal算法的设计 . 6实验四哈夫曼编码 . 7实验五树和二叉树 . 8实验六查找和排序 . 10附：实验（设计）报告封面. 11附：实验（设计）报告参考格式. 11其中实验一、实验二选择其中一题完成，实验三、实验四选择其中一题完成。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 1 第一部分算法与数据结构课程实验概述一实验目的算法与数据结构是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。在计算机科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。二实验要求2.1 实验步骤设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。因此必须严格执行良好的实验步骤规范（包括上机操作规范）。本课程实验的基本步骤是：2.1.1 问题分析充分地分析和理解问题本身，明确问题要求做什么。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如；输入、输出数据的类型、值的范围以及形式等。 同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。2.1.2 设计和编码设计即是对问题描述中涉及的操作对象定义相应的数据类型，定义主程序模块和各抽象数据类型； 定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中， 要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。 对程序中的疑名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - 2 问应作出记号，以便上机时注意解决。每个明确的功能模块程序一般不超过60 行，程序的每一行不得超过60 个字符，否则要进一步划分。2.1.3 上机前程序静态检查上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。把程序中的明显错误事先排除。2.1.4 上机调试程序上机实验时要带上C 语言教材、 数据结构教材、 数据结构上机实验指导书，调试最好分模块进行，自底向下， 即先调试低层过程或函数。调试过程中应多动手确定疑点，通过修改程序来证明。调试正确后， 认真整理源程序及其注释，写出或打印出带有完整注释的且格式良好的源程序清单和结果。2.1.5 完成上机实验报告2.2 实验报告格式见附录。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - 3 第二部分上机实验内容实验一迷宫问题 实验目的 1熟悉栈用法；2掌握回朔法及试探法程序设计技能； 预习要求 1. 认真阅读教材或参考书, 掌握栈和回朔法；2. 写出求解本实验的程序；3. 设计好相应的测试用例。 实验提示 设迷宫中数组的元素为1 表示该点道路主的阻塞，为0 表示可通。设 maze11为入口， mazemn 为出口。在 maze11和 mazemn 的元素值必为0。在任意时刻，老鼠在迷宫中的位置可以用所在点的行下标与列下标（i,j）来表示，这样，老鼠在迷宫中的某点mazeij时，其可能的运动方向有八个。下图+ 表示某时刻老鼠所在的位置（i,j）, 相邻的八个位置分别标以N、NE 、E、SE 、S、SW 、W 、NW （分别代表+点的北、东北、东、东南、南、西南、西、西北方向）；同时，相对于（i,j） ，这八个相邻位置的坐标的值都可以计算出来。但是，并非迷宫中的每一个点都有八个方向可走，四个角上就只有三个方向可供选择，边上只有五个方向可供选择。为了不在算法中每次都去检查这些边界条件，在迷宫外面套上一圈，其元素值均为1。 实验步骤 1 先设计好迷宫，并测试你的程序，直至正确为止；2 将你的程序和实录的界面存盘备用。 实验报告要求 1 阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3 简述程序的测试过程，提交实录的输入、输出文件； 思考与练习 写出用队列求解迷宫问题的算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - 4 实验二锦标赛问题 实验目的 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; 预习要求 1.认真阅读数据结构教材和算法设计教材, 了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. 实验题 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1 个选手各赛一次；（2）每个选手一天只能参赛一次；（3）循环赛在n-1 天内结束。请按此要求将比赛日程表设计成有n 行和 n-1 列的一个表。在表中的第i 行，第 j 列处填入第 i 个选手在第j 天所遇到的选手。其中1in，1jn-1。 实验提示 我们可以按分治策略将所有的选手分为两半，则n 个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 1 4 3 6 7 8 5 3 4 1 2 7 8 5 6 1 2 3 4 3 2 1 8 5 6 7 1 2 3 4 5 6 7 8 1 4 3 2 1 2 1 4 3 6 5 8 7 2 1 4 3 1 2 3 4 1 2 7 8 5 6 3 2 1 4 2 1 4 3 2 1 8 7 6 5 4 3 2 1 （1）（2）（3）图 1 2 个、 4 个和 8 个选手的比赛日程表名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - 5 图 1 所列出的正方形表（3）是 8 个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1 至选手 4 和选手 5至选手 8 前 3 天的比赛日程。 据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1 至选手 4 和选手 5 至选手 8 在后 4 天的比赛日程。 依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 实验步骤 1.设计并实现算法并准备测试用例, 修改并调试程序, 直至正确为止 ; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序 , 将你的程序整理成功能模块存盘备用. 实验报告要求 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 思考与练习 考虑 n（n 0，为任意自然数）个运动员要进行网球循环赛的问题实现。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - 6 实验三 Kruskal算法的设计 实验目的 . 根据算法设计需要, 掌握连通网的灵活表示方法; . 掌握最小生成树的Kruskal算法 ; . 基本掌握贪心算法的一般设计方法; . 进一步掌握集合的表示与操作算法的应用. 预习要求 . 认真阅读算法设计教材和数据结构教材内容, 熟习连通网的不同表示方法和最小生成树算法 ; . 设计 Kruskal算法实验程序. 实验步骤 1.设计测试问题 , 修改并调试程序, 输出最小生成树的各条边, 直至正确为止; 2.待各功能子程序调试完毕, 去掉测试程序 , 将你的程序整理成功能模块存盘备用. 实验报告要求 1.阐述实验目的和实验内容; 2.阐述 Kruskal算法的原理方法; 3.提交实验程序的功能模块; 4.提供测试数据和相应的最小生成树. 思考与练习 用 C语言实现 Prim 算法 . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - 7 实验四哈夫曼编码 实验目的 . 根据算法设计需要, 掌握哈夫曼编码的二叉树结构表示方法; . 编程实现哈夫曼编译码器; . 掌握贪心算法的一般设计方法。 预习要求 1. 认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理; 2. 设计和编制哈夫曼编译码器。 实验步骤 1.设计 SetTree 的测试方案和程序, 输入测试数据 , 修改并调试程序, 直至正确为止 ; 2.设计 EnCode的测试方案和程序, 输入测试数据, 修改并调试程序, 直至正确为止 ; 3.设计 DeCode的测试方案和程序, 输入测试数据, 修改并调试程序, 直至正确为止 ; 4.将你的程序整理成功能模块存盘备用。 实验报告要求 1.阐述实验目的和实验内容; 2.提交实验程序的功能模块; 3.记录最终测试数据和测试结果。 思考题 1.试证明哈夫曼问题具有贪心选择性质；2.试证明哈夫曼问题具有最优子结构性质。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - 8 实验五树和二叉树一、实验目的1. 掌握二叉树，二叉树排序数的概念及存储方法。2. 掌握二叉树的遍历算法。3. 熟练掌握编写实现树的各种运算的算法。4.熟悉图的各种存储方法。5.掌握遍历图的递归和非递归的算法。6. 理解图的有关算法。二、实验内容1. 用二叉树表示代数表达式并输出代数表达式的前缀式和后缀式要求及提示 ：编写一个程序， 用二叉树来表示代数表达式，树的每个结点包括一个运算符，代数表达式由输入得到（其中只包含=， +，-，* ，/和用一个字母表示的数且没有错误，并且按照先乘除后加减的原则） ，试编写程序输出表达式的前缀式和后缀式。实验数据 ：X:=(-b+(b2-4*a*c)0.5)/(2*a) 2. 求二叉树中从根结点到叶子节点的路径要求及提示 对于 1 中的代数表达式二叉树，分别用递归和非递归的方法编写程序完成如下功能：:=/*+-*2ab-*4ab20.5*c名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - 9 1输出所有的叶子结点的数据项值。2输出所有从叶子节点到根结点的路径3. 实现图的邻接矩阵和邻接表存储要求及提示 对于下图所示的有向图G，编写一个程序完成如下功能：1 建立 G 的邻接表存储结构2 输出下图的拓扑排序序列3 编写一个程序输出从顶点A 开始的深度优先遍历序列（递归算法） 和广度优先遍历序列（非递归算法） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - 10 实验六查找和排序 实验目的 1. 掌握顺序查找，二分法查找，分块查找的算法。2掌握各种排序算法及其性能的比较 实验内容 1编写一个程序输出在顺序表13 ，22，35，43，54，68，71，82，98，1005 中采用顺序方法和折半方法查找某个关键字的过程。2编写一个程序实现直接插入排序过程，并输出94 ，28，57，66，35，84，63，42，71，10 的排序过程3编写一个程序实现快速排序算法，并输出94，28，57，66，35，84，63，42，71，10的排序过程。 实验报告要求 1.阐述实验目的和实验内容; 2.提交实验程序的功能模块; 3.记录最终测试数据和测试结果。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - 11 附：实验（设计）报告封面信息科学与工程学院实验报告系别专业年级姓名学号指导教师学年第学期附：实验（设计）报告参考格式名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 12 设计一题目一、设计目的二、设计内容1任务描述2问题的表示方案3主要数据类型与变量t ypedef NodeNumber int; /* 节点编号 */ typedef CostType int; /* 成本值类型 */ （必要时，可对数据类型和变量进一步解释或说明，增加可读性）4算法或程序模块int FindForward(CostType *costn, NodeNumber i, NodeNumber cur) 功能 : （必要时，可对算法或程序模块进一步解释或说明，增加可读性）三、测试1方案描述测试方案、测试模块、测试数据实例（文字数据、图或表等形式）2结果结合测试数据实例描述测试过程和测试结果，最好给出表示测试过程和结果的抓图，对测试结果进行分析并得出结论。四、总结与讨论可针对本设计谈体会、谈改进、谈设想等，展示你的概括、归纳和创新思维能力，看重的不是你的对与错，而是鼓励你的想象和创新思维。附：程序模块的源代码名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -