哈夫曼编码贪心算法.doc

《哈夫曼编码贪心算法.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、淮海工学院计算机工程学院实验报告书课程名：《算法分析与设计》题目：实验3贪心算法哈夫曼编码班级：软件102班学号：11003215姓名：鹿迅评语：成绩：指导教师：批阅时间：年月日实验3贪心算法实验目的和要求（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用（4）证明哈夫曼树满足最优子结构性质；（5）设计贪心算法求解哈夫曼编码方案；（6）设计测试数据，写出程序文档。实验内容设需要编码的字符集为{d1,d2,…,dn}，它们出现的频率为{w1,w2,…,wn}，应用哈夫曼树构造最短的不等长编码方案。实验环境Turbo

2、C或VC++实验学时2学时，必做实验数据结构与算法structhuffman{doubleweight;//用来存放各个结点的权值intlchild,rchild,parent;//指向双亲、孩子结点的指针};核心源代码#include#includeusingnamespacestd;structhuffman{doubleweight;intlchild,rchild,parent;};staticinti1=0,i2=0;intSelect(huffmanhuff[],inti){intmin=11000;intmin1;for(intk=0;

3、k

4、k<2*n-1;k++){inti1=Select(huff,k);inti2=Select(huff,k);huff[i1].parent=k;huff[i2].parent=k;huff[k].weight=huff[i1].weight+huff[i2].weight;huff[k].lchild=i1;huff[k].rchild=i2;}}voidhuffmancode(huffmanhuff[],intn){strings;intj;for(inti=0;i

5、parent].lchild==j)s=s+"0";elses=s+"1";j=huff[j].parent;}cout<=0;j--){cout<>n;cout<<"inputtheweight:";for(inti=0;i>w[i];}HuffmanTree(huff,w,n);huff

6、mancode(huff,n);}实验结果实验体会哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树，n-1次合并后，成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数最快（或最慢）为原则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。每次选择两个权值最小的二叉树时，规定了较小的为左子树。