完整word版哈夫曼编码 贪心算法

1、算机工程学院实验报告算法分析与设计目:实验3贪心算法哈夫曼编码级:t=r.号:软件102班11003215名:评语：成绩：指导教师：批阅时间：年月日算法分析与设计实验报告-1 -实验3贪心算法实验目的和要求(1)了解前缀编码的概念，理解数据压缩的基本方法;(3)掌握最优子结构性质的证明方法； 掌握贪心法的设计思想并能熟练运用证明哈夫曼树满足最优子结构性质;(5)(6)设计贪心算法求解哈夫曼编码方案; 设计测试数据，写出程序文档。实验内容设需要编码的字符集为d1, d2,dn,它们出现的频率为 哈夫曼树构造最短的不等长编码方案。jZ akw1, w2,wn,应用k 土实验环境Turbo C 或

2、VC+实验学时2学时，必做实验数据结构与算法struct huffma ndouble weight; II用来存放各个结点的权值int lchild,rchild, parent; II指向双亲、孩子结点的指针;核心源代码#in clude#in clude using n ames pace std;struct huffma ndouble weight;int lchild,rchild, parent;static int i1=0,i2=0;int Select(huffman huff,i nt i)算法分析与设计实验报告-5 -int min=11000;int mi n1;f

3、or(i nt k=0;ki;k+)if(huffk.weightmi n&huffk. paren t=-1)min=huffk.weight;min 1=k;huff min 1. paren t=1;return mi n1;void Huffma nTree(huffma n huff,i nt weight,i nt n)for(i nt i=0;i2* n-1;i+)huffi.lchild=-1;huffi. paren t=-1;huffi.rchild=-1;for(i nt l=0;l n;l+)huffl.weight=weightl;for(i nt k=n; k2*

4、n-1;k+)int i1=Select(huff,k);int i2=Select(huff,k);huffi1. paren t=k;huffi2. pare nt=k;huffk.weight= huffi1.weight+huffi2.weight;huffk.lchild=i1;huffk.rchild=i2;void huffma ncode(huffma n huff,i nt n)stri ng s;int j;for(i nt i=0;i n;i+)s=;j=i;while(huffj. pare nt!=-1)if(huffhuffj. paren t.lchild=j)s

5、=s+0;else s=s+1;j=huffj. parent;couti+1=0;j-)coutsj;coute ndl;void main()huffman huf20;int n,w20;coutn;couti nput the weight:;for(i nt i=0;i wi;Huffma nTree(huff,w, n);huffma ncode(huff, n);实验结果 HiSH De b U ghu ffma ntre.input the number of the elenents:B01B 011 0010input the ueigrbt ：1 2 3 4 5夫号壇码为；HI1jcontinue5的夫S编码为:Pfces any key to实验体会n-1次合并后,哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树, 成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策 略