124
函数返回值：1～7 中的一个序号。
可供选择的功能如下：
1--- Initialization 2---Encode 3---Decode
4---Print huffmantree 5---Print huffman Table 6---Print char Coding 7---Quit
(3)初始化函数：Initialization
函数格式：void Initialization() 函数参数：无参数
函 数 功 能 ： 输 入 编 码 字 符 和 权 值 ， 生 成 哈 夫 曼 树 和 字 符 编 码 ， 并 用 文 件
TableFileName 和 CodeFileName 保存哈夫曼树和字符编码数据。 函数返回值：无
(4)文本串编码函数：Encode
函数格式 void Encode(void)
函数功能：从文本串文件 SourceFileName 中读入文本字符，按照 CodeFileName
文件中字符的编码将其转换为“0”和“1”表示的哈夫曼编码，并把编码 结果写入文件 EnCodeFileName 中。 函数参数：无 函数返回值：无
(5)译码函数：Decode
函数格式 void Decode()
函数功能：从文件 EnCodeFileName 中读入“0”和“1”表示的哈夫曼编码数
据，将其转换为文本字符，并将译码结果写入文件 DecodeFileName 中。 函数参数：无 函数返回值：无
(6)显示哈夫曼树函数：PrintHuffmanTree
函数格式 void PrintHuffmanTree() 函数功能：以凹式形式显示哈夫曼树
函数参数：无 函数返回值：无
(7)显示哈夫曼树表函数：PrintHuffmanTable
函数格式 void PrintHuffmanTable() 函数功能：以表格形式显示哈夫曼树 函数参数：无
125
函数返回值：无
(8)显示字符哈夫曼编码函数：PrintCharCoding
函数格式 void PrintCharCoding() 函数功能：显示字符的哈夫曼编码 函数参数：无 函数返回值：无
(9)读文件函数：ReadFromFile
函数格式 int ReadFromFile()
函数功能：从文件 TableFileName 中读哈夫曼树数据 函数参数：无
函数返回值：0—读数据失败
>0--读入的数据个数
(10)选择根界点函数：Select
函数格式 void Select(struct node ht[],int n, int *s1,int *s2)
函数功能：从多棵树中选择两个权值最小的根结点 函数参数：struct node ht[]—哈夫曼树
int n—选择结点的范围，即只能在 0～n 中选择结点 int *s1—指向第一个权值最小的结点的指针
int *s2—指向第二个权值最小的结点的指针
函数返回值：无
五、主要算法描述
1、初始化函数 Initialization 算法描述
功能：读入字符及其权值，生成哈夫曼树和字符哈夫曼编码。
字符输入的处理：C 语言输入字符的处理很不方便，任何一个字符都当作有效字符处理， 包括空格字符和回车符。而用格式读函数读字符串很方便，空格字符和回车符都当作字符串 数据的分隔。因此，可以先把字符用格式读函数把字符读入字符数组中，再将其赋值给字符 变量，这样处理更简单。
算法步骤：
（1）输入：读入 n 个叶结点的字符和权值存放于静态树 T 中的前 n 个分量中。
（2）初始化：将树 T 的其余结点的三个指针均置为空（-1），权值置为 0，字符为“*”。
（3）合并：进行 n-1 次合并，将产生的新结点 i 依次放入 T 的第 i 个分量中（n≤i≤m-1）。
合并分两步进行：
①在当前森林 T[0..i-1]的所有结点中，选取权最小和次小的两个根结点 T[p1]和 T[p2] 作为合并对象。（0≤p1,p2≤i-1）
②将根为 T[p1]和 T[p2]的两棵树作为左右子树合并为一棵新的树。新树的根为 T[i]， 权值为 T[p1]和 T[p2]的权值之和。并且 T[p1]和 T[p2]的 parent 为 i，T[i]的 lchild 和 rchild
126
分别为 p1 和 p2。（4）保存哈夫曼树数据。 （5）生成字符编码。
（6）保存字符编码数据。 算法描述如图 7-3 所示。
接口参数：(无) do-While(n<=1) 输入权值个数 n 计算结点个数 m=2n-1,申请存储空间 ht 输入字符和权值 for(i=0;i 127 2、编码函数 Encode 算法描述 原理：对被编码文件中的每个字符，在编码数据表中查找，若字符在编码数据表中，则取 出字符编码放入结果文件中。 算法描述如图 7-4 所示。 接口参数：(无) 打开字符编码数据文件 读入字符及编码数据 从键盘上读入被编码文本串 把读入的文本串存储到文件中 打开存放编码结果的数据文件 读入字符及编码数据 写编码到文件 i++; break for(i=0; Encodestr;) for(j=0;j 图 7-4 编码函数算法描述意图 3、译码函数 Decode 算法描述 译码原理：依次从文件中读入“0”和“1”串，从哈夫曼树根结点开始，若读入的是“0”， 则指针以到根结点的左孩子结点；若为“1”，则指针以到根结点的右孩子结点。重复该过程， 直到指针达到哈夫曼树的叶结点，输出该叶结点对应的字符，即完成一个字符的译码。 算法描述如图 7-5 所示。 128 接口参数：(无) 读哈夫曼树数据文件数据 打开编码数据文件,文件指针 cfp 打开译码数据文件,文件指针 tfp f=m-1 ch=fgetccfp) while((!feof(CFP))&& ht[f].lchild!=-1) f=ht[f].lchild ch==?0? f=ht[f].lchild While(!feof(cfp)) fputc(ht[f].ch,TFP) ht[f].lchild==-1 feof(cfp) break 释放内存空间 关闭文件 return 图 7-5 译码函数算法描述示意图 3、显示哈夫曼树函数 PrintHuffmanTree 算法描述 原理：显示哈夫曼树的过程实际上就是按先根顺序输出哈夫曼树结点的过程。如果要按凹 式形式输出结点，不仅要知道结点的输出顺序，而且要知道结点的层次，通过结点的层次可 以计算出输出内容凹进的格数。在先序遍历的非递归算法中，把结点的层次也作为栈元素的 基本内容就可以解决该问题。 栈的结点结构定义如下：