线性表应用,栈和队列的应用,二叉树的应用,图论及其应用,查找,排序(数据结构实验)
南阳理工学院10级数据结构实验代码(by 岳):
(线性表应用,栈和队列的应用,二叉树的应用,图论及其应用,查找,排序)
实验1 线性表应用
一、实验目的
1.了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实现。
2.能够利用线性表结构对实际问题进行分析建模，利用计算机求解。
3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
二、实验内容及步骤
1.利用程序设计语言分别实现顺序表和链表的抽象数据类型。
2.掌握程序分文件（头文件和实现文件）书写的方式。
3.分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。
实现代码见附录，word文档，程序均测试通过！
点击下载
实验2 栈和队列的应用
一、实验目的
1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
2.熟练掌握栈类型的两种实现方法。
3.熟练掌握循环队列和链队列的基本操作实现算法。
二、实验内容及步骤
1.用程序设计语言实现栈和队列的抽象数据类型。
2.在第一题的基础上完成以下选择：
选择一：
1)设计并实现括号匹配算法。
2)用队列实现在屏幕上打印杨辉三角。
选择二：
分别用栈和队列实现迷宫问题求解。
选择三：
分别用栈和队列实现一个列车调度系统。
实现代码见附录，word文档，程序均测试通过！
点击下载
实验3 二叉树应用
一、实验目的
1.领会并理解二叉树的类型定义。
2.熟练掌握二叉树的主要特性，。
3.熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。
4.熟练掌握二叉树和树的各种存储结构及其建立的算法。
5.了递归算法的实现过程。
二、实验内容及步骤
1.实现二叉树的抽象数据类型。
2.构造一棵二叉树并用递归实现其先序、中序、后序遍历算法并验证。
3.用非递归算法实现二叉树的中序遍历。
4.给出一段报文和每个字符出现的概率，对其进行哈夫曼编码和解码。
实现代码见附录，word文档，程序均测试通过！
点击下载
实验4 图论及其应用
一、实验目的
1.了解图的基本概念及术语,并能够熟练掌握图的两种存储结构(邻接矩阵和邻接表)。
2.理解最小生成树的概念，能按Prim算法构造最小生成树。
3.掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)、拓扑排序、关键路径、最短路径的算法思想。
二、实验内容及步骤
1.实现网（有权图）的存储结构。
2.利用prim算法构造它的最小生成树。
3.选择一个源点，寻找从原点出发到达其它顶点的最短路径。
实现代码见附录，word文档，程序均测试通过！
点击下载
实验5 查找
一、实验目的
1.理解”查找表”的结构特点以及各种表示方法的适用性。
2.熟练掌握顺序查找和折半查找，并对其性能做出分析。
3.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。
二、实验内容及步骤
1.实现查找表的顺序查找和折半查找算法。
2.试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的平均查找长度。
（ZHAO, QIAN, SUN, LI, ZHOU, WU, CHEN, WANG, CHANG, CHAO, YANG, JIN）
实现代码见附录，word文档，程序均测试通过！
点击下载
实验6 排序
一、实验目的
1.了解内部排序的定义和基本方法
2.理解排序的基本思想和基本概念
3.掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤、算法及时空效率分析
二、实验内容及步骤
1.实现排序表的抽象数据类型，可以随机生成n(5000 2.分别对每一个排序表多次运行插入排序、冒泡排序、快速排序、直接选择排序、堆排序，计算其平均运行时间。
3.以横轴为数据规模，纵轴表示时间对实验结果进行描点并绘制每一个排序算法的时间轨迹。
实现代码见附录，word文档，程序均测试通过！