baidu_29435963
绿藻君的gps
采纳率50%
2015-12-04 11:37

赫夫曼树出错 ,编译没错 不知道哪里错了运行不了

10
已采纳

编译没有错误,运行失败


#include <stdio.h>
#include <stdlib.h>
#include <math.h> 
#include <string.h> 
#define STACK_INIT_SIZE 100//存储空间初始分配量  没分号“;” 
#define STACKINCREMENT 10 //存储空间分配增量

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1

typedef struct {
    unsigned int weight;
    unsigned int parent,lchild,rchild;  
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

//在HT[1..i-1]选择parent为0且weight最小的两个结点,
//其序号为最小s1和次小s2(若parent≠0,则说明被选取过不能再选)
//s1s2并不是指的weight权值,而是最(次)小的这个字符前面的编号(后面需要填进lchild、rchild)

void Select(HuffmanTree p,int n,int *s1,int *s2)
{
    int i;
    int min = 99999;
    for(i=1;i<=n;i++){
        if(p[i].parent == 0){
            if(p[i].weight <= min){
            min = p[i].weight;
            *s1 = i;
            }
        }   
    }
    min = 99999;
    for(i=1;i<=n;i++){
        if(p[i].parent==0){
            if(p[i].weight<=min && i!=*s1){
            min = p[i].weight;
            *s2 = i;
            }
        }   
    }   
}


void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n){
    //n字符 m节点 HT空间
    int m,i;
    HuffmanTree p;
    //int w[8] = {5,29,7,8,14,23,3,11};
    m = 2*n-1;
    if(n<=1){return;}   
    //加上一个未用的0号单元
    HT = (HuffmanTree *)malloc((m+1)*sizeof(HTNode)); 

    //一:初始化,得a图:
    //(1)把已有字符(1-8) 权重赋值w,左右孩子及parent赋值为0,p指向第二个单元(非0第一个) 
    for(p=*HT+1,i=1 ; i<=n ; ++i,++p,++w){//[问题p=HT+1?]看和鸿昌的聊天记录 
        //*p={*w,0,0,0};
        //错误原因: 赋值数组不能分着写
        //http://zhidao.baidu.com/link?url=jZOgI5PGVycg1v6c1pJ2AlDI3J6fiDLUQQ-1FkGjGzrXTE-hYQusYkoVQlM-EBhr3IjdF9d1wy-o_6elz6m2hald8u0LVM1EUzDaTZ6Rs7e
        (*p).weight = *w;
        (*p).parent = 0;
        (*p).lchild = 0;
        (*p).rchild = 0;
    }
    //(2)把未知字符(9-15) 权重、左右孩子及parent赋值为0, p指向上面跳出来的 未知字符的第一个 9
    for(;i<=m;++i,++p){
        (*p).weight = 0;
        (*p).parent = 0;
        (*p).lchild = 0;
        (*p).rchild = 0;    
    }

    //二:建立赫夫曼树,得到b图 
    //在HT[1..i-1]选择parent为0且weight最小的两个结点,其序号为最小s1和次小s2(若parent≠0,则说明被选取过不能再选)
    for(i=n+1;i<=m;++i){    //n+1 即后面未知字符 (比如9开始到15) 
    int s1,s2;
    //void Select(HuffmanTree HT,int q,int *s1,int *s2){
    Select(*HT,i-1,&s1,&s2);

    //select(*HT,i-1,&s1,&s2);

    //给s1 s2的parent赋值为当前i 编号 
    (*HT)[s1].parent = i;
    (*HT)[s2].parent = i;
    //给当前i 的lchild和rchild赋值为s1、s2编号 ,给当前i 的 weight赋值为二者权重之和
    //设最小的作左子树,次小的作右子树 
    (*HT)[i].lchild = s1;
    (*HT)[i].rchild = s2;
    (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    }

    //三:从叶子到根逆向求每个结点字符的赫夫曼编码 

    //存放赫夫曼编码的cd 
    char cd[n];
    int c,f;
    //分配n个字符编码的头指针向量HC 
    //HuffmanTree HC;报错类型:declaration of'HTNode* HC'shadows a parameter 原因:函数参数里已有HC的定义导致重复 
    HC = (HuffmanCode *)malloc((n+1)*sizeof(char *));
    //编码结束符  如声明cd[8],0-7中最后一个结束符则为cd[7] 
    cd[n-1] = '\0';//书上写错了,应该是'\0' 
    //1-8逐个求 
    for(i=1;i<=n;++i){
        //编码结束符位置 
        int start = n-1;
        //c=i,f指向当前字 符i的双亲 双亲不为0则循环 经过循环一次后,当前字符变成它的双亲,以此逆向递推 
        //小细节:--start  如图 
        for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent){
            if((*HT)[f].lchild ==c){
            cd[--start]='0';//书上写错了,应该是单引号'0' 
            }else{
            cd[--start]='1';
            }
            //for循环结束后,得到cd,为第i个字符分配存储空间HC
            (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
            //start目前指到最前面了,所以将cd复制(strcpy)给HC 
            /*原型声明:char *strcpy(char* dest, const char *src);
                头文件:#include <string.h> 和 #include <stdio.h>
                功能:把从src地址开始且含有NULL结束符的字符串复制到以dest开始的地址空间*/
            strcpy((*HC)[i],&cd[start]);
        }
    }
    free(cd);
}




int main(void){
   HuffmanTree HT;
   HuffmanCode HC;
   int n;
   printf("请输入字符个数(空格间隔):");
   scanf("%d",&n);

   int i; 
   int *w=NULL;
   w=(int*)malloc(n*sizeof(int));
   printf("请依次输入权值(空格间隔):");
   for(i=0;i<n;i++){
      scanf("%d",w+i);
   }

   HuffmanCoding(&HT,&HC,w,n);
   for(i=1;i<=n;i++){ 
   puts(HC[i]);//???
   } 
}

已解决。。。

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

3条回答

  • qq_27183003 ysuwood 6年前

    你用写的?
    char cd[n];
    这句能通过编译?怎么可能?

    点赞 评论 复制链接分享
  • qq_27183003 ysuwood 6年前

    对照一下,你的代码有一下错误。
    http://blog.csdn.net/xlgen157387/article/details/22168785

    点赞 评论 复制链接分享
  • Quack_quack Quack_quack 6年前

    写得好长。。不想看了。。
    题目描述
    输入N个整数表示N个叶节点权值,构造一棵最优二叉树,从左向右输出每个叶节点的哈夫曼编码。
    输入
    第1行:1个整数N(N≤50)第2行:N个空格分开的整数
    输出
    共N行,每行表示1个叶节点的编码。
    样例输入
    3
    1 2 4
    样例输出
    00
    01
    1

    #include
    #include
    #include
    #include
    using namespace std;
    int n;
    string op="";
    struct tree{
    int left,right,val,father;
    }point[110];
    bool compare(tree a,tree b)
    {
    return a.val<=b.val;
    }
    void rls(int x,string s)
    {
    if(x!=0)
    {
    if(point[point[x].father].left==x)s=s+'0';
    else if(point[point[x].father].right==x)s=s+'1';
    if(!point[x].left)cout< rls(point[x].left,s);
    rls(point[x].right,s);
    }
    }
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>point[i].val;
    sort(point+1,point+n+1,compare);
    int x=1,k=n;
    if(x==k){cout<<'0';return 0;}
    while(x<k)
    {
    point[++k].val=point[x].val+point[x+1].val;
    point[k].left=x;
    point[k].right=x+1;
    x+=2;
    sort(point+x,point+k+1,compare);
    }
    for(int i=1;i<=2*n-1;i++)
    {
    if(point[i].left){point[point[i].left].father=i;}
    if(point[i].right){point[point[i].right].father=i;}
    }
    for(int i=1;i<=2*n-1;i++)
    if(point[i].father==0){rls(i,op);break;}
    }

    
    
    点赞 评论 复制链接分享

相关推荐