首页 > 代码库 > 一步一步写算法(之哈夫曼树 下)
一步一步写算法(之哈夫曼树 下)
原文: 一步一步写算法(之哈夫曼树 下)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱: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;}
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)算法注意复用,这里就用到了原来讲到的通用算法内容
一步一步写算法(之哈夫曼树 下)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。