2023年数据结构哈夫曼树的实验报告.pdf
软件学院设计性实验报告专 业：网络工程 年 级/班 级：2 0 2 3 2023学年第一学期课程名称数据结构指 导教师本组成员学号姓名实验地点实验时间项目名称哈夫曼编/译码系统的设计与实现实验类型设计性、实验目的理解哈夫曼树的特性及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码;通过该实验，使学生对数据结构的应用有更深层次的理解。二、实验仪器或设备学院提供公共机房,1台/学生微型计算机。三、总 体 设 计（设 计 原 理、设 计 方 案 及 流 程 等）1 .问题描述：运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传输时间，减少传输成本。但是，这规定在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。2.一个完整的系统应具有以下功能：1 ）初始化（I ni t i a 1 z a t i o n）.从数据文献D a t a F i l e.d a t中读入字符及每个字符的权值，建立哈夫曼树Hu f f T r e e;2）编码（En Co d i n g）。用已建好的哈夫曼树，对文献T oB e T r a n.d a t中的文本进行编码形成报文，将报文写在文献C od e,t x t中；3 ）译 码（D e c od i ng ）。运用已建好的哈夫曼树,对文献C o d e F i 1 e.d a t中的代码进行解码形成原文，结果存入文献T e x t f i l e .t x t中；4）输出（O u t p u t）:输出D a t a F i l e.d a t中出现的字符以及各字符出现的频度（或概率）；输出 T o B e T r a n.d a t 及其报文 C od e.t x t ；输出 C od e F i l e.d a t 及其原文 T e x t f i 1 e.t x t;规定:所设计的系统应能在程序执行的过程中,根据实际情况（不同的输入）建 立 Da t aFile.dat、ToBeTran.dat和 Cod e Fi 1 e.dat三个文献，以保证系统的通用性。四、实验环节(涉及重要环节、代码分析等)1)编写C语言程序#i n c 1 u d e#i n c 1 u d e#in c l u d eS in c 1 u d e#i n c l u d e#d ef i n eT R UE1#d e fin eF A L S E0#d efi n eO K1#d efin eER R O R0#d e f i n eI N F EAS I BLE-1t y p e d ef s t ru c t(ch ar d a t a;in t w e ight;o in t p a r e n t,1 c hil d,rc h i 1 d ;H T N o d e,H u ffm a n T ree;t y p ed e f c h a r*n Co d e；v o i d H u f f m a n C o d i n g(H u ffm a n T ree&H T,H u f f m a n Co d e&HC ,c h a r*d,i nt*w,i n t n)构造哈弗曼函数H T,构造编码H Cvoi d s e l e c t(Huf f m a n T r e e H T,in t n,in t&sl,i n t&S 2);ei n t m,c,f,j;H u ffm a n T ree p ;in t i ,s 1,s2,st a rt；c ha r*c d;m=2 n-l；/m为结点数，n为叶子数H T=(H u ffm a n T r e e)m a l l o c (m+l)*si z e o f(H T N o d e);叩=H T ;叩+;f o r(i=1;i d a t a=d i；/=*d ,*w,0,0,0;p-w eigh t =w i ;gp p a re n t=0；o p -l c hil d=0；gp-rc h i l d=0;)fo r(i=n+1;i d a t a=;p w e ight =0；p p a r e n t =0；p-1 c hil d=0;p-rc hil d=O;6S 1=1;s 2=2；fo r(i =n+l;i H T s 1.p a r e n t =i；H T s 2 .p a r en t=i;o H C=(H u f fm a n C o d e)m a l l o c(n+1)*siz eo f(H u ffm a n T re e);/开辟空间，编码 c d=(c h a r*)m a l l o c (n*siz eo f(c ha r);c d nT=0；fo r(i=l;i V=n;+i )。st a rt=n-l;f o r(c=i ,f=H T i.p a ren t;f!=0;c=f,f=H T f.p a r en t)。(b if(H T f.l c hil d=c )o c d-s t a rt =，O;el sec d -s t a r t =,1eH C i =(c ha r*)m a l l o c (n-s t a r t )*s iz eo f(c ha r)；st rc p y(H Ci ,&c d st a rt );。p ri n t f(c 的编码是：，H T i);。p u t s(H C i )；free(c d)；v o id sel ec t(H u f f m a n T ree H T,in t n,in t&sl,in t&s2)/求最小两数(ei n t i,t;o s 1=1；，s2=2;o w h i l e(H T s 1 .p a ren t!=0)sl+;o w h i l e(H T s2.p a r en t!=0)I(s l=s2)8 s2+;/*fo r(i=l;i H T i.w e ight&H T i .p aren t=0&s2!=i )o sl=i;i f(H T s 1 .w e i ght H T s 2.w eight)b t=S l；sl=s 2;s2=t ;fo r(i=l;i H T i.w eight&H T i .p a ren t=0)3 s 2=i;i“*/f o r(i=l;i=n ；i +)o (if(si!=i&i!=s2)6 if(H T i.w e i gh t H T si .w eig h t&H Ti .p a ren t=0&i!=s2)o i f(H T sl .w e i ght H T s2.w eight)s 2=s 1 ;sl=i;g e 1 seg if(H T i.w e i ght st r;t=H T；/t为树的指向各节点的指针6fo r(i=0;i(st r 1 e n (s t r)；i+)b if(s t ri=0)a t=H T t .I c hil d；比1 s e if(st r i =，17)g t =H T t .r c hil d;o e l s e8 18p rin t f（编码输入错误）；。b r e ak;0if(!(HT Lt.lchild&H T t.rchild)(g prin t f H T t.data);8t=num;a)prin t f(n)；)void main()(v o id H u ffm a n C o din g(Huff m a n T r e e&HT,HuffmanCo d e&H C,c h ar d,i n t w ,int n);void transla tio n(H u ff m a n T re e HT,i n t num);Hu f fmanT r e e HT=NULL;Huffman Code HC=NULL;char d a ta,n,*p,*d;i n t *w,wei,i,n um；pr i ntf(please i ntp u t c h a rac t er num b er：);oscanf(%d，&n);od=(ch a r*)ma 1 lo c(n+l)*s i z eof(c har)；ow=(int)ma 1 loc(n+l)*s i z eof(i n t);p r in t f（请输入H u f f m a n 树中的字符：n ）;fo r(i =1；i d a t a;d i =d a t a;)f ip ri n t f(请输入为d 次位权 n:,n);f o r (i =1;i =n;i+)6(c in w ei;w i =w ei;)n u m=2*n 1;H u f f m a n Co d in g(H T,H C,d ,w,n)：t r a n s l a t io n(H T,n u m);)2)程序分析此实验是构造哈夫曼树，求出哈夫曼编码然后输出构造哈夫曼树的算法操作时选出两棵根节点的权值最小的一颗树的左右子树，且置新树的根节点的权值为其左右子树上根节点的权值之和，根据哈夫曼树求出带权途径的算法操作是用递归调用的方法。在此实验的操作过程中要注意构造哈夫曼树的方法，由于在此操作的过程中用的的指针变量特别多，容易混淆。3)运营结果举例,C:UsersfzlDocumentsTencent Files1125653O39FileRecvDebugllq.exe*回please intput character nunber：?请 输 入f man树巾的字符：13-23456137911.或曰f否得否否否能zvJM-AHTflTa2.,1-i-LF-L-Z.1D-2.，二z.，：-d-10400011Rn10001011111001110输Press any key to continue五、结果分析与总结1）在做这个实验时前期要做很多准备，由于这个实验操作很复杂,虽然老师已经讲过了大体构思和算法思想，课本上也有相关算法及其伪代码，但翻译成C语言的过程要注意语法等因素,所以要查找一些资料。2）对于不懂得地方要像其他同学虚心请教。3）哈夫曼编码很考验编程者的细心限度，并且涉及的问题也很复杂，培养了我们的细心和耐心。教师署名：s年月
