数据结构课程设计报告—哈夫曼编码译码器.doc

《数据结构课程设计报告—哈夫曼编码译码器.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计报告设计题目专业班级姓名学号完成日期目录1.问题描述……………………………………………第2页2.系统设计……………………………………………第2页3.数据结构与算法描述………………………………第5页4.测试结果与分析……………………………………第6页5.总结………………………………………………第10页6.参考文献……………………………………………第10页附录程序源代码………………………………………第11页课程设计题目1.问题描述利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码

2、系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。试为这样的信息传输写一个哈夫曼编/译码系统。2.系统设计2.1设计目标一个完整的系统应具有以下功能：1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。输出哈夫曼树，及各字符对应的编码。2）W：输入（Input）。从终端读入需要编码的字符串s，将字符串s存入文件Tobetran.txt中。3）E：编码（Encoding）与译码（Decoding）。编码（Encoding）。利用已建好的哈夫曼树（如不在存，则从

3、文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。4）T：印哈夫曼树（TreePrinting）。将已在存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。5）Q：退出程序。返回WINDO

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

5、多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。2.3系统模块划分main()Initialization（）初始化函数Input()输入待编码字符函数Encoding（）编码函数Decoding（）译码函数Code_printing()打印编码函数Tree_printing()打印哈夫曼树图2-3哈夫曼编/解码器的程序结构图2.3.1初始化算法：程序从文件abc.txt中获取26个英文字母的权值。2.3.2编码算法：  （1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值{w1,w2,……

6、，wN}构成n棵二叉树的集合F={T1,T2,……，Tn}把它们保存到结构体数组HT[n]中,其中{Ti是按它们的ASCⅡ码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。 （2）在HT[1..i]中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。 （3）哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。2.3.3译码算法：  译码的过程是分解电文中字符串，从根出发，按字符'0',或'1'确定找左孩子或右孩子，直至叶

7、子结点，便求的该子串相应字符并输出接着下一个字符。3.数据结构与算法描述3-1typedefstruct{intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树  typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表3-2intmin(HuffmanTreet,inti)//---------求赫夫曼编码-------------3-3voidselect(HuffmanTreet,inti,int&s1,int&s2)//----slect函数

8、----3-4voidHuffmanCoding(H