哈夫曼树实验报告

1、计算机科学与技术学院数据结构实验报告班级 2 0 14级计算机 1班 学号 2 0 1 44 1 38021姓名 张建华 成绩实验项目简单哈夫曼赢"7译码得设计与实现实验日期2 016、1、5一、实验目得本实验得目得就是进一步理解哈夫曼树得逻辑结构与存储结构，进一步提高使用理论知识指导解决实际 问题得能力。二、实验问题描述利用哈夫曼编码进行通信可以大大提高彳t道利用率，缩短信息传输时间，降低传输成本。但就是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来得数据进行译码 ，此实验即设计这样得一个简单编/码系统。系统应该具有如下得几个功能：1、接收原始数据。从终端读入字

2、符集大小n,以及n个字符与n个权值，建立哈夫曼树，并将它存于文件 hfmt ree、d a t 中。2、编码。?利用已建好得哈夫曼树（如不在内存，则从文件hfmtree、da t中读入），对文件中得正文进行编码，然后将结果存入文件 code中。3、译码。利用已建好得哈夫曼树将文件code中得代码进行译码，结果存入文件t e x t中。4、打印编码规则。即字符与编码得一一对应关系。5、打印哈夫曼树，将已在内存中得哈夫曼树以直观得方式显示在终端上。三、实验步骤1、实验问题分析1、构造哈夫曼树时使用静态链表作为哈夫曼树得存储。在构造哈夫曼树时，设计一个结构体数组H uffNode保存哈夫曼树中各结点

3、得信息 ，根 据二叉树得性质可知，具有n个叶子结点得哈夫曼树共有 2n-1个结点，所以数组HuffN。d e得大小设置为2 n 1,描述结点得数据类型为：Typedef strc u t? Int weight ; /* 结点权值*/I n t parent;I n t lchild;I nt r chil d ;HNod e T y pe;2、求哈夫曼编码时使用一维结构数组Hu f fCode作为哈夫曼编码信息得存储。求哈夫曼编码，实质上就就是在已建立得哈夫曼树中，从叶子结点开始，沿结点得双亲链域回退到根结点，没回退一步，就走过了哈夫曼树得一个分支，从而得到一位哈夫曼码值，由于一个字符得哈夫

4、曼 编码就是从根结点到相应叶子结点所经过得路径上各分支所组成得0、1序列，因此先得到得分支代码为所求编码得低位码，后得到得分支代码位所求编码得高位码，所以设计如下数据类型：#defi n e MAX BIT 10T y pedef struct Int bitMAXB I T;? Int s tart; H Cod e Type;3、文件 h f m tree、dat、code 与 text 。2、功能(函数)设计( 1)、初始化功能模块。此功能模块得功能为从键盘接收字符集大小 n ，以及 n 个字符与 n 个权值。(2) 、建立哈夫曼树得功能模块。此模块功能为使用 1 中得到得数据按照教材中

5、得构造哈夫曼树得算法构造哈夫曼树,即将Huff Node数组中得各个位置得各个域都添上相关得值，并将这个结构体数组存于文件hfmtree、dat中。(3) 、建立哈夫曼编码得功能模块。此模块功能为从文件hfmtree 、 dat 中读入相关得字符信息进行哈夫曼编码,然后将结果存入code中,同时将字符与0、1代码串得一一对应关系打印到屏幕上。(4) 、译码得功能模块。此模块功能为接收需要译码得 0、 1 代码串,按照3 中建立得编码规则将其翻译成字符集中字符所组成得字符串形式，存入文件t e x t ,同时将翻译得结果在屏幕上打印输出。(5 )、打印哈夫曼树得功能模块。,以图形得方式将各个结点

6、以及叶子此模块功能为从HuffNo d e数组中读入相关得结点信息结点得权值与左分支上得0 与右分支上得 1 画出来。)及分析1、实验主要代码t y pedef s true tstring hfm str;? int we i ght;int parent ；i nt 1 c h ild;int r child; HN o d eT y p e;typ e def st r uct*结点结构体*/ 结点内容* / 结点权值*/* 编码结构体*/in t b i tM AXBI T ; in t sta r t ;HCodeT y p e; *创建哈夫曼树*/v oid C re a t e

7、_Hu f fMTree(HNodeTyp e HFMTre e 口,int n) ? in tml, x1,m2,x2 ;? i n t i,j;? f o r( i =0; i <2 *n- 1 ;i+ )? HFM Treei 、h f ms tr=""HFMT r e e i 、we ight=0 ;? H FMTr eei 、par e nt = - 1;HF M Tr e e ： i、lchild=-1;HFM T re e i 、r c h i ld=-1 ;? f or (i=0 ; i<n;i+ +)?<<e n d l;cout&

8、lt;<"请输入第"<< i + 1<v"个权值"? c in> > HFMTre ei 、weig h t;? co ut<<”请输入对应字符"<<e ndl;? cin> > HFM T r ee i、h f mst r;?f or ( i = 0 ; i<n 1;i+ )? x1=x2=MAX VALUE;? ml =m2= 0;for(j = 0;j<n+ i ;j + +)? ? i f(H F MTreej 、parent=-1&&H

9、FMT r ee j 、w eigh t <x1) ?x 2 = x 1;? ? ? m2=m1;? x 1 = HF M T re e j > weig h t;m 1=j;? ? ? else i f (H FMTr eej 、p arent =-1&&HFMTr e e j 、wei g h t<x2) ?x2=HFMTree j 、weight ;? m2=j ；? HFMTr eem1、p arent= n + i ;HFMTre e m2、pa r e n t =n+i ;? ? HF MTree n + i 、we ig h t = H FMTr

10、 e em1、weight+H F MTreem2、weight ;? HF MT re e n+i 、1 ch i 1 d= ml ;? H F MTre en+i 、r c hild=m 2 ;? c o u t v”创建哈夫曼树成功！ u v <en d l;void Haffma n Code (HNodeType HFMTree口,H C odeT y p e Huff Code口 ,int n) /* 构建 哈夫曼编码*/? HCo deType c d;i n t i,j, c ,p;for(i = 0;i<n ; i+) cd 、 start=n 1； c= i ;

11、p=HFMTreec 、parent ;w h i 1 e ( p!=- 1 )i f (HFMTr ee p、lchild = = c) cd 、 bitcd 、 start=0 ；el bitcd 、 start=1;c d > s tar t -;c =p；p =HFM Tree c 、par ent;fo r (j=cd、sta r t+1;j < n;j+)HuffCod e i 、b i tj = c d、bitj;Huff Code i 、start = cd、star t ;v o id d e cod e i n g ( c har s t ring,H Nod

12、eType HFMTr e e , i n t n) /* 解码 * /int i , t mp=0 ,code102 4 ;int m =2*n-1;c h ar *n u mp;cha r n um1 0 24;for ( i = 0 ; i<s t rl e n (strin g) ; i + +)i f(stringi = ='0')numi =0;elsen u m i =1;i =0;nump=&nun 0;w h ile(nump<( & num st r 1 e n ( s tring) )? tmp = m-1;wh i le( (HFMTree tmp、lc h i 1 d! =- 1)&&( H FMT ree t mp、rchild! =- 1)?if(*n u mp= =0)?tmp=HFMTree tmp 卜 1 c h i ld ;?e lsetmp=HFMT r eet m p、rch i ld;n ump+ +;cout v<HFMTreet m p、h fms t r;cou t << e n d 1 ;请湎