하프 만 코드

//        :       ，        ；
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct{
   unsigned int weight;
   unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; 
typedef char **HuffmanCode;
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
{  
// HT[1..n]   parent 0 weight       ，
//       s1 s2。
    int i;
    s1=-1;s2=-1;
    for(i=1; i<=n; i++)
        if(HT[i].parent == 0)
        {
            if(s1 == -1)
                s1 = i;
            else if(HT[i].weight < HT[s1].weight)
            {
                s2 = s1;
                s1 = i;
            }
            else if(s2 == -1 || HT[i].weight < HT[s2].weight)
                s2 = i;
        }
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
  //    n         HC
  int i, m, s1, s2, start;
  char *cd;
  unsigned int c, f;
  if (n<=1) return;
  m = 2 * n - 1;
  HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));  // 0     
  for (i=1; i<=n; i++) { //   
    HT[i].weight=w[i-1];
    HT[i].parent=0;
    HT[i].lchild=0;
    HT[i].rchild=0;
  }
  for (i=n+1; i<=m; i++) { //   
    HT[i].weight=0;
    HT[i].parent=0;
    HT[i].lchild=0;
    HT[i].rchild=0;
  }
  for (i=n+1; i<=m; i++) {  //      
    //  HT[1..i-1]   parent 0 weight       ，
    //       s1 s2。
    Select(HT, i-1, s1, s2);
    HT[s1].parent = i;  HT[s2].parent = i;
    HT[i].lchild = s1;  HT[i].rchild = s2;
    HT[i].weight = HT[s1].weight + HT[s2].weight;
  }
   //---                    ---
  cd = (char *)malloc(n*sizeof(char));    //           
  cd[n-1] = '\0';                         //      。
  for (i=1; i<=n; ++i) {                  //           
    start = n-1;                          //        
    for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent) 
      //           
      if (HT[f].lchild==c) cd[--start] = '0';
      else cd[--start] = '1';
    HC[i] = (char *)malloc((n-start)*sizeof(char)); 
         //   i         
    strcpy(HC[i], &cd[start]);    //  cd    ( ) HC    
    
  }
  free(cd);   //      
} //HuffmanCoding
int _tmain(int argc, _TCHAR* argv[])
{
   int i,n;
   int *w;
   HuffmanTree HT;
   HuffmanCode HC;
   printf("Node Number:");
   scanf("%d",&n);  //    
   w=(int *)malloc(n*sizeof(int));  
   printf("Input weights:");
   for ( i=0;i<n;i++)  //    
     scanf("%d",&w[i]);
   
   HC=(char **)malloc((n+1)*sizeof(char*)); //0    
   HT=(HuffmanTree)malloc((2*n+1+1)*sizeof(HTNode));//0    
   HuffmanCoding(HT, HC, w, n);
   printf("
");   
   for (i = 1; i<n+1; i++){
     printf("%s
", HC[i]);  //       
     free(HC[i]);  //    
   }
   free(HC);
   free(HT);
   system("pause");
   return 0;
}

int min(HuffmanTree t,int i)
{
    //   void select()  
    int j,flag;
    unsigned int k=UINT_MAX; //  k        
    for(j=1; j<=i; j++)
        if(t[j].weight<k&&t[j].parent==0)
            k=t[j].weight,flag=j;
    t[flag].parent=1;
    return flag;
}
void select(HuffmanTree t,int i,int &s1,int &s2)
{
    // s1              
    s1=min(t,i);
    s2=min(t,i);
   /* if(s1>s2)
    {
        j=s1;
        s1=s2;
        s2=j;
    }*/
}