一、問題描述： 
利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編／譯碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編／譯碼系統。 

二、基本要求： 
1、I：初始化（Initialization），從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。 
2、E：編碼（Encoding），利用已建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀人），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。 
3、D：譯碼（Decoding），利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。 
4、P：輸出代碼文件（Print），將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。 
5、T：輸出哈夫曼樹（TreePrinting），將已在內存中的哈夫曼樹以直觀的方式（樹或凹人表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。 

三、測試數據：] 
用下表給出的字符集和頻度的實際統計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。 

字符 A B C D E F G H I J K L M 
頻度 186 64 13 22 32 103 21 15 47 1 5 32 20 20 

字符 N O P Q R S T U V W X Y Z 
頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 

四、實現提示： 
1、哈夫曼編碼采用一個字符串數組存儲。 
2、用戶界面可以設計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。 
3、在程序的一次執行過程中，第一次執行I、D或C命令之后，哈夫曼樹已經在內存了，不必再讀入。每次執行中不一定執行I命令，因為文件hfmTree可能早已建好。 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
#include<ctype.h> 
int n; 
struct node{ 
int w; 
int flag; 
char c; 
struct node *plink,*llink,*rlink; 
char code[50]; 

}*num[100],*root; 
FILE *fp; 
char tmpcode[50]; 
int t=0; 

void main(void) 
{ 
int i; 
void settree(void); //建立樹 
void code(void); //對文件編碼 
void decode(void); // 譯碼 
void disp(void); 
root=(struct node*)malloc(sizeof(struct node)); 
puts("*******************哈夫曼編/譯碼器演示******************************"); 

while(1){ 
start: 

puts("1. 初始化 2. 編碼 3. 譯碼 4.顯示編碼表 5. 退出"); 
while(scanf("%d",&i)!=1) 
{ 
while(getchar()!='\n') 
continue; 
puts("輸入錯誤!"); 
puts("請重新輸入！"); 
puts("1. 初始化 2. 編碼 3. 譯碼 4.顯示編碼表 5. 退出"); 
} 
switch (i) 
{ 
case 1: 
settree(); 
break; 
case 2: 
code(); 
break; 
case 3: 
decode(); 
break; 
case 4: 
disp(); 
break; 
case 5: 
exit(0); 
default: 
puts("輸入錯誤！"); 
puts("請重新輸入！"); 
goto start; 
} 
} 
} 
void settree(void) 
{ 
int i,j,k; 
struct node *p1,*p2,*tmp,*p; 
void go(struct node *); 
void setcode(struct node *);//建立每一個字符的編碼 
void printtree(struct node *); 
puts("輸入字符集的大小："); 
scanf("%d",&n); 
while(getchar()!='\n') 
continue; 

for(i=0;i<n;i++) 
{ 
p=(struct node *)malloc(sizeof(struct node)); 
puts("請輸入一個字符"); 
scanf("%c",&p->c); 
while(getchar()!='\n') 
continue; 
puts("請輸入該字符的權值:"); 
scanf("%d",&p->w); 
while(getchar()!='\n') 
continue; 

p->plink=NULL; 
p->rlink=NULL; 
p->llink=NULL; 
num[i]=p; 
} 

for(i=0;i<n-1;i++) //（遞增）排序 
{ 
for(j=i+1;j<n;j++) 
{ 
if(num[i]->w>num[j]->w) 
{ 
tmp=num[i]; 
num[i]=num[j]; 
num[j]=tmp; 
} 
} 
} 
/*******************************開始建立樹***********************/ 
num[n]=NULL; //結束標志 
k=n; 
while(num[1]!=NULL) 
{ 
p=(struct node *)malloc(sizeof(struct node)); 
p1=num[0]; 
p2=num[1]; 
p->llink=p1; 
p->rlink=p2; 
p->plink=NULL; 
p1->plink=p; 
p2->plink=p; 
p->w=p1->w+p2->w; 

for(i=1;i<k;i++) 
{ 
num[i]=num[i+1]; 
} 

k--; 
num[0]=p; 
for(i=0;i<k-1;i++) //排序 
{ 
for(j=i+1;j<k;j++) 
{ 
if(num[i]->w>num[j]->w) 
{ 
tmp=num[i]; 
num[i]=num[j]; 
num[j]=tmp; 
} 
} 
} 
} 

root=num[0]; 
/*建立完畢*/ 
/*寫入文件，前序*/ 
if((fp=fopen("c:\\hfmtree.wxl","wb"))==NULL) 
{ 
puts("文件打開錯誤！"); 
getchar(); 
exit(0); 
} 
setcode(root); 
go(root); 
fclose(fp); 
} 
void setcode(struct node *p) 
{ 
if(p->llink==NULL&&p->rlink==NULL) 
{ 
tmpcode[t]='\0'; 
strcpy(p->code,tmpcode); 
} 
else 
{ 
tmpcode[t++]='0'; 
setcode(p->llink); 
t--; 
tmpcode[t++]='1'; 
setcode(p->rlink); 
t--; 
} 
} 



void go(struct node *p) 
{ 

if(p->llink==NULL&&p->rlink==NULL) 
{ 
fputc('(',fp); 
fputc(p->c,fp); 
fputs(p->code,fp); 
fputc(')',fp); 
} 
else 
{ 

go(p->llink); 
go(p->rlink); 
} 
} 

void code(void) 
{ 
FILE *fp1,*fp2,*fp3; 
char ch1,ch2,c; 
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL) 
{ 
puts("文件打開錯誤！"); 
getchar(); 
exit(0); 
} 
if((fp2=fopen("c:\\tobetrans.txt","wb"))==NULL) 
{ 
puts("文件打開錯誤！"); 
getchar(); 
exit(0); 
} 
if((fp3=fopen("c:\\codefile.wxl","wb"))==NULL) 
{ 
puts("文件打開錯誤！"); 
getchar(); 
exit(0); 
} 

while((ch1=fgetc(fp2))!=EOF) 
{ 
t=0; 


while((ch2=fgetc(fp1))!=EOF) 
{ 
if(ch1==ch2) 
{ 
while((c=fgetc(fp1))!=')') 
{ 
tmpcode[t++]=c; 
} 
tmpcode[t]='\0'; 
fputs(tmpcode,fp3); 
fputc('@',fp3); 
rewind(fp1); 
break; 
} 
} 
} 
fclose(fp1); 
fclose(fp2); 
fclose(fp3); 
} 

void decode(void) 
{ 
FILE *fp1,*fp2,*fp3; 
char ch1,ch2,ch3; 
char temp_3[20]; 
char temp_1[20]; 
int t1,t3; 
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL) 
{ 
puts("文件打開錯誤！"); 
getchar(); 
exit(0); 
} 
if((fp2=fopen("c:\\textfile.txt","wb"))==NULL) 
{ 
puts("文件打開錯誤！"); 
getchar(); 
exit(0); 
} 
if((fp3=fopen("c:\\codefile.wxl","rb"))==NULL) 
{ 
puts("文件打開錯誤！"); 
getchar(); 
exit(0); 
} 

while((ch3=fgetc(fp3))!=EOF) 
{ 
t3=0; 
while(ch3!='@') 
{ 
temp_3[t3++]=ch3; 
ch3=fgetc(fp3); 
} 
temp_3[t3]='\0'; 
while((ch1=fgetc(fp1))!=EOF) 
{ 
if(isalpha(ch1)) 
{ 
ch2=ch1; 
t1=0; 
while((ch1=fgetc(fp1))!=')') 
{ 
temp_1[t1++]=ch1; 
} 
temp_1[t1]='\0'; 

if(strcmp(temp_1,temp_3)==0) 
{ 
fputc(ch2,fp2); 
rewind(fp1); 
break; 
} 
} 
} 
} 
fclose(fp1); 
fclose(fp2); 
fclose(fp3); 
} 


void disp(void) 
{ 
FILE *fp1,*fp2; 
char ch1,ch2; 
char tmp[20]; 
int t; 
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL) 
{ 
puts("文件打開錯誤！"); 
getchar(); 
exit(0); 
} 
if((fp2=fopen("c:\\hfmcode.txt","wb"))==NULL) 
{ 
puts("文件打開錯誤！"); 
getchar(); 
exit(0); 
} 
while((ch1=fgetc(fp1))!=EOF) 
{ 
if(ch1=='(') 
{ 
t=0; 
ch1=fgetc(fp1); 
ch2=ch1; 
while((ch1=fgetc(fp1))!=')') 
{ 
tmp[t++]=ch1; 
} 
tmp[t]='\0'; 
printf("%c-----%s\n",ch2,tmp); 
fputc(ch2,fp2); 
fputc('-',fp2); 
fputc('-',fp2); 
fputc('-',fp2); 
fputs(tmp,fp2); 
fputc('\n',fp2); 
} 
} 
fclose(fp1); 
fclose(fp2); 
}