| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
买学问 - 大牛一对一辅导,有问必答买学问 - 专业的付费知识问答平台
共有 593 人关注过本帖
标题:关于哈夫曼编码的问题求大神指教谢谢!
只看楼主 加入收藏
不要做咸鱼
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2018-3-5
结帖率:0
  已结贴   问题点数:20  回复次数:2   
关于哈夫曼编码的问题求大神指教谢谢!
哈夫曼树的创建应该是没有问题的错误在哈夫曼编码上,我的思路是从叶子到根逆求编码的话得到的编码是反着的,再创建一个数组然后该数组第一位等于求到的哈夫曼编码的最后一位,这样就可以把它倒过来了
代码如下:
#include <stdio.h>
#include <stdlib.h>
#define MAXCODE 100
#define MAXTREE 100
typedef struct{
    char data;
    int parent,lchild,rchild,weight;
    int code[MAXCODE];
}Huffman;

void Select(Huffman tree[],int i,int &s1,int &s2)//选择两个权值最小的叶子
{
    int j,m1=0,m2=0;
    for(j=0;j<i;j++){
        if(tree[j].parent==0){//寻找最小权值过程建立在没有父母的基础上
            if(m1==0){
                m1=tree[j].weight;//为第一小权值赋值
                s1=j;
            }
            else if(m2==0){//为第二小权值赋值
                if(m1>tree[j].weight){//如果该权值小于第一小权值那么这个给第一,第一给第二
                    m2=m1;
                    s2=s1;
                    m1=tree[j].weight;
                    s1=j;
                }
                else{
                    m2=tree[j].weight;
                    s2=j;
                }
            }
            else if(m1<tree[j].weight){//小权值跟后面的做比较
                if(m2>tree[j].weight){//若第一小小于该权值第二小大于那么第二小更换
                    m2=tree[j].weight;
                    s2=j;
                }
            }
            else{//如果一二均小于该权值那么第一给第二该权值给第一
                m2=m1;
                s2=s1;
                m1=tree[i].weight;
                s1=j;
            }
        }
    }
}
void HuffmanTree(Huffman tree[],int n)//构建哈夫曼树
{
    int i,s1,s2;
    //tree=(Huffman*)malloc((2*n)*sizeof(Huffman));
    for(i=0;i<=2*n-2;i++){
        tree[i].parent=0;
        tree[i].lchild=0;
        tree[i].rchild=0;
    }
    /*for(i=0;i<=n;i++){
        tree[i].weight=w[i];
    }*/
    for(i=n;i<2*n-1;i++){
        Select(tree,i,s1,s2);
        tree[s1].parent=tree[s2].parent=i;
        tree[i].lchild=s1;
        tree[i].rchild=s2;
        tree[i].weight=tree[s1].weight+tree[s2].weight;
    }
}
void HuffmanCoding(Huffman tree[],int n)//哈夫曼编码
{
    int f,c,j=1,i,q;
    for(i=0;i<n;i++){
        int cd[MAXCODE];
        cd[0]=9;
        for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent,j++){
            if(tree[f].lchild==c){
                cd[j]=0;
            }
            else{
                cd[j]=1;
            }
        }
        for(q=0;j>=0;j--,q++){
            tree[i].code[q]=cd[j];
        }
    }
}
int main()
{
    Huffman tree[MAXTREE];
    char c;
    int i=0,j,k;
    printf("enter some data:");
    c=getchar();
    while(c!='\n'){
        tree[i].data=c;
        i++;
        c=getchar();
    }
    printf("enter the weight:");
    for(j=0;j<i;j++){
        scanf("%d",&tree[j].weight);
    }
    HuffmanTree(tree,i);
    printf("printf the huffmantree:");
    for(j=0;j<2*i-1;j++){
        printf("%d ",tree[j].weight);
    }
    printf("\nprintf the huffmancoding:\n");
    HuffmanCoding(tree,i);
    for(j=0;j<i;j++){
        printf("%c ",tree[j].data);
        for(k=0;tree[j].code[k]!=9;k++){
            printf("%d",tree[j].code[k]);
        }
        printf("\n");
    }
    return 0;
}
2018-11-10 10:04
MeandC
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:8
帖 子:245
专家分:792
注 册:2018-7-14
  得分:20 
可不可以像非递归遍历二叉树一样把指向结点的指针用栈存起来。

C果然是有点难啊!
2018-11-11 13:07
不要做咸鱼
Rank: 1
等 级:新手上路
帖 子:12
专家分:0
注 册:2018-3-5
  得分:0 
回复 2楼 MeandC
啊谢谢我去试一试
2018-11-11 13:23







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

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