程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一步一步寫算法(之哈夫曼樹 下)

一步一步寫算法(之哈夫曼樹 下)

編輯:關於C語言

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱: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)算法注意復用,這裡就用到了原來講到的通用算法內容

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved