前面說(shuō)到了哈夫曼樹(shù)的創(chuàng )建，那下面一個(gè)重要的環(huán)節就是哈夫曼樹(shù)的排序問(wèn)題。但是由于排序的內容是數據結構，因此形式上說(shuō)，我們需要采用通用數據排序算法，這在我之前的博客里面已經(jīng)涉及到了（通用算法設計）。所以，我們所要做的就是編寫(xiě)compare和swap兩個(gè)函數。通用冒泡代碼如下所示，
- 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;
- }
有了創(chuàng )建函數和排序函數，那么哈夫曼樹(shù)就可以創(chuàng )建了，
- 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;
- }
上面的代碼完整了寫(xiě)出了huffman樹(shù)的創(chuàng )建過(guò)程，那么我們怎么知道符號的編碼是多少呢？這其實(shí)不難，因為根節點(diǎn)都知道了，我們只要按照自下而上的順序遍歷節點(diǎn)就可以打印出編碼，只不過(guò)編碼是逆序的而已，
- 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;
- }
如果對代碼本身還有懷疑，可以編譯一個(gè)測試用例驗證一下，
- 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）哈夫曼樹(shù)不復雜，如果手算可以成功，那么編程應該也沒(méi)有什么問(wèn)題
（2）復雜算法都是由小算法搭積木而成的，朋友們應該在基本算法上打下堅實(shí)的基礎
（3）算法注意復用，這里就用到了原來(lái)講到的通用算法內容
