201320142数据结构实验.docVIP

五邑大学 计算机学院2013-2014（2） 数据结构实验 班级：120803~120805 PAGE 4 实验项目名称：线性表（实验一） 实验目的 (1) 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系有顺序存储结构和链式存储结构； (2) 掌握这两种存储结构的描述方法； (3) 掌握线性表的基本操作（查找、插入、删除）； (4) 考虑时间和空间复杂度设计算法。 2、实验内容 （1）创建一个顺序表，存放在数组A[N]中，元素的类型为整型，设计算法调整A，使其左边的所有元素小于0，右边的所有元素大于0（要求算法的时间复杂度和空间复杂度均为O(n)）。 建立一个循环单链表，其节点有left,data和right三个域，其中data为数据域，存放元素的有效信息，right域为指针域，指向后继节点，left为指针域，它的值为NULL。编写一个算法将此表改为循环双链表。 实验项目名称：栈（实验二） 、 实验目的 (1) 理解栈的定义、特点及与线性表的异同； (2) 熟悉顺序栈的组织方法，栈满、栈空的判断条件及其描述； (3) 掌握栈的基本操作（进栈、退栈等）。 2、实验内容 (1) 设计一个算法，将一般算术表达式转化为逆波兰表达式，并求逆波兰表达式的值。 (2) 设计两个栈S1、S2都采用顺序栈方式，并且共享一个存储区[0，MaxLen-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向、迎面增长的存储方式，如下图所示。设计一个有关栈的入栈和出栈算法。 实验项目名称：队列（实验三） 、 实验目的 (1) 理解队列的定义、特点及与线性表的异同； (2) 熟悉队列的组织方法，队列满、队列空的判断条件及其描述； (3) 掌握队列的基本操作（入队、出队等）。 2、实验内容 (1) 假设以数组sequ[MaxSise]存放环形队列的元素，同时rear和len分别指示环形队列中队尾元素的位置和内含元素的个数。设计相应的入队和出队算法。 (2) 某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分别为客车类和货车类，上船有如下规定：同类车先到先上船，客车先于货车上渡船，且每上4辆客车，才允许上一辆货车；若等待客车不足4辆则以货车代替；若无货车等待则允许客车都上船。设计一个算法模拟渡口管理。 实验项目名称：二叉树（实验四） 1、实验目的 (1) 掌握二叉树的结构特性和二叉链表存储结构； (2) 理解二叉树、完全二叉树、满二叉树的概念和存储特点； (3) 掌握二叉树遍历的递归和非递归方法。 2、实验内容 （1）假设二叉树采用链接存储方式存储，分别编写一个二叉树先序遍历的递归算法和非递归算法。 （2）一棵完全二叉树以顺序方式存储，设计一个递归算法，对该完全二叉树进行中序遍历。 实验项目名称：哈夫曼树（实验五） 1、实验目的 (1) 理解哈夫曼树的概念、结构特性和哈夫曼编码原理； (2) 掌握构造哈夫曼树的基本方法； (3) 掌握运用哈夫曼树进行哈夫曼编码的方法； 2、实验内容 根据哈夫曼(Huffman)编码的原理，编写一个程序，在用户输入节点权重的基础上建立它的哈夫曼编码。 实验项目名称：图（实验六） 1、实验目的 (1) 理解图的基本概念、图的结构特性； (2) 掌握邻接表表示图的基本方法； (3) 掌握连通图遍历的基本的方法。 2、实验内容 (1) 用邻接表存储一个图G。分别设计实现下列要求的算法： -求出图G中每个顶点的出度； -求出图G中出度最大的一个顶点，输出该顶点的编号； -计算图G中出度为0的顶点数。 (2) 编写一个实现连通图G的深度优先遍历（从顶点V0出发，以邻接矩阵为存储结构）的递归和非递归函数，分别用这两种方法对图进行深度优先遍历，比较遍历结果。 实验项目名称：图（实验七） 1、实验目的 (1) 理解拓扑排序的基本概念和拓扑排序的实用意义； (2) 掌握AOV-网解决拓扑排序问题的基本方法。 (3) 理解最小生成树的基本概念和实用意义； (4) 掌握利用MST性质构造最小生成树的prim算法和Kruskal算法。 2、实验内容 (1) 教学计划编制问题。按先修课程和后续课程关