赫夫曼编码及译码器设计文档.docx
- 文档编号:8868971
- 上传时间:2023-05-15
- 格式:DOCX
- 页数:26
- 大小:290.30KB
赫夫曼编码及译码器设计文档.docx
《赫夫曼编码及译码器设计文档.docx》由会员分享,可在线阅读,更多相关《赫夫曼编码及译码器设计文档.docx(26页珍藏版)》请在冰点文库上搜索。
赫夫曼编码及译码器设计文档
滁州学院
课程设计报告
课程名称:
数据结构
设计题目:
赫夫曼编码与解码器
系别:
计算机科学与技术
专业:
计算机科学与技术
组别:
第二组
起止日期:
11年5月25日~11年6月10日
指导教师:
胡成祥
计算机科学与技术系二○○九年制
课程设计题目
赫夫曼编码和解码
组长
陆伟
学号
2010211108
班级
计科
(2)班
系别
计算机系
专业
计算机科学与技术
组员
李梦2010211102林川2010211105
彭祥2010211112马岩2010211109
指导教师
胡成祥
课程设计目的
设计一个赫夫曼编码和解码程序
课程设计所需环境
MicrosoftVisualC++6.0
课程设计任务要求
通过设计的程序对指定的文件进行编码和解码
课程设计工作进度计划
序号
起止日期
工作内容
分工情况
5-25~5-27
商讨问题的解决路径和初步实施方案。
本小组组员根据个人所学情况,对问题认真分析,想出自己特色的实施方案,
为下次会议的方案选择做准备。
5-28~6-6
针对问题提出自己的见解,并根据实际情况采取行动。
林川、李梦编写赫夫曼树的生成及初始化;马岩编写编码;彭祥编写界面和主函数;陆伟编写译码以及负责最后的程序代码的综合和检查修补。
6-7~6-10
完成文档的编写并对个人工作进行分析,发表自己的见解。
林川、李梦:
需求分析;马岩:
概要设计及调试操作;彭祥:
目录和总结、体会;陆伟:
需求分析和致谢、参考文献。
指导教师签字:
年月日
教研室审核意见:
教研室主任签字:
年月日
目录
1引言4
1.1课程设计目的5
1.2课程设计背景5
1.3课程设计主要内容6
2.需求分析6
2.1课程设计题目6
2.2课程设计任务6
2.3要求6
2.4课程设计思想7
2.5软硬件运行环境7
2.6开发工具7
3.概要设计7
3.1课程设计的流程图7
3.2主要的数据结构8
3.3完成本课程设计所用方法及其原理9
4详细设计9
5调试与操作说明22
5.1首先进行初始化操作22
5.2译码、编码等操作实现23
5.2.1译码操作23
5.2.2编码操作24
5.2.3退出程序的运行操作25
6课程设计总结与体会26
7致谢27
8参考文献27
9附录28
1引言
当今社会,计算机技术和通信技术已经不断发展,处理和传输的数据量越来越庞大。
如何采用有效的数据压缩技术引起了人们的极大重视。
从而产生了赫夫曼编码,它是一种应用广泛且非常有效的数据压缩技术,该技术一般可将数据压缩20%至90%,通常我们将压缩技术称为编码,将解压过程称为解码。
树状结构简称为数,是一种以分支关系进行定义的层次结构,是十分重要的非线性数据结构,在计算机软件设计方面,有着广泛的应用。
1.1课程设计目的
本课程设计是为了让同学们了解学习数据结构的作用和意义。
数据结构是计算机科学与技术专业的专业基础课,是十分重要的课程。
所有的计算机系统软件和应用软件都要用到各种类型的数据结构。
因此,想要更好地运用计算机来解决实际问题,仅仅掌握几门计算机程序设计语言是远远难以应付当前众多复杂的课题,想要有效地使用计算机,充分发挥它的性能,还必须学习和掌握好数据结构的有关知识,打好数据结构这门课的扎实基础,对于学习计算机专业其它的课程,如操作系统、软件工程、编译原理、数据库、人工智能等十分有益。
1.2课程设计背景
当今社会,计算机技术和通信技术已经不断发展,处理和传输的数据量越来越庞大。
如何采用有效的数据压缩技术引起了人们的极大重视。
从而产生了赫夫曼编码,它是一种应用广泛且非常有效的数据压缩技术,该技术一般可将数据压缩20%至90%,通常我们将压缩技术称为编码,将解压过程称为解码。
树状结构简称为数,是一种以分支关系进行定义的层次结构,是十分重要的非线性数据结构,在计算机软件设计方面,有着广泛的应用。
在这个信息量发达的时代,随着社会的进步,信息不断地增多和更新,为了使信息更加快速、准确有效的传输,那就需要一个编码和解码的程序来完成。
1.3课程设计主要内容
本课程设计要求完成发送端对待传送数据的编码和接收端对传送来的数据的译码。
要实现五个功能:
接收原始数据、编码、译码、将编码和译码存档。
通过系统的提示建立赫夫曼树并对载入的原文件进行编码,并保存到指定的文件中,同时输出到屏幕。
另一方面,对原文件进行译码,并将译码的结果保存到指定的文件中,同时输到屏幕。
对于编码和译码的操作中的文件导入,分为键盘输入和文件输入两种。
2.需求分析
2.1课程设计题目
赫夫曼编/译码器。
2.2课程设计任务
设计一个赫夫曼编码和解码程序。
2.3要求
根据赫夫曼编码和解码算法,将指定的文件中的赫夫曼编码进行译码,并输出到文件中,还要实现对文件中支付的编码,并输出编码到文件中。
2.4课程设计思想
输入字符的和字符出现的频率,并将字符作为叶子节点,频率作为节点权值建立哈夫曼树,再根据在哈夫曼树中,由叶子结点逐步走到根节点的路径对叶子节点进行编码,译码时,从根节点找到叶子节点完成译码过程。
2.5软硬件运行环境
MicrosoftWindowsXP版本2002ServicePack3
或
MicrosoftWindows7旗舰版
2.6开发工具
MicrosoftVisualC++6.0
3.概要设计
3.1课程设计的流程图
界面设计
voidprint()
3.2主要的数据结构
#defineM100
#defineMAX10000
typedefstruct{
intweight;
intflag;
intparent;
charch;
intlchild;
intrchild;
}HafNode;
typedefstruct{
intbit[M];
intstart;
intweight;
charch;
}HCode;
typedefstruct{
charbit[M];
charch;
intweight;
}Coding;
3.3完成本课程设计所用方法及其原理
输入字符的和字符出现的频率,并将字符作为叶子节点,频率作为节点权值建立哈夫曼树,再根据在哈夫曼树中,由叶子结点逐步走到根节点的路径对叶子节点进行编码,译码时,从根节点找到叶子节点完成译码过程。
4详细设计
程序源代码:
#include
#include
#include
#defineM100
#defineMAX10000
typedefstruct
{
intweight;
intflag;
intparent;
charch;
intlchild;
intrchild;
}HafNode;
typedefstruct
{
intbit[M];
intstart;
intweight;
charch;
}HCode;
typedefstruct
{
charbit[M];
charch;
intweight;
}Coding;
voidhaffman(intweight[],charch[],intn,HafNodehaffTree[]){
inti,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
if(i { haffTree[i].weight=weight[i]; haffTree[i].ch=ch[i]; } else haffTree[i].weight=0; haffTree[i].parent=-1; haffTree[i].flag=0; haffTree[i].lchild=-1; haffTree[i].rchild=-1; } for(i=0;i { m1=m2=MAX; x1=x2=0; for(j=0;j { if(haffTree[j].weight { m2=m1; x2=x1; m1=haffTree[j].weight; x1=j; } elseif(haffTree[j].weight { m2=haffTree[j].weight; x2=j; } } haffTree[x1].parent=n+i; haffTree[x2].parent=n+i; haffTree[x1].flag=1; haffTree[x2].flag=1; haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; haffTree[n+i].lchild=x1; haffTree[n+i].rchild=x2; } FILE*fp; fp=fopen("huffman.txt","w+"); printf("%d\n",n); fprintf(fp,"%d\n",n); for(i=0;i fprintf(fp,"%c%d%d%d\n",haffTree[i].ch,haffTree[i].parent,haffTree[i].lchild,haffTree[i].rchild); for(i=n;i<2*n-1;i++) fprintf(fp,"%%d%d\n",haffTree[i].parent,haffTree[i].lchild,haffTree[i].rchild); fclose(fp); } voidHaffmanCode(HafNodehaffTree[],intn,HCodehaffCode[]) { HCode*cd=(HCode*)malloc(sizeof(HCode)); inti,j,child,parent; for(i=0;i { cd->start=n-1; cd->weight=haffTree[i].weight; cd->ch=haffTree[i].ch; child=i; parent=haffTree[child].parent; while(parent! =-1) { if(haffTree[parent].lchild==child) cd->bit[cd->start]=0; else cd->bit[cd->start]=1; cd->start--; child=parent; parent=haffTree[child].parent; } for(j=cd->start+1;j haffCode[i].bit[j]=cd->bit[j]; haffCode[i].start=cd->start+1; haffCode[i].weight=cd->weight; haffCode[i].ch=cd->ch; } } voidInit(intweight[],charch[]) { FILE*fp; inti,j,n; charch1,wj[15]; printf("进行初始化操作......\n请选择你要进行的操作: \nJ.键盘输入.W.文件输入.\n"); scanf("%c",&ch1); if(ch1=='J') { printf("请输入字符集的大小n: \n"); scanf("%d",&n); } if(ch1=='W') { printf("请输入文件名: \n"); scanf("%s",wj); fp=fopen(wj,"r"); fscanf(fp,"%d",&n); } HafNode*myHaffTree=(HafNode*)malloc(sizeof(HafNode)*(2*n+1)); HCode*myHaffCode=(HCode*)malloc(sizeof(HCode)*n); for(i=0;i { if(ch1=='J') { printf("请输入字符和权值: \n"); scanf("%s%d",&ch[i],&weight[i]); } if(ch1=='W') fscanf(fp,"%s%d",&ch[i],&weight[i]); } if(ch1=='W') fclose(fp); haffman(weight,ch,n,myHaffTree); HaffmanCode(myHaffTree,n,myHaffCode); fp=fopen("hfmtree.txt","w+"); for(i=0;i { printf("%c%d",myHaffCode[i].ch,myHaffCode[i].weight); fprintf(fp,"%c%d",myHaffCode[i].ch,myHaffCode[i].weight); for(j=myHaffCode[i].start;j { printf("%d",myHaffCode[i].bit[j]); fprintf(fp,"%d",myHaffCode[i].bit[j]); } fprintf(fp,"\n"); printf("\n"); } fclose(fp); printf("初始化成功! \n"); } voidBian_ma() { FILE*fp,*fp1,*fp2; charzf[500]; fp=fopen("hfmtree.txt","r"); Codingch[100]; charc; inti=0; while(feof(fp)==0) { fscanf(fp,"%s%d%s",&ch[i].ch,&ch[i].weight,&ch[i].bit); i++; } fclose(fp); printf("现在进行编码操作。 。 。 \n请选择: \nJ.键盘输入.W.文件输入.\n"); scanf("%s",&c); if(c=='J') { printf("请输入字符串: \n"); scanf("%s",zf); } charch1[20],ch2[20]; intj; if(c=='W') { printf("请输入正文的文件名: \n"); scanf("%s",&ch1); fp1=fopen(ch1,"r"); } printf("请输入保存结果的文件名: \n"); scanf("%s",&ch2); fp2=fopen(ch2,"w+"); if(c=='J') { intlen,k; len=strlen(zf); for(k=0;k for(j=0;j if(ch[j].ch==zf[k]) { fprintf(fp2,"%s",ch[j].bit); printf("%s",ch[j].bit); } printf("\n"); } if(c=='W') { while(feof(fp1)==0) { fscanf(fp1,"%c",&c); for(j=0;j if(ch[j].ch==c) { fprintf(fp2,"%s",ch[j].bit); printf("%s",ch[j].bit); } } fprintf(fp2,"\n"); printf("\n"); fclose(fp1); } fclose(fp2); printf("提示: 编码过程完成! 已将结果存入%s中.\n\n",ch2); } voidYi_ma() { FILE*fp,*fp1; fp=fopen("huffman.txt","r"); inti,n; fscanf(fp,"%d",&n); HafNode*myHaffTree=(HafNode*)malloc(sizeof(HafNode)*(2*n+1)); for(i=0;i fscanf(fp,"%s%d%d%d\n",&myHaffTree[i].ch,&myHaffTree[i].parent,&myHaffTree[i].lchild,&myHaffTree[i].rchild); for(i=n;i<2*n-1;i++) fscanf(fp,"%d%d%d\n",&myHaffTree[i].parent,&myHaffTree[i].lchild,&myHaffTree[i].rchild); fclose(fp); printf("请输入译码文件的文件名: \n"); charch1[20],ch2[20]; scanf("%s",ch1); printf("请输入结果文件的文件名: \n"); scanf("%s",ch2); fp=fopen(ch1,"r"); fp1=fopen(ch2,"w+"); charch; i=2*n-2; while(! feof(fp)) { fscanf(fp,"%c",&ch); if(ch=='0') i=myHaffTree[i].lchild; if(ch=='1') i=myHaffTree[i].rchild; if(i { printf("%c",myHaffTree[i].ch); fprintf(fp1,"%c",myHaffTree[i].ch); i=2*n-2; } } printf("\n"); fprintf(fp1,"\n"); fclose(fp); fclose(fp1); printf("提示: 译码过程完成! 已将结果存入%s中.\n\n",ch2); } voidprint() { printf("********************************数据结构课程设计********************************\n"); printf("********************滁州学院———计算机科学与技术专业 (2)班*******************\n"); printf("******************【陆伟李梦林川彭祥马岩】——设计******************\n"); printf("************************欢迎使用哈夫曼编码器和译码器**************************\n"); printf("********************************操作菜单如下所示********************************\n"); printf("*********************A.编码 B.译码 C.退出***********************\n"); printf("********************************************************************************\n"); } intmain() { inti,j,n=4; intweight[100]; charch[100],cha; print(); Init(weight,ch); while (1) { printf("请输入要执行的操作: \nA.编码 B.译码 C.退出\n"); printf("请输入要执行的操作: \n"); scanf("%s",&cha); if(cha=='C') break; switch(cha) { case'A': Bian_ma();break;//执行编码操作 case'B': Yi_ma();break;//执行译码操作 } } return0; } 5调试与操作说明 5.1首先进行初始化操作 输入字符Z,X,C,V,B,N,M,并输入每个字符的相应权值1,1,22,8,13,57,20,然后对输入的字符构造哈夫曼树,并对每个字符进行编码。 运行结果如图所示: 5.2译码、编码等操作实现 5.2.1译码操作 将计算机硬盘中存储的名为“待译码.txt”的文件译码,并肩结果保存在相应的文件夹下的名为“译码后.txt”的文件中。 5.2.2编码操作 首先用键盘输入字符串ZXCVBNMMNBZZ,让程序对其进行编码,并将编码结果保存在相应文件夹下名为“键盘输入字符的编码.txt”这个文件中。 再将计算机硬盘中存储的名为“待编码的文件.txt”的文件进行编码,并将编码后的结果保存在相应的文件夹下名为“待编码的文件编码后.txt”的文件中。 在进行译码和编码的时候,将保存到计算机硬盘中的文件中的结果也显示在控制台的屏幕上,以便观看。 程序结果如图所示: 5.2.3退出程序的运行操作 用键盘输入操作代号“C”,退出程序。 程序结果如图所示: 6课程设计总结与体会 经过我们小组的密切努力合作,共同完成了题目设计实验。 总体感觉,受益匪浅。 我们认为,在这学期的实验中,在收获知识的同时,还收获了阅历,收获了成熟,在此过程中,我们通过查找大量资料,请教老师,以及不懈的努力,不仅培养了独立思考、动手操作的能力,在各种其它能力上也都有了提高。 更重要的是,在实验课上,我们学会了很多学习的方法。 而这是日后最实用的,真的是受益匪浅。 要面对社会的挑战,只有不断的学习、实践,再学习、再实践。 通过设计并编写有关赫夫曼编码与解码,锻炼自己的c 语言编程能力,养成良好的c语言编程风格。 不管怎样,这些都是一种锻炼,一种知识的积累,能力的提高。 完全可以把这个当作基础东西,只有掌握了这些最基础的,才可以更进一步,取得更好的成绩。 很少有人会一步登天吧。 永不言弃才是最重要的。 而且养成了我们的团队合作精神,俗话说团结就是力量,通过这次试验,充分体会到团结的重要性。 无论困难重重还是,一马平川,我们都相互讨论以获得最好的效果
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 赫夫曼 编码 译码器 设计 文档