huffman.cpp

本程序中定义了霍夫曼类实现霍夫曼编码和解码

//
// 霍夫曼(huffman)编码/解码实现
//
#include<iostream.h>
#include "binarytree.h"
#include "minheap.h"

#define MAX 100

// 定义输入的符号信息
class Symbol {
	friend class Huffman;
private:
	char data;    // 数据
	float weight; // 符号出现的概率
	int start;    // 符号在编码数组中的起始下标
	int len;      // 符号的编码长度
};
// 定义霍夫曼类，实现编码和解码
class Huffman {
public:
	Huffman() {n = 10; s = new Symbol[n+1];}
	~Huffman() {delete [] s;}
	void Input();// 输入函数
	BinaryTree<int,float> HuffmanTree();  // 构造霍夫曼树
	void recursecoding(BinaryTreeNode<int,float>*, char*, int, int&); // 对霍夫曼树递归编码
	void Encoding();// 编码函数
	void Output();// 输出函数
	void Decoding();// 译码函数
private:
	BinaryTree<int,float> htree; // 构造的霍夫曼树
    Symbol *s;    // 输入的信源符号
	char code[MAX]; // 存储符号编码的字符数组
	int n;       // 信源长度
};
// 输入函数
void Huffman::Input()
{
	cout<<"****************Huffman编码/解码*********************"<<endl;cout<<endl;
	cout<<"请输入信源符号的个数：";
    cin>>n;
	while(n > MAX) {
		cout<<"个数太多，请重新输入..."<<endl;
		cout<<"请输入信源符号的个数：";
		cin>>n;
	}
	delete []s;
	s = new Symbol[n+1];
	cout<<"请输入信源符号及其概率："<<endl;
	for(int i=1; i<=n; i++) {
		cout<<"输入第"<<i<<"个信源符号：";
		cin>>s[i].data;
		cout<<"           概率为：";
		cin>>s[i].weight;
		cout<<endl;
	}
}
// 构造霍夫曼树
BinaryTree<int,float> Huffman::HuffmanTree()
{// 创建一个单节点树的数组
	BinaryTree<int,float> *z = new BinaryTree<int,float>[n+1], zero;
	for(int i = 1; i <= n; i++)
		z[i].MakeTree(i, s[i].weight, zero, zero);
     
	// 把数组变成一个最小堆
	MinHeap< BinaryTree<int,float> > H(1);
	H.Initialize(z, n, n);
	// 将堆中的树不断合并
	BinaryTree<int,float> x, y, t;
	for(i = 1; i < n; i++) {
		H.DeleteMin(x);
		H.DeleteMin(y);
		t.MakeTree(0, x.root->weight+y.root->weight, x, y);
		H.Insert(t);
	}
	H.DeleteMin(t); // 最后的树
	H.Deactivate() ;
	delete [] z;
	return t;
}
// 对霍夫曼树递归编码
void Huffman::recursecoding(BinaryTreeNode<int,float> *t, char *cd, int level, int &start)
{   // 对以t为根节点的树进行编码，编码信息临时存储在数组cd中
	// level是编码在树中进行的层次也即是码长，start用于记录符号编码在编码数组code中的起始位置
	BinaryTreeNode<int,float> *l, *r;
	// 对左子树编码
	l = t->LeftChild;
	if(l == NULL) return;
	cd[level] = '0'; // 存储字符编码的临时数组
	if(l->LeftChild == NULL && l->RightChild == NULL) { // 为叶节点时，获取编码信息
		// 存储字符编码的位置信息
		s[l->data].start = start;
		s[l->data].len = level;
		for(int i=1; i<=level; i++) //将临时数组中的编码复制到编码数组code
			code[start++] = cd[i];
	}
	recursecoding(l, cd, level+1, start); // 递归对左子树的子树编码
	// 递归对右子树编码
	r = t->RightChild;
	cd[level] = '1';
	if(r->LeftChild == NULL && r->RightChild == NULL) { // 为叶节点时，获取编码信息
		// 存储字符编码的位置信息
		s[r->data].start = start;
		s[r->data].len = level;
		for(int i=1; i<=level; i++) //将临时数组中的编码复制到编码数组code
			code[start++] = cd[i];
	}
	recursecoding(r, cd, level+1, start); // 递归对右子树的子树编码
}


// 编码函数
void Huffman::Encoding()
{
	char *cd = new char[MAX/2+1];
	int level=1, start = 0;
	htree = HuffmanTree(); // 构造霍夫曼树
	if(htree.root == NULL || htree.root->LeftChild == NULL || htree.root->LeftChild == NULL) {
		cout<<"未能构造霍夫曼树，无法进行编码！"<<endl;
		return;
	}
	//调用递归编码函数
	// 编码从霍夫曼树的第一层孩子节点开始，从编码数组code的开始位置存储编码
	recursecoding(htree.root, cd, level, start);
	delete []cd;
}

// 输出函数
void Huffman::Output()
{
	cout<<"Huffman编码的结果："<<endl;
	cout<<"序号   信源符号   编码"<<endl;
	for(int i=1; i<=n; i++) {
		cout<<" "<<i<<"        "<<s[i].data<<"       ";
		for(int b=s[i].start; b<s[i].start+s[i].len; b++)
			cout<<code[b];
		cout<<endl;
	}
	cout<<endl;
}
// 译码函数
void Huffman::Decoding()
{
	char *cd = new char[MAX];
	int len, k;
	BinaryTreeNode<int,float> *t;
	bool leaf;
	cout<<"请输入一串编码（以2结束，最长为100）：";
	for(int i = 0; ; i++) {
		cin>>cd[i];
		if(cd[i] == '2') break;
	}
	len = i; //编码串长度
	i = 0;
	cout<<"解码的结果是：";
	while(1) {
		t = htree.root; // 通过霍夫曼树解码，从树根开始遍历
		leaf = false;  
		k = i;
		while(i < len) { // 循环读入编码串
			if(cd[i++] == '0')
				t = t->LeftChild;
			else 
				t = t->RightChild;
			if(t->LeftChild == NULL && t->RightChild == NULL) { //为叶节点时，输出解码的符号
				cout<<s[t->data].data;
				leaf = true;  // 标记叶节点
				break;
			}
		}
		if(i == len) break; // 读完编码串则结束
	}
	cout<<endl;
	if(leaf == true) // 从树根遍历到叶节点，则解码完成
		cout<<"解码成功!"<<endl;
	else {           // 从树根未能遍历到叶节点，则编码串不能再进行解码
		cout<<"无法完全解码输入的编码串，剩余编码串为：";
		for(i=k; i<len; i++)
			cout<<cd[i];
		cout<<endl;
	}
	delete []cd;
}
// 主程序
void main()
{
	Huffman hf;
	hf.Input();
	hf.Encoding();
	hf.Output();
    hf.Decoding();
}