赫夫曼 .cpp

这是一个霍夫曼编码程序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#include<iostream.h>
#include<fstream.h>
#define MAX 30
#define MAXWEIGHT  30000
typedef struct{
	int key;
	int position;
}redtype ;
typedef struct{
	redtype r[27];
	int length;
}sqlist;
typedef struct{
	char data;
	int weight;
	int parent;
	int lchild;
	int rchild;
}huffnode,*huffmantree;//赫夫曼结点

typedef struct{
	char cd[MAX];
	int start;
}huffcode,*huffmancode;//赫夫曼编码
char codefilenm[81];//翻译后保存的文件名codefilenm
                     //此文件在编码和译码时都有需要
huffmantree ht;
  huffmancode hc;
int count[27];
int leafnum=26;
 char letter[28]={'@','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','\0'};//@键代表不是英文字符的其他数符；
 	


//函数名：int*array(char*filename)
 //功能：统计英文文件中的26个以英文字符出现的次数
 //返回值：返回文件中统计字符个数的数组的指针

int* array(char*filename)//返回filename文件中的统计字符个数的数组的指针 
{

	char ch;
	fstream file;
	file.open (filename,ios::in|ios::nocreate);
	if(!file){
		cout<<filename<<"打开文件失败！\n";
		exit(0);
	}
	for(int i=0;i<27;i++)  count[i]=0;
	file.get(ch);
	while(!file.eof()){
		switch(ch){
		case'a': 
		case'A':
			count[1]++;
			break;
		case'b':
		case'B':
			count[2]++;
			break;
		case'c':
		case'C':
			count[3]++;
			break;
		case'd':	
		case'D':
			count[4]++;
			break;
		case'e':
		case'E':
			count[5]++;
			break;
		case'f':
		case'F':
			count[6]++;
			break;
		case'g':
		case'G':
			count[7]++;
			break;
		case'h':
		case'H':
			count[8]++;
			break;
		case'i':
		case'I':
			count[9]++;
			break;
		case'j':
		case'J':
			count[10]++;
			break;
		case'k':
		case'K':
			count[11]++;
			break;
		case'l':
		case'L':
			count[12]++;
			break;
		case'm':
		case'M':
			count[13]++;
			break;
		case'n':
		case'N':
			count[14]++;
			break;
		case'o':
		case'O':
			count[15]++;
			break;
		case'p':
		case'P':
			count[16]++;
			break;
		case'q':
		case'Q':
			count[17]++;
			break;
		case'r':
		case'R':
			count[18]++;
			break;
		case's':
		case'S':
			count[19]++;
			break;
		case't':
		case'T':
			count[20]++;
			break;
		case'u':
		case'U':
			count[21]++;
			break;
		case'v':
		case'V':
			count[22]++;
			break;
		case'w':
		case'W':
			count[23]++;
			break;
		case'x':
		case'X':
			count[24]++;
			break;
		case'y':
		case'Y':
			count[25]++;
			break;
		case'z':
		case'Z':
			count[26]++;
			break;
		default:
			count[0]++;
			break;
			}
			file.get(ch);
			}
	
	file.close();
	return count;

}

/*//函数名：select函数
//功能：将最小权重的两个节点位置赋予s1,s2
//返回值：无
 	void select(huffmantree ht,int n,int &s1,int &s2){
	int m1=MAXWEIGHT;
	int m2=MAXWEIGHT;
	int k;
		s1=s2=0;//s1,s2为最小权重的两个结点的位置
		for(k=1;k<=n;k++){
			if(ht[k].parent ==-1){
				if(ht[k].weight <m1){
					m2=m1;
					s2=s1;
					m1=ht[k].weight;
					s1=k;
				}//if
				else if(ht[k].weight<m2){
					
					m2=ht[k].weight ;
					s2=k;
				}//else if
			}//if
		}//for
}//select*/


//函数名：heapselect函数
//功能：将最小权重的两个节点位置赋予s1,s2
//返回值：无
 	//n为赫夫曼结点个数
//s1和s2返回结点权值最小的点
void heapadjust(sqlist &l,int s,int m){
	
	
	redtype rc;
	rc=l.r[s];
    int j;
	for(j=2*s;j<=m;j*=2){
	if(j<m&&(l.r[j].key <l.r[j+1].key ))  ++j;
	if(!(rc.key <l.r[j].key ))        break;
	   l.r[s]=l.r[j];s=j;             
		
		}
		l.r[s]=rc;

}
void heapselect(huffmantree ht,int n,int&s1,int&s2){
	 sqlist l;
	
	 int i,j=1;
	 for(i=1;i<=n;i++){
	 if(ht[i].parent==-1){
		 l.r[j].key =ht[i].weight;
	     l.r[j].position =i;
		 j++;
	 }
	 }
	 l.length =j-1;
	 redtype temp;
	n=l.length ;
	for(i=n/2;i>0;--i)
		heapadjust(l,i,n );
	for(i=l.length ;i>1;--i){
         temp=l.r[1];
		 l.r[1]=l.r[i];
		 l.r[i]=temp;
		 heapadjust(l,1,i-1);
	}
	s1=l.r[1].position ;
	s2=l.r[2].position ;
}


//函数名：void huffcoding(huffmantree &ht,huffmancode&hc,int* w,int n,char* letter)
//功能：根据文件中统计字符后返回数组进行赫夫曼编码
//返回值：无

void huffcoding(huffmantree &ht,huffmancode  &hc){
//w存放n个字符的权值（均〉0），构造赫夫曼树ht,并求n个字符的赫夫曼编码hc
	ht=(huffmantree)malloc((2*leafnum)*sizeof(huffnode));
	hc=(huffmancode)malloc((leafnum+1)*sizeof(huffcode));
    int n=leafnum;
	int i=1,j=1;
	int c;
	int f;
	int m;
	m=2*n-1;
	
	
	for(i=1;i<=n;i++){
		ht[i].data  =letter[i];
		ht[i].weight  =count[i];
		ht[i].parent =-1;
		ht[i].lchild =-1;
		ht[i].rchild =-1;//若用0后译码不方便
		
	}
	for(;i<=m;i++) {
		ht[i].data  =0;
		ht[i].weight  =0;
		ht[i].lchild  =-1;
		ht[i].rchild =-1;
    	ht[i].parent  =-1;
	}
	//构造赫夫曼树
	int s1,s2;
	for(i=n+1;i<=2*n-1;i++){

	        	heapselect(ht, i-1,s1,s2);//s1,s2为最小权重的两个结点的位置
				ht[s1].parent =i;
				ht[s2].parent =i;
				ht[i].weight=ht[s1].weight +ht[s2].weight;
				ht[i].lchild =s1;
				ht[i].rchild =s2;
				}//for
  //------从叶子到根逆求每个字符的赫夫曼编码-------------
   huffcode d;

   
  for(i=1;i<=n;i++)
	{
		d.start =n+1;
		c=i;
		f=ht[i].parent ;
		while(f!=-1){
			if(ht[f].lchild  ==c)
				d.cd[--d.start ]='0';
			else
				d.cd [--d.start ]='1';
			    c=f;
			    f=ht[f].parent ;
		}//while
		hc[i]=d;
}//for
}//huffmancoding

//函数名：encodehufftree()
//功能：根据filename文件中英文字符出现的次数对文件进行赫夫曼编码，编码保存在另一文件codefilenm中；
//返回值：无返回值
void encodehufftree(huffmantree&ht,huffmancode &hc ){
	 fstream infile,outfile;
	 char ch;
	 int k;
	 char filename[81]; //要翻译的文件名filename 
	 
	 
	        
	 cout<<"请输入要翻译的文件名：";
	 cin>>filename;
	 infile.open(filename,ios::in|ios::nocreate);
	 if(!infile){
		 cout<<filename<<"打开文件失败\n";
         exit(0);
	 }//if(!infile)
	 cout<<"请输入编码保存的文件：";
	 cin>>codefilenm;
	 outfile.open(codefilenm,ios::out);
	 if(!outfile){
	      cout<<codefilenm<<"打开文件失败\n";
	      exit(0);
	}//if(!outfile)

	    array(filename);//功能：统计英文文件中的26个以英文字符出现的次数
	
        
 
        huffcoding(ht,hc);//功能：根据文件中统计字符后返回数组进行赫夫曼编码
        infile.get(ch);
	    while(!infile.eof()){
		       switch(ch){
        case'a': 
        case'A':
			 for(k=hc[1].start ;k<=leafnum;k++)
			 outfile<<hc[1].cd[k];
			 break;
		case'b':
		case'B':
			for(k=hc[2].start ;k<=leafnum;k++)
			 outfile<<hc[2].cd[k];
			break;
		case'c':
		case'C':
			for(k=hc[3].start ;k<=leafnum;k++)
			 outfile<<hc[3].cd[k];
			break;
		case'd':	
		case'D':
			for(k=hc[4].start ;k<=leafnum;k++)
			 outfile<<hc[4].cd[k];
			break;
		case'e':
		case'E':
			for(k=hc[5].start ;k<=leafnum;k++)
			 outfile<<hc[5].cd[k];
			break;
		case'f':
		case'F':
			for(k=hc[6].start ;k<=leafnum;k++)
			 outfile<<hc[6].cd[k];
			break;
		case'g':
		case'G':
			for(k=hc[7].start ;k<=leafnum;k++)
			 outfile<<hc[7].cd[k];
			break;
		case'h':
		case'H':
			for(k=hc[8].start ;k<=leafnum;k++)
			 outfile<<hc[8].cd[k];
			break;
		case'i':
		case'I':
			for(k=hc[9].start ;k<=leafnum;k++)
			 outfile<<hc[9].cd[k];
			break;
		case'j':
		case'J':
			for(k=hc[10].start ;k<=leafnum;k++)
			 outfile<<hc[10].cd[k];
			break;
		case'k':
		case'K':
			for(k=hc[11].start ;k<=leafnum;k++)
			 outfile<<hc[11].cd[k];
			break;
		case'l':
		case'L':
			for(k=hc[12].start ;k<=leafnum;k++)
			 outfile<<hc[12].cd[k];
			break;
		case'm':
		case'M':
			for(k=hc[13].start ;k<=leafnum;k++)
			 outfile<<hc[13].cd[k];
			break;
		case'n':
		case'N':
			for(k=hc[14].start ;k<=leafnum;k++)
			 outfile<<hc[14].cd[k];
			break;
		case'o':
		case'O':
			for(k=hc[15].start ;k<=leafnum;k++)
			 outfile<<hc[15].cd[k];
			break;
		case'p':
		case'P':
			for(k=hc[16].start ;k<=leafnum;k++)
			 outfile<<hc[16].cd[k];
			break;
		case'q':
		case'Q':
			for(k=hc[17].start ;k<=leafnum;k++)
			 outfile<<hc[17].cd[k];
			break;
		case'r':
		case'R':
			for(k=hc[18].start ;k<=leafnum;k++)
			 outfile<<hc[18].cd[k];
			break;
		case's':
		case'S':
			for(k=hc[19].start ;k<=leafnum;k++)
			 outfile<<hc[19].cd[k];
			break;
		case't':
		case'T':
			for(k=hc[20].start ;k<=leafnum;k++)
			 outfile<<hc[20].cd[k];
			break;
		case'u':
		case'U':
		for(k=hc[21].start ;k<=leafnum;k++)
			 outfile<<hc[21].cd[k];
			break;
		case'v':
		case'V':
			for(k=hc[22].start ;k<=leafnum;k++)
			 outfile<<hc[22].cd[k];
			break;
		case'w':
		case'W':
			for(k=hc[23].start ;k<=leafnum;k++)
			 outfile<<hc[23].cd[k];
			break;
		case'x':
		case'X':
			for(k=hc[24].start ;k<=leafnum;k++)
			 outfile<<hc[24].cd[k];
			break;
		case'y':
		case'Y':
			for(k=hc[25].start ;k<=leafnum;k++)
			 outfile<<hc[25].cd[k];
			break;
		case'z':
		case'Z':
			for(k=hc[26].start ;k<=leafnum;k++)
			 outfile<<hc[26].cd[k];
			break;
		default:
			outfile<<ch;
			break;
					}//switch
		
			infile.get(ch);
		}//while
			infile.close();
			outfile.close()	;
			cout<<"编码完成!\n";
			
	}
			
//函数名：void printhuffmancode(huffmantree ht,huffmancode hc,int leafnum
//功能：输出每个字符的和夫曼编码
//返回值：无
void printhuffcode(huffmantree HT,huffmancode HC,int n){
	int i;
	int k;
    if(HT==NULL){
		cout<<"\n请先编码！";
		exit(0);
	}
	printf("输出赫夫曼编码：\n");
	for(i=1;i<=n;i++)
	{
		printf("%c:",HT[i].data );
		printf(" %-3d ",HT[i].weight);
		for(k=HC[i].start ;k<=n;k++)
			printf("%c",HC[i].cd[k]);
		printf("\n");
	}
}


//函数名：void decoderhufftree(huffmantree ht,int datanum)
//功能：根据已建立的的赫夫曼树和编码文件codefilenm对编码文件进行译码；
//函数返回值：无
void decoderhufftree(huffmantree ht){
	fstream codefile,decodefile;
	int i=leafnum*2-1;
	char ch;

	codefile.open(codefilenm,ios::in|ios::nocreate);
	if(!codefile){
		cout<<codefilenm<<"请先编码\n";
		exit(0);
	}
	char decfilenm[81];
	cout<<"\n请输入将译码后字符保存的文件：";
    cin>>decfilenm;
	decodefile.open(decfilenm,ios::out);
	if(!decodefile){
		cout<<decfilenm<<"打开文件失败\n";
        exit(0);
	}
	if(ht==NULL){
		cout<<"请先编码!";
         return;
	}
	cout<<"\n下面是译码内容：\n";
	codefile.get(ch);
	while(!codefile.eof()){
		if(ch=='0'||ch=='1'){	
		         if(ch=='0')  i=ht[i].lchild ;
		         else if(ch=='1')     i=ht[i].rchild ; 
    	    if(ht[i].lchild ==-1){
				 cout<<ht[i].data ;
                 decodefile<<ht[i].data ;
				 i=leafnum*2-1;//表示重新从根结点开始往下搜索
			}
		}
		else{
				cout<<ch;
				decodefile<<ch;
			 }
            codefile.get(ch); 
		
	}
	codefile.close() ;
	decodefile.close();
	cout<<"\n译码完成\n";

}




//////////////////////////////////////////////////////////////////////////////////////////////////////
//主函数
//参数返回值：无

int menu()
{


	cout<<"             欢迎使用此赫夫曼编/译码系统!\n";
	cout<<"                               学号：040640203 姓名：张莉\n";
	cout<<"此编码尚有多处不足，请谅解!\n";
	cout<<"在此系统中可进行以下操作：\n";
	cout<<"      (1)编码(E)                 (2)译码(D) \n";
	cout<<"      (3)打印代码文件(P)         (4)退出(Q)\n    ";
   	
	char yourchoice;
    
	while(1){
		cout<<"请从清单中选择一个操作：(无大小写之分)\n";
		cin>>yourchoice;
		
		switch(yourchoice)
		{
		case'e':
		case'E':
			system("cls");
			cout<<"下面对文件进行编码:\n";
			
			encodehufftree(ht,hc);
			 break;
		case'd':
		case'D':
			system("cls");
			cout<<"下面对文件进行译码：\n";
			decoderhufftree(ht);
            break;
		case'p':
		case'P':
			system("cls");
			printhuffcode(ht,hc,leafnum);
			break;
		case'q':
		case'Q':
			system("cls");
			cout<<"\n---------------------感谢使用此程序-------------------\n\n";
			cout<<"pause";
			exit(0);
			return 0;
		}
			cout<<"    \n        (1)编码(E)                 (2)译码(D) \n";
        	cout<<"              (3)打印代码文件(P)         (4)退出(Q)\n    ";

	}
}

void main(){
	system("color 1f"); //屏幕颜色设定
    system("mode con: cols=140 lines=130"); 
	menu();
}