哈夫曼编码-贪心算法.docx

淮海工学院计算机工程学院 实验报告书 课程名： 《算法分析与设计》 题 目 实验3 贪心算法 哈夫曼编码 班 级： 软件102班 学 号： 姓 名： 鹿迅 评语: 成绩： 指导教师： 批阅时间: 实验 3 贪心算法 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 j ??wn}，应设需要编码的字符集为{di, d2, --dn }，它们出现的频率为 ak ??wn}，应 ki 用哈夫曼树构造最短的不等长编码方案。 实验环境 Turbo C 或 VC++ 实验学时 2 学时，必做实验 数据结构与算法 struct huffman { double weight; // 用来存放各个结点的权值 int lchild,rchild,parent; // 指向双亲、孩子结点的指针 }; 核心源代码 #includeiostream #include string using namespace std; struct huffman { double 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(huff[k].weightminhuff[k].parent==-1) { min=huff[k].weight; min1=k; } } huff[min1].parent=1; return min1; } void HuffmanTree(huffman huff[],int weight[],int n) { for(int i=0;i2*n-1;i++) { huff[i].lchild=-1; huff[i].parent=-1; huff[i].rchild=-1; } for(int l=0;ln;l++) { huff[l].weight=weight[l]; } for(int k=n;k2*n-1;k++) { int i1=Select(huff,k); int i2=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; } } void huffmancode(huffman huff[],int n) { string s; int j; for(int i=0;in;i++) { s=; j=i; while(huff[j].parent!=-1) { if(huff[huff[j].parent].lchild==j) s=s+0; else s=s+1; j=huff[j].parent; } couti+1 的霍夫曼编码为： for(int j=s.length();j=0;j--) { couts[j]; } coutendl; } void mai n() { huffman huff[20]; int n,w[20]; couti nput the nu mber of the eleme nts:; cin?n; couti nput the weight:; for(i nt i=0;i n; i++) { cin w[i]; } Huffma nTree(huff,w, n); huffma ncode(huff, n); } 实验结果 ■ *H:\著法设计\DEbug\huffrnmrrtrg“. - = ~ I勺勺勺 t i马马马马3yhehe I勺勺勺 t i马马马马3y hehe曼曼〕SB箕ny 七t夫夫夫夫夫a S10 011 UU ie 11 cont inue 实验体会 哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树， n-1次合并后, 成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策 略，以满足约束方程为条件，以使目标函数最快（或最慢）为原则，在候选集合中进行一系列的选 择，以便尽快构成问题的可行解。 每次选择两个权值最小的二叉树时，规定了较小的为左子树。