您的位置：志宏網 >計算機 >數據結構(C語言) >哈夫曼編碼 
 
  
HuffmanTree  
實驗目的  樹型結構是一種應用極為廣泛的非線性數據結構,也是本課程的重點內容,哈夫曼樹(最優二叉樹)是樹型結構的典型應用,本次實驗突出了數據結構加操作的程序設計觀點,希望能根據樹型結構的非線性特點,熟悉各種存儲結構的特性,達到如何應用樹型結構的非線性特點,熟悉各種存儲結構的特性,達到如何應用樹型結構解決具體問題的目的.  
問題描述 利用哈夫曼編碼進行住處通訊可以大大提高信道利用率,縮短住處傳輸時間,降低成本,但是,這要求在發送端通過一個編碼系統將傳輸的數據預先編碼,在接收端通過一個譯碼系統對傳來的數據進行譯碼(復原),對于雙向傳輸信息的信道,每端都一個完整的編碼譯碼系統,試為這樣的住處收發站寫一個哈夫曼友的編碼譯碼系統.  
 
基本要求 一個完整的系統應以下功能:
1. 初始化,從終端讀入n個字符和n個權值,建立哈夫曼樹,并將它存放在文件HuffmanTree中.
2. 編碼.利用已建立好的哈夫曼樹,對要傳輸的數據正文(存在文件StextFile中)進行編碼,將結果代碼存(傳輸)到文件CodeFile中.
3. 譯碼.利用已建好的哈夫曼樹,對傳輸到達的CodeFile中的數據代碼進行譯碼,將譯碼結果存入文件RtestFile中.
4. 打印和顯示哈夫曼樹,(可以樹或凹入表的形式)
5. 打印文件.打印CodeFile,StestFile,RtestFile文件內容,以比較它們的不同.  
測試數據 1. 利用教科書例6-2中的數據調試程序.
2. 用下面給出的字符集及頻度的統計數據建立哈夫曼樹:
字符:ABCDEFGHIJKLMN
頻度:64 13 22 32 103 21 15 47 57 1 5 32 20 57 
字符:OPQRSTUVWXYZ 空
頻度:63 15 1 48 51 80 23 8 18 1 16 1 186
并實現正文"THIS PROGEAM IS MY FAVORITE"的編碼和譯碼.  
實現提示 1. 文件可以使用數組表示.
2. 用戶界面可以設計為菜單方式.
3. 第一次執行初始化程序后,哈夫曼樹已建好,以后不一定需要再建立哈夫曼樹.  
選做內容  對你的"哈夫曼友的編碼譯碼系統"的源程序代碼(包括行尾符號)進行編碼和譯碼. 



--------------------------------------------------------------------------------
本源代碼,版權所有,嚴禁復制,違者必究!
--------------------------------------------------------------------------------
測試通過,  僅供大家參考!!  

#define MAX_INIT_TREE 100
#define OK 1
#define ERROR 0
#define SCREENWIDTH 40
#define SCREENHEIGHT 40
#define MAX_FILENAME 20
#include<stdio.h>

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

HuffmanTree HT;

void FillTree(int n){
 int i,weight,go,j;
 char ch;
 printf("There are %d TreeNodes requere!\nInput the 1 node!\n",n);
 printf("ch\n");
 scanf("%c",&ch);
 getchar();
 printf("weight\n");
 scanf("%d",&weight);
 getchar();
 HT[1].character=ch;
 HT[1].weight=weight;
 for(i=2;i<=n;){
  go=OK;
  printf("There are %d TreeNodes requere!\nInput the %d node!\n",n,i);
  printf("ch\n");
  scanf("%c",&ch);
  getchar();
  printf("weight\n");
  scanf("%d",&weight);
  getchar();
  for(j=1;j<i;j++)
   if(HT[j].character==ch){
    printf("ERROR!\nHT[%d] is the same number!\nPlease reinput!\n",j);
    go=ERROR;
    break;
   }
  if(go){
   HT[i].character=ch;
   HT[i].weight=weight;
   i++;
  }
 }
}
void Select(int num,int *s1,int *s2){
 int i,num0,num1,num2;
 for(i=1;i<num;i++)if(!(HT[i].parent)){num1=i++;break;}
 for(;i<num;i++)if(!(HT[i].parent)){num2=i++;break;}
 if(HT[num1].weight>HT[num2].weight){
  num0=num1;num1=num2;num2=num0;
 }
 for(;i<num;i++){
  if(HT[i].weight<HT[num2].weight&&!(HT[i].parent))
   if(HT[i].weight<HT[num1].weight){
    num2=num1;num1=i;
   }else num2=i;
 }
 *s1=num1;*s2=num2;
}
int PrintFile(char *filename){
 FILE *fp;
 char ch;
 int i;
 printf("file:\t%s\n\n",filename);
 if(!(fp=fopen(filename,"r"))){
  printf("file %s is not exist!\n",filename);
  return ERROR;
 }
 while(!feof(fp))putchar(fgetc(fp));
 putchar('\n');
 fclose(fp);
 return OK;
}
int CreateHFTree(int *treenodes){
 int n,i,m,s1,s2;
 char ch;
 m=treenodes;
 printf("Tree has how many nodes?\n");
 scanf("%d",&n);getchar();
 if(n<=1||n>MAX_INIT_TREE){printf("Input ERROR!\n");return ERROR;}
 m=2*n;
 if(!(HT=(HuffmanTree)malloc(m*sizeof(HTNode))))printf("ERROR\n!");
 for(i=0;i<m;i++){
  HT[i].parent=0;
  HT[i].lchild=0;
  HT[i].rchild=0;
 }
 FillTree(n);
 for(i=n+1;i<m;i++){
  Select(i,&s1,&s2);
  HT[i].lchild=s1;
  HT[i].rchild=s2;
  HT[s1].parent=HT[s2].parent=i;
  HT[i].weight=HT[s1].weight+HT[s2].weight;
  HT[i].character='\0';
 }
 *treenodes=n+1;
 return OK;
}
void ClearScreen(){
 int i;
 for(i=0;i<SCREENHEIGHT;i++)putchar('\n');
 putchar('\n');
}
void HR(){
 int i;
 for(i=0;i<SCREENWIDTH;i++)putchar('=');
 putchar('\n');
}
int InCode(char *infile,int treenodes,char *outfile){
 FILE *in,*out;
 char ch,c[MAX_INIT_TREE];
 int self,parent,start,i;
 if(!(in=fopen(infile,"r"))){
  printf("file %s is not exist!\n",infile);
  return ERROR;
 }
 if(!(out=fopen(outfile,"w"))){
  printf("open file %s ERROR!\n",outfile);
  return ERROR;
 }
 while(!feof(in)){
  ch=fgetc(in);
  for(i=1;i<=treenodes;i++)
   if(ch==HT[i].character){
    start=MAX_INIT_TREE;
    c[--start]='\0';
    self=i;parent=HT[self].parent;
    while(parent){
     c[--start]=(HT[parent].lchild==self)?'0':'1';
     self=parent;
     parent=HT[self].parent;
    }
    while(start<MAX_INIT_TREE)fputc(c[start++],out);
    break;
   }
  if(i>=treenodes)printf("%c is not found in HuffmanTree!\n",ch);
 }
 fclose(in);
 fclose(out);
 return OK;
}
int OutCode(char *infile,int treenodes,char *outfile){
 FILE *in,*out;
 int self,child;
 char ch;
 if(!(in=fopen(infile,"r"))){
  printf("can not open file %s!\n",infile);
  return ERROR;
 }
 if(!(out=fopen(outfile,"w"))){
  printf("can not open file %s!\n",outfile);
  return ERROR;
 }
 while(!feof(in)){
  ch=fgetc(in);
  self=2*treenodes-3;
  if('0'==ch)child=HT[self].lchild;
  else child=HT[self].rchild;
  while(child){
   self=child;
   child=('0'==fgetc(in))?HT[self].lchild:HT[self].rchild;
  }
  fputc(HT[self].character,out);
 }
 return OK;
}
void PrintTree(int root,int n){
 int i;
 getch();
 printf("[%c](%d)----",HT[root].character,HT[root].weight);
 if(HT[root].rchild)PrintTree(HT[root].rchild,n+1);
 else printf("NULL\n");
 for(i=0;i<=n;i++)printf("|          ");
 printf("\n");
 for(i=0;i<n;i++)printf("|          ");
 if(HT[root].lchild)PrintTree(HT[root].lchild,n);
 else printf("NULL\n");
}
main(){
 char initfile[]={"D:\\stextfil.txt"},midfile[]={"D:\\codefile.txt"},lastfile[]={"D:\\textfile.txt"};
 int treenodes;
 ClearScreen();
 CreateHFTree(&treenodes);
 HR();getch();
 printf("The following is the tree you just inputed!\n\n");
 PrintTree(2*treenodes-3,0);HR();getch();
 PrintFile(initfile);HR();getch();
 InCode(initfile,treenodes,midfile);HR();
 PrintFile(midfile);HR();getch();
 OutCode(midfile,treenodes,lastfile);HR();getch();
 PrintFile(lastfile);HR();getch();
 printf("Now!OK!\n");
}