huffmantree.cpp

Huffman编码和解码程序

#include "HuffmanTree.h"
#include <iostream>

using namespace std;

void HUFFMAN(HufmTree tree[])
{//构建Huffman树
	int i,j,p1,p2;
	float small1,small2;
	for(i=0;i<NODENUM;i++)
	{//编码树的初始化
		tree[i].data = '0';
		tree[i].lchild = 0;
		tree[i].parent = 0;
		tree[i].rchild = 0;
		tree[i].weight = 0;
	}
	cout << "共有" << LEAFNUM << "个待编码符号" << endl;
	for(i=0;i<LEAFNUM;i++)
	{//输入并存储节点信息
		cout << "请输入第" << i+1 << "个符号（字符型）：" << endl;
		cin >> tree[i].data;
		cout << "请输入第" << i+1 << "个符号的权重：" << endl;
		cin >>tree[i].weight;
	}
	for(i=LEAFNUM;i<NODENUM;i++)
	{//合并节点，生成码树
		p1 = p2 = 0;
		small1 = small2 = MAXWEIGHT;
		//查找最小的两个节点
		for(j=0;j<i;j++)
			if(tree[j].parent==0)
			{
				if(tree[j].weight<small1)
				{
					small2 = small1;
					small1 = tree[j].weight;
					p2 = p1;
					p1 = j;
				}
				else if (tree[j].weight<small2)
				{
					small2 = tree[j].weight;
					p2 = j;
				}
			}
			//合并节点
			tree[p1].parent = i;
			tree[p2].parent = i;
			tree[i].lchild = p1;
			tree[i].rchild = p2;
			tree[i].weight = tree[p1].weight + tree[p2].weight;
	}
	return;
}

void HUFFMANCODE(CodeType code[], HufmTree tree[])
{//Huffman编码
	int i,c,p;
	CodeType cd;
	for(i=0;i<LEAFNUM;i++)
	{//遍历码树，译码
		cd.start = LEAFNUM;
		c = i;
		p = tree[c].parent;
		cd.data = tree[c].data;
		while(p!=0)
		{
			cd.start--;
			if(tree[p].lchild == c)
				cd.bits[cd.start] = '0';
			else 
				cd.bits[cd.start] = '1';
			c = p;
			p = tree[c].parent;
		}
		code[i] = cd;
	}
	return;
}

void Print(CodeType code[])
{//显示编码结果
	int i,j;
	for(i=0;i<LEAFNUM;i++)
	{//顺序打印
		cout << code[i].data << ": ";
		for(j=code[i].start;j<LEAFNUM;j++)
			cout << code[i].bits[j];
		cout << endl;
	}
	return;
}