用C语言编无失真信源编码（哈夫曼编码）

#include <string.h>
#include <stdio.h>
#include <malloc.h>
typedef unsigned char U8;
typedef unsigned short U16;
typedef unsigned long U32;
typedef struct HuffmanNode
{
double prob;
struct HuffmanNode *left;
struct HuffmanNode *right;
}huffmancode;

void Init ( U32*, double** );
huffmancode* Encode ( double*, U32 );
huffmancode* CreateBinaryTree ( huffmancode**, int );
void Print ( huffmancode*, char* );
void DeleteBinaryTree ( huffmancode* );

void main()
{
U32 n;
double *p;
huffmancode *pHuffman;

Init ( &n, &p );

pHuffman = Encode ( p, n );
Print ( pHuffman, "" );

DeleteBinaryTree ( pHuffman );
}

void DeleteBinaryTree ( huffmancode *pHuffman )
{
if ( pHuffman->left != NULL )
  DeleteBinaryTree ( pHuffman->left );
if ( pHuffman->right != NULL )
  DeleteBinaryTree ( pHuffman->right );
free ( pHuffman );
return;
}

void Print ( huffmancode *pHuffman, char *code )
{
int numChild = 0;
int strLen = strlen(code);
char *nextCode = (char*) malloc ( strLen + 2 );
if ( pHuffman->left != NULL )
{
  numChild++;
  strcpy ( nextCode, code );
  nextCode[strLen] = '0';
  nextCode[strLen+1] = '\0';
  Print ( pHuffman->left, nextCode );
}
if ( pHuffman->right != NULL )
{
  numChild++;
  strcpy ( nextCode, code );
  nextCode[strLen] = '1';
  nextCode[strLen+1] = '\0';
  Print ( pHuffman->right, nextCode );
}
if ( numChild == 0 )
{
  printf ( "%lf\t==>\t%s\n", pHuffman->prob, code );
}
free ( nextCode );
return;
}

huffmancode* Encode ( double *p, U32 n )
{
U32 i;
huffmancode *pRes;
huffmancode **ppHuffman;

ppHuffman = (huffmancode**) malloc ( sizeof(huffmancode*) * n );
for ( i = 0; i < n; i++ )
{
  ppHuffman[i] = (huffmancode*) malloc ( sizeof(huffmancode) );
  ppHuffman[i]->prob = p[i];
  ppHuffman[i]->left = NULL;
  ppHuffman[i]->right = NULL;
}

pRes = CreateBinaryTree ( ppHuffman, n );
free ( ppHuffman );
return pRes;
}

huffmancode* CreateBinaryTree ( huffmancode **ppHuffman, int n )
{
int i;
int min1 = 0, min2 = 1;  /* min1 < min2 */
huffmancode *tmp, *pRes;

pRes = (huffmancode*) malloc ( sizeof ( huffmancode ) );

if ( ppHuffman[0]->prob > ppHuffman[1]->prob )
  min1 = 1, min2 = 0;

for ( i = 2; i < n; i++ )
{
  if ( ppHuffman[i]->prob < ppHuffman[min2]->prob )
  {
   if ( ppHuffman[i]->prob < ppHuffman[min1]->prob )
   {
    min2 = min1;
    min1 = i;
   }
   else
   {
    min2 = i;
   }
  }
}
pRes->prob = ppHuffman[min1]->prob + ppHuffman[min2]->prob;
pRes->left = ppHuffman[min1];
pRes->right = ppHuffman[min2];

if ( min1 == n - 1 )
  ppHuffman[min2] = pRes;
else if ( min2 == n -1 )
  ppHuffman[min1] = pRes;
else
{
  ppHuffman[min1] = pRes;
  ppHuffman[min2] = ppHuffman[n-1];
}

if ( n != 2 )
  pRes = CreateBinaryTree ( ppHuffman, n-1 );
return pRes;
}

void Init ( U32 *n, double **pp )
{
*n = 6;
*pp = (double*) malloc ( sizeof(double) * (*n) );

(*pp)[0] = 0.1;
(*pp)[1] = 0.2;
(*pp)[2] = 0.3;
(*pp)[3] = 0.15;
(*pp)[4] = 0.04;
(*pp)[5] = 0.21;

/* (*pp)[0] = 0.1;
(*pp)[1] = 0.1;
(*pp)[2] = 0.1;
(*pp)[3] = 0.1;
(*pp)[4] = 0.1;
(*pp)[5] = 0.1;
(*pp)[6] = 0.1;
(*pp)[7] = 0.1;*/


return;
}