哈夫曼树的编码与译码

《哈夫曼树的编码与译码》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、目录一、摘要5二、题目6三、实验目的6四、实验原理6五、需求分析75.1实验要求75.2实验内容7六、概要设计76.1所实现的功能函数76.2主函数86.3系统结构图9七、详细设计和编码9八、运行结果15九、总结189.1调试分析189.2心得体会18参考文献1916一、摘要二、题目哈夫曼树的编码与译码三、实验目的（1）熟悉对哈夫曼的应用以及构造方法，熟悉对树的构造方式的应用；（2）进一步掌握哈夫曼树的含义；（3）掌握哈夫曼树的结构特征，以及各种存储结构的特点以及使用范围；（4）熟练掌握哈夫曼树的建立和哈夫曼编码方法；（5）提高分析问题、解决问题的能力，进

2、一步巩固数据结构各种原理与方法；（6）掌握一种计算机语言，可以进行数据算法的设计。四、实验原理哈夫曼（Huffman）编码属于长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（codingtree）的技术。算法步骤如下：（1）初始化，根据富豪概率的大小按由大到小顺序对符号进行排序；（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和；（3）重复第（2）步，直到形成一个符号为止（树）

3、，其概率最后等于1；（4）从编码树的根开始回溯到原始的符号，并将每一下分支赋值1，上分支赋值0；译码的过程是分解电文中字符串，从根出发，按字符“0”或者“1”确定找做孩子或右孩子，直至叶子节点，便求得该子串相应的字符。16五、需求分析5.1实验要求（1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树的存储结构；（2）利用已经建好的哈夫曼树，对给定的n个字符正文进行编码，并输出结果。（3）利用已建好的哈夫曼树，对给定的一个哈夫曼编码进行译码，判断此编码对应的字符，并输出结果。5.2实验内容（1）定义哈夫曼树结构；（2）初始化哈夫曼树，存储哈夫曼

4、树信息；（3）定义哈夫曼编码的函数；（4）定义哈夫曼译码的函数；（5）写出主函数；（6）测试系统；（7）运行程序。六、概要设计6.1所实现的功能函数voidinitHuffmanTree();//初始化哈夫曼树intinputInit();//进行哈夫曼树的初始化intHuffmanCoding(int*w);//初始化哈夫曼数，按照哈夫曼规则建立二叉树。此函数块调用了Select()函数。voidSelect(intj,int&s1,int&s2);//选择parent为0，且weight最小的两个节点序号为s1，s2voidencoding();//哈

5、夫曼编码voidinputEnco();//进行哈夫曼编码voiddecode();//哈夫曼译码16voidinputDeco();//进行哈夫曼译码6.2主函数intmain(){intsel=0;cout<<"XinYun"<

6、;cout<<"t*t"<<"3.decode"<>sel;if(sel==4)break;switch(sel){case1:initHuffmanTree();break;case2:encoding();break;case3:decode();break;default:cout<<"Sorry!Thenumberyouhaveinputiswrong!"<

7、utstuf.close();cout<<"Thankyoutouseit!!!"<

8、ncoding（）译码调用decode（）调用inputEnco（