回 帖 发 新 帖 刷新版面

主题:请帮我解释一下这个程序的意思!谢谢各位!

[em18] 这是创建哈夫曼树还有哈夫曼编码的一个程序 但是很多地方自己看不懂 请各位帮忙看看解释一下 谢谢了[em2]   麻烦各位拉
#include <stdio.h>
#define MAX  1000
#define MAXSYMBS 30  (请问一下这是不是编码的最大位数)
#define MAXNODE 59   (请问一下这是不是初始的最大的结点数)

typedef struct
{
  int weight;   (是不是权值)
  int flag;     (看不懂)
  int parent;   (是不是双亲节点的下标)
  int lchild;
  int rchild;
}huffnode;

typedef struct
{
  int bits[MAXSYMBS];   (不懂)
  int start;            (是不是编码的起始下标)
}huffcode;

main()
{
    huffnode huff_node[MAXNODE];      (?)
    huffcode huff_code[MAXSYMBS],cd;  (?)
    int i,j,m1,m2,x1,x2,n,c,p;

    clrscr();
    printf("please input the leaf num :\n");   (?)
    scanf("%d",&n);   
    for(i=0;i<2*n-1;i++)      (这个循环里做的是不是初始哈夫曼树 )
    {
        huff_node[i].weight=0;      
        huff_node[i].parent=0;
        huff_node[i].flag=0;     (?)
        huff_node[i].lchild=-1;  (?)
        huff_node[i].rchild=-1;  (?)
    }

    printf("please input the weight of every leaf\n");    (?)
    for(i=0;i<n;i++)
        scanf("%d",&huff_node[i].weight);
/* creat huff_tree*/
    for(i=0;i<n-1;i++)     (这个循环基本上看不懂)
    {
        m1=m2=MAX;    (?)
        x1=x2=0;      (?)
        for(j=0;j<n+i;j++)
    {    
            if (huff_node[j].weight<m1&&huff_node[j].flag==0)  (这个if语句下的也不懂)
               {    
           m2=m1;         (?)
                x2=x1;           (?)
                m1=huff_node[j].weight;    (?)
                x1=j;    (?)
            }
            else if (huff_node[j].weight<m2&&huff_node[j].flag==0)   (?)
            {
                m2=huff_node[j].weight;   (?)
                                x2=j;    (?)
            }
        }

        huff_node[x1].parent=n+i;    (?)
        huff_node[x2].parent=n+i;    (?)
        huff_node[x1].flag=1;        (?)
        huff_node[x2].flag=1;
        huff_node[n+i].weight=huff_node[x1].weight+huff_node[x2].weight;
        huff_node[n+i].lchild=x1;
        huff_node[n+i].rchild=x2;
    }
/*creat huff_code*/

    for(i=0;i<n;i++)    
      {
    cd.start=n;   (?)
    c=i;          (?)
         p=huff_node[c].parent;    (?)
         while(p!=0)    (?)
        {
            if(huff_node[p].lchild==c)

                cd.bits[cd.start]=0;
            else
                cd.bits[cd.start]=1;
            cd.start=cd.start-1;   (?)
            c=p;   (?)
            p=huff_node[p].parent;   (?)
        }
        cd.start++;
        for(j=cd.start;j<=n;j++)     (?)
     huff_code[i].bits[j]=cd.bits[j];   (?)
        huff_code[i].start=cd.start;   (?)
    }
    /*input huff_code*/
    puts("The Hafman code are:");
    for(i=0;i<n;i++)
    {
        for(j=huff_code[i].start;j<=n;j++)
            printf("%10d",huff_code[i].bits[j]);
        printf("\n");
                                                                                                                                                                                                   
        
    }
    puts("Press any key to quit...");
    getch();

}

回复列表 (共2个回复)

沙发

问题都给你回答在各条语句尾处了,如果还有问题可以加我QQ聊

#include <stdio.h>
#define MAX  1000
#define MAXSYMBS 30
//(请问一下这是不是编码的最大位数)
#define MAXNODE 59
//(请问一下这是不是初始的最大的结点数)

typedef struct
{
  int weight;   //(是不是权值) 就是权值
  int flag;   //  (看不懂) 这个是用来标记元素是否被比较过,没有则赋值0,用过则为1
  int parent;  // (是不是双亲节点的下标) 这里的双亲,孩子都是用的它们的下标,这就是所谓的孩子双亲表示法
  int lchild;
  int rchild;
}huffnode;

typedef struct
{
  int bits[MAXSYMBS];   //(不懂) 这个是存放哈夫曼编码的数组
  int start;           // (是不是编码的起始下标) 可以看作是编码的起始下标
}huffcode;

main()
{
    huffnode huff_node[MAXNODE];   //   (?) 定义哈夫曼树
    huffcode huff_code[MAXSYMBS],cd; // (?) 定义存放哈夫曼编码的元素
    int i,j,m1,m2,x1,x2,n,c,p;

    clrscr();
    printf("please input the leaf num :\n");  // 输入这个哈夫曼树的叶子数目
    scanf("%d",&n);   
    for(i=0;i<2*n-1;i++)   //   (这个循环里做的是不是初始哈夫曼树 ) 初始哈夫曼树
    {
        huff_node[i].weight=0;      
        huff_node[i].parent=0;
        huff_node[i].flag=0;    // 这个是用来标记元素是否被比较过,没有则赋值0,用过则为1
        huff_node[i].lchild=-1; // (?)
        huff_node[i].rchild=-1; // (?)  这个都是初始化,刚开始各个元素都没有叶子或不知道叶子,所以赋值为-1,反正不要是正数就行
    }

    printf("please input the weight of every leaf\n");   // 输入各叶子的权值
    for(i=0;i<n;i++)
        scanf("%d",&huff_node[i].weight);
/* creat huff_tree*/
    for(i=0;i<n-1;i++)    // (这个循环基本上看不懂)
    {
        m1=m2=MAX;   // (?)
        x1=x2=0;     // (?) 这两条可以说是对它们的初始化,反正m1 m2要足够大,x1,x2不要大于0就行
        for(j=0;j<n+i;j++)
        {
            if (huff_node[j].weight<m1&&huff_node[j].flag==0) // (这个if语句下的也不懂)
               {    
                m2=m1;      //   这条语句的作用是为了再执行多次循环之后的下面的else if 语句作铺垫
                x2=x1;         // 这条语句可以不用,是多余的
                m1=huff_node[j].weight;  //  (?) 找权值中最小的一个元素
                x1=j;   // (?)  用x1记录这个元素
                }
            else if (huff_node[j].weight<m2&&huff_node[j].flag==0)  // (?)
               {
                m2=huff_node[j].weight;  // (?) 找权值第二小的一个元素
                                x2=j;   // (?)  用x2记录这个元素
               }
        }

        huff_node[x1].parent=n+i;   //
        huff_node[x2].parent=n+i;   //   第x1  x2个元素的双亲是第n+i个元素
        huff_node[x1].flag=1;       //
        huff_node[x2].flag=1;       //  标记第x1  x2个元素都被比较过了
        huff_node[n+i].weight=huff_node[x1].weight+huff_node[x2].weight; //第n+i个元素的权值等于第x1个的权值加上第x2个的权值
        huff_node[n+i].lchild=x1;
        huff_node[n+i].rchild=x2;
    }
/*creat huff_code*/

    for(i=0;i<n;i++)    
      {
    cd.start=n;   //(?)cd作中间变量,如果要把代码精简的话可以不用它的,不过这样好看一点
    c=i;          //(?)把i赋给c下面有用
         p=huff_node[c].parent;  //  (?) 把第c个元素的双亲的下标赋给p
         while(p!=0)  //  (?)  如果第c 个元素的双亲存在
        {
            if(huff_node[p].lchild==c) //如果第c个元素是第p个元素的左孩子

                cd.bits[cd.start]=0; //定义左孩子哈夫曼码为0
            else    //如果第c个元素是第p个元素的右孩子
                cd.bits[cd.start]=1;
            cd.start=cd.start-1;  // (?)bit数组的第cd.start个地方已经存放了数据,所以要在前一个地址存入下一个哈夫曼码
            c=p; //  (?) 下一步是以p为起点找它的双亲,循环执行
            p=huff_node[p].parent;  // (?)这里可以改成 p=huff_node[c].parent; 不知道可不可以更好理解
        }
        cd.start++; //执行完while循环后因为上面有一个cd.start=cd.start-1;所以要对它加一
     //   for(j=cd.start;j<=n;j++)    // (?)
     //huff_code[i].bits[j]=cd.bits[j];//   (?)
     //  huff_code[i].start=cd.start; //  (?)
     //这上面三条写了一大堆,其实就是下面这条语句,上三条语句完全冗余
       huff_code[i]=cd;
    }
    /*input huff_code*/
    puts("The Hafman code are:");
    for(i=0;i<n;i++)
    {
        for(j=huff_code[i].start;j<=n;j++)
            printf("%10d",huff_code[i].bits[j]);
        printf("\n");
                                                                                                                                                                                                   
        
    }
    puts("Press any key to quit...");
    getch();

}

板凳

#define MAXSYMBS 30
//定义最大位数
#define MAXNODE 59
//定义最大节点数
//存放位置在
 huffnode huff_node[“MAXNODE”];   
    huffcode huff_code[“MAXSYMBS”];

我来回复

您尚未登录,请登录后再回复。点此登录或注册