《数据结构与算法》课程设计
一、题目：
利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。
二、实验目的：
学习哈夫曼编码及其思想。
三、需求分析：
1.实现创建哈夫曼树
2.能对输入的字符串（或从ToBeTran.txt文件中读取的字符串）进行编码，并保存到Codefile.txt文件中。
3.能对输入的哈夫曼编码（或从Codefile.txt文件中读取的哈夫曼编码）进行解码，并保存到Textfile.txt文件中。
4.能将创建出的哈夫曼树打印出来，并保存到ftree.txt中。
四、概要设计：
定义一个结构体来存储数据
typedef struct hu{
char data,hf[300];
int weight; //其权值
int parent,lc,rc; //双亲节点和孩子节点
}HTNode,*HuffmanTree;
1.创建哈夫曼树
采用哈夫曼算法
1.为每个符号建立一个叶子节点，并加上其相应的发生频率
2.当有一个以上的节点存在时，进行下列循环：
1）把这些节点作为带权值的二叉树的根节点，左右子树为空
2）选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3）把权值最小的两个根节点移除
4）将新的二叉树加入队列中。
5）最后剩下的节点暨为根节点，此时二叉树已经完成。
2.哈夫曼编码
对哈夫曼树进行遍历，左分支取0，右分支取1。所有的孩子节点都在双亲节点编码的基础上增加0或1，最后每个叶子节点（即存储字符的节点）的编码就是其哈夫曼编码。
3.解码
读取哈夫曼编码，从根节点开始，左分支取0，右分支取1，检测到叶子节点，便说明一个字符以解码完成，对此进行循环即可完成解码。
4.打印哈夫曼树
采用递归的思想输出。
五、程序说明：
六、详细设计：
1. #include<stdio.h>
2. #include<string.h>
3. #include<stdlib.h>
4. typedef struct hu{
5. char data,hf[300];
6. int weight;
7. int parent,lc,rc;
8. }HTNode,*HuffmanTree;
9.
10. struct hu HT[2000];
11. FILE *fp1,*fp2,*fp3,*fp4,*fp5;
12. int wei,i,n,s1,s2,minum,j,k,p;
13. char a,ch[3000],bm[1000],f;
14. //fp1是编码的TXT
15. //fp2是解码的TXT
16. //fp3是读取树的TXT
17. //fp4是读取的TXT
18. //fp5是打印树的TXT
19.
20. void pf(); //输出菜单
21. void creat(); //建树
22. void bianma(); //对字符集进行编码
23. void jiema(); //对编码进行解码
24. void show(int x,int y,char *pr); //打印哈夫曼树
25.
26. void pf(){ //输出菜单
27. printf("**************************************************n");
28. printf("* 创建哈夫曼树------1 *n");
29. printf("* 编码--------------2 *n");
30. printf("* 解码--------------3 *n");
31. printf("* 打印树------------4 *n");
32. printf("* 退出--------------Q *n");
33. printf("*************************************************n");
34. printf("输入你要进行的操作:n");
35. }
36.
37. void creat(){ //创建哈夫曼树
38. printf("**************************************************n");
39. printf("* 字符集及权值来源 *n");
40. printf("* 使用权值文件hfmTree.txt进行编码-----1 *n");
41. printf("* 自行输入字符集及权值----------------2 *n");
42. printf("* 返回上层----------------------------3 *n");
43. printf("**************************************************n");
44. printf("输入你要进行的操作:n");
45. scanf("%d",&p);
46. getchar();
47. if(p==1){
48. n=27;
49. for(i=1;i<=n;i++){
50. if(i==1){
51. HT[i].data=' ';
52. }else{
53. HT[i].data='A'+i-2;
54. }
55. HT[i].parent=0;
56. HT[i].lc=0;
57. HT[i].rc=0;
58. strcpy(HT[i].hf,"");
59. }
60. HT[2].weight=64;HT[3].weight=13;HT[4].weight=22;HT[5].weight=32;HT[6].weight=103;
61. HT[7].weight=21;HT[8].weight=15;HT[9].weight=47;HT[10].weight=57;HT[11].weight=1;
62. HT[12].weight=5;HT[13].weight=32;HT[14].weight=20;HT[15].weight=57;HT[16].weight=63;
63. HT[17].weight=15;HT[18].weight=1;HT[19].weight=48;HT[20].weight=51;HT[21].weight=80;
64. HT[22].weight=23;HT[23].weight=8;HT[24].weight=18;HT[25].weight=1;HT[26].weight=16;
65. HT[27].weight=1;HT[1].weight=186;
66. }else if(p==3){
67. return ;
68. }else if(p==2){
69. printf("输入字符集的个数n");
70. scanf("%d",&n);
71. getchar();
72. printf("输入字符与权值(例:a:1)n");
73. for(i=1;i<=n;i++){
74. scanf("%c:%d",&a,&wei);
75. getchar();
76. HT[i].data=a;
77. HT[i].weight=wei;
78. HT[i].parent=0;
79. HT[i].lc=0;
80. HT[i].rc=0;
81. strcpy(HT[i].hf,"");
82. }
83. }
84. k=1;
85. for(i=n+1;i<=2*n-1;i++){ //非叶子节点初始化
86. HT[i].weight=0;
87. HT[i].parent=0;
88. HT[i].lc=0;
89. HT[i].rc=0;
90. HT[i].data='+';
91. strcpy(HT[i].hf,"");
92. }
93. for(i=n+1;i<=2*n-1;i++){ //创建非叶子节点，建哈夫曼树
94. for(j=1;j<=i-1;j++){ // 以下是找到第一个最小值
95. if(HT[j].parent==0){
96. minum=j;
97. break;
98. }
99. }
100. for(j=1;j<=i-1;j++){
101. if(HT[j].parent==0)
102. if(HT[j].weight<HT[minum].weight)
103. minum=j;
104. }
105. s1=minum;
106. for(j=1;j<=i-1;j++){
107. if(HT[j].parent==0&&j!=s1){
108. minum=j;
109. break;
110. }
111. }
112. for(j=1;j<=i-1;j++){
113. if(HT[j].parent==0&&j!=s1)
114. if(HT[j].weight<HT[minum].weight)
115. minum=j;
116. }
117. s2=minum;
118. HT[s1].parent=i; // 删除结点
119. HT[s2].parent=i;
120. HT[i].lc=s1;
121. HT[i].rc=s2;
122. HT[i].weight=HT[s1].weight+HT[s2].weight;
123. } //进行哈夫曼编码
124. for(i=2*n-1;i>=n+1;i--){
125. if(HT[i].lc!=0 && HT[i].rc!=0){
126.
127. strcpy(HT[HT[i].lc].hf,HT[i].hf);
128. strcat(HT[HT[i].lc].hf,"0");
129.
130. strcpy(HT[HT[i].rc].hf,HT[i].hf);
131. strcat(HT[HT[i].rc].hf,"1");
132. }
133. }
134. printf("霍夫曼的字符编码:n");
135. fprintf(fp3,"霍夫曼的字符编码:n");
136. for(i=1;i<=n;i++){
137. printf("%c:%sn",HT[i].data,HT[i].hf);
138. fprintf(fp3,"%c:%sn",HT[i].data,HT[i].hf);
139. }
140. printf("霍夫曼的字符编码已存入ftree.txtn");
141. fclose(fp3);
142. fp3=fopen("ftree.txt","a+");
143. }
144.
145. void bianma(){ //进行编码
146. printf("**************************************************n");
147. printf("* 字符串来源 *n");
148. printf("* 直接输入字符串----------------------1 *n");
149. printf("* 从ToBeTranfile.txt中读取------------2 *n");
150. printf("* 返回上层----------------------------3 *n");
151. printf("**************************************************n");
152. scanf("%d",&p);
153. getchar();
154. if(p==1){
155. printf("输入字符串n");
156. gets(ch);
157. printf("n%s编码后:n",ch);
158. }else if(p==3){
159. return ;
160. }else if(p==2){
161. fgets(ch,1024,fp4);
162. if(strlen(ch)==0){
163. printf("未读取到字符串!n");
164. return ;
165. }
166. printf("读取出的字符串为%sn编码后为:",ch);
167. }
168. //fprintf(fp1,"%s编码后:n",ch);
169. for(i=0;i<strlen(ch);i++){
170. for(j=1;j<=n;j++){
171. if(ch[i]==HT[j].data){
172. printf("%s",HT[j].hf);
173. fprintf(fp1,"%s",HT[j].hf);
174. }
175. }
176. }
177. printf("n");
178. printf("编码内容已保存至CodeFile.txtnn");
179. fclose(fp1);
180. fp1=fopen("CodeFile.txt","a+");
181. }
182.
183. void jiema(){ //进行解码
184. printf("**************************************************n");
185. printf("* 哈夫曼编码来源 *n");
186. printf("* 直接输入哈夫曼编码------------------1 *n");
187. printf("* 从Codefile.txt中读取----------------2 *n");
188. printf("* 返回上层----------------------------3 *n");
189. printf("**************************************************n");
190. scanf("%d",&p);
191. getchar();
192. if(p==1){
193. printf("输入哈夫曼编码n");
194. gets(bm);
195. printf("n%s解码后:n",bm);
196. }else if(p==2){
197. fgets(bm,1024,fp1);
198. if(strlen(bm)==0){
199. printf("未读取到编码!n");
200. return ;
201. }
202. printf("读取出的哈夫曼编码为:n%sn解码后为:",bm);
203. }else if(p==3){
204. return ;
205. }
206. char jm[50];
207. int t,f=0,p1=0;
208. strcpy(jm,"");
209. t=2*n-1;
210. for(j=0;j<strlen(bm);j++){
211. if(bm[j]=='0'){
212. t=HT[t].lc;
213. }else if(bm[j]=='1'){
214. t=HT[t].rc;
215. }
216. if(HT[t].lc==0 && HT[t].rc==0){
217. jm[p1]=HT[t].data;
218. t=2*n-1;
219. p1++;
220. }
221. }
222. jm[p1]='�';
223. printf("%sn",jm);
224. fprintf(fp2,"%s",jm);
225. printf("解码内容已保存至Textfile.txtnn");
226. fclose(fp2);
227. fp2=fopen("Textfile.txt","a+");
228. }
229. void show(int x,int y,char *pr){ //打印哈夫曼树
230. strcat(pr,"|");
231. if(x){
232. printf("%s--%cn",pr,HT[y].data);
233. fprintf(fp5,"%s--%cn",pr,HT[y].data);
234. if(x==y || HT[x].rc==y){
235. int len=strlen(pr);
236. pr[len-1]=' ';
237. }
238. if(HT[y].lc!=0 || HT[y].rc!=0){
239. char *p1=(char*)malloc(sizeof(char)*100);
240. strcpy(p1,pr);
241. strcat(p1," ");
242. show(y,HT[y].lc,p1);
243.
244. char *p2=(char*)malloc(sizeof(char)*100);
245. strcpy(p2,pr);
246. strcat(p2," ");
247. show(y,HT[y].rc,p2);
248. }
249. }else{
250. if(HT[y].lc!=0 && HT[y].rc!=0){
251. printf("%s--#n",pr);
252. fprintf(fp5,"%s--#n",pr);
253. }
254. }
255. }
256. int main(void){ //主函数
257. k=0; //k是判断是否已经建树
258. printf(" 哈夫曼编译器 n");
259. fp1=fopen("CodeFile.txt","a+"); //编码完的放这里
260. fp2=fopen("Textfile.txt","a+"); //解码完的放这里
261. fp3=fopen("ftree.txt","a+"); //建完树后的每个字符的编码完的放这里
262. fp4=fopen("ToBeTran.txt","a+"); //这是待读取的字符集
263. fp5=fopen("TreePrint.txt","a+"); // 树打印在这个文件夹里
264. pf(); //输出菜单
265. scanf("%c",&f);
266. while(f!='Q'&&f!='q'){
267. if(f=='1'){ //创建哈夫曼树
268. creat();
269. printf("n");
270. }else if(f=='2'&&k==1){ //编码
271. bianma();
272. printf("n");
273. }else if(f=='3'&&k==1){ //解码
274. jiema();
275. printf("n");
276. }else if(f=='4'&&k==1){ //打印树
277. printf(" +代表空结点n");
278. char *ppp=(char*)malloc(sizeof(char)*100);
279. strcpy(ppp,"");
280. show(2*n-1,2*n-1,ppp);
281. printf("n已将打印出的树保存至TreePrint.txtnn");
282. fclose(fp5);
283. fp5=fopen("TreePrint.txt","a+");
284. getchar();
285. }else if(k==0&&f!='1'){
286. printf("请先建哈夫曼树nn");
287. getchar();
288. }
289. pf();
290. scanf("%c",&f);
291. }
292. fclose(fp1); //关闭文件
293. fclose(fp2);
294. fclose(fp3);
295. fclose(fp4);
296. fclose(fp5);
297. return 0;
298. }
七、调试分析：
白盒：
白盒测试也称结构测试或逻辑驱动测试，它是按照程序内部的结构测试程序，通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行检验程序中的每条通路是否都能按预定要求正确工作。 这一方法是把测试对象看作一个打开的盒子，通过在不同点检查程序的状态，确定实际的状态是否与预期的状态一致。
黑盒：
黑盒测试也称功能测试，它是通过测试来检测每个功能是否都能正常使用。在测试中把程序看作一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试，它只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息。黑盒测试着眼于程序外部结构，不考虑内部逻辑结构主要针对软件界面和软件功能进行测试。
测试数据为：THIS IS QKY DATA STRUCTURE
输出为：1101000101100011111011000111111100001001110000111000111111011010101101101011100111101001000001000001101000010010010
时间复杂度为：0（n2）
遇到问题：
1.创建哈夫曼树时无法正确为字符编码，
2.解码时无法正确解码，输出乱码
3.不会打印图形化的树
4.不会搞可视化窗口
1，2，3已解决
4可视化窗口设计的能力仍有待提高
八、实验心得与体会（总结）
本次课程设计使我对《数据结构》这门课程有了更深入的理解。《数据结构》是一门实践性较强的课程，为了学好这门课程必须在掌握理论知识的同时加强上机实践
我的课程设计题目是霍夫曼编码。刚开始做这个程序的时候感到完全无从下手，于是开始查阅各种资料以及参考文献之后便开始着手写程序写完运行时有很多问题。
在本课程设计中我明白了理论与实际应用相结合的重要性。这次课程设计同样提高了我的综合运用所学知识的能力。《数据结构》是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。
通过这段时间的课程设计我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力使我掌握了程序设计的基本技能提高了我适应实际实践编程的能力。
总的来说这次课程设计让我获益匪浅对数据结构也有了进一步的理解和认识。
文章评论