// haffman.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include<iostream>
using namespace std; typedef struct hfnode
{
char ch; //存储字符
int weight; //存储权值
int parent; //双亲结点位置
int lchild; //左右孩子结点位置
int rchild;
} hfnode,*hfmtree; typedef struct node
{
char code[];
} node,*hfcode; #define Nsymbols 10 hfnode *Inithfm(hfnode *tree,int n) //千万不能用关键字命名。把这些节点作为带权值的二叉树的根节点，左右子树为空
{
//tree = new hfnode[n]; //多余了，已经在main函数中声明了。
for(int i = ;i < n; i++)
{
tree[i].ch = '';
tree[i].weight = ;
tree[i].lchild = ;
tree[i].rchild = ;
tree[i].parent = ;
}
cout << "请输入想要编码的字符序列,按照先字符后次数的顺序输入" << endl;
for(int i = ;i < ; i++)
{
cin >> tree[i].ch >>tree[i].weight;
}
cout <<endl; for(int i = ;i < ;i++)
cout << tree[i].ch << " "<<tree[i].weight<<" ";
cout << endl;
return tree;
} void select(hfnode *tree,int n,int *p1,int *p2) //选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
{
//找一个作为参考,返回的是结点
int x,y;
for(int i = ;i <= n;i++)
{
if(tree[i].parent==)
{
x = i;
break;//找到一个参考点即可
}
} for(int i = ;i <= n;i++) //找出最小的结点
{
if((tree[i].parent==)&&(tree[i].weight!=))
{
if(tree[i].weight < tree[x].weight)
x = i;
}
} for(int j = ;j <= n;j++)
{
if((tree[j].parent==)&&(j!=x))
{
y = j;
break;//找到一个参考点即可
}
}
for(int j = ;j <= n;j++) //找出次小的结点
{
if((tree[j].parent==)&&(tree[j].weight!=)&&j!=x)
{
if(tree[j].weight < tree[y].weight)
y = j;
}
}
*p1 = x;
*p2 = y;
}
//对哈弗曼树进行编码。 void HfCode(hfnode *tree,int n,node *hfmcode,int m)
{
int c,f;
int start = ; for(int i=;i<;i++)
{
for(c=i,f=tree[c].parent;f!=;c=f,f=tree[c].parent) //追溯法，从叶子节点出发，一路往上追溯。
{
if(tree[f].lchild==c)
hfmcode[i].code[start++] = '';
else
hfmcode[i].code[start++] = '';
}
start = ;
}
} void Print(node *hfmcode,int m)
{
for(int i = ;i < m;i++)
{
for(int j = ;j < m;j++)
cout <<hfmcode[i].code[j];
cout << endl;
}
cout << endl;
} int main()
{
int p1=,p2=; //为了接收最小和次小的两个节点
hfnode tree[Nsymbols]; //当我们不是用指针，这种情况下，已经全部赋值了。不用再一次赋值了。
Inithfm(tree,Nsymbols); //初始化结构体数组。 //建立哈弗曼树 for(int m = ;m < *-;m++) //二叉树性质
{
select(tree,m-,&p1,&p2);
tree[p1].parent = m;
tree[p2].parent = m;
tree[m].lchild = p1;
tree[m].rchild = p2;
tree[m].weight = tree[p1].weight + tree[p2].weight;
tree[m].parent =; //其实这句也可以不用，因为初始化时已经初始化为0了。
} node hfmcode[];
// 初始化，不然打印的时候会出现未知错。
for(int i = ;i < ;i++)
{
for(int j = ;j < ;j++)
hfmcode[i].code[j]='\0';
} HfCode(tree,Nsymbols,hfmcode,); //编码函数
Print(hfmcode,); //打印函数
return ;
}
实验名称：哈弗曼编码
实验目的：了解前缀编码的概念，理解数据压缩的基本方法；
掌握Huffman编码的设计思想并能熟练应用。
实验要求：对有字符集｛A，B，C，D｝，各字符在电文中出现的次数集为｛1,3,4,7｝；
要求编程实现Huffman树的构造，并在此基础上编程实现Huffman编码。
实验步骤及内容：
1、首先建立一个定义哈弗曼树的结构体Node，及结构体指针LinkList，该结构体包含一个存储字符的ch,存储权值的weight，存储双亲结点的parent，存储左右孩子的lchild与rchild。代码如下：
typedef struct hfnode
{
char ch; //存储字符
int weight; //存储权值
int parent; //双亲结点位置
int lchild; //左右孩子结点位置
int rchild;
} hfnode,*hfmtree;
2、定义一个存储编码的结构体，主要是为了方便打印，代码如下：
typedef struct node
{
char code[10];
} node,*hfcode;
3、初始化函数，因为默认值是一个不确定的值，必须进行初始化才行。
hfnode *Inithfm(hfnode *tree,int n) //千万不能用关键字命名。把这些节点作为带权值的二叉树的根节点，左右子树为空
{
//tree = new hfnode[n]; //多余了，已经在main函数中声明了。
for(int i = 0;i < n; i++)
{
tree[i].ch = '0';
tree[i].weight = 0;
tree[i].lchild = 0;
tree[i].rchild = 0;
tree[i].parent = 0;
}
cout << "请输入想要编码的字符序列,按照先字符后次数的顺序输入" << endl;
for(int i = 0;i < 4; i++)
{
cin >> tree[i].ch >>tree[i].weight;
}
cout <<endl;
for(int i = 0;i < 4;i++)
cout << tree[i].ch << " "<<tree[i].weight<<" ";
cout << endl;
return tree;
}
4、选择两棵根结点权值最小的树作为左右子树。
void select(hfnode *tree,int n,int *p1,int *p2) //选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
{
//找一个作为参考,返回的是结点
int x,y;
for(int i = 0;i <= n;i++)
{
if(tree[i].parent==0)
{
x = i;
break;//找到一个参考点即可
}
}
for(int i = 0;i <= n;i++) //找出最小的结点
{
if((tree[i].parent==0)&&(tree[i].weight!=0))
{
if(tree[i].weight < tree[x].weight)
x = i;
}
}
for(int j = 0;j <= n;j++)
{
if((tree[j].parent==0)&&(j!=x))
{
y = j;
break;//找到一个参考点即可
}
}
for(int j = 0;j <= n;j++) //找出次小的结点
{
if((tree[j].parent==0)&&(tree[j].weight!=0)&&j!=x)
{
if(tree[j].weight < tree[y].weight)
y = j;
}
}
*p1 = x;
*p2 = y;
}
5、构造哈弗曼树
//建立哈弗曼树
for(int m = 4;m < 2*4-1;m++) //二叉树性质
{
select(tree,m-1,&p1,&p2);
tree[p1].parent = m;
tree[p2].parent = m;
tree[m].lchild = p1;
tree[m].rchild = p2;
tree[m].weight = tree[p1].weight + tree[p2].weight;
tree[m].parent =0; //其实这句也可以不用，因为初始化时已经初始化为了。
}
6、对哈弗曼树进行编码。编码函数如下：
//对哈弗曼树进行编码。
void HfCode(hfnode *tree,int n,node *hfmcode,int m)
{
int c,f;
int start = 0;
for(int i=0;i<10;i++)
{
for(c=i,f=tree[c].parent;f!=0;c=f,f=tree[c].parent) //追溯法，从叶子节点出发，一路往上追溯。
{
if(tree[f].lchild==c)
hfmcode[i].code[start++] = '0';
else
hfmcode[i].code[start++] = '1';
}
start = 0;
}
}
7、打印编码
void Print(node *hfmcode,int m)
{
for(int i = 0;i < m;i++)
{
for(int j = 0;j < m;j++)
cout <<hfmcode[i].code[j];
cout << endl;
}
cout << endl;
}
另配上一副自己用画图工具画的理论分析图：
结果与C++代码结果一致。
总结：
此次实验，让我理解了结构体数组的使用以及初始化，内存管理等方面的熟悉，感觉收获挺大的。