【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
前面說到了哈夫曼樹的創建，那下面一個重要的環節就是哈夫曼樹的排序問題。但是由於排序的內容是數據結構，因此形式上說，我們需要采用通用數據排序算法，這在我之前的博客裡面已經涉及到了（通用算法設計）。所以，我們所要做的就是編寫compare和swap兩個函數。通用冒泡代碼如下所示，
void bubble_sort(void* array[], int length, int (*compare)(void*, void*), void(*swap)(void**, void**))
{
int outer;
int inner;
for(outer = length -1; outer >0; outer --){
for(inner = 0; inner < outer; inner ++){
if(compare(array[inner], array[inner + 1]))
swap(&array[inner], &array[inner + 1]);
}
}
return;
}
void bubble_sort(void* array[], int length, int (*compare)(void*, void*), void(*swap)(void**, void**))
{
int outer;
int inner;
for(outer = length -1; outer >0; outer --){
for(inner = 0; inner < outer; inner ++){
if(compare(array[inner], array[inner + 1]))
swap(&array[inner], &array[inner + 1]);
}
}
return;
}
compare和swap代碼如下所示，
int compare (void* a, void* b)
{
HUFFMAN_NODE* node1 = (HUFFMAN_NODE*)a;
HUFFMAN_NODE* node2 = (HUFFMAN_NODE*)b;
return node1->frequence > node2->frequence ? 1 : 0;
}
void swap(void** a, void** b)
{
HUFFMAN_NODE* median;
HUFFMAN_NODE** node1 = (HUFFMAN_NODE**)a;
HUFFMAN_NODE** node2 = (HUFFMAN_NODE**)b;
median = *node1;
*node1 = *node2;
*node2 = median;
}
int compare (void* a, void* b)
{
HUFFMAN_NODE* node1 = (HUFFMAN_NODE*)a;
HUFFMAN_NODE* node2 = (HUFFMAN_NODE*)b;
return node1->frequence > node2->frequence ? 1 : 0;
}
void swap(void** a, void** b)
{
HUFFMAN_NODE* median;
HUFFMAN_NODE** node1 = (HUFFMAN_NODE**)a;
HUFFMAN_NODE** node2 = (HUFFMAN_NODE**)b;
median = *node1;
*node1 = *node2;
*node2 = median;
}
有了創建函數和排序函數，那麼哈夫曼樹就可以創建了，
HUFFMAN_NODE* create_huffman_tree(HUFFMAN_NODE* huffmanNode[], int length)
{
HUFFMAN_NODE* head = NULL;
if(NULL == huffmanNode || length <= 1)
return NULL;
while(length > 1){
bubble_sort((void**)huffmanNode, length, compare, swap);
head = create_new_node('\0', huffmanNode[0]->frequence + huffmanNode[1]->frequence);
assert(NULL != head);
head->left = huffmanNode[0];
head->right = huffmanNode[1];
huffmanNode[0]->parent = head;
huffmanNode[0]->symbol = 1;
huffmanNode[1]->parent = head;
huffmanNode[1]->symbol = 0;
memmove(&huffmanNode[0], &huffmanNode[2], sizeof(HUFFMAN_NODE*) * (length -2));
huffmanNode[length -2] = head;
length --;
}
return head;
}
HUFFMAN_NODE* create_huffman_tree(HUFFMAN_NODE* huffmanNode[], int length)
{
HUFFMAN_NODE* head = NULL;
if(NULL == huffmanNode || length <= 1)
return NULL;
while(length > 1){
bubble_sort((void**)huffmanNode, length, compare, swap);
head = create_new_node('\0', huffmanNode[0]->frequence + huffmanNode[1]->frequence);
assert(NULL != head);
head->left = huffmanNode[0];
head->right = huffmanNode[1];
huffmanNode[0]->parent = head;
huffmanNode[0]->symbol = 1;
huffmanNode[1]->parent = head;
huffmanNode[1]->symbol = 0;
memmove(&huffmanNode[0], &huffmanNode[2], sizeof(HUFFMAN_NODE*) * (length -2));
huffmanNode[length -2] = head;
length --;
}
return head;
} 上面的代碼完整了寫出了huffman樹的創建過程，那麼我們怎麼知道符號的編碼是多少呢？這其實不難，因為根節點都知道了，我們只要按照自下而上的順序遍歷節點就可以打印出編碼，只不過編碼是逆序的而已，
void print_code_for_str(HUFFMAN_NODE* pNode, HUFFMAN_NODE* head)
{
if(NULL == pNode || NULL == head)
return;
while(head != pNode){
printf("%d", pNode->symbol);
pNode = pNode->parent;
}
return;
}
void print_code_for_str(HUFFMAN_NODE* pNode, HUFFMAN_NODE* head)
{
if(NULL == pNode || NULL == head)
return;
while(head != pNode){
printf("%d", pNode->symbol);
pNode = pNode->parent;
}
return;
}
如果對代碼本身還有懷疑，可以編譯一個測試用例驗證一下，
void test()
{
HUFFMAN_NODE* node1 = NULL;
HUFFMAN_NODE* node2 = NULL;
HUFFMAN_NODE* node3 = NULL;
HUFFMAN_NODE* node4 = NULL;
HUFFMAN_NODE* test[] = {node1 = create_new_node('a', 0.1),
node2 = create_new_node('b', 0.2),
node3 = create_new_node('c', 0.3),
node4 = create_new_node('d', 0.4),
};
HUFFMAN_NODE* head = create_huffman_tree(test, sizeof(test)/sizeof(HUFFMAN_NODE*));
print_code_for_str(node1, head);
print_code_for_str(node2, head);
print_code_for_str(node3, head);
print_code_for_str(node4, head);
}
void test()
{
HUFFMAN_NODE* node1 = NULL;
HUFFMAN_NODE* node2 = NULL;
HUFFMAN_NODE* node3 = NULL;
HUFFMAN_NODE* node4 = NULL;
HUFFMAN_NODE* test[] = {node1 = create_new_node('a', 0.1),
node2 = create_new_node('b', 0.2),
node3 = create_new_node('c', 0.3),
node4 = create_new_node('d', 0.4),
};
HUFFMAN_NODE* head = create_huffman_tree(test, sizeof(test)/sizeof(HUFFMAN_NODE*));
print_code_for_str(node1, head);
print_code_for_str(node2, head);
print_code_for_str(node3, head);
print_code_for_str(node4, head);
}
總結：
（1）哈夫曼樹不復雜，如果手算可以成功，那麼編程應該也沒有什麼問題
（2）復雜算法都是由小算法搭積木而成的，朋友們應該在基本算法上打下堅實的基礎
（3）算法注意復用，這裡就用到了原來講到的通用算法內容
