《数据结构课程实验》大纲

实习四 树、图及其应用

树和图是两种应用极为广泛的数据结构，也是这门课程的重点。它们的特点在于非线性。广义表本质上是树结构；稀疏矩阵的十字链表存储结构也是图的一种存储结构，故也把它们归在这次实习中。本章实习继续突出了数据结构加操作的程序设计观点，但根据这两种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。遍历逻辑的（或符号形式的）结构，访问动作可是任何操作。本次实习还希望达到熟悉各种存储结构的特征，以及如何应用树和图结构解决具体问题（即原理与应用的结合）等目的。

1、二叉树的建立与遍历 [问题描述]

建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。 [基本要求]

从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。 [测试数据]

ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA [选作内容]

采用非递归算法实现二叉树遍历。

2、打印树结构 [问题描述]

按凹入表形式打印树形结构。 例如：

[测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空树。 [实现提示]

（1）利用树的先根遍历方法；

（2）利用结点的深度控制横向位置。

3、哈夫曼编码/译码器 【问题描述】

设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。

【基本要求】

(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树； (2)编码：利用建好的哈夫曼树生成哈夫曼编码； (3)输出编码；

(4)设字符集及频度如下表：

字符 空格 A B C D E F G H I J K L M

频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z

频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【选做内容】 (1)译码功能； (2)显示哈夫曼树； (3)界面设计的优化。

4、图遍历的演示 [问题描述]

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示无向图的遍历操作。 [基本要求]

以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。 [实现提示]

设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,?,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。 [选作内容]

（1） 借助于栈类型（自己定义和实现）将深度优先遍历用非递归算法实现。

（2） 以邻接多重表为存储结构建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树

（3） 实现有向图的遍历操作。

实习五 查找和排序

本次实习旨在集中对几个专门的问题作较为深入的探讨和理解，不强调对某些特定的编程技术的训练。

1、二叉排序树 [问题描述]

从键盘读入一组数据，建立二叉排序树并对其进行查找、遍历、格式化打印等有关操作。 [基本要求]

建立二叉排序树并对其进行查找，包括成功和不成功两种情况，并给出查找长度。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据。 [选作内容]

实现二叉排序树的插入、删除操作。

2、哈希表设计 [问题描述]

针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。 [基本要求]

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 [测试数据]

取读者周围较熟悉的30个人名。 [选作内容] （1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。

（2） 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。

（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。

3、内部排序算法比较 [问题描述]

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 [基本要求]

（1） 对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。

（2） 待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。 [测试数据]

由随机产生器决定。 [实现提示]

主要工作是设法在程序中适当的地方插入计数操作。程序还可以包括计算几组数据得出结果波动大小的解释。注意分块调试的方法。

[选作内容]

对不同的输入表长做试验，观察检查两个指标相关于表长的变化关系。还可以对稳定性做验证。

3、统计成绩 [问题描述]

给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计，并打印统计表。 [基本要求]

（1） 按总数高低次序，打印出名次表，分数相同的为同一名次； （2） 按名次打印出每个学生的学号、姓名、总分以及各科成绩。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据。 [选作内容]

对各科成绩设置不同的权值。