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

. . 实验四 哈夫曼树与哈夫曼编码 一、实验内容 [问题描述] 　　已知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) {//在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].weig ht+HT [Select(HuffmanTree HT,int n,int *s1,int *s2)：在所给的权值中，选择出权值最小的两个值。 int i, 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==0i!=*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=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根结点求编码 if(HT[f].lchild==c) cd[--star]=0; //左分支标0 else cd[-