2011数据结构实验指导书.doc

数据结构实验指导书实验一实现队列和栈的各种算法及操作一、目的和要求1. 理解队列和栈的顺序存储结构和链式存储结构。通过本实验，熟悉队列、栈的结构特点；2. 熟悉队列、栈结构上的操作与算法的实现。二、实验内容1. 队列的基本操作和应用。2. 栈的基本操作和应用。三、仪器、设备和材料1. 适合实验要求的计算机系统2. 语言编程平台。四、实验原理队列与栈是一种操作受限制的线性表，在了解线性表的基本原理的基础上，理解与完成此项实验。五、实验步骤1. 采用队列的顺序存储结构，2用菜单的形式完成队列的建立，出队，入队等基本操作。3. 采用栈的链式存储结构4. 用菜单的形式完成栈的出栈、入栈等基本操作。六、实验注意事项1注意熟悉使用链表的操作2注意测试程序，观察实验结果。实验二用Huffman树进行编码与解码算法一、目的和要求1、通过本实验，熟悉二叉树、Huffman树的基本概念，掌握二叉树的存储结构及各种算法。2、熟悉用Huffman树进行电文的加密与解密算法。二、实验内容1、Huffman树的存储方式2、加密与解密算法在电文编码中的应用三、仪器、设备和材料1适合实验要求计算机系统2C语言变成平台四、实验原理Huffman树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符的频度，能够达到编码电文的最小化。五、实验步骤1、统计电文中字符的出现频率。 2. 用统计频率建立Hffman树。3生成前缀码；4建立huffman树的解码算法5用随机输入的电文完成编码与解码过程。六、实验注意事项1注意熟悉使用Huffman树的生成算法。2注意观察实验结果。实验三 实现深度优先搜索与广度优先搜索算法一、目的与要求1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历。 2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。二、实验内容 1、建立图的几种存储方式2、图的深度优先搜索算法3、图的广度优先搜索算法三、仪器、设备和材料1适合实验要求计算机系统2C语言变成平台四、实验原理图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历。广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索；而深度优先遍历是将某一条枝桠上的所有节点都搜索到了之后，才转向搜索另一条枝桠上的所有节点。五、实验步骤1建立图的存储结构。2输入图的基本接点与信息，完成初始化图的工作。3完成图的深度优先搜索（DFS）和广度优先搜索算法，可以采用菜单形式进行显示与选择。（可以在键盘输入边的信息以构建一个无向图。以（a,b）的形式输入边的信息；对此无向图进行深度优先搜索，并输出正确的序列。）六、实验注意事项1注意熟悉使用图的存储结构。2注意观察实验结果。七、思考题1图的存储方式有几种？本实验中你会采用什么样的存储方式？2、给出一幅无向图G如下：V(G)=v1，v2，v3，v4，v5，v6，v7，v8 ，E(G)=(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)，（v1,v8），（v2,v8）1）请画出示意图；2）请根据你采用的存储方式画出存储图示； 3）在题目2的基础上，请给出图的深度优先搜索序列；4）在题目2的基础上，请给出图的广度优先搜索序列。实验四 实现典型的排序算法一、目的与要求1通过本实验，熟悉排序基本概念。 2熟悉排序中使用的存储结构，掌握插入排序、选择排序、交换排序算法。二、实验内容 1几种典型的排序算法2计算不同的排序算法的时间复杂度并比较3判定某种排序算法是否稳定的标准三、仪器、设备和材料1适合实验要求计算机系统2C语言变成平台四、实验原理排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。五、实验步骤1输入记录的基本结点与信息，选用相关的存储结构，完成记录的存储、输入的初始化工作。2编程实现堆排序，希尔排序和快速排序算法，用菜单形式进行显示与选择。3计算排序算法的最优，最劣和平均时间复杂度。4验证算法并观察结果。六、实验注意事项1注意对不同算法复杂度的比较。2注意观察实验结果。实验五 实现典型的查找算法一、目的与要求1通过本实验，熟悉查找基本概念。 2熟悉查找中使用的相关存储结构，掌握顺序查找和折半查找算法。二、实验内容1、几种典型的查找算法2、计算查找成功和查找失败时的时间复杂度并比较三、仪器、设备和材料1适合实验要求计算机系统2C语言变成平台三、实验原理 查找是计算机内经常进行的一种操作，其目的是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。四、实验步骤1输入记录的基本结点与信息，选用相关的存储结构，完成记录的存储，完成记录初始化。2编程实现顺序查找算法和折半查找算法；3计算两种算法查找成功和失败时的时间复杂度；六、实验注意事项1注意对不同算法复杂度的比较。2注意观察实验结果。七、实验思考题1请为有序序列选择适合的数据结构进行存储。2给出如下12个数字，请给出其有序（升序）序列。 36，47，58，12，17，22，97，1