哈夫曼编译码器 c语言

c语言课程实践 哈弗曼编译器

《数据结构》课程设计

c语言课程实践 哈弗曼编译器

目 录

1. 问题描述 第 2页 2. 系统设计 第 2页 3. 数据结构与算法描述 第 5页 4. 测试结果与分析 第 6页 5. 总 结 第10页 6. 参考文献 第10页

附录 程序源代码 第11页

c语言课程实践 哈弗曼编译器

课程设计题目

1. 问题描述

利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。试为这样的信息传输写一个哈夫曼编/译码系统。

2. 系统设计

2.1 设计目标

一个完整的系统应具有以下功能：

1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。输出哈夫曼树，及各字符对应的编码。 2）W：输入（Input）。从终端读入需要编码的字符串s，将字符串s存入文件Tobetran.txt中。

3）E：编码（Encoding）与译码（Decoding）。

编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。

4）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 5）Q：退出程序。返回WINDOWS界面。 2.2 设计思想

哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这种方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中

c语言课程实践 哈弗曼编译器

各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 2.3 系统模块划分

2.3.1 初始化算法：

程序从文件abc.txt中获取26个英文字母的权值。 2.3.2 编码算法：

（1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为

权值{w1,w2, ，wN}构成n棵二叉树的集合F={T1,T2, ，Tn}把它们保存到结构体数组HT[n]中,其中{Ti是按它们的ASCⅡ码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。

（2）在HT[1..i]中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。

（3）哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。 2.3.3 译码算法：

译码的过程是分解电文中字符串，从根出发，按字符'0',或'1'确定找左孩子或右孩子，直至叶子结点，便求的该子串相应字符并输出接着下一个字符。

3. 数据结构与算法描述

3-1

typedef struct { int weight;

图2-3 哈夫曼

编/解码器的程序结构图

c语言课程实践 哈弗曼编译器

int parent,lchild,rchild;

}HTNode,* HuffmanTree; //动态分配数组存储赫夫曼树 typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表

3-2 int min(HuffmanTree t,int i) // ---------求赫夫曼编码------------- 3-3 void select(HuffmanTree t,int i,int &s1,int &s2) //----slect函数---- 3-4

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)

// w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC 3-5 void Initialization() //----------初始化赫夫曼链表-------------- 3-6 void InputCode() //---------获取报文并写入文件------------- 3-7 void Encoding() //----------------编码函数------------------ 3-8 void Decoding() //-----------------译码函数----------------- 3-9 void Code_printing() //-------------打印编码的函数-------------- 3-19 void coprint(HuffmanTree start,HuffmanTree HT) //------------------------打印赫夫曼树的函数-----------------------

3-20 void main() //--------------------主函数-------------------

4. 测试结果与分析

表4-1 abc.txt文件中的字母和权值

声明：程序预先将Huffman编码解码所需的26个字母和权值保存在根目录下的abc.txt文件下。

c语言课程实践 哈弗曼编译器

4-1.按照程序提示输入i对Huffman进行初始化。

4-2.初始化后程序对abc.txt文件中的数据进行读取并运行编码函数进行哈夫曼编码。然后将字母、权值和哈夫曼编码存在根目录下的htmTree.txt文件中。在屏幕显示出字

符、权值、编码。

c语言课程实践 哈弗曼编译器

4-3.输入w进入待编码字符输入窗口，并键入字符串（注意单词间无空格）“happynewyear”。

4-4.可以看出所获得的字符串已经存入根目录下的tobetran.txt文件中

。

4-5.输入e进行编码、译码和打印编码功能。 4-6.

输

入

t

打

印

哈

夫

曼

树

。

c语言课程实践 哈弗曼编译器

由于哈夫曼树过于巨大，一次截屏无法完全显示，使用两次截屏。

以上两幅图显示出来程序编出的哈夫曼树的形状。打印出来的图形与教科书上的常见哈夫曼树略有不同，左边的数是右边数的父节点。 4-7.输入q退出程序。

5. 总 结

5-1、用户界面设计为“菜单”模式，使人们更加容易使用。

5-2、在程序的一次执行过程中，第一次执行e命令之后，哈夫曼树已经在内存了，不必再读入。

5-3.在编程中使用了很不规范的编程方法，应用了一些临时变量来实现功能，，而大量临时变量在代码中没有很好地进行命名。这给程序的阅读和维护带来了极大的困难。 5-4.本程序仅能对26个小写字母构成的字符串进行处理，并不具有对汉字等的编码处理能力。

c语言课程实践 哈弗曼编译器

5-5.设计中得到了老师和广大同学的帮助，并参考了网络上的优秀论文和纸质文件，使我的程序设计能够较为顺利的进行下去。在此我衷心感谢我的老师同学和对以上资源的作者 …… 此处隐藏：8608字，全部文档内容请下载后查看。喜欢就下载吧 ……