数据结构与算法实验指导书(计科1021)(3)

3) 遍历算法分别用递归和非递归算法。

实验十：二叉树的应用 求二叉树叶子结点个数和深度

一、问题描述：

已知一棵二叉树，求该二叉树中的叶子结点的个数和深度。 二、基本要求：

1) 采用二叉链表存储结构；

2) 设计算法求二叉树中的叶子结点的个数和二叉树t的深度。 三、设计思想：

在实验九（二叉树的操作）的基础上设计算法求二叉树中的叶子结点个数和二叉树t的深度。

分别用递归和非递归算法。

实验十一：二叉树的应用（哈夫曼编码）

一、问题描述：

设某编码系统共有n个字符，使用频率分别为（w1,w2,…,wn）。设计一个不等长的编码方案，使用该编码系统的空间效率最好。 二、基本要求：

1) 设计数据结构； 2) 设计编码算法；

3）分析算法的时间复杂度和空间复杂度。

三、设计思想：

利用Huffman编码树求得最佳的编码方案。

根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组Huffman，保存哈夫曼树中各结点的信息，每个结点包括权值、左孩子、右孩子和双亲。由于哈夫曼树中共有2n－1个结点。并且进行n－1次合并操作，所以该数组的长度为2n－1。

weigth lchild rchild parent 在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼树编码。

实验十二：图的操作

一、实验目的：

1）掌握图的存储结构； 2）掌握构造邻接矩阵的方法； 3）掌握图的遍历算法的算法实现。 二、实验内容及要求：

按给定的任一连通无向图构造邻接矩阵，再进行深度优先遍历和广度优先遍历。

实验十三：图的应用 求无向连通图的生成树

一、问题描述：

求无向连通图的一棵生成树。 二、基本要求：

1）采用邻接矩阵存储； 2) 求深度优先生成树； 3) 输出该生成树的每一条边。 三、设计思想：

在一个连通无向图G=(V,E)中，如果从任一个顶点开始进行深度优先遍历，必定将边集E分成两个集合T和B,其中T是遍历过程中经历的边的集合，B是剩余的边的集合。显然，边集T和图G所有顶点一起构成连通图G的一棵生成树。因此，修改深度优先遍历算法，输出遍历所经过的边。

实验十四：图的应用

求有向图的路径

一、问题描述：

对于有向图G=(V,E),任意vi，vj (i≠j),判断从顶点vi到顶点vj是否存在路径。 二、基本要求：

1）有向图采用邻接矩阵存储； 2) 设计算法完成问题求解；

3) 设计存储结构存储从顶点vi到顶点vj的路径。

三、设计思想：

可以利用深度优先遍历，从顶点vi出发进行深度优先遍历，如果在遍历过程中，访问到顶点vj，则从顶点vi到顶点vj存在路径。 因此，修改深度优先遍历算法，判断在遍历中是否访问顶点vj。

实验十五：查找操作

一、实验目的：

1）掌握顺序查找技术和拆半查找技术； 2）掌握查找的算法实现； 二、实验内容及要求：

1、产生n个随机整数用顺序查找的方法进行查找操作，并统计查找的次数。

2、给定n个有序整数用折半查找的方法进行查找操作，并统计查找的次数。

要求分别用初始化函数，顺序查找函数，折半查找函数及输出函数来完成。

实验十六：查找应用 散列表的建立和查找

一、实验目的：

1）掌握散列查找的基本思想； 2）掌握闭散列表的构造方法； 3) 掌握线性探测处理冲突的方法；

4) 掌握散列技术的查找性能。 二、实验内容及要求：

1) 对于给定的一组整数和散列函数，采用线性探测法处理冲突构造散列表；

2) 设计查找算法，验证查找性能。

实验十七：排序操作

一、实验目的：

1）深刻理解各种排序算法的设计思想； 2）掌握各种排序算法的执行过程； 3）掌握各种排序算法的设计实现。 二、实验内容及要求：

产生n个随机整数分别采用直接插入排序、希尔排序和冒泡排序的方法进行排序。

要求分别采用各排序函数和输出函数来完成。

实验十八：排序应用

一、问题描述：

一个班有n个学生，每个学生有学号（no）、姓名（name）、年龄（age）、成绩（score）。定义数据结构来描述学生信息。并按成绩进行降序排列。 二、基本要求：

1) 可任用一种排序算法，按成绩进行降序排列。 2) 输出已排序的学生数据；要求输出整齐。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构与算法实验指导书(计科1021)(3)在线全文阅读。