huffman.txt

数据结构中树的构造方法,可以借鉴一下,以做出更好的算法

/*   huffman树的构造方法*/   
    
  #include<stdlib.h>   
  #include<stdio.h>   
  #define     MAXINT         2147483647   
  #define     MAXNUM       50 /*   数组w中最多容纳的元素个数，注意   m<=MAXNUM   */   
  #define     MAXNODE     100 /*   哈夫曼树中的最大结点数，注意   2*m-1<MAXNODE   */   
    
  struct   HtNode   {                 /*   哈夫曼树结点的结构   */   
          int   ww;   
          int   parent,llink,rlink;   
  };   
    
  struct   HtTree   {   
          int         root;/*   哈夫曼树根在数组中的下标*/   
          struct   HtNode     ht[MAXNODE];   
  };   
    
  typedef   struct   HtTree     *PHtTree;   /*   哈夫曼树类型的指针类型   */   
    
  /*   构造具有m个叶结点的哈夫曼树*/   
  PHtTree   huffman(int   m,   int   *w)   {     
          PHtTree     pht;   
          int   i,   j,   x1,   x2,   m1,   m2;   
          pht   =   (PHtTree)malloc(sizeof(struct   HtTree));     /*   创建空哈夫曼树   */   
          if   (pht   ==   NULL)   {   
                  printf("Out   of   space!!   \n");   
                  return   pht;   
          }   
          for   (i   =   0;   i   <   2*m-1;   i++)   {/*   置初态   */   
                  pht->ht[i].llink   =   -1;   
                  pht->ht[i].rlink   =   -1;   
                  pht->ht[i].parent   =   -1;   
                  if   (i   <   m)   
                          pht->ht[i].ww   =   w[i];   
                  else   
                          pht->ht[i].ww   =   -1;   
          }   
          for   (   i   =   0;   i   <   m-1;   i++) {/*   每循环一次构造一个内部结点   */   
                  m1   =   MAXINT;   
                  m2   =   MAXINT;/*   相关变量赋初值   */   
                  x1   =   -1;   
                  x2   =   -1;   
                  for   (j   =   0;   j   <   m+i;   j++) /*   找两个最小权的无父结点的结点   */   
                          if   (pht->ht[j].ww   <   m1   &&   pht->ht[j].parent   ==   -1)   {   
                                  m2   =   m1;   
                                  x2   =   x1;   
                                  m1   =   pht->ht[j].ww;   
                                  x1   =   j;   
                          }   
                          else   if   (pht->ht[j].ww   <   m2   &&   pht->ht[j].parent   ==   -1)   {   
                                  m2   =   pht->ht[j].ww;   
                                  x2   =   j;   
                          }   
    
                  pht->ht[x1].parent   =   m+i; /*   构造一个内部结点   */   
                  pht->ht[x2].parent   =   m+i;   
                  pht->ht[m+i].ww   =   m1+m2;     
                  pht->ht[m+i].llink   =   x1;     
                  pht->ht[m+i].rlink   =   x2;   
                  pht->root   =   m+i;   
          }     
          return   pht;   
  }   
    
  int   main()   {   
          int   m   =   0,   j   =   0,   i   =   0,   parent   =   0;   
          int*   w;   
          PHtTree   pht;   
          printf("please   input   m   =   ");/*输入外部结点个数*/   
          scanf("%d",   &m);   
          if   (m   <   1)   {   
                  printf("m   is   not   reasonable!\n");   
                  return   1;   
          }   
          w   =   (int   *)malloc(sizeof(int)*m);   
          if   (w   ==   NULL)   {   
                  printf("overflow!\n");   
                  return   1;   
          }   
          printf("please   input   the   %d   numbers：\n",m);/*输入权值*/   
          for   (j   =   0;   j   <   m;   j++)   
                  scanf("%d",   w+j);   
          pht   =   huffman(m,   w);   
          for   (j   =   0;   j   <   m;   j++)   {   
                  printf("the   Reverse   code   of   the   %d   node   is:",   j+1);/*得到的编码应倒过来*/   
                  i   =   j;   
                  while   (pht->ht[i].parent   !=   -1)   {   
                          parent   =   pht->ht[i].parent;   
                          if   (pht->ht[parent].llink   ==   i)   
                                  printf("0");   
                          else   
                                  printf("1");   
                          i   =   parent;   
                  }   
                  printf("\n");   
          }   
          return   0;   
  }