版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p> 《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程設(shè)計(jì)報(bào)告</p><p> 課題名稱: 哈夫曼編碼</p><p> 課題設(shè)計(jì)人: </p><p><b> 學(xué)號(hào): </b></p><p> 指導(dǎo)教師: </p><p> 評(píng)閱成績(jī):__________________
2、__________</p><p> 評(píng)閱意見(jiàn):______________________________________________________________________________________________________________________________________________________________________________________
3、__________</p><p> 提交報(bào)告時(shí)間:20 13 年 12 月 25 日</p><p><b> 哈夫曼編碼</b></p><p><b> 實(shí)驗(yàn)三:哈夫曼編碼</b></p><p><b> 實(shí)驗(yàn)?zāi)康呐c要求</b></p><
4、;p> 1.要求對(duì)文件進(jìn)行Huffman編碼的算法,以及對(duì)一編碼文件進(jìn)行解碼的算法。</p><p> 2.熟練掌握二叉樹(shù)的應(yīng)用。</p><p><b> 三、實(shí)驗(yàn)環(huán)境</b></p><p> 1.硬件環(huán)境:Intel(R) Celeron®m CPU</p><p> 520 @1.60
5、GHz</p><p><b> 0.99GB 內(nèi)存</b></p><p><b> 2.軟件環(huán)境:</b></p><p> 操作系統(tǒng):WIN 7</p><p> 編譯軟件:MicroSoft Visual C++ 6.0</p><p><b>
6、四、算法描述</b></p><p><b> 1.概要設(shè)計(jì)</b></p><p> 1. bool InitFromFile(string fileadd) 從文件中初始化哈夫曼樹(shù)函數(shù)</p><p> 2. void HTCreat(HTNode ht[],int n) 構(gòu)造哈夫曼樹(shù)函數(shù)</p><p
7、> 3. void HCCreat(HTNode ht[],HCode hcd[],int n) 構(gòu)造哈夫曼編碼函數(shù)</p><p> 4. void ConvertFile(HCode hcd[],string fileadd,string fileadd2) 壓縮and寫入文件函數(shù)</p><p> 5. void DecompressionFile(string file
8、add2,string fileadd3) 文件解壓函數(shù)</p><p> 6. string Compression(string fileadd) 壓縮函數(shù)</p><p> 7. string Decompression(string fileadd2) 解壓函數(shù)</p><p><b> 2.壓縮算法:</b></p>
9、<p><b> A核心算法:</b></p><p> Huffman編碼是一種可變長(zhǎng)編碼方式,是由美國(guó)數(shù)學(xué)家David Huffman創(chuàng)立的,是二叉樹(shù)的一種特殊轉(zhuǎn)化形式。編碼的原理是:將使用次數(shù)多的代碼轉(zhuǎn)換成長(zhǎng)度較短的代碼,而使用次數(shù)少的可以使用較長(zhǎng)的編碼,并且保持編碼的唯一可解性。Huffman算法的最根本的原則是:累計(jì)的(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長(zhǎng)度)為最小,也就
10、是權(quán)值(字符的統(tǒng)計(jì)數(shù)字*字符的編碼長(zhǎng)度)的和最小。</p><p> B哈夫曼樹(shù)構(gòu)造算法:</p><p> Huffman樹(shù)是二叉樹(shù)的一種特殊轉(zhuǎn)化形式。以下是構(gòu)件Huffman樹(shù)的例子:比如有以下數(shù)據(jù), ABFACGCAHGBBAACECDFGFAAEABBB先進(jìn)行統(tǒng)計(jì)A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括號(hào)里面的是統(tǒng)計(jì)次數(shù)</p&
11、gt;<p> 生成Huffman樹(shù):每次取最小的那兩個(gè)節(jié)點(diǎn)(node)合并成一個(gè)節(jié)點(diǎn)(node),并且將累計(jì)數(shù)值相加作為新的接點(diǎn)的累計(jì)數(shù)值,最頂層的是根節(jié)點(diǎn)(root) 注:列表中最小節(jié)點(diǎn)的是指包括合并了的節(jié)點(diǎn)在內(nèi)的所有節(jié)點(diǎn),已經(jīng)合并的節(jié)點(diǎn)不在列表中</p><p><b> 運(yùn)算的過(guò)程如下:</b></p><p><b> 1:D
12、+H(2)</b></p><p><b> 2:DE+H(4)</b></p><p><b> 3:F+G(6)</b></p><p> 4:C+DEH(8)</p><p> 5:B+FG(12)</p><p> 6:A+CDEH(16)<
13、;/p><p> 7:ACDEH+BFG(28)</p><p> 那么轉(zhuǎn)化為Huffman樹(shù)就是</p><p> Huffman樹(shù) 層數(shù)</p><p> Root </p><p><b> ┌┴┐</b></p><p>
14、 ACDEH BFG 1</p><p><b> ┌┴┐┌┴┐</b></p><p> CDEH A B FG 2</p><p> ┌┴┐ ┌┴┐</p><p> DEH C F G 3</p>
15、<p><b> ┌┴┐</b></p><p> DH E 4</p><p><b> ┌┴┐</b></p><p> D H 5</p><p> 取左面是1 右面是
16、0 則有。</p><p> 注:層數(shù)就是位數(shù)或者說(shuō)是代碼長(zhǎng)度,權(quán)值=代碼長(zhǎng)度*該字的統(tǒng)計(jì)次數(shù)。</p><p> 代碼 位數(shù) 權(quán)值</p><p> A = 10 2 16</p><p> B = 01 2 12</p><
17、;p> C = 110 3 12</p><p> D = 11111 5 5</p><p> E = 1110 4 8</p><p> F = 001 3 9</p><p> G = 000
18、 2 6</p><p> H = 11110 5 5</p><p> 可以看出Huffman代碼是唯一可解的(uniquely decodable),如果你讀到110就一定是C ,不會(huì)有任何一個(gè)編碼是以110開(kāi)始的。</p><p> 如果不使用Huffman算法,而使用普通的編碼,結(jié)果是什么呢?</
19、p><p> Huffman樹(shù) 層數(shù)</p><p><b> Root</b></p><p><b> ┌┴┐</b></p><p> ABCD EFGH 1</p><p><b> ┌┴┐ ┌
20、┴┐</b></p><p> AB CD EF GH 2</p><p> ┌┴┐┌┴┐┌┴┐┌┴┐</p><p> A B C D E F G H 3</p><p> 取左面是1 右面是0 則有</p><p> 代碼
21、 位數(shù) 權(quán)值</p><p> A = 111 3 24</p><p> B = 110 3 18</p><p> C = 101 3 12</p><p> D = 100 3 3</p>
22、;<p> E = 011 3 6</p><p> F = 010 3 9</p><p> G = 001 3 9</p><p> H = 000 3 3</p><p> 利用Huffman編
23、碼得到的權(quán)值累計(jì)是 73,如果利用普通定長(zhǎng)編碼的話,則要用84字符長(zhǎng)度。從這個(gè)比較,可以看出,Huffman是怎么進(jìn)行壓縮的。</p><p> C哈夫曼編碼結(jié)構(gòu)及算法</p><p> 編碼:將ABCDEFGH用Huffman樹(shù)產(chǎn)生的編碼對(duì)應(yīng)著寫到文件中,并且保留原始的Huffman樹(shù),主要是編碼段的信息。一般要編碼256個(gè)元素的話需要511個(gè)單位來(lái)儲(chǔ)存Huffman樹(shù),每個(gè)Huff
24、man樹(shù)都必須有以下的結(jié)構(gòu):code,char,left,right,probability(出現(xiàn)次數(shù)),通常情況是利用一個(gè)數(shù)組結(jié)構(gòu)。因?yàn)樵诮獯a的時(shí)候只需要用到code,所以只需要記錄每個(gè)元素的編碼就可以了。</p><p> 解碼:利用文件中保存的Huffman編碼,一一對(duì)應(yīng),解讀編碼,把可變長(zhǎng)編碼轉(zhuǎn)換為定長(zhǎng)編碼。</p><p> D寫入算法的優(yōu)化——使用二級(jí)1024K緩沖器<
25、;/p><p> 在寫入編碼的過(guò)程中,宏觀的過(guò)程是:以字節(jié)形式讀取原文件,然后找到該字節(jié)的編碼,進(jìn)而以字節(jié)形式寫到壓縮文件中去。不停的字節(jié)讀寫會(huì)給cpu帶來(lái)頻繁的中斷并且硬盤的磁頭來(lái)回在磁道扇區(qū)中移動(dòng),減慢了速度。而如果以數(shù)據(jù)塊的形式讀寫則可以有效地利用到DMA通訊,減少了cpu中斷,并使硬盤磁頭連續(xù)移動(dòng),顯著加快了速度。而c++語(yǔ)言的iofstream類的read()與write()成員函數(shù)為此思想的實(shí)現(xiàn)提供了可
26、能。 </p><p> 所以,可以開(kāi)辟一個(gè)1024K的緩沖區(qū),先將文件前1024K的字節(jié)讀入內(nèi)存緩沖區(qū)中,編碼后的字節(jié)也不急于寫入文件中,而是先寫到另一個(gè)二級(jí)緩沖區(qū)中,當(dāng)其足夠1024K時(shí)再以數(shù)據(jù)塊的形式寫到壓縮文件中。然后清空緩沖區(qū),繼續(xù)做下一個(gè)1024K的編碼寫入。</p><p> 而緩沖區(qū)本身,其實(shí)就是二個(gè)整形數(shù)組,read_buffer[1048576]和write_buf
27、fer[1048576]。不過(guò)這樣的數(shù)組聲明已經(jīng)太大了,可以用STL的vector向量類來(lái)代替這個(gè)數(shù)組(vector結(jié)構(gòu)實(shí)際也就是一個(gè)封裝了的加強(qiáng)型數(shù)組)。</p><p><b> 3.解壓算法</b></p><p> A.基于字符匹配的解壓算法</p><p> 讀出結(jié)點(diǎn)數(shù)就能知道哈夫曼樹(shù)存入部分的總長(zhǎng),方便讀出樹(shù)哈夫曼樹(shù)(子結(jié)點(diǎn)值
28、和權(quán)值),就能由次些信息重新構(gòu)造完整的哈夫曼樹(shù),和各結(jié)點(diǎn)的哈夫曼編碼。解壓時(shí),讀取一個(gè)字節(jié)(8 bit)用一個(gè)函數(shù)轉(zhuǎn)換為8個(gè)字符(用一個(gè)數(shù)組記錄,其元素只是一個(gè)0或一個(gè)1),然后按哈夫曼樹(shù)從頂向下查找,如果到達(dá)葉子結(jié)點(diǎn),就讀出該葉子結(jié)點(diǎn)的值,放入緩沖區(qū)中,如果不是,則繼續(xù)找,如此重復(fù),直到緩沖區(qū)滿了,就寫入到解壓文件中,再循環(huán)以上過(guò)程,直到處理完所有數(shù)據(jù)。</p><p><b> B.緩沖輸入輸出&
29、lt;/b></p><p> 和壓縮時(shí)采用1M二級(jí)緩沖相同,如果的壓縮時(shí)也采用此技術(shù),也會(huì)有很大的速度優(yōu)化,當(dāng)然程序也變得更加復(fù)雜。</p><p><b> 五、源程序</b></p><p> #include<fstream></p><p> #include<iostream&
30、gt;</p><p> #include<String></p><p> #include<cmath></p><p> using namespace std;</p><p> struct HTNode</p><p><b> {</b></p
31、><p> char data; //節(jié)點(diǎn)數(shù)據(jù)</p><p> int weight; //權(quán)值</p><p> int parent; //父親</p><p> int lchild; //左孩子</p><p> int rchild; //右孩子</p><p>&
32、lt;b> };</b></p><p> typedef char* Code;</p><p> HTNode *ht;</p><p> Code *hcd;</p><p> int maplist[256]; //建立字符與哈夫曼編碼的映射</p><p> int
33、nodenum=0; //哈夫曼樹(shù)結(jié)點(diǎn)數(shù)</p><p> int rearnum=0; //哈夫曼編碼尾補(bǔ)碼</p><p> int textlen=0; //需壓縮的文件長(zhǎng)度</p><p> int codelen=0; //壓縮后的文件的哈夫曼編碼總長(zhǎng)度</p>&
34、lt;p> int const bufferlen=1024; //設(shè)置讀取緩沖區(qū)長(zhǎng)度</p><p> int clean(); //清空節(jié)點(diǎn)及編碼指針內(nèi)容</p><p> void dtobin(int num,int bin[8]); //十進(jìn)制變換成二進(jìn)制</p><p> void H
35、TCreate(HTNode ht[],int n); //建立哈夫曼樹(shù)</p><p> void HCCreat(HTNode ht[],Code hcd[],int n); //提取哈夫曼編碼</p><p> void WriteFile(char *tmp); //寫入文件</p><p> unsigned char
36、 ConvertBinary(char *tmp);//變換二進(jìn)制文件</p><p> void ConvertFile(Code hcd[],string fileadd,string fileadd2);//壓縮并解壓文件</p><p> bool InitFromFile(string fileadd);//初始化文件</p><p>
37、; void DecompressionFile(string fileadd2,string fileadd3); //解壓文件</p><p> string Compression(string fileadd);//壓縮文件</p><p> string Decompression(string fileadd2); //解壓文件子函數(shù)<
38、;/p><p> ///////////////十進(jìn)制轉(zhuǎn)二進(jìn)制函數(shù)/////////////////</p><p> int clean()</p><p><b> {</b></p><p> delete[] ht;</p><p> delete[] hcd;</p>
39、<p><b> return 1;</b></p><p><b> }</b></p><p> void dtobin(int num,int bin[8])</p><p><b> {</b></p><p><b> int i=0;
40、</b></p><p> for(i=0;i<8;i++)</p><p><b> {</b></p><p><b> bin[i]=0;</b></p><p><b> }</b></p><p><b>
41、 i=0;</b></p><p> while(num>0)</p><p><b> {</b></p><p> bin[8-1-i]=num%2;</p><p> num=num/2;</p><p><b> i++;</b></
42、p><p><b> }</b></p><p><b> }</b></p><p> //////////////////壓縮和寫入文件//////////////////</p><p> void ConvertFile(Code hcd[],string fileadd,string
43、fileadd2)</p><p><b> {</b></p><p> ////////////////////////////////////////</p><p> fstream infile(fileadd.c_str(),ios::in|ios::binary);</p><p> fstream
44、 outfile(fileadd2.c_str(),ios::out|ios::binary);</p><p> if(!infile) cout<<"open file fail!"<<endl;</p><p> if(!outfile) cout<<"creat file fail!"<<e
45、ndl;</p><p> //unsigned</p><p><b> char ch;</b></p><p> /////////////寫入哈夫曼樹(shù)//////////////</p><p> ch=nodenum;</p><p> outfile.write(&c
46、h,1); ///寫入結(jié)點(diǎn)數(shù)</p><p><b> ch=8;</b></p><p> outfile.write(&ch,1); ///寫入補(bǔ)位數(shù)(預(yù)寫入)</p><p> codelen=0;</p><p> outfile.write((char *)&
47、codelen,4); //寫入壓縮后的文件的哈夫曼編碼總長(zhǎng)度(預(yù)寫入)</p><p><b> int h=0;</b></p><p> for(h=0;h<nodenum;h++)</p><p><b> {</b></p><p> outfile.write((char
48、*)&ht[h].data,sizeof(char));</p><p> outfile.write((char*)&ht[h].weight,sizeof(int));</p><p><b> }</b></p><p> ///////////////////////////</p><p>
49、; char tmp[8]; //設(shè)置緩沖區(qū)</p><p> char outbuffer[bufferlen]; //設(shè)置寫入緩沖區(qū)</p><p> char *tmpcd;</p><p> int i=0,j,k,last=0;</p><p> char inbuffer[bufferlen];</p&g
50、t;<p> int readlen=0;</p><p> //infile.seekg(i,ios::beg);</p><p><b> h=0;</b></p><p><b> do</b></p><p><b> {</b></p&g
51、t;<p> infile.read(inbuffer,bufferlen);</p><p> readlen=infile.gcount();</p><p> tmpcd=hcd[maplist[(unsigned char)inbuffer[i]]];</p><p> for(i=0;i<readlen;)</p>
52、<p><b> {</b></p><p> for(j=last;j<8 && *tmpcd!='\0';j++)</p><p><b> {</b></p><p> tmp[j]=*tmpcd;</p><p><b>
53、 tmpcd++;</b></p><p><b> }</b></p><p> if(j==8 && *tmpcd=='\0')</p><p><b> {</b></p><p><b> last=0;</b><
54、;/p><p><b> i++;</b></p><p> ch=ConvertBinary(tmp);</p><p> //cout<<':'<<(unsigned int)ch<<' ';</p><p> outbuffer[h]=ch;&
55、lt;/p><p><b> h++;</b></p><p> codelen++; //壓縮文件長(zhǎng)度加一</p><p> if(h==bufferlen)</p><p><b> {</b></p><p> outfile.write(outbuffer,
56、bufferlen);</p><p><b> h=0;</b></p><p><b> }</b></p><p> if(i<readlen) tmpcd=hcd[maplist[(unsigned char)inbuffer[i]]];</p><p><b> e
57、lse</b></p><p><b> {</b></p><p><b> i=0;</b></p><p><b> break;</b></p><p><b> }</b></p><p><b&
58、gt; }</b></p><p> else if(j<8 && *tmpcd=='\0')</p><p><b> {</b></p><p><b> last=j;</b></p><p><b> i++;</b
59、></p><p> if(i<readlen) tmpcd=hcd[maplist[(unsigned char)inbuffer[i]]];</p><p><b> else</b></p><p><b> { i=0;</b></p><p><b>
60、break;</b></p><p><b> }</b></p><p> /////繼續(xù)循換////</p><p><b> }</b></p><p> else if(j==8 && *tmpcd!='\0')</p>&l
61、t;p><b> {</b></p><p><b> last=0;</b></p><p> //WriteFile(tmp);</p><p> ch=ConvertBinary(tmp);</p><p> outbuffer[h]=ch;</p><p&
62、gt;<b> h++;</b></p><p> codelen++; //壓縮文件長(zhǎng)度加一</p><p> if(h==bufferlen)</p><p><b> {</b></p><p> outfile.write(outbuffer,bufferlen);</p
63、><p><b> h=0;</b></p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p&g
64、t;<p> while(readlen==bufferlen);</p><p> if(j==8 && readlen<bufferlen)</p><p><b> {</b></p><p> outfile.write(outbuffer,h);</p><p>&l
65、t;b> }</b></p><p> else if(j<8 && readlen<bufferlen)</p><p><b> {</b></p><p> for(k=j;k<8;k++)</p><p><b> {</b>&l
66、t;/p><p> tmp[k]='0';</p><p><b> }</b></p><p> ch=ConvertBinary(tmp);</p><p> outbuffer[h]=ch;</p><p><b> h++;</b></p&
67、gt;<p> outfile.write(outbuffer,h);</p><p> codelen++; //壓縮文件長(zhǎng)度加一</p><p><b> }</b></p><p> cout<<endl;</p><p><b> ch=8-j;</b>
68、;</p><p> rearnum=8-j;</p><p> outfile.seekp(1,ios::beg);</p><p> outfile.write(&ch,1); //寫入真正的補(bǔ)位數(shù)</p><p> outfile.seekp(2,ios::beg);</p><p>
69、 outfile.write((char*)&codelen,4); //寫入真正的壓縮后的文件的哈夫曼編碼總長(zhǎng)度長(zhǎng)度</p><p> outfile.close();</p><p> infile.close();</p><p><b> }</b></p><p> ////////////
70、//構(gòu)造哈夫曼樹(shù)////////////</p><p> void HTCreate(HTNode ht[],int n)</p><p><b> {</b></p><p> int i,k,lnode,rnode;</p><p> int min1,min2;</p><p>
71、 for(i=0;i<2*n-1;i++)</p><p><b> {</b></p><p> ht[i].parent=ht[i].rchild=ht[i].lchild=-1;</p><p><b> }</b></p><p> for(i=n;i<2*n-1;i++
72、)</p><p><b> {</b></p><p> min1=min2=2147483647;</p><p> lnode=rnode=-1;</p><p> for(k=0;k<=i-1;k++)</p><p><b> {</b></p
73、><p> if(ht[k].parent==-1)</p><p><b> {</b></p><p> if(ht[k].weight<min1)</p><p><b> {</b></p><p> min2=min1;</p><p
74、> min1=ht[k].weight;</p><p> rnode=lnode;</p><p><b> lnode=k;</b></p><p><b> }</b></p><p> else if(ht[k].weight<min2)</p><
75、p><b> {</b></p><p> min2=ht[k].weight;</p><p><b> rnode=k;</b></p><p><b> }</b></p><p><b> }</b></p><
76、p><b> }</b></p><p> ht[lnode].parent=i;</p><p> ht[rnode].parent=i;</p><p> ht[i].weight=ht[lnode].weight+ht[rnode].weight;</p><p> ht[i].lchild=lno
77、de;</p><p> ht[i].rchild=rnode;</p><p><b> }</b></p><p><b> }</b></p><p> ///////////構(gòu)造哈夫曼編碼/////////////</p><p> void HCCreat
78、(HTNode ht[],Code hcd[],int n)</p><p><b> {</b></p><p> int i,p,c;</p><p><b> Code hc;</b></p><p> hc=new char[n];</p><p> int
79、 start,tmplen;</p><p> for(i=0;i<n;i++)</p><p><b> {</b></p><p><b> tmplen=0;</b></p><p> start=n-1;</p><p> hc[start]='
80、;\0';</p><p><b> c=i;</b></p><p> p=ht[i].parent;</p><p> while(p!=-1)</p><p><b> {</b></p><p> if(ht[p].lchild==c) //是左孩
81、子結(jié)點(diǎn)</p><p><b> {</b></p><p> hc[--start]='0';</p><p><b> tmplen++;</b></p><p><b> }</b></p><p><b> e
82、lse</b></p><p><b> {</b></p><p> hc[--start]='1';</p><p><b> tmplen++;</b></p><p><b> }</b></p><p>&l
83、t;b> c=p;</b></p><p> p=ht[p].parent;</p><p><b> }</b></p><p> hcd[i]=new char[n-start];</p><p> strcpy(hcd[i],&hc[start]);</p><
84、;p><b> }</b></p><p> delete[] hc;</p><p><b> }</b></p><p> void WriteFile(char *tmp)</p><p><b> {</b></p><p>&l
85、t;b> int i;</b></p><p> for(i=0;i<8;i++)</p><p> cout<<tmp[i];</p><p> cout<<' ';</p><p><b> tmp="";</b></
86、p><p><b> }</b></p><p> unsigned char ConvertBinary(char *tmp)</p><p><b> {</b></p><p> char ch=0;</p><p><b> int i;</b&
87、gt;</p><p> for(i=0;i<8;i++)</p><p><b> {</b></p><p> ch=(unsigned char)pow(2.0,8-i-1)*(tmp[i]-48)+ch;</p><p><b> }</b></p><p&
88、gt; return ch;</p><p><b> }</b></p><p> //////////////打開(kāi)文件//////////////</p><p> bool InitFromFile(string fileadd)</p><p><b> {</b></p&g
89、t;<p> fstream infile(fileadd.c_str(),ios::binary|ios::in);</p><p> if(!infile){cout<<"error!"<<endl;return 0;}</p><p> int table[256];</p><p><b&
90、gt; int i,j;</b></p><p> int len=0,num=0;</p><p> unsigned char ch;</p><p> for(i=0;i<256;i++) {table[i]=0;maplist[i]=-1;}</p><p> int readlen=0;</p>
91、;<p> char buffer[bufferlen]; //設(shè)置讀取緩沖區(qū),加快讀取速度</p><p><b> do</b></p><p><b> {</b></p><p> infile.read(buffer,bufferlen);</p><p
92、><b> i=0;</b></p><p> readlen=infile.gcount();</p><p> while(i<readlen)</p><p><b> {</b></p><p> ch=(unsigned char)buffer[i];</p&g
93、t;<p> table[ch]++;</p><p><b> len++;</b></p><p><b> i++;</b></p><p><b> }</b></p><p><b> }</b></p>&
94、lt;p> while(readlen==bufferlen);</p><p> for(i=0;i<256;i++)</p><p><b> {</b></p><p> if(table[i]!=0) num++;</p><p><b> }</b></p>
95、;<p> ht=new HTNode[2*num-1];</p><p> hcd=new Code[num];</p><p> for(i=0,j=0;i<256;i++)</p><p><b> {</b></p><p> if(table[i]!=0)</p>&
96、lt;p><b> {</b></p><p> ht[j].data=i;</p><p> ht[j].weight=table[i];</p><p> maplist[i]=j; //建立字符與哈夫曼編碼的映射</p><p><b> j++;</b></p>
97、<p><b> }</b></p><p><b> }</b></p><p> nodenum=num;</p><p> textlen=len;</p><p> infile.clear();</p><p> infile.close(
98、);</p><p><b> return 1;</b></p><p><b> }</b></p><p> /////////////從文件解壓////////////////////</p><p> void DecompressionFile(string fileadd2,s
99、tring fileadd3)</p><p><b> {</b></p><p> //cout<<"............解壓并輸出新文件過(guò)程:"<<endl;</p><p> fstream infile(fileadd2.c_str(),ios::in|ios::binary);&
100、lt;/p><p> fstream outfile(fileadd3.c_str(),ios::out|ios::binary);</p><p> cout<<endl;</p><p> /////////////////讀出哈夫曼樹(shù)的數(shù)據(jù)/////////////</p><p><b> int h=0;&
101、lt;/b></p><p> char buffer[bufferlen]; //讀入文件的緩沖區(qū)</p><p> char outbuffer[bufferlen]; //寫入文件的緩沖區(qū)</p><p> infile.read(buffer,1);</p><p> nodenum=(unsigned c
102、har)*buffer;//哈夫曼樹(shù)結(jié)點(diǎn)數(shù)</p><p> if(nodenum==0) nodenum=256;</p><p> infile.read(buffer,1);</p><p> rearnum=(unsigned char)*buffer;</p><p> infile.read((char*)&cod
103、elen,4);</p><p> //cout<<" 讀出哈夫曼樹(shù)數(shù)據(jù)...."<<endl;</p><p> ht=new HTNode[2*nodenum-1];</p><p> hcd=new Code[nodenum];</p><p> //hcdlen=new int[n
104、odenum];</p><p> for(h=0;h<nodenum;h++)</p><p><b> {</b></p><p> infile.read(&ht[h].data,1);</p><p> infile.read((char*)&ht[h].weight,4);<
105、/p><p><b> }</b></p><p> //////構(gòu)走哈夫曼樹(shù)///////</p><p> HTCreate(ht,nodenum);</p><p> //////構(gòu)造哈夫曼編碼/////</p><p> HCCreat(ht,hcd,nodenum);</p&
106、gt;<p> ///////////////////////////////////////////////</p><p> ///////////////////////解壓并輸出解壓文件////////////////////////</p><p> char *buffertmp=new char;</p><p> int bin
107、[8],j=0,i=0;</p><p> int coderead=0; //記錄以度的長(zhǎng)度,用于判斷何時(shí)達(dá)到文件最后一字節(jié)(用codelen比較)</p><p> int readlen=0;</p><p> int child=0;</p><p> int last=2*nodenum-2; //解壓時(shí)記錄上次
108、指示器的位置</p><p> child=last;</p><p> unsigned char outp;</p><p><b> h=0;</b></p><p><b> do</b></p><p><b> {</b></
109、p><p> infile.read(buffer,bufferlen);</p><p> readlen=infile.gcount();</p><p> for(j=0;j<readlen;j++)</p><p><b> {</b></p><p> coderead++;
110、</p><p> outp=buffer[j];</p><p> dtobin(outp,bin);</p><p> if(coderead==codelen) //達(dá)到文件尾</p><p><b> {</b></p><p> for(i=0;i<=8-rearnu
111、m;i++)</p><p><b> {</b></p><p> if(ht[child].lchild==-1 && ht[child].rchild==-1)</p><p><b> {</b></p><p> //cout<<ht[child].da
112、ta;</p><p> outbuffer[h]=ht[child].data;</p><p><b> h++;</b></p><p> if(h==bufferlen) {outfile.write(outbuffer,bufferlen);h=0;}</p><p> last=2*nodenum-2
113、;</p><p> if(i==8-rearnum)</p><p><b> {</b></p><p> if(h!=0) outfile.write(outbuffer,h);</p><p> child=last;</p><p><b> break;</b
114、></p><p><b> }</b></p><p><b> else i--;</b></p><p><b> }</b></p><p> else if(i!=8)</p><p> { if(bin[i]==0) l
115、ast=ht[child].lchild;</p><p> else if(bin[i]==1) last=ht[child].rchild;</p><p><b> }</b></p><p> child=last;</p><p><b> }</b></p><
116、;p><b> }</b></p><p> else //沒(méi)達(dá)到文件尾</p><p><b> {</b></p><p> for(i=0;i<=8;i++)</p><p><b> {</b></p><
117、;p> if(ht[child].lchild==-1 && ht[child].rchild==-1)</p><p><b> {</b></p><p> //cout<<ht[child].data;</p><p> outbuffer[h]=ht[child].data;</p>
118、<p><b> h++;</b></p><p> if(h==bufferlen)</p><p><b> {</b></p><p> outfile.write(outbuffer,bufferlen);</p><p><b> h=0;</b&g
119、t;</p><p><b> }</b></p><p> last=2*nodenum-2;</p><p><b> if(i==8)</b></p><p><b> {</b></p><p> child=last;</p&g
120、t;<p><b> break;</b></p><p><b> }</b></p><p><b> else i--;</b></p><p><b> }</b></p><p> else if(i!=8)</p&
121、gt;<p> { if(bin[i]==0) last=ht[child].lchild;</p><p> else if(bin[i]==1) last=ht[child].rchild;</p><p><b> }</b></p><p> child=last;</p><p>&
122、lt;b> }</b></p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> while(readlen==bufferlen);</p><p>
123、 //cout<<j<<endl;</p><p> infile.close();</p><p> outfile.close();</p><p><b> }</b></p><p> string Compression(string fileadd)</p>&
124、lt;p><b> {</b></p><p><b> int i;</b></p><p> for(i=0;i<fileadd.length();i++)</p><p> if(fileadd[i]=='\\') fileadd[i]='/';</p>
125、<p> string fileadd2;</p><p> fileadd2=fileadd+".rax";</p><p> InitFromFile(fileadd); //從文件中初始化哈夫曼樹(shù)</p><p> HTCreate(ht,nodenum); //構(gòu)造哈夫曼樹(shù) </p>
126、<p> HCCreat(ht,hcd,nodenum); //構(gòu)造哈夫曼編碼</p><p> ConvertFile(hcd,fileadd,fileadd2); //壓縮并寫入文件</p><p><b> clean();</b></p><p> return fileadd2;</p>&
127、lt;p><b> }</b></p><p> string Decompression(string fileadd2)</p><p><b> {</b></p><p><b> int i;</b></p><p> for(i=0;i<fil
128、eadd2.length();i++)</p><p> if(fileadd2[i]=='\\') fileadd2[i]='/';</p><p> string fileclass;</p><p> string fileadd3;</p><p> for(i=fileadd2.length(
129、)-5;fileadd2[i]!='.' && i>0;i--) </p><p> fileclass.insert(0,fileadd2.substr(i,1));</p><p><b> if(i!=0) </b></p><p> fileadd3=fileadd2.substr(0,i)+
130、"_"+'.'+fileclass;</p><p><b> else </b></p><p> fileadd3=fileadd2.substr(0,fileadd2.length()-4)+"_";</p><p> DecompressionFile(fileadd2,fi
131、leadd3);</p><p><b> clean();</b></p><p> return fileadd3;</p><p><b> }</b></p><p> int main()</p><p><b> {</b><
132、/p><p> cout<<"緩沖區(qū)長(zhǎng)度:"<<bufferlen<<"Bytes."<<endl<<endl;</p><p> cout<<"\t*******************************************************\n&qu
133、ot;;</p><p> cout<<"\t* *\n";</p><p> cout<<"\t* 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) *\n";</p>
134、<p> cout<<"\t* 基于哈夫曼的文件壓縮解壓程序 *\n";</p><p> cout<<"\t* *\n";</p><p> cout<
135、;<"\t*******************************************************\n"; </p><p> string fileadd;</p><p> string fileadd2;</p><p> char usage;</p><p><b>
136、 do</b></p><p><b> {</b></p><p> cout<<""<<endl;</p><p> cout<<"(1)壓縮C"<<endl;</p><p> cout<<&q
137、uot;(2)解壓D"<<endl;</p><p> cout<<"(3)退出Q "<<endl;</p><p> cout<<""<<endl;</p><p> cout<<"*請(qǐng)輸入選項(xiàng):";</p>
138、;<p> cin>>usage;</p><p> if(usage=='C' || usage=='c')</p><p><b> {</b></p><p> cout<<"請(qǐng)輸入壓縮文件的路徑:";</p><p>
139、; cin>>fileadd;</p><p> cout<<"壓縮文件開(kāi)始..."; </p><p> fileadd2=Compression(fileadd);</p><p> cout<<"壓縮文件完畢,壓縮后文件的路徑是:"<<fileadd2<<
140、;endl<<endl;</p><p><b> }</b></p><p> else if(usage=='D' || usage=='d')</p><p><b> {</b></p><p> cout<<"請(qǐng)輸入
141、解壓文件的路徑:";</p><p> cin>>fileadd;</p><p> cout<<"解壓文件開(kāi)始..."; </p><p> fileadd2=Decompression(fileadd);</p><p> cout<<"解壓文件完畢,解壓
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 課程設(shè)計(jì)-哈夫曼編碼
- 《哈夫曼編碼》課程設(shè)計(jì)
- 課程設(shè)計(jì)哈夫曼編碼
- 課程設(shè)計(jì) 哈夫曼樹(shù)及哈夫曼編碼
- 哈夫曼編碼課程設(shè)計(jì)
- 課程設(shè)計(jì)哈夫曼編碼
- 哈夫曼編碼與譯碼課程設(shè)計(jì)報(bào)告
- 課程設(shè)計(jì)--哈夫曼編碼與譯碼
- (哈夫曼編碼譯碼器)(課程設(shè)計(jì)報(bào)告)
- 課程設(shè)計(jì)---哈夫曼編碼編程實(shí)現(xiàn)
- 哈夫曼課程設(shè)計(jì)報(bào)告
- 哈夫曼編碼的java實(shí)現(xiàn)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈夫曼編碼
- 哈夫曼編碼譯碼器課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼編碼
- 哈夫曼課程設(shè)計(jì)報(bào)告--哈夫曼編譯碼器
- 哈夫曼樹(shù)課程設(shè)計(jì)報(bào)告
- 哈夫曼編碼譯碼的實(shí)現(xiàn)課程設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論