Huffman編碼C實現

Huffman編碼：根據Huffman樹進行編碼的，用到的數據結構是二叉樹。

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

Huffman編碼實現（詳細實現） http://www.linuxidc.com/Linux/2012-01/51730.htm

Huffman編碼與解碼的實現 http://www.linuxidc.com/Linux/2014-08/105644.htm

typedef int elemtype;
typedef struct
{
  elemtype weight;
  int parent,l_child,r_child;
} binarytree;

//2、構建最優二叉樹
void CreateHuffman(int leafnum, binarytree *huffmantree)
{
    //leafnum個葉子，決定nodenum個結點數
 int nodenum=2*leafnum-1;
 huffmantree=(binarytree *)malloc(nodenum*sizeof(binarytree));  //0號單元也使用
 
 //leafnum個葉子，決定nodenum個結點數，也決定了（nodenum-1）個bit位編碼
 char *huffmancode;
 huffmancode =(char *)malloc((nodenum-1)*sizeof(char));

 //huffmantree的初始化:葉子結點data權值手動輸入，非葉子默認值都為0
 cout<<"請輸入葉子權值：";
 int i;
 for(i=0;i<nodenum;i++)
 {
  if(i<leafnum)
  {
   cin>>huffmantree[i].weight;
  }
  else
  {
    huffmantree[i].weight=0;
  }
  huffmantree[i].parent=huffmantree[i].l_child=huffmantree[i].r_child=0;
 }

 int j;
 //j從leafnum開始，指的是包含了新建子樹的結點編號
 for(j=leafnum;j<nodenum;j++)
 {
  int w1=32767,w2=0; //存儲最小權值；
  int p=0,q=0; //存儲最小權值的編號；

      int k; 
    for(k=0;k<j;k++)
    {
      if(huffmantree[k].parent==0)  //判斷結點是否使用
      {
      if(huffmantree[k].weight<w1)
        {
        w2=w1;
        q=p;
        w1=huffmantree[k].weight;
        p=k;       
         
        }
      else if(huffmantree[k].weight<w2)
      {
        w2=huffmantree[k].weight;
        q=k;
      }
      }
      }
  //p對應左節點，編碼為‘0’；q對應左節點，編碼為‘1’；
  huffmancode[p]='0';
  huffmancode[q]='1';
 
  huffmantree[j].weight =w1+w2;
  huffmantree[j].l_child=p;
  huffmantree[j].r_child=q;
  huffmantree[p].parent=j;
  huffmantree[q].parent=j; 
 }

//3、尋找從子節點到根節點的編碼 HuffmanCoding(int n,binarytree *HuffmanTree)
 //針對每一個葉子，從葉子到根方向尋找huffmancode
 //每一個葉子，對應的編碼長度codelength
 const int maxsize=10;
 char iscode[maxsize][maxsize];
 int m;
 for(m=0;m<leafnum;m++)  //從第一個葉子開始找
 {
      int n=0;
  iscode[m][n]=huffmancode[m]; 
  int parent=huffmantree[m].parent;   
  while(parent !=0)
  {
    iscode[m][++n]=huffmancode[parent];
    parent=huffmantree[parent].parent;
  };

  int x;
  cout<<"第"<<m+1<<"個葉子的HuffmanCode————";
  for(x=0;x<n;x++)
    cout<<iscode[m][x]; 
  cout<<endl;
 }
}

void main()
{
  binarytree *T=0;
  int leafnum;
  printf("輸入葉子數量n=\n");
  cin>>leafnum;
  CreateHuffman( leafnum, T);
  while(1);
}

編譯結果如下：