huaffmantree.cpp

简单的哈夫曼树的编码实现。 将出现不同频率的字母

#include<iostream.h> 
#include<iomanip.h> 
#define NUM 4 //字母数 
#define TNUM 7 // 
#define LTH 4 //编码最大长度 

class Node 
{ 
	public: 
		char data; 
		int weight; 
		int parent; 
		int lchild; 
		int rchild; 
}; 

void main() 
{ 
	char ch[NUM]={'A','B','C','D'};//26个字母 

	int weit[NUM]={12,3,5,9};//出现频率 

	Node nodes[TNUM]; //用对象数组存储哈夫曼树 

	int i,j,one,two,a,b; 
	int hc[NUM][LTH]; //用于存储编码 
	int m,n; 

//初始化数组 
	for(i=0;i<NUM;i++) 
	{ 
		nodes[i].data=ch[i]; 
		nodes[i].weight=weit[i]; 
		nodes[i].parent=-1; 
		nodes[i].lchild=-1; 
		nodes[i].rchild=-1; 
	} 
	for(i=NUM;i<TNUM;i++) 
	{ 
		nodes[i].data='@'; 
		nodes[i].weight=-1; 
		nodes[i].parent=-1; 
		nodes[i].lchild=-1; 
		nodes[i].rchild=-1; 
	} 

//建立哈夫曼树 
	for(i=NUM;i<TNUM;i++) 
	{ 
		a=b=-1; 
		one=two=10000; //最大权数 
	for(j=0;j<i;j++) 
	{ 
		if(nodes[j].parent==-1) 
		{ 
			if(nodes[j].weight<=two) 
			{ 
				one=two; 
				two=nodes[j].weight; 
				a=b; 
				b=j; 
			} 
			else if(nodes[j].weight>two&&nodes[j].weight<=one) 
			{ 
				one=nodes[j].weight; 
				a=j; 
			} 
		} 
	}//for语句得到 parent=-1(即尚没有父结点)且weight最小的两个结点 
	nodes[a].parent=i; 
	nodes[b].parent=i; 
	nodes[i].lchild=a; 
	nodes[i].rchild=b; 
	nodes[i].weight=nodes[a].weight+nodes[b].weight; 
	} 

//初始化hc 
	for(i=0;i<LTH;i++) 
	{ 
		for(j=0;j<NUM;j++) 
		{ 
			hc[j][i]=7; 
		} 
	} 

//编码 
	for(i=0;i<NUM;i++) 
	{ 
		j=LTH-1; 
		for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent) 
		{ 
			if(nodes[n].lchild==m) 
			{ hc[i][j]=0; } 
			else 
			{ hc[i][j]=1; } 
			j--; 
		} 
	} 

//输出 nodes 
	cout<<"HuffmanTree:"<<endl; 
	cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6) 
	<<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl; 
	for(i=0;i<TNUM;i++) 
	{ 
		cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6) 
		<<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl; 
	} 

//输出编码 
	cout<<endl<<"Result:"<<endl; 
	cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n"; 
	for(i=0;i<NUM;i++) 
	{ 
		cout<<setw(6)<<ch[i]<<setw(8)<<weit[i]; 
		cout<<"      "; 
		for(j=0;j<LTH;j++) 
		{ 
			if(hc[i][j]!=7) 
			{ cout<<hc[i][j]; } 
		} 
		cout<<endl; 
	} 
	cout<<"\nDone.\n"<<endl; 
}