C++實現Huffman樹

#include "stdafx.h"
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

//存儲HuffmanTree的數據結構
typedef struct tagHuffmanTree
{
 unsigned int nWeight;
 unsigned int nParent,nLchild,nRchild;   //用於保存節點在數組中的位置
}HTNode, *HuffmanTree;                         // 動態分配數組存儲赫夫曼樹

typedef char* HuffmanCodeLine;
typedef char** HuffmanCode;                 // 動態分配數組存儲赫夫曼編碼表。。二級指針

//從數列中找出parent為0且權值最小的兩個葉節點.. nMin1和nMin2為數組中位置
void SelectMinWeight(HuffmanTree &HT, int nNodeCount, int &nMin1, int &nMin2)
{
 int i = 0;
 int c = 0;
 int nMinWeight1 = 65535;
 int nMinWeight2 = 65535;

 int *pOrder = new int[nNodeCount];
 for (i=1; i<=nNodeCount; ++i)
 {
  if (0 == HT[i].nParent)                           //統計parent為0的節點及下標
  {
   pOrder[c++] = i;
  }
 }

 //比較parent為0的節點中權值大小,獲取權值小的位置
 for (i=0; i<c; ++i)
 {
  // 在每次循環中, 始終將較小值存入nMinWeight1, 較大值存入nMinWeight2;
  // 執行完畢後, nMinWeight1中是最小值, nMinWeight2中是次小值.
  int nTempWeight = HT[pOrder[i]].nWeight;
  if (nTempWeight < nMinWeight1)
  {
   nMinWeight2 = nMinWeight1;
   nMin2 = nMin1;
   nMinWeight1 = nTempWeight;
   nMin1 = pOrder[i];
  }
  else if (nTempWeight < nMinWeight2)
  {
   nMinWeight2 = nTempWeight;
   nMin2 = pOrder[i];
  }
 }

 if (pOrder)
 {
  delete [] pOrder;
  pOrder = NULL;
 }

 return;
}

//建樹及獲取葉子節點編碼

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *pWeight, int nLeafCount)
{
 if (nLeafCount <= 1)
 {
  return;
 }

 //pWeight為存放權值的數組；nLeafCount為葉子節點數目，即待編碼節點數

 int nNodeCount = 2*nLeafCount - 1;                   //總節點數目
 HT = new HTNode[nNodeCount + 1];                 //多申請一個空間，為了0號單元不使用

 HTNode *pTemp = NULL;
 int i = 0;
 //初始化前幾個存儲單元，存放葉子節點。
 for (i=1,pTemp=HT+1; i<=nLeafCount; ++i, ++pTemp, ++pWeight)             //pTemp=HT+1，第0號單元不用
 {
  (*pTemp).nWeight = *pWeight;
  (*pTemp).nParent = 0;
  (*pTemp).nLchild = 0;
  (*pTemp).nRchild = 0;
 }

 //初始化HT後幾個存儲單元，均為存放後來生成的Parent節點的、
 for (; i<=nNodeCount; ++i,++pTemp)
 {
  (*pTemp).nWeight = 0;
  (*pTemp).nParent = 0;
  (*pTemp).nLchild = 0;
  (*pTemp).nRchild = 0;
 }

 //建立HuffmanTree。
 int nMin1, nMin2;
 for (i=nLeafCount+1; i<=nNodeCount; ++i)
 {
  //在HT[1...i-1]中尋找parent為0且權值最小的兩個。分別為nMin1, nMin2（nMin1, nMin2是在數組中的位置）
  SelectMinWeight(HT, i-1, nMin1, nMin2);
  HT[nMin1].nParent = i;
  HT[nMin2].nParent = i;
  HT[i].nLchild = nMin1;
  HT[i].nRchild = nMin2;
  HT[i].nWeight = HT[nMin1].nWeight + HT[nMin2].nWeight;
 }

 //----------------編碼部分-------------------------------
 //從葉子到根逆向求編碼
 HC = new HuffmanCodeLine[nLeafCount + 1];    //0號單元未用
 char *pCode = new char[nLeafCount];                  //用於保存一個節點的編碼序列
 memset(pCode, 0, nLeafCount);
 //pCode[nLeafCount - 1] = '\0';                                //編碼結束符
 int nStart = 0;
 for (i=1; i<=nLeafCount; ++i)                                  //遍歷葉子節點
 {
  nStart = nLeafCount - 1;                                        //編碼結束符的位置,pCode數組最後一個位置
  int nTempPos;
  unsigned int nParent;
  for (nTempPos=i,nParent=HT[i].nParent; nParent!=0; nTempPos=nParent, nParent=HT[nParent].nParent)
  {
   if (nTempPos == HT[nParent].nLchild)                //默認左子樹賦值0，右子樹賦值1
   {
    pCode[--nStart] = '0';
   }
   else
   {
    pCode[--nStart] = '1';
   }
  }
  HC[i] = new char[ nLeafCount - nStart ];
  strcpy(HC[i], &pCode[nStart]);                             //將一個葉子節點的編碼拷貝
 }

 if (pCode)
 {
  delete [] pCode;
  pCode = NULL;
 }

 return;
}

//主程序入口
int _tmain(int argc, _TCHAR* argv[])
{
 int i = 0;
 int nLeafCount = 0;                   //葉子數即為要編碼的節點數
 //int nNodeCount = 0;
 cout<<"Input num of leaf:"<<endl;
 cin>>nLeafCount;
 while (0 == nLeafCount)
 {
  cout<<"Num of leaf can not be 0"<<endl;
  cin>>nLeafCount;
 }

 //申請內存保存字符值和權值
 char *pLetter = new char[nLeafCount];          //保存字符值
 int *pWeight = new int[nLeafCount];              //保存權值
 for (i=0; i<nLeafCount; ++i)
 {
  cout<<"Input letter and weight"<<endl;
  cin>>pLetter[i]>>pWeight[i];
 }

 HuffmanTree HT = NULL;
 HuffmanCode HC = NULL;
 HuffmanCoding(HT, HC, pWeight, nLeafCount);       //調用方法，建立Huffman樹，並獲取編碼序列

 for (int i=1; i<=nLeafCount; ++i)                                   //輸出葉子節點的編碼
 {
  cout<<HC[i]<<endl;
 }

 system("pause");

 if (HT)                        //釋放樹資源
 {
  delete [] HT;
  HT = NULL;
 }

 for (int i=1; i<=nLeafCount; ++i)        //釋放存放編碼的資源
 {
  delete [] HC[i];
  HC[i] = NULL;
 }

 if (HC)
 {
  delete [] HC;
  HC = NULL;
 }

 if (pLetter)
 {
  delete [] pLetter;
  pLetter = NULL;
 }
 if (pWeight)
 {
  delete [] pWeight;
  pWeight = NULL;
 }

 return 0;
}