C++算法之哈夫曼树
发布时间:2020-12-16 07:44:28 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 在数据传输的过程当中,我们总是希望用尽可能少的带宽传输更多的数据,哈夫曼就是其中的一种较少带宽传输的方法。哈夫曼的基本思想不复杂,那就是对于
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考
在数据传输的过程当中,我们总是希望用尽可能少的带宽传输更多的数据,哈夫曼就是其中的一种较少带宽传输的方法。哈夫曼的基本思想不复杂,那就是对于出现频率高的数据用短字节表示,对于频率比较低得数据用长字节表示。 ??比如说,现在有4个数据需要传输,分别为A、B、C、D,所以一般来说,如果此时没有考虑四个数据出现的概率,那么我们完全可以这么分配,平均长度为2,
/* * A - 00 B - 01 * C - 10 D - 11 */????但是,现在条件发生了改变,四个数据出现的频率并不一样,分别为0.1/0.2/0.3/0.4。那么这时候应该怎么分配长度呢,其实也简单。我们只要把所有数据按照频率从低到高排列,每次取前两位合并成新的节点,再把这个新节点放到队列中重新排序即可。新节点的左结点默认设为1,右结点默认设为0。然后重复上面的过程,直到所有的节点都合并成一个节点为止。如果应用到实际的示例中,合并的过程应该是这样的, ????第一步,首先合并A和B,因为A和B是概率最小的 /* * * total_1(0.3) C (0.3) D(0.4) * / * A(0.1) B(0.2) */????第二步,接着合并total_1和C, /* * total_2 (0.6) * / * total_1(0.3) C (0.3) D(0.4) * / * A(0.1) B(0.2) */????最后一步,合并total_2和D, /* * final (1.0) * / * D (0.4) total_2 (0.6) * / * total_1(0.3) C (0.3) * / * A(0.1) B(0.2) */ //该代码片段来自于: http://www.sharejs.com/codes/cpp/6552????所以按照上面的生成树,数据的编号应该这么安排, /* * A - 011 B - 010 * C - 00 D - 1 */????看上去A和B的长度还增加了,但是D的长度减少了。那么整个数据的平均长度有没有减少呢?我们可以计算一下。3?*?0.1?+?3?*?0.2?+?2?*?0.3?+?0.4?=?1.9?<?2。我们发现调整后的数据平均长度比原来减少了近(2?-?1.9)/2?*?100%?=?10?%,这可是巨大的发现啊。 ????为了完成整个哈夫曼树的创建,我们还需要定义一个数据结构: typedef struct _HUFFMAN_NODE { char str; double frequence; int symbol; struct _HUFFMAN_NODE* left; struct _HUFFMAN_NODE* right; struct _HUFFMAN_NODE* parent; }HUFFMAN_NODE; //该代码片段来自于: http://www.sharejs.com/codes/cpp/6552????其中str记录字符,frequency记录字符出现的频率,?symbol记录分配的数据,左子树为1、右子树为0,left为左子树,right为右子树,parent为父节点。接下来,我们从创建huffman结点开始。 HUFFMAN_NODE* create_new_node(char str,double frq) { HUFFMAN_NODE* pNode = (HUFFMAN_NODE*)malloc(sizeof(HUFFMAN_NODE)); assert(NULL != pNode); pNode->str = str; pNode->frequence = frq; pNode->symbol = -1; pNode->left = NULL; pNode->right = NULL; pNode->parent = NULL; return pNode; }???前面说到了哈夫曼树的创建,那下面一个重要的环节就是哈夫曼树的排序问题。但是由于排序的内容是数据结构,因此形式上说,我们需要采用通用数据排序算法,这在我之前的博客里面已经涉及到了(通用算法设计)。所以,我们所要做的就是编写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(' ',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)算法注意复用,这里就用到了原来讲到的通用算法内容 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |