淮海工学院计算机工程学院实验报告书
课程名：《算法分析与设计》
题目：实验3 贪心算法
哈夫曼编码
班级：软件102班
学号：11003215
姓名：鹿迅
实验3 贪心算法
实验目的和要求
（1）了解前缀编码的概念，理解数据压缩的基本方法；
（2）掌握最优子结构性质的证明方法；
（3）掌握贪心法的设计思想并能熟练运用
（4）证明哈夫曼树满足最优子结构性质；
（5）设计贪心算法求解哈夫曼编码方案；
（6）设计测试数据，写出程序文档。

实验内容
设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。

实验环境
Turbo C 或VC++
实验学时
2学时，必做实验
数据结构与算法
struct huffman
{
double weight; //用来存放各个结点的权值
int lchild,rchild,parent; //指向双亲、孩子结点的指针
}; 核心源代码
#include<iostream>
#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)
{
∑=j
i k k a
int min=11000;
int min1;
for(int k=0;k<i;k++)
{
if(huff[k].weight<min&&huff[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;i<2*n-1;i++)
{
huff[i].lchild=-1;
huff[i].parent=-1;
huff[i].rchild=-1;
}
for(int l=0;l<n;l++)
{
huff[l].weight=weight[l];
}
for(int k=n;k<2*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;i<n;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;
}
cout<<i+1<<"的霍夫曼编码为：";
for(int j=s.length();j>=0;j--)
{
cout<<s[j];
}
cout<<endl;
}
}
void main()
{
huffman huff[20];
int n,w[20];
cout<<"input the number of the elements:";
cin>>n;
cout<<"input the weight:";
for(int i=0;i<n;i++)
{
cin>>w[i];
}
HuffmanTree(huff,w,n);
huffmancode(huff,n);
}
实验结果
实验体会
哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树，n-1次合并后，成为最终的一棵哈夫曼树。

这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数最快（或最慢）为原则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。

每次选择两个权值最小的二叉树时，规定了较小的为左子树。