| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 317 人关注过本帖
标题:关于数据结构赫夫曼编译码器的问题,请高手指点下问题所在
只看楼主 加入收藏
aini5235180
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2012-12-15
结帖率:0
收藏
已结贴  问题点数:20 回复次数:1 
关于数据结构赫夫曼编译码器的问题,请高手指点下问题所在
#include <stdio.h>
#include<stdlib.h>
#include <malloc.h>
#include <string.h>
typedef struct
{
    char ch;
    int weight;
    int parent,lchild,rchild;
}HTnode,*Huffmantree;
typedef char **Huffmancode;       //动态分配数组存储赫夫曼编码表
int main()
{
//------------构造赫夫曼树及赫夫曼编码-------------------
    Huffmantree HT;
    Huffmancode HC;
    char *cd,s[10000],g[10000];
    int n,mm,m,i,j=0,f,start,c,s1=0,s2=0,temp1,temp2;char x;
    int w[97];
   
    int a[97]={0};
   
     printf("*********************欢迎使用同赫夫曼编译码器************************************************\n");
     printf("请选择要进行的操作:(注:要进行后续操作必须先选择第一项)\n");
     printf("A.初始化赫夫曼树\t\t B.编码\t\t C.译码\t\t\n");
     scanf("%c",&x);
     if(x=='A')
     {
         
                printf("请输入一段字符:");
            gets(s);
                n=strlen(s);
              /*for(i=0;s[i]!='\n';i++)
              {   
                  scanf("%c",&s[i]);
                  n++;
              }*/
              for(i=0;i<n;i++)
              a[s[i]-' ']++;
              for(i=0;i<97;i++)
              if(a[i]!=0)
              {
               w[j]=a[i];
               j++;
               }
            //w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
              n=j;
              m=2*n-1;
              HT=(Huffmantree )malloc((m+1)*sizeof(HTnode));//0号单元未用
              for(i=0,j=0;i<97;i++)
              if(a[i]!=0)
               {
                 HT[j+1].ch=i+' ';
                 j++;
                }
   
              for(i=1,j=0;i<=n;++i,++j)
                {
                   HT[i].weight=w[j];
                   HT[i].parent=HT[i].lchild=HT[i].rchild=0;
                  }      //n个叶子赋初值
              for(;i<=m;++i)
                   HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;    //除叶子外的节点赋初值

                  for(i=n+1;i<=m;i++)
                    {
                      //建赫夫曼树,在HT[1..i-1]选择parent为0且weight最小的两个节点,其序号为别为s1,s2.
                       temp1=temp2=1000;
                       for(j=1;j<=i-1;j++)
                       if(HT[j].parent==0)
                         if(HT[j].weight<temp1)
                           {
                              temp1=HT[j].weight;
                              s1=j;
                             }
                        for(j=1;j<=i-1;j++)
                        if(HT[j].parent==0&&j!=s1)
                          if(HT[j].weight<temp2)
                           {
                             temp2=HT[j].weight;
                             s2=j;
                            }
                        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;//父节点权值为左右两孩子权值之和
                         }
                       printf("num  weight lchild parent rchild    ch\n");
                       for(i=1;i<=m;i++)
                       printf("%-4d%4d%8d%8d%8d%6c\n",i,HT[i].weight,HT[i].lchild,HT[i].parent,HT[i].rchild,HT[i].ch);
                       
     }
                     
            if(x=='B')
        {//---------------从叶子到根逆向求每个字符的赫夫曼编码--------------------

                          HC=(Huffmancode)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量
                          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));  //为第i个字符编码分配空间
                         strcpy(HC[i],cd+start);     //从cd复制编码到HC
                             }
                         free(cd);  
                         printf("\nnum  bianma\n");
                         for(i=1;i<=n;i++)
                         printf("%c\t\t%s\n",HT[i].ch,HC[i]);
            }
            if(x=='C')
            {//--------------解码-----------------------------------------------------
                             printf("\n请输入一段0-1编码\n");
                             gets(g);
                             printf("\n解码后为:");
                             mm=m;
                             for(i=0;i<=(signed)strlen(g);)
                              {
                                  if(HT[mm].lchild==0&&HT[mm].rchild==0)
                                      {
                                         printf("%c",HT[mm].ch);
                                         mm=m;
                                        //continue;
                                        }
                                   else
                                    {
                                       if(g[i]=='0')
                                         {
                                            mm=HT[mm].lchild;
                                            i++;
                                           }
                                        else
                                          {
                                             mm=HT[mm].rchild;
                                             i++;
                                             }
                                       }
                                 }
                                 printf("\n");
            }
                  return 0;
}


请指导下我这个赫夫曼编译码器怎么了,我没加IF控制语句时候能运行,但是加了个IF语句后发觉好像里面包的那些函数被屏蔽了一样,失去了原来的效果。请高手指点下,我哪里出问题了,要怎么修改,尽可能小的变动我的源代码,谢谢!
搜索更多相关主题的帖子: 译码器 parent include 存储 结构 
2012-12-15 11:11
w527705090
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:11
帖 子:441
专家分:1882
注 册:2011-6-28
收藏
得分:20 
这也不是个小问题,霍夫曼编码这是要看算法的吧 。。。。
很多人不知道霍夫曼是什么呢
你先介绍下霍夫曼编码的原理

有心者,千方百计;无心者,千难万难。
2012-12-20 20:44
快速回复:关于数据结构赫夫曼编译码器的问题,请高手指点下问题所在
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.039133 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved