[原创]我的一个产生哈夫曼编/译码演示系统的C程序

主题：[原创]我的一个产生哈夫曼编/译码演示系统的C程序

gongsong [专家分：0] 发布于 2004-06-29 23:39:00

[color=FF00FF][/color][em2][em2]#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define M 50

int n,m;
struct node   /*tree struct*/
{
   int weight;
   int parent;
   int lchild,rchild;
   char c;
   int num;
   };

  struct node *ht;
  typedef char * *hfmcode;
  hfmcode HC;
  char wd[M];

FILE *fp1,*fp2,*fp3,*h,*fp4,*fp5;

void Initialization()
{
     int i=0,j=0,k=0,x=0,y=0,b=0,tm=0;
     int p=0,r=0,l=0,w=0;
     int tmp;
     char ch;
     ht=(struct node *)malloc((m+1)*sizeof(struct node));
     for(i=1;i<=n;i++)
     {
         puts("input a char:");
         scanf("%c",&ht[i].c);
     wd[i]=ht[i].c;
         while(getchar()!='\n')
         continue;
     puts("input the weight of this char:");
         scanf("%d",&ht[i].weight);
         while(getchar()!='\n')
         continue;

         ht[i].parent=0;
         ht[i].rchild=0;
         ht[i].lchild=0;
         ht[i].num=i;
       }

     for(i=n+1;i<=m;i++) /*adding  branch */
      {
        ht[i].parent=0;
        ht[i].num=i;
        ht[i].weight=0;
        ht[i].lchild=0;
        ht[i].rchild=0;
    ht[i].c='$';
       }

     for(i=1;i<n;i++)  /*sort */
     {
       k=i;
       for(j=i+1;j<n+1;j++)
     if(ht[j].weight<ht[k].weight) k=j;

          p=ht[k].parent;
      w=ht[k].weight;
      r=ht[k].rchild;
      l=ht[k].lchild;
      tmp=ht[k].num;
      ch=ht[k].c;
      ht[k].parent=ht[i].parent;
      ht[k].weight=ht[i].weight;
      ht[k].rchild=ht[i].rchild;
      ht[k].lchild=ht[i].lchild;
      ht[k].num=ht[i].num;
          ht[k].c=ht[i].c;
      ht[i].parent=p;
      ht[i].weight=w;
      ht[i].rchild=r;
      ht[i].lchild=l;
      ht[i].num=tmp;
      ht[i].c=ch;

       }

     y=n+1;
     x=1; b=2;
     for(i=n+1;i<=m;i++,x+=2,b+=2,y++)
      {
        ht[x].parent=i; ht[b].parent=i;
        ht[i].lchild=ht[x].num; ht[i].rchild=ht[b].num;
        ht[i].weight=ht[x].weight+ht[b].weight;

       for(tm=1;tm<y;tm++)  /*sort */
       {
        k=tm;
        for(j=tm+1;j<y+1;j++)
     if(ht[j].weight<ht[k].weight) k=j;

          p=ht[k].parent; w=ht[k].weight; r=ht[k].rchild; l=ht[k].lchild;
      tmp=ht[k].num;  ch=ht[k].c;
          ht[k].parent=ht[tm].parent; ht[k].weight=ht[tm].weight; ht[k].rchild=ht[tm].rchild;
      ht[k].lchild=ht[tm].lchild; ht[k].num=ht[tm].num;
          ht[k].c=ht[tm].c;
          ht[tm].parent=p; ht[tm].weight=w; ht[tm].rchild=r; ht[tm].lchild=l;
      ht[tm].num=tmp;  ht[tm].c=ch;

        }

   }
       for(i=1;i<m;i++)  /* the last time repair */
     {
       k=i;
       for(j=i+1;j<m+1;j++)
     if(ht[j].num<ht[k].num)   k=j;

          p=ht[k].parent;
      w=ht[k].weight;
      r=ht[k].rchild;
      l=ht[k].lchild;
      tmp=ht[k].num;
      ch=ht[k].c;
      ht[k].parent=ht[i].parent;
      ht[k].weight=ht[i].weight;
      ht[k].rchild=ht[i].rchild;
      ht[k].lchild=ht[i].lchild;
      ht[k].num=ht[i].num;
          ht[k].c=ht[i].c;
      ht[i].parent=p;
      ht[i].weight=w;
      ht[i].rchild=r;
      ht[i].lchild=l;
      ht[i].num=tmp;
      ht[i].c=ch;

     }
      printf("the  lasted hffmantree is :\n");
      printf("   number        zifu       weight        parent         lchild         rchild\n");

     for(i=1;i<=m;i++)
   printf("%4d %13c %13d %13d %13d %13d\n",ht[i].num,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);

if((h=fopen("hfmTree","wb"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
  for(i=1;i<=m;i++)
    fprintf(h,"%4d %13c %13d %13d %13d %13d\r\n",ht[i].num,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
    fclose(h);
}
void Encode()
{ int i,mm,c,f,start;
  char wr,*cd,*str,ch;
  if((h=fopen("hfmTree","rb"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
   for(i=1;i<=m;i++)
    fscanf(h,"%4d %13c %13d %13d %13d %13d\n",ht[i].num,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
    fclose(h);
  HC=(hfmcode)malloc((n+1)*sizeof(char *));
  cd=(char *)malloc(n*sizeof(char));
  cd[n-1]='\0';
  for(i=1;i<=n;i++)
    { start=n-1;
      for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)
    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",wd[i],HC[i]);
  puts("IF input the file tobetran select A or a,  ELSE read from disk! ARE YOU SURE?");
  printf("PLEASE INPUT:");
  scanf("%c",&wr);getchar();
  if(wr=='a'||wr=='A')
    {  if((fp1=fopen("ToBeTran","w"))==NULL)
       { printf("cannot open file\n");
         exit(0);
        }
      printf("Please input the tobetran:\n");
      ch=getchar();
      while(ch!='#')
       { fputc(ch,fp1);
         putchar(ch);
         ch=getchar();
        }
      fclose(fp1);
  }
printf("\n");
  getchar();
  if((fp1=fopen("ToBeTran","r"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
  if((fp2=fopen("CodeFile","w"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
  while(!feof(fp1))
    { ch=fgetc(fp1);
      for(i=1;i<=n;i++) if(wd[i]==ch) for(mm=0;HC[i][mm]!='\0';mm++) fputc(HC[i][mm],fp2);
    }
  fclose(fp1);
  fclose(fp2);
}
void Decode()
{ int i,c,f=m;
  char ch;
  if((h=fopen("hfmTree","rb"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
   for(i=1;i<=m;i++)
    fscanf(h,"%4d %13c %13d %13d %13d %13d\n",ht[i].num,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
    fclose(h);
  if((fp2=fopen("CodeFile","r"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
  if((fp3=fopen("TextFile","w"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }

  while(!feof(fp2))
    { ch=fgetc(fp2);    printf("%c",ch);
      if(ch=='0')  f=ht[f].lchild;
      if(ch=='1')  f=ht[f].rchild;
      if(!ht[f].lchild&&!ht[f].rchild) { fputc(wd[f],fp3); f=m; }
    }
  fclose(fp2);
  fclose(fp3);
  printf("\n");
}

void Printcode()
{ int i=0;
  char ch;
  if((fp2=fopen("CodeFile","r"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
  if((fp4=fopen("CodePrin","w"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
  while(!feof(fp2)) { if(i==50) { printf("\n");  i=0; }  ch=fgetc(fp2); fputc(ch,fp4); printf("%c",ch); i++; }
  printf("\n");
  fclose(fp2);
  fclose(fp4);
}
void Printtree()
{ int i,k,top,b,p;

  int *level,*stack;
  printf("THE HUFFMANTREE IS :\n");
  level=(int *)malloc(n*sizeof(int));
  stack=(int *)malloc(n*sizeof(int));
  if((h=fopen("hfmTree","rb"))==NULL)
    { printf("cannot open file\n");
      exit(0); }

   for(i=1;i<=m;i++)
    fscanf(h,"%4d %13c %13d %13d %13d %13d\n",ht[i].num,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
    fclose(h);
  b=m;
  if(b!=0)
  { top=1; stack[top]=b;  level[top]=3;
    while(top>0)
    { p=stack[top];   k=level[top];    for(i=1;i<=k;i++) printf(" ");
      printf("%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; }
    }
  }
  if((fp5=fopen("TreePrint","w"))==NULL)
    { printf("cannot open file\n");
      exit(0); }
  for(i=1;i<=m;i++)
    fprintf(fp5,"%4d %13c %13d %13d %13d %13d\r\n",ht[i].num,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
  fclose(fp5);
}
void main()
{ char en;
  printf("********************huffmantree encode/decode display ststem*******************\n");
  puts("i/I---Initialization   d/D---decode    q/Q---end");
  puts("t/T---print hfmtree    e/E---encode    p/P---print file's code");
  puts("********************huffmantree encode/decode display ststem********************");
  puts("please select a menu number:");
  scanf("%c",&en);getchar();
  for(;!(en=='q'||en=='Q');)
  {
   if(en=='i'){puts("input the number of the total char n:");scanf("%d",&n);m=2*n-1;
               while(getchar()!='\n')  continue; Initialization();}
   if((en=='e')||(en=='E'))  Encode();
   if((en=='d')||(en=='D'))  Decode();
   if((en=='p')||(en=='P'))  Printcode();
   if((en=='t')||(en=='T'))  Printtree();
   puts("*******************huffmantree encode/decode display ststem*******************");
   puts("i/I---Initialization   d/D---decode    q/Q---end");
   puts("t/T---print hfmtree    e/E---encode    p/P---print file's code");
   puts("*******************huffmantree encode/decode display ststem*******************");
   puts("please select a menu number:");
   scanf("%c",&en);
   while(getchar()!='\n')  continue;
   }
}

本帖地址： http://bbs.pfan.cn/post/43807.html

回复列表（共15个回复）

沙发

sagiltarivs [专家分：2610] 发布于 2004-06-30 04:02:00

太经典了！

板凳

ufoufobufo [专家分：0] 发布于 2004-06-30 22:36:00

好　谢谢

3 楼

jjgoooooole [专家分：30] 发布于 2004-07-03 19:19:00

高！

4 楼

doglin [专家分：30] 发布于 2004-07-04 10:59:00

hi:
could some one explain what is hoffman encoding???

I am just too lazy to google :P

5 楼

robitxie [专家分：0] 发布于 2004-07-06 22:19:00

有错啊!!!大大

6 楼

meteor135 [专家分：6060] 发布于 2004-07-09 16:29:00

希望你花点时间整理一下你的代码，太乱了！
其中最大的问题就是，程序运行后用户不能随便选择菜单，否则就出错！
我花了大半天时间修改了你的代码，但是因为有点着急，部分算法可能改的和原来不一致了，等我改完后把我修改后的贴上，让你看看那叫什么感受！
这次先贴点片断吧。

7 楼

meteor135 [专家分：6060] 发布于 2004-07-09 17:34:00

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

/*常量文件名*/
const char *TableFileName = "HfmTbl.txt";
const char *SourceFileName = "SrcText.txt";
const char *CodeFileName = "HfmCode.txt";
const char *DecodeFileName ="DecodeText.txt";

/*打印格式字符串常量*/
const char *PrintFormatStr = "%4d %13c %13d %13d %13d %13d\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)

/*内存交换函数，用于结构体变量交换*/
void MemSwap(void *buf1, void *buf2, size_t buflen)
{
    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);
    }
}

/*从文件读取数据*/
int ReadFromFile()
{
    int i;
    int m;
    FILE *h;

    if((h=fopen(TableFileName,"r"))==NULL)
    {
        printf("cannot open file\n");
        exit(0);
    }
    fscanf(h,"%d",&m);
    if(ht!=NULL)
        free(ht);
    ht=(struct node *)malloc((m+1)*sizeof(struct node));
    memset(ht,0,(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 EatCharsUtilNewLine()
{
    while(getchar()!='\n')
        continue;
}

/*根据参数n初始化*/
void Initialization(int n)
{
    int i=0,j=0,x=0,y=0;
    FILE *h;

    int m=2*n-1;

    ht=(struct node *)malloc((m+1)*sizeof(struct node));
    /*动态内存全部初始化为0*/
    memset(ht,0,(m+1)*sizeof(struct node));

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

        puts("input the weight of this char:");
        scanf("%d",&ht[i].weight);
        EatCharsUtilNewLine();

        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);
    }

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

    /*数据写入文件并输出至屏幕*/
    if((h=fopen(TableFileName,"wb"))==NULL)
    {
        printf("cannot open file\n");
        exit(0);
    }
    printf("the  lasted hffmantree is :\n");
    printf("   number        zifu       weight        parent         lchild         rchild\n");

    /*首行写入数据行数*/
    fprintf(h,"%d\n",m);
    /*循环写入每行同时向屏幕输出*/
    for(i=1;i<=m;i++)
    {
        printf(PRINT_FORMAT_PARAM(i));
        fprintf(h,PRINT_FORMAT_PARAM(i));
    }
    fclose(h);
}

/*其它暂保留*/

8 楼

suiyu715 [专家分：0] 发布于 2004-07-10 03:12:00

服了

9 楼

tmdcool [专家分：0] 发布于 2004-07-11 15:52:00

麻烦 matorl50 把自己的程序贡献出来，让大家一起分享。你真得写得很好啊[em8][em15]

10 楼

meteor135 [专家分：6060] 发布于 2004-07-11 18:20:00

To tmdcool:
    最近本人因为工作原因没有充足的时间上网，你可能不知道本人曾是本论坛版主之一，由于长久没有管理论坛，被站长削为普通网客，令本人汗颜之至！同样因为此原因，我都不敢再申请版主之职，只能忙里偷乐给大家解决一些小问题。怎奈身在江湖，身不由己阿！
    本贴所发程序本人尚未改完，并不是不想与大家分享，且去搜索本人所发帖子，基本都是本着为大家服务解难的宗旨的。
    本人编程之心未老，以程序谈论人生之志不泯！

PS.   My name is meteor135, not mator150!

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[原创]我的一个产生哈夫曼编/译码演示系统的C程序

回复列表（共15个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创]我的一个产生哈夫曼编/译码演示系统的C程序

回复列表 （共15个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共15个回复）