哈夫曼编码贪心算法

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

2、短的不等长编码方案。 实验环境 Turbo C 或VC+实验学时 2学时，必做实验数据结构与算法struct huffmandouble weight; /用来存放各个结点的权值int lchild,rchild,parent; /指向双亲、孩子结点的指针;核心源代码#include<iostream>#include <string>using namespace std;struct huffmandouble weight;int lchild,rchild,parent;static int i1=0,i2=0;int Select(huffman huff,i

3、nt i)int min=11000;int min1;for(int k=0;k<i;k+)if(huffk.weight<min&&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;i<2*n-1;i+)huffi.lchild=-1;huffi.parent=-1;huffi.rchild=-1;for(int l=0;l<n;l+)huff

4、l.weight=weightl;for(int k=n;k<2*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;i<n;i+)s=""j=i;while(huffj.pare

5、nt!=-1)if(huffhuffj.parent.lchild=j)s=s+"0"else s=s+"1"j=huffj.parent;cout<<i+1<<"的霍夫曼编码为：" for(int j=s.length();j>=0;j-) cout<<sj; cout<<endl;void main() huffman huff20;int n,w20;cout<<"input the number of the elements:"cin>>n;cout<<"input the weight:"for(int i=0;i<n;i+) cin>>wi; HuffmanTree(huff,w,n); huffmancode(huff,n);实验结果实验体会哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树，n-1次合并后，成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局