《数据结构与算法》实验指导书2015

1、算法与数据结构实验指导书.12目 录第一部分 算法与数据结构课程实验概述1一实验目的2二实验要求22.1实验步骤22.2实验报告格式3第二部分 上机实验内容4实验一 迷宫问题4实验二 锦标赛问题5实验三 Kruskal算法的设计7实验四 哈夫曼编码8实验五 树和二叉树9实验六 查找和排序11附：实验（设计）报告封面12附：实验（设计）报告参考格式13其中实验一、实验二选择其中一题完成，实验三、实验四选择其中一题完成。第一部分 算法与数据结构课程实验概述一实验目的算法与数据结构是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以

2、便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。在计算机科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。二实验要求2.1实验步骤 设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。因此必须严格执行良好的实验步骤规范（包括上机操作规范）。本课程实验的基本步骤是： 2.1.1问题分析 充分地分析和理解问题本身，明确问题要求

3、做什么。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如；输入、输出数据的类型、值的范围以及形式等。同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。2.1.2设计和编码设计即是对问题描述中涉及的操作对象定义相应的数据类型，定义主程序模块和各抽象数据类型；定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。 编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。对程序中的疑问应作出记号，以便上机时注意解决。每个明确的功能模块程序一般不超过60行，程序的每一行不得

4、超过60个字符，否则要进一步划分。 2.1.3上机前程序静态检查 上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。 静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。把程序中的明显错误事先排除。2.1.4上机调试程序上机实验时要带上C语言教材、数据结构教材、数据结构上机实验指导书，调试最好分模块进行，自底向下，即先调试低层过程或函数。调试过程中应多动手确定疑点，通过修改程序来证明。调试正确后，认真整理源程序及其注释，写出或打印出带有完整注释的且格式良好的源程序清单和结果。2.1.5完成上机实验报告2.2实验报告格式

5、见附录。第二部分 上机实验内容实验一 迷宫问题实验目的1熟悉栈用法；2掌握回朔法及试探法程序设计技能； 预习要求1.认真阅读教材或参考书, 掌握栈和回朔法；2.写出求解本实验的程序；3.设计好相应的测试用例。实验提示设迷宫中数组的元素为1表示该点道路主的阻塞，为0表示可通。设maze11为入口，mazemn 为出口。在maze11和mazemn的元素值必为0。在任意时刻，老鼠在迷宫中的位置可以用所在点的行下标与列下标（i,j）来表示，这样，老鼠在迷宫中的某点mazeij时，其可能的运动方向有八个。下图表示某时刻老鼠所在的位置（i,j）,相邻的八个位置分别标以N、NE、E、SE、S、SW、W、N

6、W（分别代表点的北、东北、东、东南、南、西南、西、西北方向）；同时，相对于（i,j），这八个相邻位置的坐标的值都可以计算出来。但是，并非迷宫中的每一个点都有八个方向可走，四个角上就只有三个方向可供选择，边上只有五个方向可供选择。为了不在算法中每次都去检查这些边界条件，在迷宫外面套上一圈，其元素值均为1。实验步骤1 先设计好迷宫，并测试你的程序，直至正确为止；2 将你的程序和实录的界面存盘备用。 实验报告要求1 阐述实验目的和实验内容；2 提交模块化的实验程序源代码；3 简述程序的测试过程，提交实录的输入、输出文件；思考与练习 写出用队列求解迷宫问题的算法。实验二 锦标赛问题 实验目的1. 基本

7、掌握分治算法的原理.2. 能用程序设计语言求解锦标赛等问题的算法;预习要求1. 认真阅读数据结构教材和算法设计教材,了解分治算法原理;2. 设计用分治算法求解背包问题的数据结构与程序代码.实验题【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1in，1jn-1。 实验提示我们可以按分治策略将所有的选手分为两半，则n个选手的比赛

8、日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。12345671234567821436785341278561234321856712345678143212143658721431234127856321421432187654321（1） （2） （3）图1 2个、4个和8个选手的比赛日程表图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置

9、抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 实验步骤1. 设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;2. 应用设计的算法和程序求锦标赛问题;3. 去掉测试程序,将你的程序整理成功能模块存盘备用. 实验报告要求1. 阐述实验目的和实验内容;2. 阐述分治算法原理;3. 提交实验程序的功能模块;4. 记录最终测试数据和测试结果。思考与练习考虑n（n0，为任意自然数）个运动员要进行网球循环赛的问题实现。 实验三 Kruskal算法的设

10、计实验目的. 根据算法设计需要, 掌握连通网的灵活表示方法;. 掌握最小生成树的Kruskal算法;. 基本掌握贪心算法的一般设计方法;. 进一步掌握集合的表示与操作算法的应用.预习要求. 认真阅读算法设计教材和数据结构教材内容, 熟习连通网的不同表示方法和最小生成树算法;. 设计Kruskal算法实验程序. 实验步骤1. 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止;2. 待各功能子程序调试完毕, 去掉测试程序, 将你的程序整理成功能模块存盘备用.实验报告要求1. 阐述实验目的和实验内容;2. 阐述Kruskal算法的原理方法;3. 提交实验程序的功能模块;4. 提

11、供测试数据和相应的最小生成树.思考与练习 用C语言实现Prim算法. 实验四 哈夫曼编码 实验目的. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法;. 编程实现哈夫曼编译码器;. 掌握贪心算法的一般设计方法。预习要求1. 认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理;2. 设计和编制哈夫曼编译码器。 实验步骤1. 设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2. 设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;3. 设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;4. 将你

12、的程序整理成功能模块存盘备用。实验报告要求1. 阐述实验目的和实验内容;2. 提交实验程序的功能模块;3. 记录最终测试数据和测试结果。思考题1. 试证明哈夫曼问题具有贪心选择性质；2. 试证明哈夫曼问题具有最优子结构性质。实验五 树和二叉树一、 实验目的1. 掌握二叉树，二叉树排序数的概念及存储方法。2. 掌握二叉树的遍历算法。3. 熟练掌握编写实现树的各种运算的算法。4.熟悉图的各种存储方法。5.掌握遍历图的递归和非递归的算法。6. 理解图的有关算法。二、实验内容1. 用二叉树表示代数表达式并输出代数表达式的前缀式和后缀式要求及提示：编写一个程序，用二叉树来表示代数表达式，树的每个结点包括

13、一个运算符，代数表达式由输入得到（其中只包含=，+，-，*，/和用一个字母表示的数且没有错误，并且按照先乘除后加减的原则），试编写程序输出表达式的前缀式和后缀式。实验数据：X:=(-b+(b2-4*a*c)0.5)/(2*a)2. 求二叉树中从根结点到叶子节点的路径要求及提示对于1中的代数表达式二叉树，分别用递归和非递归的方法编写程序完成如下功能：1 输出所有的叶子结点的数据项值。2 输出所有从叶子节点到根结点的路径3. 实现图的邻接矩阵和邻接表存储要求及提示对于下图所示的有向图G，编写一个程序完成如下功能：1 建立G的邻接表存储结构2 输出下图的拓扑排序序列3 编写一个程序输出从顶点0开始的

14、深度优先遍历序列（递归算法）和广度优先遍历序列（非递归算法）。实验六 查找和排序实验目的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. 记录最终测试数据和测试结果。附：实验（设计）报告封面信息科学与工程学院 实验报告 系 别 专 业 年 级 姓 名 学 号 指导教师 学年 第 学期附：实验（设计）报告参考格式设计一题目一、 设计目的二、 设计内容1 任务描述2 问题的表示方案3 主要数据类型与变量typedef NodeNumber int; /* 节点编号 */typedef CostType int; /* 成本值类型 */（必要时，可对数据类型和变量进一步解释或说明，增加可读性）4 算法或程序模块int FindForward(CostType *costn, No