实验四--哈夫曼树与哈夫曼编码

实验四哈夫曼树与哈夫曼编码一、实验内容[问题描述]已知n个字符在原文中出现的频率，求它们的哈夫曼编码。[基本要求]1.初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。（具体算法可参见教材P147的算法6.12）2.编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。二、概要设计算法设计：要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两个权值最小的作为新的两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。流程图：算法：开始输入哈弗曼树的带权结点数目n输入相应的权值和对应的字符建立哈夫曼树Huffmantree(HT,w,n,e)显示哈夫曼树outputHuffman(HT,m)哈夫曼树的编码CHuffmancode(HT,HC,n)结束主函数Huffmantree(HuffmanTree&HT,int*w,intn,char*e)*hc,intn)CHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn)outputHuffman(HuffmanTreeHT,intm)select(HuffmanTree*ht,intn,int*s1,int*s2)模块：在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下：首先建立一个哈夫曼树和哈夫曼编码的存储表示：typedefstruct{intweight;intparent,lchild,rchild;charelem;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree*ht,int*w,intn)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。构造哈夫曼树：for(i=n+1;i=m;++i){//在HT[1……i]选择parent为0且weight最小的两个Select(HT,i-1,&s1,&s2);开始叶子初始化非叶子初始化调用select函数选择权值最小的两个这两个权值最小的两个字符非别作为同一个结点的左右孩子，其父母的权值为两个字符的权值之和结束HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[Select(HuffmanTree&HT,intn,int*s1,int*s2)：在所给的权值中，选择出权值最小的两个值。inti,min;for(i=1;i=n;i++){if(HT[i].parent==0){min=i;i=n+1;}}for(i=1;i=n;i++){if(HT[i].parent==0){if(HT[i].weightHT[min].weight)min=i;}}*s1=min;在选择s2的时候和s1相似，只有在判断是否为最小的时候就，要加上一个条件：if(HT[i].parent==0&&i!=*s1)，就可以了，否则，选出来的最小权值和s1就相等了，失去了选择的意义了。CHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn)：从叶子到根逆向求编码：左孩子为0，右孩子为1，这样一直循环下去，而最重要的是：for(inti=1;i=n;++i){star=n-1;//从右向左逐位存放编码，首先存放编码结束符for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根结点求编码if(HT[f].lchild==c)cd[--star]='0';//左分支标0elsecd[--star]='1';//右分支标1HC[i]=newchar[n-star];//为第i个编码分配空间strcpy(HC[i],&cd[star]);//从cd复制编码串到HC}outputHuffman(HuffmanTreeHT,intm)：显示出哈夫曼树的编码和字符以及权重，与二叉树的遍历相似：if(m!=0){coutHT[m].elemHT[m].weightendl;outputHuffman(HT,HT[m].lchild);outputHuffman(HT,HT[m].rchild);}三、测试数据测试一：字符为：ABC权重：10128测试数据二：字符为：ABCDEFG权重为：788121596四、结果调试调试一：否是是开始从叶子到根结点求编码c=if=HT[i].parentf!=0c=将0输入到cd数组HT[f].lchild==c中将1输入到cd数组HT[f].lchild==c从cd复制编码串到HCc=f,f=HT[f].parent否输出字符权值相应的编码结束调试二：五．总结在进行这个程序的编写的时候，其实有点毫无头绪，只是知道在书上的算法就可以编写成功。但是在一次又一次的过程，还是一次又一次的错误，最后在进行理解才稍微理解了哈夫曼树的编码过程，但是选择权值最小的过程还是不太理解，进行了调试才明白也一些，但是还是没有明白透彻。在这次的实验过程中，我明白了调试的重要性，不要在自己遇到问题的时候就去问同学，因为那样会养成自己的依赖性，在自己不会的时候，不会进行深层次的了解就去问，那样对自己没有太大的提高，只有自己理解和同学的讲解相结合，才能有所提高。六、附录：#includeiostream.h#includestring.htypedefstruct{intweight;intparent,lchild,rchild;charelem;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表////////////////////////求赫夫曼编码voidSelect(HuffmanTree&HT,intn,int*s1,int*s2){inti,min;for(i=1;i=n;i++){if(HT[i].parent==0){min=i;i=n+1;}}for(i=1;i=n;i++){if(HT[i].parent==0){if(HT[i].weightHT[min].weight)min=i;}}*s1=min;for(i=1;i=n;i++){if(HT[i].parent==0&&i!=*s1){min=i;i=n+1;}}for(i=1;i=n;i++){if(HT[i].parent==0&&i!=*s1){if(HT[i].weightHT[min].weight)min=i;}}*s2=min;}////////////////////voidHuffmantree(HuffmanTree&HT,int*w,intn,char*e){//w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCintm,i,s1,s2;if(n=1)return;m=2*n-1;//总的结点HT=newHTNode[m+1];for(i=1;i=n;++i){/*1-n号放叶子结点，初始化*/HT[i].weight=w[i];HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;HT[i].elem=e[i];}for(i=n+1;i=m;++i){/*非叶子结点初始化*/HT[i].weight=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;HT[i].elem=0;}for(i=n+1;i=m;++i){//在HT[1……i]选择parent为0且weight最小的两个Select(HT,i-1,&s1,&s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}}////////////////////////////////////////////////////////voidCHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn){char*cd;intc,f,star;HC=newchar*[n+1];cd=newchar[n];cd[n-1]='\0';//编码结束符for(inti=1;i=n;++i){star=n-1;//从右向左逐位存放编码，首先存放编码结束符for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根结点求编码if(HT[f].lchild==c)cd[--star]='0';//左分支标0elsecd[--star]='1';//右分支标1HC[i]=newchar[n-star];//为第i个编码分配空间strcpy(HC[i],&cd[star]);//从cd复制编码串到HC}deletecd;//释放工作空间for(i=1;i=n;i++)coutHT[i].elemHT[i].weight:HC[i]endl;}/////////////////////////////////////////////////////voidoutputHuffman(HuffmanTreeHT,intm){if(m!=0){coutHT[m].elemHT[m].weightendl;outputHuffman(HT,HT[m].lchild);outputHuffman(HT,HT[m].rchild);}}voidmain(){HuffmanTreeHT;HuffmanCodeHC;int*w;char*e;charc;inti,n,m,wei;cout请输入赫夫曼树的带权数目：;cinn;w=newint[n+1];e=newchar[n+1];for(i=1;i=n;i++){cout请输入第i个元素的权值:;cinwei;w[i]=wei;cout请输入第i个字符:;cinc;e[i]=c;}Huffmantree(HT,w,n,e);m=2*n-1;outputHuffman(HT,m);CHuffmancode(HT,HC,n);}