huffman qi.cpp

来自「本程序不能编译除大小写字母之外的编码 本程序需事先建立字母权值文后件才可运行」· C++ 代码 · 共 277 行

//预先在程序文件的目录下建立文件HFMT。DAT中放入如下文字（字母和权值）
//a64b13c22d32e103f21g15h47i57j1k5l32m20n57o63p15q1r48s51t80u23v8w18x1y16z1


//赫夫曼编码器
#include <stdio.h>
#include <stdlib.h>

#include <conio.h>
#define OK 	1
#define ERROR	0

typedef int Status;

typedef struct
{	char data;
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

Status Initialization(HuffmanTree *Tb,int n); 	//建立赫夫曼树
Status Encoding(HuffmanTree HT, int n);		//编码
Status Decoding(HuffmanTree HT, int n);		//解码
void Tree_Print(HuffmanTree HT,int n);		//打印赫夫曼树

void main()
{   HuffmanTree HT=NULL;
    FILE *fp_hfmt,*fp_tobetran,*fp_code,fp_textfile;
//文件hfmt中放各字母权值，tobetran放待译文， codefile中为赫夫曼码
    int n=1,d;
    char x,c;

    do{

	printf("       Main Menu\n");
	printf("------------------------------\n");
	printf("   Build Huffman Tree\n");	
	printf("   Read Huffman Tree\n");
	printf("   Encoding\n");
	printf("   Decoding\n");
	printf("   Scan & Encoding\n");
	printf("   Decoding & OutPut\n");
	printf("   Huffman Tree printing\n");
	printf("   Quit\n");
	printf("------------------------------");
	printf("\nYour Choice: ");

	x=getchar();
	switch(x)
	{  case 'q': case 'Q':
		break;
	   case 'b': case 'B':
		if((fp_hfmt=fopen("hfmt.dat","w"))==NULL)
		  { printf("file cannot be opened.\nPress any key to continue...");
		    getch();	exit(1);
		  }
		printf("enter data & weight: \nctrl+z to end \n?");
		scanf(" %c%d",&c,&d);

		while(!feof(stdin))
		 {
		   fprintf(fp_hfmt,"%c%d",c,d);
		   ++n;
		   printf("?");
		   scanf(" %c%d",&c,&d);
		 }
		 Initialization(&HT,n);
		 fclose(fp_hfmt);
		 break;
	   case 'r': case 'R':
		 if((fp_hfmt=fopen("hfmt.dat","r"))==NULL)
		  { printf("file cannot be opened.\nPress any key to continue...");
		    getch();	exit(1);
		  }
		 while(fscanf(fp_hfmt,"%c",&c)!=EOF)
		      if(!(c<='9'&c>='0'))  ++n;

		 Initialization(&HT,n);
		 fclose(fp_hfmt);
		 printf("read HuffmanTree finish !\nany key to continue...");
		 getch();
		 break;
	   case 'e': case 'E':
		 if(n == 0)
		   {  printf("no HuffmanTree found!\nany key to continue...");
		      getch();
		      break;
		   }
		 if(Encoding(HT, n))
		     printf("Encoding Finished!");
		 else   printf("Cannot Encoding!");
		 printf("\nPress any key to continue...");
		 getch();
		 break;
	   case 'd': case 'D':
		 if(n == 0)
		   {  printf("no HuffmanTree found!\nany key to continue...");
		      getch();
		      break;
		   }
		 if(Decoding(HT, n))
		    printf("Decoding Finished !");
		 else
		    printf("Cannot Decoding!");
		 printf("Press any key to continue...");
		 getch();
		 break;
	   case 's': case 'S':
		if((fp_tobetran=fopen("ToBeTran.dat","w"))==NULL)
			break;
		printf("enter( # for end) :");
		while((scanf("%c",&c),c)!='#')
		    fprintf(fp_tobetran,"%c",c);
		fclose(fp_tobetran);
		if(Encoding(HT, n))
		   {  printf("Encoding Finished!\nany key to continue...");
		      getch();
		      break;
		   }
	   case 'o': case 'O':
		 if(Decoding(HT, n))
		    {	fp_code=fopen("codefile.dat","r");
			while(!feof(fp_code)){
			  fscanf(fp_code, "%c",&c);
			  printf("%c",c);
			  }
			printf("\ndone.");
		    }
		  else{
		      printf("Cannot Decode.");
		  }
		  fclose(fp_code);
		  printf("\nany key to continue...");
		  getch();
		  break;
	   case 'h': case 'H':
		 if(n == 0)
		   {  printf("no HuffmanTree found!\nany key to continue...");
		      getch();
		      break;
		   }
		 Tree_Print(HT,2*n-1);
		 printf("\n HuffmanTree Printed!\nany key to continue...");
		 getch();
		 break;

	}//switch
    }while(x!='q');


}


Status Initialization(HuffmanTree *Tb,int n){
//Tb实际上是返回的赫夫曼数组的头指针
//n为赫夫曼树的叶子数
//从文件hfmT.dat建立赫夫曼树

	FILE *fp_hfmt;
	HuffmanTree HT,pt;
	int i=0,j,m,k,l,r,wei;
	char c;

	if((fp_hfmt=fopen("hfmt.dat","r"))==NULL)
		return ERROR;

	m=2*n-1;

	HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for(i=1; !feof(fp_hfmt); ++i){	  //输入叶子结点
		fscanf(fp_hfmt,"%c%d",&c,&wei);
		HT[i].data = c;
		HT[i].weight = wei;
		HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
	}
	for(; i<=m; i++){		//初始化父母兄弟
		HT[i].data = '*';
		HT[i].weight = 1000;
		HT[i].parent=HT[i].lchild=HT[i].rchild=0;
	}

	for(i=n+1; i<=m; i++){
		int m1,m2, l,r;
		m1=m2=1000;l=r=0;
		for(k=1; k<=m; k++)  //该循环实际是函数select 取最小的两个值
			if(HT[k].parent==0)
				if(HT[k].weight<m1)
				{  m2=m1;
				   r=l;
				   m1=HT[k].weight;
				   l=k;
				}
				else if(HT[k].weight<m2)
				{ m2=HT[k].weight;
				  r=k;
				}
		HT[l].parent = i;
		HT[r].parent = i;
		HT[i].weight = HT[l].weight + HT[r].weight;
		HT[i].lchild = l;
		HT[i].rchild = r;
	}//for

	fclose(fp_hfmt);
	*Tb=HT;		//返回huffmantree
	return OK;
}//Initialization


Status Encoding(HuffmanTree HT, int n){
//建立编码
	FILE *fp_tbt,*fp_code;
	char c0,*ch;
	int i,start,f,c;

	ch = (char *)malloc(n*sizeof(char));
	ch[n-1] = '\0';
	if((fp_tbt=fopen("tobetran.dat","r"))==NULL)   return ERROR;
	if((fp_code=fopen("codefile.dat","wb"))==NULL) return ERROR;

	while(fscanf(fp_tbt,"%c",&c0)!=EOF){
		start = n-1;
		for(c=1;  HT[c].data!=c0&&c<n+1; c++) ;//在树中寻找该字母

		if(c>n)  continue;		//没找到
		for(f = HT[c].parent; f!=0; c=f,f=HT[f].parent)
			if(HT[f].lchild==c)  ch[--start] = '0';
			else	ch[--start] = '1';
		for(i=start; i<n; i++)
			fprintf(fp_code,"%c",ch[i]);	//写入文件
	}
	fclose(fp_tbt);
	fclose(fp_code);
	return OK;
}//Encoding

Status Decoding(HuffmanTree HT, int n){
//解码，将解码后的数据放入文件textfile中       
	FILE *fp_code,*fp_txt;
	char c;
	int i;

	if((fp_code=fopen("codefile.dat","r"))==NULL) return ERROR;
	if((fp_txt= fopen("textfile.dat","w"))==NULL) return ERROR;

	i=2*n-1;//树根
	while(fscanf(fp_code,"%c",&c)!=EOF){
	 if(c=='1')  i=HT[i].rchild;
	 if(c=='0')  i=HT[i].lchild;
	 if(HT[i].lchild==0) //找到叶子
		{ fprintf(fp_txt,"%c",HT[i].data);//写入文件
		  i=2*n-1; //再从根开始
		}
	}
	fclose(fp_txt);
	fclose(fp_code);
	return OK;
}//Decoding

void Tree_Print(HuffmanTree HT,int n){
//递归算法打印赫夫曼树
	if(n){ 	printf("(%c,%d)",HT[n].data,HT[n].weight);
		if(HT[n].lchild||HT[n].rchild)
		{  printf("[");
		   Tree_Print(HT, HT[n].lchild);
		   if(HT[n].rchild) printf(",");
		   Tree_Print(HT,HT[n].rchild);
		   printf("]");
		}
	}
}//Tree_Print


//本程序不能编译除大小写字母之外的编码
//本程序需事先建立字母权值文后件才可运行
//本程序从文件中读入文字，编译后写入文件，所以屏幕上不会直接出现答案