哈夫曼编/译码演示系统的C程序

/*==============================================*/
/*                          */
/* huffman.c(pp) - a huffman arithmetic demonstration */
/* smith_135@163.com                 */
/* QQ: 58101543                    */
/* version 0.9                    */
/* copyright (c) meteor135              */
/* 2004.7.13                     */
/*                          */
/*==============================================*/
#include <stdio.h>
#include <stdlib.h>

#ifdef __cplusplus
#include <conio.h>
#include <ctype.h>
#include <string.h>
#endif /*__cplusplus*/

/*树结构和全局结构指针*/
struct node
{
  int num;/*结点编号*/
  char c;
  int weight;
  int parent;
  int lchild,rchild;
} * ht;

/*常量文件名*/
const char *TableFileName  = "HfmTbl.txt";
const char *SourceFileName  = "SrcText.txt";
const char *CodeFileName   = "HfmCode.txt";
const char *DecodeFileName  = "DecodeText.txt";
const char *TreeViewFileName = "TreeView.txt";
/*打印格式字符串常量*/
const char *PrintFormatStr = "%4d %13c %13d %13d %13d %13d\r\n";
/*读取格式字符串常量*/
const char *ReadFormatStr = "%d %c %d %d %d %d";
/*打印参数宏*/
#define PRINT_PARAM(i) ht[(i)].num,ht[(i)].c,ht[(i)].weight,\
    ht[(i)].parent,ht[(i)].lchild,ht[(i)].rchild
/*读取参数宏*/
#define READ_PARAM(i) &ht[(i)].num,&ht[(i)].c,&ht[(i)].weight,\
    &ht[(i)].parent,&ht[(i)].lchild,&ht[(i)].rchild
/*打印格式和参数宏*/
#define READ_FORMAT_PARAM(i) ReadFormatStr,READ_PARAM(i)
/*读取格式和参数宏*/
#define PRINT_FORMAT_PARAM(i) PrintFormatStr,PRINT_PARAM(i)


/************************************************************/
/**       UTILITY FUNCTIONS             **/
/************************************************************/
/*内存交换函数，用于结构体变量交换*/
void MemSwap(void *buf1, void *buf2, size_t buflen)
{
  if(buf1!=buf2)
  {
    void *p = malloc(buflen);
    memmove(p,buf1,buflen);
    memmove(buf1,buf2,buflen);
    memmove(buf2,p,buflen);
    free(p);
  }
}

/*打印表*/
void PrintHT(int from, int to)
{
  int i;
  for(i=from;i<=to;i++)
  {
    printf(PRINT_FORMAT_PARAM(i));
  }
  printf("\n");
}

/*选择法排序*/
void SelectSort(int from, int to)
{
  int i,j,k;
  for(i=from;i<to;i++) /*sort */
  {
    for(k=i,j=i+1;j<=to;j++)
      if(ht[j].weight<ht[k].weight)
        k=j;
    if(k!=i)
      MemSwap(&ht[k],&ht[i],sizeof(struct node));
    PrintHT(from,to);
  }
}

/*释放ht*/
void free_ht()
{
  if(ht != NULL)
  {
    free(ht);
    ht = NULL;
  }
}

/*从文件读取数据保存到全局堆中，调用方要记得释放*/
int ReadFromFile()
{
  int i;
  int m;
  FILE *h;
  
  if((h=fopen(TableFileName,"r"))==NULL)
  {
    printf("cannot open %s\n", TableFileName);
    getch();
    return 0;
  }
  fscanf(h,"%d",&m);
  free_ht();
  ht=(struct node *)calloc(m+1,sizeof(struct node));
  //printf("%d\n",m);
  for(i=1;i<=m;i++)
  {
    fscanf(h,READ_FORMAT_PARAM(i));
    // printf(PRINT_FORMAT_PARAM(i));
  }
  fclose(h);
  return m;
}

/*吃掉无效的垃圾字符*/
void EatCharsUntilNewLine()
{
  while(getchar()!=@#\n@#)
    continue;
}

/*按节点序号重新排序*/
void SortByNum(int m)
{
  int i = 0, j;
  size_t len = sizeof(struct node);
  for(i = 1; i < m; i ++)
  {
    for(j = i + 1; j <= m; j ++ )
    {
      if (ht[j].num == i)
      {
        MemSwap(&ht[i],&ht[j],len);
        break;
      }
    }
  }
}
/************************************************************/
/**       COMMAND INSTRUCTION FUNCTIONS       **/
/************************************************************/
/*初始化并写入文件*/
void Initialize()
{
  int i=0,x=0,y=0,n,m;
  FILE *h;

  puts("input the number of the total char n:");
  scanf("%d",&n);
  EatCharsUntilNewLine();

  m=2*n-1;
  ht=(struct node *)calloc(m+1,sizeof(struct node));

  /*遍历叶子结点进行初始化*/
  for(i=1;i<=n;i++)
  {
    puts("input a char:");
    scanf("%c",&ht[i].c);
    EatCharsUntilNewLine();
    
    puts("input the weight of this char:");
    scanf("%d",&ht[i].weight);    
    EatCharsUntilNewLine();

    ht[i].num=i;
  }
  PrintHT(1,n);

  for(i=n+1;i<=m;i++) /*adding branch */
  {
    ht[i].c=@#$@#;
    ht[i].num=i;
  }
  PrintHT(n+1,m);

  /*用选择法将第1到n个元素从小到大排序*/
  SelectSort(1,n);
  PrintHT(1,n);

  for(x=1,i=n+1;i<=m;i++,x+=2)
  {
    y=x+1;
    ht[x].parent=ht[y].parent=i;
    ht[i].lchild=ht[x].num;
    ht[i].rchild=ht[y].num;
    ht[i].weight=ht[x].weight+ht[y].weight;
    /*排序*/
    SelectSort(1, i);
  }

  /*察看排序效果*/
  PrintHT(1,m);
  getch();

  SortByNum(m);
  /*察看恢复序号效果*/
  PrintHT(1,m);
  getch();
  
  /*数据写入文件并输出至屏幕*/
  if((h=fopen(TableFileName,"wb"))==NULL)
  {
    printf("cannot open %s\n", TableFileName);
    getch();
    return;
  }
  printf("The huffmantree is:\n");
  printf("  number   character   weight    parent     lchild     rchild\n");

  /*首行写入数据行数*/
  fprintf(h,"%d\r\n",m);
  /*循环写入每行同时向屏幕输出*/
  for(i=1;i<=m;i++)
  {
    printf(PRINT_FORMAT_PARAM(i));
    fprintf(h,PRINT_FORMAT_PARAM(i));
  }
  free_ht();
  fclose(h);
}
/*编码并写入文件*/
void Encode()
{
  int i,mm,c,f,start;
  char wr,*cd = (char *)NULL, ch;
  char **HC = (char **)NULL;
  FILE *fp1, *fp2;
  int m = ReadFromFile();
  int n = (m+1)/2;
  
  if(HC!=NULL) free(HC);
  HC=(char **)calloc(n+1,sizeof(char *));
  if(HC==NULL) return;

  if(cd!=NULL) free(cd);
  cd=(char *)calloc(n,sizeof(char));
  if(cd==NULL) return;

  for(i=1;i<=n;i++)
  {
    start=n-1;
    for(c=i,f=ht[i].parent; f!=NULL; c=f,f=ht[f].parent)
    {
      /*cd[--start]=@#1@#-(ht[f].lchild==c);*/
      if(ht[f].lchild==c)
        cd[--start]=@#0@#;
      else
        cd[--start]=@#1@#;
    }

    HC[i]=(char *)malloc((n-start)*sizeof(char));
    strcpy(HC[i],&cd[start]);
  }
  free(cd);
  
  for(i=1;i<=n;i++)
    printf("%c----%s\n",ht[i].c,HC[i]);

  printf("IF input the file tobetran select A or a, ELSE read from %s.\n",SourceFileName);
  printf("PLEASE INPUT:");
  scanf("%c",&wr);

  if(wr==@#a@#||wr==@#A@#)
  {
    if((fp1=fopen(SourceFileName,"w+"))==NULL)
    {
      printf("cannot open %s\n", SourceFileName);
      getch();
      return;
    }
    printf("Please input the tobetran:(end with @##@#)\n");
    ch=getch();
    while(ch!=@##@#)
    {
      fputc(ch,fp1);
      putchar(ch);
      ch=getch();
    }
    rewind(fp1);
    printf("\n");
  }
  else
  {
    if((fp1=fopen(SourceFileName,"r"))==NULL)
    {
      printf("cannot open %s\n", SourceFileName);
      getch();
      return;
    }
  }
  if((fp2=fopen(CodeFileName,"w"))==NULL)
  {
    printf("cannot open %s\n", CodeFileName);
    getch();
    return;
  }
  while(!feof(fp1))
  {
    ch=fgetc(fp1);
    for(i=1;i<=n;i++)
      if(ht[i].c==ch)
        for(mm=0;HC[i][mm]!=@#\0@#;mm++)
        {
          fputc(HC[i][mm],fp2);
          printf("%c",HC[i][mm]);
        }
  }
  printf("\n");
  for(i=1;i<=n;i++)
    fprintf(fp1,"\r\n%c----%s",ht[i].c,HC[i]);
  for(i=1;i<=n;i++)
    fprintf(fp2,"\r\n%s----%c",HC[i],ht[i].c);
  for(i = 1; i <= n; i ++)
  {
    free(HC[i]);
  }
  free(HC);
  free_ht();
  fclose(fp1);
  fclose(fp2);
}
/*解码写入文件并输出*/
void Decode()
{
  FILE *CodeFileP, *TextFileP;
  char ch = @#\0@#;
  int f;
  int m = ReadFromFile();
  f = m;
  if((CodeFileP=fopen(CodeFileName,"r"))==NULL)
  {
    printf("cannot open %s\n", CodeFileName);
    getch();
    return;
  }
  if((TextFileP=fopen(DecodeFileName,"w"))==NULL)
  {
    printf("cannot open %s\n", DecodeFileName);
    getch();
    return;
  }

  while(!feof(CodeFileP)&&ch!=@#\n@#)
  {
    ch=fgetc(CodeFileP); 
    if(ch==@#0@#)
      f=ht[f].lchild;
    if(ch==@#1@#)
      f=ht[f].rchild;
    if(!ht[f].lchild&&!ht[f].rchild)
    {
      fputc(ht[f].c,TextFileP);
      printf("%c",ht[f].c);
      f=m;
    }
  }
  free_ht();
  fclose(CodeFileP);
  fclose(TextFileP);
  printf("\n");
}
/*不解码直接输出文件中的huffman编码*/
void PrintCode()
{
  int i=0;
  char ch = 0;
  FILE *CodeFileP;
  if((CodeFileP=fopen(CodeFileName,"r"))==NULL)
  {
    printf("cannot open %s\n",CodeFileName);
    getch();
    return;
  }
  while(!feof(CodeFileP)&&ch!=@#\n@#)
  {
    if(i++==50)
    {
      printf("\n");
      i=0;
    }
    ch=fgetc(CodeFileP);
    printf("%c",ch);
  }
  printf("\n");
  fclose(CodeFileP);
}

/*输出Huffman树*/
void PrintTree()
{
  int i,k,top,p;
  int *level,*stack;
  FILE *TreePrintFileP;
  int m = ReadFromFile();
  int n = (m+1)/2;

  if((TreePrintFileP=fopen(TreeViewFileName,"w"))==NULL)
  {
    printf("cannot open %s\n", TreeViewFileName);
    getch();
    return;
  }

  printf("THE HUFFMANTREE IS :\n");
  fprintf(TreePrintFileP,"THE HUFFMANTREE IS :\n");
  level=(int *)malloc(n*sizeof(int));
  stack=(int *)malloc(n*sizeof(int));

  if(m!=0)
  {
    top=1;
    stack[top]=m;
    level[top]=3;
    while(top>0)
    {
      p=stack[top]; 
      k=level[top];  
      for(i=1;i<=k;i++)
      {
        printf(" ");
        fprintf(TreePrintFileP," ");
      }
      printf("%d\n",ht[p].weight);
      fprintf(TreePrintFileP,"%d\n",ht[p].weight);
      top--;
      if(ht[p].rchild!=0)
      {
        top++;
        stack[top]=ht[p].rchild;
        level[top]=k+3;
      }
      if(ht[p].lchild!=0)
      {
        top++;  
        stack[top]=ht[p].lchild;
        level[top]=k+3;
      }
    }
  }
  free(level);
  free(stack);
  fclose(TreePrintFileP);
}

int prompt()
{
  char en;
  puts("\n******************* huffman arithmetic demonstration *****************");
  puts("i/I---Initialize   e/E---encode  p/P---print file@#s code");
  puts("t/T---print hfmtree d/D---decode  q/Q---quit program");
  puts("******************* huffman arithmetic demonstration *****************");
  puts("please choose a menu item and press enter to continue.");
  printf(">");
  scanf("%c",&en);
  EatCharsUntilNewLine();
  return tolower(en);
}

void main()
{
  while(1)
  {
    switch(prompt())
    {
      case @#i@#:
        Initialize();
        break;
      case @#e@#:
        Encode();
        break;
      case @#d@#:
        Decode();
        break;
      case @#p@#:
        PrintCode();
        break;
      case @#t@#:
        PrintTree();
        break;
      case @#q@#:
        free_ht();
        return;
    }
  }
}

如有问题，请与我们联系。

原文转自：http://www.ltesting.net