有點兒興奮，有點兒緊張，這是我人生發的第一篇正式的blog，在進入正文之前，請容許我說一點兒序言，之所以發這一blog文章，一來是想記錄下自己一天做了些什么，學了些什么，所謂：好記性不如爛筆頭，以前沒有體會到這一點兒的好，在經過一個項目的總結之后，看到同事在做一個項目的總結文檔和自己的一比，才知道，原來實時記錄自己所學，所想的重要性，成功是一點兒一點兒積累起來的；二來，也是便于自己經常的復習所學的東西，不致于要用的時候，到處找，像無頭蒼蠅一般；

好了，讓我們進入正題吧，今天所學的是用代碼實現“赫夫曼編碼”。當然，什么是赫夫曼編碼呢？在此，我就不多說了，因為本人也不是很了解，只知道“赫夫曼編碼”又稱“前綴編碼”，在《數據結構(C語言)版——嚴蔚敏感編著》中第146頁有些許的介紹。有興趣的朋友可以下去多了解學習一下，本人只注重代碼的實現。謝謝！

讓我先來看看生成“赫夫曼編碼”所需的數據結構：

typedef struct_huffman_node

{

unsigned int weight;

unsigned int parent,lchild,rchild;

_huffman_node(const int w,const int p,const int l ,const int r)

{

weight=w;parent=p;lchild=l;rchild=r;

}

bool operator<(const _huffman_node t)

{

return weight<t.weight;

}

}HTNode,*HuffmanTree;

typedef char ** HuffmanCode;//動態分配數組存儲赫夫曼編碼表

注：之所以把父指針、左子樹、右子樹定義為unsigned int是因為我采用的是數據存儲結構是數組，故，parent、lchild、rchild存放的是相應的下標值，無需用指針來存儲。當然，網上也有很多利用其二叉樹來實現的方法，由于自己還沒有達到那個高度，所以只好先用數組來實現了，慢慢來，慢慢提高，慢慢的接近大神。

在這個結構體中，還定義了一個結構體的構造函數，與“<”運算符的函數。這樣便于對結構體賦值及比較。稍后，為大家帶來詳細的講解。

其次，來看實現編碼的函數。

void HuffmanCoding( HuffmanTree &HT,HuffmanCode& HC,int *w,int n )

{

if (w==NULL || n<=1)

{

return;

}

if (HT!=NULL || HC !=NULL)

{

throw INVALID_PARAMETER;

return;

}

int m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//從下標開始計數

if (HT == NULL)

{

return;//是否還有什么工作沒有做

}

HuffmanTree p = HT;

*p=HTNode(0,0,0,0);

p++;

for (int i =1; i<=n; ++i,++p,++w)

{

*p=HTNode(*w,0,0,0);//利用結點的權值，初始化huffman樹的前n個結點。這就是用了結構體的構造函數好處，可以少寫很多的賦值代碼。

}

for(int i =n+1;i<=m;i++,++p)

{

*p=HTNode(0,0,0,0);//初始化huffman樹中的雙親節點。

}

unsigned int s1=0,s2=0;

for(int i=n+1;i<=m;++i)

{

//建立赫夫曼樹

SelectSubtree(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;

}

//

/*

*從葉子到根逆向求每個字符的赫夫曼編碼

*/

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n個字符編碼的頭指針向量

char * cd =(char*)malloc(n*sizeof(char));

if (HC==NULL || cd ==NULL)

{

return ;//是否還有什么別的工作沒有做。

}

cd[n-1]='\0';

int start=0;

int c =0 ,f =0,len=0;

for (int 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';

}

}

len = n-start;

HC[i] = (char *)malloc((len+1)*sizeof(char));//為第i個字符編碼分配空間

memset(HC[i],0,len+1);

strcpy_s(HC[i],len,&cd[start]);

}

free(cd);

}

注：1、要注意函數中，多處用了malloc動態的開辟內存空間，要及時的對新開辟的內存空間初始化。

2、要注意對開辟空間數據的操作，本人在對此指針操作的時候，多次造成指針越界，調試非常的痛苦，請朋友們一定要注意啦。如：strcpy_s函數，開始由于沒有對cd開辟的空間做初始化為0的操作，造成了，函數多次彈出“buffer too small”的bug.

第三，HuffmanCoding函數中調用了一個SelectSubtree(...)函數，當然函數的定義如下，

void SelectSubtree( const HuffmanTree &HT,int limit,unsigned int & s1,unsigned int& s2 )

{

if (HT == NULL || limit<=0)

{

throw INVALID_PARAMETER;//參數異常

}

unsigned int min_1 = 0,min_2 =0;

for (int i = 1;i<=limit;i++)

{

if (HT[i].parent!=0)

{

continue;

}

else if (min_1==0)

{

min_1=i;

}

else if (min_2 == 0)

{

if (HT[i]<HT[min_1])

{//這里就利用了結構體中”<”運算符的作用，是不是看得很直觀啊！

min_2=min_1;

min_1=i;

}

else

{

min_2=i;

}

}

else if (HT[i]<HT[min_1])

{

min_2=min_1;

min_1=i;

}

else if (HT[i]<HT[min_2])

{

min_2 = i;

}

}

s1=min_1;

s2=min_2;

}

好了，到此，今天的blog已接近尾聲了，希望能幫助到難看的游客朋友，如果，你發現了其中的不足，請您提出您的的寶貴建議，讓我們共同提高，共同進步，本人的QQ：1272725，當然，要是你還有什么不明白的地方，也可以加本人的QQ聯系，或者留言，一起討論。謝謝……

總結

以上是生活随笔為你收集整理的huffman(赫夫曼编码)之C/C++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。