实验五-哈夫曼编码与译码的设计与实现.doc

《实验五-哈夫曼编码与译码的设计与实现.doc》由会员分享，可在线阅读，更多相关《实验五-哈夫曼编码与译码的设计与实现.doc（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验五 哈夫曼编码与译码的设计与实现一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。基本要求：(1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存于文件nodedata。dat中.(2）编码：利用已建好的哈夫曼树（如不在内存,则从文件nodedata。dat中读入），对文件中的正文进行编码，然后将结

2、果存入文件code.dat中。(3）译码：利用已建好的哈夫曼树将文件code。dat中的代码进行译码,结果存入文件textfile。txt中。（4)打印编码规则：即字符与编码的一一对应关系。(5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。二、数据结构设计1、构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n1个结点,所以数组HuffNode的大小设置为2n1，描述结点的数据类型为：typedef struct int weight;int p

3、arent;int lchild；int rchild；char inf；HNodeType；2.求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位码.所以设计如下数据类型:define MaxBit 10struct HcodeTypeint bitMaxBit；

4、int start；;3、文件nodedata.dat、code.dat、textfile。txt三、功能函数设计1、初始化功能模块此功能模块的功能为从键盘接受字符集大小n，以及n个字符和n个权值。2、建立哈夫曼编码的功能模块此模块功能为使用1中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树，即将HuffNode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组存于文件nodedata.dat中.函数原型为：void Creat_Haffmantree(int &n)HNodeType HaffNode=new HNodeType2n1;int i，j;int m1，m2，x1，x

5、2；for(i=0；i2n1；i+）HaffNodei.weight=0;HaffNodei。parent=-1;HaffNodei。lchild=1；HaffNodei。rchild=1；HaffNodei。inf=0；for（i=0；in;i+）cout”请输入字符”HaffNodei.inf;cout”请输入该字符的权值HaffNodei.weight;for(i=0；in1；i+)/构造哈夫曼树m1=m2=Maxvalue；x1=x2=0；for（j=0;jn+i；j+）/选取最小和次小if(HaffNodej。parent=-1&HaffNodej.weightm1）m2=m1；x2

6、=x1；m1=HaffNodej。weight;x1=j；elseif（HaffNodej。parent=1&HaffNodej.weightm2）m2=HaffNodej.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显示存储的哈弗曼树信息:”

7、endl； cout”权值左孩子右孩子双亲”endl； for（i=0;i2n-1；i+） coutHaffNodei.inf” ; coutHaffNodei。weight” ； coutHaffNodei.lchild” ； coutHaffNodei。rchild” ； coutHaffNodei。parentendl; /写入文件fstream outfile1；outfile1。open(”E：nodedata。dat”,ios：outios：trunc|ios：binary)；/建立进行写入的文件if(！outfile1） /没有创建成功则显示相应信息coutnodedata。da

8、t文件不能打开”endl；abort（）；for（i=0;i2*n1；i+） /将内存中从HaffNodei地址开始的sizeof(HaffNodei）的内容写入文件中outfile1。write（(char）HaffNodei，sizeof（HaffNodei）);outfile1.close （）；/关闭文件delete HaffNode;3、建立哈弗曼编码功的功能模块此模块功能是从文件nodedata.dat中读入相关的字符信息进行哈弗曼编码，然后将结果存入code。dat中，同时将字符与0和1代码串的一一对应关系显示到屏幕上。函数原型为：void HaffCode（int &n）/哈夫

9、曼编码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*n1)sizeof（HNodeType);in。close（）；fstream outfile;outfile。open（”E:codedata.dat”,ios:：outios:：binary）；/建立进行写入的文件for（i=0;i

10、n；i+）cd.start=n1；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。start=cd。start;for（i=0；in；i+) outfileHaffNodei.inf;for（j=HaffCodei。start+1;jn；j+）outfileHaffCodei。b

11、itj； 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”）”endl；char inf100;cininf;int f=strlen(inf）；fstream outfile1;outfile1。open（”E：code.dat，ios：:out|

12、ios：:binary）；/建立进行写入的文件if(！outfile1） cout”code。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（HaffCodei.bitj）； coutHaffCodei.bitj； coutendl； cout”编译后的代码串已经存入cod

13、e。dat文件中！endl； coutendl； outfile1.close(）； delete HaffNode;delete HaffCode；4。 此模块功能为接收需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式,存入文件textfile.dat，同时将翻译的结果在屏幕上打印输出.接受0、1代码串有两种形式,一种是直接输入,一种是从文件中读取.函数原型为：void decode( int n)/解码int i；HNodeType HaffNode=new HNodeType2n1;fstream infile1；infile1。open（E：nod

14、edata.dat,ios：in|ios：:binary）；/读出哈夫曼树if（!infile1）cout”nodedata.dat文件不能打开”endl；abort（)；for(i=0；i2n1；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”从文件中解码，

15、请按5endl；int q；cinq；while(q5|q4)couttempcodei；cout”输入的编码为：”；for(i=0；inum；i+）couttempcodei;coutendl；int m=2n-2;i=0;cout译码后为：”endl； fstream outfile； outfile.open(”E：textfile。txt”，ios：out）; if（!outfile) cout”textfile。txt文件不能打开！”endl； abort（）； while(inum)/ 小于字符串的长度 while（HaffNodem.lchild！=-1HaffNodem。rch

16、ild！=1） if（tempcodei=0)m=HaffNodem。lchild；i+；else if(tempcodei=1）m=HaffNodem.rchild；i+； coutHaffNodem。inf；outfileHaffNodem。inf；m=2n2； coutendl; outfile。close()； cout”译码后的结果已经存入textfile.txt中!endl； delete HaffNode； break;case 5：fstream infile2；/读编码infile2.open（”E:code。dat”，ios：inios:binary);while(！inf

17、ile2.eof（)）infile2。read（(char*)&tempcodenum，sizeof（tempcodenum）；num+;infile2.close();num-；cout”从文件中读出的编码为”endl；for（i=0；inum;i+)couttempcodei； coutendl； int m=2n-2； i=0； coutendl； cout”译码后为：endl; fstream outfile; outfile.open（E:textfile.txt”，ios：out）; if（!outfile） cout”textfile.txt文件不能打开！”endl; abort

18、（); while（inum）/ 小于字符串的长度 while(HaffNodem.lchild！=-1HaffNodem.rchild!=-1） if(tempcodei=0）m=HaffNodem。lchild；i+;else if（tempcodei=1）m=HaffNodem。rchild;i+; coutHaffNodem。inf；outfileHaffNodem.inf;m=2*n2； coutendl; outfile。close(); cout”译码后的结果已经存入textfile。txt中！”includeincludestdlib.husing namespace std;

19、define MaxBit 10#define Maxvalue 100/应该大于权重之和define Maxleaf 100#define Maxnode Maxleaf*21typedef 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 HNodeType2n-1；int i，j;int m1，m2，x1，x2;f

20、or(i=0；i2*n1；i+）HaffNodei。weight=0;HaffNodei.parent=1;HaffNodei.lchild=1;HaffNodei。rchild=1；HaffNodei.inf=0；for（i=0;in；i+）cout请输入字符”HaffNodei.inf；coutHaffNodei.weight;for（i=0；in-1;i+）/构造哈夫曼树m1=m2=Maxvalue；x1=x2=0;for(j=0；jn+i;j+）/选取最小和次小if（HaffNodej。parent=-1HaffNodej。weightm1）m2=m1;x2=x1;m1=HaffNod

21、ej。weight；x1=j；elseif（HaffNodej。parent=1&HaffNodej.weightm2)m2=HaffNodej。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”权值左孩

22、子右孩子双亲endl; for(i=0；i2*n1;i+） coutHaffNodei.inf” ； coutHaffNodei.weight” ”； coutHaffNodei。lchild” ”; coutHaffNodei.rchild” ”; coutHaffNodei.parentendl； /写入文件fstream outfile1；outfile1。open(”E：nodedata。dat,ios:outios：truncios：binary);/建立进行写入的文件if（！outfile1） /没有创建成功则显示相应信息cout”nodedata。dat文件不能打开endl;ab

23、ort()；for(i=0；i2*n-1；i+） /将内存中从HaffNodei地址开始的sizeof（HaffNodei）的内容写入文件中outfile1.write（(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

24、 in（”E：nodedata.dat，ios：:inios:binary）;in。read（char*）HaffNode，(2n1）*sizeof（HNodeType)；in。close（)；fstream outfile；outfile。open（E：codedata.dat，ios：outios：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

25、-;c=p；p=HaffNodec.parent；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

26、; outfile。close （）;cout”请输入要编码的字符串，基本元素为(”；for（i=0；in;i+）coutHaffNodei。inf，”;cout）”endl；char inf100；cininf；int f=strlen(inf);fstream outfile1；outfile1。open（”E:code。dat”,ios：outios:：binary);/建立进行写入的文件if（!outfile1） cout”code.dat文件不能打开！”endl; abort（); else coutendl; cout”字符串编码后为:”; for（int x=0;xf；x+） f

27、or（i=0;in;i+） if(infx=HaffNodei。inf） for（j=HaffCodei。start+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;void decode( int n)/解码int i;HNodeType *HaffNod

28、e=new HNodeType2*n1；fstream infile1;infile1。open（”E:nodedata.dat，ios：in|ios:：binary）;/读出哈夫曼树if(！infile1）cout”nodedata.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 Hcode

29、Typen；cout请选择要做的操作：”endl；cout”输入串解码，请按4”endl；coutq；while(q5|q4）cout”输入错误请重新输入”;cinq;switch（q）case 4:cout请输入要解码的0,1串(按其他键结束输入）：”endl；i=0;cintempcodei；while(tempcodei=0tempcodei=1)i+；num=i；cintempcodei；cout”输入的编码为：”；for（i=0;inum；i+)couttempcodei;coutendl；int m=2*n2；i=0;cout”译码后为：endl； fstream outfile;

30、 outfile.open(”E：textfile。txt”,ios：out); if（！outfile） cout”textfile。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=2n-2; coutendl；

31、 outfile。close(）； cout译码后的结果已经存入textfile.txt中！”endl; delete HaffNode； break;case 5：fstream infile2;/读编码infile2.open（”E:code。dat，ios：:inios：binary)；while(!infile2.eof（)）infile2.read（char）tempcodenum,sizeof（tempcodenum）；num+；infile2。close();num-;cout从文件中读出的编码为”endl；for(i=0;inum;i+）couttempcodei； coute

32、ndl; int m=2n2； 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。rchi

33、ld；i+； coutHaffNodem。inf；outfileHaffNodem。inf;m=2*n2; coutendl; outfile。close（）； cout”译码后的结果已经存入textfile.txt中！”endl； delete HaffNode; break； int main（) int n；cout”* 欢迎进入编/译码系统!*”endl； int ch1；docout” 1。建树endl;cout 2：编码，并显示字符和对应的编码endl；cout” 3：译码”endl;cout” 0：退出”endl； coutch1；while(！（ch1=3ch1=0)） /输入

34、不在到之间无效coutch1； switch(ch1) case 1: cout”ttt请输入编码个数”endl；/叶子结点个数 cinn； Creat_Haffmantree（n)； break； case 2: HaffCode(n）； break; case 3： decode（n）; break； while(ch1!=0);return 0；五、界面设置在主函数中运用do while语句,使程序可以不断循环六、运行与测试1、令叶子结点个数n为4，权值集合为1，3,5，7,字符集合为A，B，C，D，并有如下对应关系，A1、B3，C5,D7,调用初始化功能模块可以正确接收这些数据。2、调用建立哈夫曼树的功能模块，构造静态链表HuffNode的存储.3、调用建立哈夫曼编码的功能模块，在屏幕上显示如下对应关系：A-011，B