北京邮电大学数据结构实验二

利用二叉树结构实现哈夫曼编/解码器。

基本要求：

（1）初始化(Init)：能够对输入的任意长度的字符串 s 进行统计，统计每个字 符的频度，并建立哈夫曼树； 
（2）建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个 字符的编码输出；
（3）编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字 符串输出；
（4）译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码， 并输出译码结果;
（5）计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码 的压缩效果。

原创

这个不用STL太麻烦了，所以就果断使用了string，另外由于只是处理字符类型，所以没有使用模板类。

以下是头文件

#include
using namespace std;

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, string newcode);//为初始语句中的字符进行编码
public:
	void CreateHTree(int a[], char name[]);//建立哈夫曼树	
	void CreateTable();//编码表
	void Init(int n, char name[], int a[]);//初始化
	void Encoding(string d);//编码函数
	void Decoding(char* s);//解码函数
	~Huffman() { printf("已删除上一棵哈夫曼树n"); }
};

 以下是类函数的实现

#include "Huffman.h"
#include
using namespace std;

void Huffman::CreateHTree(int a[], char name[])
{
	HCodeTable = new HCode[N];
	HTree = new HNode[2 * N - 1];
	for (int i = 0; i < N; i++)
	{
		HTree[i].weight = a[i];
		HTree[i].parent = HTree[i].LChild = HTree[i].RChild = -1;
		HCodeTable[i].data = name[i];
	}//初始化树的节点和编码表元素
	int x, y;//以下为依次选出两个权重最小的子树形成新的树
	for (int i = N; i < 2 * N - 1; i++)
	{
		x = y = -1;
		int min1 = 10000, min2 = 10001;
		for (int t = 0; t < i; t++)
		{
			if (HTree[t].parent == -1){
				if (HTree[t].weight < min2){
					if (HTree[t].weight < min1){
						min2 = min1;
						min1 = HTree[t].weight;
						y = x;
						x = t;
					}
					else {
						min2 = HTree[t].weight;
						y = t;
					}
				}
			}
		}
        HTree[x].parent = HTree[y].parent = i;
		HTree[i].weight = HTree[x].weight + HTree[y].weight;
		HTree[i].LChild = x;
		HTree[i].RChild = y;
		HTree[i].parent = -1;
	}
}

void Huffman::code(int i, string newcode)
{
	if (HTree[i].LChild == -1) {
		HCodeTable[i].code = newcode;
		return;
	}
	code(HTree[i].LChild, newcode + "0");
	code(HTree[i].RChild, newcode + "1");
}

void Huffman::CreateTable()
{
	code(2 * N - 2, "");
	for (int i = 0; i < N; i++)
		cout << "字符：" << HCodeTable[i].data << "  " << "编码：" << HCodeTable[i].code << endl;
}

void Huffman::Init(int n, char name[], int a[])
{
	N = n;
	CreateHTree(a, name);
	CreateTable();
}

void Huffman::Encoding(string d)
{
	for(int i = 0; i < d.length() ;i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (d[i] == HCodeTable[j].data) {
				cout << HCodeTable[j].code;
				break;
			}
		}
	}
	cout << endl;
}

void Huffman::Decoding(char* s)
{
	while (*s != '')
	{
		int parent = 2 * N - 2;
		while (HTree[parent].LChild != -1)
		{
			if (*s == '0')
				parent = HTree[parent].LChild;
			if (*s == '1')
				parent = HTree[parent].RChild;
			s++;
		}
		cout << HCodeTable[parent].data;
	}
	cout << endl;
}

然后主函数的实现主要在于菜单的逻辑，要让每一步都能正确返回位置，而退出则可以直接用"return 0;"，还有一个难点在于怎么读取空格，这里我用的是getline，但注意getline()前要用getchar()防止getline将回车直接读取而结束。

以下是主函数

#include"Huffman.h"
#include
#include
using namespace std;

int main()
{
	char name[100];
	int a[100];
	cout << "哈夫曼树       菜单" << endl;
	while (1)
	{
		memset(name, -1, sizeof(name));
		memset(a, 0, sizeof(a));
		string words;
		int temp;
		cout << "请选择你要进行的操作：" << endl;
		cout << "1.进行哈夫曼编码，并打印编码表" << endl << "0.退出程序" << endl;
		cin >> temp;
		getchar();
		if (temp) {
			cout << "请输入语句：";
			getline(cin, words);
			int n = 0;
			for (int i = 0; i < words.length(); i++)
			{
				int j = 0;
				while (1)//统计出现的字符以及相应的频率
				{
					if (name[j] == -1) {
						name[j] = words[i];
						a[j]++;
						n++;
						break;
					}
					if (name[j] == words[i]) {
						a[j]++;
						break;
					}
					j++;
				}
			}
			Huffman HM;
			cout << "已完成编码" << endl;
			HM.Init(n, name, a);
			while (1)
			{
				cout << "请选择你要进行的操作：" << endl;
				cout << "1.进行编码" << endl << "2.进行解码" << endl << "0.返回" << endl;
				cin >> temp;
				if (temp == 1) {
					string ch;
					cout << "请输入待编码的语句：";
					getchar();
					getline(cin, ch);
					HM.Encoding(ch);
				}
				else if (temp == 2) {
					char ch[5000];
					cout << "请输入待解码的语句：";
					cin >> ch;
					HM.Decoding(ch);
				}
				else break;
			}
		}
		else return 0;
	}
	return 0;
}

最后让我们试试效果吧