bill1829
bill1829
采纳率0%
2015-04-28 14:58 浏览 1.8k

哈夫曼树运行错误 但调试却正确 一直找不成错误

估计问题是出在HuffmanCoding 但怎么都找不出来

 #include "stdio.h"
#include "stdlib.h"
#include "string.h"
char alphabet[]={'A','B','C','D'};
typedef struct 
{
    int weight;     //权值 
    int parent;     //父节点序号 
    int left ;
    int right;
}HuffmanTree;

typedef char *HuffmanCode;  //Huffman编码指针 
void SelectNode (HuffmanTree *ht,int n,int *bt1,int *bt2)
//从n个节点中选择parent节点为0,权重最小的两个节点 
{
    int i;
    HuffmanTree *ht1,*ht2,*t;
    ht1=ht2=NULL;
    for(i=1;i<=n;i++)
    {
        if(!ht[i].parent)               //父节点为空 
        {
            if(ht1==NULL)   
            {
                ht1=ht+i;               // 
                continue;
            }
            if(ht2==NULL)
            {
                ht2=ht+i;
                if(ht1->weight>ht2->weight)
                {
                    t=ht2;
                    ht2=ht1;
                    ht1=t;          //让ht1指向最小节点 ht2指向第二小 
                }
                continue;
            }
            if(ht1 &&ht2)
            {
                if(ht[i].weight<=ht1->weight)
                {
                    ht2=ht1;                    //如果还有比ht1更小的则把ht1赋给ht2 ,ht1继续等于最小 
                    ht1=ht+i;
                }
                else if(ht[i].weight<ht2->weight){
                    ht2=ht+i;                       //没有比ht1更小的 但有比ht2小的 
                }
            }
        }
    } 
    if(ht1>ht2){                    //按数组最初的位置排序 
        *bt2=ht1-ht;
        *bt1=ht2-ht;
    }
    else
    {
        *bt1=ht1-ht;
        *bt2=ht2-ht;
    }
}
void CreateTree(HuffmanTree *ht,int n,int *w)
{
    int i,m=2*n-1;    //总节点数 
    int bt1,bt2;
    if(n<=1)
        return ;
    for(i=1;i<=n;++i)
    {
        ht[i].weight=w[i-1];
        ht[i].parent=0;
        ht[i].left=0;
        ht[i].right=0;
    } 
    for(;i<=m;++i)
    {
        ht[i].weight=0;
        ht[i].parent=0;
        ht[i].left=0;
        ht[i].right=0;
    }
    for(i=n+1;i<=m;++i)
    {
        SelectNode(ht,i-1,&bt1,&bt2);
        ht[bt1].parent=i;
        ht[bt2].parent=i;
        ht[i].left=bt1;
        ht[i].right=bt2;
        ht[i].weight=ht[bt1].weight+ht[bt2].weight;  
    }
}


void HuffmanCoding(HuffmanTree *ht,int n,HuffmanCode *hc)
{
    char *cd;
    int start,i;
    int current,parent;
    cd=(char*)malloc(sizeof(char)*n);
    cd[n-1]='\0';
    for(i=1;i<=n;i++)
    {
        start=n-1;                      
        current=i;                          //获得当前节点序号 
        parent=ht[current].parent;          //获得当前节点父亲的序号 
        while(parent)           //当父节点不为空 
        {
            if(current==ht[parent].left)    //若当前节点是父亲的左节点 
                cd[--start]='0';            //字符最后编码为0 注意这个编码是逆序的 最后其实根节点 
            else
                cd[--start]='1';
            current=parent;                 //从当前节点向根节点寻找 
            parent=ht[parent].parent;
        }
        hc[i-1]=(char*)malloc(sizeof(char*)*(n-start)); //分配保存编码的内存 
        strcpy(hc[i-1],&cd[start]);                     //复制生成的编码 
    }
    free(cd);
} 

void Encode(HuffmanCode *hc,char *alphabet,char *str,char *code)
{
    int len=0,i=0,j;
    code[0]='\0';
    while(str[i])
    {
        j=0;
        while(alphabet[j]!=str[i])   //搜索字母在编码表的位置 
            j++;
        strcpy(code+len,hc[j]);     //字母在叶节点的编号到根节点的编号全部复制给code 
        len=len+strlen(hc[j]);      // 扩大len的长度(也就是节点深度) 
        i++;                    
    }
    code[len]='\0';
}

void Decode(HuffmanTree *ht,int m,char *code,char *alphabet,char *decode)//解码 
{
    int position=0,i,j=0;
    m=2*m-1;
    while(code[position])
    {
        for(i=m;ht[i].left &&ht[i].right;position++ )   
        {   
            if(code[position]=='0')             
                i=ht[i].left;               
            else
                i=ht[i].right;
        }
        decode[j]=alphabet[i-1];
        j++;
    }   
    decode[j]='\0';
}
int main()
{
    int i,n=4,m;
    char test[]="DBDBDABDCDADBDADBDADACDBDBD";
    char code[100],code1[100];

    int w[]={5,7,2,13};
    HuffmanTree *ht;
    HuffmanCode *hc;
    m=2*n-1;
    ht=(HuffmanTree *)malloc((m+1)*sizeof(HuffmanTree));
    if(!ht)
    {
        printf("分配内存失败\n");
        exit(0);
    }
    CreateTree(ht,n,w);
    HuffmanCoding(ht,n,hc);
    for(i=1;i<=n;i++)
        printf("字母:%c,权重:%d,编码:%s\n",alphabet[i-1],ht[i].weight,hc[i-1]);
    Encode(hc,alphabet,test,code);
    printf("\n字符串:\n%s\n转换后:\n%s\n",test,code);
    Decode(ht,n,code,alphabet,code1);
    printf("\n编码:\n%s\n转换后:\n%s\n",code,code1);

    return 0;
} 
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

3条回答 默认 最新

  • gsky1986 foreach_break 2015-04-28 15:13

    我帮你看看~~~~~~~~~~~~·

    点赞 评论 复制链接分享
  • gsky1986 foreach_break 2015-04-28 16:29

    简单帮你修改了下。请采纳!

    #include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    char alphabet[]={'A','B','C','D'};
    typedef struct 
    {
        int weight;     //权值 
        int parent;     //父节点序号 
        int left ;
        int right;
    }HuffmanTree;
    
    typedef char *HuffmanCode;  //Huffman编码指针 
    void SelectNode (HuffmanTree *ht,int n,int *bt1,int *bt2)
    //从n个节点中选择parent节点为0,权重最小的两个节点 
    {
        int i;
        HuffmanTree *ht1,*ht2,*t;
        ht1=ht2=NULL;
        for(i=1;i<=n;i++)
        {
            if(!ht[i].parent)               //父节点为空 
            {
                if(ht1==NULL)   
                {
                    ht1=ht+i;               // 
                    continue;
                }
                if(ht2==NULL)
                {
                    ht2=ht+i;
                    if(ht1->weight>ht2->weight)
                    {
                        t=ht2;
                        ht2=ht1;
                        ht1=t;          //让ht1指向最小节点 ht2指向第二小 
                    }
                    continue;
                }
                if(ht1 &&ht2)
                {
                    if(ht[i].weight<=ht1->weight)
                    {
                        ht2=ht1;                    //如果还有比ht1更小的则把ht1赋给ht2 ,ht1继续等于最小 
                        ht1=ht+i;
                    }
                    else if(ht[i].weight<ht2->weight){
                        ht2=ht+i;                       //没有比ht1更小的 但有比ht2小的 
                    }
                }
            }
        } 
        if(ht1>ht2){                    //按数组最初的位置排序 
            *bt2=ht1-ht;
            *bt1=ht2-ht;
        }
        else
        {
            *bt1=ht1-ht;
            *bt2=ht2-ht;
        }
    }
    void CreateTree(HuffmanTree *ht,int n,int *w)
    {
        int i,m=2*n-1;    //总节点数 
        int bt1,bt2;
        if(n<=1)
            return ;
        for(i=1;i<=n;++i)
        {
            ht[i].weight=w[i-1];
            ht[i].parent=0;
            ht[i].left=0;
            ht[i].right=0;
        } 
        for(;i<=m;++i)
        {
            ht[i].weight=0;
            ht[i].parent=0;
            ht[i].left=0;
            ht[i].right=0;
        }
        for(i=n+1;i<=m;++i)
        {
            SelectNode(ht,i-1,&bt1,&bt2);
            ht[bt1].parent=i;
            ht[bt2].parent=i;
            ht[i].left=bt1;
            ht[i].right=bt2;
            ht[i].weight=ht[bt1].weight+ht[bt2].weight;  
        }
    }
    
    
    void HuffmanCoding(HuffmanTree *ht,int n,HuffmanCode *hc)
    {
        char *cd;
        int start,i;
        int current,parent;
        cd=(char*)malloc(sizeof(char)*n);
        cd[n-1]='\0';
        for(i=1;i<=n;i++)
        {
            start=n-1;                      
            current=i;                          //获得当前节点序号 
            parent=ht[current].parent;          //获得当前节点父亲的序号 
            while(parent)           //当父节点不为空 
            {
                if(current==ht[parent].left)    //若当前节点是父亲的左节点 
                    cd[--start]='0';            //字符最后编码为0 注意这个编码是逆序的 最后其实根节点 
                else
                    cd[--start]='1';
                current=parent;                 //从当前节点向根节点寻找 
                parent=ht[parent].parent;
            }
    
            hc[i-1]=(char*)malloc(sizeof(char)*(n-start)); //分配保存编码的内存 
            strcpy(hc[i-1],&cd[start]);                     //复制生成的编码 
        }
        free(cd);
    } 
    
    void Encode(HuffmanCode *hc,char *alphabet,char *str,char *code)
    {
        int len=0,i=0,j;
        code[0]='\0';
        while(str[i])
        {
            j=0;
            while(alphabet[j]!=str[i])   //搜索字母在编码表的位置 
                j++;
            strcpy(code+len,hc[j]);     //字母在叶节点的编号到根节点的编号全部复制给code 
            len=len+strlen(hc[j]);      // 扩大len的长度(也就是节点深度) 
            i++;                    
        }
        code[len]='\0';
    }
    
    void Decode(HuffmanTree *ht,int m,char *code,char *alphabet,char *decode)//解码 
    {
        int position=0,i,j=0;
        m=2*m-1;
        while(code[position])
        {
            for(i=m;ht[i].left &&ht[i].right;position++ )   
            {   
                if(code[position]=='0')             
                    i=ht[i].left;               
                else
                    i=ht[i].right;
            }
            decode[j]=alphabet[i-1];
            j++;
        }   
        decode[j]='\0';
    }
    int main()
    {
        int i,n=4,m;
        char test[]="DBDBDABDCDADBDADBDADACDBDBD";
        char code[100],code1[100];
    
        int w[]={5,7,2,13};
        HuffmanTree *ht;
        HuffmanCode *hc;
        m=2*n-1;
        ht=(HuffmanTree *)malloc((m+1)*sizeof(HuffmanTree));
        hc=(HuffmanCode *)malloc((n+1)*sizeof(HuffmanCode));
        if(!ht)
        {
            printf("分配内存失败\n");
            exit(0);
        }
        CreateTree(ht,n,w);
        HuffmanCoding(ht,n,hc);
        for(i=1;i<=n;i++)
            printf("字母:%c,权重:%d,编码:%s\n",alphabet[i-1],ht[i].weight,hc[i-1]);
        Encode(hc,alphabet,test,code);
        printf("\n字符串:\n%s\n转换后:\n%s\n",test,code);
        Decode(ht,n,code,alphabet,code1);
        printf("\n编码:\n%s\n转换后:\n%s\n",code,code1);
        free(hc);
        hc = NULL;
        free(ht);
        ht = NULL;
        return 0;
    } 
    
    点赞 评论 复制链接分享
  • gsky1986 foreach_break 2015-04-28 16:31

    图片说明

    点赞 评论 复制链接分享

相关推荐