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

I《算法与数据结构》实验指导书.I目录第一部分算法与数据结构课程实验概述.....................................................................................1一．实验目的...........................................................................................................................1二．实验要求...........................................................................................................................12.1实验步骤....................................................................................................................12.2实验报告格式............................................................................................................2第二部分上机实验内容.............................................................................................................3实验一迷宫问题...........................................................................................................................3实验二锦标赛问题.......................................................................................................................4实验三Kruskal算法的设计........................................................................................................6实验四哈夫曼编码.......................................................................................................................7实验五树和二叉树.......................................................................................................................8实验六查找和排序...................................................................................................................10附：实验（设计）报告封面.........................................................................................................11附：实验（设计）报告参考格式.................................................................................................11其中实验一、实验二选择其中一题完成，实验三、实验四选择其中一题完成。1第一部分算法与数据结构课程实验概述一．实验目的《算法与数据结构》是计算机专业的主干课程和必修课程之一，其目的是让大家学习、分析和研究数据对象特征，掌握数据组织方法和计算机的表示方法，以便选择合适的数据逻辑结构和存储结构，设计相应的运算操作，把现实世界中的问题转化为计算机内部的表示与处理的方法，要求掌握算法的时间、空间复杂度分析基本技术，培养良好的程序设计风格，掌握进行复杂程序设计的技能。在计算机科学领域，尤其是在系统软件和应用软件的设计和应用中要用到各种数据结构，因此，掌握数据结构对提高软件设计和程序编制水平有很大的帮助。二．实验要求2.1实验步骤设计步骤的规范不但可以培养学生科学的工作方法和作风，而且还能有效地减少错误，提高工作效率。因此必须严格执行良好的实验步骤规范（包括上机操作规范）。本课程实验的基本步骤是：2.1.1问题分析充分地分析和理解问题本身，明确问题要求做什么。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如；输入、输出数据的类型、值的范围以及形式等。同时为调试程序准备好测试数据，包含合法的输入数据和非法形式输入的数据。2.1.2设计和编码设计即是对问题描述中涉及的操作对象定义相应的数据类型，定义主程序模块和各抽象数据类型；定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。编码即把详细设计的结果进一步求精为程序设计语言程序，写出源程序。对程序中的疑2问应作出记号，以便上机时注意解决。每个明确的功能模块程序一般不超过60行，程序的每一行不得超过60个字符，否则要进一步划分。2.1.3上机前程序静态检查上机前程序静态检查可有效提高调试效率，减少上机调试程序时的无谓错误。静态检查主要有两种途径：用一组测试数据手工执行程序；通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑。把程序中的明显错误事先排除。2.1.4上机调试程序上机实验时要带上《C语言》教材、《数据结构》教材、《数据结构上机实验指导书》，调试最好分模块进行，自底向下，即先调试低层过程或函数。调试过程中应多动手确定疑点，通过修改程序来证明。调试正确后，认真整理源程序及其注释，写出或打印出带有完整注释的且格式良好的源程序清单和结果。2.1.5完成上机实验报告2.2实验报告格式见附录。3第二部分上机实验内容实验一迷宫问题[实验目的]1．熟悉栈用法；2．掌握回朔法及试探法程序设计技能；[预习要求]1.认真阅读教材或参考书,掌握栈和回朔法；2.写出求解本实验的程序；3.设计好相应的测试用例。[实验提示]设迷宫中数组的元素为1表示该点道路主的阻塞，为0表示可通。设maze[1][1]为入口，maze[m][n]为出口。在maze[1][1]和maze[m][n]的元素值必为0。在任意时刻，老鼠在迷宫中的位置可以用所在点的行下标与列下标（i,j）来表示，这样，老鼠在迷宫中的某点maze[i][j]时，其可能的运动方向有八个。下图○+表示某时刻老鼠所在的位置（i,j）,相邻的八个位置分别标以N、NE、E、SE、S、SW、W、NW（分别代表○+点的北、东北、东、东南、南、西南、西、西北方向）；同时，相对于（i,j），这八个相邻位置的坐标的值都可以计算出来。但是，并非迷宫中的每一个点都有八个方向可走，四个角上就只有三个方向可供选择，边上只有五个方向可供选择。为了不在算法中每次都去检查这些边界条件，在迷宫外面套上一圈，其元素值均为1。[实验步骤]1．先设计好迷宫，并测试你的程序，直至正确为止；2．将你的程序和实录的界面存盘备用。[实验报告要求]1．阐述实验目的和实验内容；2．提交模块化的实验程序源代码；3．简述程序的测试过程，提交实录的输入、输出文件；[思考与练习]写出用队列求解迷宫问题的算法。4实验二锦标赛问题[实验目的]1.基本掌握分治算法的原理.2.能用程序设计语言求解锦标赛等问题的算法;[预习要求]1.认真阅读数据结构教材和算法设计教材,了解分治算法原理;2.设计用分治算法求解背包问题的数据结构与程序代码.[实验题]【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能参赛一次；（3）循环赛在n-1天内结束。请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。[实验提示]我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。12345671234567821436785341278561234321856712345678143212143658721431234127856321421432187654321（1）（2）（3）图12个、4个和8个选手的比赛日程表5图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。[实验步骤]1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止;2.应用设计的算法和程序求锦标赛问题;3.去掉测试程序,将你的程序整理成功能模块存盘备用.[实验报告要求]1.阐述实验目的和实验内容;2.阐述分治算法原理;3.提交实验程序的功能模块;4.记录最终测试数据和测试结果。[思考与练习]考虑n（n0，为任意自然数）个运动员要进行网球循环赛的问题实现。6实验三Kruskal算法的设计[实验目的]１.根据算法设计需要,掌握连通网的灵活表示方法;２.掌握最小生成树的Kruskal算法;３.基本掌握贪心算法的一般设计方法;４.进一步掌握集合的表示与操作算法的应用.[预习要求]１.认真阅读算法设计教材和数据结构教材内容,熟习连通网的不同表示方法和最小生成树算法;２.设计Kruskal算法实验程序.[实验步骤]1.设计测试问题,修改并调试程序,输出最小生成树的各条边,直至正确为止;2.待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用.[实验报告要求]1.阐述实验目的和实验内容;2.阐述Kruskal算法的原理方法;3.提交实验程序的功能模块;4.提供测试数据和相应的最小生成树.[思考与练习]用C语言实现Prim算法.7实验四哈夫曼编码[实验目的]１.根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法;２.编程实现哈夫曼编译码器;３.掌握贪心算法的一般设计方法。[预习要求]1.认真阅读数据结构教材和算法设计教材内容,熟悉哈夫曼编码的原理;2.设计和编制哈夫曼编译码器。[实验步骤]1.设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2.设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;3.设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;4.将你的程序整理成功能模块存盘备用。[实验报告要求]1.阐述实验目的和实验内容;2.提交实验程序的功能模块;3.记录最终测试数据和测试结果。[思考题]1.试证明哈夫曼问题具有贪心选择性质；2.试证明哈夫曼问题具有最优子结构性质。8实验五