huffmancode.cpp

/*哈夫曼编/译码器 完成Huffman 编码的译码过程。 即输入一个码串

  /*哈夫曼编/译码器
完成Huffman 编码的译码过程。
即输入一个码串，请翻译成相应的字符串。
要求有编码过程和解码过程。*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define WordNUM 28//字符集中字符个数
#define MessageNUM 100000//最大信息量

typedef struct {
	int N;
	int SumWeight;
	char word[WordNUM+1];
	int weight[WordNUM+1]; 
}Word,*Wordset;//字符集及其权重.0号单元未用

typedef int Boolean;
typedef char* Message;//动态分配字符串数组存储信息

typedef struct {
	int n;//n序号
    char data;
	int weight;//权重值
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树;

typedef struct{
    char data;
	char* Code;//动态分配字符串数组存储哈夫曼编码表
}HCode,*HuffmanCode;//动态分配字符串数组存储哈夫曼编码表

void printstar(){
	printf("************************************************************\n");
}//printstar

Boolean UserSaysYes(){//与用户对话函数
	int c,t;
	printf("(y,n)?");
	do{
		while((c=getchar())=='\n');//Ignore new line character.
        if(c=='y'||c=='Y'||c=='n'||c=='N')
		{	
			while((t=getchar())!='\n');//读去'\n'
			return(c=='y'||c=='Y');
		}
		printf("Please respond by typing one of the letters y or n\n");
	}while(1);
}

//字符集Wordset操作
void CreatWordset(Wordset w){//建立自定义字符集和权重
    int i;
	char word[WordNUM+1]={
		'#',' ','\n',
		'a','b','c','d','e','f','g',
		'h','i','j','k','l','m','n',
		'o','p','q','r','s','t',
		'u','v','w','x','y','z'};
	int weight[WordNUM+1]={
		0,186,4,
		60,13,22,32,103,21,15,
		47,57,1,5,32,20,57,
		63,15,1,48,51,80,
		23,8,18,1,16,1};
	w->N =WordNUM;//记录字符个数
	w->SumWeight=0;//记录总的权重值
	for(i=1;i<=w->N;i++)
	{
		w->word [i]=word[i];
		w->weight [i]=weight[i];
		w->SumWeight+=weight[i];
	}
}		

void SaveWordsetFile(Wordset w){//保存到文件
	FILE*fp;
	if(!(fp=fopen("wordset","wb")))puts("cann't open file.");
	if(fwrite(w,sizeof(Word),1,fp)!=1)puts("SaveWordsetFile write error!");
	fclose(fp);	
}

void OpenWordsetFile(Wordset w){//读文件
	FILE*fp;
	w=(Wordset)malloc(sizeof(Word));//字符集及其权重所占空间分配
	if(!(fp=fopen("wordset","rb")))puts("cann't open file.");
	fread(w,sizeof(Word),1,fp);
}

void OutputWordset(Wordset w){//输出
	int i;
    for(i=1;i<=w->N;i++){
		printf("%c %d\t",w->word [i],w->weight [i]);
	}
	printf("SumWeight=%d\n",w->SumWeight);

}


//Huffman操作
void Select(HuffmanTree HT,int t,int*s1,int*s2){//在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号为s1,s2.
	int i;
	HuffmanTree p;
	int weight=99999 ;
	*s1=*s2=0;
	for(i=1,p=HT+1;i<=t;++i,++p)
	{
		if(p->parent==0 )
			if(weight>p->weight)
			{
				*s1=i;
				weight=p->weight ;
			}
	}
	weight=99999 ;
	for(i=1,p=HT+1;i<=t;++i,++p)
	{
		if(p->parent==0 && i!=*s1)
			if(weight>p->weight)
			{
				*s2=i;
                weight=p->weight ;
			}
	}
}

void CreatHuffmanTree(HuffmanTree HT,Wordset w){//建立HuffmanTree
	//w存放n个字符的权值（均>0），构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC。
	int i,n,m,s1,s2;
	HuffmanTree p;
    if(w->N<=1)return;
	n=w->N;
	m=2*n-1;//一棵有n个叶子结点的赫夫曼树共有2n-1个结点
	for(p=HT,i=0;i<=n;++i,++p)//HuffmanTree initing
	{
		p->n =i;
		p->data =w->word [i];
		p->weight =w->weight [i];
		p->lchild =0; p->parent =0; p->rchild =0;
	}
	for(;i<=m;++i,++p){
		p->n =i;p->lchild =0;p->data ='#';p->parent =0;p->rchild =0;p->weight =0;
	}
	printf("初始Huffman树:\n");
	for(p=&HT[1],i=1;i<=n;++i,++p)
	{
		printf("%d %c %d %d %d %d\t",p->n,p->data,p->weight,p->lchild,p->parent,p->rchild);
	}
	printf("\nCreat HTTree:\n");
	for(i=n+1;i<=m;++i){//建哈夫曼树
		//在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号为s1,s2.
		Select(HT,i-1,&s1,&s2);
		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;
		printf("%d %d %d %d %d\t",HT[i].n,HT[i].weight,HT[i].lchild,HT[i].parent,HT[i].rchild);
	}
	printf("\n");
}

void CreatHuffmanCode(HuffmanTree HT,HuffmanCode HC,Wordset w){//建立HuffmanCode
	//---从叶子结点到根逆向求每个字符的哈夫曼编码---
	char* cd;
	int i,n,start,c,f;
	n=w->N ;
    for(i=1;i<=n;i++)HC[i].data=w->word[i];  
	cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间
	cd[n-1]='\0';//编码结束符
	for(i=1;i<=n;++i){//逐个字符球哈夫曼编码
		start=n-1;//编码结束符位置
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){//从叶子结点到根逆向求编码
			if(HT[f].lchild==c) cd[--start]='0';//左0右1
			else cd[--start]='1';
		}
		HC[i].Code=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
		strcpy(HC[i].Code,&cd[start]);
	}
	free(cd);
	for(i=1;i<=n;i++)
		printf("%c %s\n",HC[i].data,HC[i].Code);
    printf("\n");
}//HuffmanCoding

void SaveHuffmanFile(HuffmanTree HT,HuffmanCode HC,int m,int n){//保存HuffmanTree和HuffmanCode
	FILE*fp1,*fp2;
	int i;

	//写出到文件
	if((fp1=fopen("HT","wb"))==NULL)
	{puts("can't open file \"HT.dat\" .");exit(0); }
	if((fp2=fopen("HC","wb"))==NULL)
	{puts("can't open file \"HC.dat\" .");exit(0); }
	for(i=0;i<=m;i++)
	    if(fwrite(&HT[i],sizeof(HTNode),1,fp1)!=1)puts("write error!\n");
	for(i=0;i<=n;i++)
	    if(fwrite(&HC[i],sizeof(HC[i]),1,fp2)!=1)puts("write error!\n");
	fclose(fp1);fclose(fp2);

}

void OpenHuffmanFile(HuffmanTree HT,HuffmanCode HC){	//从文件读入
	FILE*fp1,*fp2;

   	HT=(HuffmanTree)malloc((WordNUM+1)*sizeof(HTNode));//0号单元未用
	HC=(HuffmanCode)malloc((WordNUM+1)*sizeof(char*));//分配n个字符编码的头指针向量
	if((fp1=fopen("HT","rb"))==NULL)
	{puts("can't open file \"HT.dat\" .");exit(0); }
	if((fp2=fopen("HC","rb"))==NULL)
	{puts("can't open file \"HC.dat\" .");exit(0); }
	fread(&HT,sizeof(HT),1,fp1);
	fread(&HC,sizeof(HC),1,fp2);
	fclose(fp1);fclose(fp2);
}

 void OutputHuffmanTree(HuffmanTree HT,int n,int m){//输出HuffmanTree
	int i;
	puts("Huffman Tree:");
	printf("%d leaves %d HTNode :\n",n,m);
	puts("非叶节点的data域不是有效字符，不予输出!");
	for(i=1;i<=m;i++)//非叶节点的data域不是有效字符，不予输出
	{
		if(i<=n)printf("%d %c %d %d %d %d\t",HT[i].n,HT[i].data,HT[i].weight,HT[i].lchild,HT[i].parent,HT[i].rchild);
		else printf("%d %d %d %d %d\t",HT[i].n,HT[i].weight,HT[i].lchild,HT[i].parent,HT[i].rchild);
	}
	printf("\n");
}

void OutputHuffmanCode(HuffmanCode HC,int n){//输出HuffmanCode
	int i;
	puts("Huffman Code:");
	for(i=1;i<=n;i++)
		printf("%c %s\n",HC[i].data,HC[i].Code);
    printf("\n");
}

 void MessageInput(Message M){//信息输入
   char  s[1000]={'\0'};//输入缓冲
   M[0]='\0';
   while(strlen(gets(s))>0)//提供多行信息输入
   {
	   strcat(M,s);
	   strcat(M,"\n");
   }
}

void SaveMessageFile(Message M){//信息保存
   FILE  *fp;
   if((fp=fopen("Message.txt","w"))==NULL)
   {   printf("cann't open file");exit(0); }
   fputs(M,fp);
   fclose(fp);
}

void MessageFileOutput(Message M){//打开信息文件并输出
   FILE*fp;
   char s[1000];
   M[0]='\0';
   puts("The message in the Message File is :");
   if((fp=fopen("Message.txt","r"))==NULL){printf("cann't open file");exit(0); }
   while(fgets(s,1000,fp)!=NULL){
      fputs(s,stdout);
	  strcat(M,s);
   }
   fclose(fp);
   printstar();
   puts("MessageSource we code is:");
   puts(M);
}

void MessageCoding(Message M,Message MD,HuffmanCode HC,int n){//信息编码函数
    int i,k; 
	MD[0]='\0';
	for(i=0;M[i]!='\0';i++)
		for(k=1;k<=n;k++)
			if(M[i]==HC[k].data)strcat(MD,HC[k].Code);
}

void SaveMessageCode(Message MD){//信息编码保存到文件
   FILE  *fp;
   if((fp=fopen("MessageCode.txt","w"))==NULL)
   {   printf("cann't open file");exit(0); }
   fputs(MD,fp);
   fclose(fp);
}

void OutputMessageCode(Message MD){//信息编码输出
   puts("MessageCode is:");
   puts(MD);
   printstar();
   strcat(MD,"#");//作为结束标志
}

 void MessageDecoding(Message MD,HuffmanTree HT){//信息解码函数
   int i,root,r;
   for(i=1;HT[i].parent!=0;i++);//找根
   r=root=i;
   for(i=0;MD[i]!='#';){
	   while(HT[r].lchild&&HT[r].rchild){//0左走1右走，直到叶节点
		   if(MD[i]=='1')r=HT[r].rchild;
		   else r=HT[r].lchild;
		   i++;
	   }
	   putchar(HT[r].data);//输出叶节点
	   r=root;
   }
   putchar('\n');
}

void welcome(){
	puts("-----------------HuffmanCoding---------------");
	puts("\t\t\t\tJS000603-060059-李建平");
}

 void main(){//主函数，安排流程。
	HuffmanTree HT;
	HuffmanCode HC;
	Wordset w;
	Message M,MD;
	int n=WordNUM,m,i; 
	m=2*n-1;//一棵有n个叶子结点的赫夫曼树共有2n-1个结点
	printstar();
	welcome();
	printstar();
    
	//初始化
	for(i=0;i<5E8;i++);
	printstar();
	puts("初始化....");
	printstar();
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用
	HC=(HuffmanCode)malloc((n+1)*sizeof(HCode));//分配n个字符编码的头指针向量
	w=(Wordset)malloc(sizeof(Word));//字符集及其权重所占空间分配
    MD=(Message)malloc(MessageNUM*sizeof(char));
	M=(Message)malloc(MessageNUM*sizeof(char));
	for(i=0;i<5E8;i++);
	puts("Init OK!");
	printstar();

	//字符集操作与保存
	puts("创建字符集和权重....");
	printstar();
	for(i=0;i<5E8;i++);
	CreatWordset(w);//创建字符集和权重
    puts("CreatWordset ok!");
	printstar();
	for(i=0;i<5E8;i++);
	puts("Saving to file....");
	printstar();
	for(i=0;i<5E8;i++);
	SaveWordsetFile(w);//保存到文件
	puts("save OK!");
	printstar();
	puts("reading from the wordset file...");
	printstar();
	for(i=0;i<5E8;i++);
	OpenWordsetFile(w);//读文件
	puts("The wordset and each word's weight are:");
	printstar();
 	OutputWordset(w);//输出
	printstar();

    //HuffmanTree和HuffmanCode的建立与保存
	puts("建立HuffmanTree....");
	printstar();
	for(i=0;i<5E8;i++);
    CreatHuffmanTree(HT, w);//建立HuffmanTree
	printstar();
	puts("建立HuffmanCode....");
	printstar();
	for(i=0;i<5E8;i++);
	CreatHuffmanCode(HT,HC,w);//建立HuffmanCode
	printstar();
	puts("写入文件前输出HuffmanTree和HuffmanCode....");//写入文件前输出
	printstar();
	for(i=0;i<5E8;i++);
	OutputHuffmanTree(HT,n,m);//输出HuffmanTree
	printstar();
	for(i=0;i<5E8;i++);
    OutputHuffmanCode(HC,n);//输出HuffmanCode
	printstar();
	puts("Saving to file....");
    printstar();
	for(i=0;i<5E8;i++);
	SaveHuffmanFile(HT,HC,n,m);//保存HuffmanTree和HuffmanCode到文件
	puts("save OK!");
	printstar();
    puts("从文件读入后输出HuffmanTree和HuffmanCode....");//读入文件后输出
	printstar();
	for(i=0;i<5E8;i++);
	OpenHuffmanFile(HT,HC);//打开HuffmanTree和HuffmanCode文件
	OutputHuffmanTree(HT,n,m);//输出HuffmanTree
	printstar();
	for(i=0;i<5E8;i++);
    OutputHuffmanCode(HC,n);//输出HuffmanCode
	printstar();
    
	do{//信息输入及其编码与解码
		puts("please input the message you want to code....");
		printstar();
		MessageInput(M);//信息输入
		printstar();
		puts("saving to file....");//保存信息至文件
		printstar();
	    for(i=0;i<5E8;i++);
        SaveMessageFile(M);
        puts("MessageSave OK!");
	    printstar();
		puts("信息从文件读出并输出....");
		printstar();
	    for(i=0;i<5E8;i++);
	    MessageFileOutput(M);//信息从文件读出并输出
	    printstar();
		puts("信息编码....");
	    for(i=0;i<5E8;i++);
	    MessageCoding(M,MD,HC,n);//信息编码
	    printstar();
		puts("saving to file....");
		printstar();
	    for(i=0;i<5E8;i++);
        SaveMessageCode(MD);
		puts("save OK!");
		printstar();
		puts("编码输出");
		printstar();
	    OutputMessageCode(MD);//编码输出
	    printstar();
		puts("信息解码....");
		for(i=0;i<5E8;i++);
	    printf("The message after decoding is:\n");
		MessageDecoding(MD,HT);//解码输出
	    printstar();
		puts("源码输出对比....");
	    for(i=0;i<5E8;i++);
        puts("The MessageSource is:");
        puts(M);//源码输出对比
		printstar();
		printf("Try again?");
	}while(UserSaysYes());//提供重复进行信息输入
}//main