数据结构课程设计哈夫曼编码.docx
- 文档编号:18358190
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:27
- 大小:191.62KB
数据结构课程设计哈夫曼编码.docx
《数据结构课程设计哈夫曼编码.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计哈夫曼编码.docx(27页珍藏版)》请在冰点文库上搜索。
数据结构课程设计哈夫曼编码
课程设计报告
课程名称数据结构
课题名称哈夫曼编码与译码
专业通信工程
班级通信0902
学号**********28
姓名肖俊
指导教师田娟秀、李杰君、张鏖烽
2011年07月01日
湖南工程学院
课程设计任务书
课程名称数据结构
课题哈夫曼编码与译码
专业班级通信0902
学生姓名肖俊
学号**********28
指导老师田娟秀、李杰君、张鏖烽
审批
任务书下达日期2011年06月27日
任务完成日期2011年07月01日
1设计内容与设计要求
1.1设计内容
课题五:
对电文中的字符串编码和译码
Huffman编码是一种最优变长码,即带权路径最小。
这种编码有很强的应用背景,是数据压缩中的一个重要理论依据。
对输入的一串文字符号实现Huffman编码,再对Huffman编码生成的代码串进行译码,输出电文字符串。
要求完成以下功能:
a)针对给定的字符串,建立Huffman树。
b)生成Huffman编码。
c)对编码文件译码。
1.2选题方案:
所选题目根据学号确定,学号模6加1,即(学号%6+1)。
如你的学号为9,则所选题目号为:
9%6+1=(题目4)。
注意,所有的课题都要求用图形方式演示步骤和结果。
有兴趣的同学可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。
1.3设计要求:
1.3.1课程设计报告规范
(1)需求分析
a.程序的功能。
b.输入输出的要求。
(2)概要设计
a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系;每个模块的功能。
b.课题涉及的数据结构和数据库结构;即要存储什么数据,这些数据是什么样的结构,它们之间有什么关系等。
(3)详细设计
a.采用C语言定义相关的数据类型。
b.写出各模块的类C码算法。
c.画出各函数的调用关系图、主要函数的流程图。
(4)调试分析以及设计体会
a.测试数据:
准备典型的测试数据和测试方案,包括正确的输入及输出结果和含有错误的输入及输出结果。
b.程序调试中遇到的问题以及解决问题的方法。
c.课程设计过程经验教训、心得体会。
(5)使用说明
用户使用手册:
说明如何使用你编写的程序,详细列出每一步的操作步骤。
(6)书写格式
a.设计报告要求用A4纸打印成册:
b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。
(7)附录
源程序清单(带注释)
1.3.2考核方式
指导老师负责验收程序的运行结果,并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评,并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。
具体考核标准包含以下几个部分:
(1)平时出勤(占10%)
(2)系统需求分析、功能设计、数据结构设计及程序总体结构合理与否(占10%)
(3)程序能否完整、准确地运行,个人能否独立、熟练地调试程序(占40%)
(4)设计报告(占30%)
注意:
不得抄袭他人的报告(或给他人抄袭),一旦发现,成绩为零分。
(5)独立完成情况(占10%)。
1.3.3课程验收要求
(1)运行所设计的系统。
(2)回答有关问题。
(3)提交课程设计报告。
(4)提交软盘(源程序、设计报告文档)。
(5)依内容的创新程度,完善程序情况及对程序讲解情况打分。
2进度安排
第19周:
星期一8:
00——12:
00上课
星期一14:
30——18:
30上机
星期二14:
30——18:
30上机
星期四8:
00——12:
00上机
附:
课程设计报告装订顺序:
封面、任务书、目录、正文、评分表、附件(A4大小的图纸及程序清单)。
正文的格式:
一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。
正文的内容:
一、课题的主要功能;二、课题的功能模块的划分(要求画出模块图);三、主要功能的实现(至少要有一个主要模块的流程图);四、程序调试;五、总结;六、附件(所有程序的原代码,要求对程序写出必要的注释)。
正文总字数要求在4500字以上(不含程序原代码)。
一.需求分析
1.程序的功能
能对输入的字符串实现Huffman编码,且能利用生成的编码对Huffman代码串进行译码,输出相应字符串。
2.输入输出的要求
首先,输入一个字符串,程序会列出字符串中包含的字符种类及每一种字符出现的次数,然后输出通过Huffman编码得到的各种字符的Huffman编码。
此时程序要求输入一串Huffman代码串,输入完毕程序会判断输入的代码串是否合法,若合法则输出译码结果。
二.概要设计
1.程序模块及其关系
程序由主函数模块,编码模块,译码模块组成,主函数模块可调用编码模块,译码模块,编码模块可对字符串进行编码,译码模块可对输入的代码串进行译码并输出。
各模块之间的关系示意图如下:
图1.各功能模块关系
2.课题涉及的数据结构
1.哈夫曼树类型HTNode(树形结构):
typedefstruct//哈弗曼树结点
{
chardata;//存储字符
doubleweight;//存储权值
intparent;//双亲结点位置
intlchild;//左右孩子结点位置
intrchild;
}HTNode;
HTNodeht[2n-1];
2.哈夫曼编码类型HCode(顺序结构)
typedefstruct//各叶子结点的哈弗曼编码
{
charcd[30];//cd[start]~cd[n]存储哈夫曼编码
intstart;//字符数组中哈夫曼编码的起始位置
}HCode;
HCodehcd[n];
3.CNode类型(顺序结构)
typedefstructCNode//用于保存字符频度的类型
{
charc;//存储出现字符种类
intnum;//字符出现次数
intflag;//存储字符是否出现的标记
};
CNodeCharNode[MAXV];
三.
详细设计
1.相关数据类型(采用C语言定义)
intcd[n];//储存哈夫曼编码
charstr[n];//储存需要编码的字符串
doubleweight;//储存字符出现频度(权值)
intlchild,rchild,parent;//储存哈夫曼树中各结点位置
2.各函数的调用关系图、主要函数的流程图
1.各函数调用关系
2.CreateHT函数
3.main函数
4.CreateHCode函数
3.各模块的类C码算法
1)编码模块:
首先通过键盘输入需要键盘的字符串,调用countstr()函数统计并储存字符频度,再调用函数:
voidCreateHT(HTNodeht[],intn)//构造哈弗曼树
{
inti,j,k,lnode,rnode;
doublemin1,min2;//分别存放lnode和rnode的两个结点位置
使所有结点的相关域置-1
for(i=n;i<2*n-1;i++)
{
先寻找权值最小结点,使其成为左右孩子结点;
再求出权值为左右孩子结点权值之和的h[i]结点;
使ht[i]作为双亲结点;
}
}
再调用:
voidCreateHCode(HTNodeht[],HCodehcd[],intn)
{
for(i=0;i { hc.start=n; c=i; f=ht[i].parent; 若ht[i]为ht[f]的左孩子结点,则 hc.cd[hc.start--]='0'; 若ht[i]为ht[f]的右孩子结点,则 hc.cd[hc.start--]='1'; 再对ht[f]进行同样的判断,直至f=-1 hc.start++; hcd[i]=hc; } } 2)译码模块: 先通过键盘输入哈夫曼编码代码串,再调用: intReadCode(charstr1[],HCodehcd[],HTNodeht[],intMAX,intn)//译码函数 { inti,j,m=0,k; intflag=1;//flag为1则哈弗曼编码输入合法 chartemp[30]=""; for(i=0;str1[i]! ='\0';i++,m++)//进行译码 { temp[m]=str1[i]; for(j=0;j { 若找到对应编码 { printf("%c",ht[j].data); for(k=0;k<30;k++) temp[k]='\0'; m=-1; 终止循环;} } } 四.调试分析以及设计体会 1.测试数据: 准备典型的测试数据和测试方案,包括正确的输入及输出结果和含有错误的输入及输出结果: 输入: 图6.编码输入演示图 输出: 图7.编码输出演示图 正确输入哈夫曼编码代号: 图8.正确译码输入演示图 输出: 图9.正确输入译码译码结果输出演示图 错误输入哈夫曼编码代号: 图10.错误输入哈夫曼编码代码串示意图 输出: 图11.错误输入哈夫曼编码代码串输出示意图 2.程序调试中遇到的问题以及解决问题的方法: 编写完译码函数ReadCode()后进行调试,程序会在译码过程中进入死循环,且无法译出正确字符串。 经过仔细观察,发现程序中有一个循环的终止条件本应为str[i]! =’\0’,却将其误写成了str[i]! =’\n’,因而无法正常终止循环并译码,改正后实现了译码功能。 3.课程设计过程经验教训、心得体会: 此次课程设计,我编写程序的时候遇到了不少问题,在攻克这些问题,最终实现课题任务的过程中,我学到了不少东西: 首先,在完成一个课题之前,要仔细理解课题要求。 我在此次课程设计中犯的最严重的错误,应该算没有仔细审题。 课题的要求是用读取文件的方式输入需要编码字符,译码所需的编码代号也要用文本方式输入。 我在拿到这个课题的时候,因为没有仔细理解这些要求,就采用了键盘输入字符进行编码和译码的方式,以致没有完全达到课题的要求。 另外,这次课程设计充分暴露了我的惰性思想。 在拿到这个课题后,因为对哈夫曼编码这个知识点理解比较到位,所以没花多少时间就完成了课题要求实现的功能。 然而,在此之后,我由于自我感觉良好和惰性,没有积极地去寻找改进程序的方法,也没对程序运行的界面进行美化,使其拥有良好的用户使用体验。 最终在答辩的时候,交给老师的是一个界面简陋,功能不全面的程序。 通过这次课程设计,我更加深入了理解了哈夫曼编码的过程,以及利用哈夫曼编码对数据进行压缩的优越性,并且使我能够更熟练地运用树形的数据结构。 并且体会到了在学习中,要严格要求自己,不能因为一点点的成功就骄傲自满,停止不前。 五.用户使用手册 1.运行程序,程序首先会要求你输入需要编码的字符串,输入完毕按回车即可进行编码: 图12.程序启动画面 输出: 图13.编码输出画面 2.输出编码后,程序会提示输入需要译码的哈夫曼编码串,输入后按回车即可进行译码: 图14.译码输入界面 输出: 图15.译码输出界面 3.译码结束后,输入a可退出程序,输入b可继续进行译码。 六.附录 源程序清单(带注释): typedef.h文件代码: #defineMAXV30 typedefstructCNode//用来保存字符次数的结构体 { charc; intnum; intflag; }; typedefstruct//哈弗曼树结点 { chardata; doubleweight; intparent; intlchild; intrchild; }HTNode; typedefstruct//各叶子结点的哈弗曼编码 { charcd[30]; intstart; }HCode; main.cpp文件代码: #include #include #include #include"typedef.h" #defineN100 externvoidinsertstr(charstr[]); externintcountstr(charstr[],CNode*); externvoiddispCNode(CNode*,int); externvoidCreateHT(HTNodeht[],int); externvoidCreateHCode(HTNodeht[],HCodehcd[],intn); externintDispHCode(HTNodeht[],HCodehcd[],intn); externvoidinsertstr1(charstr[]); externintReadCode(charstr1[],HCodehcd[],HTNodeht[],intMAX,intn); intn=0; voidmain() { inti; intMAX;//哈弗曼编码的最大长度 intflag=0;//标记哈弗曼编码输入是否合法 charchoice; charstr[N],str1[N]; CNodeCharNode[MAXV]; HTNodeht[100]; HCodehcd[50]; insertstr(str); printf("\n"); n=countstr(str,CharNode); printf("\n"); dispCNode(CharNode,n); printf("\n"); for(i=0;i { ht[i].data=CharNode[i].c; ht[i].weight=CharNode[i].num; } CreateHT(ht,n); CreateHCode(ht,hcd,n); MAX=DispHCode(ht,hcd,n); printf("\n"); while(flag==0) { insertstr1(str1); printf("\n"); printf("译码结果如下: \n"); flag=ReadCode(str1,hcd,ht,MAX,n); printf("\n请选择: a(退出)/b(继续译码)\n"); getchar(); scanf("%c",&choice); switch(choice) { case'a': exit (1);break; case'b': flag=0;break; } } } function.cpp文件代码: #include #include #include"typedef.h" #defineN100 voidinsertstr(charstr[])//输入字符串 { printf("请输入一个字符串: \n"); scanf("%s",str); } intcountstr(charstr[],CNode*CharNode)//记录字符出现次数,并保存在CNode中 { inti,j,a=0; for(i=0;i { CharNode[i].flag=-1; CharNode[i].num=0; CharNode[i].c='|'; } for(i=0;str[i]! ='\0';i++) { for(j=0;j { if(str[i]==CharNode[j].c) { CharNode[j].num++; break; } else if(CharNode[j].flag==-1) { a++; CharNode[j].c=str[i]; CharNode[j].num++; CharNode[j].flag=0; break; } } } returna; } voiddispCNode(CNode*CharNode,intn) { inti; printf("输入的字符极其出现次数如下: \n"); for(i=0;i { if(CharNode[i].flag! =-1) { printf("%c: ",CharNode[i].c); printf("%d\n",CharNode[i].num); } } } voidCreateHT(HTNodeht[],intn)//构造哈弗曼树 { inti,j,k,lnode,rnode; doublemin1,min2;//分别存放lnode和rnode的两个结点位置 for(i=0;i<2*n-1;i++)//所有结点的相关域置-1 ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n;i<2*n-1;i++) { min1=min2=32767; lnode=rnode=-1; for(k=0;k<=i-1;k++) if(ht[k].parent==-1) { if(ht[k].weight { min2=min1; rnode=lnode; min1=ht[k].weight; lnode=k; } elseif(ht[k].weight { min2=ht[k].weight; rnode=k; } } ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode;//ht[i]作为双亲结点 ht[lnode].parent=i;ht[rnode].parent=i; } } voidCreateHCode(HTNodeht[],HCodehcd[],intn)//求哈弗曼编码 { inti,f,c; HCodehc; for(i=0;i { hc.start=n; c=i; f=ht[i].parent; while(f! =-1) { if(ht[f].lchild==c) hc.cd[hc.start--]='0'; else hc.cd[hc.start--]='1'; c=f; f=ht[f].parent; } hc.start++; hcd[i]=hc; } } intDispHCode(HTNodeht[],HCodehcd[],intn)//输出哈弗曼编码 { inti,k; intj; intMAX=0; printf("输出哈弗曼编码: \n"); for(i=0;i { j=0; printf("%c: ",ht[i].data); for(k=hcd[i].start;k<=n;k++) { printf("%c",hcd[i].cd[k]); j++; if(j>=MAX) MAX=j; } printf("\n"); } returnMAX; } voidinsertstr1(charstr1[])//输入哈弗曼编码 { inti; for(i=0;i str1[i]='\0'; printf("请输入一串需要译码的哈弗曼编码: \n"); scanf("%s",str1); } intstrcompare(HCodehcd[],chartemp[],inta,intn)//字符串比较函数 { inti,j=hcd[a].start; charstr[30]=""; for(i=0;j<=n;i++,j++) { str[i]=hcd[a].cd[j]; } if(strcmp(str,temp)==0) return1; else return0; } intReadCode(charstr1[],HCodehcd[],HTNodeht[],intMAX,intn)//译码函数 { intstrcompare(HCodehcd[],chartemp[],inta,intn);//声明字符串比较函数 inti,j,m=0,k; intflag=1;//flag为1则哈弗曼编码输入合法 chartemp[30]=""; for(i=0;str1[i]! ='\0';i++,m++)//进行译码 { temp[m]=str1[i]; for(j=0;j { if(strcompare(hcd,temp,j,n))//存在对应编码 { printf("%c",ht[j].data); for(k=0;k<30;k++) temp[k]='\0'; m=-1; break; } } if(m>=MAX-1)//输入不合法 { printf("无译码,你所输入的编码不正确! \n"); flag=0; break; } } returnflag;//返回标记值 } 计算机与通信学院课程设计评分表 课程名称: 哈夫曼编码与译码 项目 评价 设计方案的合理性与创造性 设计与调试结果 设计说明书的质量
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 哈夫曼 编码
![提示](https://static.bingdoc.com/images/bang_tan.gif)