哈夫曼编码译码.c

给定电文进行哈夫曼编码

#include <stdio.h> 
#define MAXBIT 10 /*定义哈夫曼编码的最大长度*/ 
#define MAXVALUE 10000 /*定义最大权值*/ 
#define MAXLEAF 10 /*定义哈夫曼树中最多叶子节点个数*/ 
#define MAXNODE MAXLEAF*2-1 /*哈夫曼树最多结点数*/ 
#define OK  1;
#define ERROR 0;

typedef struct 
{ /*哈夫曼编码信息的结构*/ 
	int bit[MAXBIT]; 
	int start;
}Hcodetype; 
typedef struct 
{ /*哈夫曼树结点的结构*/
	    char c1;  /*c1表示叶子结点里的字符*/
		int weight; 
		int parent; 
		int lchild; 
		int rchild; 
}Hnodetype; 
	void huffmantree(Hnodetype huffnode[MAXNODE],int n) /*构造哈夫曼树的函数*/ 
	{ 
		int i,j,m1,m2,x1,x2; 
		for(i=0;i<2*n-1;i++) /*存放哈夫曼树结点的数组huffnode[]初始化*/ 
		{ 
			char r[10]={'a','b','c','d','e','f','g','h','i','j'}; 
			huffnode[i].c1=r[i];  /*分别将10个叶子结点赋上字符信息*/ 		
			huffnode[i].weight=0;  /*将哈夫曼树各叶子结点权值赋为0*/
			huffnode[i].parent=-1; /*起初各结点为独立的结点*/
			huffnode[i].lchild=-1; 
			huffnode[i].rchild=-1; 
		} 
		for(i=0;i<n;i++) /*输入n个叶子结点的权值*/ 
		{
			char r[10]={'a','b','c','d','e','f','g','h','i','j'};
			printf("please input character %c's weight\n",r[i]); /*输入提示信息*/
			scanf("%d",&huffnode[i].weight); /*输入n个叶子结点的权值*/ 
		}
		for(i=0;i<n-1;i++) /*开始循环构造哈夫曼树*/ 
		{ 
			m1=m2=MAXVALUE; /*将最大的权值赋给m1,m2*/
			x1=x2=0; 
			for(j=0;j<n+i;j++) /*在叶子结点中寻找权值最小的两个结点*/
			{ 
				if((huffnode[j].weight<m1)&&(huffnode[j].parent==-1)) 
				{ 
					m2=m1;
					m1=huffnode[j].weight;
					x2=x1;
					x1=j; 
				} 
				else if(huffnode[j].weight<m2&&huffnode[j].parent==-1) 
				{ 
					m2=huffnode[j].weight;
					x2=j; 
				} 
			} 
			huffnode[x1].parent=n+i; /*地址为x1,x2的双亲结点的地址为n+i*/
			huffnode[x2].parent=n+i; 
			huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight; /*所得新结点的权值是两个权值最小的结点权值之和*/
			huffnode[n+i].lchild=x1; /*所得新结点的左右孩子的地址分别为x1,x2*/
			huffnode[n+i].rchild=x2; 
		} 
	} 
	int Visit(Hnodetype *HT)  /*进行译码时，判断是否走到叶子结点*/
	{
	   	if ((HT->c1>=97)&&(HT->c1<=106)) /*字符'a'的ASCII值为97，字符'j'的ASCII值为106*/
		{
			printf("%c",HT->c1); /*若是叶子结点，则输出此字符*/
			return OK;
		}
		else
			return ERROR;
	}
	int Decoding(Hnodetype *HT,int(*Visit)(Hnodetype *HT)) /*进行译码操作的函数*/
		{
			int i=0,I=0;
			char m[100]={'\0'};
			Hnodetype *p1;
			p1=HT;
			printf("输入电文\n");
			getchar(); 
			gets(m);   /*输入电文信息*/
			printf("译码后为\n");
			I=MAXNODE-1;i=0;	
			while(m[i]!='\0')  /*从根结点开始遍历*/
			{
				while(p1[I].lchild!=-1&&p1[I].rchild!=-1&&m[i]!='\0')  /*若此结点为叶子结点，则进行以下操作*/
				{
						if(m[i++]=='0')
							I=p1[I].lchild;
						else
							I=p1[I].rchild;
				}
				Visit(&p1[I]);
				I=MAXNODE-1;
			}
			printf("\n");
			return OK;
			
	}
	void main() 
	{ 
		Hnodetype huffnode[MAXNODE]; 
		Hcodetype huffcode[MAXLEAF],cd; 
		int i,j,c,p,n; 
		printf("please input the number of the leaves:\n"); /*输入提示信息*/
		scanf("%d",&n); /*输入叶子节点个数*/
		huffmantree(huffnode,n); /*建立哈夫曼树*/ 
		for(i=0;i<n;i++) /*该循环求每个叶子结点对应字符的哈夫曼编码*/ 
		{ 
			cd.start=n-1;c=i; 
			p=huffnode[c].parent; 
			while(p!=-1) 
			{ 
				if(huffnode[p].lchild==c) cd.bit[cd.start]=0; 
				else cd.bit[cd.start]=1; 
				cd.start--;c=p; 
				p=huffnode[c].parent; 
			} 
			for(j=cd.start+1;j<n;j++) /*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/ 
				huffcode[i].bit[j]=cd.bit[j]; 
			huffcode[i].start=cd.start; 
		} 
		for(i=0;i<n;i++) /*输出每个叶子结点的哈夫曼编码*/ 
		{ 
			char r[10]={'a','b','c','d','e','f','g','h','i','j'};
			printf("%c character is:",r[i]); 
			for(j=huffcode[i].start+1;j<n;j++) 
				printf("%d",huffcode[i].bit[j]); /*输出所得的哈夫曼编码*/
			printf("\n"); 
		} 

		Decoding(huffnode,Visit);  /*调用译码函数*/
	}