哈夫曼编码.txt

一个关于哈夫曼编码的程序

您的位置：志宏网 >计算机 >数据结构(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");
}