




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1软件学院课程设计报告设计名称: 数据结构课程设计 选题名称: 哈夫曼编码/译码的设计与实现 姓 名: 学 号: 专业班级: 移动 一 班 系 (院): 软件学院 设计时间: 2014.6.12014.6.4 目 录一、需求分析-3 二、系统设计-33、 程序流程图-10四、实现代码-13五、总结-23六、参考书目-23数据结构课程设计报告 第 22 页 共 23 页1、 需求分析哈夫曼编码是一种应用广泛且非常有效的数据压缩技术,哈夫曼编码是一种编码方式,以哈夫曼树,带权路径长度最小的二叉树,经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符进行编码。这张编码表的特殊在于,它是根据每一
2、个源字符出现的估算概率而建立起来的。哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码成为哈夫曼编码,树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码,这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进制代码。输入二进制代码时可以编译成字符串。2、 系统设计构造哈夫曼树时,使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点
3、,所以数组HuffNode的大小设置为2n-1,求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,每回退一步,就走过了哈夫曼的一个分支,从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码为所求的高位码1、初始化功能模块此功能模块的功能为从键盘接受字符集大小n,以及n个字符和n个权值。2、建立哈夫曼编码的功能模块此模块功能为使用1中得到的数据按照教材中的构造哈弗曼的
4、算法构造哈弗曼树,即将HuffNode数组中的各个位置的各个域都填上相关的值,并将这个结构体数组存于文件nodedata.dat中。函数原型为:void Creat_Haffmantree(int &n)HNodeType *HaffNode=new HNodeType2*n-1;int i,j;int m1,m2,x1,x2;for(i=0;i2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf=0;for(i=0;in;i+)cout请输入字
5、符HaffNodei.inf;cout请输入该字符的权值HaffNodei.weight;for(i=0;in-1;i+)/构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;for(j=0;jn+i;j+)/选取最小和次小if(HaffNodej.parent=-1&HaffNodej.weightm1)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&HaffNodej.weightm2)m2=HaffNodej.weight;x2=j;/将找出的最小和次小合并,创造其父母结点HaffNodex1.pare
6、nt=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x2;HaffNoden+i.rchild=x1;HaffNoden+i.inf=NULL;cout显示存储的哈弗曼树信息:endl; cout权值左孩子右孩子双亲endl; for(i=0;i2*n-1;i+) coutHaffNodei.inf ; coutHaffNodei.weight ; coutHaffNodei.lchild ; coutHaffNodei.rchild ; c
7、outHaffNodei.parentendl; /写入文件fstream outfile1;outfile1.open(E:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立进行写入的文件if(!outfile1) /没有创建成功则显示相应信息coutnodedata.dat文件不能打开endl;abort();for(i=0;i2*n-1;i+) /将内存中从HaffNodei地址开始的sizeof(HaffNodei)的内容写入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile
8、1.close ();/关闭文件delete HaffNode;3、建立哈弗曼编码功的功能模块此模块功能是从文件nodedata.dat中读入相关的字符信息进行哈弗曼编码,然后将结果存入code.dat中,同时将字符与0和1代码串的一一对应关系显示到屏幕上。函数原型为:void HaffCode(int &n)/哈夫曼编码HNodeType *HaffNode=new HNodeTypeMaxnode;HcodeType *HaffCode=new HcodeTypeMaxleaf;HcodeType cd;int i,j,c,p;fstream in(E:nodedata.dat,ios:i
9、n|ios:binary);in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeType);in.close();fstream outfile;outfile.open(E:codedata.dat,ios:out|ios:binary);/建立进行写入的文件for(i=0;in;i+)cd.start=n-1;c=i;p=HaffNodec.parent;while(p!=-1)if(HaffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.pare
10、nt;for(j=cd.start+1;jn;j+)HaffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=0;in;i+) outfileHaffNodei.inf;for(j=HaffCodei.start+1;jn;j+)outfileHaffCodei.bitj; cout字符信息-编码信息endl; for(i=0;in;i+) coutHaffNodei.inf-; for(j=HaffCodei.start+1;jn;j+) coutHaffCodei.bitj; coutendl; outfile.close ();cout请
11、输入要编码的字符串,基本元素为(;for(i=0;in;i+)coutHaffNodei.inf,;cout)inf;int f=strlen(inf);fstream outfile1;outfile1.open(E:code.dat,ios:out|ios:binary);/建立进行写入的文件if(!outfile1) coutcode.dat文件不能打开!endl; abort(); else coutendl; cout字符串编码后为:; for(int x=0;xf;x+) for(i=0;in;i+) if(infx=HaffNodei.inf) for(j=HaffCodei.s
12、tart+1;jn;j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj); coutHaffCodei.bitj; coutendl; cout编译后的代码串已经存入code.dat文件中!endl; coutendl; outfile1.close(); delete HaffNode;delete HaffCode;4. 此模块功能为接收需要译码的0、1代码串,按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式,存入文件textfile.dat,同时将翻译的结果在屏幕上打印输出。接受0、1代码串有两种形式
13、,一种是直接输入,一种是从文件中读取。函数原型为:void decode( int &n)/解码int i;HNodeType *HaffNode=new HNodeType2*n-1;fstream infile1;infile1.open(E:nodedata.dat,ios:in|ios:binary);/读出哈夫曼树if(!infile1)coutnodedata.dat文件不能打开endl;abort();for(i=0;i2*n-1;i+)infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close(); int tem
14、pcode100;int num=0;for(i=0;i100;i+)tempcodei=-1;HcodeType *Code=new HcodeTypen;cout请选择要做的操作:endl;cout输入串解码,请按4endl;cout从文件中解码,请按5q;while(q5|q4)coutq;switch(q)case 4:cout请输入要解码的0,1串(按其他键结束输入):tempcodei;while(tempcodei=0|tempcodei=1)i+;num=i;cintempcodei;cout输入的编码为:;for(i=0;inum;i+)couttempcodei;coute
15、ndl;int m=2*n-2;i=0;cout译码后为:endl; fstream outfile; outfile.open(E:textfile.txt,ios:out); if(!outfile) couttextfile.txt文件不能打开!endl; abort(); while(inum)/ 小于字符串的长度 while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; coutHaff
16、Nodem.inf;outfileHaffNodem.inf;m=2*n-2; coutendl; outfile.close(); cout译码后的结果已经存入textfile.txt中!endl; delete HaffNode; break;case 5:fstream infile2;/读编码infile2.open(E:code.dat,ios:in|ios:binary);while(!infile2.eof()infile2.read(char*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-;cout从文件中
17、读出的编码为endl;for(i=0;inum;i+)couttempcodei; coutendl; int m=2*n-2; i=0; coutendl; cout译码后为:endl; fstream outfile; outfile.open(E:textfile.txt,ios:out); if(!outfile) couttextfile.txt文件不能打开!endl; abort(); while(inum)/ 小于字符串的长度 while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.l
18、child;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; coutHaffNodem.inf;outfileHaffNodem.inf;m=2*n-2; coutendl; outfile.close(); cout译码后的结果已经存入textfile.txt中!endl; delete HaffNode; break; 3、 程序流程图1. 系统结构图 哈夫曼编码译码器 退出 译码 编码 建树2. 各部分功能图建树: 开始 初始化哈夫曼链表且有2n-1个节点 i=1inweight=countip=p-next for(i=n;iParent-L
19、Child)HCi.code-HCi.start=1HCi.code-HCi.start=0 p=p-nexti=n时 结束译码: 开始Root指向根节点 P!=rootp=p-RChildcodei=0 p=p-LChildp-LChild=NULL&p-RChild=NULLsk+=strj p=root 结束4、 实现代码/#include stdafx.h#include#include#include#includeusing namespace std;#define MaxBit 10#define Maxvalue 100#define Maxleaf 100#define M
20、axnode Maxleaf*2-1typedef struct int weight;int parent;int lchild;int rchild;char inf;HNodeType;struct HcodeTypeint bitMaxBit;int start;void Creat_Haffmantree(int &n)HNodeType *HaffNode=new HNodeType2*n-1;int i,j;int m1,m2,x1,x2;for(i=0;i2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchi
21、ld=-1;HaffNodei.rchild=-1;HaffNodei.inf=0;for(i=0;in;i+)cout请输入字符HaffNodei.inf;cout请输入该字符的权值HaffNodei.weight;for(i=0;in-1;i+)/构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;for(j=0;jn+i;j+)if(HaffNodej.parent=-1&HaffNodej.weightm1)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&HaffNodej.weightm2)m2=H
22、affNodej.weight;x2=j;/创造其父母结点HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x2;HaffNoden+i.rchild=x1;HaffNoden+i.inf=NULL;cout显示存储的哈弗曼树信息:endl; cout权值左孩子右孩子双亲endl; for(i=0;i2*n-1;i+) coutHaffNodei.inf ; coutHaffNodei.weight ; cou
23、tHaffNodei.lchild ; coutHaffNodei.rchild ; coutHaffNodei.parentendl; /写入文件fstream outfile1;outfile1.open(E:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立进行写入的文件if(!outfile1) /没有创建成功则显示相应信息coutnodedata.dat文件不能打开endl;abort();for(i=0;i2*n-1;i+) /将内存中从HaffNodei地址开始的sizeof(HaffNodei)的内容写入文件中outfile1.writ
24、e(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/关闭文件delete HaffNode;void HaffCode(int &n)/哈夫曼编码HNodeType *HaffNode=new HNodeTypeMaxnode;HcodeType *HaffCode=new HcodeTypeMaxleaf;HcodeType cd;int i,j,c,p;fstream in(E:nodedata.dat,ios:in|ios:binary);in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeTy
25、pe);in.close();fstream outfile;outfile.open(E:codedata.dat,ios:out|ios:binary);/建立进行写入的文件for(i=0;in;i+)cd.start=n-1;c=i;p=HaffNodec.parent;while(p!=-1)if(HaffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;for(j=cd.start+1;jn;j+)HaffCodei.bitj=cd.bitj;HaffCodei.
26、start=cd.start;for(i=0;in;i+) outfileHaffNodei.inf;for(j=HaffCodei.start+1;jn;j+)outfileHaffCodei.bitj; cout字符信息-编码信息endl; for(i=0;in;i+) coutHaffNodei.inf-; for(j=HaffCodei.start+1;jn;j+) coutHaffCodei.bitj; coutendl; outfile.close ();cout请输入要编码的字符串,基本元素为(;for(i=0;in;i+)coutHaffNodei.inf,;cout)inf;
27、int f=strlen(inf);fstream outfile1;outfile1.open(E:code.dat,ios:out|ios:binary);/建立进行写入的文件if(!outfile1) coutcode.dat文件不能打开!endl; abort(); else coutendl; cout字符串编码后为:; for(int x=0;xf;x+) for(i=0;in;i+) if(infx=HaffNodei.inf) for(j=HaffCodei.start+1;jn;j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(H
28、affCodei.bitj); coutHaffCodei.bitj; coutendl; cout编译后的代码串已经存入code.dat文件中!endl; coutendl; outfile1.close(); delete HaffNode;delete HaffCode;void decode( int &n)/解码int i;HNodeType *HaffNode=new HNodeType2*n-1;fstream infile1;infile1.open(E:nodedata.dat,ios:in|ios:binary);/读出哈夫曼树if(!infile1)coutnodedat
29、a.dat文件不能打开endl;abort();for(i=0;i2*n-1;i+)infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close(); int tempcode100;int num=0;for(i=0;i100;i+)tempcodei=-1;HcodeType *Code=new HcodeTypen;cout请选择要做的操作:endl;cout输入串解码,请按4endl;cout从文件中解码,请按5q;while(q5|q4)coutq;switch(q)case 4:cout请输入要解码的0,1串(按其他键结
30、束输入):tempcodei;while(tempcodei=0|tempcodei=1)i+;num=i;cintempcodei;cout输入的编码为:;for(i=0;inum;i+)couttempcodei;coutendl;int m=2*n-2;i=0;cout译码后为:endl; fstream outfile; outfile.open(E:textfile.txt,ios:out); if(!outfile) couttextfile.txt文件不能打开!endl; abort(); while(inum)/ 小于字符串的长度 while(HaffNodem.lchild!
31、=-1&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; coutHaffNodem.inf;outfileHaffNodem.inf;m=2*n-2; coutendl; outfile.close(); cout译码后的结果已经存入textfile.txt中!endl; delete HaffNode; break;case 5:fstream infile2;/读编码infile2.open(E:code.dat,ios:in|ios:
32、binary);while(!infile2.eof()infile2.read(char*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-;cout从文件中读出的编码为endl;for(i=0;inum;i+)couttempcodei; coutendl; int m=2*n-2; i=0; coutendl; cout译码后为:endl; fstream outfile; outfile.open(E:textfile.txt,ios:out); if(!outfile) couttextfile.txt文件不能打开!endl; abort(); while(inum)/ 小于字符串的长度 while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+; coutHaffNodem.inf;outfileHaffNodem.inf;m=2*n-2; coutendl; outfile.close(); co
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年陪诊师考试高效学习路径与试题及答案
- 2024年监理工程师考试复习试题及答案
- 投资咨询工程师目标设定试题及答案
- 2024计算机二级考试攻关试题及答案
- 宠物殡葬中涉及的生物学常识试题及答案
- 黑龙江生态工程职业学院《法医学基础实验》2023-2024学年第二学期期末试卷
- 黑龙江省双鸭山市名校2025届高中毕业班阶段性测试(四)化学试题含解析
- 黑龙江省大庆十中2024-2025学年高三适应性联合考试数学试题试卷含解析
- 黑龙江省孙吴县第一中学2025年高三下学期质量监控(二模)生物试题试卷含解析
- 黑龙江省绥化市青冈县2024-2025学年高三第二次质量调研(二模)化学试题含解析
- (2025)新《公司法》知识竞赛题库(附含参考答案)
- 大象版小学科学四年级下册全册教案(教学设计)及反思
- DB37T5299-2024建设工程文明施工标准
- iso28000-2022供应链安全管理手册程序文件表单一整套
- 成都市绿色建筑施工图设计与审查技术要点及附表(2024版)
- 《预应力装配式混凝土框架结构技术标准》JGJT502-2024-知识培训
- T-CSUS 69-2024 智慧水务技术标准
- DBJ-T15-224-2021 广东省城市轨道交通公共卫生管理规范
- 妇联选举主持词
- 07K103-2 防排烟系统设备及附件选用及安装
- 新版高中物理必做实验目录及器材-(电子版)
评论
0/150
提交评论