数据结构综合性实验教学大纲

数据结构综合性实验教学大纲

实验项目名称：哈夫曼编码/译码器；拓扑排序和关键路径

所涉及综合知识或相关课程：《软件工程》、《C语言程序设计》

计划学时：5学时

课程类型：专业选修课

一、实验目的与要求

目的：通过实验，可使学生深刻理解逻辑结构、存储结构的特性，培养实际问题

分析能力。通过编写算法，掌握的程序设计方法和技术，为计算机软件设计、开发打

下良好的基础。

要求：熟悉TC2.0或VC++的编程和调试环境，根据实验内容和要求，认真完成程

序编写、上机调试、运行结果分析，撰写实验报告。

二、实验内容提要

实验选题：（1）哈夫曼编码/译码器；（2）拓扑排序和关键路径

（1）哈夫曼编码/译码器

Huffman编码是最优变长码，请设计一个Huffman编码程序，实现以下功能：

（a）接收原始数据（从终端读入字符集大小n、n个字符及其权值，建立Huffman

树）

（b）编码（利用已建立的Huffman树，对文件中的正文进行编码）

（c）译码（利用已建立的Huffman树将编码的文件进行译码）

（d）打印编码规则（即：字符与编码之间的一一对应关系）

（e）打印Huffman树（将已存入内存中的Huffman树打印在屏幕上显示）

（2）拓扑排序和关键路径

实现AOV网的拓扑排序和AOE网的关键路径求法，而在求关键路径过程中用到拓

扑排序来判断图中是否存在回路。为保持图的初始化一致性，虽然在拓扑排序算法中

不要求边的权值，但关键路径需要，所以在输入图的时候都规定了一种格式：

（V1,V2,W1）,表示边（VI,V2）上的权值为W1。本程序应实现以下功能：

（a）初始化图（将图转化为计算机可以识别的方式，数据结构用邻接表）

（b）求出图中所有顶点的入度（首先给入度向量赋初值为0,然后对顶点表中的

每一个顶点，依次访问与此顶点相关联的边，并令入度自增1。当遍历所有顶点后，也

就求出了所有顶点的入度）

(c)拓扑排序(先得到所有结点的入度，将所有入度为0的顶点压栈，进行栈的

操作)

(d)求关键路径

三、实验步骤及结果测试

♦哈夫曼编码/译码器

Huffman编码是一种最优变长码，即带权路径长度最小。本实验实现了最简单的一

种Huffman编码，可以实现把一个文件中的字符集合进行编码，转换为相应的0/1代

码，同时可以把0/1代码进行译码，还原原始文件等功能。实验步骤如下：

1.数据结构设计

每个结点有三个指针域：IchiId,rchild,parent,本身字符信息以及相应的权值。

在编码类型设计中，为了实现字符与编码的一一对应关系，定义了存放字符域letter

和存放二进制代码域bit。具体数据结构类型定义如下：

#defineMAXLEAF50/*叶子最多个数*/

typedefstructhnode{/*结点类型定义*/

charletter;

intweight,parent,Ichild,rchild;

}HuffmanNode;

typedefstruct{/*编码类型定义*/

charletter,bit[MAXLEAF];

intstart;

}HCode;

2.功能函数设计

(1)Huffman树的初始化函数InitHuffman()

提供两种建立Huffman树的方法：①ComputerLoading;②ManCreateo

当用户选择从文件中读取时，程序调用函数WriteHuffmanO以得到树的初始化。

(2)建立Huffman树函数HuffmanTree()

此算法的基本思想为：

①由给定的n个树值{wl,w2,w3,…,wm},构造m棵由空二叉树扩充得到的扩充二叉

树，每一个扩充二叉树只有一个外部结点，它的权值为wi。

②在已经构造的所有扩充二叉树中，选到根结点的权值最小和次小的两个，将它们

作为左、右子树，构造成一棵新的扩充二叉树，它的根结点的权值为两子树的权值之

和。

③重复执行步骤②，每次都扩充二叉树的个数减一，当只剩下一棵扩充二叉树时，

它是所要构造的Huffman树。

(3)编码函数HuffmanCode()

从根结点开始，寻找每一个叶子结点，在寻找的过程中，经过左子树时，编码增加

“0”，经过右子树时，编码增加“1”，当每一个叶子结点都访问过时，便得到相应

的编码。

(4)译码函数Hencode()

开始时，读入所有的0/1代码入内存，遇过“0”转向左孩子结点，遇到“1”转向

右孩子结点，直到遇到叶子结点时，访问该结点时，继续下一组代码转换，直到所有

的代码读写结束。

(5)查看编码规则函数HshowCodeO

对已经建立好的Huffman编码，通过此函数以较为直观的方式显示给用户看。

首先进行合理性检查，如果树还没有建好，则拒绝显示编码规则。当通过检测后，

把能以前建立好的代码打印出即可。

(6)对一些字母进行编码函数CharCode()

如同上面的查看函数，这里也设计了防错。当条件满足进，把文件中的所有字符读

入内存，用上面建立的编码规则进行编码，并把转换后的0/1代码存入文件

codefile,dat中。

(7)查看已建立的Huffman树函数HuffmanShowTree()

当树不为空时，运用相关数学知识，借用C函数库中的图形功能画出树的图形。

(8)Huffman树的主选择函数HuffmanMenu()

打印所有可供选择的操作。用户可根据需要选择相应的操作，程序再执行相应的功

能函数即可。若选择不在此选择范围之内，系统认为是选择了查看编码规则这一函数。

3.根据上面的分析再进行编码和结果测试。

♦拓扑排序和关键路径

采用两种不同的图的表示办法，实现拓扑排序和关键路径的求解过程。使用实现

的算法对A0E网的拓扑排序和关键路径求法，并分析不同存储结构对于算法效率的影

响。在求关键路径过程中用到拓扑排序来判断图中是否存在回路。为了保持图的初始

化一致性，虽然在拓扑排序算法中不要求边的权值，但关键路径需要，所以在输入图

的时候都规定了一种格式：(V1,V2,W1),表示边(VI,V2)上的权值为W1。

1.数据结构设计

在用邻接表当作图的存储结构时，它包括两部分：顺序存储的顶点表与各个顶点

相关联的链式存储的边表。顶点表包括：顶点字段(vertex)存放顶点vi信息，指针

字段(edgelist)存放与vi相关联的边表的第一个结点位置。边表中每个边结点表示

的都是与vi关联的边：包括位置字段(endvex),权字段(weight),链字段(nextedge)。

具体说明如下：

typedefstructedgenode{

intendvex;/*相邻顶点在顶点表中的下标*/

intweight;/*边的权值*/

structedgenodenextedge;/*链字段*/

}EdgeNode,*EdgeList;/*边表中的结点*/

typedefstruct{

intvertex;/*顶点*/

EdgeListedgelist;/*边表头指针*/

}VexNode;/*顶点表中的结点*/

typedefstruct{

intvexnum;/*图的顶点数*/

intarcnum;/*图的边数*/

VexNodevexs;/*顶点表

}GraphList;/*图的邻接表表示法*/

2.功能函数设计

(1)初始化图函数InitGraphO

这是图转化为计算机可以识别的方式，数据结构用的是邻接表。首先提示输入此图

的顶点个数和边数，格式为：(vertexnum,arcnum)。再依次输入所有的边信息：(起

点，终点，权值)，程序将自动建立图的邻接表，这是实现下述所有功能的基础。

(2)求出图中所有顶点的入度函数FindlnDegreeO..

首先给入度向量赋初值为0,然后对顶点表中的每一个顶点，依次访问与此顶点相

关联的边，并令入度自增1。当遍历所有顶点后，也就求出了所有顶点的入度。

(3)拓扑排序函数据TopSort。

拓扑排序前，先调用FindlnDegreeO得到所有结点的入度，然后将所有入度为0

的顶点压栈。从栈顶取出一个顶点将其输出，由它的出边表可以得到以该顶点为起点

的出边，将这些边的入度减1,即删除这些边。如果某条边终点的入度为0,则将该顶

点压栈。反复进行上述操作，直到栈空，如果这时输出的顶点个数小于图的边数，则

说明该A0V网中存在回路，否则，拓扑排序正常结束。拓扑序列放在向量plopo中。

(4)求关键路径函数CritcalPathO

ee(j)：事件vj可能的最早发生时间；le(i)：事件vi允许最迟发生时间；

e(k)：活动<vi,vj>的最早开始时间；1(始:活动<vi,vj>的最晚开始时间;

ee(O)=0；ee(j)=max{ee(i)+weight(<vi,vj»},Kj<n-1；

le(n-1)=ee(n-1);le(i)=min{le(j)-weight(<vi,vj>)},OWiWn-2;

e(k)=ee(i);1(k)=le(j)-weight«vi,vj»

计算ee(j)必须在顶点vj所有前驱顶点的最早发生时间都已经求出的前提下进行,

而计算le(i)必须在顶点vi所有后继顶点的最迟发生时间都已经求出的前提下进行，

因此，顶点序列必须是一个拓扑序列，故这里调用了TopoSortO来判断图中