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

《实验四 哈夫曼树与哈夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验四哈夫曼树与哈夫曼编码一、实验内容[问题描述]　　已知n个字符在原文中出现的频率，求它们的哈夫曼编码。[基本要求]　　1.初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。（具体算法可参见教材P147的算法6.12）　　2.编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。二、概要设计算法设计：要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两

2、个权值最小的作为新的两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用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)CHuffm

3、ancode(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**Huffm

4、anCode;//动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree*ht,int*w,intn)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。构造哈夫曼树：开始叶子初始化非叶子初始化调用select函数选择权值最小的两个这两个权值最小的两个字符非别作为同一个结点的左右孩子，其父母的权值为两个字符的权值之和结束for(i=n+1;i<=m;++i){//在HT[1……i]选择parent为0且weight最小的两个Select(HT,i-1,&s1,&s2);HT[s1].pare

5、nt=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].weight

6、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

7、].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}否是是开始从叶子到根结点求编码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否输出字符权值相

8、应的编码结束output