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

数据结构实验报告一 一 实验五 简朴哈夫曼编/译码的设计与实现本实验的目的是通过对简朴哈夫曼编/译码系统的设计与实现来纯熟掌握树型结构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现。一、【问题描述】。运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传输时间，减少传输成本。但是,这规定在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码,此实验即设计这样的一个简朴编/码系统。系统应当具有如下的几个功能：1、接受原始数据。从终端读入字符集大小n,以及n 个字符和n 个权值，建立哈夫曼树，并将它存于文献n o ded a ta.da t 中。2、编码。运用已建好的哈夫曼树（如不在内存，则从文献nod e da t a.dat中读入），对文献中的正文进行编码，然后将结果存入文献code.dal中。3、译码。运用已建好的哈夫曼树将文献code.dat中的代码进行译码,结果存入文献textfile.dat中。4、打印编码规则。即字符与编码的一一相应关系。二、【数据结构设计】。1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组HuffN o d e 保存哈夫曼树中各结点的信息,根据二叉树的性质可知，具有n 个叶子结点的哈夫曼树共有2n-l个结点，所以数组H u f fN ode的大小设立为2 n-l,描述结点的数据类型为：t yp e def st r u c tint we i g ht;/结点权值int par e nt;“n 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 ef struct（ointb i tMA X BIT;“nt st a rt;Hc o deTy p e；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、建立哈夫曼编码的功能模块。此模块功能为从文献n oded a t a.d a t 中读入相关的字符信息进行哈夫曼编码，然后将结果存入c ode.d a t 中,同时将字符与0、1 代码串的一一相应关系打印到屏幕上。4、译码的功能模块。此模块功能为接受需要译码的0、1 代码串，按照3 中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文献t e x tf i le.d a t,同时将翻译的结果在屏幕上打印输出。四、【编码实现】#in c 1 ude#i n clude#i n cl u d e#i n c 1 u de#define Ma xBit 10#de f ine Ma x valu e 10 0/应当大于权重之和#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(i n t weig h t;in t pa r ent;6int Ich i Id;in t rch i Id;c h a ri nf;HN o deTyp e;s t ruct HcodeT y p e(“n t bitM a xB it;。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 y pe2*n-l;int i,j；A n t m l,m2,x 1 ,x2;f o r (i=0;i 2*n 1;i+)oH a fTNod e i.we i g h t=0;Haf f Nodei.p are n t=-l;HaffNodei.Ich i ld=1;-Haf f N ode i.rchild=-l;ooHaf f N ode i.inf=O;)f o r(i=0;i vn;i+)o o c ou t ”请输入字符H e nd 1 ;sei n HaffNode i.inf;ocout”请输入该字符的权值”en d 1 ;。cinHa f f Node i.w e ig h t;f or(i=O;in-l；i+)/构造哈夫曼树6ml=m2=Max va 1 ue；xl=x 2=0;8for(j=0;jn+i;j+)选取最小和次小(bi f(Haf f No d efjl.p a ren t=-l&Haf f Nodej.we i ghtml)m2=m 1；。x2=x 1;0m l=Ha f fN o dej.we i gh t;)g e Iseg g if(H a ffNodej.par e nt=-l&HaffNo d ej.w ei g h t m 2)b e。m2=HaffNode L j.w e i ght；8 8X 2=j；)b 0。将找出的最小和次小合并，发明其父母结点oHaifNode xl.par e nt=n+i;。HaffN o d e Ex2.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 odex2.wei g ht;Ha f fNode n+i.Ich i 1 d=x 1;。HaffNoden+i.rch i ld=x2;HaffNode n+i.inf=N U LL;o ut显示存储的哈弗曼树信息:endl;c out 权值左孩子右孩子双亲V Vend 1 ;f o r(i=0;i2*n-1;i+)c ou t H a ffNodei.we i ght ；c o u t HaffN o dei.lch i ld；c outHaffN o dei.rchild。co u tHaffNo d ei.pa r e nto c o utH a f fNo d e i .i n fendl;e)。写入文献ofstr e a m o u t f il e 1；out f i 1 el.ope n(E：nod e data,d a t,ios:out|ios:t r un c|i os:binary)“/建立进行写入的文献。i f(!o utf i lei)/没有创建成功则显示相应信息 c o u t nodedata.dat 文献不能打开end 1 ;“abort。；ofo r(i=0;i 2*n-1；i+)/将内存中从 H a f f N o de口 地址开始的 sizeof(Ha ff N odei)的内容写入文献中so utfil e 1.write(ch ar*)&HaffNode i,s izeof(HaffNodei);o u t fil e 1 .cl o se()；/关闭文献。d elete ClHaffN o de;)void HaffCode(i n t&n)哈夫曼编码(bHNo d eTy p e*Haf f Node=new HNodeTyp e Maxno d e；HcodeTy p e*HaffCo d e=new He o deTyp e Max 1 ea f;eHc o deT y pe c d;“n t i,j,c,p;fst r e am in(nE:no d eda t a.d a t,i o s:i n|i o s:b i n ary);in.r e 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;6 o ut f il e.o pen(nE:c ode d ata.da t,ios:：out|i os:binary)；建立进行写入的文献油 o r(i=0;i n;i+)(8cd.s ta r t=n-1 ；。c=i；p=HaffNodec.pare n t;owhile(p!1)if(HaffNode p.lch i 1 d=c)cd.b i t cd.s tart=0；e 1 se。c d.bitcd.s tart=1 ;。cd.s t art-;8C=p;。p=Haf f No d e c.paren t;0)8 fol(j=cd.start+1;j n；j+)oHaf f Cod e j=c d.bit j;oeH a ffCodei.s t art=c d.s t a rt;)fbr(i=O;in;i+)(。o u tf i leHaffNod e i.i n f;a for(j=HaffC o dei.start+1 ;j n；j+)go u tf i leHa f fCod e i.bi t j;)cout n字符 信 息 编码信息“Wend 1 ；for(i=0；i n；i+)(e cout H a f fNo d ei.i n f n H;f or(j=HaffC o d e i.s t art+1；j n;j+)匕 cout Haf f Cod ei.b i t j ;c o u ten d 1 ;H)utf i 1 e.c 1 ose();co u tv”请输入要编码的字符串,基本元素为(”;for(i=0;in；i+)8 c o ut H a f f Nod e i .i n f,n;cou t H)n en d 1 ;c h ar i n f100;c i n in f;in t f=s t r 1 e n(inf)；fstream o u tf i lei;oo u tfi 1 e l.open(E：code.datn,ios:：out|ios：:b in a ry);/建立进行写入的文献“f(!o utfilel)(。c o u t nc o de.d a t 文献不能打开！H endl；3 a b ort()；el s e c o u tendl;3 c out”字符串编码后为for(in t x=O;xf;x+)(f o r(i=0；i n;i+)i f(infx=Ha f fNode i.inf)000。for(j=H a ffCo d e i.start+l;jn；j+)8。outf i 1 el.write(char*)&Ha f fC o dei.bitj,size o f(Ha f fCod ei.bitj )；。c o u t H a f f C o de i.bi t j;0 0)6)c out e n dl;o co u 编译后的代码串已经存入co d e.d a t文献中！vVendl;couten d 1;outfilel.clos e();dele t e LH a ffNo d e;delete HaffC o de;)void decode(int&n)/解码(in t i;HNod e Ty p e*H affNod e=ne w II NodeType2*1 ;fstr e am i n file 1;“n file 1.o p en(E:n o ded a ta.dat n,io s:in|i os:：bi n ary);/读出哈夫曼树o if(iin file l)c o u t n nodedat a.d a t 文献不能打开“V V e n d 1;a b o rt()；of o r(i=0;i 2*nl;i+)n f i le 1 .read(char*)&HaffNod e i,sizeof(HNo d eTy p e)；“n fiiel.c lose();i nt tern p c odef 1 0 0;“n t num=0;for(i=0;i 100;i+)tempc o de i =-l;出 c odeT y pe*C o d e=new HcodeTypen；f st r e a m i nf i le2;读编码ei n file2.open(nE：Wcode.dat,ios:i n|i o s:：binary);while(!infil e 2.e of()。infi 1 e 2.r ead(c h a r *)&t empco d e num,s i zeof(tempcode nu m);gnum+;i n file2.close();n u m;。c o u t”从文献中读出的编码为 endl;for(i=0;inum;i+)。couttempcodei ;coutend 1 ;int m=2*n-2；i=0;c o u ten d 1 ;co u t”译码后为:V e ndl;f s tr e am out f i l e;o u t file.open(E:textfile.tx t,io s:：out);i f(!o utf i 1 e)(coutn te x tfile.txt 文献不能打开!”Vvendl;a b or t();)w h ile(i n u m)/小于字符串的长度w h il e(HaffNo d em.1 c h il d!=1&HaffNodem.r c h i Id!=-l)(if(tempcod e i=0)3 b 0m=Ha f fN o d em.1c h il d;i+；)el s e if(temp c od e i=1)(gm=Haf f Nodem.r c h i 1 d;i+;c outH a f fNod e m.i n f;o u tfile H af f Nodem.inf;cm=2*n-2;)c o u t e n d l;outfi 1 e.c 1 ose();c outV”译码后的结果已经存入textfi 1 e.t x t中!”v en d 1 ；d e 1 e t e Ha f fN o d e;)i n t m a i n()(in t n;0 co u t vv”*欢迎进入编/译码系统！*vend 1 ;“n t ch 1;0 do cou t n1.建树“w e n d l;cout ”2:编码，并显示字符和相应的编码V e ndl；O C 0 U t 3:译码 n e n d l;b cou t n0:退出”endl;c o ut”*vchl；whi 1 e(!(c h 1 =0)输入不在0 到4 之间无效0。coutV V 数据输入错误，请重新选择(04):;。c in c hl;8 switc h(ch 1)(。ca s e 1：b 8 。cou t t tt请输入编码个数 e nd 1 ;/叶子结点个数。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;c a s e 3:d ecode(n);break；)w h ile(ch l!=0);。re t u r n 0；五、【运营与测试】1、令叶子结点个数n为4,权值集合为1,3,5,7 ,字符集合为A,B,C,D ,并有如下相应关系，A 1、B一一3,C-5,D-7,调用初始化功能模块可以对的接受这些数据。2、调用建立哈夫曼树的功能模块,构造静态链表HuflNode的存储。3、调用建立哈夫曼编码的功能模块，在屏幕上显示如下相应关系：A 一一1 11、B 一一110、C一一 10、D一一0。4、调用译码的功能模块，输 入 代 码 串 后，屏幕上显示译码结果：。-A BCD