哈夫曼编码-贪心算法

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