哈夫曼编码译码器概要.docx
- 文档编号:16972333
- 上传时间:2023-07-20
- 格式:DOCX
- 页数:19
- 大小:98.32KB
哈夫曼编码译码器概要.docx
《哈夫曼编码译码器概要.docx》由会员分享,可在线阅读,更多相关《哈夫曼编码译码器概要.docx(19页珍藏版)》请在冰点文库上搜索。
哈夫曼编码译码器概要
沈阳航空航天大学
课程设计报告
课程设计名称:
数据结构课程设计
课程设计题目:
哈夫曼编码/译码器
院(系):
计算机学院
专业:
计算机科学与技术
班级:
学号:
姓名:
指导教师:
目录
沈阳航空航天大学I
第1章概要设计1
1.1题目的内容与要求1
1.2总体结构1
第2章算法分析2
2.1核心算法思想2
2.2算法结构定义2
第3章详细设计3
3.1功能流程3
第4章系统实现5
4.1错误分析5
4.2运行结果5
参考文献8
附录9
第1章概要设计
1.1题目的内容与要求
内容:
设计一个利用哈夫曼算法的编码和译码系统,可以接收从键盘输入的字符集大小、字符和权值信息,创建哈夫曼树生成哈夫曼编码并能对其进行解码。
要求:
1.存储结构自定;
2.将生成的哈夫曼编码与等长编码进行比较,判断优劣;
3.给出动态演示过程(选作)。
1.2总体结构
本程序主要分为3个模块(功能模块图见图1.1):
主模块,编码模块,译码模块。
主模块:
程序的主体部分,分别调用各个模块,实现各项功能。
编码模块:
对每个出现的字符进行编码。
译码模块:
将已有编码译成字符,使之可以直接被读出。
图1.1功能模块图
第2章算法分析
2.1核心算法思想
哈夫曼树的建立由赫夫曼算法的定义可知,初始森林中共有n棵只含有根结点的二叉树。
算法的第二步是:
将当前森林中的两棵根结点权值最小的二叉树,合并成一棵新的二叉树;每合并一次,森林中就减少一棵树,产生一个新结点。
显然要进行n-1次合并,所以共产生n-1个新结点,它们都是具有两个孩子的分支结点。
由此可知,最终求得的哈夫曼树中一共有2n-1个结点,其中n个结点是初始森林的n个孤立结点。
并且哈夫曼树中没有度数为1的分支结点。
我们可以利用一个大小为2n--1的一维数组来存储哈夫曼树中的结点。
哈夫曼编码是可变字长编码。
编码时借助哈夫曼树,也即带权路径长度最小的二叉树,来建立编码。
译码的基本思想是:
读文件中编码,并与原先生成的赫夫曼编码表比较,遇到相等时,即取出其对应的字符存入一个新串中。
2.2算法结构定义
结构体存储表示
typedefstruct{
intweight;
intparent,lchild,rchild;
}Htnode,*Hfmtree;//动态分配数组存储哈夫曼树
typedefchar**Hfmcode;//动态分配数组存储哈弗曼编码表
第3章详细设计
3.1功能流程
此流程图为构造哈夫曼树的过程,输入字符的次数为权值对每个结点赋值,构造哈夫曼树,如图3.1
图3.1流程图
此流程图(图3.2)为对字符进行哈夫曼编码的过程,将字符转化为哈夫曼编码。
图3.2字符编码模块流程图
第4章系统实现
4.1错误分析
在此程序调试过程中主要遇到以下几类问题:
1、本程序运用了对文件进行操作,一定要注意在操作文件是文件的位置,我在做次程序是就是因为操作的文件位置错了导致程序无法正常运行。
2、在函数内部有时需要多定义参数,注意参数的作用域,而且注意传引用调用和传值调用的区别,不能不正确的修改实参的值,否则会导致程序运行的错误。
3、本程序用到的外部函数较多,在调用时一定要注意传入的参数是否符合函数的定义,而且位置也不能错,这是引用函数要注意的一点。
4、刚开始时清屏函数运用出错,导致操作界面消失,使用户无法操作,因此,在使用一些函数是一定要注意。
4.2运行结果
运行程序首先出现界面图,如图4.2所示。
图4.1界面图
选择操作1后,输入相应的字符大小,字符和权值,生成哈夫曼树。
系统会显示每个字符的哈夫曼编码,如图4.2所示。
图4.2程序运行截图
选择操作2后,输入字符串,系统会显示对字符串进行哈弗曼编码得到的哈弗曼编码,显示以下界面(图4.3)供用户选择。
图4.3程序运行截图
选择操作3后,系统会显示用哈夫曼编码翻译成的字符,显示以下界面(图4.4)供用户选择
图4.4程序运行截图
选择操作4后,退出系统,显示以下界面(图4.5)
图4.5程序运行截图
参考文献
[1]严蔚敏.数据结构(C语言版).清华大学出版社,2007
[2]谭浩强.C语言程序设计教程.高等教育出版社,2006
[3]苏仕华.数据结构课程设计.机械工业出版社,2007
附录
源程序如下:
#include
#include
#include
#include
#include
typedefstruct{//赫夫曼树的结构体
charch;
intweight;//权值
intparent,lchild,rchild;
}Htnode,*Hfmtree;//动态分配数组存储赫夫曼树
typedefchar**Hfmcode;//动态分配数组存储赫夫曼编码表
voidSelect(Hfmtree&HT,inta,int*s1,int*s2)//Select函数,选出HT树到a为止,权值最小且parent为0的2个节点
{
inti,j,x,y;
for(j=1;j<=a;++j){
if(HT[j].parent==0){
x=j;
break;
}
}
for(i=j+1;i<=a;++i){
if(HT[i].weight x=i;//选出最小的节点 } } for(j=1;j<=a;++j){ if(HT[j].parent==0&&x! =j) { y=j; break; } } for(i=j+1;i<=a;++i) { if(HT[i].weight =i) { y=i;//选出次小的节点 } } if(x>y){ *s1=y; *s2=x; } else { *s1=x; *s2=y; } } voidHfmcoding(Hfmtree&HT,Hfmcode&HC,intn)//构建赫夫曼树HT,并求出n个字符的赫夫曼编码HC { inti,start,c,f,m,w; intp1,p2; char*cd,z; if(n<=1){ return; } m=2*n-1; HT=(Hfmtree)malloc((m+1)*sizeof(Htnode)); for(i=1;i<=n;++i)//初始化n个叶子结点 { printf("请输入第%d字符信息和权值: ",i); scanf("%c%d",&z,&w); while(getchar()! ='\n') { continue; } HT[i].ch=z; HT[i].weight=w; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(;i<=m;++i)//初始化其余的结点 { HT[i].ch='0'; HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=n+1;i<=m;++i)//建立赫夫曼树 { Select(HT,i-1,&p1,&p2); HT[p1].parent=i; HT[p2].parent=i; HT[i].lchild=p1; HT[i].rchild=p2; HT[i].weight=HT[p1].weight+HT[p2].weight; } HC=(Hfmcode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; //-------从叶子到根逆向给出每个字符的哈夫曼编码-------------- for(i=1;i<=n;++i) { start=n-1;//编码起始符位置 for(c=i,f=HT[i].parent;f! =0;c=f,f=HT[f].parent)//从叶子到根逆向求编码 { if(HT[f].lchild==c) { cd[--start]='0'; } else { cd[--start]='1'; } } HC[i]=(char*)malloc((n-start)*sizeof(char));//为地i个字符编码分配空间 strcpy(HC[i],&cd[start]); } free(cd); } voidmain() { charcode[100],h[100],hl[100]; intn,i,j,k,l; ifstreaminput_file;//文件输入输出流 ofstreamoutput_file; charchoice,str[100]; HfmtreeHT; HfmcodeHC; while(choice! ='4')//当choice的值4时循环 { printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("*************************赫夫曼编码/译码器*************************\n"); printf("*************************1创建哈夫曼树*************************\n"); printf("*************************2编码*************************\n"); printf("*************************3译码*************************\n"); printf("*************************4退出*************************\n"); printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"); printf("请输入您要操作的步骤"); cin>>choice; if(choice=='1')//初始化赫夫曼树 { cout<<"请输入字符个数: "; cin>>n; Hfmcoding(HT,HC,n); for(i=1;i<=n;++i) { cout< "< } output_file.open("hfmTree.txt"); if(! output_file){ cout<<"can'toenfile! "< } for(i=1;i<=n;i++) { output_file<<"("< } output_file.close(); printf("赫夫曼树已经创建完毕,并且已经放入hfmTree.txt文件中! \n"); } elseif(choice=='2')//进行编码,并将字符放入A.txt,码值放入B.txt中 { printf("请输入字符: "); gets(str); output_file.open("A.txt"); if(! output_file) { cout<<"can'toenfile! "< } output_file< output_file.close(); output_file.open("B.txt"); if(! output_file){ cout<<"can'toenfile! "< } for(i=0;i for(j=0;j<=n;++j) { if(HT[j].ch==str[i]) { output_file< break; } } } output_file.close(); cout<<"\n"; printf("编码完毕,并且已经存入B.txt文件! \n"); input_file.open("B.txt");//从B.txt中读入编码,输出在终端 if(! input_file) { cout<<"can'toenfile! "< } input_file>>code; cout<<"编码码值为: "< input_file.close(); } elseif(choice=='3')//读入B.txt中的编码进行译码,将译出来的字符放入Textfile.txt中 { input_file.open("B.txt"); if(! input_file){ cout<<"can'toenfile! "< } input_file>>h; input_file.close(); output_file.open("Textfile.txt"); if(! output_file) { cout<<"can'toenfile! "< } k=0; while(h[k]! ='\0')//先用编码中的前几个和字符的编码相比较,然后往后移 { for(i=1;i<=n;i++){ l=k; for(j=0;j hl[j]=h[l]; } hl[j]='\0'; if(strcmp(HC[i],hl)==0) { output_file< k=k+strlen(HC[i]); break; } } } output_file.close(); input_file.open("Textfile.txt"); if(! input_file){ cout<<"can'toenfile! "< } input_file>>h; cout< input_file.close(); printf("译码结束,字符已经存入Textfile.txt文件中! \n"); } elseif(choice=='4') { exit(0); } else//如果选了选项之外的就让用户重新选择 { printf("您没有输入正确的步骤,请重新输入! "); } } } 课程设计总结: 通过近两周的课程设计使我对哈夫曼树以及哈夫曼编码译码有了更深的认识和理解,也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。 在做课设的过程中我也遇到了很多问题: 开始的时候,代码中有许多的错误,特别是有一个“无法找到文件”的错误让我束手无策,最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。 然后在实现文章的读入时,由于对文件不是太熟悉,只好翻开C语言和C++语言书本仿照其模式编写,但后来进入了死循环,最后的解决方式是在main函数里有一个控制语句使用不正确。 我们遇到问题很正常,说明我们掌握的知识还是太少不灵活,并且这些错误也让我明白了一个道理---细节决定成败。 同时,对于编程者而言,思路清晰是相当重要的。 在适当的时候和同学一起交流探讨是一个十分好的学习机会。 请教老师和同学也很重要,毕竟对待同一问题我们会有不同的理解和分析,相互之间的交流也是一种学习方法的沟通。 通过这次课程设计,我看清楚了自己的编程功底和动手能力还不如人意,这主要是平时实践太少的缘故。 我想,在即将到来的寒假中,我会努力尝试编写一些程序,争取提高自己的编程水平。 我相信通过我的不断努力,我一定能收获更多果实。 指导教师评语: 指导教师(签字): 年月日 课程设计成绩
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼 编码 译码器 概要