| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2707 人关注过本帖, 1 人收藏
标题:求助赫夫曼树编码的问题
取消只看楼主 加入收藏
sala0127
Rank: 2
等 级:论坛游民
帖 子:56
专家分:52
注 册:2011-11-8
结帖率:85.71%
收藏(1)
已结贴  问题点数:40 回复次数:4 
求助赫夫曼树编码的问题
程序是模仿严慧敏数据结构算法6.12和算法6.13的思路写的。程序执行后会无响应报错退出,于是调试了几次,只发现了cdlen的值会被减到负数,目前发现会减到-1和-2,请大家帮忙看下哪里出问题了,谢谢。
程序代码:
#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef struct
{
    int weight;
    int parent,lchild,rchild;
}htnode,*huffmantree;

void select(huffmantree &HT,int n,int &s1,int &s2)
{
    int i;
    int min_weight=65536;
    for(i=0;i<n;i++)
    {
        if(HT[i].parent==0)
        {
            if(HT[i].weight<min_weight)
            {
                min_weight=HT[i].weight;
                s1=i;
            }
        }
    }
    HT[s1].parent=1;
    min_weight=65536;
    for(i=0;i<n;i++)
    {
        if(HT[i].parent==0)
        {
            if(HT[i].weight<min_weight)
            {
                min_weight=HT[i].weight;
                s2=i;
            }
        }
    }
    HT[s2].parent=1;
}


void huffmancoding(huffmantree &HT,char ** &HC,int *w,int n)
{
    //构造赫夫曼树
    int i;
    int m=2*n-1;
    int s1,s2;
    huffmantree t;
    HT=t=(huffmantree)malloc((m+1)*sizeof(htnode));
    if(!HT) return;
    for(i=1;i<=n;i++,w++,t++)
    {
        (*t).weight=*w;
        (*t).parent=0;
        (*t).lchild=0;
        (*t).rchild=0;
    }
    for(;i<=m;i++,t++)
    {
        t->weight=0;
        t->parent=0;
        t->lchild=0;
        t->rchild=0;
    }
    for(i=n;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=(char **)malloc((n+1)*sizeof(char *));
    char cd[1000];
    int p=m-1,cdlen=0,flag=0;
    for(i=0;i<m;i++) HT[i].weight=0;
    while(1)
    {
        if(HT[p].weight==0)
        {
            HT[p].weight=1;
            if(HT[p].lchild!=0)
            {
                p=HT[p].lchild;
                cd[cdlen++]='0';
            }
            else if(HT[p].rchild==0)
            {
                HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
                if(!HC[p]) return;
                cd[cdlen]='\0';
                strcpy(HC[p],cd);
                flag++;
                if(flag==n) break;
            }
        }
        else if(HT[p].weight==1)
        {
            HT[p].weight=2;
            if(HT[p].rchild!=0)
            {
                p=HT[p].rchild;
                cd[cdlen++]='1';
            }

        }
        else if(HT[p].weight==2)
        {
            HT[p].weight=0;
            p=HT[p].parent;
            cdlen--;
        }
    }
}

void main()
{
    int n,i;
    int *w,*p;
    huffmantree HT;
    char ** HC;
    printf("请输入待编码字符数n<n大于0>:");
    scanf("%d",&n);
    printf("\n");
    p=w=(int *)malloc(n*sizeof(char));
    if(!w) return;
    printf("请输入待编码字符:\n");
    for(i=1;i<=n;i++) scanf("%d",w++);
    huffmancoding(HT,HC,p,n);
    for(i=0;i<n;i++) printf("%s\n",HC[i]);
}

2012-08-09 10:30
sala0127
Rank: 2
等 级:论坛游民
帖 子:56
专家分:52
注 册:2011-11-8
收藏
得分:0 
没人帮忙么。。难道是分太少了么。。。
2012-08-09 14:39
sala0127
Rank: 2
等 级:论坛游民
帖 子:56
专家分:52
注 册:2011-11-8
收藏
得分:0 
回复 5楼 zanzan1986
注释因为我觉得是按书本的算法思路写的,所以贪方便就没写。作用是用最优二叉树把一串字符或者数字换成最短的二进制密码,要求为前缀编码
2012-08-10 16:19
sala0127
Rank: 2
等 级:论坛游民
帖 子:56
专家分:52
注 册:2011-11-8
收藏
得分:0 
自己终于弄明白了。。。。原来是书上的节点是从1开始的,0代表没有双亲节点或孩子节点,而我把算法改成节点从0开始的,而程序中还是把0作为判断有没有双亲节点或孩子节点的标准,而实际上0是其中一个节点的左孩子。。。所以结果出错了。。要把判断节点是否有双亲节点或孩子节点的值改掉,不能用0。。。。

对于初学者来说数据结构好麻烦。。。它可以是一种存储上的物理结构也可以是一种算法处理,思路上的结构,例如回溯法,分支试探是树的思想但不一定用树来存储。。。而后面那种的话对于我这种初学者来说比较抽象啊。。。

[ 本帖最后由 sala0127 于 2012-8-10 19:26 编辑 ]
2012-08-10 17:07
sala0127
Rank: 2
等 级:论坛游民
帖 子:56
专家分:52
注 册:2011-11-8
收藏
得分:0 
嗯,散分了
2012-08-11 01:24
快速回复:求助赫夫曼树编码的问题
数据加载中...
 
   



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

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