minheap.txt

别处下的一个huffman压缩程序

#include <stdio.h>
#include <stdlib.h>
#include "error.h"
#include "minheap.h"
//minheap.c//

/* function prototype */
static int cmp(HuffTree, HuffTree);

/* creates a new minheap array and initializes its elements to NULL */
MinHeap NewMinHeap(void)
{
   HuffTree *array;
   int i;
   MinHeap mh;

   mh = malloc(sizeof(struct MinHeapInfo));
   if(mh == NULL)
   {
      FatalError("Not enough memory!");
   }

	array = malloc(MAX_ARRAY * sizeof(struct HuffNode));
    {
      FatalError("Not enough memory!");
   }

   for(i = 0; i < MAX_ARRAY; i++)
   {
      array[i] = NULL;
   }

   mh->ArraySize = MAX_ARRAY;
   mh->Size = 0;
   mh->heap_array = array;
   return mh;
}

/* deletes an element from the minheap...thus the resulting "leaves" of
   the minheap "tree" are sorted according to lowest frequency */
HuffTree DeleteMinHeap(MinHeap mh)
{
   int i, j;
	HuffTree first,last;
    if(mh->Size == 0)
   {
      FatalError("Can't delete from an empty MinHeap!");
   }

   /* need to know what the first element (the one to be deleted) and
      the last element (the "leaf" that will be unattached temporarily)
      are */
   first = mh->heap_array[1];
   last = mh->heap_array[mh->Size];

   while(i <= (mh->Size)/2)
   {
      j = (i * 2);
      /* keep looking until we find an out-of-order subtree (sorted by
         frequency */
      if((j != mh->Size) &&
         (cmp(mh->heap_array[j + 1],mh->heap_array[j]) < 0))
      {
         j++;
		}
       if(cmp(last, mh->heap_array[j]) > 0)
      {
         /* don't need to put last here, but the "lower" leaf needs
            to be moved up the tree */
         mh->heap_array[i] = mh->heap_array[j];
      }
      else
      {
         /* we need to put last at the current i location in the minheap
            array */
         break;
      }
      i = j;
   }
   mh->heap_array[i] = last;
   mh->Size--;
   return first;
}

/* this function inserts a "tree" into the minheap */
void InsertMinHeap(MinHeap h, HuffTree t)
{
 if(h->Size == h->ArraySize)
   {
      FatalError("MinHeap is too full!");
   }

   /* we're going to be putting a new tree into minheap, so increment
      its size */
   h->Size++;

   i = h->Size;
   /* search for the proper place to put the new tree */
   while(cmp(t,h->heap_array[i / 2]) < 0)
   {
      /* go farther up the tree, resorting as you go */
      h->heap_array[i] = h->heap_array[i / 2];
      i = (i / 2);
   }

   h->heap_array[i] = t;
   return;
}
int SizeMinHeap(MinHeap h)
{
   return h->Size;
}

/* compares the frequencies of two HuffTrees */
static int cmp(HuffTree t1, HuffTree t2)
{
   if(t2 == NULL)
   {
      return 1;
   }
   else if(t1->frequency < t2->frequency)
   {
      return -1;
   }
   else if(t1->frequency > t2->frequency)
   {
      return 1;
   }
   else
	{
	 }
	}