霍夫曼编码对英文文本的压缩和解压缩.doc

Ｈｕffman编码对英文文本的压缩和解压缩中国地质大学计算机学院信息安全专业信息论实验报告#inｃlude #include #ｉnｃｌude　＜coniｏ．h>stｒuct　hｅａｄ {ﻩuｎsｉｇneｄ char ｂ; ﻩ ﻩﻩ ／/记录字符在数组中的位置ﻩloｎg count;ﻩ ﻩﻩ ﻩ ／/字符浮现频率(权值）　ﻩｌonｇ ｐaｒeｎｔ,lｃｈ,rch; ﻩ ﻩ／/定义哈夫曼树指针变量ﻩcｈａr bits[256];ﻩﻩﻩﻩ ／/定义存储哈夫曼编码的数组 }headeｒ[５12],ｔmp;voｉd　compｒｅss(） {ﻩｃｈａｒ fileｎame[255］,outputfile[２5５],bｕｆ［５12］; unsiｇｎｅｄ　cｈａr ｃ; ﻩlong n,m，i,j,f; ﻩ ﻩﻩ ﻩ //作计数或临时存储数据用 ｌong ｍin1，pt1,flength=0,ｌengtｈ1,leｎgth2;　 //记录最小结点、文献长度ﻩdouble div；ﻩﻩ //计算压缩比用ﻩFILE *ifp,*ｏfp; ﻩﻩﻩ ／/分别为输入、输出文献指针ﻩpｒiｎtf("\ｔ请您输入需要压缩的文献（需要途径）:")； gｅts（filｅnａme）； ﻩiｆｐ=fopｅn（ｆilｅｎaｍｅ,"rb＂); ﻩif（ifp==NUＬＬ){ﻩﻩpriｎtｆ("\ｎ\t文献打开失败!＼n "); ﻩﻩsyｓtem（"ｐａuse"); ﻩ ﻩreturn;　 } priｎｔf("\t请您输入压缩后的文献名(如无途径则默觉得桌面文献):"); getｓ(outpuｔｆｉlｅ); ﻩofp＝fｏpｅn（outpｕtfilｅ，＂wb"）;　 if（oｆp==NUＬL）｛ printf("＼n＼t压缩文献失败！\n ＂）; ﻩ system("ｐａuｓe"); ﻩﻩrｅtｕrn; ｝ ｆｌｅngth＝0; ﻩwｈiｌｅ(！feｏｆ（ifp)){ ﻩfreaｄ（&c,１,1,ifp)；　 headｅr[c].couｎt+＋；ﻩ ﻩﻩ ／/字符反复浮现频率+1 ﻩflenｇth＋+; ﻩ ﻩ／/字符浮现原文献长度+１ﻩ｝ﻩflength-－; ﻩleｎgth1=ｆlength; ﻩ ﻩ//原文献长度用作求压缩率的分母 heaｄer［c].ｃｏｕnt--； ﻩfｏr(ｉ＝0;ｉ＜51２;i+＋){ﻩ if(headeｒ[i］.ｃouｎt！=０） ﻩ hｅａdeｒ[i].b=(unｓigned　char)ｉ; ﻩﻩﻩ ﻩ／＊将每个哈夫曼码值及其相应的AＳＣＩＩ码ﻩﻩ ﻩ ﻩﻩﻩﻩ寄存在一维数组heaｄer[i]中,且编码表ﻩ ﻩﻩﻩﻩﻩ 中的下标和ＡＳCIＩ码满足顺序寄存关系*/ﻩ eｌse ﻩﻩﻩheader[i].b＝０; ﻩﻩhｅader[i].parenｔ=-1;heaｄer[i].ｌｃh＝heａdｅr[ｉ]．rch=-1; ／/对结点进行初始化 ｝ for(i＝0;i<２５6;i＋+){ ﻩﻩ //按浮现权值从大到小排序 ﻩfor(ｊ=ｉ+1;j<256;j＋+){ﻩ if（headｅr[i］．couｎtｈeader[j].cｏuｎt)｛ﻩﻩ ｐt１＝ｊ; ﻩﻩﻩﻩｍｉｎ1=ｈeadeｒ[ｊ]．coｕnt； ﻩﻩﻩcoｎtinuｅ;　 ﻩ}　ﻩ ｝ header[i］.count＋＝ｈeaｄer[pt1]．count;　 ﻩheadeｒ[i]．ｒｃh＝pｔ1; 　　ﻩﻩheａdeｒ［pt１].ｐareｎt=i； ﻩ ／/哈夫曼无反复前缀编码ﻩ} foｒ(ｉ＝0;i

下一种是'１',应当|1，成果０000０0０１　ﻩﻩﻩ 同理4位都做完,应当是0000０1１０，由于字节中的8位并没有 ﻩ所有用完,继续读下一种字符，根据编码表继续拼完剩余 ﻩﻩ 4位,如果字符的编码局限性4位，还要继续读一种字符,如果 ﻩ 字符编码超过4位,那么把剩余的位信息拼接到一种新的字节里＊/ whiｌe(!ｆeof(ifp))｛ﻩ c=fｇeｔｃ(ifp）; f++；　 ﻩｆor（ｉ＝０;ｉ＜ｎ；ｉ+＋){ﻩﻩﻩﻩﻩ//找到相应的heａder[i］ﻩ ﻩｉf(c=＝header[ｉ].ｂ) ﻩ ｂreａk； ﻩ｝ ｓｔrcaｔ(bｕｆ,header［i].ｂits); ﻩﻩj＝strlen(buf）;ﻩ ｃ=０; ﻩwhiｌe(j>=8）｛ﻩ for（i=0;ｉ<8;ｉ++){ﻩﻩ if（buｆ[i]＝='１')　ﻩﻩ ﻩﻩc=(c＜<1)｜１;ﻩ ﻩ//添加最后一位为1 ﻩﻩelse　ﻩ ﻩ c=c<<１；ﻩﻩﻩ //添加最后一位为0ﻩﻩﻩ} ﻩfwritｅ(&c，1,1,oｆｐ）; ﻩﻩｐt1++; 　 ﻩ strcｐy(buf,buf＋8)；　ﻩ ﻩｊ=ｓｔrleｎ(buf); ﻩﻩ ﻩ ﻩ ﻩ ﻩ}ﻩﻩif(f==flｅngtｈ） ﻩ ﻩbreak； ﻩ｝ if(j>0）{ ﻩﻩ ﻩﻩ //最后不满八位的buf解决 ﻩｓtrcaｔ（ｂuf,＂00000000"); ﻩ //ｂuf后加八位0 foｒ(i=０；i<8；ｉ＋+){ ﻩﻩ//逐位输入八位前的二进制符 ｉf(ｂuf[ｉ]＝=＇1') ﻩﻩﻩc=(c<＜1)|1; ﻩ ｅlsｅ ﻩﻩﻩｃ=c＜<１; }ﻩﻩfｗｒite（&c,1,１，ｏfｐ)； ﻩﻩpt1+＋; } fsｅek（ｏfp，４，SEEK_SＥＴ)； ﻩﻩﻩﻩ/／指针回到输出文献头部背面四位 fwrite(&pt1,ｓｉｚeof(lｏnｇ),１，ofｐ); ﻩ/／pｔ1记录了输出文献中的字符个数,涉及了最后的'/0' ｆseｅｋ（ofｐ,pt1,ＳEEＫ＿SＥT); ﻩfwrite(&n,ｓｉzｅof（long),1,ofp);ﻩﻩﻩﻩ／/ｎ记录了权值不为0的headeｒ[]数量 ｆoｒ(i＝0；i