6-01 2,468 views
编码字符：”w”,”o”,”r”,”l”,”d”，权重值4,2,1,5,7。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include <stdlib.h> #include <stdio.h> typedef struct Node{ int value; int parent; }Node,*HTree; void printCode(HTree tree,int l,int i); int main() { int i,j; int w[5]={4,2,1,5,7}; int n = 5; HTree tree = (Node*)malloc(sizeof(Node)*(2*n-1)); //贪心策略构造Huffman树 for (i=0;i<n;i++) { tree[i].value = w[i]; tree[i].parent = 0; } for (i=n;i<2*n-1;i++) { int min1 = -1; int min2 = -1; for (j=0;j<i;j++) { if (tree[j].parent == 0) { if (min1 == -1) min1 = j; else if (min2 == -1) { min2 = j; if (tree[min1].value>tree[min2].value) { int temp = min1; min1 = min2; min2 = temp; } } else { if (tree[j].value<tree[min1].value) { min2 = min1; min1 = j; } else if (tree[j].value<tree[min2].value) { min2 = j; } } } } tree[min1].parent = i; tree[min2].parent = i; tree[i].parent = 0; tree[i].value = tree[min1].value+tree[min2].value; } //递归输出Huffman编码 for (i=0;i<n;i++) { printCode(tree,2*n-1,i); printf("\r\n"); } return 0; } void printCode(HTree tree,int l,int i) { if (tree[i].parent == 0) return; printCode(tree,l,tree[i].parent); if ((tree[tree[i].parent].value-tree[i].value)>tree[i].value) printf("0"); else printf("1"); } |
结果：
01
001
000
10
11
