一步一步写算法（之哈夫曼树 下）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：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));
补充：软件开发 , C语言 ,
