7_26.cpp

C++的电子教程

#include<stdio.h>
#include<stdlib.h>
#define N 100
#define Max 9999
typedef struct node
{	union 
	{	char data;
		int w;
	}val;
	struct node *left,*right;
}NODE;

//构造Huffman树
NODE *htree(char *dat,int *w,int n)    
{	NODE *T[N],*p;
	int n1,n2,min1,min2,i,j,v;
	for(i=0;i<n;i++)     //构造n棵只有根结点的二叉树的森林
	{	T[i]=(NODE *)malloc(sizeof(NODE));
		T[i]->val.w=w[i];
		T[i]->left=NULL;
		T[i]->right=NULL;
	}
	for(i=0;i<n-1;i++)   //重复（2）和（3）
	{	n1=n2=-1;
		min1=min2=Max;
		for(j=0;j<n;j++)  //选取两棵根结点权值最小的树
		{	if(T[j]!=NULL)
			{	v=T[j]->val.w;
				if(v<min1)
				{	min2=min1;	n2=n1;
					min1=v; 	n1=j;
				}
				else if(v<min2)/**/
				{	min2=v;	n2=j; }
			}
		}
		p=(NODE *)malloc(sizeof(NODE));
		p->val.w=T[n1]->val.w+T[n2]->val.w;
		p->left=T[n1];		p->right=T[n2];
		if(T[n1]->left==NULL)   //新树的左子树的根为叶结点
			T[n1]->val.data=dat[n1];
		else		T[n1]->val.data='*';	   //否则为分支结点
		if(T[n2]->left==NULL)  //新树的右子树的根为叶结点
			T[n2]->val.data=dat[n2];
		else		T[n2]->val.data='*';		//否则为分支结点
		T[n1]=p; T[n2]=NULL;  //在森林中，用新树取代原先的两棵树
	}
	p->val.data='*';    //最后树的根结点为分支结点
	return(p);
}
//按嵌套括号表示发输出树
void prn_btree(NODE *b)
{	if(b!=NULL)
	{	printf("%c",b->val.data);
		if(b->left!=NULL)
		{	printf("(");
			prn_btree(b->left);
			printf(",");
			prn_btree(b->right);
			printf(")");
		}
	}
}
//编码表的输出
void prn_code(NODE *b)
{	static char stack[N];
	static int top=0;
	int i;
	if(b->left)
	{	stack[top++]='0';
		prn_code(b->left);
		top--;
		stack[top++]='1';
		prn_code(b->right);
		top--;
	}
	else
	{	printf("\n%c= ",b->val.data);
		for(i=0;i<top;i++)
			printf("%c",stack[i]);
	}
}
//译码的实现
void encode(NODE* b,char s[])
{	NODE* p=b;
	int i=0;
	char c=s[i++];
	while(c!='\0')
	{	if(p->left) //分支结点
		{	if(c=='0')	p=p->left;
			else	p=p->right;
			if(!p->left) printf("%c",p->val.data); //叶结点，输出字符
			c=s[i++];
		}
		else p=b; //回到根结点
	}
}
//主函数
void main()	
{	NODE *h=NULL;
	char d[N]="ABCDE";/*ABACCA*/
	int w[]={4,7,5,2,9};
	char s[]="1100011100010101";
	h=htree(d,w,5);
	prn_btree(h);	printf("\n");
	printf("输出编码表:");
	prn_code(h);	printf("\n");
    printf("译码为：\n");
	encode(h,s);	printf("\n");
}