北邮数据结构：哈夫曼树

用类与对象C++编程

分为头文件Huffman.h

和主函数main.cpp两部分

（功能陆续添加）

类的声明：
 

class	Huffman
{
private:
	HNode*HTree;//哈夫曼树节点 
	HCode*HCodeTable;//存储编码表 
	int	N;//叶子节点数量 
	void	code(int	i, string	newcode);//递归函数，对第i个节点编码
public:
	Huffman() {
		HTree = new	HNode;	HCodeTable = new	HCode;	N = 0;
	};
	void	CreateHTree(int	a[], int	n, char	name[]);//构建哈夫曼树
	void	CreateCodeTable();//创建编码表
	void	Encode(string	s, char	*d);//编码 
	void	Decode(char	*s, char	*d);//解码
	~Huffman();//析构函数 
	void	SelectMin(int	&x, int	&y, int	a, int	b);//辅助搜索最小值函数 
	void	Printeach(int	retime);//打印每一个字母对应的编码 
};//类的定义

两种结点的定义：

树中结点和编码中的结点：

struct	HNode
{
	int	weight;//结点权值
	int	parent;//双亲数组下标
	int	LChild;//左孩子数组下标	
	int	RChild;//右孩子数组下标 
};//每个结点的结构体 

struct	HCode
{
	char	data;//存储节点的内存 
	string	code;//存储结点对应的编码 
};//记录每个节点的编码 

具体代码如下：

Huffman.h

#include
#include
using	namespace	std;
#define	manum	0x3f3f3f3f
struct	HNode
{
	int	weight;//结点权值
	int	parent;//双亲数组下标
	int	LChild;//左孩子数组下标	
	int	RChild;//右孩子数组下标 
};//每个结点的结构体 

struct	HCode
{
	char	data;//存储节点的内存 
	string	code;//存储结点对应的编码 
};//记录每个节点的编码 

class	Huffman
{
private:
	HNode*HTree;//哈夫曼树节点 
	HCode*HCodeTable;//存储编码表 
	int	N;//叶子节点数量 
	void	code(int	i, string	newcode);//递归函数，对第i个节点编码
public:
	Huffman() {
		HTree = new	HNode;	HCodeTable = new	HCode;	N = 0;
	};
	void	CreateHTree(int	a[], int	n, char	name[]);//构建哈夫曼树
	void	CreateCodeTable();//创建编码表
	void	Encode(string	s, char	*d,int &contro);//编码 
	void	Decode(char	*s, char	*d);//解码
	~Huffman();//析构函数 
	void	SelectMin(int	&x, int	&y, int	a, int	b);//辅助搜索最小值函数 
	void	Printeach(int	retime);//打印每一个字母对应的编码 
};//类的定义



//辅助函数，搜索数列中最小的两个结点值

void	Huffman::SelectMin(int	&x, int	&y, int	a, int	b)
{
	//cout << a << " " << b << endl;
	//cout << HTree[b - 1].weight << endl;
	int	m = manum, n = manum;//最小的两个数 
	for (int i = a; i < b; i++)
	{
		if (HTree[i].weight < m)
		{
			m = HTree[i].weight;
			x = i;
		}
	}
	for (int i = a; i < b; i++)
	{
		if (HTree[i].weight < n&&HTree[i].weight != HTree[x].weight)
		{
			n = HTree[i].weight;
			y = i;
		}
	}
}


//构造哈夫曼树 
//a[]存储每种字符的权值，n为字符的种类,name为各个字符的内容 
void	Huffman::CreateHTree(int	a[], int	n, char	name[])
{
	N = n;
	HCodeTable = new	HCode[N];
	HTree = new	HNode[2 * N - 1];//2*n-1为总结点个数
	for (int i = 0; i < N; i++)
	{
		HTree[i].weight = a[i];
		HTree[i].LChild = HTree[i].RChild = HTree[i].parent = -1;
		HCodeTable[i].data = name[i];
	}
	int	x, y;
	for (int i = n; i < 2 * N - 1; i++)//开始构建哈夫曼树
	{
		SelectMin(x, y, 0, i);//从1~i中选出两个权值最小的结点
		//cout << "x=" << x <<" "< 
main.cpp
 
#include
#include
#include
#include"Huffman.h"
using	namespace	std;
#define Size	1000
string	str;
char	name[60];//字符类型（0-25为大写，30-55为小写,26为下划线） 
int		Time[60];//字符的权值 
char	name2[60];
int		Time2[60];
int	main()
{
	cout << "请输入你想传递的字符串(空格用下划线代替),如想结束程序，请输入(END)" << endl;
	while (cin >> str)
	{
		if (str == "END")
			break;
		memset(Time, 0, sizeof(Time));
		memset(Time2, 0, sizeof(Time2));
		int	len = str.size();
		for (int i = 0; i < len; i++)
		{
			if (str[i] == '_')
			{
				Time[26]++;
				name[26] = '_';
			}
			if (str[i] >= 'A'&&str[i] <= 'Z')
			{
				Time[str[i] - 'A']++;
				name[str[i] - 'A'] = str[i];
			}
			if (str[i] >= 'a'&&str[i] <= 'z')
			{

				Time[str[i] - 'a' + 30]++;
				name[str[i] - 'a' + 30] = str[i];

			}
		}//录入并处理字符串 
		int	retime = 0;//实际上出现的字符个数 
		for (int i = 0; i < 60; i++)
		{
			if (Time[i] != 0)
			{
				name2[retime] = name[i];
				Time2[retime] = Time[i];
				retime++;
			}
		}
		//cout << "retime=" << retime << endl;
		name2[retime] = '';
		//精细化两个数组
		//运用类完成功能 
		Huffman	Huf;
		cout << retime << endl;
		Huf.CreateHTree(Time2, retime, name2);
		Huf.CreateCodeTable();			//树和表的建立 
		Huf.Printeach(retime);//打印每一个字符对应的哈夫曼编码 
		char	*ar = new	char[Size];//编码后的字符串
		char	*br = new	char[Size];//解码后的字符串
		int	contro=0;
		Huf.Encode(str, ar,contro);
		cout << "编码结果如下:" << endl;
		for (int i = 0; i < contro; i++)
			cout << *(ar + i);
		cout << endl;
		//cout << ar << endl;
		cout << "解码结果如下:" << endl;
		Huf.Decode(ar, br);
		for (int i = 0; i < len; i++)
			cout << *(br + i) ;
		cout << endl;

		Huf.~Huffman();
		cout << "请输入你想传递的字符串(空格用下划线代替),如想结束程序，请输入(END)" << endl;
	}
}//5.16更新，修改vs上出现字符错乱的bug