2023年数据结构哈夫曼编码实验报告.docx

《2023年数据结构哈夫曼编码实验报告.docx》由会员分享，可在线阅读，更多相关《2023年数据结构哈夫曼编码实验报告.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告一一实验五简朴哈夫曼编/译码的设计与实现本实验的目的是通过对简朴哈夫曼编/译码系统的设计与实现来纯熟掌握树型结构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几 个功能来设计和实现。一、【问题描述】。运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传输时间，减少传输成本。但 是，这规定在发送端通过一个编码系统对待传数据预先编码,在接受端将传来的数据进行译码, 此实验即设计这样的一个简朴编/码系统。系统应当具有如下的几个功能：1、接受原始数据。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文献n o de d a ta.da

2、 t 中。2、编码。运用已建好的哈夫曼树（如不在内存，则从文献nod e da t a .dal中读入），对文献中的 正文进行编码，然后将结果存入文献co de.dat中。3、译码。运用已建好的哈夫夏树将文献code.dal中的代码进行译码,结果存入文献lexlfile.dat 中。4、打印编码规则。即字符与编码的一一相应关系。二、【数据结构设计】。1、构造哈夫曼树时使用静态链表作为哈夫曼树的存偌。在构造哈夫曼树时，设计一个结构体数组HuffN o de保存哈夫曼树中各结点的信息,根据二 又树的性质可知，具有n个叶子结点的哈夫曼树共有2n-l个结点，所以数组Huf fNode 的大小设立为2n

3、-l,描述结点的数据类型为：t yp e def st r u c I for(j=H a ffCo d e i .start+l;jn； j+)00outf i lei. write (char* )& Ha f fC o dei .bitj,size o f(Ha f fCo d ei.bit j )；。8。cou tHa f f C o de i .bi t j;0 ) c out e ndl;。co utV”编译后的代码串已经存入co de. da t文献中！ Vendl;couten d 1;outfile 1. clos e ();dele t e H a ffNo d e ;de

4、lete HaffC o de;1void decode( int &n) /解码(in t i ;HNod e Ty p e *11 affNod e =ne w IINodeType2 * n-1 ;fstr e am i n file 1 ;oi n filel. o p en ( E: n o ded a ta.dat ,io s :in| i os:： bi n ary);/读出哈夫 曼树oi f (!infi 1 e 1 )c o ut * nodedat a . d a t 文献不能打开V V e n d 1;g a b o rt()；。of o r(i= 0 ; i 2*n l

5、;i+)n f i le 1 .read(char*)&HaffNod e i ,sizeof(HNo d eTy p e )；A n filel. c lose();i nt lem p c ode 1 0 0 ;in t num=0;for(i=0; i 100;i+)tempo o de i =-l;0H c odeT y pe *C o d e=new HcodeTypen；f st r e a m i nf i le2;读编码o i n file2.open(E： Wcode.dat, ios: i n|i o s :： binary);while(!infil e 2. e of(

6、)infi 1 e 2. r ead( char *)& t empco d e num, s i zeof(tempcode n u m);oonum+;i n file2.close();叫 u m;。c o u从文献中读出的编码为 endl;for (i= 0 ;inum; i +) couttempcodei ;coutend 1 ;int m=2*n-2；i= 0 ；c o u ten d 1 ;co u K 译码后为: e ndl;f s tr e am out file;out file.open ( E :textfile.tx t H,io s :： out);i f (!

7、o utf i 1 e)(cout tex tfilc.txt 文献不能打开!VVendl;a b or t ();)w h ile ( i n u m) / /小于字符串的长度(while (HaffNo d em. 1 c h il d ! = _1 &HaffNodem.r c h i Id !=-l)0 (if(tempcod e f i =0)o am=Ha f fN o d em .1c h il d ;oooa i +；。 )。 el s e if (temp c od e i= 1 )(om=Haf f Nodem. r c h i 1 d;i+ + ;c outHa f fN

8、od e m . i n f;o utfileHaf f Nodem.inf;0m=2* n -2;)c o u t endl;outfi 1 e. c 1 ose();c outV”译码后的结果已经存入textfi 1 e.t x t中!”Vend 1 ； delete Ha f fNo d e;i n t ma i n ()in t n;co u t * * * * 欢迎进入编/译码系统！*火* * * * * *cnd 1 ;i n t ch 1 ;do0COU t 1.建树” vvendl;cout cout 2:编码,并显示字符和相应的编码 V e ndl；C 0 utC 0 ut3

9、:译码 H endl;cou t 0:退出 vendl;c o utn* * * * * * * * * * * * * * * * *ch1 ；whi 1 e(!( c h 1 =0) 输入不在0到4之间无效 (。 coutVV”数据输入错误，请重新选择(04) :*;。 c in chi;00 switc h (ch 1 )(。ca s e 1 ：08。cou t V” t ll请输入编码个数“ V endl ;/叶子结点个数。o ci n n;C r e a t _Ha f fmantre e ( n );break；)。case 2: Haf f Co d e(n); bre a k;

10、case 3: d ecode(n); break； wh i 1 e (chi!=0)ore t u r n 0； )五、【运营与测试】1、令叶子结点个数n为4,权值集合为1, 3,5, 7,字符集合为A,B, C, D,并有 如下相应关系，A1、B3, C5,D7 ,调用初始化功能模块可以对的接受这些数据。2、调用建立哈夫曼树的功能模块,构造静态链表HuffNode的存储。3、调用建立哈夫曼编码的功能模块，在屏幕上显示如下相应关系：A1 1 I B110、C10、D0。4、调用译码的功能模块，输入代码串”后，屏幕上显示译码结果：0A BCDint we i g ht;/结点权值int pa

11、r e nt;in t 1 c h i Id;“n t r c hild;c har inf； H N o d eT y pe;2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域【可退 到根结点,没回退步,就走过了哈夫曼树的个分支，从而得到位哈夫曼码值，由于个字 符的哈夫曼编码是从根结点到相应叶子结点所通过的途径上各分支所组成的0、1序列，因 此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计 如下数据类型：#define MAXBIT 1 0ty p e d

12、 ef struct（oint b i tMA X BITJ;aint st a rt;Hc o dcTy p c；03、文献 nod e data.dat、c o d e .da t 和 text f il e . date三、【功能（函数）设计】1、初始化功能模块。此功能模块的功能为从键盘接受字符集大小n,以及n个字符和n个权值。2、建立哈夫曼树的功能模块。此模块功能为使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即 将HuffNode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文献hfmtree.d a t 中。3、建立哈夫曼编码的功能模块。此模块功能为

13、从文献n oded at a .d a t中读入相关的字符信息进行哈夫曼编码，然后 将结果存入c ode. d a t中,同时将字符与()、1代码串的一一相应关系打印到屏幕上。4、译码的功能模块。此模块功能为接受需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符 集中字符所组成的字符串形式，存入文献t ext file, dat，同时将翻译的结果在屏幕上打 印输出。四、【编码实现】# in c 1 udei n clude# i n cl u d e i n c 1 u de# define Ma x Bit 10de f inc Ma x valu e 10 0 /应当大于权重之和

14、# d e fine Maxie a f 1 00#d e fi n e M a xnode Maxlea f * 2 1typ e def s t r u ct(1 n t weig h t;in t pa r ent;int Ich i Id;in t rch i Id;c h a r i n f；)HN o deTyp e ;s t ruct HcodeT y p ein t bilM a xBit;。i n t s tart;；v o id Creat_ H af f ma n t r ee( i nt & n)(HNodeT ype *HaffNod e =new HNod e T

15、y pe2*n-l;int i ,j ；“ n t m l,m2, x 1 ,x2;for (i=0;i 2 * n 1; i +)(H a ffNod e i. we i g h t=0;Haf f Nodci. p arc n t = 1;HaffNodefi .Ic h i ld= - 1 ;“Haf f N o d e ij.rchild= 1;ooHaf f N ode i) f o r ( i =0; i n;i+)oo c ou t 请输入字符e nd 1 ;ooci n HaffNode i.inf;ocout”请输入该字符的权值en d 1 ;cinHa f f Nodef

16、i . w e i g h t ;。for (i=0;in-l； i+)/ / 构造哈夫曼树l=m2 = Maxva 1 ue；xl= x 2=0;gfor(j=0 ;jn+i;j + + )选取最小和次小(o i f (Ha f f No d ej.p a ren t =-l&Haf f Nodej. we i ghtml)8 (m2=m 1 ；ox2= x 1;om l=Ha f fN o dej. we i gh t ;8 OXl=j；)g e IseOd 。if ( H a ffNodefjl.par e nt=-l &HaffNo d ej.wei g h t m 2 )0o。 m2

17、=HaffNode j . w e i ght；8 8X 2 =j；)00 )0)。/将找出的最小和次小合并，发明其父母结点oHaffNode xlj. par e nt=n+i;。 HaffN ode x2.par e nt= n + i ；oHaf f N o d e n+i .we i g h t = H a ffNod e xl.w e ight+ H a f fN o dex2. wei g ht;Ha f fNode n + i. Ich i 1 d =x 1 ;。 HaffN o den+ i . rc h i ld = x2;HaffNode n +i. inf=N U LL;

18、0 Jooc o utI显示存储的哈弗曼树信息:vvendl;c out ”权值左孩子右孩子双亲 V Vend 1 ;f o r (i=0;i2* n -1 ;i + + )(cou tHa ffNodei. we i ghtn ” ；c o u t HaffN odei.lch i ldH ；c outHaffN o dei.rchild ；。 co u tHaffNo d ei. pa r e nt。 c o utH a f fNo d e i .i n fendl;0)。写入文献ofstr e a m o u t f il e 1 ;out f i 1 el.ope n ( E： nod

19、 e data, d a tios:out|ios:t r un c | i os:bin ary) ;/建立进行写入的文献 oif(! o u tf i lei) /没有创建成功则显示相应信息o c o u t nodedata.dat 文献不能打开end 1 ;abort();ofo r (i=0; i 2*n-1 ； i+) / / 将内存中从 H a f f N o dei地址开始的 siz e of (H af f Nodei)的内容写入文献中o u tfil e 1 .write(ch ar*) &HaffNode Li, s izeof(HaffNodei);u t fil e

20、1 . cl o se ()； /关闭文献。delete HaffN o de;v o id H aff C od e ( i n t & n )哈夫曼编码(oH No d eTy p e *Haf f Node= new HNodeTyp e Maxno de；oHcodeTy p e * HaffCo d e=ne w He o deTyp e Max 1 ea f ;He o deT y pe c d ;in t i, j, c , p;fst r e am in (E:no d eda t a. d a t H, i o s: i n|i o s: b i n ary);in.r e

21、a d (char *)H affN o d e,( 2 * n- 1 ) *size o f(HNode T yp e );i n. close (); f st r e am o u t f ile;o o ut f il e . o pen(HE: c ode d ata.da t n,ios:： out| i os:binary)； 建立进行写入 的文献of o r ( i = 0 ; i n;i+)(8cd. s ta r t=n-1 ；o c=i； p=HaffNodec.pare n t ;while(p! =-l)oif( Haff Node pj.lch i 1 d =c)c

22、d.b i t cd. s tart =0；e 1 se。c d.bilcd. s lart= 1 ;。 cd.s t art;。笺=p；。 p=Haf f No d e c .paren t ; oofor(j=cd. start+1; j n； j+)Haf f Cod e j = c d.bit j ;a ffCodei. s t art= c d. s t a rt;)for(i=0;i n;i+)( o u if i IeHaffNod e i, i n f;。for ( j = H affC o dcij. start+ 1 ;j n ； j +) ooo utf i leHaff

23、Code i.bi t j ;cout 字符信息-编码信息11(1 1 ;for( i =0； i n： i+)(。 cout Ha f fNo d ei. i nfvvf or( j = Haff Co d e i .s t art+1 ； j n ;j+) cout Haf f Cod eij.b i t j ;c o u ten d 1 ;outf i 1 e.c 1 ose ();co u tv”请输入要编码的字符串，基本元素为(”;for( i =0;in； i +)outH a f f Node i .in f;cou t )uen d 1 ;charinfl()();c i n

24、inf;in t f= s t r 1 e n(inf)；fstream o u tf i lei;u tfi 1 e l.open(E： Wcode.dat,ios:： out|ios： : b in a ry); / /建立进行写入的文 献oif ( ! outfilel)f c o u tMc o de. d a t 文献不能打开！ H endl；。a b ort()；)el s e cou tendl;。c outv字符串编码后为:“；for(in t x =0;xf;x+ + )(i f (infxJ=Ha f fNode i J.inf)f o r ( i =0； i n; i + + ) 0000000