main.cpp

实现HaffmanEncoder算法的程序

#include <iostream.h>

struct node
{
	int weith;
	int left,right;
	int parent;
	char code[10];
};

const int max = 35000;

void main()
{
	int n;
	int c;
	int small1,small2;
	int p1,p2;
	p1 = 0;
	p2 = 0;
	cout<<"please input how many the code is: "<<endl;
	cin>>n;
	int m = 2*n-1;
	node *tree;
	tree = new node[m];
	for (int i=0; i<m; i++)
	{
		tree[i].weith = max;
		tree[i].left = max;
		tree[i].parent = 0;
		tree[i].right = 0;
	}
	for (i=0; i<n; i++)
	{
		cout<<"input the weith of a code."<<endl;
		cin>>c;
		tree[i].weith = c; 
	}
	for (i=n; i<m; i++)
	{	
		small1 = max;
		small2 = max;
		for (int j=0; j<i; j++ )
		{
			if((tree[j].parent == 0))
			{
				if(tree[j].weith < small1)
				{
					small2 = small1;
					small1 = tree[j].weith;
					p2 = p1;
					p1 = j;
				}
				else 
					if(tree[j].weith < small2)
					{
						small2 =tree[j].weith;
						p2 = j;
					}
			}
		}
		tree[p1].parent = i;
		tree[p2].parent = i;
		tree[i].left = p1;
		tree[i].right = p2;
		tree[i].weith = tree[p1].weith + tree[p2].weith; 
		tree[i].parent = 0;
	}

//haffman编码器

	int p;
	i=0;
	int temp;
	for (int j=0; j<n; j++)
	{
		p = tree[j].parent;
		c = j;
		while (p != 0)
		{
			if (tree[p].left == c)
				tree[j].code[i] = '0';
			else
				tree[j].code[i] = '1';
			i++;
			c = p;
			p = tree[p].parent;
		}
		tree[j].code[i] = '\0';
		p=i-1;
		i = i/2;
		for (int k=0; k<i; k++)
		{
			temp = tree[j].code[k];
			tree[j].code[k] = tree[j].code[p-k];
			tree[j].code[p-k] = temp;
		}
		i=0;
		cout<<"the haffman code of "<<tree[j].weith<<" is :"<<tree[j].code<<endl; 
	}
//解码器
	bool end = true;
	p = m-1;
	while (end)
	{
		while (tree[p].left != max)
		{
			cout<<"input the codes:"<<endl;
			cin>>c;
			if(c == 0)
				p = tree[p].left;
			else
				p = tree[p].right;
		}
		cout<<"the code is "<<tree[p].weith<<endl;
		p = m-1;

	}
}