本节主要来自书本《大话数据结构》,挺容易看懂的。
另附Huffman编码代码,代码来自:
https://www.cnblogs.com/kubixueshen
1 //haffman 树的结构
2 typedef struct
3 {
4 //叶子结点权值
5 unsigned int weight;
6 //指向双亲,和孩子结点的指针
7 unsigned int parent;
8 unsigned int lChild;
9 unsigned int rChild;
10 } Node, *HuffmanTree;
11
12 //动态分配数组,存储哈夫曼编码
13 typedef char *HuffmanCode;
14
15 //选择两个parent为0,且weight最小的结点s1和s2的方法实现
16 //n 为叶子结点的总数,s1和 s2两个指针参数指向要选取出来的两个权值最小的结点
17 void select(HuffmanTree *huffmanTree, int n, int *s1, int *s2)
18 {
19 //标记 i
20 int i = 0;
21 //记录最小权值
22 int min;
23 //遍历全部结点,找出单节点
24 for(i = 1; i <= n; i++)
25 {
26 //如果此结点的父亲没有,那么把结点号赋值给 min,跳出循环
27 if((*huffmanTree)[i].parent == 0)
28 {
29 min = i;
30 break;
31 }
32 }
33 //继续遍历全部结点,找出权值最小的单节点
34 for(i = 1; i <= n; i++)
35 {
36 //如果此结点的父亲为空,则进入 if
37 if((*huffmanTree)[i].parent == 0)
38 {
39 //如果此结点的权值比 min 结点的权值小,那么更新 min 结点,否则就是最开始的 min
40 if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight)
41 {
42 min = i;
43 }
44 }
45 }
46 //找到了最小权值的结点,s1指向
47 *s1 = min;
48 //遍历全部结点
49 for(i = 1; i <= n; i++)
50 {
51 //找出下一个单节点,且没有被 s1指向,那么i 赋值给 min,跳出循环
52 if((*huffmanTree)[i].parent == 0 && i != (*s1))
53 {
54 min = i;
55 break;
56 }
57 }
58 //继续遍历全部结点,找到权值最小的那一个
59 for(i = 1; i <= n; i++)
60 {
61 if((*huffmanTree)[i].parent == 0 && i != (*s1))
62 {
63 //如果此结点的权值比 min 结点的权值小,那么更新 min 结点,否则就是最开始的 min
64 if((*huffmanTree)[i].weight < (*huffmanTree)[min].weight)
65 {
66 min = i;
67 }
68 }
69 }
70 //s2指针指向第二个权值最小的叶子结点
71 *s2 = min;
72 }
73
74 //创建哈夫曼树并求哈夫曼编码的算法如下,w数组存放已知的n个权值
75 void createHuffmanTree(HuffmanTree *huffmanTree, int w[], int n)
76 {
77 //m 为哈夫曼树总共的结点数,n 为叶子结点数
78 int m = 2 * n - 1;
79 //s1 和 s2 为两个当前结点里,要选取的最小权值的结点
80 int s1;
81 int s2;
82 //标记
83 int i;
84 // 创建哈夫曼树的结点所需的空间,m+1,代表其中包含一个头结点
85 *huffmanTree = (HuffmanTree)malloc((m + 1) * sizeof(Node));
86 //1--n号存放叶子结点,初始化叶子结点,结构数组来初始化每个叶子结点,初始的时候看做一个个单个结点的二叉树
87 for(i = 1; i <= n; i++)
88 {
89
90 //其中叶子结点的权值是 w【n】数组来保存
91 (*huffmanTree)[i].weight = w[i];
92 //初始化叶子结点(单个结点二叉树)的孩子和双亲,单个结点,也就是没有孩子和双亲,==0
93 (*huffmanTree)[i].lChild = 0;
94 (*huffmanTree)[i].parent = 0;
95 (*huffmanTree)[i].rChild = 0;
96 }// end of for
97 //非叶子结点的初始化
98 for(i = n + 1; i <= m; i++)
99 {
100 (*huffmanTree)[i].weight = 0;
101 (*huffmanTree)[i].lChild = 0;
102 (*huffmanTree)[i].parent = 0;
103 (*huffmanTree)[i].rChild = 0;
104 }
105
106 printf("\n HuffmanTree: \n");
107 //创建非叶子结点,建哈夫曼树
108 for(i = n + 1; i <= m; i++)
109 {
110 //在(*huffmanTree)[1]~(*huffmanTree)[i-1]的范围内选择两个parent为0
111 //且weight最小的结点,其序号分别赋值给s1、s2
112 select(huffmanTree, i-1, &s1, &s2);
113 //选出的两个权值最小的叶子结点,组成一个新的二叉树,根为 i 结点
114 (*huffmanTree)[s1].parent = i;
115 (*huffmanTree)[s2].parent = i;
116 (*huffmanTree)[i].lChild = s1;
117 (*huffmanTree)[i].rChild = s2;
118 //新的结点 i 的权值
119 (*huffmanTree)[i].weight = (*huffmanTree)[s1].weight + (*huffmanTree)[s2].weight;
120
121 printf("%d (%d, %d)\n", (*huffmanTree)[i].weight, (*huffmanTree)[s1].weight, (*huffmanTree)[s2].weight);
122 }
123
124 printf("\n");
125 }
126
127 //哈夫曼树建立完毕,从 n 个叶子结点到根,逆向求每个叶子结点对应的哈夫曼编码
128 void creatHuffmanCode(HuffmanTree *huffmanTree, HuffmanCode *huffmanCode, int n)
129 {
130 //指示biaoji
131 int i;
132 //编码的起始指针
133 int start;
134 //指向当前结点的父节点
135 int p;
136 //遍历 n 个叶子结点的指示标记 c
137 unsigned int c;
138 //分配n个编码的头指针
139 huffmanCode=(HuffmanCode *)malloc((n+1) * sizeof(char *));
140 //分配求当前编码的工作空间
141 char *cd = (char *)malloc(n * sizeof(char));
142 //从右向左逐位存放编码,首先存放编码结束符
143 cd[n-1] = '\0';
144 //求n个叶子结点对应的哈夫曼编码
145 for(i = 1; i <= n; i++)
146 {
147 //初始化编码起始指针
148 start = n - 1;
149 //从叶子到根结点求编码
150 for(c = i, p = (*huffmanTree)[i].parent; p != 0; c = p, p = (*huffmanTree)[p].parent)
151 {
152 if( (*huffmanTree)[p].lChild == c)
153 {
154 //从右到左的顺序编码入数组内
155 cd[--start] = '0'; //左分支标0
156 }
157 else
158 {
159 cd[--start] = '1'; //右分支标1
160 }
161 }// end of for
162 //为第i个编码分配空间
163 huffmanCode[i] = (char *)malloc((n - start) * sizeof(char));
164
165 strcpy(huffmanCode[i], &cd[start]);
166 }
167
168 free(cd);
169 //打印编码序列
170 for(i = 1; i <= n; i++)
171 {
172 printf("HuffmanCode of %3d is %s\n", (*huffmanTree)[i].weight, huffmanCode[i]);
173 }
174
175 printf("\n");
176 }
177
178 int main(void)
179 {
180 HuffmanTree HT;
181 HuffmanCode HC;
182 int *w,i,n,wei,m;
183
184 printf("\nn = " );
185
186 scanf("%d",&n);
187
188 w=(int *)malloc((n+1)*sizeof(int));
189
190 printf("\ninput the %d element's weight:\n",n);
191
192 for(i=1; i<=n; i++)
193 {
194 printf("%d: ",i);
195 fflush(stdin);
196 scanf("%d",&wei);
197 w[i]=wei;
198 }
199
200 createHuffmanTree(&HT, w, n);
201 creatHuffmanCode(&HT,&HC,n);
202
203 return 0;
204 }
评论(0)
您还未登录,请登录后发表或查看评论