《nghlpAAA哈夫曼编码实验报告》由会员分享，可在线阅读，更多相关《nghlpAAA哈夫曼编码实验报告（10页珍藏版）》请在装配图网上搜索。
1、weight 为输入的频率数组，把其中的值赋给依次建立的 HT Node对象中的 data 属性，即每一个 HT Node 对应一个输入的频率。然后根据 data 属性按从小到大顺序排序，每次从 data 取出两个最小和此次小的 HT Node，将他们的 data 相加，构造出新的 HTNode 作为他们的父节点，指针 parent，leftchild，rightchild 赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找 parent,直到 parent 为树的顶点为止。这样，根据每次向上搜索后，原节点为父节
2、点的左孩子还是右孩子，来记录 1 或 0，这样，每个频率都会有一个 01 编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。六、实验流程 初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树；根据符号概率的大小按由大到小顺序对符号进行排序；把概率最小的两个符号组成一个节点；重复步骤（2）（3），直到概率和为 1；从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”；从根节点开始，对符号进行编码；译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。七、实验程序#include#include#include#include using
3、namespace std;typedef struct .t中选择 parent 不为 0 且权值最小的两个结点，其序号分别为 s1 和 s2 s1=0;s2=0;int n1=30000,n2=30000;for(int k=1;k=i;k+)if(HTk.parent=0)if(HTk.weightn1)n2=n1;n1=HTk.weight;s2=s1;s1=k;else if(HTk.weightn2)n2=HTk.weight;s2=k;void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int n)ata=zifui;HTi.weig
4、ht=weighti;for(i=n+1;i=m;i+)HTi.data=;for(i=1;i=m;i+)HTi.parent=HTi.lchild=HTi.rchild=0;for(i=n+1;i=m;+i)int s1,s2;Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);开辟一个求编码的工作空间 char*cd;cd=(char*)
5、malloc(n*sizeof(char);arent;f!=0;c=f,f=HTf.parent)child=c)cd-start=0;eightsetw(3)HTi.parentsetw(3)HTi.lchildsetw(3)HTi.rchildendl;coutisetw(5)HTi.datasetw(3)HTi.weightsetw(3)HTi.parentsetw(3)HTi.lchildsetw(3)HTi.rchildendl;void printHuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n)ata;cout(HCi)endl
6、;fout(HCi)endl;void code_file(HuffmanTree HT,HuffmanCode HC,int n)ata)foutHCj;break;();();void Decoding(HuffmanTree HT,HuffmanCode HC,int n)child)if(ai=1)p=HTp.rchild;else p=HTp.lchild;i+;foutHTp.data;coutHTp.data;void main()int n;coutn;printf(n);HuffmanTree HT;/哈夫曼树 HT HuffmanCode HC;/哈夫曼编码表 HC Huf
7、fmanCoding(HT,HC,n);/进行哈夫曼编码 printHuffmanCoding(HT,HC,n);/显示编码的字符 printf(n);code_file(HT,HC,n);/显示要编码的字符串，并把编码值显示出来 Decoding(HT,HC,n);/译码并显示译码后的字符串 printf(nnn);system(pause);八、结果分析 哈夫曼编码是动态变长编码，临时建立概率统计表和编码树。概率小的码比较长，概率小的码比较长。概率大的码短，这样把一篇文件编码后，就会压缩许多。从树的角度看，哈夫曼编码方式是尽量把短码都利用上。首先，把一阶节点全都用上，如果码字不够时，然后，再从某个节点伸出若干枝，引出二阶节点作为码字，以此类推，显然所得码长最短，再根据建立的概率统计表合理分布和放置，使其平均码长最短就可以得到最佳码。九、实验总结 通过这次实验，我对二叉树和哈希曼树有了更好的认识。在实验过程中，我掌握了哈曼树的构造方法，学会了如何将理论知识传换成实际应用。同时，在解决程序中遇到的一些问题的同时，我也对调试技巧有了更好的掌握，分析问题的能力也略有提高。在实验中，我遇到了许多难点，比如：统计字符的权值，就需要我们有扎实的基础，需要有灵活的头脑，只有不断的练习，不断的训练，我们才能处理各种问题。在以后的学习中，我要不断的努力，多联系，多思考，我相信我能有所进步的。
nghlpAAA哈夫曼编码实验报告
