正在浏览栏目导航：首页 > 开发学院 > C/C++ >

霍夫曼编码中的解码问题

时间:2008-06-05 13:55:19 来源:论坛整理作者: 编辑:chinaitzhe

这个是霍夫曼编码的问题，要求输入只含有ABCD的四句话，且每句8个字符的长度，然后求出四个字符每个的概率，然后当成权值计算霍夫曼编码，我的这个程序已经实现了输入、概率统计、计算出霍夫曼编码存在了bian[]这个数组中，但是在解码出卡住了，都郁闷两天了，感觉越想就越糊涂，希望帮帮忙提供个思路：如何解码，就是把一堆0101翻译为原来的abcd的字符编码，最好是根据我的这个程序提出一些方法，另外本人初学数据结构，希望讲解的通俗一点点，谢谢！！

C/C code






Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/





#include "stdio.h" 

#include "stdlib.h"

#include "string.h"



typedef struct

{ 

   char elem;

   float m_weight; 

   int parent,lchild,rchild; 

}HTNode,*HuffmanTree; 



typedef char** HuffmanCode; 

typedef struct weight

{

  char elem; 

  float m_weight; 

}Weight;



void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int); 

void Select(HuffmanTree,int,int *,int *);



main() 

{

  HuffmanTree HT; 

  HuffmanCode HC; 

  Weight *w; 

  int i,j,n=4,a_len,b_len,c_len,d_len,m,k=0;

  char x[4][8],bian[30],jie[8],a[4],temp[4],fan[3],shou[8],tem[4];

  for(i=0;i<=30;i  )

      bian[i]='\0';

  float tj[4]={0,0,0,0};

  w=(Weight *)malloc(n*sizeof(Weight)); 

  w[1].elem='a';

  w[2].elem='b';

  w[3].elem='c';

  w[4].elem='d';

  printf("请输入4句字符编码,要求仅含有a,b,c,d四个字符,而且每个字符编码限8个字符\n");

  for(i=0;i<4;i  )

  {

    for(j=0;j<8;j  )

        scanf("%c",&x[i][j]);

    getchar();/*用于接收每行输入完之后输入的回车*/

  }

  for(i=0;i<4;i  )/*统计abcd的个数*/

    for(j=0;j<8;j  )

    {

        switch(x[i][j])

        {

        case 'a':

            tj[0]  ;

            break;

        case 'b':

            tj[1]  ;

            break;

        case 'c':

            tj[2]  ;

            break;

        case 'd':

            tj[3]  ;

            break;

        }

    }

    printf("经统计,刚输入的字符编码中\na为%f个,b为%f个,c为%f个,d为%f个\n",tj[0],tj[1],tj[2],tj[3]);

    for(i=0;i<4;i  )/*求出abcd的概率并存入数组tj[4]中*/

        tj[i]=tj[i]/32;

    printf("概率依次为\n%f\n%f\n%f\n%f\n",tj[0],tj[1],tj[2],tj[3]);

    for(i=0;i<4;i  )

        w[i].m_weight=tj[i];

    HuffmanCoding(&HT,&HC,w,n);

    for(i=1;i<=4;i  )

    {

        printf("第%d个字符为",i);

        printf("%s\n",HC[i]);

    }

    printf("请输入你要发送的一句字符\n");

    scanf("%d",&i);

    for(j=0;j<8;j  )

    {

        switch(x[i-1][j])

        {

        case 'a':

            strcat(bian,HC[1]);

            break;

        case 'b':

            strcat(bian,HC[2]);

            break;

        case 'c':

            strcat(bian,HC[3]);

            break;

        case 'd':

            strcat(bian,HC[4]);

            break;

        }

    }

    printf("%s\n",bian);/*此字符串中存放的就为要发送的编码*/

    a_len=strlen(HC[1]);

    b_len=strlen(HC[2]);

    c_len=strlen(HC[3]);

    d_len=strlen(HC[4]);

    printf("a的长度为%d,b为%d,c为%d,d为%d\n",a_len,b_len,c_len,d_len);

    printf("要发送的编码长度为%d\n",strlen(bian)); 



    ×××××××××××××××××× 

    printf("收到的编码信息为\n");

    for(i=0;i<8;i  )

    {

        printf("%c",shou[i]);

    }

}



void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)

{ 

    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(i=1;i<=n;  i)

    { 

       (*HT)[i].elem=w[i-1].elem; 

       (*HT)[i].m_weight=w[i-1].m_weight; 

       (*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; 

    } 



    for(;i<=m;  i)

    { 

        (*HT)[i].elem='0'; 

        (*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].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].m_weight=(*HT)[s1].m_weight (*HT)[s2].m_weight; 

    } 

  

    (*HC)=(HuffmanCode)malloc(n*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]);

    } 

} 



void Select(HuffmanTree HT,int n,int *s1,int *s2) 

{ 

  int i; 

  (*s1)=(*s2)=0; 

  for(i=1;i<=n;i  )

  { 

    if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)

    { 

      if(HT[i].m_weight<HT[(*s1)].m_weight)

      { 

          (*s2)=(*s1); 

          (*s1)=i; 

      } 

      else (*s2)=i; 

    } 

    if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)

    { 

      if((*s1)==0) (*s1)=i; 

      else if((*s2)==0)

      { 

          if(HT[i].m_weight<HT[(*s1)].m_weight)

          { 

              (*s2)=(*s1); 

              (*s1)=i; 

          } 

          else (*s2)=i; 

      } // end of else if 

    } // end of if 

  } // end of for 

  if((*s1)>(*s2))

  { 

      i=(*s1);

      (*s1)=(*s2);

      (*s2)=i;

  } 

  return; 

}

网友回复:编码和解码正好是两个相反的过程，
编码是根据权值生成树，解码就是得到生成树根据权值还原其原有的编码
lz能把编码写出来，解码就应该也能写出来才对萨
网友回复:你要建立一个表 - 保存字符概率表
解码根据权值算出所有编码的概率大小
字符概率表比较得出解码
网友回复:我以前写过，现在帮你改改，等下给你贴代码，记得结贴给分哟
网友回复:昨天有事出去了
想在你的代码上改，不过很痛苦，我讲一下思路好了
for(i=0;i <=30;i )
bian[i]='\0';
数组越界了，危险

w=(Weight *)malloc(n*sizeof(Weight));
w[1].elem='a';
w[2].elem='b';
w[3].elem='c';
w[4].elem='d';
下标似乎要从0开始

printf("请输入你要发送的一句字符\n");
scanf("%d",&i);
输入一句字符，似乎要用
fgets()
或者getline()
至少也是scanf("%s",、、)

解码的思路：
例如：1000101010，赫夫曼编码，每一个编码值，都不会是其他编码的前缀，所以，可以按照以下方法查找
首先获取1，去编码的里面找1，是不是编码
假如不是的话，再找个一个位，加上之前的，合起来成为10，查找是不是编码，是就翻译出来，翻译之后，从下一个开找
不是继续寻找，
直到全部翻译完

网友回复:大哥，怎么这样啊？？在main函数里，我看到你打印的shou这个数组，在main里，总共就出现了两次：

C/C code






Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/







char x[4][8],bian[30],jie[8],a[4],temp[4],fan[3],shou[8],tem[4];







    for(i=0;i<8;i  )

        {

            printf("%c",shou[i]);

        }

这不出错才怪呢！
网友回复:同意4楼，

建议写个函数，参数char* key，

功能为，在编码表内按“对key的前缀相似”方式搜索
（抱歉引号内说的挺别扭，一时难以用合适的词表示这个意思）
然后，函数返回查到的结果数。

网友回复:是这样的
我的代码中间有一段“××××××××”
那段表示解码过程
不过没写好呢
写完就能打印出来了
网友回复:很痛苦？？
不能吧，感觉写的挺通俗的，就我这水平想故作高深都难啊
printf("请输入你要发送的一句字符\n");
scanf("%d",&i);
这个是要输入原先输入的四句话中的一句的序号，没写清楚，sorry
另外你的这个思路很好，我试着完善一下程序
关于分的问题你不着急吧，呵呵，不懂的地方再问你，谢谢大哥

关键字：霍夫曼,编码,解码,问题,

网友评论加入收藏错误报告论坛讨论关闭此页

上一篇：帮忙改正一下霍夫曼解码算法

下一篇：下面没有链接了

·帮忙改正一下霍夫曼解码算法 (2008-06-05)

·java可以解析含有不同分隔符的字 (2008-06-05)

·ASM投资3000万美元在成都设半导体 (2008-06-05)

·初学C ，编译同一个程序，对VC6 (2008-06-05)

·一道acm题目，有爱好的过来说说看 (2008-06-05)

·用C语言储存BMP文件 (2008-06-05)

·用C语言读取BMP文件的像素数据 (2008-06-05)

·用C写的轮廓跟踪实现的代码 (2008-06-05)