哈夫曼树实验报告

1、数据结构实验报告实验名称 : 实验三哈夫曼树学生姓名：班级 :班内序号:学号：日期:程序分析 :、1 存储结构 :二叉树2、 程序流程 : m late < clas T> l s B ree ubl c：BiTree();?/?/?构造函数，其前序序列由键盘输入 i ee(voi ); ? ?/析构函数? Bi o <T> * Ge root() ；?/ 获得指向根结点得指针 protecte ：Bi d <T> *ro t;? / 指向根结点得头指针；/ 声明类 B Te及定义结构 BiNode ata:二叉树就是由一个根结点与两棵互不相交得左右子树构成

2、二叉树中得结点具有相同数据类型及层次关系data:?HCo * HCo Table ；/ 编码表 n Si e；二叉树得节点结构 e p ate <classstru t BiN deT data ；T ch d; ch ； ?T par t; ;示意图 :?TT data 编码表得节点结构 s uct H har har>T lchildode/编码表中得总字符数/ 二叉树得结点结构/ 记录数据 左孩子/ 右孩子双亲T rchildT parentdaa; c e100 ； /编码表中得字符/ 该字符对应得编码char data; 示意图：char code100待编码字符串由键

3、盘输入 , 输入时用链表存储 , 链表节点为 struct Node?char c ar ct r;?unsigne?bo?Nde*;示意图 :、3 i t counus ;ex;/ 输入得字符;/ 该字符得权值/ 建立树得时候该字符就是否使用过 / 保存下一个节点得地址char character关键算法分析 :1、初始化函数 （ id Huffma Tre:I t（st ing Input） 算法伪代码 :unsigned int countbool usedNode* next1、初始化链表得头结点2、获得输入字符串得第一个字符，并将其插入到链表尾部,n （记录得就是链表中字符得个数 ）

4、、从字符串第 2 个字符开始 ,逐个取出字符串中得字符3、1 将当前取出得字符与链表中已经存在得字符逐个比较,如果当前取出得字符与链表中已经存在得某个字符相同,则链表中该字符得权值加 1。、 2 如果当前取出得字符与链表中已经存在得字符都不相同，则将 其加入到链表尾部 ,同时 n+、 tSize=n（t ize 记录链表中字符总数，即哈夫曼树中叶子节点总数） 、创建哈夫曼树、销毁链表源代码 : void Huffm Tree： it（str n I put）Node *f ontnew Noe; /初始化链表得头结点i （!fr nt）?t row ex ption（ 堆空间用尽 "

5、）; fr> nex =NULL;fron >c ar e N ; ron> co nt=0;?ode *pfro =fr t;hr ch=Ipu0；/获得第一个字符Node* Ne = ew Node；? （！Ne 1）?thr w ex eption（" 堆空间用尽 ）;?N w1->chara er=c;/将第一个字符插入链表? w1->count=1;?New1- > next=pfro t->next ；?pfr nt->n t=New1;?bol re lce=0;/判断在已经写入链表得字符中就是否有与当前读出得字符相同得字

6、符itn=1;/统计链表中字符个数for(i t i=1;i<Inp t、legt();i +)ch Input do;/ 获得第个字符? pfront=p r t->next;if（ in ）pfr nt->character = （int） h） /如果在链表中有与当前字符 相同得字符，该字符权值加 1 ? fro -> nt ;?r?eplace=1；?b ak；?while（ front->next） ； f（!replace ）/如果在链表中没找到与当前字符相同得字符,则将该字符作为新成员插入链表 ?N?o e* =new ode；?i?（ !New）?

7、t rw e cept o （"堆空间用尽 "） ；?New- > aract r ch;? New >c unt=1;? ew->nex =p ront->n xt ； ?p?fr n->nxtNe； ? +；?p ro t=front ；认值?repl ce0;? Size=n；数?C eateHTee(front ，n);? fro =fr n;w ile(pfront)?r nt fon；? pfront=pfront- > n xt;? de et front;时间复杂度 :/重置 p r nt 与 repac变量为默/tSiz

8、记录得就是编码表中字符个/创建哈夫曼树/销毁整个链表若输入得字符串长度为 ,则时间复杂度为 O（n）2、创建哈夫曼树 （od Hu fm Tree:Cr ateCodeTa le（ ode p）算法伪代码 :1. 创建一个长度为 2*tSiz 1得三叉链表2. 将存储字符及其权值得链表中得字符逐个写入三叉链表得前tSiz个结点得 ata 域,并将对应结点得孩子域与双亲域赋为空3. 从三叉链表得第 tSiz个结点开始 ,i=tSiz 3.1 从存储字符及其权值得链表中取出两个权值最小得结点,y,记录其下标 x ， y。3.2 将下标为 x 与 y得哈夫曼树得结点得双亲设置为第i 个结点3.3 将

9、下标为 x 得结点设置为 i 结点得左孩子 ,将下标为 y 得结点设置为 i 结点得右孩子， i 结点得权值为 x 结点得权值加上结点得权值 ,i 结点 得双亲设置为空4、根据哈夫曼树创建编码表 源代码 :voi Hu fmanTree:Cr at H ree（ ode *p, nt n）root new Bi od<in >2*n-1; /初始化哈夫曼树?N de *fro t=p- > next;if（n =0）? hrow excpin（" 没有输入字符 "）; r（int i= ;i<n;i+）/将 n 个字符得权值存储在哈夫曼树数组得前 n

10、 位? ro t i 、da a=front->co nt;root i 、 child=-1 ；? ooti 、 rchi =-；?ro i 、 paren ;? ron=fr nt->ne ;?f ont p;int N 1, ew2; r(i= ； i< *n-1;i+)Se e t n(N w1,N w2， 0,i);/从 i 中选出两个权值最小得结点ro N 、 p ren =root ew、 pare t=i； /用两个权值最小 得结点生成新结点, 新节点为其双亲roo i 、 ata= ot w 、da +r oNew2 、 ata;/新结点得权值 为其孩子得权

11、值得与? oo i 、 child= ew1;ro 、 rchi Nw2 ；?rooti 、 pare t=- ;?CreateCode ble(p);/创建编码表时间复杂度 :在选取两个权值最小得结点得函数中要遍历链表,时间复杂度为 O(n) ，故该函数得时间复杂度为 O(n2 ) .创建编码表 (oid H ma Tre :Cre teCo eTab (Node *p) 算法伪代码：1、初始化编码表、初始化一个指针 ,从链表得头结点开始 ,遍历整个链表2、 将链表中指针当前所指得结点包含得字符写入编码表中2、 2 得到该结点对应得哈夫曼树得叶子结点及其双亲、 3 如果哈夫曼树只有一个叶子结

12、点 ,将其字符对应编码设置为 02、 如果不止一个叶子结点 ,从当前叶子结点开始判断、 4、1 如果当前叶子结点就是其双亲得左孩子,则其对应得编码为 ,否则为 12、4、 ch ld 指针指向叶子结点得双亲， p rent 指针指向 c ild 指 针得双亲 ,重复 2、4、1 得操作、 5 将已完成得编码倒序、 6 取得链表中得下一个字符.输出编码表源代码 :void ufaree：:CeateCeabl(Node *p)/初始化编码表HCodeTabl =new HCode t i ;ode *r t=p->n xt; or（ nt i 0;i<tSiz ; +）? HCod

13、Ta ei 、 a=front->character; /将第 i 个字符写入编码表? hld=i ；得到第 i 个字符对应得叶子节点?it pare t=root、parent;/得到第个字符对应得叶子节点得双亲i t k=0;?if （tSize=1）/如果文本中只有一种字符 ,它得编码为0? CodeT bei、codk ='0'；? k+; ?while（ aren!= 1）/从第 i 个字符对应得叶子节点开始 ,寻找它到根结点得路径?if(ch ? ld=rotp e 、 il） /如果当前结点为双亲得左孩子，则编码为 0, 否则编码为 1 HCodeablei

14、、code k='0;elseHCodeTablei 、 c d = 1'k+;c ild= ar nt;parent= ootchi 、 a en；HCo Table i 、coek= 0'Revers （H o T bl i 、 cod）;/将编码逆置front front->n x ;/得到下一个字符? ? ut<< " 编码表为 :"<<endl; r（i=0;i < tSiz ;i+）/输出编码表? c ut<<HCodeTa lei 、 dta<< '<<H

15、odeTabl 、 cod << dl； 时间复杂度： 需要遍历哈夫曼树获取编码 ,时间复杂度为 O（ 2） 4 选择两个最小权值得函数算法伪代码 :1. 从下标为 b gin 得结点开始 ,寻找第一个没用过得结点2. 遍历哈夫曼树中从下标为 bein 到下标为 nd 得结点序列 ,寻找没用过得 同时权值又就是最小得结点。3.4.5.源代码 :暂时改变找到得权值最小结点得双亲域,防止第 2 次找到相同得结点。将权值最小结点得下标记录下来。重复步骤 4,找到第个权值最小得结点void Huffm nTre：SlectMn（ n ew1,in &N 2,int begi， en

16、d）i min;/要选择两个权值最小得结点/从下标为 begin 得结点开始 ,寻找第 1 个没用过?f r（ nt j=0 ； j< ;j+ ）? s gn beg n;? or（int i= gin;i< nd； i+） 得结点?if(root 、 parent =-1)/没用过得结点其双亲应为空?min=rooti 、 da a;?sig i;?brea；? ? （i= gi； i< n ;i+ ）/从 begi到 e d,寻找权值最小得没用过得结点?if（r oti 、 t= 1）?if?( >rooti 、 ta)?min=root i、 d ta;?sig

17、=i ；? ? ?rotsig、prnt=0;/暂时改变所找最小结点得双亲域 ,防止第 2 次找到得就是同一 个结点? i （!j）?New1= ign;? e s? ?New2=si n;?时间复杂度 : 两次遍历链表，时间复杂度为 O（n）5、将字符串倒序得函数 （vod u fm nTre :R ers（har *pch）算法伪代码 :1 得到字符串得长度2 初始化两个记录下标得变量 ,一个为字符串开头字符所在得下标,另一个为字符串结尾字符所在得下标3 将下标为 i 与得字符交换4 + ， j - -时间复杂度 :时间复杂度为 O（ ）6、编码函数 （void Huffman ee:En

18、 de（ strin ,string &d）算法伪代码 :1、从 s开头得字符开始 ,逐一对 s 中得字符进行编码2、在编码表中查找与当前字符对应得字符3. 如果找到了与当前字符对应得编码表中得字符，将其编码追加到解码串得末 尾。4、重复以上步骤，直到所有待编码串中得字符都编码完毕5、输出编码后得字符串源代码 :void Huffm nTre： :Enc e（str ng & ,strin &d）fo （int j= ;j<s 、leng （）； j ）/逐个对待编码字符串中得字符进行编码for（in i=0;i<tS e;i+ ） /在编码表中查找与当前字

19、符对应得编码?f（s = CdTabe、d t）?d、 ppend（ CodTable、 coe）; /编码?b ea；? u < << <en l;/输出编码后得字符串时间复杂度 :设待编码字符串长度为,编码表中字符个数为 m，则复杂度为 O（ *m）7、解码函数算法伪代码 :1. 得到指向哈夫曼树得根结点得指针与指向待解码串中得第 1 个字符得指针2. 逐个读取待解码串中得字符 ,若为 ,则指向哈夫曼树当前结点得指针指向当前结点得左孩子 ,若为 1,则指向当前结点得右孩子3. 指向待解码串得指针指向解码串中得下一个字符,直到指向哈夫曼树结点得指针得孩子结点为空4.

20、如果哈夫曼树只有一个叶子结点 ,直接将待解码串中得编码转换为对应得字?8、符5. 如果指向哈夫曼树结点得指针得孩子结点已经为空，则将叶子结点下标对 应得字符追加到解码串中。6. 输出解码串 源代码 : for(int i=0;i< vo Huffma Tree:Decode(str ng &s,s ing &d)lngt();)i t parent=2*tSiz - -;wh e( root p re、 lchild!=-1 ) 结点/得到哈夫曼树得根结点/如果结点不为叶子? if(si='0 )/ 编码为 0 则寻找其左孩子are t=r o paren 、 c

21、hil ；? e se/编码为 1 则寻找右孩子?paren =r ot ar nt 、 rchil ；i+;if( tSi e= )结点i+;pped(1,HCdeTabeparen、 ata);/将叶子节点对应得字符追加到解码串中 t<<d< <endl ； 时间复杂度 : 设待解码串长度为 n,则复杂度为 (n) 计算哈夫曼编码得压缩比 (voi u fman ree: alculate (srig s1,stri g s2) 算法伪代码 :获得编码前字符串得长度 ,即其占用得字节数 获得编码后得字符串得长度 ,将其除以 8 然后向上取整 ,得到其占用得字节数 压

22、缩比将两个相除/ 如果编码表只有一个字符 ,则根结点即为叶子d、1.2.3. 源代码 : d Huf ree:Cal la e(str ng 1,s ring s ) int c 1=、 l ngth() ； in cal2 2、 gth() ；? 2=ceill (floa ) ca ); /将编码串得比特数转化为字节 数? cou< <" 编码前得字符串长度 :" < <cal1<<endl;cut<<" 编码后得字符串长度： "<< l2<<enl; c ut<<&

23、quot;压缩比为 :"<<(d u le)cal2/( oub e)cal1)*1 0<<"%"<<end ;时间复杂度O（1）、 打印哈夫曼树 （ oid Hu m n ree:： Pri t ree（ Tre de,int la r） ）算法伪代码 :1. 如果待打印结点为空 ,则返回2. 递归调用函数打印当前结点得右子树3. 根据当前结点所在得层次确定其前面要输出多少空格,先输出空格 ,在打印当前结点得权值4. 递归调用函数打印当前结点得左子树源代码 :id Huf nT ee:Pri tTree（ int Tree o

24、d ,int layer）i（Tr ode 1）/如果待打印结点为空 ,则返回?return; ls P n Tree（root re N de 、 rc il ， layer 1）; /先打印该结点得右 子树, ye记录得就是该结点所在得层次 o （i i= ；il e * ; +） /根据该结点所在得层次， 确定在它之 前需要打印多少空格 cout ' 'cout r t eNd、dt nl；/打印该结点得权值Pri t ree（rootTreeN de、lhil,lyer+1）； / 打印该结点得左子树 ?时间复杂度 :中序遍历哈夫曼树 ,复杂度为 O（n）10、 菜单函数 （oid HuffmanTr e:Me u（） 算法伪代码 :1、 逐一读取键盘缓存区中得字符 ,并将它们逐一追加到记录输入字符串得 strig 变量中，直到读到回车输入符为止2、 删除 string 变量末尾得回车输入符3. 利用 s ing 变量创建哈夫曼树 ,初始化编码表。4、直观打印哈夫曼树、 对输入得字符串进行编码6、对编码后得字符串进行解码7、计算编码前后得压缩比并输出源代码 :void uffman r： Menu（ ）cou 请输入您要编码得文本 ,按回车键确定输入 "end ;string nput；char let er;? d/将字符逐