C++哈夫曼树与哈夫曼编码.doc

哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容问题描述已知n个字符在原文中出现的频率，求它们的哈夫曼编码。基本要求1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。测试数据利用教材P.148 例62中的数据调试程序。可设8种符号分别为A,B,C,D,E,F,G,H。编/译码序列为 “CFBABBFHGH”(也可自己设定数据进行测试)。三、实验前的准备工作1、掌握树的逻辑结构。2、掌握哈夫曼树的定义及生成算法。3、掌握哈夫曼编码的方法。四、问题分析根据实验内容，首先需要将从键盘读入n个字符以及他们的权值，可以先将他们保存到两个数组中，在建立Huffman树，并进行初始化，将n个字符以及权值保存进Huffman树中，建立完Huffman树后，对每个字符进行编码，可以从子叶逆向求，最后在根据所得的各个字符的编码对给定的字符串进行编码。五、算法设计首先是Huffman树的建立，n个字符Huffman树需要2n-1个结点，为了方便，为HT申请2n个HuffmanTree的动态内存用于建立Huffman树。先对前n个结点进行初始化，将字符和权值分别赋给HTi.charname和HTi.weight，HTi.parent、HTi.lchild、HTi.rchild分别赋0.，其余结点的属性全赋0.选择两个weight最小的结点，将其parent属性改为一个charname为0的结点，并将该结点的lchild和rchild属性分别改为两个结点。以此循环，直至Huffman树建立完成。其次是每个字符的编码，从Huffman树的子叶开始，向上找其parent，若是其parent的左孩子，则在数组cd中计0，又孩子计1，直至结点无parent为止，最后将cd数组中的值strcpy给HT。最后是为字符串编码，字符串的每个字符对应Huffman中的字符，输出其HC中的字符编码即可。六、测试数据1.字符个数：5字符1，2，3，4，5权值1,2,3,4,5理论结果：编码分别为：010,011,00,10,11测试字符串：43152编码：1000010110112.字符个数：8字符A,B,C,E,F,G,H权值5,29,7,8,14,23,3,11理论结果：编码分别为：0001,10,1110,1111,110,01,0000,001测试字符串：BDFGEHCA编码：10111101000011000111100001七、总结对于本次试验，主要是在Huffman树的建立上，选择parent为0且weight最小的两个结点不容易，只要这个问题解决，Huffman树的建立就迎刃而解了，每个字符的编码求起来到不是太难，仅是子叶到根逆向的问题。字符串的编码就更容易了，只需将相应字符的编码输出即可。八、附录#include#includetypedef structchar charname;double weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;int n;char *a;double *b;void initcin()cout请输入字符个数n;a=new charn;b=new doublen;cout请输入字符！endl;for (int i=0;iai;cout请输入权值！endl;for(i=0;ibi;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *a,double*b,int n)if(n=1)return;int m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);int i;for(i=1;i=n;+i)HTi.charname=ai-1;HTi.weight=bi-1;HTi.parent=HTi.lchild=HTi.rchild=0;/coutHTi.parentendl;for(;i=m;+i)HTi.charname=0;HTi.weight=0;HTi.parent=HTi.lchild=HTi.rchild=0;for(i=n+1;i=m;+i)for(int s1=1;HTs1.parent!=0;)s1+;for (int j=s1;j=i-1;j+)if(HTj.parent!=0)continue;s1=HTj.weightHTs1.weight?j:s1;HTs1.parent=i;HTi.lchild=s1;for(int s2=1;HTs2.parent!=0;)s2+;for (j=s2;j=i-1;j+)if(HTj.parent!=0)continue;s2=HTj.weightHTs2.weight?j:s2;HTs2.parent=i;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);char *cd=(char*)malloc(n*sizeof(char);cdn-1=0;for (i=1;i=n;+i)int start=n-1,c,f;for (c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c) cd-start=0;else if(HTf.rchild=c) cd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);f=n-start;for(int d=0;df;d+,start+)HCid=cdstart;void coutHC(HuffmanTree &HT,HuffmanCode &HC,int n)for (int i=1;i=n;i+)coutHTi.weight的编码为：;for(int d=0;HCid!=0;d+)coutHCid;coutendl;void translante(HuffmanTree &HT,HuffmanCode &HC,int n)int d;coutd;char *c=new chard;cout请输入字符串：;for (int i=0;ici;cout编码为：;for (i=0;id;i+)for(int q=1;q=n;q+)if(HTq.charname=ci)for(int f=0;HC