HuffmanTree 霍夫曼树实现

操作环境：

1. IDE Clion
2. 编译器：VS2020

代码实现

#include 
#include "stdlib.h"
#include "string.h"typedef struct {int weight;int parent, lChild, rChild;
}htNode, *huffmanTree;typedef char * *huffmanCode ;void traverseHuffmanCode(huffmanCode hc, int n, char ele[]);int com(int minW1, int minW2, huffmanTree ht, int j){if ((ht + j)->parent == 0 && minW2 > (ht + j)->weight && minW2 > minW1){return 0;}if((ht + j)->parent == 0 && minW1 > (ht + j)->weight){return 1;} else if ((ht + j)->parent == 0 && minW2 > (ht + j)->weight){return 2;}return -1;
}void select(huffmanTree ht, int i, int *s1, int *s2){int minW1 = INT_MAX, minW2 = INT_MAX;for (int j = 1; j <= i; ++j) {switch (com(minW1, minW2, ht, j)) {case 0:*s2 = *s1;*s1 = j;minW2 = minW1;minW1 = (ht + j)->weight;break;case 1:*s1 = j;minW1 = (ht + j)->weight;break;case 2:*s2 = j;minW2 = (ht + j)->weight;break;}}}void huffmanCoding(huffmanTree *ht, huffmanCode *hc, int *w, int n){if(n <= 1) return;int m = 2 * n - 1;*ht = (huffmanTree)malloc(sizeof(htNode) * (m + 1));huffmanTree p = (*ht) + 1;int i = 1;for (; i <= n; ++i, ++p, ++w){p->weight = *w;p->lChild = p->rChild = p->parent = 0;}for (i = n + 1; i<=m; ++i){int s1 = 0,s2 = 0;select(*ht, i-1, &s1, &s2);(*ht + s1)->parent = i;(*ht + s2)->parent = i;(*ht + i)->lChild = s1;(*ht + i)->rChild = s2;(*ht + i)->weight = (*ht + s1)->weight + (*ht + s2)->weight;(*ht + i)->parent = 0;}*hc = (huffmanCode)malloc(sizeof(char *) * (n + 1));char *cd = (char *)malloc(n * sizeof(char));cd[n-1] = '\0';for (int j = 1; j <= n; ++j) {int start = n-1;int c = j;int f = (*ht + j)->parent;for (; f!=0; c = f, f = (*ht + f)->parent){if ((*ht + f)->lChild == c){cd[--start] = '1';} else{cd[--start] = '0';}}*(*hc + j) = (char *)malloc((n- start) * sizeof(char));for (int k = 0; k < n - start; ++k) {*(*(*hc + j)+k) = *(cd + start + k);}}free(cd);}void traverseHuffmanCode(huffmanCode hc, int n, char ele[]){for (int i = 1; i <= n; ++i) {int k = 0;printf("%c: ", ele[i-1]);while (*(*(hc + i)+k)!='\0'){printf("%c", *(*(hc + i)+k));k++;}printf("\n");}}void traverseHuffmanTree(huffmanTree ht, int n){int len = 2 * n;printf("the huffman tree is:\n");printf("---------------------\n");for (int i = 1; i < len; ++i) {huffmanTree ht_i = (ht + i);printf("|%3d %3d %3d %3d %3d|\n", i, ht_i->weight, ht_i->parent, ht_i->lChild, ht_i->rChild);}printf("---------------------\n");
}
int main() {char ele[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};int weight[] = {5, 29, 7, 8, 14, 23, 3, 11};huffmanTree ht = NULL;huffmanCode hc = NULL;huffmanCoding(&ht, &hc, weight, 8);traverseHuffmanCode(hc, 8, ele);traverseHuffmanTree(ht, 8);printf("\nHello, World!\n");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！