数据结构实验哈夫曼编译码.docx
《数据结构实验哈夫曼编译码.docx》由会员分享，可在线阅读，更多相关《数据结构实验哈夫曼编译码.docx（16页珍藏版）》请在冰点文库上搜索。
数据结构实验哈夫曼编译码
实验九哈夫曼编译码
1.实验目的
（1）掌握哈夫曼树的特性。
（2）掌握哈夫曼树的建立算法。
（3）掌握哈夫曼编码算法。
（4）掌握哈夫曼译码算法。
2.实验内容
（1）建立哈夫曼树。
（2）输出哈夫曼编码。
（3）根据输入串进行哈夫曼译码
3.实验要求
（1）根据实验内容编写程序，上机调试并获得运行结果
（2）撰写实验报告
4.关键步骤思路与算法
（1）构造哈弗曼树
算法思路；
若已知有n个叶结点，则构造的哈夫曼树有2n-1个结点。
①先输入字符集中的n个字符（叶结点）和表示其概率分布的权值，存储在ht（ HuffNode型）数组的前n个数组元素中.然后将2n-1个结点的双亲和左右孩子均置为0。
②在所有的结点中，选取双亲为0，且具有最小权值m1和次小权值m2的两个结点，用p1和p2指示这两个结点在数组中的位置.将根为ht［p1］和ht［p2］的两棵树合并，使其成为新结点ht［i］的左右孩子，ht［i］的权值为最小权值m1和次小权值m2之和；ht[p1]和ht［p2］的双亲指向i。
重复上述过程，共进行n-1次合并就构造了一棵 Huffman树。
当进行n-1次合并时，产生n-1个结点，次放入ht数组中，数组的下标从n到2n-2
算法如下；
1.//构造哈弗曼树
2.int Huffman（HuffNode *hf）
3.{
4. int i,k,n,m1,m2,p1,p2;
5. printf（"请输入元素的个素:
"）;
6. scanf（"%d",&n）;
7. for（i = 1;i <= n;i++）
8. {
9. getchar（）;//接收回车,如果不加这条语句，那么当输入完权重时，会按"\n"，就会被下一次输入值时被接收，于是就会出错
10. printf（"请输入第%d元素的=>\n\t节点值：
",i）;
11. scanf（"%c",&（hf[i].data））;//hf可以当做数组来用,因为hf[i]在这里不是一个指针，而是一个结构体，所以可以直接使用.运算符来调用data
12. printf（"\t权重:
"）;
13. scanf（"%d",&（hf[i].weight））;
14. }
15. for（i = 1;i <= 2 * n - 1;i++）/*对数组的父节点以及左右节点进行初始化,总共有2n-1个结点，初始权值结点n个，父节点n-1个*/
16. {
17. hf[i].parent = 0;
18. hf[i].lch = 0;
19. hf[i].rch = 0;
20. }
21. for（i = n + 1;i <= 2 * n - 1;i++）
22. {
23. m1 = m2 = 32767;//假设这两个权值一开始为int的最大值
24. p1 = p2 = 1;//位置初始值设为第一个节点的位置
25. for（k = 1;k < i;k++）
26. {
27. if（hf[k].parent == 0）
28. {
29. if（hf[k].weight < m1）
30. {
31. m2 = m1;//重新置次小值
32. p2 = p1;//重新置次小值对应的位置
33. m1 = hf[k].weight;//重新置最小值
34. p1 = k;//重新置最小值的位置
35. }
36. else if（hf[k].weight < m2）
37. {
38. m2 = hf[k].weight;//重新置次小值
39. p2 = k;//重新置次小值的位置
40. }
41. }
42. }
43. hf[p1].parent = i;//把最小的位置的节点的父节点位置设为i
44. hf[p2].parent = i;//把次小的位置的节点的父节点位置设为i
45. hf[i].weight = m1 + m2;//置新的生成的父节点的权重
46. hf[i].lch = p1;//设置新生成的节点的左节点
47. hf[i].rch = p2;//设置新生成的节点的左节点
48. }
49. printf（"Huffman树已经建立成功!
"）;
50. return n;
51.}
（2）编码
算法思路；
从 Huffman树的叶结点ht［i］（1≤i≤n）出发，通过双亲 parent找到其双亲ht［f］，通过ht［f］的left和 right域，可知ht［i］ht［f的左分支还是右分支，若是左分支，生成代码0；若是右分支，生成代码1，代码存放在数组cd［start］中，然后把ht［f］作为出发点，重复上述过程，直到找到树根为止。
显然，这样生成的代码序列与要求的编码次序相反，为了得到正确的代码，把最先生成的代码存放在数组的第n（虽然各个字符的编码长度不同，但都不会超过n）个位置处，再次生成的代码放在数组的第n-1个位置处，依此类推。
用变量 start指示编码在数组cd中的起始位置， start初始值为n，生成一个代码后， start的值就减1
算法如下；
1.void Encoding（HuffNode ht[],HuffCode hcd[],int n）//这里的hcd[]存有n个初始权值节点代码数组的数组，n是初始权值节点的个数;
2.{
3. HuffCode d;//存储每一个初始权值节点的代码数组
4. int i,c,f,k;
5. for（i = 1;i <= n;i++）
6. {
7. d.start = n + 1;//把d的start下标设为代码数组的末尾位置，因为存储代码时是从最下面的叶子结点到根，所以在存储是需要倒序存储的，且这里start一开始设为n+1，是因为尽管各个字符的代码长度不同，但都不可能超过n
8. c = i;//从叶节点开始向上
9. f = ht[i].parent;
10. while（f !
= NULL）//这里的循环是通过判断父节点是否为空为终止条件的
11. {
12. if（ht[f].lch == c）
13. d.cd[--d.start] = '0';
14. else
15. d.cd[--d.start] = '1';
16. c = f;
17. f = ht[f].parent;
18. }
19. hcd[i] = d;
20. }
21. printf（"输出Huffma编码如下：
\n"）;
22. for（i = 1;i <= n;i++）
23. {
24. printf（"%c对应Huffman编码为:
",ht[i].data）;
25. for（k = hcd[i].start;k <= n;k++）
26. printf（"%c",hcd[i].cd[k]）;
27. printf（"\n"）;
28. }
29.}
（3）译码
算法思路；
首先输入二进制代码串，存放在数组ch中，以“＃”为结束标志。
接下来，将代码与编码表比较，如果为0，转向左子树若为1，转向右子树，直到叶结点结束，此时输出叶结点的数据域，即所对应的字符。
继续译码，直到代码结束。
算法如下；
1.//译码
2.void Decoding（HuffNode ht[],HuffCode hcd[],int n）
3.{
4. int f,m,k;
5. DataType c,ch[200];
6. printf（"请输入电文（0 or 1）,以输入'#'截止:
"）;
7. c = getchar（）;
8. k = 1;
9. while（c !
= '#'）
10. {
11. ch[k] = c;
12. c = getchar（）;
13. k++;
14. }
15. m = k;
16. f = 2 * n - 1;//代表树根节点
17. k = 1;
18. printf（"输出哈夫曼译码如下:
\n"）;
19. while（k < m）
20. {
21. while（ht[f].lch !
= 0）//初始权值节点的标志
22. {
23. if（ch[k] == '1'）
24. f = ht[f].rch;
25. if（ch[k] == '0'）
26. f = ht[f].lch;
27. k++;
28. }
29. printf（"%c",ht[f].data）;
30. f = 2 * n - 1;//重置f
31. }
32. printf（"\n"）;
33.}
5.源代码
1.#include
2.#include
3.#include
4.#include
5.#include
6.#include
7.#include
8.#define TRUE 1
9.#define FALSE 0
10.#define MAXNUM 50
11.typedef char DataType;
12.
13.//Huffman树节点的存储结构定义
14.typedef struct
15.{
16. DataType data;
17. int weight;
18. int parent;
19. int lch;
20. int rch;
21.}HuffNode;
22.typedef struct
23.{
24. DataType cd[MAXNUM];
25. int start;
26.}HuffCode;
27.
28.//构造哈弗曼树
29.int Huffman（HuffNode *hf）
30.{
31. int i,k,n,m1,m2,p1,p2;
32. printf（"请输入元素的个素:
"）;
33. scanf（"%d",&n）;
34. for（i = 1;i <= n;i++）
35. {
36. getchar（）;//接收回车,如果不加这条语句，那么当输入完权重时，会按"\n"，就会被下一次输入值时被接收，于是就会出错
37. printf（"请输入第%d元素的=>\n\t节点值：
",i）;
38. scanf（"%c",&（hf[i].data））;//hf可以当做数组来用,因为hf[i]在这里不是一个指针，而是一个结构体，所以可以直接使用.运算符来调用data
39. printf（"\t权重:
"）;
40. scanf（"%d",&（hf[i].weight））;
41. }
42. for（i = 1;i <= 2 * n - 1;i++）/*对数组的父节点以及左右节点进行初始化,总共有2n-1个结点，初始权值结点n个，父节点n-1个*/
43. {
44. hf[i].parent = 0;
45. hf[i].lch = 0;
46. hf[i].rch = 0;
47. }
48. for（i = n + 1;i <= 2 * n - 1;i++）
49. {
50. m1 = m2 = 32767;//假设这两个权值一开始为int的最大值
51. p1 = p2 = 1;//位置初始值设为第一个节点的位置
52. for（k = 1;k < i;k++）
53. {
54. if（hf[k].parent == 0）
55. {
56. if（hf[k].weight < m1）
57. {
58. m2 = m1;//重新置次小值
59. p2 = p1;//重新置次小值对应的位置
60. m1 = hf[k].weight;//重新置最小值
61. p1 = k;//重新置最小值的位置
62. }
63. else if（hf[k].weight < m2）
64. {
65. m2 = hf[k].weight;//重新置次小值
66. p2 = k;//重新置次小值的位置
67. }
68. }
69. }
70. hf[p1].parent = i;//把最小的位置的节点的父节点位置设为i
71. hf[p2].parent = i;//把次小的位置的节点的父节点位置设为i
72. hf[i].weight = m1 + m2;//置新的生成的父节点的权重
73. hf[i].lch = p1;//设置新生成的节点的左节点
74. hf[i].rch = p2;//设置新生成的节点的左节点
75. }
76. printf（"Huffman树已经建立成功!
"）;
77. return n;
78.}
79.
80.//编码
81.void Encoding（HuffNode ht[],HuffCode hcd[],int n）//这里的hcd[]存有n个初始权值节点代码数组的数组，n是初始权值节点的个数;
82.{
83. HuffCode d;//存储每一个初始权值节点的代码数组
84. int i,c,f,k;
85. for（i = 1;i <= n;i++）
86. {
87. d.start = n + 1;//把d的start下标设为代码数组的末尾位置，因为存储代码时是从最下面的叶子结点到根，所以在存储是需要倒序存储的，且这里start一开始设为n+1，是因为尽管各个字符的代码长度不同，但都不可能超过n
88. c = i;//从叶节点开始向上
89. f = ht[i].parent;
90. while（f !
= NULL）//这里的循环是通过判断父节点是否为空为终止条件的
91. {
92. if（ht[f].lch == c）
93. d.cd[--d.start] = '0';
94. else
95. d.cd[--d.start] = '1';
96. c = f;
97. f = ht[f].parent;
98. }
99. hcd[i] = d;
100. }
101. printf（"输出Huffma编码如下：
\n"）;
102. for（i = 1;i <= n;i++）
103. {
104. printf（"%c对应Huffman编码为:
",ht[i].data）;
105. for（k = hcd[i].start;k <= n;k++）
106. printf（"%c",hcd[i].cd[k]）;
107. printf（"\n"）;
108. }
109.}
110.
111.//译码
112.void Decoding（HuffNode ht[],HuffCode hcd[],int n）
113.{
114. int f,m,k;
115. DataType c,ch[200];
116. printf（"请输入电文（0 or 1）,以输入'#'截止:
"）;
117. c = getchar（）;
118. k = 1;
119. while（c !
= '#'）
120. {
121. ch[k] = c;
122. c = getchar（）;
123. k++;
124. }
125. m = k;
126. f = 2 * n - 1;//代表树根节点
127. k = 1;
128. printf（"输出哈夫曼译码如下:
\n"）;
129. while（k < m）
130. {
131. while（ht[f].lch !
= 0）//初始权值节点的标志
132. {
133. if（ch[k] == '1'）
134. f = ht[f].rch;
135. if（ch[k] == '0'）
136. f = ht[f].lch;
137. k++;
138. }
139. printf（"%c",ht[f].data）;
140. f = 2 * n - 1;//重置f
141. }
142. printf（"\n"）;
143.}
144.
145.//主函数
146.int main（）
147.{
148. int n, select, flag = FALSE;
149. HuffNode ht[2 * MAXNUM];
150. HuffCode hcd[MAXNUM];
151. while（TRUE）
152. {
153. printf（"\t请选择您所想要实现的功能:
（请输入1-4号数字）\n"）;
154. printf（"\t1---建立Huffman树\n"）;
155. printf（"\t2---编码\n"）;
156. printf（"\t3---译码\n"）;
157. printf（"\t4---退出系统!
\n"）;
158. scanf（"%d",&select）;
159. if（select !
= 1 && select !
= 4 && flag == FALSE）
160. {
161. printf（"请先建立Huffman树再进行编码译码操作!
\n"）;
162. continue;//进入下一次循环
163. }
164. flag = TRUE;
165. switch（select）
166. {
167. case 1:
168. n = Huffman（ht）;
169. break;
170. case 2:
171. Encoding（ht,hcd,n）;
172. break;
173. case 3:
174. Decoding（ht,hcd,n）;
175. break;
176. case 4:
177. exit（0）;
178. }
升级会员 