构造哈夫曼树并求哈夫曼编码的算法实现

1 #define HUGE 999
2 #define N 8
3 #define M 2*N-1
4 struct HuffmanNode {
5 int weight;
6 int parent;
7 int left;
8 int right;
9 };
10 struct HuffmanCode {
11 int bit[10];
12 int start;
13 };
14 int weight[] = {5,29,7,8,14,23,3,11,0,0,0,0,0,0,0};
15 struct HuffmanNode HT[M];
16 struct HuffmanCode HC[N];
17
18 void init()
19 {
20 int i;
21 for (i=0;i22 HT[i].parent = -1;
23 HT[i].weight = weight[i];
24 HT[i].left = -1;
25 HT[i].right = -1;
26 }
27 }
28
29 int minimum()
30 {
31 int i,k;
32 int min = HUGE;
33 for (i=0;i34 if (min>weight[i] && weight[i] != 0) {
35 min = weight[i];
36 k = i;
37 }
38 weight[k] = HUGE;
39 return k;
40 }
41
42 void huffmantree()
43 {
44 int i,l,r;
45 for (i=N;i46 l = minimum();
47 r = minimum();
48 HT[l].parent = i;
49 HT[r].parent = i;
50 HT[i].left = l;
51 HT[i].right = r;
52 HT[i].weight = HT[l].weight + HT[r].weight;
53 weight[i] = HT[i].weight;
54 }
55 }
56
57 void huffmancode()
58 {
59 int i,p,j,c;
60 struct HuffmanCode cd;
61 for(i=0;i62 cd.start = N-1;
63 c = i;
64 p = HT[c].parent;
65 while (p != 0) {
66 if (HT[p].left == c)
67 cd.bit[cd.start] = 0;
68 else cd.bit[cd.start] = 1;
69 cd.start--;
70 c = p;
71 p = HT[c].parent;
72 }
73 for(j=cd.start+1;j74 HC[i].start = cd.start;
75 }
76 }
77
78 void main()
79 {
80 int i,j;
81 clrscr();
82 init();
83 huffmantree();
84 for (i=0;i85 printf("%3d%3d%3d%3d\n",HT[i].weight,HT[i].parent,
HT[i].left,HT[i].right);
86 printf("\n");
87 huffmancode();
88 for (i=0;i89 printf("%5d: ",HT[i].weight);
90 for (j=HC[i].start+1;j91 printf("%d ",HC[i].bit[j]);
92 printf("\n");
93 }
94 }