哈夫曼编译码数据结构C语言版课程设计.docx
《哈夫曼编译码数据结构C语言版课程设计.docx》由会员分享,可在线阅读,更多相关《哈夫曼编译码数据结构C语言版课程设计.docx(13页珍藏版)》请在冰点文库上搜索。
哈夫曼编译码数据结构C语言版课程设计
《数据结构》
课程设计报告
设计题目哈夫曼(Huffman)编/译码器
学院名称信息工程学院
专业班级12计本2
姓名张翠翠
学号17______
题目:
哈夫曼(Huffman)编/译码器
一、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。
对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
试为这样的信息收发站写一个哈夫曼码的编/译码系统。
二、设计目标
帮助学生熟练掌握树的应用和基本操作,重点掌握二叉树的存储,这里以哈夫曼树为设计目标进一步提高学生的设计能力及对树的理解。
三、任务要求
一个完整的系统应具有以下功能:
1)I:
初始化(Initialization)。
从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。
2)E:
编码(Encoding)。
利用以建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
3)D:
译码(Decoding)。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。
4)P:
印代码文件(Print)。
将文件CodeFile以紧凑格式显示在终端上,每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。
5)T:
印哈夫曼树(TreePrinting)。
将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
四、需求分析
利用哈夫曼树(Huffman)编/译码
(一)、初始化哈夫曼树
(二)、建立哈夫曼树
(三)、对哈夫曼树进行编码
(四)、输出对应字符的编码
(五)、译码过程
五、概要设计
哈夫曼树的存储结构描述
typedefstruct
{
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;
哈弗曼树的算法
voidCreateHT(HTNodeht[],intn)arent=ht[i].lchild=ht[i].rchild=-1;arent==-1)eight}
elseif(ht[k].weight{
min2=ht[k].weight;rnode=k;
}
}
}
ht[lnode].parent=i;ht[rnode].parent=i;eight=ht[lnode].weight+ht[rnode].weight;child=lnode;ht[i].rchild=rnode;arent;
while(f!
=-1)child==c)arent;
}
++;ata);
for(k=hcd[i].start;k<=n;k++)d[k]);
}
printf("\n");
}
}
voideditHCode(HTNodeht[],HCodehcd[],intn)ata)tart;k<=n;k++)
{
printf("%c",hcd[j].cd[k]);
}
break;tart,j=0;k<=n;k++,j++)d[k])ata);
for(x=0;code[x-1]!
='#';x++)ata=str[i];
ht[i].weight=fnum[i];
}
while(flag).");
getch();
system("cls");
break;
case'b':
case'B':
system("cls");
printf("请输入要进行编码的字符串(以#结束):
\n");
editHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case'c':
case'C':
system("cls");
DispHCode(ht,hcd,n);
printf("请输入编码(以#结束):
\n");
deHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case'd':
case'D':
flag=0;
break;
default:
system("cls");
}}}
六、详细设计
字符
空格
A
B
C
D
E
F
G
H
I
J
K
L
M
频度
186
64
13
22
32
103
21
15
47
57
1
5
32
20
由上表画出哈夫曼树:
由哈夫曼树得出各字符的编码:
字符
编码
字符
编码
空格
10
D
0001
A
010
E
1111
B
011111
F
11001
C
0000
G
01110
关系调用:
该程序的流程图:
七、测试分析
白盒:
查看代码完整性
白盒测试也称结构测试或逻辑驱动测试,它是按照程序内部的结构测试程序,通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行,检验程序中的每条通路是否都能按预定要求正确工作。
这一方法是把测试对象看作一个打开的盒子,测试人员依据程序内部逻辑结构相关信息,设计或选择测试用例,对程序所有逻辑路径进行测试,通过在不同点检查程序的状态,确定实际的状态是否与预期的状态一致。
黑盒:
测试是否可以正确的创建,删除,插入,打印,查找等操作
黑盒测试也称功能测试,它是通过测试来检测每个功能是否都能正常使用。
在测试中,把程序看作一个不能打开的黑盒子,在完全不考虑程序内部结构和内部特性的情况下,在程序接口进行测试,它只检查程序功能是否按照需求规格说明书的规定正常使用,程序是否能适当地接收输入数据而产生正确的输出信息。
黑盒测试着眼于程序外部结构,不考虑内部逻辑结构,主要针对软件界面和软件功能进行测试。
八、使用说明
1)输入n个字符的权值
2)输入对应的字符
3)得出各字符的编码
九、测试数据
用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:
“THISPROGRAMISMYFAVORITE”。
字符空格ABCDEFGHIJKLM
频度1866413223210321154757153220
字符NOPQRSTUVWXYZ
频度5763151485180238181161
注:
学生在测试数据时,需要写出测试用例和截图
十、该程序的源代码
#include<>
#include<>arent=ht[i].lchild=ht[i].rchild=-1;arent==-1)eight}
elseif(ht[k].weight{
min2=ht[k].weight;rnode=k;
}
}
}
ht[lnode].parent=i;ht[rnode].parent=i;eight=ht[lnode].weight+ht[rnode].weight;child=lnode;ht[i].rchild=rnode;arent;
while(f!
=-1)child==c)arent;
}
++;ata);
for(k=hcd[i].start;k<=n;k++)d[k]);
}
printf("\n");
}
}
voideditHCode(HTNodeht[],HCodehcd[],intn)ata)tart;k<=n;k++)
{
printf("%c",hcd[j].cd[k]);
}
break;tart,j=0;k<=n;k++,j++)d[k])ata);
for(x=0;code[x-1]!
='#';x++)ata=str[i];
ht[i].weight=fnum[i];
}
while(flag).");
getch();
system("cls");
break;
case'b':
case'B':
system("cls");
printf("请输入要进行编码的字符串(以#结束):
\n");
editHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case'c':
case'C':
system("cls");
DispHCode(ht,hcd,n);
printf("请输入编码(以#结束):
\n");
deHCode(ht,hcd,n);
printf("\n按任意键返回...");
getch();
system("cls");
break;
case'd':
case'D':
flag=0;
break;
default:
system("cls");
}
}
}
:
该程序的截图:
初始化界面截图如下
选A时的显示结果截图如下
选择B时的显示结果截图如下
选C时的显示结果截图如下
十一、使用说明(给出软件如何使用,使用时的注意事项)
VC++编程环境使用
1、?
VC++程序启动?
2、新建工程Project
3、?
设定工程Project名称、保存位置?
4、?
设定工程Project的类型?
5、?
工程Project的描述信息生成
6、?
空工程Project建立完毕
7)?
向工程Project中添加(新建)源代码文件的类型、名称、保存位置?
8、设定源代码文件的类型、名称
9、?
源代码文件被添加到工程中?
10、在源代码文件中添加程序代码
11、程序代码编译完成后编译、链接过程
注意事项:
?
(1)?
一个工程project中可以有多个源文件(.cpp)、多个头文件(.h);
但这些源代码文件中只能出现一个main函数,作为整个程序运
行的入口;?
(2)必须关闭前一次程序运行结果窗口,才能进行下一次程序运行;?
(3)书写标识符时,忽略了大小写字母的区别。
?
(4)?
忘记加分号?
(5)多加分号
十二、课程设计总结
本次课程设计的题目是:
哈夫曼(Huffman)编/译码器。
通过这次课程设计,我了解到自己在编写程序方面还有很多不足,在实践过程中老师给了我很大的帮助。
在这次课程设计中,虽然不会成功的编写一个完整的程序,但是在看程序的过程中,不断的上网查资料以及翻阅相关书籍,通过不断的模索,测试,发现问题,解决问题和在老师的帮助下一步一步慢慢的正确运行程序,终于完成了这次课程设计,虽然这次课程设计结束了但是总觉得自已懂得的知识很是不足,学无止境,以后还会更加的努力深入的学习。