![哈夫曼编译码---数据结构C语言版课程设计_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-4/17/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e1.gif)
![哈夫曼编译码---数据结构C语言版课程设计_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-4/17/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e2.gif)
![哈夫曼编译码---数据结构C语言版课程设计_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-4/17/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e3.gif)
![哈夫曼编译码---数据结构C语言版课程设计_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-4/17/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e4.gif)
![哈夫曼编译码---数据结构C语言版课程设计_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-4/17/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e/7f9cf2c4-3655-4ccb-b590-2b39ad3d949e5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、精选优质文档-倾情为你奉上数据结构课程设计报告设计题目 哈 夫 曼 (Huffman) 编/译 码 器 学院名称 信 息 工 程 学 院 专 业 班 级 12 计 本 2 姓 名 张 翠 翠 学 号 _ 题目:哈夫曼(Huffman)编/译码器一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 二、设计目标帮助学生熟练掌握树的应用和基本操
2、作,重点掌握二叉树的存储,这里以哈夫曼树为设计目标进一步提高学生的设计能力及对树的理解。三、任务要求一个完整的系统应具有以下功能: 1) I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。 2) E:编码(Encoding)。利用以建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 3) D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 4) P:
3、印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 5) T:印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。 四、需求分析利用哈夫曼树(Huffman)编/译码(一)、初始化哈夫曼树(二)、建立哈夫曼树(三)、对哈夫曼树进行编码(四)、输出对应字符的编码(五)、译码过程五、概要设计哈夫曼树的存储结构描述typedef structunsigned int weight;unsigned
4、int parent, lchild, rchild;HTNode, *HuffmanTree; 哈弗曼树的算法void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和
5、rnode记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weightmin1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /
6、两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点哈弗曼编码void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-=0; else /处理右孩子结点 hc.cdhc.star
7、t-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf( 输出哈夫曼编码:n); for (i=0;in;i+) /输出data中的所有数据,即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /输出所有data中数据的编码 printf(%c,hcdi.cdk); printf(n); void editHCode(
8、HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要进行编码的字符串存入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#为终止标志for (j=0;jn;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号,相同的就输出这个字符的编码for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /输出完成后跳出当前for循环哈弗曼译码void deHCod
9、e(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要进行译码的字符串存入code数组中while(code0!=#)for (i=0;in;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf(%c,hti.data);f
10、or(x=0;codex-1!=#;x+) /把已经使用过的code数组里的字符串删除codex=codex+j;主函数void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立结构体 HCode hcdN; /建立结构体
11、 for (i=0;in;i+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fnumi; while (flag) /菜单函数,当flag为0时跳出循环显示部分源程序: printf(n); printf( *); printf(n * 1-显示编码 *); printf(n * 2-进行编码 *); printf(n * 3-进行译码 *); printf(n * 4-退出 *n); printf( * *); printf(n); printf( 请输入选择的编号:); scanf(%c,&orz); switch(orz) case a: ca
12、se A: system(cls); /清屏函数 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(n按任意键返回.); 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
13、,hcd,n); printf(请输入编码(以#结束):n); deHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls); break; case d: case D: flag=0; break; default: system(cls); 六、详细设计字符空格ABCDEFGHIJKLM频度1866413223210321154757153220由上表画出哈夫曼树:由哈夫曼树得出各字符的编码:字符编码字符编码空格10D0001A010E1111BF11001C0000G01110关系调用:该程序的流程图:开始结点数是否大于1将data
14、和权值赋给ht输出根结点和权值调用selectmin函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点 点是否为根结点?左子是否为空?此时编码为0i=2*ni+编码为1结束否否否右子是否为空是是否否是是是七、测试分析白盒:查看代码完整性白盒测试也称结构测试或逻辑驱动测试,它是按照内部的结构测试程序,通过测试来检测产品内部动作是否按照设计规格说明书的规定正常进行,检验程序中的每条通路是否都能按预定要求正确工作。 这一方法是把测试对象看作一个打开的盒子,测试人员依据程序内部相关信息,设计或选择,对程序所有逻辑路径进行测试,通过在不同点检查程序的状态,确定实际的状态是否与预期的状态一致
15、。 黑盒:测试是否可以正确的创建,删除,插入,打印,查找等操作黑盒测试也称,它是通过测试来检测每个功能是否都能正常使用。在测试中,把看作一个不能打开的黑盒子,在完全不考虑程序内部结构和内部特性的情况下,在进行测试,它只检查程序功能是否按照需求规格说明书的规定正常使用,程序是否能适当地接收输入数据而产生正确的输出信息。黑盒测试着眼于外部结构,不考虑内部,主要针对和软件功能进行测试。八、使用说明1) 输入n个字符的权值2) 输入对应的字符3) 得出各字符的编码九、测试数据用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVO
16、RITE”。字符 空格 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 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1注:学生在测试数据时,需要写出测试用例和截图十、该程序的源代码#include #include /要用system函数要调用的头文件#include /用getch()要调用的头文件#include #define N 50 /义用N表示50叶节点数#define M 2*N-1 /用M表示节点总数
17、 当叶节点数位n时总节点数为2n-1#define MAXSIZE 100typedef struct char data; /结点值 int weight; /权值 int parent; /双亲结点 int lchild; /左孩子结点 int rchild; /右孩子结点HTNode; typedef struct char cdN; /存放哈夫曼码 int start; /从start开始读cd中的哈夫曼码HCode;void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; f
18、or (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weightmin1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk
19、.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (
20、i=0;in;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-=0; else /处理右孩子结点 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf( 输出哈夫曼编
21、码:n); for (i=0;in;i+) /输出data中的所有数据,即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /输出所有data中数据的编码 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要进行编码的字符串存入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#
22、为终止标志for (j=0;jn;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号,相同的就输出这个字符的编码for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /输出完成后跳出当前for循环void deHCode(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要进行译码的字符串存入code数组中while(code0!=#)for (i=0;in;i+)m=0; /m为想同编码个数的计数器
23、 for (k=hcdi.start,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已经使用过的code数组里的字符串删除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T
24、,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立结构体 HCode hcdN; /建立结构体 for (i=0;in;i+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fnumi; while (flag) /菜单函数,当flag为0时跳出循环 printf(n); printf( *); printf(n * A-显示编码 *); printf(n *
25、 B-进行编码 *); printf(n * C-进行译码 *); printf(n * D-退出 *n); printf( *); printf(n); printf( 请输入选择的编号:); scanf(%c,&orz); switch(orz) case a: case A: system(cls); /清屏函数 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(n按任意键返回.); 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); D
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- Unit 2 More than fun 第4课时Developing ideas (2) 教学设计 2024-2025学年外研版(2024)七年级英语上册
- 33 高考英语听力冲刺模拟训练(33)(教学设计)2025版高考英语听力冲刺模拟训练(提升篇)
- 职业病管理制度
- 玄武岩纤维复合材料骑行车架组(征求意见稿)编制说明
- RPA财务机器人开发与应用:基于华为WeAutomate-课件-模块一-RPA机器人认知
- 软件技术服务合同范本-1
- 某公司承包商管理制度范文
- 2023年浙江大学强基计划真题与解答
- 河道疏浚施工管理报告
- 2023年贵州贵州省铜仁凤凰机场有限责任公司招聘考试真题
- 小学英语《六年级上册单元教学计划》
- Unit1OurclassroomPartA(课件)闽教版英语四年级上册
- 校本活动课程无人机教案
- 2024年(高级)政工师理论考试题库及答案(含各题型)
- 基层减负工作实施方案
- 互联网医疗健康可行性研究报告
- 口腔种植体周围炎的病因、防治和修复
- 2021年全国高中化学竞赛陕西赛区试题及答案
- 大班交通安全家长会
- 存款保险知识课件
- 安全生产法律法规培训
评论
0/150
提交评论