哈夫曼编码实验报告

1、实验报告与总结一、实验目得1、掌握哈夫曼编码原理 ;2、熟练掌握哈夫曼树得生成方法；3 、理解数据编码压缩与译码输出编码得实现.二、实验要求实现哈夫曼编码与译码得生成算法。三、实验内容先统计要压缩编码得文件中得字符字母出现得次数,按字符字母与空格出现得概率对其进行哈夫曼编码，然后读入要编码得文件 , 编码后存入另一个文件 ; 接着再调出编码后得文 件，并对其进行译码输出 ,最后存入另一个文件中。五、实验原理1、哈夫曼树得定义：假设有 n 个权值 ,试构造一颗有 n 个叶子节点得二叉树 ,每个叶子带权 值为 wi, 其中树带权路径最小得二叉树成为哈夫曼树或者最优二叉树；2、哈夫曼树得构造 :w为

2、输入得频率数组，把其中得值赋给依次建立得H Nod 对象中得 dta 属性,即每一个 HT Node 对应一个输入得频率。 然后根据 dta 属性按从小到大顺序排 序,每次从 ata 取出两个最小与此次小得 HT Node, 将她们得 da相加，构造出新得 TN e 作为她们得父节点 ,指针 pare t,l f d,r g tchil 赋相应值。 在把这个新 得节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。通过已经构造出得哈夫曼树 ,自底向上 ,由频率节点开始向上寻找 p ent, 直到 p en 为树得顶点为止。这样 ,根据每次向上搜索后，原节点为父节点得左孩子还就是右孩子,来记录或

3、 0，这样 ,每个频率都会有一个编码与之唯一对应,并且任何编码没有前部分就是同其她完整编码一样得。六、实验流程 初始化，统计文本文件中各字符得个数作为权值 , 生成哈夫曼树 ; 根据符号概率得大小按由大到小顺序对符号进行排序； 把概率最小得两个符号组成一个节点 ; 重复步骤 (2) ( 3 )，直到概率与为； 从根节点开始到相应于每个符号得 “树叶 ”概,率大得标 “ 0，”概率小得标 “ 1;” 从根节点开始，对符号进行编码 ; 译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。七、实验程序#incl de i stre m# nclude fst eam> in

4、c ude<iomanip > #i lu e < vecto >usin na espace s d;typ e str ct/节点结构char d t ;/记录字符值?long in weigh ;/记录字符权重unsi ned in pare t，lchld，rhil;HTNo e,* uf a re;/动态分配数组存储哈夫曼树typ def har * *Hu fmanCode ； / 动态分配数组存储哈夫曼编码表void Seet（Huffm nTree &HT,int i,it &s1,i &2） / 在 HT1、 t 中选择 par

5、ent 不为 0 且权值最小得两个结点 ,其序号分别为 1 与 s2? 1=0;s2 ;?int n=30 00,n2=30 00;f（ int k=1 ；k<= ； k +）?if（HT 、 par =0 ）? f（ H k 、 eig <n1）? n2=n1; 1=HT 、 weig t;? 2=s1; s1= ；?el?i（H、wihtn2 ）?n2HT 、 we ght ；? 2k;?oid H fma Codin （Huffm nTree HT,ffmaCode &HC, nt n）/ 将要编码 得字符串存入空树中ifstr a fi 1 （ ” zif、u tx

6、t ）； ifstr a fin2（ weig t、txt ”；） if（n ）ret r； int 2* 1；int i ；?H =new Tode +1 ; ch zifu ； n *wei t；zifu= c ar +1; weig t=new i t n+1;?fr（ =1;i =n； i+）/ 将待编码得字符放在 ifu 数组中?ha ch;c =fin1 、get （）;?ifui= h；?fo（ i=1;i =n; +）/ 将带编码字符对应得权值放在w ight 数组中? inwi ti; or（ i=1 ； ;i+ ）?HTi 、 dat =zifui;?H 、w igh we

7、ight i;?for （in+1;i<=m ；i+） i、 dt='?fr（ 1；i=m ； +）HT 、p en=Ti、 child=H 、rc i d=0 ；?for （ i=n+1 ；i<=m ；+i ）?it s1,s ;Sele （T,s1,2）；H s1 、pa ent i; T 、paen=i；?Ti、l il s1; HTi 、 r hild=s2;?Ti 、weight= s1 、 weig t+ Ts2 、 e ht;?HC= （ Huffm no ）malloc（n+1） zeo （ char* ）;开辟一个求编码得工作空间?char *cd;?cd

8、=（ har * ） mall c（ * ze f（c a ）; / 开辟空间存放权值cd -1=' 0'f r（i=1;i<= ； i+）?int s art= 1;?n c， f;for（ =, f=H i 、 parent;f!= ;c=f ，f=H f 、 p rent） / 从叶子到根逆向 求编码? if（Tf、lc ld= ）? ? cd start= '；0/'/ 若就是左孩子编为 '0'?el? ?cdsa '1'/ 若就是右孩子编为' 1'?HC = （ ha * ） m ll c（ n-s

9、tart） sze （ har）; / 为第个编码分 配空间str py（HCi,& art ） ;?deet d； / 释放工作空间 d prnHff nTree （ uffm ee HT ， nt ） / 显示有 n个叶子 结点得哈夫曼树得编码表 o stream fout（"h mtree 、 txt ）;/将对应字符得得哈弗曼树存入?cout < "NUM”dta"<"”< ”w i ht"<< ” ” <<"parent ”<” "<lchild&quo

10、t;< <” ”< "rchlid ” ndl; o （int i=； i<= *n 1； +）? fo< T i、 eig t etw（3） < i、paetsew（）<< H 、 c il <<s tw（3） <H i 、 h ld<<endl ；? t i <se （5 ） < T i 、 da a< w （ 3） <HT 、weght< etw（3） <Hi、p nt< <s tw（ ）<<HTi 、lchild se w（3 ）<

11、<HTi 、 child ndl;vod printHuffmanCodi g（ uffm n ree HT,Hu f nCode C,nt n）/输出字 符得对应哈弗曼编码并存入 code 、xt 文件c t< "Huf man c e is ： ”< endl;?ofstream fout （ ” co e、 tx ”；）fo（in=；i<=n;i +）?c ut< HTi 、 aa<<” -> ;?cout<<（HC ）< endl;?out <（HCi ） <<endl ；?vo co _ H

12、T,Hu fma e HC，it n）/对文件 tbern、txt 进行编码 , 并将编码存入 codefile 文件中ifs am fin("oran、txt?ofstreafot( ”od”);?ecr cha a；?chrc;?le（ch=fi 、get()！='* ')、 pu hback（c);cout<"待编码得字符串为:"；?for(int=;<a、sie（）；k+ )? u k?cout endl ；?co t n 编码结果： "<< l；?for（in i=0； i、 si e（）;i+）?for

13、（int j 1;j =n； +）?i? （a i =H j、 data）?f < H j;? break;?fi、 clos （） ;?fo t、 coe（） ;void Decodi （Hu ma Tr ,Huffman od C,i ）/打开 code ile 文件并对文件内容进行译码in os m *n1; istream fin （ code” ）;?of t a fout（"text"）;ve t r<c ar> a;?fo（ h ； f n> >c；） a、ps_bac （c）;?int c t=0;fo（ int k=0;k&l

14、t;a 、 ze（） ;+）? o ak ；? co nt+ ；? if（ ont%5 =0 ）? ot< ndl；?int =0;?int p ；/ 用 p 来记住 m 得值o t<enl； out < <”n 译码结果 : ”< endl;while（i a、s e（）?= ;从哈弗曼数得根开始遍历? i e（HT 、lild）? if（a = '1'）? HT p、rch ld; ls ? p= Tp 、 lchi ；? i+;? fo HTp 、 ata;? cout HTp 、 at ;o d main（） t n;out”输入权值个数：

15、 ”; /设置权值数值?ci n;? rintf（ n"”）;?Huff Tree T; / 哈夫曼树 HT?Huffman de HC; / 哈夫曼编码表 C?Hu anCodin （HT,H ， n）; / 进行哈夫曼编码ri tHu f anCodi g（HT ， ,n）; 显示编码得字符 ? rint "）；ode_ ）；/显示要编码得字符串 ,并把编码值显示出来?eco ing（H ,HC,n）;/译码并显示译码后得字符串?p i f（ ” n” ）;?syst m（pau e"）；八、结果分析哈夫曼编码就是动态变长编码， 临时建立概率统计表与编码树。 概率小得码比较长， 概 率小得码比较长。概率大得码短，这样把一篇文件编码后，就会压缩许多。从树得角度瞧， 哈夫曼编码方式就是尽量把短码都利用上。 首先,把一阶节点全都用上 ,如果码字不够时 ,然后 , 再从某个节点伸出若干枝 ,引出二阶节点作为码字，以此类推，显然所得码长最短,再根据建立得概率统计表合理分布与放置 , 使其平均码长最短就可以得到最佳码。