哈夫曼編碼畢業(yè)課程設(shè)計報告

1、(此文檔為word格式，下載后您可任意編輯修改！)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告基于哈夫曼樹的文件壓縮/解壓程序 專業(yè)班級：信科（2）班 姓名：徐愛娟 謝靜學(xué)號： 51 50 _31 一 需求分析1.課題要求（實現(xiàn)文件的壓縮與解壓并計算壓縮率）A.描述壓縮基本符號的選擇方法B.運行時壓縮原文件的規(guī)模應(yīng)不小于5K2.設(shè)計目標(biāo)A軟件名稱：基于哈夫曼編碼的文件壓縮實用程序系統(tǒng)B軟件組成：huffman.exe C制作平臺及相關(guān)調(diào)試工具： Windows XP sp3 Microsoft Visual C+ 6.0D運行環(huán)境：dos/ win2K/win2003/winxp/E性能特點：1. 軟件由一個可執(zhí)行文

2、件組成huffman.exe為dos系統(tǒng)應(yīng)用程序，體積小，高效快捷，適用范圍廣。2. 對單字節(jié)（256葉子）進行哈夫曼編碼，壓縮率良好3. 使用二級緩沖壓縮/解壓技術(shù)，速度比一般算法高4. 可壓縮最大體積為4G的文件，達到Fat32文件系統(tǒng)極限5. 文件索引體積比常規(guī)算法小50%二概要設(shè)計1.相關(guān)函數(shù)介紹1. bool InitFrom ) 從文件中初始化哈夫曼樹函數(shù)2. void HTCreat(HTNode ht,int n) 構(gòu)造哈夫曼樹函數(shù)3. void HCCreat(HTNode ht,HCode hcd,int n) 構(gòu)造哈夫曼編碼函數(shù)4. void Convert hcd,st

3、ring ) 壓縮and寫入文件函數(shù)5. void Decompression ) 文件解壓函數(shù)6. string Compression(string ) 壓縮函數(shù)7. string Decompression(string ) 解壓函數(shù)三 詳細設(shè)計1壓縮算法部分A核心算法： Huffman編碼是一種可變長編碼方式，是由美國數(shù)學(xué)家David Huffman創(chuàng)立的，是二叉樹的一種特殊轉(zhuǎn)化形式。編碼的原理是：將使用次數(shù)多的代碼轉(zhuǎn)換成長度較短的代碼，而使用次數(shù)少的可以使用較長的編碼，并且保持編碼的唯一可解性。Huffman算法的最根本的原則是：累計的(字符的統(tǒng)計數(shù)字*字符的編碼長度)為最小，也就是

4、權(quán)值(字符的統(tǒng)計數(shù)字*字符的編碼長度)的和最小。B哈夫曼樹構(gòu)造算法：Huffman樹是二叉樹的一種特殊轉(zhuǎn)化形式。以下是構(gòu)件Huffman樹的例子：比如有以下數(shù)據(jù)， ABFACGCAHGBBAACECDFGFAAEABBB先進行統(tǒng)計A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括號里面的是統(tǒng)計次數(shù)生成Huffman樹：每次取最小的那兩個節(jié)點(node)合并成一個節(jié)點(node)，并且將累計數(shù)值相加作為新的接點的累計數(shù)值，最頂層的是根節(jié)點(root) 注：列表中最小節(jié)點的是指包括合并了的節(jié)點在內(nèi)的所有節(jié)點，已經(jīng)合并的節(jié)點不在列表中運算的過程如下：1:D+H(2)2

5、:DE+H(4)3:F+G(6)4:C+DEH(8)5:B+FG(12)6:A+CDEH(16)7:ACDEH+BFG(28)那么轉(zhuǎn)化為Huffman樹就是Huffman樹 層數(shù) Root ACDEH BFG 1 CDEH A B FG 2 DEH C F G 3 DH E 4D H 5取左面是1 右面是0 則有。注：層數(shù)就是位數(shù)或者說是代碼長度，權(quán)值=代碼長度*該字的統(tǒng)計次數(shù)。 代碼 位數(shù) 權(quán)值A(chǔ) = 10 2 16B = 01 2 12C = 110 3 12D = 11111 5 5E = 1110 4 8F = 001 3 9G = 000 2 6H = 11110 5 5可以看出Hu

6、ffman代碼是唯一可解的(uniquely decodable)，如果你讀到110就一定是C ，不會有任何一個編碼是以110開始的。如果不使用Huffman算法，而使用普通的編碼，結(jié)果是什么呢？Huffman樹 層數(shù) Root ABCD EFGH 1 AB CD EF GH 2A B C D E F G H 3取左面是1 右面是0 則有代碼 位數(shù) 權(quán)值A(chǔ) = 111 3 24B = 110 3 18C = 101 3 12D = 100 3 3E = 011 3 6F = 010 3 9G = 001 3 9H = 000 3 3利用Huffman編碼得到的權(quán)值累計是 73，如果利用普通定長

7、編碼的話，則要用84字符長度。從這個比較，可以看出，Huffman是怎么進行壓縮的。C哈夫曼編碼結(jié)構(gòu)及算法編碼：將ABCDEFGH用Huffman樹產(chǎn)生的編碼對應(yīng)著寫到文件中，并且保留原始的Huffman樹，主要是編碼段的信息。一般要編碼256個元素的話需要511個單位來儲存Huffman樹，每個Huffman樹都必須有以下的結(jié)構(gòu)：code,char,left,right,probability(出現(xiàn)次數(shù))，通常情況是利用一個數(shù)組結(jié)構(gòu)。因為在解碼的時候只需要用到code，所以只需要記錄每個元素的編碼就可以了。解碼：利用文件中保存的Huffman編碼，一一對應(yīng)，解讀編碼，把可變長編碼轉(zhuǎn)換為定長編

8、碼。2解壓縮算法部分A.基于字符匹配的解壓算法讀出結(jié)點數(shù)就能知道哈夫曼樹存入部分的總長，方便讀出樹哈夫曼樹（子結(jié)點值和權(quán)值），就能由次些信息重新構(gòu)造完整的哈夫曼樹，和各結(jié)點的哈夫曼編碼。解壓時，讀取一個字節(jié)（8 bit）用一個函數(shù)轉(zhuǎn)換為8個字符（用一個數(shù)組記錄，其元素只是一個0或一個1），然后按哈夫曼樹從頂向下查找，如果到達葉子結(jié)點，就讀出該葉子結(jié)點的值，放入緩沖區(qū)中，如果不是，則繼續(xù)找，如此重復(fù)，直到緩沖區(qū)滿了，就寫入到解壓文件中，再循環(huán)以上過程，直到處理完所有數(shù)據(jù)。B.緩沖輸入輸出和壓縮時采用1M二級緩沖相同，如果的壓縮時也采用此技術(shù)，也會有很大的速度優(yōu)化，當(dāng)然程序也變得更加復(fù)雜。四 用戶

9、使用說明1.運行huffman.exe程序，出現(xiàn)下面的界面2.選擇相應(yīng)的功能，輸入正確文件路徑，對文件進行壓縮、解壓。五 設(shè)計心得體會通過這次課題實驗的程序?qū)嵺`，我實在獲益匪淺！數(shù)據(jù)結(jié)構(gòu)是本學(xué)期開展的一門學(xué)科，學(xué)習(xí)好這門學(xué)科是非常重要的，在以后的程序設(shè)計方面這門學(xué)科能給我們很大的幫助。同時，學(xué)習(xí)這門學(xué)科也是艱辛的，因為它比較難懂，這不僅需要我們要發(fā)揮我們的聰明才志，還需要我們在不斷的實踐中領(lǐng)悟。六 附錄程序清單在此，給出huffman.exe的程序清單。#include#include#include#includeusing namespace std;struct HTNode char

10、data; /節(jié)點數(shù)據(jù) int weight; /權(quán)值 int parent; /父親 int leftchild; /左孩子 int rightchild; /右孩子;typedef char* Code;HTNode *ht;Code *hcd;int maplist256; /建立字符與哈夫曼編碼的映射int nodenum=0; /哈夫曼樹結(jié)點數(shù)int rearnum=0; /哈夫曼編碼尾補碼int textlen=0; /需壓縮的文件長度int codelen=0; /壓縮后的文件的哈夫曼編碼總長度int const bufferlen=1024; /設(shè)置讀取緩沖區(qū)長度int cle

11、an(); /清空節(jié)點及編碼指針內(nèi)容void dtobin(int num,int bin8); /十進制變換成二進制void HTCreate(HTNode ht,int n); /建立哈夫曼樹void HCCreat(HTNode ht,Code hcd,int n); /提取哈夫曼編碼void Write *tmp); /寫入文件unsigned char ConvertBinary(char *tmp);/變換二進制文件void Convert hcd,string );/壓縮并解壓文件bool InitFrom );/初始化文件void Decompression ); /解壓文件s

12、tring Compression(string );/壓縮文件string Decompression(string ); /解壓文件子函數(shù)/十進制轉(zhuǎn)二進制函數(shù)/int clean() delete ht;delete hcd;return 1;void dtobin(int num,int bin8) int i=0; for(i=0;i0) bin8-1-i=num%2; num=num/2; i+; /壓縮和寫入文件/void Convert hcd,string ) fstream in(),ios:in|ios:binary);fstream out(),ios:out|ios:b

13、inary);if(!infile) coutopen !endl;if(!outfile) coutcreat !endl;/unsigned char ch; /寫入哈夫曼樹/ ch=nodenum; out(&ch,1); /寫入結(jié)點數(shù) ch=8; out(&ch,1); /寫入補位數(shù)(預(yù)寫入) codelen=0; out(char *)&codelen,4); /寫入壓縮后的文件的哈夫曼編碼總長度(預(yù)寫入) int h=0; for(h=0;hnodenum;h+) out(char*)&hth.data,sizeof(char); out(char*)&hth.weight,siz

14、eof(int); char tmp8; /設(shè)置緩沖區(qū) char outbufferbufferlen; /設(shè)置寫入緩沖區(qū) char *tmpcd; int i=0,j,k,last=0; char inbufferbufferlen; int readlen=0; /in(i,ios:beg);h=0; do in(inbuffer,bufferlen); readlen=in(); tmpcd=hcdmaplist(unsigned char)inbufferi; for(i=0;ireadlen;) for(j=last;j8 & *tmpcd!=0;j+) tmpj=*tmpcd; t

15、mpcd+; if(j=8 & *tmpcd=0) last=0; i+; ch=ConvertBinary(tmp); /cout:(unsigned int)ch ; outbufferh=ch; h+; codelen+; /壓縮文件長度加一if(h=bufferlen) out(outbuffer,bufferlen); h=0; if(ireadlen) tmpcd=hcdmaplist(unsigned char)inbufferi; elsei=0;break; else if(j8 & *tmpcd=0) last=j; i+; if(ireadlen) tmpcd=hcdma

16、plist(unsigned char)inbufferi; else i=0; break; /繼續(xù)循換/ else if(j=8 & *tmpcd!=0) last=0;/Write); ch=ConvertBinary(tmp); outbufferh=ch; h+; codelen+; /壓縮文件長度加一if(h=bufferlen) out(outbuffer,bufferlen); h=0; while(readlen=bufferlen);if(j=8 & readlenbufferlen) out(outbuffer,h); else if(j8 & readlenbuffer

17、len) for(k=j;k8;k+) tmpk=0; ch=ConvertBinary(tmp); outbufferh=ch; h+; out(outbuffer,h); codelen+; /壓縮文件長度加一 coutendl; ch=8-j; rearnum=8-j; out(1,ios:beg); out(&ch,1); /寫入真正的補位數(shù) out(2,ios:beg);out(char*)&codelen,4); /寫入真正的壓縮后的文件的哈夫曼編碼總長度長度 out(); in();/構(gòu)造哈夫曼樹/void HTCreate(HTNode ht,int n) int i,k,ln

18、ode,rnode; int min1,min2; for(i=0;i2*n-1;i+) hti.parent=hti.rightchild=hti.leftchild=-1; for(i=n;i2*n-1;i+) min1=min2=; lnode=rnode=-1; for(k=0;k=i-1;k+) if(htk.parent=-1) if(htk.weightmin1) min2=min1; min1=htk.weight; rnode=lnode; lnode=k; else if(htk.weightmin2) min2=htk.weight; rnode=k; htlnode.p

19、arent=i; htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.leftchild=lnode; hti.rightchild=rnode; /構(gòu)造哈夫曼編碼/void HCCreat(HTNode ht,Code hcd,int n) int i,p,c; Code hc; hc=new charn; int start,tmplen; for(i=0;in;i+) tmplen=0; start=n-1; hcstart=0; c=i; p=hti.parent; while(p!=-1) if(htp.le

20、ftchild=c) /是左孩子結(jié)點 hc-start=0; tmplen+; else hc-start=1; tmplen+; c=p; p=htp.parent; hcdi=new charn-start; strcpy(hcdi,&hcstart); delete hc;void Write *tmp) int i; for(i=0;i8;i+) couttmpi; cout ; tmp=;unsigned char ConvertBinary(char *tmp) char ch=0; int i; for(i=0;i8;i+) ch=(unsigned char)pow(2.0,8

21、-i-1)*(tmpi-48)+ch; return ch;/打開文件/bool InitFrom ) fstream in(),ios:binary|ios:in); if(!infile)couterror!endl;return 0; int table256; int i,j; int len=0,num=0; unsigned char ch; for(i=0;i256;i+) tablei=0;maplisti=-1; int readlen=0; char bufferbufferlen; /設(shè)置讀取緩沖區(qū),加快讀取速度 do in(buffer,bufferlen); i=0;

22、 readlen=in(); while(ireadlen) ch=(unsigned char)bufferi; tablech+; len+; i+; while(readlen=bufferlen);for(i=0;i256;i+) if(tablei!=0) num+; ht=new HTNode2*num-1; hcd=new Codenum; for(i=0,j=0;i256;i+) if(tablei!=0) htj.data=i; htj.weight=tablei; maplisti=j; /建立字符與哈夫曼編碼的映射 j+; nodenum=num; textlen=len

23、; in();in(); return 1;/從文件解壓/void Decompression ) /cout.解壓并輸出新文件過程:endl; fstream in(),ios:in|ios:binary); fstream out(),ios:out|ios:binary); coutendl; /讀出哈夫曼樹的數(shù)據(jù)/ int h=0; char bufferbufferlen; /讀入文件的緩沖區(qū) char outbufferbufferlen; /寫入文件的緩沖區(qū) in(buffer,1); nodenum=(unsigned char)*buffer;/哈夫曼樹結(jié)點數(shù) if(node

24、num=0) nodenum=256; in(buffer,1); rearnum=(unsigned char)*buffer; in(char*)&codelen,4); /cout 讀出哈夫曼樹數(shù)據(jù).endl; ht=new HTNode2*nodenum-1; hcd=new Codenodenum; /hcdlen=new intnodenum; for(h=0;hnodenum;h+) in(&hth.data,1); in(char*)&hth.weight,4); /構(gòu)走哈夫曼樹/ HTCreate(ht,nodenum); /構(gòu)造哈夫曼編碼/ HCCreat(ht,hcd,n

25、odenum); /解壓并輸出解壓文件/ char *buffertmp=new char; int bin8,j=0,i=0; int coderead=0; /記錄以度的長度,用于判斷何時達到文件最后一字節(jié)(用codelen比較) int readlen=0; int child=0; int last=2*nodenum-2; /解壓時記錄上次指示器的位置 child=last; unsigned char outp; h=0; do in(buffer,bufferlen); readlen=in(); for(j=0;jreadlen;j+) coderead+; outp=buff

26、erj; dtobin(outp,bin); if(coderead=codelen) /達到文件尾 for(i=0;i=8-rearnum;i+) if(htchild.leftchild=-1 & htchild.rightchild=-1) /couthtchild.data; outbufferh=htchild.data; h+;if(h=bufferlen) out(outbuffer,bufferlen);h=0; last=2*nodenum-2; if(i=8-rearnum)if(h!=0) out(outbuffer,h);child=last;break;else i-

27、; else if(i!=8) if(bini=0) last=htchild.leftchild; else if(bini=1) last=htchild.rightchild; child=last; else /沒達到文件尾 for(i=0;i=8;i+) if(htchild.leftchild=-1 & htchild.rightchild=-1) /couthtchild.data; outbufferh=htchild.data; h+;if(h=bufferlen) out(outbuffer,bufferlen); h=0; last=2*nodenum-2;if(i=8)

28、child=last;break;else i-; else if(i!=8) if(bini=0) last=htchild.leftchild; else if(bini=1) last=htchild.rightchild; child=last; while(readlen=bufferlen); /coutjendl; in(); out();string Compression(string )int i;for(i=0;i();i+)if(i=) i=/;string ;.rax;InitFrom); /從文件中初始化哈夫曼樹HTCreate(ht,nodenum); /構(gòu)造哈夫

29、曼樹 HCCreat(ht,hcd,nodenum); /構(gòu)造哈夫曼編碼 Convert); /壓縮并寫入文件 clean();return ;string Decompression(string ) int i;for(i=0;i0;i-) (0,(i,1);if(i!=0) (0,i)+_+.+;else (0,()-4)+_;Decompression);clean();return ;int main()cout緩沖區(qū)長度:bufferlenBytes.endlendl;coutt*n; coutt* *n; coutt* 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 *n; coutt* 基于哈夫曼的文件壓縮

30、解壓程序 *n; coutt* *n; coutt*n; string ;string ;char usage;docoutendl;cout(1)壓縮Cendl;cout(2)解壓Dendl;cout(3)退出Q endl;coutendl;coutusage;if(usage=C | usage=c)cout;cout壓縮文件開始.; ();cout壓縮文件完畢,壓縮后文件的路徑是:endlendl;else if(usage=D | usage=d)cout;cout解壓文件開始.; ();cout解壓文件完畢,解壓后文件的路徑是:endlendl;else if(usage=Q | u

31、sage=q) return 0;while(1); return 0;#include#include#include#includeusing namespace std;struct HTNode char data; /節(jié)點數(shù)據(jù) int weight; /權(quán)值 int parent; /父親 int leftchild; /左孩子 int rightchild; /右孩子;typedef char* Code;HTNode *ht;Code *hcd;int maplist256; /建立字符與哈夫曼編碼的映射int nodenum=0; /哈夫曼樹結(jié)點數(shù)int rearnum=0;

32、/哈夫曼編碼尾補碼int textlen=0; /需壓縮的文件長度int codelen=0; /壓縮后的文件的哈夫曼編碼總長度int const bufferlen=1024; /設(shè)置讀取緩沖區(qū)長度int clean(); /清空節(jié)點及編碼指針內(nèi)容void dtobin(int num,int bin8); /十進制變換成二進制void HTCreate(HTNode ht,int n); /建立哈夫曼樹void HCCreat(HTNode ht,Code hcd,int n); /提取哈夫曼編碼void Write *tmp); /寫入文件unsigned char ConvertBin

33、ary(char *tmp);/變換二進制文件void Convert hcd,string );/壓縮并解壓文件bool InitFrom );/初始化文件void Decompression ); /解壓文件string Compression(string );/壓縮文件string Decompression(string ); /解壓文件子函數(shù)/十進制轉(zhuǎn)二進制函數(shù)/int clean() delete ht;delete hcd;return 1;void dtobin(int num,int bin8) int i=0; for(i=0;i0) bin8-1-i=num%2; nu

34、m=num/2; i+; /壓縮和寫入文件/void Convert hcd,string ) / fstream in(),ios:in|ios:binary);fstream out(),ios:out|ios:binary);if(!infile) coutopen !endl;if(!outfile) coutcreat !endl; /unsigned char ch; /寫入哈夫曼樹/ ch=nodenum; out(&ch,1); /寫入結(jié)點數(shù) ch=8; out(&ch,1); /寫入補位數(shù)(預(yù)寫入) codelen=0; out(char *)&codelen,4); /寫入壓縮后的文件的哈夫曼編碼總長度(預(yù)寫入) int h=0; for(h=0;hnodenum;h+) out(char*)&hth.data,sizeof(char); out(char*)&hth.weight,sizeof(int); char tmp8; /設(shè)置緩沖區(qū) char outbufferbufferlen; /設(shè)置寫入緩沖區(qū) char *tmpcd; int i=0,j,k,last=0; char inbufferbufferlen; int readlen