1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<
string.h>
4 #define OK 1
5 #define NO 0
6 #define True 1
7 #define FALSE 0
8 #define ERROR -1
9 #define MAX_TREE_SIZE 100
10
11 typedef
int Status;
12 typedef
struct
13 {
14 unsigned
int weight;
15 unsigned
int parent;
16 unsigned
int lchild;
17 unsigned
int rchild;
18 }HTNode;
19 typedef HTNode *
HuffmanTree;
20 typedef
char*
HCNode;
21 typedef HCNode*
HuffmanCode;
22
23 void InitTree_HT(HuffmanTree *
HT);
24
25 Status CreateHuffmanTree_HT(HuffmanTree *
HT);
26
27 Status Select_HT(HuffmanTree HT,
int end,
int *order_1,
int *order_2);
//在哈夫曼树结点中一次选出权值最小且未编入树的两个结点的序号order_1,order_2；
28
29 Status ShowHuffmanTree_HT(HuffmanTree HT);
30
31 Status HuffmanCoding_HT(HuffmanTree HT,HuffmanCode *HC);
//先序遍历计算哈夫曼编码值
32
33 void ShowHuffmanCode_HT(HuffmanTree HT,HuffmanCode HC);
34
35 int main (
int argc,
char**
argv){
36 HuffmanTree HT;
37 HuffmanCode HC;
38 printf(
"1\n函数InitTree_HT 测试..\n");
39 {
40 printf(
"初始化哈夫曼树 HT..\n");
41 InitTree_HT(&
HT);
42 printf(
"\n");
43 }
44 printf(
"2,3\n函数CreateHuffmanTree_HT等测试..\n");
45 {
46 printf(
"创建哈夫曼树HT..\n");
47 printf(
"作为示范，输入8个结点的权值（5，29，7，8，14，23，3，11）..\n");
48 CreateHuffmanTree_HT(&
HT);
49 printf(
"\n");
50 }
51 printf(
"5\n函数 ShowHuffmanTree_HT");
52 {
53 printf(
"展示哈夫曼树 HT=\n");
54 ShowHuffmanTree_HT(HT);
55 printf(
"\n");
56 }
57 printf(
"4\n函数HuffmanCoding_HT 测试..\n");
58 {
59 printf(
"计算哈夫曼编码 HC..\n");
60 HuffmanCoding_HT(HT,&
HC);
61 printf(
"\n");
62 }
63 printf(
"6\n函数ShowHuffmanCode_HT测试..\n");
64 {
65 printf(
"展示哈夫曼编码 HC = ");
66 ShowHuffmanCode_HT(HT,HC);
67 printf(
"\n");
68
69 }
70 }
71 void InitTree_HT(HuffmanTree *
HT){
72 *HT=
NULL;
73 }
74
75 Status CreateHuffmanTree_HT(HuffmanTree *
HT){
76 int m,n;
//n为叶子的个数，m为总的结点树 m=2*n-1
77 int w[MAX_TREE_SIZE];
78 HuffmanTree p;
79 int i;
80 int s1,s2;
81
82 printf(
"录入哈夫曼树叶子结点个数-->");
83 //scanf 要在用n之前给n幅值
84 scanf(
"%d",&
n);
85 printf(
"\n");
86 printf(
"依次录入各叶子结点的权值-->");
87 for(i=
1;i<=n;i++)
//0单元弃用
88 scanf(
"%d",&
w[i]);
89 printf(
"\n");
90 m=
2*n-
1;
//哈夫曼树的有效结点个数
91 *HT=(HuffmanTree)malloc((m+
1)*
sizeof(HTNode));
//0单元弃用,申请了m+1个连续的存储单元，其中首个单元*(HT)[0]用来存放叶子的数目
92 if(!(*
HT))
93 exit(ERROR);
94 (*HT)[
0].weight = n;
//利用0号单元的权值存储哈夫曼树叶子个数
95 for(i=
1;i<=m;i++
)
96 {
97 if(i<=
n)
98 (*HT)[i].weight=w[i];
//[1,2,……,n]叶子的结点
99 else
100 (*HT)[i].weight=
0;
//其余的双亲结点，权重都设置为0
101 (*HT)[i].parent=
0;
102 (*HT)[i].lchild=
0;
103 (*HT)[i].rchild=
0;
//初始化各个结点
104 }
105 for(i=n+
1;i<=m;i++
)
106 {
107 Select_HT(*HT,i-
1,&s1,&
s2);
108 /****************************************************************************************************************************
109 *本实现方法为，将所有的哈夫曼树的结点都按照静态链表存储起来，然后对于权重weight来说，首先是只有前n个结点中有权重，后面的 *
110 *全都被重置为0，然后从第n+1个结点开始操作，这个结点原本没有写入weight(为0)后来经过了Select_HT的遍历之后找到了前面没有使用 *
111 *过的两个最小的权重，并且将它们的父亲都设置成这个i+1,结点，相当与将这两个结点合并，然后在下一次进入这个循环的时候i变成了n *
112 *+2，然后这个时候遍历的就是前面n+1个结点，找出最小的weight，同时将这个时候的双亲设置成为n+2,但这个时候需要注意的是，不能够 *
113 *选取之前选过的结点，可以对他们添加一些标记，比如将它们的改变他们的父亲的值，这个之前已经改变过了，因此只要遍历的时候再增加*
114 *一次判断即可 *
115 ****************************************************************************************************************************/
116 (*HT)[s1].parent=(*HT)[s2].parent=
i;
117 (*HT)[i].lchild=
s1;
118 (*HT)[i].rchild=
s2;
119 (*HT)[i].weight=(*HT)[s1].weight+(*
HT)[s2].weight;
120 }
121 return OK;
122
123 }
124 Status Select_HT(HuffmanTree HT,
int end,
int *order_1,
int *
order_2){
125 //传进来的end是i-1因为i是要当双亲的结点
126 HuffmanTree p;
127 int i,count;
128 int m,n,tmp;
129 if(end<
2)
//此时只有一个结点,无法进行比较
130 return ERROR;
131 for(i=
1,count=
1;i<=end;i++)
//遍历找到前两个并没有被使用的weight
132 {
133 if(HT[i].parent==
0)
//只有还没有被使用才会进入循环
134 {
135 if(count==
1)
136 m=i;
//找到第一个位置
137 if(count==
2)
138 n=i;
//找到第二个位置
139 count++
;
140 }
141 if(count>
2)
//找到两个之后就结束跳出循环
142 break;
143 }
144 if(HT[m].weight>HT[n].weight)
//保证m的weight比较的小
145 {
146 tmp=
n;
147 n=
m;
148 m=
tmp;
149
150 }
151 i=(m>n?m:n)+
1;
//便于继续遍历找到下一个未使用的结点，找到m,n两者的较大值的后一个
152 while(i<=end)
//找到最小的两个weight
153 {
154 if(HT[i].parent==
0)
//同前
155 {
156 if(HT[i].weight<HT[m].weight)
//如果i的weight小 那么就选择i，m 将最小的i给m,第二小的m给n
157 {
158 n=
m;
159 m=
i;
160 }
161 else
162 {
163 if(HT[i].weight>=HT[m].weight&&HT[i].weight<HT[n].weight)
//如果i的weight在m,n之间，那么将i的权重给n,同时比较两者大的舍去
164 n=
i;
165 }
166 }
167 i++
;
168
169 }
170
171 *order_1=HT[m].weight<=HT[n].weight?m:n;
//最小的weigth
172 *order_2=HT[m].weight>HT[n].weight?m:n;
//第二小的weight
173 return OK;
174
175 }
176
177 Status ShowHuffmanTree_HT(HuffmanTree HT){
178 int i;
179 printf(
" ---------------------------------------- \n");
180 printf(
"┃*order┃weight┃parent┃lchild┃rchild┃\n");
181 for(i=
0;i<=
2*HT[
0].weight-
1;i++
)
182 {
183 if(i==
0)
184 printf(
"┃m┃m┃ * ┃ * ┃ * ┃\n",i,HT[i].weight);
185 else
186 printf(
"┃m┃m┃m┃m┃m┃\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
187 }
188 printf(
" ---------------------------------------- \n");
189 return OK;
190
191 }
192
193 Status HuffmanCoding_HT(HuffmanTree HT,HuffmanCode *
HC){
194 int m,n,i;
195 int cdlen;
196 int p,mark[MAX_TREE_SIZE];
//mark用来标记访问的次数
197 char *code;
//用来存储编码 赋值给HC
198
199 n=HT[
0].weight;
//哈夫曼树叶子结点个数
200 m=
2*n-
1;
//哈夫曼树结点个数
201
202 *HC=(HuffmanCode)malloc((n+
1)*
sizeof(HCNode));
203 if(!(*
HC))
204 exit(ERROR);
205 code=(
char*)malloc(n*
sizeof(
char));
206 if(!
code)
207 exit(ERROR);
208 for(i=
1;i<=n;i++
)
209 code[i]=
'\0';
210 for(i=
1;i<=m;i++
)
211 mark[i]=
0;
//0，1，2分别表示访问零次一次两次
212 p=
m;
213 cdlen=
0;
214 /*对于每一个结点p，都会经历2次访问，最后退回到父亲的结点，因此一层层递归之后，最后会回到根节点的上一个也就是之前定义过的0结束循环*/
215 while(p)
216 {
217 if(mark[p]==
0)
//第一次访问这个结点
218 {
219 mark[p]=
1;
//左孩子不存在，那么这个时候就只是执行了mark[p]=1，下次就不会直接进来
220 if(HT[p].lchild!=
0)
//从根结点的向左访问
221 {
222 p=HT[p].lchild;
//p向左走一步
223 code[cdlen]=
'0';
//走左边就给一个0
224 cdlen++
;
225 }
226 else
227 {
228 if(HT[p].rchild==
0)
//找到叶子结点
229 {
230 (*HC)[p]=(
char*)malloc((cdlen+
1)*
sizeof(
char));
//+1是为了放置最后的'\0'，指针数组中存放的是一个指针，
231 //所以p不一样的时候会指向不同的地方
232 strcpy((*HC)[p],code);
//复制编码串
233 }
234 }
235
236 }
237 else //左孩子不存在的时候，这个时候右孩子可能存在，因为右孩子是不是0都会进入这里
238 {
239 if(mark[p]==
1)
//第二次访问，当
240 {
241 mark[p]=
2;
242 if(HT[p].rchild!=
0)
//如果右孩子存在，那么这个时候由于之前判断了左孩子不存在，所以p不是叶子，因此继续往右并给编码1
243 {
244 p=
HT[p].rchild;
245 code[cdlen]=
'1';
246 cdlen++;
//这个时候code继续加长
247 }
248
249 //先标记p为2，如果p的右孩子不存在的话
250 }
251
252 /*
253 当p的右孩子是0的时候，进行第三次访问，由于在第一个if中就已经用strcpy将code字符串的值给了HC的指针所以可以直接返回p
254 并且在字符串的尾部加上‘\0’
255 */
256 else
257 {
258 p=HT[p].parent;
//退回父亲之后，之前的在的code的最右边的值需要抹掉，重新让结点访问，相当于后进先出的栈结构
259 cdlen--
;
260 code[cdlen]=
'\0';
261 }
262
263 }
264
265 }
266 free(code);
267
268 return OK;
269
270 }
271
272 void ShowHuffmanCode_HT(HuffmanTree HT,HuffmanCode HC){
273 int i;
274 printf(
" ------------------------------------ \n");
275 printf(
"┃*order┃weight┃ ┃ 哈夫曼编码 ┃\n");
276 for(i=
1;i<=HT[
0].weight;i++
)
277 {
278
279 printf(
"┃m┃m┃----->s┃\n",i,HT[i].weight,HC[i]);
280 }
281 printf(
" ---------------------------------------- \n");
282
283
284
285 }
参考：http://www.cnblogs.com/kangjianwei101/p/5222014.html
转载于:https://www.cnblogs.com/lovecodepql/p/7712770.html
相关资源：数据结构—成绩单生成器
