哈夫曼编码译码设计与实现.docx

1、软件学院课程设计报告设计名称：数据结构课程设计选题名称：哈夫曼编码 / 译码的设计与实现姓名：学号：专业班级：移动一班系 （院）：软件学院设计时间：2014.6.12014.6.40/13目 录一、需求分析 -3二、系统设计 -3三、程序流程图 -10四、实现代码 -13五、总结 -23六、参考书目-231/13一、需求分析哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，哈夫曼编码是一种编码方式，以哈夫曼树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符进行编码。这张编码表的特殊在于，它是根据每一个源字符出现的估算概率而建立起来的。哈夫曼编码的应用很广泛

2、，利用哈夫曼树求得的用于通信的二进制编码成为哈夫曼编码，树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“ 0”码，指向右子树的分支表示“ 1”码，取每条路径上的“ 0”或“ 1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进制代码。输入二进制代码时可以编译成字符串。二、系统设计构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组 HuffNode 保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点，所以数组 HuffNode 的大小设置

3、为 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请输入字符 Haff

5、Nodei.inf;2/13cout请输入该字符的权值 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.pa

6、rent=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;coutHaff

7、Nodei.parentendl;/写入文件fstream outfile1;out(E:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立进行写入的文件 if(!outfile1) / 没有创建成功则显示相应信息coutnodedata.dat文件不能打开 endl;abort();3/13for(i=0;i2*n-1;i+) / 将内存中从 HaffNodei 地址开始的 sizeof(HaffNodei) 的内容写入文件中out(char*)&HaffNodei,sizeof(HaffNodei);out ();/ 关闭文件delete Haff

8、Node;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:in|ios:binary); in.re

9、ad(char*)HaffNode,(2*n-1)*sizeof(HNodeType); in.close();fstream outfile;out(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+)

10、HaffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=0;in;i+)outfileHaffNodei.inf;for(j=HaffCodei.start+1;jn;j+)outfileHaffCodei.bitj;4/13cout字符信息 -编码信息 endl;for(i=0;in;i+)coutHaffNodei.inf-;for(j=HaffCodei.start+1;jn;j+)coutHaffCodei.bitj;coutendl;out ();cout请输入要编码的字符串,基本元素为（ ;for(i=0;in;i+)coutHa

11、ffNodei.inf,;cout)inf;int f=strlen(inf);fstream outfile1;out(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+)out(char*)&HaffCodei.bitj,sizeof(HaffCod

12、ei.bitj); coutHaffCodei.bitj;coutendl;cout编译后的代码串已经存入 code.dat文件中 !endl; coutendl;out();delete HaffNode;delete HaffCode;5/134. 此模块功能为接收需要译码的 0、1 代码串，按照 3 中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文件 text，同时将翻译的结果在屏幕上打印输出。接受 0、1 代码串有两种形式，一种是直接输入，一种是从文件中读取。函数原型为：void decode( int &n)/ 解码int i;HNodeType *HaffNode=

13、new HNodeType2*n-1;fstream infile1;in(E:nodedata.dat,ios:in|ios:binary);/读出哈夫曼树if(!infile1)coutnodedata.dat文件不能打开 endl;abort();for(i=0;i2*n-1;i+)in(char*)&HaffNodei,sizeof(HNodeType);in();int tempcode100;int num=0;for(i=0;i100;i+)tempcodei=-1;HcodeType *Code=new HcodeTypen;cout请选择要做的操作： endl;cout输入串

14、解码，请按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;coutendl;int m=2*n-2;i=0;6/13cout译码后为： endl;fstream outfile;out(E:text,ios:out);if(!outfile)couttext 文件不能打开

15、 !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;out();cout译码后的结果已经存入text 中!endl;delete HaffNode;break;case 5:fstream in 读编码in(E:c

16、ode.dat,ios:in|ios:binary);while(!in()in(char*)&tempcodenum,sizeof(tempcodenum); num+;in();num-;cout从文件中读出的编码为endl;for(i=0;inum;i+)couttempcodei;coutendl;int m=2*n-2;i=0;7/13coutendl;cout 译码后为 :endl;fstream outfile;out(E:text,ios:out);if(!outfile)couttext 文件不能打开 !endl;abort();while(inum)/小于字符串的长度whi

17、le(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;out();cout译码后的结果已经存入text 中!endl;delete HaffNode;break;三、程序流程图1.系统结构图哈夫曼编码译码器建树编码译码退出8/132.各部分功能图建树：开始初始化哈夫曼链表且有2n-1 个节点i

18、=1inweight=countip=p-nextfor(i=n;iParent-LChild)HCi.code-HCi.start=0p=p-nextHCi.code-HCi.start= 19/13译码：p=p-RChildi=n 时 结束开始Root 指向根节点P!=rootcodei= 0p=p-LChildp-LChild=NULL&p-RChild=NULLsk+=strjp=root结束四、实现代码/#include stdafx.h#include#include#include#includeusing namespace std;#define MaxBit 10#define Maxvalue 100#define Maxleaf 100#define Maxnode Maxleaf*2-1typedef struct10/13int weight;int parent;int lchild;int rchild;char inf;HNodeType;struct HcodeTypeint bitMaxB