《哈夫曼编码译码的设计与实现》由会员分享，可在线阅读，更多相关《哈夫曼编码译码的设计与实现（18页珍藏版）》请在金锄头文库上搜索。
1、. . .软件学院课程设计报告设计名称： 数据结构课程设计 选题名称： 哈夫曼编码/译码的设计与实现 姓 名：学 号：专业班级： 移动 一 班 系 院： 软件学院设计时间： 2014.6.12014.6.4 目 录一、需求分析-3二、系统设计-3三、 程序流程图-10四、实现代码-13五、总结-23六、参考书目-23 / . . .一、 需求分析哈夫曼编码是一种应用广泛且非常有效的数据压缩技术,哈夫曼编码是一种编码方式,以哈夫曼树,带权路径长度最小的二叉树,经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符进行编码。这张编码表的特殊在于,它是根据每一个源字符出现的估算概率而建立起来的。
2、哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码成为哈夫曼编码,树中从根到每个叶子都有一条路径,对路径上的各分支约定：指向左子树的分支表示0码,指向右子树的分支表示1码,取每条路径上的0或1的序列作为和各个叶子对应的字符的编码,这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进制代码。输入二进制代码时可以编译成字符串。二、 系统设计构造哈夫曼树时,使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1,求哈
3、夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,每回退一步,就走过了哈夫曼的一个分支,从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码为所求的高位码1、初始化功能模块此功能模块的功能为从键盘接受字符集大小n,以及n个字符和n个权值。2、建立哈夫曼编码的功能模块此模块功能为使用1中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树,即将HuffNode数组中的各个位
4、置的各个域都填上相关的值,并将这个结构体数组存于文件nodedata.dat中。函数原型为：void Creat_HaffmantreeHNodeType *HaffNode=new HNodeType2*n-1;int i,j;int m1,m2,x1,x2;fori=0;iHaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf=0;fori=0;icout请输入字符HaffNodei.inf;cout请输入该字符的权值HaffNodei.weight;fori=
5、0;i/构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;forj=0;j/选取最小和次小ifHaffNodej.parent=-1&HaffNodej.weightm2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseifHaffNodej.parent=-1&HaffNodej.weightm2=HaffNodej.weight;x2=j;/将找出的最小和次小合并,创造其父母结点HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNode
6、x2.weight;HaffNoden+i.lchild=x2;HaffNoden+i.rchild=x1;HaffNoden+i.inf=NULL;cout显示存储的哈弗曼树信息:endl; cout权值左孩子右孩子双亲endl; fori=0;i coutHaffNodei.inf ; coutHaffNodei.weight ; coutHaffNodei.lchild ; coutHaffNodei.rchild ; coutHaffNodei.parentendl;/写入文件fstream outfile1;outfile1.open;/建立进行写入的文件if /没有创建成功则显示相
7、应信息coutnodedata.dat文件不能打开endl;abort;fori=0;i /将内存中从HaffNodei地址开始的sizeof的内容写入文件中outfile1.write&HaffNodei,sizeof;outfile1.close ;/关闭文件delete HaffNode;3、建立哈弗曼编码功的功能模块此模块功能是从文件nodedata.dat中读入相关的字符信息进行哈弗曼编码,然后将结果存入code.dat中,同时将字符与0和1代码串的一一对应关系显示到屏幕上。函数原型为：void HaffCode/哈夫曼编码HNodeType *HaffNode=new HNodeT
8、ypeMaxnode;HcodeType *HaffCode=new HcodeTypeMaxleaf;HcodeType cd;int i,j,c,p;fstream in;in.readHaffNode,*sizeof;in.close;fstream outfile;outfile.open;/建立进行写入的文件fori=0;icd.start=n-1;c=i;p=HaffNodec.parent;whileifcd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;forj=cd.start+1;jH
9、affCodei.bitj=cd.bitj;HaffCodei.start=cd.start;fori=0;i outfileHaffNodei.inf;forj=HaffCodei.start+1;joutfileHaffCodei.bitj; cout字符信息-编码信息endl; fori=0;i coutHaffNodei.inf-; forj=HaffCodei.start+1;j coutHaffCodei.bitj; coutendl; outfile.close ;cout请输入要编码的字符串,基本元素为;fori=0;icoutHaffNodei.inf,;coutinf;in
10、t f=strlen;fstream outfile1;outfile1.open;/建立进行写入的文件if coutcode.dat文件不能打开!endl; abort; else coutendl; cout字符串编码后为:; forint x=0;x fori=0;i if forj=HaffCodei.start+1;j outfile1.write&HaffCodei.bitj,sizeof; coutHaffCodei.bitj; coutendl; cout编译后的代码串已经存入code.dat文件中!endl; coutendl; outfile1.close; delete HaffNode;delete HaffCode;4. 此模块功能为接收需要译
