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

《实验四--哈夫曼树与哈夫曼编码.pdf》由会员分享，可在线阅读，更多相关《实验四--哈夫曼树与哈夫曼编码.pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用 0 标记，右孩子用 1 标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。流程图：算法：开始 输入哈弗曼树的带权结点数目 n 输入相应的权值和对应的字符 建 立 哈 夫 曼 树Huffmantree(HT,w,n,显 示 哈 夫 曼 树outputHuffman(HT,哈夫曼树的编码 CHuffmancode(HT,HC,n)结束 主函数 Huffmantree(HuffmanTree&HT,int*w,int n,char CHuffmancode(HuffmanTree&HT,HuffmanCode&HC,

3、int outputHuffman(HuffmanTree HT,int m)select(HuffmanTree*ht,int n,int*s1,int 模块：在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下：首先建立一个哈夫曼树和哈夫曼编码的存储表示：typedef struct int weight;int parent,lchild,rchild;char elem;HTNode,*HuffmanTree;arent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weig ht+HTSelect(

4、HuffmanTree&HT,int n,int*s1,int*s2)：在所给的权值中，选择出权值最小的两个值。int i,min;for(i=1;i=n;i+)开始 叶子初始化 非叶子初始化 调用 select 函数选择权值最小的两个 这两个权值最小的两个字符非别作为同一个结点的左右孩子，其父母的权值为两个字符的权值之和 结束 if(HTi.parent=0)min=i;i=n+1;for(i=1;i=n;i+)if(HTi.parent=0)if(HTi.weightHTmin.weight)min=i;*s1=min;在选择 s2 的时候和 s1 相似，只有在判断是否为最小的时候就，要加

5、上一个条件：if(HTi.parent=0&i!=*s1)，就可以了，否则，选出来的最小权值和 s1 就相等了，失去了选择的意义了。CHuffmancode(HuffmanTree&HT,HuffmanCode&HC,int n)：从叶子到根逆向求编码：左孩子为 0，右孩子为 1，这样一直循环下去，而最重要的是：for(int i=1;i=n;+i)star=n-1;arent;f!=0;c=f,f=HTf.parent)child=c)cd-star=0;lem HTm.weightendl;outputHuffman(HT,HTm.lchild);outputHuffman(HT,HTm.

6、rchild);三、测试数据 测试一：字符为：A B C 权重：10 12 8 测试数据二：字符为：ABCDEFG 权重为：7 8 8 12 15 9 6 四、结果调试 调试一：否 是 是 开始 从叶子到根结点求编码 c=i f!=0 将 0 输入到 cd 数将 1 输入到 cd 数HTf.lchild=从 cd 复制编码串到 HC c=f,f=HTf.par否 输出字符权值相应的编码 结束 调试二：五总结 在进行这个程序的编写的时候，其实有点毫无头绪，只是知道在书上的算法就可以编写成功。但是在一次又一次的过程，还是一次又一次的错误，最后在进行理解才稍微理解了哈夫曼树的编码过程，但是选择权值最

7、小的过程还是不太理解，进行了调试才明白也一些，但是还是没有明白透彻。在这次的实验过程中，我明白了调试的重要性，不要在自己遇到问题的时候就去问同学，因为那样会养成自己的依赖性，在自己不会的时候，不会进行深 层次的了解就去问，那样对自己没有太大的提高，只有自己理解和同学的讲解相结合，才能有所提高。六、附录：#include#include typedef struct int weight;int parent,lchild,rchild;char elem;HTNode,*HuffmanTree;arent=0)min=i;i=n+1;for(i=1;i=n;i+)if(HTi.parent=0

8、)if(HTi.weightHTmin.weight)min=i;*s1=min;for(i=1;i=n;i+)if(HTi.parent=0&i!=*s1)min=i;i=n+1;for(i=1;i=n;i+)if(HTi.parent=0&i!=*s1)if(HTi.weightHTmin.weight)min=i;*s2=min;eight=wi;HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.elem=ei;for(i=n+1;i=m;+i)/*非叶子结点初始化*/HTi.weight=0;HTi.lchild=0;HTi.rchild=0;HTi

9、.parent=0;HTi.elem=0;for(i=n+1;i=m;+i)arent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;arent;f!=0;c=f,f=HTf.parent)child=c)cd-star=0;lem HTi.weight:HCiendl;lem HTm.weightendl;outputHuffman(HT,HTm.lchild);outputHuffman(HT,HTm.rchild);void main()HuffmanTree HT;HuffmanCode HC;int*w;char*e;char c;int i,n,m,wei;coutn;w=new intn+1;e=new charn+1;for(i=1;i=n;i+)cout请输入第iwei;wi=wei;cout请输入第ic;ei=c;Huffmantree(HT,w,n,e);m=2*n-1;outputHuffman(HT,m);CHuffmancode(HT,HC,n);