Huffman編碼與解碼的實現

Huffman編碼相信學過數據結構這麼課的都知道，概念也比較好理解，但是一般好理解的算法，在實際實現的過程中總是會遇到各種問題，一方面個人認為是對算法的實現過程不熟，另一方面在實際實現的過程中可以提升自己實現算法的能力，將自己的想法實現後還是比較滿足的。下面是本人親自實現的Huffman編碼與解碼的C語言實現，主要是記錄一下自己當時的想法，供以後備忘吧。

C++使用優先隊列來構建huffman樹[哈夫曼樹]  http://www.linuxidc.com/Linux/2012-01/52790.htm

Huffman編碼實現（詳細實現） http://www.linuxidc.com/Linux/2012-01/51730.htm
 
數據結構定義如下：

typedef struct{
 unsigned int weight;
 unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree;

typedef char * * HuffmanCode;

建Huffman樹的過程是使用順序結構數組存儲樹，由於沒有度為一的節點，因此總數為2*n - 1個節點，n為葉子節點個數，也是待編碼的字符個數。
 
建樹的關鍵代碼如下：

        //建立Huffman樹，初始化1到n號元素的parent都為0，每次從parent為0的元素中
 //挑選最小的兩個建樹之後,將它們的parent都置為對應號碼
 for(i = n + 1; i <= m; i++)
 {
  int  min1, min2;
  int j;
  for(j = 1; j <= i - 1; j++)
   if(HT[j].parent == 0) {min1 = j; break;}
  for(j = 1; j <= i - 1; j++)
  {
   if(HT[j].parent != 0) continue;
   if(HT[j].weight < HT[min1].weight)
    min1 = j;
  }
  HT[min1].parent = i;
 
  for(j = 1; j <= i - 1; j++)
   if(HT[j].parent == 0) {min2 = j; break;}
  for(j = 1; j <= i - 1; j++)
  {
   if(HT[j].parent != 0) continue;
   if(HT[j].weight < HT[min2].weight)
    min2 = j;
  } 
  HT[min2].parent = i;
 
  HT[i].lchild = min1;
  HT[i].rchild = min2;
  HT[i].weight = HT[min1].weight + HT[min2].weight;
 }

編碼過程是更加樹的結構，對每個非葉子節點的左子樹為‘0’，右子樹為‘1’。實現如下：

//編碼
 HuffmanCode HC = (HuffmanCode)malloc(n*sizeof(char *));
 char * cd = (char *)malloc(n*sizeof(char));
 cd[n-1] = '\0';
 for(i = 0; i < n; i++)
 {
  int end = n - 1;
  int cur = i + 1;
  for (int a = HT[cur].parent; a != 0; cur = a, a = HT[a].parent)
  {
   if (HT[a].lchild == cur) cd[--end] = '0';
   else if (HT[a].rchild == cur) cd[--end] = '1';
  }
  HC[i] = (char*)malloc((n-end)*sizeof(char));
  strcpy(HC[i], &cd[end]);
 }
 free(cd);

全部實現，封裝在一個HuffmanEncode函數中。

HuffmanCode HuffmanEncode(HuffmanTree & HT, unsigned int * w, int n)
{
 int m = 2 * n - 1; 
 HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //第一個不用
 int i;
 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;
 }
 //建立Huffman樹，初始化1到n號元素的parent都為0，每次從parent為0的元素中
 //挑選最小的兩個建樹之後,將它們的parent都置為對應號碼
 for(i = n + 1; i <= m; i++)
 {
  int  min1, min2;
  int j;
  for(j = 1; j <= i - 1; j++)
   if(HT[j].parent == 0) {min1 = j; break;}
  for(j = 1; j <= i - 1; j++)
  {
   if(HT[j].parent != 0) continue;
   if(HT[j].weight < HT[min1].weight)
    min1 = j;
  }
  HT[min1].parent = i;
 
  for(j = 1; j <= i - 1; j++)
   if(HT[j].parent == 0) {min2 = j; break;}
  for(j = 1; j <= i - 1; j++)
  {
   if(HT[j].parent != 0) continue;
   if(HT[j].weight < HT[min2].weight)
    min2 = j;
  } 
  HT[min2].parent = i;
 
  HT[i].lchild = min1;
  HT[i].rchild = min2;
  HT[i].weight = HT[min1].weight + HT[min2].weight;
 }
 
 //編碼
 HuffmanCode HC = (HuffmanCode)malloc(n*sizeof(char *));
 char * cd = (char *)malloc(n*sizeof(char));
 cd[n-1] = '\0';
 for(i = 0; i < n; i++)
 {
  int end = n - 1;
  int cur = i + 1;
  for (int a = HT[cur].parent; a != 0; cur = a, a = HT[a].parent)
  {
   if (HT[a].lchild == cur) cd[--end] = '0';
   else if (HT[a].rchild == cur) cd[--end] = '1';
  }
  HC[i] = (char*)malloc((n-end)*sizeof(char));
  strcpy(HC[i], &cd[end]);
 }
 free(cd);
 return HC;
}

更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-08/105644p2.htm