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

实验四 哈夫曼树与哈夫曼编码一、实验内容问题描述已知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,int n,char *e)*hc, int n)CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n)outputHuffman(HuffmanTree HT, int m)select(HuffmanTree *ht,int n, int *s1, int *s2)模块： 在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下：首先建立一个哈夫曼树和哈夫曼编码的存储表示：typedef struct int weight; int parent,lchild,rchild;char elem;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedef char *HuffmanCode;/动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree *ht , int *w, int n)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。 构造哈夫曼树：开始叶子初始化非叶子初始化调用select函数选择权值最小的两个这两个权值最小的两个字符非别作为同一个结点的左右孩子，其父母的权值为两个字符的权值之和结束 for(i=n+1;i=m;+i)/在HT1i选择parent为0且weight最小的两个 Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weig ht+HTSelect(HuffmanTree &HT,int n,int *s1,int *s2)：在所给的权值中，选择出权值最小的两个值。int i, min; for(i=1;i=n;i+) 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相似，只有在判断是否为最小的时候就，要加上一个条件：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; /从右向左逐位存放编码，首先存放编码结束符for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根结点求编码if(HTf.lchild=c)cd-star=0; /左分支标0else cd-star=1;/右分支标1HCi=new charn-star; /为第i个编码分配空间strcpy(HCi,&cdstar);/从cd复制编码串到HC否是是开始从叶子到根结点求编码 c=i f=HTi.parentf!=0 c=将0输入到cd数组HTf.lchild=c中将1输入到cd数组HTf.lchild=c从cd复制编码串到HCc=f,f=HTf.parent否输出字符权值相应的编码结束outputHuffman(HuffmanTree HT, int m)：显示出哈夫曼树的编码和字符以及权重，与二叉树的遍历相似：if(m!=0) coutHTm.elem HTm.weightendl; outputHuffman(HT,HTm.lchild); outputHuffman(HT,HTm.rchild);三 、测试数据测试一：字符为：A B C 权重：10 12 8 测试数据二：字符为：ABCDEFG权重为：7 8 8 12 15 9 6四、结果调试调试一： 调试二： 五总结 在进行这个程序的编写的时候，其实有点毫无头绪，只是知道在书上的算法就可以编写成功。但是在一次又一次的过程，还是一次又一次的错误，最后在进行理解才稍微理解了哈夫曼树的编码过程，但是选择权值最小的过程还是不太理解，进行了调试才明白也一些，但是还是没有明白透彻。在这次的实验过程中，我明白了调试的重要性，不要在自己遇到问题的时候就去问同学，因为那样会养成自己的依赖性，在自己不会的时候，不会进行深层次的了解就去问，那样对自己没有太大的提高，只有自己理解和同学的讲解相结合，才能有所提高。六、附录：#include#include typedef struct int weight; int parent,lchild,rchild;char elem;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedef char *HuffmanCode;/动态分配数组存储赫夫曼编码表/求赫夫曼编码void Select(HuffmanTree &HT,int n,int *s1,int *s2) int i, min; for(i=1;i=n;i+) 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; 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;/void Huffmantree(HuffmanTree &HT,int*w,int n,char *e) /w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCint m,i,s1,s2;if(n=1) return;m=2*n-1;/总的结点HT=new HTNodem+1;for(i=1;i=n;+i)/*1-n号放叶子结点，初始化*/HTi.weight=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.parent=0;HTi.elem=0;for(i=n+1;i=m;+i)/在HT1i选择parent为0且weight最小的两个 Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/void CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n) char *cd; int c,f,star;HC=new char*n+1;cd=new charn;cdn-1=0;/编码结束符for(int i=1;i=n;+i)star=n-1; /从右向左逐位存放编码，首先存放编码结束符for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根结点求编码if(HTf.lchild=c)cd-star=0; /左分支标0else cd-star=1;/右分支标1HCi=new charn-star; /为第i个编码分配空间strcpy(HCi,&cdstar);/从cd复制编码串到HCdelete cd;/释放工作空间 for(i=1;i=n;i+) coutHTi.elem HTi.weight:HCiendl;/void outputHuffman(HuffmanTree HT, int m)if(m!=0) coutHTm.elem HTm.weightendl; outputHuffman(HT,HTm.lchild); outputHuffman(HT,HTm.rchild);void main() HuffmanTree HT; H