本文共 2457 字，大约阅读时间需要 8 分钟。

//哈夫曼树构造原则: 权值小的在前，相等的单节点在前；#include "stdafx.h"#include 
   
    #include 
    
     #include 
     
      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);   //释放工作空间} //HuffmanCodingint _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
     
    
   

其中的select（）函数亦可如下求解：

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
   
    s2)    {        j=s1;        s1=s2;        s2=j;    }*/}
   

转载地址：http://fdsvi.baihongyu.com/