返回首页 一步一步写算法

哈夫曼树 下

前面说到了哈夫曼树的创建,那下面一个重要的环节就是哈夫曼树的排序问题。但是由于排序的内容是数据结构,因此形式上说,我们需要采用通用数据排序算法,这在我之前的博客里面已经涉及到了(通用算法设计)。所以,我们所要做的就是编写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;  
}  

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;  
}  

有了创建函数和排序函数,那么哈夫曼树就可以创建了,

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 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)算法注意复用,这里就用到了原来讲到的通用算法内容

上一篇: 哈夫曼树 上 下一篇: 回数