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

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

1、数据结构实验报告实验题目： Huffm a n编码与解码姓名:学号:院系：。0 k= 1 ;whil e (s 2 =-l | |s2=sl)o if(HT k . paren t =0)。s 2=k;。k+;if(HTs 2 . weig h tHT si, wei g ht)。t =s2;s2= s 1； sl=t;。)for(k= 1 ;ki;k+)i f (HT k.parent=O)八if(HT k.wei g htHTsl. weigh t & k !=sl&k!=s2)00 。o s2=sl;。s l = k; o 。e 1 se if(H T k. weight=HT si.w

2、ei ght&k!=sl&k!= s 2) s2=k：v o id Huf f man C odin g (H u ffm a n Tree HT, c h ar *&HC,intn) (o Sq S t a ck S ；。InitSt a ck(S);。HC=(char*)m a II o c( n+l)*s i zeof(char*);Cod i ng (HT,HC,2*n-l,S);)void Cod i ng(HuffmanTree H T, c har *HCJnt roo t, S qStack &S)(i f (r o o t ! = 0 )。o i f(HT r o ot. 1

3、 c =0)(ooPush(S / 0)；。o H C r o o t=(ch ar* )ma 1 loc (S t ackLength(S)；st r c p y (H C root,S. e lem )；。Pop (S/ 0 );0 0 。P ush (S/ O);。Co d i ng(HT,HC, H T r oot .1 c ,S);oPop(S/0);o P ush(S/ 1);。 Co d i ng(HT 出C,HT r o ot.rc, S)：。Pop (S, 0 );v oi d I n i tStac k (SqSt a ck &S)0 S ,e 1 em=( c ha r

4、* )mall o c( s i z e*s i z e o f ( c h ar);S . s t a c k s i z e = siz e ；S. to p =-l;)vo i d P ush(Sq S ta c k & S ,char e)(。S.elem+S. t op = e;)vo i d P op(SqSta c k &S, char e)(if(S.t o p=-l) retu r n;e = S.el e mS.t o p -；。retur n；)i n t StackLeng t h (S q S tac k S)(。if (S. t op=-l) return( 0 )

5、;e r e t urn(S. t op);)int F i n d (ch a r a, c har s, i nt num)for( i =l;i = num; i +)o if (a=s i) retu r n i;。return 0 ;)i n t Recover(Huf f ma n Tr e e HT,cha r * HC,c h a r str i ng,cha r a, c ha r b ,i n t n)(i nt i =0,j= 0 , kzm = 0 , t=0, h = 0 ；o c h ar s s i ze; k=2* n 1；wh i 1 e (strin g i

6、)ooi f (!HTk.lc&! HTk.rc)(。if(s t r i ng i = =0) s j =O； k= 2 *n-l;t= 1 ； j= 0 ;i f (str i ngi=l,)0 0 0 I。sj = O;o k =2*n 1；。t =1;。J =0; 。 for(h=l; h = n ； h +) i f(!str c mp(HC h ,s)b m+=a h ;e 1 se。if(s t ring 0= O )k=HTk Jc； sj+= 0 ；。if (string i=z 1) 。k=HTk .rc;s j=z r；。j+；0 0。t=O； 00 i f(!t)。 i

7、 +;oif (!HTk .lc&! HT k .r c )ooo if(st r ing i-l=0，) sj = O, ;k=2*n-l;j=0;。 i f ( s trin g i -1 = 1 )0 0 0 I。sj =f O; k = 2 *n-l；。t= 1 ;。 J = 0 ;of o r (h=l; h O;if(k=2* n -1) r e t ur n 1 ;。else r et u rn 0;)实验名称：Huffman编码与解码实验问题描述：本实验需要以菜单形式完毕以下功能：1 .输入电文串2 .记录电文串中各个字符及其出现的次数3 .构造哈弗曼树4 .进行哈弗曼编码5

8、.将电文翻译成比特流并打印出来6 .将比特流还原成电文数据结构的描述：逻辑结构：本实验可用二叉树实现,其逻辑结构为一对二的形式，即一个结点相应两个结 点。在实验过程中我们也应用到了栈的概念。存储结构：使用结构体来对数据进行存储：t y pedef s tructin t w e igh t ;1 n t pa r ent, 1 c,rc;HTNode, *HuffmanTree;t y pe d e f st r uct LNodeb cha r * elem;。int st a ck s iz e ；。int to p ;S q Sta c k;在m a in函数里面定义一个哈弗曼树并实现上

9、述各种功能。程序结构的描述：本次实验一共构造了 1 0个函数：1 .void Hu f f T r e e (Hu f fm a nTre e &HT, i nt n ,int mun);此函数根据给定的mun个权值构建哈弗曼树，n0用于存放num个权值。2 . v o i d Selec t (HuffmanTre e &HT, int njnti, int &sljnt &s2);此函数用于在中选择paren t为0且we i ght为最小的两个结点, 其下标分别为slzs2.3 .vo i d Huffma n Cod i ng(Huf f man T ree H T,char * *&

10、H C,int n);此函数从哈弗.曼树HT上求得n个叶子结点的哈弗夏编码并存入数组HC 中。4 .v o i d C o d in g ( H uf f manTree H T ,char *H C , i n t root,S q Stack & S )；此函数用于哈弗曼编码，先序遍历哈弗曼树HT,求得每个叶子结点的编码字 符串，存入数组HC, S为一个顺序栈，用来记录遍历途径，root是哈弗曼数组HT 中根结点的位置下标。5 .voi d I n i t Stack(S q S t ac k & S )；此函数用于初始化一个栈。6 .voi d Pop( S q S tack &Szch

11、ar e)；此函数为出栈操作。7 .v o i d P ush (SqStack &Szc h ar e)；此函数为进栈操作。8.i n t S t a ckLengt h ( S q S tac k S )；此函数用于求栈长，返回一个i n t型的值。9.in t Fi n d(char a,cha r s, i nt n u m);此函数用于查找字符a在电文串中的位置。10.i n t R ecove r (H uff manTree Hl；char * * HC, c har st r ing 口 ,c h a r a,c h a r b, i nt n);此函数用于将比特流还原成电文。

12、调试分析：输入任意一个字符串，如输入welcometo u s tc:运营结果如下：又堂工XXXHHXX子： 电et口口出 口口口 口申树 Aom文文文文文文文文文曼*M12 2 12 11cwelcomtus数数数数数数数 次次次次次次次次次 现现现现现现现现现 出出出出出出出出出1.645哈弗曼编码：w ： 11108 ： 0111 ： 1111C ： 100D ： 101n : 000t ： 110u ： 001s ： 010该电文的哈弗曼编码为：请输入哈弗曼编码：按照提醒输入任意个或多个哈弗曼编码，如输入:请输入哈弗曼编码:Iwo结果对的。若输入一个111 11:请输入哈弗曼编码:11

13、111代码有误?.结果对的。实验完毕！实验体会和收获：本次实验提高了对哈弗曼树的结识，同时加深了对二叉树的理解.，在栈的运用上 更加纯熟,对数组的应用也有了提高。源代码：# i nc 1 u d e# i n c 1 u d e#i n c 1 ud e # incl u det y ped e f s t ruct。int we i ght;i n t paren t , 1 c, r c ；H T Node, * Hu f fm a n T r e e;ty p edef st rue t LN o de(char * e lem;i n t st a c k s i ze;。int to

14、p;SqSt a ck;# d e f i n e s i z e 2 0void HuffTree ( Hu f fmanTree & H Tjnt nJn t mun)；vo i d S elect (HuffmanTre e &HT, i n t njnt i Jnt &sl,i n t &s2)；v oid Huf f man C o ding(Hu f fmanTr e e HT,cha r *&H C , i nt n )；void Codi n g (Huff manT r e e HT,c h ar * * HCJ n t r oo t ,SqS t ack &S);void

15、In i t Stac k ( S qStack &S);v o id Pop(S q Sta c k &S,ch a r e )；void Pus h (S q S t ack & S ,char e);int St a ckLe n g t h(SqSt a ck S )；i nt F i n d ( c h ar a,c h a r s, i n t num);i n t R e cove r (Hu f f m a nT r e e HT,char *HC,cha r stri n gOhar a ,c h ar b,in t n);int m a in() i nt i =0,n s

16、 i z e= 0 ,j=O,k = l, n um= 0 ;ch a r strin g size = 0, msi z e=0,asize=0, b siz e =0;ch a r* HC;o Huffm a nTree HT；prin t f(”请输入电文串:n )；sc a nf( %s ,str i ng)；st r c p y (m,strin g );whi 1 e (strin g j)(。 i f (st r ing j ! =#) ak= s trin g j;i=j；。whi 1 e(str i ngi)。(。i f( s t r ing i= a k)0 0 I。s t

17、 ring =。nk+; i+；。i f (nk!=0 )0 0 1prin tf(该电文中字符c出现次数为d n,ak ,nk)；。0 n um+；k +：。p r i ntf (哈弗曼树:n“)；Huff T ree(HT,n, num);fo r (i=l; i = 2 * n u m-1； i +) print f ( %dt%d t %dt% d n,HTi.weig h tzHT i . p arentzH T i.l c 出T i.r c )；printf (“哈弗曼编码:n)3 H u ffmanC o ding(HT,HC,n u m);for (i= 1 ;i=num;i+

18、)，p r intf(% c : %s n u , a i ZHC i )；0)sprint f(n该电文的哈弗曼编码为:n )；。i= 0 ;owhi 1 e(string i )p r i nt f (%s ZHC F i n d (mi+zaz n um);P rintf ( n请输入哈弗曼编码: n)；sc a n f (% s H ,s t ring)；i f (Recove r (H7；HCzstr i n g ,a,b, n um) p r in t f( s n ，b );e e 1 se p r i ntf(代码有误!n);6 system (p a use);o r e t

19、 u r n 0;)void Huf f Tre e (Huf f m a n T re e &HTJn t nJn t num)i n t i,m, sl,s 2 ；o m=2*num-l;。HT=(Hu f fmanTree)mallo c (m + l)*sizeof ( HTN o de)；f or( i =l;i=m;i + +)。o HTi . w e ig h t=i=num?ni:0;HTi.lc=HT i .r c =HT i.pare n t=0;)for(i= n u m+l；i=m; i +)(o Select (HT,num,i,sLs2)；。 H T i. Ic=sl;HT i.rc=s2;HT i . w e i g ht = HTsl . w e ig h t+H T s2 .weigh t ;。 H T si.par e nt=HT s 2.parent= i ；。v o id S e lect (Huff ma n Tr e e &H T J n t n, i n t i , int&sl, int &s 2 ) i n t k,t;sl=s2=-l；。k= 1 ;o w h ile (sl=- 1 )。if (H T k. p arent=O)000 si = k ；k+;