数据结构（四）树—哈夫曼树了解以及代码实现 #include “huffman.h” #include “queue.h” #include <stdio.h> #include <stdlib.h> //根据字符串创建霍夫曼树 htTree* buildTree(char* str) { //先创建一个字符统计数组 int proprity[256] = { 0 }; for (int j = 0; j < strlen(str);j++) { proprity[(unsigned char)str[j]]++; } //创建一个队列，利用队列来创建一个完整的霍夫曼树 pQueue *queue; initPQueue(&queue); for (int k = 0; k < 256;k++) { if (proprity[k]!=0) { htNode* hn = (htNode*)malloc(sizeof(htNode)); hn->left = NULL; hn->right = NULL; hn->symbol = (char)k; addPQueue(&queue, hn, proprity[k]); } } //将所有队列中的数据开始合并 while (queue->size != 1) { htNode* left, *right,*tnode; //优先级必须从这里 int proprity = queue->first->priority; proprity += queue->first->next->priority; //下面返回的是霍夫曼结点，其中不含有优先级 left = getPQueue(&queue); right = getPQueue(&queue); tnode = (htNode*)malloc(sizeof(htNode)); tnode->left = left; tnode->right = right; addPQueue(&queue, tnode, proprity); } //队列中最后一个素就是霍夫曼树的根节点，我们将它赋值给霍夫曼树即可 htTree *ht = (htTree*)malloc(sizeof(htTree)); ht->root = getPQueue(&queue); return ht; } //我们通过遍历到二叉树叶子节点，从而到前缀码 void preOrderGetTb(htNode* root,hlTable table,int level, char* code) { if (root->left||root->right) { if (root->left) { code[level] = ‘0’; preOrderGetTb(root->left, table,level+1,code); } if (root->right) { code[level] = ‘1’; preOrderGetTb(root->right, table, level + 1, code); } } else { code[level] = ‘0’; hlNode* aux = (hlNode*)malloc(sizeof(hlNode)); aux->symbol = root->symbol; aux->code = (char*)malloc(sizeof(char)*(level + 1)); strcpy(aux->code, code); aux->next = NULL; if ((*table)->first==NULL) { (*table)->first = aux; (*table)->last = aux; } else { (*table)->last->next = aux; (*table)->last = aux; } } } //根据霍夫曼树创建霍夫曼前缀码表 hlTable* buildTable(htTree* HT) { hlTable* hl; hl = (hlTable*)malloc(sizeof(hlTable)); hl->first = NULL; hl->last = NULL; int k = 0; char code[255] = { 0 }; preOrderGetTb(HT->root, &hl, k, code); return hl; } //根据字符串进行编码，str是一串ASCII码字符串 void encode(hlTable* table, char *str) { hlNode* cur = table->first; char *s = str; while (*s!=’0′) { while (cur->symbol!=*s) cur = cur->next; printf(“%s”, cur->code); s++; cur = table->first; } } //根据霍夫曼树，进行解码,str类似于’00001101′ void decode(htTree* ht, char *str) { char* s = str; htNode* tn = ht->root; while (*s!=’0′) { if (*s==’0′) { tn = tn->left; if (!tn->left&&!tn->right) { printf(“%c”, tn->symbol); tn = ht->root; } } else { tn = tn->right; if (!tn->left&&!tn->right) { printf(“%c”, tn->symbol); tn = ht->root; } } s++; } }
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/56007.html
