nyist-数据结构实验指导书new

《nyist-数据结构实验指导书new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南阳理工学院数据结构上机实验指导书（2011版）软件学院·软件工程教研室2011.3I数据结构上机实验指导书——软件学院·软件工程教研室［2011版］目录实验1线性表应用2实验2栈和队列的应用2实验3线性表应用3实验4图论及其应用3实验5查找4实验6排序4数据结构上机实验指导书——软件学院·软件工程教研室［2011版］实验1线性表应用一、实验目的1.了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实现。2.能够利用线性表结构对实际问题进行分析建模，利用计算机求解。3.能够从时间和空间复杂度的角度综合比较线性表两种

2、存储结构的不同特点及其适用场合。二、实验内容及步骤1.利用程序设计语言分别实现顺序表和链表的抽象数据类型。2.掌握程序分文件（头文件和实现文件）书写的方式。3.分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。实验2栈和队列的应用一、实验目的1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。二、实验内容及步骤1.用程序设计语言实现栈和队列的抽象数据类型。2.在第一题的基础上完成以下选择：选择一

3、：1)设计并实现括号匹配算法。2)用队列实现在屏幕上打印杨辉三角。选择二：分别用栈和队列实现迷宫问题求解。选择三：分别用栈和队列实现一个列车调度系统。4数据结构上机实验指导书——软件学院·软件工程教研室［2011版］实验3线性表应用一、实验目的1.领会并理解二叉树的类型定义。2.熟练掌握二叉树的主要特性，。3.熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。4.熟练掌握二叉树和树的各种存储结构及其建立的算法。5.了递归算法的实现过程。二、实验内容及步骤1.实现二叉树的抽象数据类型。2.构造一棵二叉树并用递归实现其

4、先序、中序、后序遍历算法并验证。3.用非递归算法实现二叉树的中序遍历。4.给出一段报文和每个字符出现的概率，对其进行哈夫曼编码和解码。实验4图论及其应用一、实验目的1.了解图的基本概念及术语,并能够熟练掌握图的两种存储结构(邻接矩阵和邻接表)。2.理解最小生成树的概念，能按Prim算法构造最小生成树。3.掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)、拓扑排序、关键路径、最短路径的算法思想。二、实验内容及步骤1.实现网（有权图）的存储结构。2.利用prim算法构造它的最小生成树。3.选择一个源点，寻找从原点出发到达其它顶点的最短

5、路径。4数据结构上机实验指导书——软件学院·软件工程教研室［2011版］实验5查找一、实验目的1.理解"查找表"的结构特点以及各种表示方法的适用性。2.熟练掌握顺序查找和折半查找，并对其性能做出分析。3.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。二、实验内容及步骤1.实现查找表的顺序查找和折半查找算法。2.试为下列关键字建立一个装载因子不小于0.75的哈希表，并计算你所构造的哈希表的平均查找长度。（ZHAO,QIAN,SUN,LI,ZHOU,WU,CHEN,WANG,CHANG,CHAO,YANG,JIN）实

6、验6排序一、实验目的1.了解内部排序的定义和基本方法2.理解排序的基本思想和基本概念3.掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤、算法及时空效率分析二、实验内容及步骤1.实现排序表的抽象数据类型，可以随机生成n(5000<=n<=50000)个待排序数据。2.分别对每一个排序表多次运行插入排序、冒泡排序、快速排序、直接选择排序、堆排序，计算其平均运行时间。3.以横轴为数据规模，纵轴表示时间对实验结果进行描点并绘制每一个排序算法的时间轨迹。4