《哈夫曼编码贪心算法.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码贪心算法.docx（5页珍藏版）》请在三一办公上搜索。
1、哈夫曼编码贪心算法淮海工学院计算机工程学院 实验报告书 课程名： 算法分析与设计 题 目： 实验3 贪心算法 哈夫曼编码 班 级： 软件102班 学 号： 11003215 姓 名： 鹿 迅 评语： 成绩： 指导教师： 批阅时间： 年 月 日 算法分析与设计实验报告 - 1 - 实验3 贪心算法 实验目的和要求 了解前缀编码的概念，理解数据压缩的基本方法； 掌握最优子结构性质的证明方法； 掌握贪心法的设计思想并能熟练运用 证明哈夫曼树满足最优子结构性质； 设计贪心算法求解哈夫曼编码方案； 设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为d1, d2, , dn，它们出现的频率为 a
2、 kw1, w2, , wn，应用哈夫曼树构造最短的不等长编码方案。 实验环境 Turbo C 或VC+ 实验学时 2学时，必做实验 数据结构与算法 struct huffman double weight; /用来存放各个结点的权值 int lchild,rchild,parent; /指向双亲、孩子结点的指针 ; k=ij核心源代码 #include #include using namespace std; struct huffman ; static int i1=0,i2=0; int Select(huffman huff,int i) double weight; int lc
3、hild,rchild,parent; 算法分析与设计实验报告 - 2 - int min=11000; int min1; for(int k=0;ki;k+) huffmin1.parent=1; return min1; if(huffk.weightmin&huffk.parent=-1) min=huffk.weight; min1=k; void HuffmanTree(huffman huff,int weight,int n) for(int i=0;i2*n-1;i+) for(int l=0;ln;l+) for(int k=n;k2*n-1;k+) int i1=Sele
4、ct(huff,k); int i2=Select(huff,k); huffi1.parent=k; huffi2.parent=k; huffk.weight= huffi1.weight+huffi2.weight; huffl.weight=weightl; huffi.lchild=-1; huffi.parent=-1; huffi.rchild=-1; 算法分析与设计实验报告 - 3 - huffk.lchild=i1; huffk.rchild=i2; void huffmancode(huffman huff,int n) string s; void main int j;
5、 for(int i=0;in;i+) s=; j=i; while(huffj.parent!=-1) couti+1=0;j-) coutsj; coutendl; 算法分析与设计实验报告 - 4 - huffman huff20; int n,w20; coutn; coutinput the weight:; for(int i=0;iwi; HuffmanTree(huff,w,n); huffmancode(huff,n); 实验结果 实验体会 哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树，n-1次合并后，成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数最快为原则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。 每次选择两个权值最小的二叉树时，规定了较小的为左子树。
