英文文件的压缩和解压缩-数据结构与算法课程设计报告

1、合肥学院计算机科学与技术系课程设计报告20092010学年第 二 学期课程 数据结构与算法课程设计名称英文文件的压缩和解压缩学生姓名包学号 学04012035专业班级 08计科(2)指导教师 王昆仑2010年6月7日题目：英文文件的压缩和解压缩1、问题分析和任务定义采用哈夫曼编码思想实现文件的压缩和解压缩功能，并提供压缩前后的占用空间之比。要求：（1）压缩原文件的规模应不小于5K。（2）提供解压缩后文件与原文件的相同性比较功能，对于一篇文章，首先要打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，注意编码表设计及其数据结构，编码完成后再对其编码进行译码

2、。压缩过程就是以读的方式才T开原来的英文文件A.txt ,把其中出现的所有字符在文中出项的频率作为权值建立哈弗曼编码。以写的方式打开一个新的文件，把它作为英文文件压缩后的文本文件，在扫描英文文本文件的所有字符，把其经过一定的转换后存C.txt中。在扫描C.txt这个文件里的字符把其转换为二进制文件，在把二进制还原为初始的字符。存入 D.txt 中。任务定义是通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、 数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 深刻理解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力。在程序设计方法以及上机

3、操作等基本技能和科学作风方面进行比较系统和严格的训练。2、数据结构的选择和概要设计此程序选择的存储结构为顺序存储结构，而使用的哈弗曼树是二叉树的一种特殊结构， 可以首先把叶子节点按顺序存放在存储结构中，可以不用任何附加信息就直接寻得其左右孩子节点和父节点，方便建立哈弗曼树。对于英文文章的压缩和解压缩只要定义生成哈弗曼树和哈弗曼编码的数据类型即可。即struct head（ unsigned char b; long count;long parent,lch,rch;char bits256;header512,tmp;header【512中的每个节点包括如下信息:unsigned char

4、b存放的是节点信息Long count每个字符的权值Long parent父节点Long lch左孩子Long rch右孩子Char bits每个字符的哈弗曼编码程序中包含的函数及其功能:Void yasuo ()压缩函数，压缩文本文件Void jieya ()解压缩文本文件Void out ()输出压缩后的编码Void main ()主函数其中b是存放英文文章中的各个字符，count存放每个字符对应的权值，也就是每个字符在一篇文章中出现的次数，parent, lch, rch是某叶子节点的父节点，和左右孩子节点，bits存放各自字符的哈弗曼编码。tmp则是在生成哈弗曼编码时需要寻找最小权和次

5、小权来作为 哈弗曼的树的头两个叶子节点，把它们的和作为根节点，加入到之前的字符编码中去，另外删除最小权和次小权，继续以这种方法生成哈弗曼编码，当到最后一个节点时结束，哈弗曼树生成完毕。而后就是对文章进行压缩。Fseek()函数把文件的指针调到ifp待读文件的开始端，与此同时，在把读取的字符经过处理写入ifp文件中，c=fgetc ()读取，如果 c=headeri.b,即buf中存放的二进制转化为字 符与字符中的字符相同，则记录于c.txt中，并把相同的部分给删除。如此往复，在继续读取由字符的哈弗曼编码所构成的顺序表中的8位，转化为整数，在强制转化为字符型变量，写入c.txt,另外注意的是，当

6、最后的由哈弗曼所构成的二进制文档的字符读取到最后的时候， 如果不够8位，的话，则在末尾补零，不然就会出现错误。while(headeri.bits0!=0) c=0; for(j=0;j8;j+) if(headeri.bitsj=1) c=(c1)|1; else c=c1; 文章压缩成功后，就需要对文档文档进行解压缩，先读取 c.txt中的字符文档，是一个 一个字符的读取，然后再把读取的一个字符先强制转化为整数，这是根据ASCII码来转化的，最后在将整数转化为二进制编码，是 8位的编码，并把这编码存入buf中，在不断读取不断存储，在此过程，用字符中的编码与以读取中的编码进行比较，即 if(

7、memcmp(headeri.bits,bx,headeri.count)=0) break;if判断语句来判断，如果相等的话，也就是 memcmp ()函数的值取零，那么就记 录这个编码所对应的字符值，即c=header i . b,并且写入D.txt中，即fwrite(&c,1,1,ofp);,不断重复这一过程，知道C.txt中的字符都读取完毕，那么存入D.txt的文档也就结束，是源文件一致的英文文件。3、详细设计和编码首先，要完成此程序，首先就要建立哈弗曼树，来建立哈弗曼编码，采用顺序表存储结构， 即 struct headunsigned char b;long count;long

8、parent,lch,rch;char bits256;header512,tmp;首先定义文件指针ifp , ifp=fopen( A。txt),定义flength=0 ;统计这篇文章的所有的字符 的长度，然后在用feof()读取全文信息，用fread ()函数一个一个读取字符，headerc.count记录的是每个字符的出现的频率，然后初始化数组，加入 headeri.count不为0,即某个字 符出现在文中，用 ascii码统计headeri.count的数值，如果不为 0,那就说明此字符在文中 又出现，那么就把它赋值给headeri.b ,用强制类型转换。然后把它的左右孩子和父节点都赋

9、为-1,即为空。然后寻找最小权和次小权，for (i=n; i一个八位二进制编码-ascii码-字符(写入到 C.txt)问题2：生成了压缩文件，可以实现文件的压缩，但不能实现解压.原因是：在解压的过程中，吧从压缩文件中读取的字符转化为整数在转化为二进制编 码时没有给编码补零。在开始写程序，一开始在就觉得自己会把各种细节都会考虑到，做了准备，但是在具 体实现时却发现真的不是那么回事，是自己没有充分考虑问题。不知道怎么解压和解压缩。 5、测试结果及其分析运行程序，进入主菜单选择页面，有四个选项， 1。压缩文档，2。解压缩文档，3、输出 压缩后的文档，4。退出。选择第一个时首先输出每个字符以及对应

10、的权值和对应的哈弗曼 编码。而后在输出压缩比，最后生成讲压缩后的文档存放在C.txt中，第二个是实现解压缩功能，将解压缩的文档存放在D.txt中，第三个选项是读取 D.txt中的文章，在屏幕中显示。最后一个选项退出程序。C-哈苑宫树立现空档的尿缩和解医绢或出iH缩文z-解压缩文 A解出解压后的支 4-湛e lect1是压缩文档，2是解压缩文档，3是输出解压缩后面的文档，最后是退出。这是一个主菜单选择界面，确定你要选择的选项，界面清晰明了,这个是第一个选项实现的结果，首先输出英文文章的出现的所有的字符，并且输出它们的权值以及哈弗曼编码。并且将压缩后的文件放入C.txt中Lr- Lr- Lr- I

11、F- Lr- Lr Lr Lt.g哈弗粤树实现文档的乐编却解底煽select ： 2田维文档解压成功?见D.txt会*/人文文政日缩后压解压解输退- -12 9 4这是运行第二个选项后出现的结果，是解压缩文件后将其存放在D.txt中，其实和源文件是一样的。输出的是解压缩后的文件。F -记步本文件如量相&格式189看W律助地Thdl jms d sunny。W，I 朝g going un 寸 gy tw Hhe XX. At the crosilngi J 5jv dn 0皿网sen uas standing dt the coner 3Myrih B.uinyi I h？ car enming

12、 jnri yoi ny it “priDd %*!1 hit ri 4 trophi*. ujlkil i.o her qnH hplp Ite That sunny 。曜y. I was going on nji way tu the MX. At the crossing 41 军3m an old Q)rwn g，5 stsndinig at the toner.h刁ue rawing thf* cars condng anner phaue sailing tn? cars 匚niainq andl qaing, it 与司匹0 写hp mad a tronublF. I ualke

13、d to Upd liel cdr coning dnil gulug, It当 he hdd 国 trouLlp. I ul krd Lu tier dnd liclp tier . Thdt ims d suimyi Jay. Iijujiiy on 号 zy to the1 xx + Ai th手img $1J old vmnii9 35 $tnding dt 皿妙 cunr|hju uiiig the cqls cend going. it5h町 hM 口 trvu&lU uilk?d to* iirr dud hwlp hur . *. Iht was a 行unny ddji I

14、u4s going vn 巾to th? XX a ftt the crossing .1 saw an old uonen was standiinqi at the corer Ihaue satfimq the cars coming and qoinq1, Sened 号 nd had A ti-aui)l&,l walked t& hpr aind hrlp hrr . . that ua H 号 unrig day. I * 号 gding on 叫 uay tfi the XU in. crosliiy t( s4u1 dn ulii w dt tiw con2r.naw世thf

15、 Iroulilit. 1 uilkfMl tu her lid Jan oldl wiiwn stndin4wdlked to her and help her . Ian。 help her 国 Ihat was a suniftii d3yl. 1 uas golngi du ng way to the 丹黑 Rt tne Etdnilhig dt tliu duii&r phdu siwLnyi thi* t口广$ coiil pie| jhiI qulmg. it s(sFMjd 和电 lidd li t. Tht 岬q hS Eunnu 的心 1 帕工 gnlnqi rm ny 叫

16、叫 to thr XX. At a岫忖灯弓winq the Gonerahave sawing the cdrs cuning and 口ing. it seened whe Ihdd a trouble.1Has a sunnp daj 1 Has goingi on 叫 iMijj to the XX. At the crossing I san an old wonen uas standing at the coner rawing th* cjri coning And goinigf ithn w trnublp.l 邺al低点。to hr 肯nn np】p h(*r ThaT u

17、写 示 uningI ; quinq on MAfaahl a II ms! b-aril 十皿 h anirl 小孙1 c henThaiE, *iae* 1 *“iniiTU* ，1 me* n 界*ns nn dwt 学 t n 1111fB Mil原英文文件文章截屏如上图所示，也就是需要进行压缩和解压缩的源文件。 C_+=t -记用本寸伴幻 客斜M 格式叮|当若底1箱的 甲渤理?胡限貌啾僦喃虹1钳？覃？WI嚼(1“0神q必朗朝？ 殆巴戴年嫌，Ll.璞隹G?蝴钳？邮号wt鞭1讦面沏璐In警爷型;御工正怩龊爵第勒了背注海律手的勾雄,新版“代工理谆工厂”*趟F.松魏？猾悔于月首t刊宣匕川脆嵇

18、h中噬q虚曲印”昭知劝舜感、遍橹梆样? n餐樗瘠林嘲加强呼&去株r讦酎耨斑磷咫港3赃 但痛保I?R?jl辕营”推”?悦断圈弟勤？ 1，蕾林落棒f助6 甲雷版瞬J北1纬： 省福割干苜原姨通谢跟？邛叫釉诩让rt?薄*盯的噢F机礴？ ,一 ._ 町子洒眼疽?嘀耻阵UEI攀U ?沈”耀方?茎6支? 倒襦化u增洒噬值汨蹄饵um酹u ?s 一猾果”陶1隰炉。曜 ? L ? ?”而孽旗胞川1曙.67?序尚碓听思谭虹赭？) .沈”.腰打甚G吉?觇璃七旗tZ到城?瑟？uj红贰13埔 力程鄢氨华Q脱叮南,犯港?联独飘2|旗望道，能1制耀度嶂咻学善I . 螭蹴疸物瓶.牌UIE算1 啦?喔&咤-E查?现军谏加n睡小7

19、嘴周J曲“洒招疽了8瞰牌u口躺U嘴仃巷6查了帆第锻.骚.U琼尚J碓听剧”w奸赭* 西啜瞅蹦寝事舞| |知Up琳Ml叶度丁联宜如靛飙就U 1碍旃随，f I E一可植生福科义E图糯5?啜礴吸阍嗡B硬堞峨喑G做旧程蛆.aKn_ |上，.-LlL tan. iv -|-12- .Jutil 3.t一 j：15.re*od _ LkU bn压缩后的文件，由于经过处理，就是先将所有的字符的哈弗曼编码顺序存到一个数组buf中,而后每8位提取一下，先转化为整数，然后根据 ASCII码表转化为字符，所以出现的是乱码。t r. txt -记争4文件9 狷捐旧 精父 杳吾切 萧肋orThat ua与 a sunn

20、I was 弓oing cn my uy tu the XK. ftt th? epossing ,1 sou an old vjo cnn?raje saving rrp c3r*; enming nn gninq. It epmpfi 5np nd a trnithie,I udlkpci to hP bunii Udq. I uds yuiny on *iij vuy lu Lhtf XX. At the urusbini) , I bdU dh ulU wonen a、bid rawing the coning annciauing the coming and going, it s

21、eemed sho had a (ipi cars conirt And gninq, ir spnpn wn nan a rrniioi a _1 uialkpd rn nr Ann ip Ip tier yuinq in 1119 “aq Lu Ilie KX. Al Ilie trussintj ,I dii uld uumen was stdhding dt the tune nd going, it socmcd sho hd a troubLo, walked to hur and help her * That 口写 a 雪unn to rnp XX. nt tup ernssi

22、ng ,I an nid iinmpn srAntiinQ 4t thP 伫enPF.n修up sawiny thseemed site hud d truuble.walkedtu her diid help her. Thdt was d bunnyday. I vas ythe creasing ,I sav an oLdw at the coner,have sluingthe cars coming and goingt it seeuaIk*ti tn npr and hp ip hr . FhAt was a sun。叫一 i 卬5 gulg on ny 岬/ to the XX

23、 + n vjuiiitii 5d l4iiding dl Hit? tiiiier ,hdue sawing III町 cdrb Loninq diid juint), iL 土心甘肉甘U bht bd and help her . That was j sunny。口y. wjg going onnp 雁y to the KX fttthe crDsfingtandlrig at rtif ronpr ,naupqaurinqrnp cats rnmi ng Anngring, 1 r opphipA shphad a trnublher . . Thdl uws a 5tinny day

24、. I vi5 quinq uh 仙v udytu theNX.At tlie crubiny Jdthe concr f hive 写awing the1 cars coning dnd going, itweenedclichad a trouble . I ualkcd t峭q a 写iinn(1目少，I uns going nn np uy rn rnp MX. At the Grossing t saw ah nld unnpn u bdwing U】e cdrs cuaiinq dnd yuing t i I seeid hddd trouble. I wdlkeil Lu 恒er

25、 diiJlivlpI was going on my way 七口 the XX nt the crossing ,1ejv nnaiduonvn wa写 standing3t th解压缩后的文件，与源文件一致，压缩成功。6、用户使用说明首先要在和源程序在同一个目录的文件中建立一个英文文本文件A.txt,而后运行程序，第一个是生成一个压缩后的编码，第二个是生成一个解压缩后的编码，也就是和原来的文章一样的文件。第三个输出解压后文件，最后的是退出程序。7、参考文献(1).王昆仑，李红，数据结构与算法：c语言版北京：中国铁道出版社，2007(2)何钦铭 颜晖c语言程序设计北京：高等教育出版社，20

26、088、附录源程序：#include stdio.h#include string.h#include stdlib.hstruct headunsigned char b;long count;long parent,lch,rch;char bits256;header512,tmp;/header口记录英文文章中共有多少字符void yasuo()char buf512;unsigned char c,sum=0;long i,j,m,n,f;long min1,pt1,flength;FILE *ifp,*ofp;/定义文件指针ifp用于读，ofp用于写ifp=fopen(A.txt,

27、rb);if(ifp=NULL)printf(open error!n);return;ofp=fopen(C.txt,wb);/创建新文件，存放压缩后的英文文章if(ofp=NULL)printf(open error!n);return;flength=0;/英文文章的长度while(!feof(ifp)/文章读取结束，feof返回1,否则返回0fread(&c,1,1,ifp);headerc.count+;/记录每个字符的权值，构建哈弗曼树flength+;/记录的是一篇文章的长度flength-;headerc.count-;for(i=0;i512;i+)/ 初始化数组if(hea

28、deri.count!=0) headeri.b=(unsigned char)i;/header i .b 存放字符else headeri.b=0;headeri.parent=-1;headeri.lch=headeri.rch=-1;for(i=0;i256;i+)for(j=i+1;j256;j+)/选择法排序，header10】存放的是最权值最大的if(headeri.countheaderj.count)tmp=headeri;headeri=headerj;headerj=tmp;for(i=0;i256;i+)if(headeri.count=0)break;n=i;m=2*

29、n-1;一篇文章中有n个字符，则占取2n-1个空间来存储for(i=n;im;i+)/哈弗曼树除了叶子节点外的节点，即生成节点，进彳T n-1次合并，产生n-1个新节点min1=999999999;for(j=0;jheaderj.count)pt1=j;min1=headerj.count;/ 最小权赋值给 min1 continue;headeri.count=headerpt1.count;/ 最小权headerpt1.parent=i;headeri.lch=pt1;min1=999999999;/min1 取值这么 大是与 header【i】.count的值比较，从而找出最小权for

30、(j=0;jheaderj.count)pt1=j;min1=headerj.count;continue;/此过程找出的是次小权进行建树headeri.count+=headerpt1.count;headeri.rch=pt1;/ 确定 headeri的左孩子headerpt1.parent=i;/i就是开始两个最小的权值的值的和printf(字符统计对应权值哈弗曼编码n);for(i=0;in;i+)/ 循环，printf( %c ,headeri.b); /输出的是每个字符的权值printf(%d t,headeri.count);/输出每个字符的哈弗曼编码f=i;headeri.bi

31、ts0=0;先确定初始情况，while(headerf.parent!=-1)不断去找某个叶子节点的父节点，知道寻找到哈弗曼树的根节点为止j=f;/记录根节点f=headerf.parent;if(headerf.lch=j) j=strlen(headeri.bits);/记录的是节点i距离根节点的路径长度memmove(headeri.bits+1,headeri.bits,j+1);/ 将 headeri.bits 中移动 j+1 个字符给 headeri.bits+1headeri.bits0=0;回到初始情况，继续需找某个叶子节点的父节点，求它的哈弗曼编码else/headeri的右

32、孩子是j的情况j=strlen(headeri.bits);/求headeri.bits的长度，为了确定哈佛吗编码的长度memmove(headeri.bits+1,headeri.bits,j+1);/ 移动 j+1 个字符从 headeri到 headeri+1 的位置headeri.bits0=1;规定某个根节点的右子树编码路径是 1for(f=0;fn;f+)循环，输出的是某个节点的哈弗曼编码printf(%c,headeri.bitsf);printf(n);fseek(ifp,0,SEEK_SET);/压缩过程，将文件指针移到ifp的开始处fwrite(&flength,sizeo

33、f(int),1,ofp);/准备向文件指针ofp所指向的文彳也就是 D.txt中写入字符fseek(ofp,8,SEEK_SET);/将文件移动至距离开始8个字符处，因为根据 ascii码每个字符的编码时一个整数，可以用二进制的编码来表示buf0=0;f=0;pt1=8;while(!feof(ifp)/文件读取没有结束，就继续读取，知道结束c=fgetc(ifp);f+;/ 读取字符for(i=0;i=8)/如果buf中字符的长度大于8位时候，就读取 8位，处理for(i=0;i8;i+)if(bufi=1) c=(c1)|1;else c=c0)strcat(buf,00000000);

34、for(i=0;i8;i+) if(bufi=1) c=(c1)|1;else c=c1;fwrite(&c,1,1,ofp);pt1+;fseek(ofp,4,SEEK_SET);fwrite(&pt1,sizeof(long),1,ofp);fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp);for(i=0;in;i+)fwrite(&(headeri.b),1,1,ofp);c=strlen(headeri.bits);fwrite(&c,1,1,ofp);j=strlen(headeri.bits);if(j%8!=0)for(f

35、=j%8;f8;f+)strcat(headeri.bits,0);while(headeri.bits0!=0)c=0;for(j=0;j8;j+)if(headeri.bitsj=1) c=(c1)|1;else c=c1;strcpy(headeri.bits,headeri.bits+8);fwrite(&c,1,1,ofp); fclose(ifp);fclose(ofp);printf(n 压缩比:);printf(%f,(float)4/6);printf(n文档压缩成功！见C.txtn);)void jieya()/ 解压函数char buf255,bx255;/ 定义 buf

36、, bx 存放二进制编码unsigned char c;long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;/定义文件指针，进行文件的读写操作，其中， ifp用于读取c.txt中的字符,ofp用于向D.txt中写入字符ifp=fopen(C.txt,rb);/文件处理的具体操作if(ifp=NULL)printf(source file open error!n);return;)ofp=fopen(D.txt,wb);if(ofp=NULL)printf(destination file open error!n);return;)fread(&flength,sizeof(long),1,ifp);fread(&f,sizeof(long),1,ifp);fseek(ifp,f,SEEK_SET);fread(&n,sizeof(long),1,ifp);fo