哈夫曼编/译码器

[问题描述]
 

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。

[基本要求]

一个完整的系统应具有以下功能：

（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：印哈夫曼树（Tree printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

[测试数据]
（1）利用下面这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。
（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“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  57  1   5   32  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） 编码结果以文本方式存储在文件CodeFile中。
（2） 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
（3） 在程序的一次执行过程中，第一次执行I，D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

下面是我的作业。嘿嘿，完全通过的作业。大家自己看看就明白了。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/*定义全局变量*/
struct node{                //建立一个节点
 char c;                   //c为字母
 int w;                    //w为权值
 struct node *plink,*llink,*rlink; //plink双亲指针，llink左指针，rlink右指针
 char code[50];  //code为编码
}*num[100],*root;    //创建根指针，数组指针
FILE *fp;            //文件指针
char tmpcode[50];  //临时存放编码的数组
int n,t=0;   

void main()          //主函数
{
    char i;
 void settree();   //建立树
 void code();     //对文件编码
 void decode();   // 译码
 void treeprint();     //印哈夫曼树 
 void print();    //印代码文件
 root=(struct node*)malloc(sizeof(struct node)); //给根指针分配空间
 puts("\t*******************   哈夫曼编/译码器演示   **********************");
 puts("                                                        laycher.cn出品\n");
start:
 puts("\t*************************   菜单栏    *****************************");
 puts("I. 初始化    E. 编码    D. 译码   P.印代码文件   T.印哈夫曼树    Q. 退出");//输出菜单
 printf("请输入指令：");
 scanf("%c",&i);      //输入要操作的指令
 getchar();           //空格也是一个字符
 switch (i)           //用switch 来判断要进行的操作
 {
 case 'I':
 case 'i':
  settree();      //I 或 i 初始化，建树
  break;
 case 'E':
 case 'e':
  code();         //E 或 e 进行编码
  break;
 case 'D':
 case 'd':
  decode();       //D 或 d 进行译码
  break;
 case 'P':
 case 'p':
        print();        //P 或 p 印代码文件
  break;
 case 'T':
 case 't':
  treeprint();    //T 或 t 印哈夫曼树
  break;
 case 'Q':
 case 'q':
  exit(0);        //Q 或 q 退出
 default:
  puts("\n输入错误!");   //其他情况重新输入
  puts("请重新输入!\n");
 }
 goto start;         //不输入Q或q就无法退出
}

void settree()
{
 int i,j,k;
 struct node *p1,*p2,*tmp,*p;
 void go(struct node *);                       //建立循环函数
 void setcode(struct node *);                 //建立每一个字符的编码
 printf("输入字符集的大小：");
 scanf("%d",&n);                            //输入要输入的字符的个数
 for(i=0;i<n;i++)                             //输入每个字符以及字符的权值
 {
  
  p=(struct node *)malloc(sizeof(struct node)); //分配地址空间
  getchar();                                 //回车也是一个字符
  printf("请输入一个字符:");
  scanf("%c",&p->c);
  printf("请输入该字符的权值:");
  scanf("%d",&p->w);
  p->plink=NULL;
  p->rlink=NULL;
  p->llink=NULL;
  num[i]=p;                                  //将每个字符以及他的权值赋值到num指针数组中
 } 
 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)                             //开始建树，找两个最小的，然后p1、p2、p之间的指向关系做好
 {
  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];                         //num[2]全部前移一位
  }
  k--;                                         //总个数少一位
  num[0]=p;                                   //num[0]用来存放目前的根
  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.txt","w")))      //开始写入文件
 {
  puts("文件c:\\hfmtree.txt打开错误!");
  getchar();
  exit(0);
 }
 else
 {
  setcode(root);                          //建立每一个字符的编码
  go(root);                               //将每个字符的编码存进文件hfmtree
  fclose(fp);
 }
 printf("存入c:\\hfmtree.txt成功!\n\n"); 
}

void setcode(struct node *p)
{
 if(p->llink==NULL&&p->rlink==NULL)
 {
  tmpcode[t]='\0';                         //结束字符
  strcpy(p->code,tmpcode);                 //tmpcode为字符的编码，存到P指针的code里
 }
 else
 {
  tmpcode[t++]='0';
  setcode(p->llink);                     //利用递归函数和指针得出每个字符的编码
  t--;
  tmpcode[t++]='1';                      //左为0，右为1
  setcode(p->rlink);
  t--;
 }
}

void go(struct node *p)
{ 
 if(p->llink==NULL&&p->rlink==NULL)     //以（A000010）形式存入文件
 {
  fputc('(',fp);
  fputc(p->c,fp);
  fputs(p->code,fp);
  fputc(')',fp);
 }
 else
 {  
  go(p->llink);                  //利用递归函数，将每个字符和编码存入文件
  go(p->rlink);
 }
}

void code()                            //E编码。
{
    FILE *fp1,*fp2,*fp3;
 char ch1,ch2,c;
 if(!(fp1=fopen("c:\\hfmtree.txt","r")))    //文件打开错误情况
 {
  puts("文件c:\\hfmtree.txt打开错误!");
  getchar();
  exit(0);
 }
    if(!(fp2=fopen("c:\\tobetran.txt","r")))
 {
  puts("文件c:\\tobetran.txt打开错误!");
  getchar();
  exit(0);
 }
 if(!(fp3=fopen("c:\\codefile.txt","w")))
 {
  puts("文件c:\\codefile.txt打开错误!");
  getchar();
  exit(0);
 }
 while((ch1=fgetc(fp2))!=EOF)              //将要翻译的字母与hfmtree.txt的字母进行比较
 {                                         //如果相同则输出其对应的编码
  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);                //使文件fp1的位置指针指向文件开始。
                break;
            }
  }
 }
 fclose(fp1);
 fclose(fp2);
 fclose(fp3);
 printf("存入c:\\codefile.txt成功!\n\n");
}

void decode()                              //D译码
{
    FILE *fp1,*fp2,*fp3;
 char ch1,ch2,ch3;
 char temp3[20];
 char temp1[20];
 int t1,t3;
 if(!(fp1=fopen("c:\\hfmtree.txt","r")))
 {
  puts("文件c:\\hfmtree.txt打开错误!");
  getchar();
  exit(0);
 }
    if(!(fp2=fopen("c:\\textfile.txt","w")))
    {
  puts("文件c:\\textfile.txt打开错误!");
  getchar();
  exit(0);
    }
    if(!(fp3=fopen("c:\\codefile.txt","r")))
 {
  puts("文件c:\\codefile.txt打开错误!");
  getchar();
  exit(0);
 }
 while((ch3=fgetc(fp3))!=EOF)       //以@为标志，取得要翻译的字母的编码
 {                                  //然后与hfmtree.txt中的编码进行比较，
  t3=0;                          //相同则输出其对应的字母
  while(ch3!='@')
  {
   temp3[t3++]=ch3;
   ch3=fgetc(fp3);
  }
  temp3[t3]='\0';
  while((ch1=fgetc(fp1))!=EOF)
  {
   if(ch1>='A'&&ch1<='Z'||ch1==' '||ch1>='a'&&ch1<='z')//当ch1为英文字母a-z或A-Z或空格时，返回非零值，否则返回零。
   {
    ch2=ch1;
    t1=0;
    while((ch1=fgetc(fp1))!=')')  
    {
     temp1[t1++]=ch1;
    }  
    temp1[t1]='\0';
    if(strcmp(temp1,temp3)==0)   //如果编码一致，则将对应的字母存入文件
    {
     fputc(ch2,fp2);
     rewind(fp1);
     break;
    }
   }
  }
 }
 fclose(fp1);
 fclose(fp2);
 fclose(fp3);
    printf("存入c:\\textfile.txt成功!\n\n");
}

void print()                          //P.印代码文件
{
 FILE *fp1,*fp2;
 int ch,i=0;
    if(!(fp1=fopen("c:\\codefile.txt","r")))
 {
  puts("文件c:\\codefile.txt打开错误!");
  getchar();
  exit(0);
 }
 if(!(fp2=fopen("c:\\codeprin.txt","w")))
 {
  puts("文件c:\\codeprin.txt打开错误!");
  getchar();
  exit(0);
 }
 ch=getc(fp1);
 while(ch!=EOF)                      //将codefile.txt的编码以每行50个显示出来。
 {
  putc(ch,fp2);
  printf("%c",ch);
  ch=getc(fp1);
  i++; 
  if(i==50)
  { 
   printf("\n");
   putc('\n',fp2);
   i=0;
  }
 }
 fclose(fp1);
 fclose(fp2);
 printf("\n存入c:\\codeprin.txt成功!\n\n");
}

void treeprint()                             //T.印哈夫曼树
{
    FILE *fp1,*fp2;
 char ch1,ch2;
 char tmp[20];
 int t,n,i;
 if(!(fp1=fopen("c:\\hfmtree.txt","r")))
 {
  puts("文件c:\\hfmtree.txt打开错误!");
  getchar();
  exit(0);
 }
 if(!(fp2=fopen("c:\\treeprint.txt","w")))
 {
  puts("文件c:\\treeprint.txt打开错误!");
  getchar();
  exit(0);
 }
 while((ch1=fgetc(fp1))!=EOF)            //以凹入表的形式输出在屏幕上并保存在treeprint.txt文件中
 {
  if(ch1=='(')
  {
   t=0;
   ch1=fgetc(fp1);
   ch2=ch1;
   while((ch1=fgetc(fp1))!=')')
   {
    tmp[t++]=ch1;
   }
   tmp[t]='\0';
   n=strlen(tmp);
   for(i=0;i<n;i++)
   { printf(" ");
   fputc(' ',fp2);}
   for(i=0;i<40-n;i++)
   { printf("#");
   fputc('#',fp2); }
   printf("   %c-----%s\n",ch2,tmp);
   fputs("   ",fp2);
   fputc(ch2,fp2);
   fputs("---",fp2);
   fputs(tmp,fp2);
   fputc('\n',fp2);
  }
 }
 fclose(fp1);
 fclose(fp2);
 printf("\n存入c:\\treeprint.txt成功!\n\n");
}