| 网站首页 | 业界新闻 | 群组 | 人才 | 技术文章 | 下载频道 | 博客 | 代码贴 | 编程论坛
绝地游戏外挂辅助教学千里之行 始于足下
共有 144 人关注过本帖
标题:哈夫曼树译码的判断条件问题
只看楼主 收藏
axxhn
Rank: 1
等 级:新手上路
帖 子:26
专家分:0
注 册:2017-6-4
结帖率:50%
  问题点数:20  回复次数:5   
哈夫曼树译码的判断条件问题
本来的想法是如果输入的哈夫曼编码和上面储存的完全匹配则输出对应的原字符,但是现在弄不出来,不知道是什么原因,希望有大神来给我看看问题在哪
程序代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXBIT 10//每个字符编码的最大长度
#define MAXVALUE 1000//哈夫曼树中叶子结点的最大权值
#define MAXSIZE 26//电文中出现的字符种类的最大值
typedef struct HNode//定义哈夫曼树的结点结构
{
    int weight;
    int parent,lchild,rchild;
}HNode,*HTree;
typedef char **HCode;//哈夫曼编码
//统计电文中的字符种类及每种字符出现的次数
int Count(char *s,int cnt[],char str[])
{
    //*s指向电文字符串,cnt存储电文中字符出现的次数,str存储电文中出现的字符
    char *p;
    int i,j,k;
    int temp[26];//temp是临时数组,用于统计每个字符出现的次数
    for(i=0;i<26;i++)
    temp[i]=0;
    for(p=s;*p!='\0';p++)//统计各种字符出现的次数
        if(*p>='A'&&*p<='Z')
        {
            k=(*p)-65;
            temp[k]++;
        }
    for(i=0,j=0;i<26;i++)//统计电文中出现的字符
        if(temp[i]!=0)
        {
            str[j]=i+65;//将出现的字符存入字符数组
            cnt[j]=temp[i];//相应字符出现的次数作为该字符的权值存储到cn  
            j++;
        }
    str[j]='\0';
    return j;//返回电文中字符的种类,即哈夫曼树种叶子结点个数     
}
//构造哈夫曼树并生成叶子结点的前缀编码
void HuffmanCoding(HTree *HT,HCode *HC,int *w,int n)
{
    //w存储n个字符的权值,构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
    int m;//哈夫曼树中结点的个数
    int m1,m2,x1,x2;//m1、m2存储两个最小权值,x1、x2存储对应的下标
    int i,j,start;
    char *cd;
    int c,f;
    HNode *p;
    if(n<=1)
    return;
    //哈夫曼树的构造
    m=2*n-1;
    *HT=(HNode *)malloc(m*sizeof(HNode));
    for(p=*HT,i=0;i<n;++i,++p,++w)//初始化叶子结点信息
    {
        p->weight=*w;
        p->lchild=-1;
        p->rchild=-1;
        p->parent=-1;
    }
    for(;i<m;++i,++p)//初始化分支结点信息
    {
        p->weight=0;
        p->lchild=-1;
        p->rchild=-1;
        p->parent=-1;
    }
    for(i=n;i<m;++i)//构造哈夫曼树
    {
        m1=m2=MAXVALUE;
        x1=x2=0;
        for(j=0;j<i;++j)//寻找parent为-1且权值最小的两棵子树
        {
            if((*HT)[j].parent==-1&&(*HT)[j].weight<m1)
            {
                m2=m1;
                x2=x1;
                m1=(*HT)[j].weight;
                x1=j;
            }
            else if((*HT)[j].parent==-1&&(*HT)[j].weight<m2)
            {
                m2=(*HT)[j].weight;
                x2=j;
            }
        }
        //合并成一棵新的子树
        (*HT)[x1].parent=i;
        (*HT)[x2].parent=i;
        (*HT)[i].lchild=x1;
        (*HT)[i].rchild=x2;
        (*HT)[i].weight=m1+m2;
    }
    *HC=(HCode)malloc(n*sizeof(char *));
    cd=(char *)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(i=0;i<n;++i)
    {
        start=n-1;
        for(c=i,f=(*HT)[i].parent;    f!=-1;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[i]
    }
    free(cd);
}
void HuffmanDecoding(HCode HC,HTree *HT,char str[],int n)
{
    int i,j=0;
    char b[MAXSIZE];
    int m=2*n-1;
    i=m-1; //从根结点开始往下搜索
    printf("输入发送的编码(以'#'为结束标志):");
    gets(b);
    printf("译码后的字符为");
    while(b[j]!='#')
    {
        if(b[j]=='0')
        i=(*HT)[i].lchild; //走向左孩子
        else
        i=(*HT)[i].rchild; //走向右孩子
        if(strcmp(HC[j],b)==0)
        {
            printf("%c",str[i]);
            i=m-1;//回到根结点
        }
        j++;
         
    }
}
void Print(HCode HC,char str[],int cn[],int n)//输出电文中每个字符出现的次数及其前缀编码
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%c出现%d次,编码是:",str[i],cn[i]);
        puts(HC[i]);
        putchar('\n');
    }
    return;   
}  

main()
{
    char st[254],*s,str[26];
    int cn[26];
    int num;
    HNode *HT;
    HCode HC;
    printf("输入需要编码的大写英文字母字符串:\n");
    gets(st);
    num=Count(st,cn,str);
    HuffmanCoding(&HT,&HC,cn,num);
    Print(HC,str,cn,num);
    HuffmanDecoding(HC,&HT,str,num);
}
5 天前 16:30
axxhn
Rank: 1
等 级:新手上路
帖 子:26
专家分:0
注 册:2017-6-4
  得分:0 
顶上去
5 天前 19:49
axxhn
Rank: 1
等 级:新手上路
帖 子:26
专家分:0
注 册:2017-6-4
  得分:0 

@九转星河,版主能帮我看看吗
4 天前 18:44
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:25
帖 子:3974
专家分:11322
注 册:2016-10-22
  得分:0 
回复 3楼 axxhn
以下是引用axxhn在2017-12-8 18:44:10的发言:


@九转星河,版主能帮我看看吗



我可以说我技术有限,这个是我的盲点~
只能建议你去数据结构版块用搜索功能搜搜有关的帖子自己对比一下或者上网搜搜资料~

[code]/*~告诫自己:不要为了细微的效率差别而牺牲可读性!~2017-11-07更~*/[/code]
4 天前 20:24
axxhn
Rank: 1
等 级:新手上路
帖 子:26
专家分:0
注 册:2017-6-4
  得分:0 
回复 4楼 九转星河
好吧
4 天前 20:42
Jonny0201
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:90
专家分:139
注 册:2016-11-7
  得分:0 
代码太长,因为我懒,所以。。。懒得看。。
你是说 Huffman 编码,然后在结构体或者类数组里找,找到之后输出对应的字符,这个理解对吗?
如果是上面的理解的话,我建议你在建立结构里数组之后,对编码进行补 0 操作,补到 8 位
也就是原来 001 的补成 00100000,Huffman 代码是前面三位,只要读取前面三位就可以了
因为 Huffman 编码本身的特性,是独一无二的,所以不可能出现读取到 001 之后后面还有 0011 这种情况,肯定都是 01 开头的
对于用户输入的 Huffman 编码,同样进行补 0 操作
我当时就是这么写的,不知道各位大神还有什么好的方法
写 Huffman 编码有一段时间了,上面可能有错误的说明,欢迎指出
前天 01:50







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

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