一个赫夫曼编码/译码器的C代码

事先声明,这个也不是我写的,大家凑和着看一下吧,马上要交作业了……
//以下为原文
 

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>

#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_NUM 10000
#define MAX 60

typedef int Status;
typedef char **HuffmanCode;

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

typedef struct{
    HuffmanTree HT;
    char        *c;
    int         longth;
    HuffmanCode HC;
}Huffman;

void Select(HuffmanTree HT,int end,int *s1,int *s2)
{
  int i;
  int min1=MAX_NUM;
  int min2;
  for (i=1;i<=end;i++)
  {
    if (HT[i].parent==0&&HT[i].weight<min1)
    {
      *s1=i;
      min1=HT[i].weight;
    }
  }
  min2=MAX_NUM;
  for(i=1;i<=end;i++)
  {
    if(HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight)
    {
      *s2=i;
      min2=HT[i].weight;
    }
  }
}

Huffman HuffmanCoding(Huffman Hfm)
{
  /*———————————*/
  int i,n,m,s1,s2,start;
  int c,f;
  char *cd;
  n=Hfm.longth;
  if(n<=1)  return Hfm;
  m=2*n-1;
 
  for(i=n+1;i<=m;++i)
  {
    Select(Hfm.HT,i-1,&s1,&s2);
    Hfm.HT[s1].parent=i;
    Hfm.HT[s2].parent=i;
    Hfm.HT[i].lchild=s1;
    Hfm.HT[i].rchild=s2;
    Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;
  }
  /*——————————————*/
  Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
  cd=(char *)malloc(n*sizeof(char));
  cd[n-1]=”;

  for(i=1;i<=n;++i)
  {
    start=n-1;
    for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
    {
      if(c==Hfm.HT[f].lchild)  cd[–start]=’0′;
      else cd[–start]=’1′;
    }
    Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
    strcpy(Hfm.HC[i],&cd[start]);
  }
  free(cd);
  return Hfm;
}

Huffman InputHuffman(Huffman Hfm)
{
    int i,n;
    clrscr();
    printf("nn********************Initial*********************n");
    printf("The chars and weights will be saved in the file "hfmTree"n");
    printf("Please input the number of the chars: ");
    scanf("%d",&n);
    Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
    Hfm.c=(char *)malloc((n+1)*sizeof(char));
    for(i=1;i<=n;i++)
    {
      printf("Please input the char: ");
      scanf("%s",&Hfm.c[i]);
      printf("Please input the weight of the char: ");
      scanf("%d",&Hfm.HT[i].weight);
      Hfm.HT[i].parent=0;
      Hfm.HT[i].lchild=0;
      Hfm.HT[i].rchild=0;
    }
    for(;i<=2*n-1;++i)
    {
      Hfm.HT[i].weight=0;
      Hfm.HT[i].parent=0;
      Hfm.HT[i].lchild=0;
      Hfm.HT[i].rchild=0;
    }
    Hfm.longth=n;
    return Hfm;
}

Huffman InitHuffman(Huffman Hfm)
{
  int n,i;
  FILE *fp;
  fp=fopen("hfmTree","rt");
  if(fp==NULL)
  {
    Hfm=InputHuffman(Hfm);
    fp=fopen("hfmTree","wt");
    fprintf(fp,"%dn",Hfm.longth);
    for(i=1;i<=Hfm.longth;i++)
      fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
    rewind(fp);
  }
  else
  {
    fscanf(fp,"%dn",&n);
    Hfm.c=(char *)malloc((n+1)*sizeof(char));
    Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
    for(i=1;i<=n;i++)
      fscanf(fp,"%s %d",&Hfm.c[i],&Hfm.HT[i].weight);
    for(i=1;i<=n;i++)
    {
      Hfm.HT[i].parent=0;
      Hfm.HT[i].lchild=0;
      Hfm.HT[i].rchild=0;
    }
    for(;i<=2*n-1;++i)
    {
      Hfm.HT[i].weight=0;
      Hfm.HT[i].parent=0;
      Hfm.HT[i].lchild=0;
      Hfm.HT[i].rchild=0;
    }
    Hfm.longth=n;
  }
  fclose(fp);
  Hfm=HuffmanCoding(Hfm);
  return Hfm;
}

void Output(Huffman Hfm)
{
  int i,n;
  n=Hfm.longth;
  printf("nn******************Output the code of the chars****************nn");
  for(i=1;i<=n;i++)
  {
     printf("n");
     printf("Char: %ct",Hfm.c[i]);
     printf("Weight: %dt",Hfm.HT[i].weight);
     printf("Code: ");
     puts(Hfm.HC[i]);
  }
}

void Encoding(Huffman Hfm)
{
  int i=0,j=0,n;
  char ch[MAX];
  FILE *fp,*ffp;
  n=Hfm.longth;
  printf("nn*******************Encoding**************************nn");
  if((ffp=fopen("ToBeTran","rt"))==NULL)
  {
    printf("nPlease input the sentence: ");
    scanf("%s",&ch);
    printf("n");
    fp=fopen("CodeFile","wt+");
  }
  else
  {
    fscanf(ffp,"%s",ch);
    fclose(ffp);
  }
  while(ch[j])
    {
      for(i=1;i<=n;i++)
    if(ch[j]==Hfm.c[i])
    {
      printf("%s",Hfm.HC[i]);
      fprintf(fp,"%s",Hfm.HC[i]);
      break;
    }
     j++;
   }
   rewind(fp);
   fclose(fp);
}

void Decoding(Huffman Hfm)
{
  HuffmanTree p;
  int i,n;
  int j=0;
  char d[50];
  FILE *fp;
  n=Hfm.longth;
  printf("nn******************Decoding************************nn");
  if((fp=fopen("CodeFile","rt"))==NULL)
  {
    printf("Please input the code:");
    scanf("%s",&d);
  }
  else
  {
    fscanf(fp,"%s",d);
    fclose(fp);
  }
  printf("nThe file is : ");
  fp=fopen("TextFile","wt+");
  while(d[j])
  {
    p=&Hfm.HT[2*n-1];
    while(p->lchild||p->rchild)
    {
      if(d[j]==’0′)
      { i=p->lchild;  p=&Hfm.HT[i]; }
      else
      { i=p->rchild;  p=&Hfm.HT[i]; }
      j++;
    }
    printf("%c",Hfm.c[i]);
    fprintf(fp,"%c",Hfm.c[i]);
  }
  fclose(fp);
}

Huffman RebuildHuffman(Huffman Hfm)
{
  int n,i;
  FILE *fp;
  fp=fopen("hfmTree","wt");
  Hfm=InputHuffman(Hfm);
  fprintf(fp,"%dn",Hfm.longth);
  for(i=1;i<=Hfm.longth;i++)
  fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
  rewind(fp);
  fclose(fp);
  Hfm=HuffmanCoding(Hfm);
  return Hfm;
}

int main()
{
  Huffman Hfm;
  char choice=’a’;
  Hfm=InitHuffman(Hfm);
  while(choice!=’q’)
  {
    clrscr();
    printf("nnn*************************************nn");
    printf("a. Encoding:nn");
    printf("b. Decoding:nn");
    printf("c. Print all codes:nn");
    printf("d. Rebuild the huffmantree:nn");
    printf("q. Quit…nn");
    printf("n************************************nn");
    printf("Please enter your choice: ");
    scanf("%s",&choice);
    switch(choice)
    {
      case ‘a’:
       clrscr();
       Encoding(Hfm);
       printf("nn*******Please enter anykey to continue*******n");
       getch(); break;
      case ‘b’:
       clrscr();
       Decoding(Hfm);
       printf("nn*******Please enter anykey to continue********n");
       getch(); break;
      case ‘c’:
       clrscr();
       Output(Hfm);
       printf("nn*******Please enter anykey to continue********n");
       getch(); break;
      case ‘d’:
       clrscr();
       Hfm=RebuildHuffman(Hfm);
       printf("nn********************Initial*********************n");

       getch(); break;
      case ‘q’:
       break;
      default:
       printf(" Your choice is wrong!n Please enter anykey to choice again!n");
       getch(); break;
      }
    }
  return 0;
}

1.              选择a,输入句子,例如THIS-PROGRAM-IS-MY-FAVORITE,空格用“”代替。

2.              选择b,程序将从CodeFile文件中读取代码,译为字符输出并保存到TextFile文件。

3.              选择c,输出赫夫曼树的所有字符,权值和赫夫曼代码。

4.              选择d,重建赫夫曼树。

5.              选择q,退出系统。

由于是在TC下弄的,所以没有注释,凑合着看吧,呵呵

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: