2023年新版哈夫曼树实验报告.docx

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

1、计算机科学与技术学院数据结构实验报告班级 2 02 3级计算机1班 学号姓名 张建华 成绩实验项目简朴哈夫曼编/译码的设计与实现 实验日期一、实验目的本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问 题的能力。二、实验问题描述运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传输时间，减少传输成本。但是,这规定 在发送端通过一个编码系统对待传数据预先编码,在接受端将传来的数据进行译码,此实验即设计这样的一个 简朴编/码系统。系统应当具有如下的几个功能：1、接受原始数据。从终端读入字符集大小n ,以及n个字符和n个权值，建立哈夫曼树，并将它存于文献

2、hfmtree. da t 中。2、编码。，运用已建好的哈夫曼树（如不在内存，则从文献h fmtree. dat中读入），对文献中的正文进行编码, 然后将结果存入文献codefile, dat中。3、译码。运用已建好的哈夫曼树将文献co defile, dat中的代码进行译码,结果存入文献text file, dat 中。4、打印编码规则。即字符与编码的一一相应关系。5、打印哈夫曼树，。将已在内存中的哈夫曼树以直观的方式显示在终端上。三、实验环节1、实验问题分析1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组Huff No de保存哈夫曼树中各结点的信息，

3、根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组Hu f f Nod e的大小设立为 2n-1,描述结点的数据类型为：Typede f str c ut（I nt w e i ght ； /* 结点权值* /Int parent;I nt Ichi Id；I nt r c h i I d；）HNod e T ype;2、求哈夫曼编码时使用一维结构数组Huf f Cod e作为哈夫曼编码信息的存储。，求哈夫曼编码，实质上就是在已建立的哈夫曼树中,从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值，由于一个字符的

4、哈 夫曼编码是从根结点到相应叶子结点所通过的途径上各分支所组成的0、1序列，因此先得到的分支代码为所 求编码的低位码,后得到的分支代码位所求编码的高位码，所以设计如下数据类型：#def ine MAXB IT 10Typed e f struct（。 Int bitMAXBIT;Int sta r t; HCodeT ype;3、文献 hfmtre e . datv codef i Ie. dat 和 textfi I e . dato2、功能（函数）设计（1）、初始化功能模块。此功能模块的功能为从键盘接受字符集大小n，以及n个字符和n个权值。(2 )、建立哈夫曼树的功能模块。此模块功能为使用

5、1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即将HuffN ode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文献h f mtr e e.dat中。(3)、建立哈夫曼编码的功能模块。此模块功能为从文献hfmtree.dat中读入相关的字符信息进行哈夫曼编码，然后将结果存入cod efile.dat中,同时将字符与0、1代码串的一一相应关系打印到屏幕上。(4)、译码的功能模块。此模块功能为接受需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文献t extfi 1 e.da t,同时将翻译的结果在屏幕上打印输出。(5)、打

6、印哈夫曼树的功能模块。此模块功能为从HuffNode数组中读入相关的结点信息，以图形的方式将各个结点以及叶子结 点的权值和左分支上的0和右分支上的1画出来。四、实验结果(程序)及分析1、实验重要代码t y pedef structt y pedef struct/*结点结构体*/string h fmstr;string h fmstr;/*结点内容*/ i nt weight；/ *结点权值*/i nt parent;int I chi Id;HNodeTy pe;ty p e d ef s t r u ctty p e d ef s t r u ct/*编码结构体*/i nt bit MA

7、X BIT;i nt start;)HCodeT y pe;/*创建哈夫曼树*/void Cre ate_Huf f M T r ee(HNodeType HFMTree, in t n )(，int m 1 , x 1 , m2, x2;int i, j;，for (i=0; i 2* n 1 ; i +)。(HFMTr e ei. h f m s tr = ; o HFMTree i . w e ight=0;o HFMTre e i. paren t =- 1 ;。HFMTreei. Ichi ld=- 1 ; HFMTreei. r chi I d = 1;)a f o r (i=0;

8、in;i+)。(cout请输入第 Vi+1个权值VHFMT reei .hfmstr;。f or(i = O;in-1;i+)(。x1=x2=MAXVALUE ;o ml = m 2=0; for (j=0； jn+i; j +) o if (HFMT r e ej. pare n t=-1& H FMT r eej . we i ghtx1)，。x2=x1 ； o o m2=m 1 ； o o x1 = HFMT r e ej. wei g ht; m 1 = j;， )。o 。 e Ise if (HFMT ree j . parent=-1&HFM T ree j . we i ght

9、x 2) ，。x2=HFMTree j. weight; a m2=j;d o )d 0 )HFMTreem1. pa r ent= n +i;HFMT r eem2. par e nt=n+ i ； o HFMTreen+i. weig h t=HFMTre e ml, wei g ht+HFMT r eem2 . we i g h t； HFMTre e n+i. Ich i I d =m1;。HFMTreen4- i . r ch i I d =m2 ;)，cout v”创建哈夫曼树成功！ endl；)void Haff ma n C ode (H Nod e T ype HFMT re

10、e , HCod e Typ e HuffCode, int n)/* 构建哈夫曼编码*/( HCodeT y pe cd;int i, j, c, p;for( i =O;in; i +)c d.start= n-1;c=i;p=HFMTreec. parent;whi I e (p! =- 1)if (HFMTre e p. I chi I d = c )cd. bit c d. start =0;e I secd. bi t cd. star t =1 ；cd. st a rt;c=p；p=HFMT r ee c . p are nt;for ( j =cd. sta r t+1; jn

11、； J4+)HuffC o d ei . bi t j = cd. b i tj;H u f f Codei. s ta r t = cd. s t a rt；)/*解码*/vo i d decodei n g (char str i ng, HNo d e T y pe HFM T ree, in t(in t i, t mp=0, co d e 1 024;i n t m=2*n-1 ；ch a r *n ump;c h ar num 1 024；f o r (i = O;istrlen ( s tr ing); i +)if ( stringi=O)num i=0;e I senum i

12、=1;)i=0；n ump=& n um0；while (nump (&num st r len (str i n g)(tmp=m-1;whil e (HFMTree tmp . Ichi ld!=-1)&(HFMTr e etmp. r child! =-1)(if (*nump=0)(tm p=HF M T r ee tmp. I child ；。 )elsetmp = HFMT r ee tmp. r ch i I d ;num p +;co u tHFM T ree tmp. hf m s tr;)cout e ndl;请输入m请输入第1个权值6请输入对应字符卷输入第2个权值请输入对应字符请输入第3个权值请输入对应字符曾输入第4个权值清输入对应字符请输入第5个权值请输入对应字符创建哈夫曼树成功！a111d00s-01f110h10请输入需要解密内容ladfhsa2、测试数据与输出EjPress any key to continue