亲，您未登录哦！ 登录 | 注册
首页  |  社区  |  工具箱  |  代码库  |  博客  |  招聘  |  文章  |  新闻  |  下载  |  读书
回 帖 发 新 帖 刷新版面

主题：关于哈夫曼编码译码问题

whtuling [专家分：1230] 发布于 2006-06-26 20:28:00

以下两个程序分别是为了将建好的树存入文件，然后用另一个程序来读取树译码，前一个程序没有任何问题（tc下面结果和语法都没问题），第二个程序也能把树读到内存，而且我在程序中还把它显示出来了，但是译码完之后总是会添加一乱码？？？？？？
编码程序：
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;

int LookFor(char *str,char letter,int count)
{
    int i;
    for(i=1;i<=count;i++)
    {
        if(letter==str[i]) return i;/*如果是相同的字符就返回其下标
            否则返回-1即又有一个新的字符*/
    }
    return -1;
}
void OutputWeight(char *Data,int Length,
                  char **WhatLetter,
                  int **Weight,int *AllCount)
{
    int i;
    char *Letter=(char*)malloc((Length+1)*sizeof(char));
    int *LetterCount=(int *)malloc(Length*sizeof(int));

    int Index;
    *AllCount=0;
    for(i=0;i<Length;i++)
    {
        if(i==0)
        {
            (*AllCount)++;        
            Letter[1]=Data[0];
            LetterCount[1]=1;
        }/*第一个字符*/
        else
        {
            Index=LookFor(Letter,Data[i],*AllCount);
            if(Index==-1)
            {
                  (*AllCount)++;
                Letter[*AllCount]=Data[i];
                LetterCount[*AllCount]=1;
            }/*有新的字符产生*/
            else
            {
                LetterCount[Index]++;
            }/*重复的字符其权数加一*/
        }
    }
    (*Weight)=(int*)malloc(((*AllCount)+1)*sizeof(int));/*存放各个字符的权，比实际的不同后的总字符数多一*/
    (*WhatLetter)=(char*)malloc(((*AllCount)+1)*sizeof(char));/*存放需要编码的各个字符，比实际的不同后
    的总字符数多一，为了和后面的一一对应*/

    for(i=1;i<=(*AllCount);i++)
    {        
        (*Weight)[i]=LetterCount[i];
        (*WhatLetter)[i]=Letter[i];
    }/*为了使和后面的编码过程中的数组的下标对应这里也从一开始*/
    (*WhatLetter)[i]='\0';
    printf("AllCount:%d\n",*AllCount);
}

void Select(HuffmanTree *HT,int i,int *s1,int *s2)
{
    int k,temp;
    temp=32767;
    for(k=1;k<=i;k++)
        if((*HT)[k].parent==0&&(*HT)[k].weight<temp)
            {
                temp=(*HT)[k].weight;
                *s1=k;
            }
    temp=32767;
    for(k=1;k<=i;k++)
      if((*HT)[k].parent==0&&k!=(*s1)&&(*HT)[k].weight<temp)
          {                                           
              temp=(*HT)[k].weight;
              *s2=k;
          }
          printf("s1=%d,s2=%d\n",*s1,*s2);
}
本帖地址：  http://bbs.pfan.cn/post/177991.html

回复列表 （共5个回复）

沙发

whtuling [专家分：1230] 发布于 2006-06-26 20:29:00

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)
{
    HuffmanTree p;
    int i,m,s1,s2,start,c,f;
    char *cd;
    if(n<=1)return;
    m=2*n-1;
    *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for(p=(*HT+1),i=1;i<=n;i++,p++)/*注意这里的p=(*HT+1),因为第一个地址没用*/
    {
        p->weight=w[i];
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
        printf("p[%d]=%d\n",i,p->weight);
    }
    for(;i<=m;i++,p++)
  {
      p->weight=0;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
  }/*初始化*/
    for(i=n+1;i<=m;i++)
    {                        
        Select(HT,i-1,&s1,&s2);
        (*HT)[s1].parent=i;(*HT)[s2].parent=i;
        (*HT)[i].lchild=s1;(*HT)[i].rchild=s2;
        (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
    }
    *HC=(HuffmanCode)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);
}

void Save_HT(HuffmanTree HT,int n)
{
    FILE *HT_P;
    int i;
    if((HT_P=fopen("HuffmanTree.txt","wb"))==NULL)
    {
        printf("Cannot open file.\n");
        exit(0);
    }
    for(i=1;i<=2*n-1;i++)
    if(fwrite(&HT[i],sizeof(HTNode),1,HT_P)!=1)
        printf("File write error.\n");
    fclose(HT_P);    
}

void Save_Code(HuffmanCode HC,char *Letter,int n)
{
    FILE *HT_Code;
    int i,j;
    if((HT_Code=fopen("HuffmanCode.txt","wb"))==NULL)
    {
        printf("Cannot open file.\n");
        exit(0);
    }
    for(i=1;i<=n;i++)
  printf("%s\n",HC[i]);
  for(i=1;i<=n;i++)
    fprintf(HT_Code,"%c",Letter[i]);
    fclose(HT_Code);    
}

void main()
{
    HuffmanTree HT;
    HuffmanCode HC;
    char Data[1024],*WhatLetter,Num[1024];
    int *weight,N=0,i,flag;
    /*clrscr();*/
    puts("Enter a string:");
    gets(Data);
  OutputWeight(Data,strlen(Data),&WhatLetter,&weight,&N);
  HuffmanCoding(&HT,&HC,weight,N);
  for(i=1;i<=N;i++)
  {
      printf("%c---%d---",WhatLetter[i],weight[i]);
      printf("%s\n",HC[i]);
  }
  Save_HT(HT,N);
  Save_Code(HC,WhatLetter,N);
  printf("LWT=%d\n",strlen(WhatLetter));/*注意一号单元没有使用*/
  puts("Enter the list_01:");
  gets(Num);
  flag=2*N-1;
  for(i=0;i<strlen(Num);i++)
  {
      if(Num[i]=='0')       flag=HT[flag].lchild;
      else if(Num[i]=='1')  flag=HT[flag].rchild;
             else{puts("Wrong List!");getch();exit(0);}  
      if(HT[flag].lchild==0&&HT[flag].rchild==0)
      {    
          printf("%c",WhatLetter[flag]);
          flag=2*N-1;
      }            
  }
  getch();
}

板凳

whtuling [专家分：1230] 发布于 2006-06-26 20:31:00

以上为第一个程序，下面的译码程序真的感觉没有错啊？？？？？？？？
#include<stdio.h>
#include<string.h>
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;

char *WhatLetter;
HuffmanTree HT;
HuffmanCode HC;
int n;

void Load(int *N)
{
    FILE *HT_P,*HT_Code;
    int i,j;
    if((HT_P=fopen("HuffmanTree.txt","rb"))==NULL)
    {
        printf("打开文件出错！\n");
        getch();
        exit(0);
    }
    printf("从文件中读取出来的树\n");
    for(i=1;fread(&HT[i],sizeof(HTNode),1,HT_P)!=0;i++)        
        printf("\n%d,%d,%d,%d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    *N=i-1;
    n=(*N+1)/2;
    printf("N=%d\n",*N);
    fclose(HT_P);
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
    /*for(i=1;i<=n;i++)
    HC[i]=(char *)malloc((n+1)*sizeof(char));*/
    WhatLetter=(char *)malloc((n+1)*sizeof(char));
    if((HT_Code=fopen("HuffmanCode.txt","rb"))==NULL)
    {
        printf("Cannot open file.\n");
        exit(0);
    }
    for(i=1;i<=n;i++)
    fscanf(HT_Code,"%c",&WhatLetter[i]);
    puts(WhatLetter+1);
    fclose(HT_Code);
}
    
main()
{
    int i,N=0,flag;
    char Num[1024];
    Load(&N);
  printf("Enter the list_01:");
  gets(Num);
  flag=N;
  for(i=0;i<strlen(Num);i++)
  {     
    if(Num[i]=='0')       flag=HT[flag].lchild;
      else if(Num[i]=='1')  flag=HT[flag].rchild;
             else{puts("Wrong List!");getch();exit(0);}  
      if(HT[flag].lchild==0&&HT[flag].rchild==0)
      {    
          printf("%c",WhatLetter[flag]);
          flag=N;
      }
  }
}

3 楼

aboutbmp [专家分：830] 发布于 2006-06-26 22:42:00

设断点跟踪，调试程序啊。

4 楼

flagger [专家分：0] 发布于 2006-06-29 09:55:00

#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)



/*内存交换函数，用于结构体变量交换*/
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));
    for(i=1;i<=m;i++)
    {
        fscanf(h,READ_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;
            }
        }
    }
}

/*初始化并写入文件*/
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");

 

5 楼

flagger [专家分：0] 发布于 2006-06-29 10:01:00

/*首行写入数据行数*/
    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;
        }
    }
}
这是一个高手的程序
希望有人能添加注释

我来回复

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

程序员工具箱 new

  • 更多工具

    • 代码片段

  • 模拟键盘（不可按）
  • 碰撞的唐三
  • 精彩奥运热点赛事的实时采集
  • 获取天气动态信息
  • 文件查找
  • python大数据抓取京东电脑销量数据
  • 爬虫技术不仅仅支持数据采集
  • 抓取脉脉APP上的职业信息
  • 爬虫中多线程的运用
  • 四则运算以及一元二次方程
  • 欢迎来共享你的NB代码

    • 本版新帖

  • 分析---外星人计算PI的程序
  • 八王后图形输出
  • 24点中的不可能组合
  • 《冰原探险》
  • 《丘比特的烦恼》
  • 《快乐的蜜月》
  • 《丘比特的烦恼》2
  • 《折线》
  • 《积木搭建问题》
  • 最短路径算法及应用
  • 递归算法及其应用
  • 程序设计中的数学方法
  • 黑洞数的验证
  • 上楼梯算法的java实现
  • 关于算法的学习建议