构造哈夫曼树及哈夫曼编码.doc

《数据结构》实验报告

实验名称： 构造哈夫曼树及哈夫曼编码
专 业： 计算机科学与技术专业
班 级： 计算机科学与技术
姓 名：
学 号：
完成日期： 2012/11/22

2012年 11月22 日

一、 问题描述
构造一个哈夫曼树，并根据所构造的哈夫曼树求其哈夫曼树的编码；

二、 需求分析
哈夫曼树有叫做最优二叉树，它是指对于一组带有确定的权值的叶节点，构造具有最小的带权路径程度的二叉树。
在数据通信中，经常需要将传送的文字转换成由二进制字符0,1组成的二进制串，称之为编码。如果在所有的编码中每个字符的编码都一样的长短则有的字符在应用中出现的次数多有的字符在应用中出现的次数少，这样的话有的电文的编码会很长，所以就想用不同长度的编码区代表字符，及在电文中出现的概率大的用短的字符表示，而出现的概率小的用长的字符表示，则得到的电文可能就比较短。
基于以上的需求与要求，就出现了哈夫曼编码。

三、 概要设计
1、 先建立哈夫曼树的结构，即哈夫曼树的构造算法；
2、 再建立哈夫曼树编码的结构，即哈夫曼树编码的算法；
3、 再带入数据进行验证。

四、 详细设计
1.、哈夫曼树构造算法的编码：
#include<iostream>
using namespace std;

#define MAXVALUE 100
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 10

typedef struct
{
int weifht; //权值
int parent; //双亲节点
int lchild; //左孩子
int rchild; // 右孩子
}HNodeType;

typedef struct
{
int bit[MAXBIT];
int start;
}HCodeType;

void HuffmanTree(HNodeType HuffNode[],int n)
{
int i,j,m1,m2,x1,x2;

for(i = 0;i < 2*n-1;i++) //对数组进行初始化
{
HuffNode[i].weifht = 0;
HuffNode[i].parent = -1;
HuffNode[i].lchild = -1;
HuffNode[i].rchild = -1;
}
for(i = 0;i < n;i++) //输入各个节点的权值
{
cout<<"输入第"<<i<<"个叶节点的权值："<<endl;
cin>>HuffNode[i].weifht;
}
for(i = 0;i < n-1;i++) //构造哈夫曼树
{
m1 = MAXVALUE;
m2 = MAXVALUE;
x1 = x2 = 0;
for(j = 0;j < n + i;j++) //找出两棵权值最小的树
{
if(HuffNode[j].weifht < m1&&HuffNode[j].parent == -1)
{
m2 = m1;
x2 = x1;
m1 = HuffNode[j].weifht;
x1 = j;
}
else if(HuffNode[j].weifht < m2&&HuffNode[j].parent == -1)
{
m2 = HuffNode[j].weifht;
x2 = j;
}
}
HuffNode[x1].parent = n + i; //合并两个子树
HuffNode[x2].parent = n + i;
HuffNode[n+i].weifht = HuffNode[x1].weifht + HuffNode[x2].weifht;
HuffNode[n+i].lchild = x1;
HuffNode[n+i].rchild = x2;

}
}

void HaffmanCode() //哈夫曼编码
{
HNodeType HuffNode[MAXNODE];
HCodeType HuffCode[MAXLEAF],cd;
int i,j,c,p,n;
cout<<"输入节点的个数："<<endl; //输入节点的个数
cin>>n;
HuffmanTree(HuffNode,n);
for(i = 0;i < n;i++)
{
cd.start = n - 1;
c = i;
p = HuffNode[c].parent;
while(p != -1)
{
if(HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--;
c = p;
p = HuffNode[c].parent;
}
for(j = cd.start+1;j < n;j++)
HuffCode[i].bit[j] = cd.bit[j];
HuffCode[i].start = cd.start;
}
cout<<"哈夫曼编码为："<<endl;
for(i = 0;i < n;i++)
{
for(j = HuffCode[i].start + 1;j < n;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
}
int main(void)
{
HaffmanCode();
return 0;
}
五、 测试分析
结果：
输入节点的个数：
5
输入第0个叶节点的权值：
1
输入第1个叶节点的权值：
2
输入第2个叶节点的权值：
3
输入第3个叶节点的权值：
4
输入第4个叶节点的权值：
5
哈夫曼编码为：
010
011
00
10
11
Press any key to continue
六、 总结
在本次编写程序的时候开始把哈夫曼树的判断的时候叶节点将（p！= -1）写成了（p!= 1）结果导致不能读出哈夫曼树的编码。