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