《数据结构》实验指导书.docx

数据结构与算法实验指导书东北林业大学信息与计算机工程学院软件工程专业()类型定义(邻接表存储)顶点最大个数; 边的权; 表结点 顶点元素类型,;顶点的度，入度* 头结点，；9,; 顶点的实际数，边的实际数*()上述类型定义可以根据实际情况适当调整。()算法7、8分别利用栈、队列实现非递归算法。 四、注意问题注意理解各算法实现时所采用的存储结构。 ()注意区别正、逆邻接。实验四查找和排序的有关操作一、目的要求()掌握折半查找算法的思想及程序实现。()掌握二叉排序树、树的查找、插入、删除、建立算法的思想及程序实现。()掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。()掌握常见的排序算法的思想及其合用条件。()掌握常见的排序算法的程序实现。二、实验内容()利用实验一建立有序表，采用折半查找实现某一已知的关键字的查找。()随机产生一组关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指定关键 字元素。()建立AVL树并实现删除某一指定关键字元素。(选做)()已知散列函数为(为自定的常数)，冲突处理方法分别为线性探测法、外拉链法实现散列表的建立(利用插入算法实现)o()输入一组关键字序列分别实现下列排序：实现简单选择排序、直接插入排序和冒泡排序。实现希尔排序算法。实现快速排序算法。实现堆排序算法。(选做)快速排序的非递归算法。(选做)实现折半插入排序。(选做)采用链式存储实现简单选择排序、直接插入排序和冒泡排序。(选做)()在主函数中设计一个简单的菜单，分别测试上述算法。()综合训练：采用几组不同数据测试各个排序算法的性能(比较次数和挪移次数)。(选做)三、实验说明()存储定义(散列表的外拉链法)算法、可以参考顺序表，二叉链表的存储实现。()各种关键字数据输入可利用随机函数自动产生，以便节省上机时间。()算法 存储在文件中，算法、 存储在文件中，算法 存储在文件中。()类型定义参加排序元素的最大个数; 参加排序元素的实际个数*四、注意问题()注意理解折半查找的合用条件(链表能否实现折半查找？)。()注意建立二叉排序树、散列表时相同元素的处理。()注意理解静态查找、动态查找概念。()比较各种查找算法的各自特点，能够根据实际情况选择合适的查找方法。()在中增加一个数据项验证各种排序算法的稳定性。()注意理解各种算法的思想、了解算法的合用情况及时间复杂度，能够根据实际情况选择合适 的排序方法。1 实验目的与要求12 实验环境13实验普通步骤 14实验时数25实验内容和要求3实验一线性表和栈的有关操作构3实验二二叉树的有关操作4实验三图的有关操作6实验四 查找和排序的有关操作 8实验目的与要求从以往的教学事先实习的经验来看，在初学阶段执行严格的实习步骤规范（包括上机操作规范）， 机时利用率会大大提高，有助于养成良好的程序编制风格，培养严谨、科学、高效的工作方式。在以往的教学实践中，时常发现不少学生抱怨说，化了两个小时才找出一个错误，甚至一无所获。 他们不明白造成这种情况的原因，正是他们自己。有的学生不屑于按实习步骤规范去做，甚至对于实 习步骤的要求和建议看都不看一遍，认为那是浪费时间，这是及其害的。实习步骤规范非但可以培养 科学化的工作作风，而且还能有效地避免错误。实验环境（）计算机的硬件配置系列微机。（）计算机的软件配置或、语言的集成开辟环境，或者实验普通步骤（）问题分析与系统的结构设计充分地分析和理解问题本身，弄清要求作什么，限制条件是什么。按照以数据结构为中心的原则 划分模块，即定义数据结构及其在这些结构之上的操作，使得对数据结构的存取通过这些操作加以实 现。在这个过程中，要综合考虑系统功能。要考虑系统结构清晰、合理、简单并且易于调试。最后写 出每一个子程序（过程或者函数）的规格说明，列出它们之间的调用关系，可以使用调用关系图表 示则更加清晰，这样便完成为了系统结构设计。（）详细设计和编码详细设计的目的是对子程序（过程或者函数）的进一步求精。用、和赋值语句等，以及自然语言写出算法的框架。利用自然语言的目的是避免陷入细节。在编码是，可以对详细设计的结果进 一步求精，用高级语言表示出来。程序的每一行最好不超过 个字符。每一个子程序（或者过程、函数）通常不要太长，以 行为 宜。子程序（或者过程、函数）包含的程序行数太多，易于造成理解的艰难。控制、 等语句的连 续嵌套的深度。程序的目的性必须明确。对每一段程序完成的作用，除非常明显的除外（如： 注 释为加，没有什么意义），都应加以注释。这会对程序的调试提供不少方便。此外，根据情况可以 设立若干调试点，即输出若干信息，用于验证和你的设想是否一致。此外对于输入输出语句，必须对它们的作用加以说明。否则，在调试程序时，无法了解系统需要输入说明，系统输出的又是什么。 程序的书写，必须按照一定的规范，如保留字小写时涂黑，或者大写等等。具体的要求可参看软件工 程中的有关规定。()上机准备和静态检查高级语言文本熟悉机器的用户手册，熟悉常用的命令。准备调试的工具，考虑调试方案。如果机器上没有现成的调试工具可供利用，可以自己先设计 一些以供使用。静态检查自己用一组数据手动执行程序；或者同同学一起阅读自己的程序，以全面地了解该程序的逻辑。()上机调试程序自底向上，先调试底层模块，再调试上层模块。最后，整个程序进行联 调。调试正确后将源程序 和运行结果加以列印输出。()实习报告的整理需求及规格说明问题描述，求解的问题是什么。设计：设计思想：存储结构、主要的算法思想。设计表示：子程序(过程或者函数)的规格说明，通过调用关系图表 示它们之间的调用关系。实现注释：详细设计表示：主要算法的框架。用户手册：使用说明。调试报告：问题是如何解决的，讨论与分析、改进设想、经验与体味、时空复杂度等。附录源程序清单和结果：源程序必须有注释，以及必要的测试数据和运行结果数据。提倡用英文描述。实验报告要求：在程序开辟过程中，逐步形成各种必要的文档及资料。可以写在实验报告纸上，或者以电子文档 的形式进行书写。实验时数总实验时数不得少于学时。实验内容和要求以下的实习题目配合课程的进度，请同学们自己务必完成。为了锻炼自己的应用各种不同的数据 结构的能力，尽可能的多作一些题目是非常必要的。在完成各种不同题目的过程中，对各种算法的时、 空复杂性的分析，将匡助您在更高的角度解决各种应用问题。每次实验后要交实验报告，实验报告的内容应包括：()实验题目、班级、学号、姓名、完成日 期；()简要的需求分析与概要设计；()详细的算法描述；()程序清单与运行结果；()收获与 体味。实验一线性表和栈的有关操作一、目的要求()掌握顺序存储结构的特点和常见算法。()掌握链表的存储特点。()掌握链表的插入、删除算法及其应用算法的程序实现。()掌握栈、队列的思想及其存储实现。()掌握栈、队列的常见算法的程序实现。二、实验内容()输入一组整型元素序列，建立顺序表，实现该顺序表的遍历；在该顺序表中进行顺序查找某 一元素，查找成功返回，否则返回；判断该顺序表中元素是否对称，对称返回，否则返回；输 入整型元素序列利用有序表插入算法建立一个有序表。编写一个主函数，调试上述算法。()随机产生或者键盘输入一组元素，建立一个带头结点的单向链表；遍历单向链表；把单向链 表中元素逆置(不允许申请新的结点空间)；在单向链表中删除所有的偶数元素结点；编写在非递减 有序链表中插入一个元素使链表元素仍有序的函数，并利用该函数建立一个非递减有序单向链表。约瑟夫环问题。(单循环链表实现)()采用链式存储实现栈的初始化、入栈、出栈操作。()采用顺序存储实现循环队列的初始化、入队、出队操作。(6)综合训练：利用栈实现表达式求值算法。(选做)三、实验说明()线性表存储定义表中元素的最大个数; 元素类型;静态线性表;表的实际长度; 顺序表的类型名()建立顺序表时可利用随机函数自动产生数据。()单向链表的类型定义如下，为了算法实现简单，最好采用带头结点的单向链表。; 元素类型()双向链表的类型定义：; 元素类型()顺序栈示例栈的最大值()顺序队列示例队列的最大长度四、注意问题()插入、删除时元素的挪移原因、方向及先后顺序。()重点理解链式存储的特点及指针的含义，注意比较顺序存储与链式存储的各自特点。()注意比较带头结点、无头结点链表实现插入、删除算法时的区别。()单向链表的操作是数据结构的基础，一定要注意对这部份的常见算法的理解。()注意比较单向、双向链表的特点。实验二二叉树的有关操作一、目的要求()掌握二叉树的存储实现。()掌握二叉树的遍历思想。()掌握二叉树的常见算法的程序实现。二、实验内容()输入字符序列，建立二叉链表。()中序遍历二叉树：采用递归算法和非递归算法。(最好也能实现先序，后序非递归算法)()求二叉树的高度和叶子个数。(4)借助队列实现二叉树的层次遍历。()综合训练：为 个权值设计哈夫曼编码。(选做)()类型定义类型定义二叉链表存储元素类型()元素类型可以根据实际情况选取。四、注意问题()重点理解二叉树的存储结构。()注意理解递归算法的执行步骤。()重点理解如何利用队列结构实现的层次遍历算法。实验三图的有关操作一、目的要求()掌握图的存储思想及其存储实现。()掌握图的深度、广度优先遍历算法思想及其程序实现。()掌握图的常见应用算法的思想及其程序实现。二、实验内容()键盘输入数据，建立一个有向图的邻接表。输出该邻接表。()在有向图的邻接表的基础上计算各顶点的度，并输出。()以有向图的邻接表为基础实现输出它的拓扑排序序列。(选做)(选做)(选做)()采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。()采用邻接表存储实现无向图的深度优先非递归遍历和广度优先遍历。()采用邻接矩阵存储实现无向图的最小生成树的算法。(选做)()判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列