实验报告-哈夫曼

《实验报告-哈夫曼》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《算法分析与设计》课程设计报告题目：利用哈夫曼编码算法实现字串最优前缀码的生成工作专业：计算机科学与技术班级：姓名：指导教师：2016年5月25日一、问题分析。哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。哈夫曼树注意事项：①初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子②n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。③哈夫曼树是严格的二叉树，没有度数为1的分支结点。前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀

2、码。表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。带权值的结点都是叶子结点。权值越小的结点，其到根结点的路径越长。所谓前缀码是指，对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，比如常见的等长编码就是前缀码。所谓最优前缀码是指，平均码长或文件总长最小的前缀编码称为最优的前缀码（这里的平均码长相当于码长的期望值）。哈夫曼编码算法实现字串最优前缀码的生成，这是压缩的一种方式，在实际生活中应用广泛，一般采用贪心算法，二、问题的解决方案/算法选择/设计思路。(1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T

3、。(2)算法以

4、C

5、个叶结点开始，执行

6、C

7、－1次的“合并”运算后产生最终所要求的树T。(3)假设编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T。生成哈夫曼树（1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；（2）

8、在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。图1在队列中取最小的两个数，根的权值是这两个数的和，在将根的值带回队列中，在取最小的两个数，重复进行，得到哈夫曼树。记左子树为0，右子树为1，得到最优前缀数。三、算法设计/问题求解中所遇到的问题及分析解决方案。生成树/*功能用于生成哈夫曼树*/huffmanctrHuffmanTree(intn){i

9、ntm=2*n-1;//1~n存储叶子结点n+1~m存储树的n-1个内部结点huffmantree=(huffman)malloc(sizeof(huffmanNode)*(m+1));//用于存储哈夫曼树各结点priorityqueueh;//用于存储优先队列首地址inti;if(tree==NULL){printf("outofspace");exit(-1);}/*生成叶子结点*/for(i=1;i<=n;i++){printf("输入%d字母和权重:",i);scanf("%c%f",&tree[i].c,&tree[i].f);tree[i].i

10、=i;tree[i].parent=tree[i].lchild=tree[i].rchild=-1;tree[i].code=NULL;getchar();//吸收回车}/*初始化优先队列*/h=initializePrioQueue(n,tree);/*生成n-1个内部结点*/for(i=n+1;i<=m;i++){huffmanNodex,y,z;x=popPrioQueue(h);y=popPrioQueue(h);z.f=x.f+y.f;z.lchild=x.i;z.rchild=y.i;z.parent=-1;z.i=i;tree[x.i].pa

11、rent=i;tree[y.i].parent=i;tree[i]=z;pushPrioQueue(h,z);}/*前缀码生成*/for(i=1;i<=n;i++){char*c=(char*)malloc(sizeof(n));intstart=n-1;intj=i;if(c==NULL){printf("outofspace");exit(-1);}c[n-1]='';while(tree[j].parent!=-1){if(tree[tree[j].parent].lchild==j)c[--start]='0';elsec[--start]='1

12、';j=tree[j].parent;}/*给编码申