home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1991 / 08 / dflat5 / htree.c < prev    next >
Text File  |  1991-06-26  |  2KB  |  59 lines
  1. /* ------------------- htree.c -------------------- */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include "dflat.h"
  6. #include "htree.h"
  7.  
  8. #ifdef INCLUDE_COMPRESS_HELPFILE
  9.  
  10. struct htree *ht;
  11. int root;
  12.  
  13. /* ------ build a Huffman tree from a frequency array ------ */
  14. void buildtree(void)
  15. {
  16.     int treect = 256;
  17.     int i;
  18.  
  19.     for (i = 0; i < treect; i++)    {
  20.         ht[i].parent = -1;
  21.         ht[i].right  = -1;
  22.         ht[i].left   = -1;
  23.     }
  24.     /* ---- build the huffman tree ----- */
  25.     while (1)   {
  26.         int h1 = -1, h2 = -1;
  27.         /* ---- find the two smallest frequencies ---- */
  28.         for (i = 0; i < treect; i++)   {
  29.             if (i != h1) {
  30.                 struct htree *htt = ht+i;
  31.                 if (htt->cnt > 0 && htt->parent == -1)   {
  32.                     if (h1 == -1 || htt->cnt < ht[h1].cnt) {
  33.                         if (h2 == -1 || ht[h1].cnt < ht[h2].cnt)
  34.                             h2 = h1;
  35.                         h1 = i;
  36.                     }
  37.                     else if (h2 == -1 || htt->cnt < ht[h2].cnt)
  38.                         h2 = i;
  39.                 }
  40.             }
  41.         }
  42.         if (h2 == -1) {
  43.             root = h1;
  44.             break;
  45.         }
  46.         /* --- combine two nodes and add one --- */
  47.         ht[h1].parent = treect;
  48.         ht[h2].parent = treect;
  49.         ht = realloc(ht, (treect+1) * sizeof(struct htree));
  50.         ht[treect].cnt = ht[h1].cnt + ht[h2].cnt;
  51.         ht[treect].right = h1;
  52.         ht[treect].left = h2;
  53.         ht[treect].parent = -1;
  54.         treect++;
  55.     }
  56. }
  57.  
  58. #endif
  59.