2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題(含答案詳解+作文范文)_第1頁(yè)
已閱讀1頁(yè),還剩24頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(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ì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論