哈夫曼树.cpp

本学期所有数据结构的大作业一

#include "stdio.h"
#include "string.h"
#define LEN 50   /*输入字符最大值*/
#define MAX 100  /*选parent 为0时 S1和S2的初值*/
#define BLEN 100 /*解码时输入字符的最大值*/
struct HTNode{
	int letter;    /*字符序号*/
	int weight;    /*权重*/
	int parent;    /*双亲*/
	int lchild;    /*左孩子*/
	int rchild;    /*右孩子*/
	char code[LEN-1]; /*赫夫曼编码,仅用于叶子结点*/
	};
main(){
	struct HTNode HT[LEN];/* HT为编码区*/
	static int m, n,s1,s2,f1,f2;/*f1,f2用于选parent 为0且weight最小的两个结点,s1,s2为最小两结点序号,n为字符个数,m为总点个数,*/
	int i,j,p,num;	/*mun为字符个数,i,j为循环数,p用于解码序号*/
	int c,f;
	char cd[LEN-1],HC[LEN-1],Buff[BLEN];/*cd为暂存空间,HC为编码存储空间,Buff为输入解码的空间*/
	printf("----Huffmancode code----\n");/*赫夫曼编码建立*/
	printf("Please input the coding piece:",n);/*字符个数*/
	scanf("%d",&n);
	num=n;
	m=2*n-1;
	for(i=1;i<=n;i++){
	printf("please input the %d code weight: ",i);/*输入各字符权重*/
		scanf("%d",&HT[i].weight);
		HT[i].letter=i;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}/*for*/	
	for(i=n+1;i<=m;++i,n++){
		f1=f2=MAX;s2=s1=0;
	 for(j=1;j<=n;j++){
	 	if(HT[j].parent==0)/*选parent 为0且weight最小的两个结点,把序号附给s1,s2*/
	 	if(HT[j].weight<f2)
	 	if(HT[j].weight<f1){
	 		f2=f1;f1=HT[j].weight;
	 		s2=s1;s1=j;}
	 	else{
	 		f2=HT[j].weight;
	 		s2=j;}
	 		}	
	HT[s1].parent=i;HT[s2].parent=i;/*建赫夫曼树*/
	HT[i].lchild=s1;HT[i].rchild=s2;
	HT[i].weight=HT[s1].weight+HT[s2].weight;		
	 }/*for*/
	printf(" num weight parent lchild rchild\n");/*输出赫夫曼树初态*/
	for(i=1;i<=m;i++){
		printf("%3d %6d %5d %6d %6d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
		if(i%10==0){getchar();}
	}/*for*/
	getchar();getchar();
	for(i=1;i<=num;i++){
		strcpy(HC,"\0");
		printf("the %d Huffmancode: ",i);
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
		if(HT[f].lchild==c){
			 strcpy(cd,"0");
			 strcpy(HC,strcat(cd,HC));
			 }/*if*/
		else{
			 strcpy(cd,"1");
			 strcpy(HC,strcat(cd,HC)); 
		}/*else*/
		strcpy(HT[i].code,HC);
		printf("%s",HT[i].code);
		printf("\n");
		if(i%10==0){getchar();}
	}/*for*/  
	getchar();
	printf("----Huffmancode Decoding----\n");/*赫夫曼编码解码*/
	printf("please input Huffmancode:");/*输入要解码的01编码*/
	scanf("%s",Buff);
	i=0;p=2*num-1;
   printf("Huffmancode Decoding:");
	while(Buff[i]!='\0'){
		if(Buff[i]=='0') p=HT[p].lchild;
		else p=HT[p].rchild;
		if(HT[p].lchild==0&&HT[p].rchild==0){
			printf("%d",HT[p].letter);
			p=2*num-1;
		}
		i++;
		}
}/*main*/