数据结构实验哈夫曼编译码.docx
- 文档编号:16785228
- 上传时间:2023-07-17
- 格式:DOCX
- 页数:16
- 大小:126.09KB
数据结构实验哈夫曼编译码.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. }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 哈夫曼编 译码