huffman_tree.h

哈弗曼编码

#include "iostream.h"
#include "define.h"

struct node 
{
	char c;
	int val;
	struct node *rc;
	struct node *lc;
};
typedef struct node NODE;

struct characters
{
	char chrctr;
	int freq;
};
typedef struct characters BUFF;

struct o
{
	int tag;
	NODE *p;
};
typedef struct o O;

BUFF buffer[95];			//权值与字符对应数组
bool found=false;			//查找标志
int y=-2;					//合并结点的字符
char stack[STACK_VOLUME];
int r=-1;

NODE *createhuffman(void);	//创建huffman树
void compile_each_character(NODE *,int);		//编译每一个字符
void del_the_tree(NODE *);			//遍历
int statistic(void);		//统计文件里有多少个字符
void countleaves(NODE *);	//计算叶子结点
void push(char);
void pop(void);

void push(char c)
{
	if (r==20)
	{
		cout<<"Overflow !"<<endl;
		return;
	}
	else
	{
		r++;
		stack[r]=c;
	}
}

void pop(void)
{
	if (r==-1)
	{
		cout<<"Underflow !"<<endl;
		return;
	}
	stack[r]=0;
	r--;
}

int statistic(void)			//统计文件里有多少个字符
{
	int n=0,i=0;
	while(buffer[i].freq!=0)
	{
		n++;
		i++;
	}
	return n;
}

NODE *createhuffman(void)
{
	int temp1,temp2;			//存放权值数组下标
	O mond[95];					//存放无父结点的结点地址
	int i,min,lmin,e=0,k=0,n,j,r=0;
	int order;					//存放最小与次小数据下标
	NODE *p,*q,*h;
	p=q=h=NULL;
	n=statistic();
	y=-2;
	for (i=0;i<95;i++)
	{
		mond[i].tag=0;
		mond[i].p=NULL;
	}
	while(true)
	{
again:
		min=MAX;
		lmin=MAX;
		for (i=0;i<n+e;i++)				//找出最小的两个数
		{
			if (buffer[i].freq<min)
			{
				min=buffer[i].freq;
				order=i;
			}
		}
		temp1=order;
		buffer[order].freq=MAX;
		for (i=0;i<n+e;i++)
		{
			if (buffer[i].freq<lmin)
			{
				lmin=buffer[i].freq;
				order=i;
			}
		}
		temp2=order;
		buffer[order].freq=MAX;
		if (lmin==MAX)
			break;
		i=0;p=NULL;										//用每个结点的字符域来区分权值相同的结点
		while(mond[i].p)										//为每一个权值分配一个字符，非叶子结点分派负值，保证每一个结点的字符域不同
		{
			if (mond[i].tag==0 && mond[i].p->c==buffer[temp1].chrctr)			//进入表示最小值结点在o数组中
			{
				j=0;
				while(mond[j].p)
				{
					if (mond[j].tag==0 && mond[j].p->c==buffer[temp2].chrctr)			////进入表示次小值结点在o数组中
					{
						p=new NODE;
						p->c=y;
						p->val=min+lmin;
						p->lc=mond[i].p;
						mond[i].tag=1;
						p->rc=mond[j].p;
						mond[j].tag=1;
						buffer[n+e].chrctr=y;
						buffer[n+e].freq=min+lmin;							
						e++;
						y--;
						r=0;
						while(mond[r].p)
							r++;
						mond[r].p=p;
						mond[r].tag=0;
						goto again;
					}
					j++;
				}
				if (p==NULL)				//内层循环退出时，p=NULL，则次小值结点不在o数组中
				{
					p=new NODE;
					q=new NODE;
					p->c=buffer[temp2].chrctr;
					p->val=lmin;
					p->lc=p->rc=NULL;
					q->c=y;
					q->val=min+lmin;
					q->rc=p;
					q->lc=mond[i].p;
					mond[i].tag=1;
					buffer[n+e].chrctr=y;
					buffer[n+e].freq=min+lmin;
					e++;
					y--;
					r=0;
					while(mond[r].p)
						r++;
					mond[r].p=q;
					mond[r].tag=0;
				}
			}
			else 
				if (mond[i].tag==0 && mond[i].p->c==buffer[temp2].chrctr)			//进入表示次小值结点在o数组中
				{
					j=0;
					while(mond[j].p)
					{
						if (mond[j].tag==0 && mond[j].p->c==buffer[temp1].chrctr)			////进入表示最小值结点在o数组中
						{
							p=new NODE;
							p->c=y;
							p->val=min+lmin;
							p->lc=mond[i].p;
							mond[i].tag=1;
							p->rc=mond[j].p;
							mond[j].tag=1;
							buffer[n+e].chrctr=y;
							buffer[n+e].freq=min+lmin;
							e++;
							y--;
							r=0;
							while(mond[r].p)
								r++;
							mond[r].p=p;
							mond[r].tag=0;
							goto again;
						}
						j++;
					}
					if (p==NULL)				//内层循环退出时，p=NULL，则最小值结点不在o数组中
					{
						p=new NODE;
						q=new NODE;
						p->c=buffer[temp1].chrctr;
						p->val=min;
						p->lc=p->rc=NULL;
						q->c=y;
						q->val=min+lmin;
						q->rc=p;
						q->lc=mond[i].p;
						buffer[n+e].chrctr=y;
						buffer[n+e].freq=min+lmin;
						e++;
						y--;
						r=0;
						while(mond[r].p)
							r++;
						mond[r].p=q;
						mond[r].tag=0;
					}
				}
				i++;
			}
			if (p==NULL)					//外层循环退出时，p=NULL，则最小值结点和次小值结点都不在o数组中
			{
				h=new NODE;
				p=new NODE;
				q=new NODE;
				p->lc=p->rc=NULL;
				p->c=buffer[temp1].chrctr;
				p->val=min;
				q->c=buffer[temp2].chrctr;
				q->val=lmin;
				q->lc=q->rc=NULL;
				h->lc=p;
				h->rc=q;
				h->val=min+lmin;
				h->c=y;
				buffer[n+e].chrctr=y;
				buffer[n+e].freq=min+lmin;
				e++;
				y--;
				r=0;
				while(mond[r].p)
					r++;
				mond[r].p=h;
				mond[r].tag=0;
			}
	}
	r=0;
	while(mond[r].p)
		r++;
	r--;
	return mond[r].p;
}


void del_the_tree(NODE *p)
{
	if (p!=NULL)
	{
		del_the_tree(p->lc);
		del_the_tree(p->rc);
		if (p->lc==p->rc)
			delete p;
	}
}

void compile_each_character(NODE *p,char c)
{
	if (!p)
		return;
	else if (p->c==c)
	{
		found=true;
		return;
	}
	push('0');
	compile_each_character(p->lc,c);
	if (found==true)
		return;
	else
	{
		pop();
		push('1');
		compile_each_character(p->rc,c);
	}
	if (found==false)
		pop();
	return;
}

void countleaves(NODE *p)
{
	if (p!=NULL)
	{
		if (p->lc==NULL && p->rc==NULL)
		{
			printf("Leaf:%c  ",p->c);
			return ;
		}
		countleaves(p->lc);
		countleaves(p->rc);
	}
}