哈夫曼编码译码课程设计报告

1、哈夫曼编码译码课程设计报告作者: 日期:«数据结构课程设计赫夫曼编码/译码器设计指导教师：李文书、周维达班级：10电信实验班 学号：Q10600132 姓名：王彬彬一、实验目的1、提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法。2、熟悉掌握一门计算机语言，可以进行数据算法设计。二、实验原理哈夫曼编 译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生 成哈夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符 0、1组成的二进 制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表 0,右分 支代表1,则从根节点到每个叶子节点所经过的

2、路径分支组成的 0和1的序列便 为该节点对应字符的编码，称之为哈夫曼编码。哈夫曼树课用于构造使电文的编码总长最短的编码方案。主要流程最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字 符具有较短的编码，让出现频率低的字符具有较长的编码， 这样可能缩短传送电 文的总长度。 图如下：否编码为1将data*和权值结束三、实验步骤1:写好流程图，设计实验方案。2：初始化，从终端读入字符集大小 n,以及n个字符和n个权值，建立哈夫曼 树，并将它存于文件 HuofumanTree中。3:编码。利用已建好的哈夫曼树，对文件 ToBeTran中的正文进行编码，然后将 结果存入文件CodeFi

3、le中。4：译码。利用已建好的哈夫曼树将文件 CodeFile中的代码进行译码，结果存入 文件Textfile中。5:印代码文件(Print).将文件CodeFile以紧凑格式显示在终端上，每行 50个 代码。同时将此字符形式的编码文件写入文件Code Print中。6:印哈夫曼树(Tree printing).将已在内存中的哈夫曼树以直观的方式(比如树)In itializatio n()初始化En codi ng()编码Decod in g()译码Prin t_file()打印代码文件search(k,j, p)搜索二叉树Prin t_tree()打印二叉树menu()主菜单mai n()

4、主函数Tree Print 中。显示在终端上，同时将此字符形式的哈夫曼树写入文件 具体函数如下：12345679四、实验结果与分析(1)大致个人测试案例: 主界面：iRRz麵5； iofelA?Sl 学咼；Qiat00132 its：王栩彬*fln夫8编不骄1译码*-_帀_ 一一编 文曼串 崗夫符码1代宝了译 始曽印印入入pleAS« Input yau> eno tee hei*e j初始化:Cs曰 L1 nos-Llopc. + -H:i_20匕bjgYHtlrnar_2 匕xwUlOASO Input： VDUl' cho ±CD 1100=±

5、:a 5S-w 2Ta «u 4.fciw* 1 U hLGiiWr=Iclillil一一咕去長细的一rrli I 111Huofuman.txt初始化存入文件结果如下:1 H U of u mon Tree, txt - i 己李半立tft或<c) SSM toatxH)h笹入的值_ -'T苻大小 apa rentI oh i 1 d1r oh I I eI=1-1=1-1七h52479616/e- 11- 2w编码结果如下:code编码存入文件如下:j|匚oduElHt>t 记事本文中F)輛旧1(6 I覺W)帮輒H)I000100111011译码结果如下:te

6、xt译码存入文件如下:j Terfle .txt交件旧 備 柜式Q）童看m 誓助（Hqwcrt打印结果如下:(ue Pt please input your choice here: p000190111011please input yauF choice here:.打印树结果如下：I UU 5 ers| enov oDe?lrtopc+ *H jffna n_2De5u q Hjiff ina r_2.exeBOei 09111811 please inputyourchoice27here =please inputyourchoicehere :treeprint.txt存入文件结果

7、如下:(2)本例测试案例_1已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计哈夫曼编码。 解：假设八种字符为 ABCDEFGH,将各个概率乘以100可得权值为5 29 7 8 14 23 3 11 启动程序，测试得：初始化：_ -一曹 一 一文昌 一 一码夫 毗匚代哈 丈在码印印DPT值；谊道道蓿喧 0苴苴苴苴S甘苴苴心 -nDnnnunDn 符 1f'J3g56a'se JmM :人人A入入入 -mHstllp-ltlEMtllHmnF-IHIF-Hllr-ltlHNtlHr- 丨 1

8、11 II I L 11111留 LTe fl匚丄回冶亜亍 CiUjCr5|fikt0+ *HjQubag'F)uffnn i_t-cxerT C;U5 ers J enovo'- De 5kto pf+rH 卅陀 n _2De t>j C'XHMffm 旳=2启昨p HFonttt13? e夫豊编码-IcbildFcliald12inIS1112-1-11T-11-1291 -1 -1-1-1U 14 233 JieIS1941015112942E8160input character：A cbFipaDtRr：B c liar ac ter : Cpleaao

9、yo Ulcho icB Lore: Estart=b start：# start = Gcharacter：U r Tin vacT t : Fstart：b T taT'i: Z 7cJiainctcv : F chapactev：G r Tin va CT t ei* : His tart:9start：b T tflT't = 7Len5rtJi：4 lRnBfth：2 Lcn5rti= 4 Length：4 Hnyth： S Lungth：2 Length： 4 1 pngth： 3右Dde：测Hl Cnrtfl ：1ft GodczllieCotte ：1111Go

10、de:ei Code：删酗Code:Rfli译码打印结束:fr厂：厂:U5兰5<|en5Irtcr + +-Hlj母nn#n 2VOfbuad|-(ij科忙凸n 2 已已二rg.回pla AEDInput DUA*choxcohoiTD *DIQaet 10111011111flHCDhFCHinvut j/ourchoicebei*e:P0901101110111111901001001091丄i*puL yuui*chulce laelitre :Tn1 I42&e1HL1?a普2?9111-4153E78inpnt pniipchnicftU*程序终止F1 H H-W请按任

11、意维堆绩-«（3）本例测试案例_2用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码: “THIS PROGRAME IS MY FA VORITE ”。字符ABCDEFGHIJKLM频度153220字符NOPQRSTUVWXYZ频度57638181161解：先假设空格为#，所以输入字符时，将空格变为#。 输入如下：先将从空格到Z输入权值I 1=1 I 回CiUser'J?ncV0；D*5Ictopc + + HLIffman_2Debug'Huffrraexe及；1P电信实脸ri土 学号：Q丄醐132 姓若:王彬杞注*"&quo

12、t;幵二 書窜二 S3 - 化卜代睪芟 始码码印印.二 謬朋w?¥ = 小呀咎亦= r 0 3 s 68 2 8 1111T u u u K V £ 畫士-aSSSSSSs旗诅施诅價腔旗但旗嚣垣噩婆 -nuqzHlIZHlIzzcna £ 孟八土八芝小艺小二小土小丄A 4K. JR JK 丄-宀丄_<丄一宀丄_<二宀上 <,亠 123-4 567891v- 2 加 2 -f!-_，牛 lITll,-ITBrunpknr-h1r-n-r-kB.PIT-p 事 tut丑 p 可 p可 p p ki p ? p Rn p FnP tnP In P tn

13、 F In 方-In P*m Pin r* 一了蔓互 釜迂 Lh F F k 艺迂 IKHIKH 劭 y 入入入久仝入个仝垃£入人人久£仝人入入人入 土冃主冃土网主星冃主HE土冃青士冃青左冃主冃古冃主星冃車冃窒冃-#1冃±冃-|垦冃主用主同主冃土用主同土冃 -1- - '-J- - / - J - _ J - ' J - * r Tm-.- .- J - J n J - - J - d 2 - -i - - 1 - I - I - I - - Inoe1tt3 7 2 0 7 3b s 4322Q157G 1S32S61 1 4 61231214I

14、JKLhNOQRabcdefgn - 然后对子符进行编码: C:UserslenovoDeslctopc* THu'ffman_2DebugHuffnan.2.exe49_1_118844-1-16432-1-113362238_1_132IchildFchildpapent联二貝第彳=ue iglit9pl&a.se in put your c ho ice liere:Ecbapactei*：ttstart：17length：?Code nilcharacter ； flstart：1&length：4Cade：iai8character：Bstart：14lent

15、h：Code=199606chai-acter ： Cstart = 1Slength=5Code:00009cbapacter：Dstart：15lengtb：5Code：19110chaj*actei*：Estapt：17Iensrtb：3Code：010chaiacter： Fstart = 14length：&Code=110611chftt'acter：Gstart=14lBnsrth = 6Code；100001cbapacterHstart = 1&len|rth = 4Code = 0991chajractcr ： IstA於t：1&leng(:

16、h：4Cade = 0118character：Jstart：10lengthzlO Coile ： 1180061000chfli'acter ： Kstart = 12len|rth = SCadeliaeoeilcharacter；Lstart=15lengthiSCodc=10111chai'ftctei'： Mstart:14lensfth：&Code=118016charac七er " Hstart Sl&length-4Cade：0111chai"actei*：Ostart：1&length：4Code:IQQl

17、character；?start ：l-flengthbGodc；l(1O016character：Qsteirt = 10lengthsia Co<le： 1160661001chaQatteZRStAi-tr-lGlensfth = 4Code = 0dl Schaiac ter = Sstart：1&length：4Code = 0011chai*acter = TStart：1&lensrth：4Code：llQlcharacteredstart：15length：5Gode=00061character：Usteirc：13length：?Cadc：119eBe

18、ecJiai'ac ter； Wstart = 14lengftli：&Caae=iiaeaichaiac ter-Kst ai'f: ：10lensth：! Code=1100661019character：VStart：14length：&Code：10OeilcharftcteriZ3tart：10leng(:h：lB Coiie: 1160601011空格到Z译码然后输入字符串并编码：pieajttin pur your croicer evfi ; cplease input your character stringTHIS 卩SOflRfin IS

19、 MV PrtUORTTE iiei0eeieiie00iiiiiieeoi.009i0i0eiiee0eioeiei0ieiieeieiiioiieeQiiiiiiie0iei 000111 kiiieeiiioioiieseeeieei901001101101010保存到Code中r C&MilCrbt寿斫)科(E帕0 ggM a旳出Il tu 1,1000101 iuooiiiiiHOuoioouioi»iioouoiooioiotunooici 110110001 iniiiooiioiuuaii 1111 iu 011101011000001001001001101

20、101910然后将开始译码并结束二-T J 匸=g3_P 匸da :*-屮聲w »r I*尹謬 w *?七 *程序终止T *将译码结果保存到Text中THIS PROGRAM IS iY FAVCRITEl五、实验总结从这个课程设计中，我发现了很多问题，包括文件存储，字符串输入等等，最 主要的是经历了一次找BUG的过程，当把自己写的代码里的错误一个一个找出 来时，是非常非常兴奋的。还是希望能有多这个经历。不喜欢copy，如果copy了，就缺少了一次挑战自己的经历。六、主要代码/ Huffma n_2.c pp : Defines the en try point for the co

21、n sole app licatio n./ #i nclude "stdafx.h"#i nclude <stdio.h>#i nclude <stdlib.h> #in clude <stri ng.h> #in clude <math.h> #defi ne maxsize 1000 #defi ne len 20 #defi ne rowsize 20/初始化structint parent;int lchild,rchild; int weight;HFM_treemaxsize;structint weight;

22、char hfstr;HF M_num maxsize;structint start; int bitle n; HFM_hf;structint start; char hfch;int bitle n; int len gth;HFM_codemaxsize;int leaves;void In itializati on()int i,j;FILE* HFM_f;HFM_f = fopen ("Huofuma nTree.txt","w"); if(HFM_f = NULL)prin tf("create !n");print

23、f("请输入字符集大小：")；sca nf("%d",&leaves);fprintf(HFM_f,"-输入的值-n");fprintf(HFM_f,"字符大小 %4dn",leaves);fprintf(HFM_f,"字符权值n");for(i=0;i<leaves;i+)printf("请输入第%d个字符和其权值:",i+1);scanf(" %c "，&HF M_numi.hfstr);scan f("%d"

24、,&HF M_numi.weight);fprin tf(HFM_f,"%4c",HFM_numi.hfstr);fprin tf(HFM_f,"%4dn",HFM_numi.weight);/存储字符和权值/-建立哈夫曼树-/ for(i=0;i<maxsize;i+)/ 哈夫曼树初始化HFM_treei. pare nt = -1;HFM_treei.lchild = -1;HFM_treei.rchild = -1;HFM_treei.weight = 0; " for(i=O;ivleaves;i+)HFM_treei.w

25、eight = HFM_numi.weight;" " for(i=0;i<leaves-1;i+)int m1,m2;int m1_p os,m2_ pos;m1=m2=65536;m1_p os=m2_ pos=0;for(j=0;j<leaves+i;j+)if(HFM_treej.weight<m1 &&HF M_treej. paren t = -1) m2 = m1;m1 = HFM_treej.weight;m2_pos = m1_pos;m1_pos = j;"elseif(HFM_tree|j.weightvm2

26、&&HF M_treej. pare nt = -1) " "m2 = HFM_treej.weight;m2_pos = j;HFM_treeleaves+i. parent = -1;HFM_treeleaves+i.lchild = m1_p os;HFM_treeleaves+i.rchild = m2_pos;HFM_treem1_ pos. parent = leaves+i;HFM_treem2_ pos. parent = leaves+i;HFM_treeleaves+i.weight = m2+m1; "/输出哈夫曼树/prin

27、 tf("哈夫曼编码n");prin tf("pare nt lchild rchild weight'n");fprintf(HFM_f,"哈夫曼编码n");fprin tf(HFM_f,"pare nt lchild rchild weight'n");for(i=0;i<leaves*2-1;i+)prin 戈- &8d&8d&8d&82rfHFMee 三.parenLHFMIU-ee 三chi_aHFMee 三.rchi-d-HFMIfree 日.wei

28、gho 八fprHKHFM憑8d&8d&8d&82rfHFMee 三.parenLHFMIfree 三chi_aHF Mee 三.rchi-d-HFMIfree 日.weigho 八 ) Iprin戈vrxfc_ose(HFMIm>=void Encoding。宀inf LjpcKF一LE* HFMf Hfopen(=code=w) if(HFMIf HH NULL) 宀prinm.open 一云) fo(iHO=A-ea<es=+) 宀CH rp H HFMfree日parentHFMhf.sfart H _en4 whi-e(p 一卩 1) 宀if(HF

29、MIU-ee巨ch=d Hu c)宀HFMhf.b三HFMhf.s応m H 9 e-se宀HFMhf.b三HFMhf.s応m HHFMIhf.sfart 八CH p-p H HFMfreercLparenrf02HHFMIhf.sfart+kH£A_enj+K+) 宀 HFMIC0dem.bif2 H HFMhf.bifwHFM_codei.le ngth = len-H FM_hf.start-1;HFM_codei.start = HFM_hf.start+1;for(i=0;i<leaves;i+)HFM_codei.hfch = HFM_numi.hfstr;print

30、f("character:%。start:%dlength:%dCode:",HFM_codei.hfch,HFM_codei.start,HFM_codei.le ngth);for(j=0;j<HFM_codei.le ngth;j+)prin tf("%d",HFM_codei.bitj);fprin tf(HFM_f,"%d",HFM_codei.bitj);prin tf("n");prin tf("n");fclose(HFM_f); void Decod in g()/译码/

31、char amaxsize;char HFM_dcmaxsize;int i,j,k, p;FILE* HFM_f = fopen ("Text","w");FILE* hf = fopen( "Code","r"); if(HFM_f=NULL)prin tf("o pen !n");fsca nf(hf,"%s",a);j=0; P=0;for(i=0;i<leaves;i+)k = 2*leaves-2;while(HFM_treek.lchild!=-1 &am

32、p;& HFM_treek.rchild!=-1) if(aj='0')k = HFM_treek.lchild;if(aj='1')k = HFM_treek.rchild;j+H HFMdc巨 H HFMcodes.hfcm P+H primw- fo(no=AP=+) 宀 if(HFMIdc三 hh 送 HFMdc三 H- pl1mf(=%aHFMIdc=2 fpl1mf(HFM二求 aHFMIdc=2 fc_ose(HFMIm fc-ose(hf八=肯吕走頂洱丰.-=void prinflfi-eo宀 IF一LE* hfHfopenvcodtTX

33、F一LE* he H fopen(=codepl1n二xrw) char s 三 maxsize"inf SH fssnf(hh=%s=g2 s H sf-en(sm primw- fo(no=AS=+) 宀Pl1mf(=%asm fpl1mf(h0=%asm if(i-M)&50HH0)宀 prinmvrx fpHf(hc>n)fc-ose(hf八 fc-ose(hc)八 prin戈VI)/打印哈夫曼树/int fprowsizerowsize;int f=5;void search(i nt k,i nt j,i nt p)in t c;int d;int b;if

34、(HFM_treek.lchild!=-1)c=HFM_treek.lchild;d=j+1;b=p-2;if(fpdb) b=b+1;fpdb=HFM_treec.weight; search(c,d,b);if(HFM_treek.rchild!=-1)c=HFM_treek.rchild;d=j+1;b=p+2;if(fpdb) b=b-1;fpdb=HFM_treec.weight; search(c,d,b); void Prin t_tree() "int i,j,k,s, p,c;FILE* HFM_f;HFM_f = fopen ("Tree Prin t.

35、txt","w"); if(HFM_f = NULL)prin tf(" error!n");memset(fp,0,sizeof(fp);fpO1O = HFM_treeleaves*2-2.weight; search(leaves*2-2,0,10);p =(i nt)log(leaves*2-1)/log(2)+1; for(i=0;i< p+2;i+)for(j=0;jvrowsize;j+)if(fpij=0)printf(" "); fprin tf(HFM_f,"");elsepri

36、n tf("%3d",fpij);fprin tf(HFM_f,"%3d",fpij);prin tf("nn"); fprin tf(HFM_f,"nn"); fclose(HFM_f);/-输入字符串-/void inpu tcode()printfC'pl ease input your character stri ngn"); char hfma n_strmaxsize;int i,j,k,s;FILE* fp = fopen( "Code","w&quo

37、t;);if(fp = NULL)prin tf("o pen !n");getchar();gets(hfma n_str);k=strle n( hfma n_str);for(i=0;i<k;i+) if(hfman_stri='')for(j=0;j<HFM_code0.le ngth;j+)prin tf("%d",HFM_code0.bitj); fprin tf(fp,"%d",HFM_code0.bitj); elses=hfman_stri-'A'+1; for(j=0;jvHFM_codes.le ngth;j+) prin tf("%d",HFM_codes.bitj);