數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)報(bào)告

《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)報(bào)告學(xué)號(hào)：2010100****班級(jí)序號(hào)：114103姓名：劉洋指導(dǎo)教師：陳啟浩成績(jī)：中國(guó)地質(zhì)大學(xué)信息工程學(xué)院空間信息工程系2012年2月課程設(shè)計(jì)報(bào)告一、軟件壓縮/解壓縮軟件Szip（Huffman算法及應(yīng)用）1．需求規(guī)格說明利用哈夫曼編碼對(duì)一個(gè)現(xiàn)有文件進(jìn)行重新編碼行成新的文件，可以減小文件大小，減少存儲(chǔ)空間，這也就是壓縮。在文件使用時(shí)，再對(duì)壓縮文件進(jìn)行解壓縮，也就是譯碼，復(fù)原原有文件。即求解的問題是，根據(jù)哈夫曼編碼的知識(shí)寫一個(gè)壓縮/解壓縮軟件。2．總體分析與設(shè)計(jì)（1）設(shè)計(jì)思想：主要的算法思想及其存儲(chǔ)結(jié)構(gòu)：采用課程實(shí)習(xí)已經(jīng)寫過的huffman編碼程序?qū)σ獕嚎s文件中字符進(jìn)行讀取，統(tǒng)計(jì)字符出現(xiàn)頻率，并進(jìn)行字符編碼。將編碼后的字符以鏈表形式存儲(chǔ)其所編的huffman碼，并以該字符建立鏈表的字典索引。重新讀取待壓縮文件并根據(jù)鏈表搜索其huffman編碼按順序?qū)懭胍粫捍嫖募iuyang1.txt中保存。根據(jù)liuyang1.txt中的編碼進(jìn)行8個(gè)數(shù)字一壓縮寫入壓縮文件中。（壓縮文件頭部首先要寫入字典編碼等重要信息，以方便解碼需求）。解碼時(shí)首先以二進(jìn)制形式讀取壓縮文件中存入的字典編碼信息，根據(jù)其字符頻率信息重新構(gòu)造huffman樹，與此同時(shí)將剩余壓縮文件中每個(gè)字符解壓縮成8個(gè)字符（與liuyang1.txt對(duì)應(yīng)）寫入暫存的文件liuyang3.txt中。再依次據(jù)暫存文件liuyang3.txt讀取huffman編碼數(shù)字，根據(jù)建立的huffman搜索樹進(jìn)行解碼還原成帶壓縮文件。（2）設(shè)計(jì)表示：具體的壓縮實(shí)例部分代碼：//主程序中voidmain（）//省略其統(tǒng)計(jì)字符出現(xiàn)頻率的代碼cout<<"開始構(gòu)建huffman樹并壓縮……"<<" ";BinaryTree<Hz>d;//Hz*c=newHz[i+1]; Hz是專門用來存儲(chǔ)字典的類其中只包含私有變量charletter;字符intcount;字符統(tǒng)計(jì)頻率這倆個(gè)信息。及huffman每個(gè)節(jié)點(diǎn)均為Hz類型d=HuffmanTree(c,e-1);//構(gòu)建huffman樹的函數(shù)，d為返回的huffman樹SortedChain<BinaryTreeNode<Hz>,char>cc;C=&cc;//定義鏈表用來存儲(chǔ)字典編碼信息co=-1;//變量初始化，用來初始p數(shù)組（p用來記錄當(dāng)前01編碼）d.hfbm(hfleaf,co,true);//huffman樹類的遞歸編碼程序，壓縮、解壓縮重復(fù)利用此函數(shù)編碼//該函數(shù)最后一個(gè)參數(shù)true表示是壓縮時(shí)用，false表示是在解壓時(shí)用ofstreamofile("liuyang1.txt",ios_base::out|ios_base::binary);//建立暫存文件//……省略部分代碼BinaryTreeNode<Hz>ee;for(into=0;o<i;o++){ //調(diào)用鏈表搜索函數(shù)根據(jù)字典索引將01編碼寫進(jìn)暫存文件中intp=cc.Search(char(a[o]),ee); for(intk=0;k<=ee.i;k++) ofile<<ee.Le[k];}ofile<<'^';//暫存文件中方便標(biāo)記結(jié)束符號(hào) ofile.close();ifstreamiifile("liuyang1.txt",ios_base::in|ios_base::binary);ofstreamoofile(OutputFile.c_str(),ios_base::out|ios_base::binary);iifile.seekg(0,ios_base::end);r=(int(iifile.tellg())-1)%8;oofile<<char(r);//頭文件信息：記錄最后一個(gè)字符中有幾位數(shù)字是真真實(shí)有效的 iifile.seekg(0,ios_base::beg);oofile<<char(short(e)>>8)<<char(short(e)); //用2個(gè)字符記錄字典鏈表節(jié)點(diǎn)個(gè)數(shù) for(intk=1;k<e;k++)oofile<<c[k].Letter()<<char(c[k]>>8)<<char(c[k]);//在壓縮文件中寫入字典信息//在壓縮文件中通過bitset類寫入編碼并壓縮的字符cout<<"壓縮后文件大小"<<oofile.tellp()<<"byte 壓縮完畢！"<<endl;oofile.close();iifile.close();//釋放動(dòng)態(tài)存儲(chǔ)空間壓縮結(jié)束！解壓縮流程于此類似（3）詳細(xì)設(shè)計(jì)表示：//具體壓縮寫入的程序：while(iifile){ for(r=0;r<8;r++) {iifile.get(ch[r]); if(ch[r]=='^'){ iifile.get(ch[r]); break;}} if(r) { intl=r;if(l<8) ch[l]='\0'; stringstr(ch);bitset<8>cbit(str);unsignedlongintio;io=cbit.to_ulong();oofile<<unsignedchar(io);}}//Huffman編碼函數(shù)（類似前序遍歷的遞歸函數(shù)）template<classT>voidBinaryTree<T>::hfbm(void(*Visit)(BinaryTreeNode<T>*u,intco,boola),BinaryTreeNode<T>*t,intco,boola){ if(t) { Visit(t,co,a); co++; if(t->LeftChild) { p[co]='0'; hfbm(Visit,t->LeftChild,co,a); } if(t->RightChild) { p[co]='1'; hfbm(Visit,t->RightChild,co,a);} }}//具體將字符頻率插入到鏈表的函數(shù)voidhfleaf(BinaryTreeNode<Hz>*u,intco,boola){ if(!u->LeftChild&&!u->RightChild&&co==-1) { u->Le=newchar[co+2]; u->i=++co; p[co]='0'; u->Le[0]=p[0]; if(a) C->Insert(*u); WPL+=u->data*(co+1); }else if(!u->LeftChild&&!u->RightChild) { u->Le=newchar[co+1]; u->i=co; for(intk=0;k<=co;k++) u->Le[k]=p[k]; if(a) C->Insert(*u); WPL+=u->data*(co+1); }}3．編碼最難解決的是將8個(gè)01字符壓縮成8位的字符寫入壓縮文件中，由于所有編碼和未必是8的整數(shù)個(gè)數(shù)，所以同時(shí)還要標(biāo)記最后一個(gè)字符的二進(jìn)制數(shù)字中有幾位是真實(shí)有效的。具體解決是首先包含頭文件#include<bitset>，然后調(diào)用bitset類將01字符串轉(zhuǎn)換為二進(jìn)制與其數(shù)值相等的長(zhǎng)整數(shù)值，即以8位二進(jìn)制數(shù)值為一個(gè)無符號(hào)字符型變量的值，再寫入壓縮文件中：bitset<8>cbit(str);unsignedlongintio=cbit.to_ulong();oofile<<unsignedchar(io);對(duì)于解決標(biāo)記最后一個(gè)字符的真實(shí)有效位數(shù)，可以根據(jù)暫存文件liuyang1.txt的信息算出最后一位的有效位數(shù):r=(int(iifile.tellg())-1)%8;4．程序及算法分析使用說明：在程序運(yùn)行時(shí)有字幕提示一步一步的操作，也可根據(jù)以下示例圖片來操作。程序運(yùn)行結(jié)果如圖所示：程序首先對(duì)ly.txt文件進(jìn)行壓縮生成ly.Haf壓縮文件,再繼續(xù)對(duì)liuyang.txt文件壓縮生成liuyang.Haf壓縮文件；最后再將ly.Haf文件解壓生成ly_text.txt文件與ly.txt文件相同，實(shí)現(xiàn)了文件的無損壓縮和解壓。改進(jìn)設(shè)想及經(jīng)驗(yàn)與體會(huì)：此程序用的是二進(jìn)制流文件的讀入和輸出，且是用win32控制臺(tái)，若要改進(jìn)則應(yīng)改用界面更優(yōu)化的mfc來編寫，同時(shí)改用cfile類來進(jìn)行文件的讀入寫出。時(shí)空復(fù)雜度：對(duì)于空間復(fù)雜度來說，由于壓縮解壓縮都借助了暫存文件來存儲(chǔ)字符，因此在空間上得到了優(yōu)化；但對(duì)于時(shí)間復(fù)雜度來說，由于要多寫進(jìn)去2個(gè)暫存文件中，因此降低了時(shí)間復(fù)雜性。5．小結(jié)經(jīng)驗(yàn)的話是把壓縮的具體流程熟悉了一遍，以及處理輸入壓縮名，更改名字為.Haf結(jié)尾的字符串用法：stringInputFile,OutputFile;cout<<"輸入壓縮文件名（帶后綴）："<<" ";cin>>InputFile;OutputFile.assign(InputFile,0,InputFile.find('.'));OutputFile=OutputFile+".Haf";cout<<"壓縮后文件名為："<<OutputFile<<" ";這段代碼可為第二個(gè)題目做小部分鋪墊。（<五號(hào)宋體>，具體內(nèi)容：經(jīng)驗(yàn)與體會(huì)，或需要改進(jìn)的地方）6．附錄//前面省略的huffman樹的函數(shù)以及結(jié)點(diǎn)Hz類的代碼//類Hz是huffman樹構(gòu)建的節(jié)點(diǎn)數(shù)據(jù)data的類型classHz{public: Hz(){count=0;letter='';} voidAdd(){count++;} charLetter(){returnletter;} booloperator==(charx){if(letter==x)returntrue;returnfalse;} operatorint()const{returncount;} booloperator<=(Hza){returncount<=a.count;} booloperator<(Hza){returncount<a.count;} voidoperator=(intx){count=x;} voidoperator=(charx){letter=x;}private: charletter;//編碼的字符 intcount;//該字符的頻率};//構(gòu)建huffman樹的函數(shù)，參數(shù)數(shù)組為自定義類Hz(含字符和頻率2個(gè)私有數(shù)據(jù))BinaryTree<Hz>HuffmanTree(Hza[],intn)//改為BinaryTree<char>可以，需在該函數(shù)作相應(yīng)修改即可，只是返回一個(gè)存了字符二叉樹，沒有頻率對(duì)應(yīng){//根據(jù)權(quán)重a[1:n]//0:n-1構(gòu)造HuffmanHuffman樹//創(chuàng)建一個(gè)單節(jié)點(diǎn)樹的數(shù)組Huffman<Hz,Hz>*w=newHuffman<Hz,Hz>[n+1];BinaryTree<Hz>z,zero;Hzaz;az='~';for(inti=1;i<=n;i++){ z.MakeTree(a[i],zero,zero);//外部節(jié)點(diǎn) w[i].weight=a[i]; w[i].tree=z;}//把數(shù)組變成一個(gè)最小堆MinHeap<Huffman<Hz,Hz>>H(1);H.Initialize(w,n,n);//將堆中的樹不斷合并Huffman<Hz,Hz>x,y;for(inti=1;i<n;i++){ H.DeleteMin(x); H.DeleteMin(y); z.MakeTree(az,x.tree,y.tree);//內(nèi)部節(jié)點(diǎn) x.weight=int(x.weight)+int(y.weight); x.tree=z; H.Insert(x);}H.DeleteMin(x);//最后的樹H.Deactivate();delete[]w;returnx.tree;}二、灰度圖像壓縮/解壓縮類的實(shí)現(xiàn)（動(dòng)態(tài)規(guī)劃算法的應(yīng)用）1．需求規(guī)格說明針對(duì)提供的256色（8位）位圖數(shù)據(jù)，采用教材上第15章動(dòng)態(tài)規(guī)劃中圖像壓縮算法（圖像分段合并的思想），設(shè)計(jì)一個(gè)類，實(shí)現(xiàn)灰度位圖數(shù)據(jù)的壓縮和解壓過程。完整的灰度圖像類應(yīng)具有以下功能：（1）對(duì)8位位圖數(shù)據(jù)的讀功能，提供ReadBitmap方法。（2）對(duì)8位位圖數(shù)據(jù)的寫功能，提供WriteBitmap方法。（3）灰度圖像壓縮功能，提供Compress方法。（4）灰度圖像解壓功能，提供UnCompress方法。2．總體分析與設(shè)計(jì)（1）設(shè)計(jì)思想：主要的算法思想及其存儲(chǔ)結(jié)構(gòu)：對(duì)待壓縮的文件進(jìn)行讀取，并獲取bmp圖像相應(yīng)的頭文件信息。將文件中圖像色階的信息轉(zhuǎn)為二進(jìn)制表示并寫入暫存的文件bianma1.txt中；讀取暫存的二進(jìn)制信息并初步合并相鄰且位數(shù)相等的數(shù)值信息得到段落l和位數(shù)b數(shù)組的初步信息，再將其帶入課本中動(dòng)態(tài)規(guī)劃學(xué)習(xí)時(shí)所用的縮短表示的二進(jìn)制位數(shù)的代碼中進(jìn)行數(shù)據(jù)優(yōu)化合并，得到最優(yōu)壓縮的段落ll和位數(shù)o數(shù)組的信息；據(jù)新數(shù)組信息重新將bianma1.txt中的圖像二進(jìn)制信息寫入暫存文件bianma2.txt中，此時(shí)已得到壓縮文件后二進(jìn)制的相應(yīng)表示，再根據(jù)之前壓縮的經(jīng)驗(yàn)用bitset類將此二進(jìn)制信息轉(zhuǎn)進(jìn)后綴為.img的壓縮文件中（原圖像頭文件的信息已寫入此壓縮文件，且隨之更改頭文件BITMAPINFOHEADER類中的biSizeImage數(shù)值為當(dāng)前壓縮文件中圖像信息的實(shí)際大?。?。解壓縮部分是獲取壓縮文件的頭信息并根據(jù)biSizeImage值獲取壓縮圖像色階數(shù)據(jù)以二進(jìn)制數(shù)值寫入暫存文件jiema1.txt中，再將biSizeImage還原至原信息數(shù)值，將整個(gè)頭文件寫入解壓縮后的bmp圖像頭信息中，再根據(jù)jiema1.txt中得到的二進(jìn)制分段信息還原至原數(shù)值二進(jìn)制信息并寫回到解壓縮后的bmp圖像數(shù)據(jù)信息中，完成解壓縮。此處主要是采用定義數(shù)組指針，動(dòng)態(tài)分配內(nèi)存空間來存儲(chǔ)分段信息的。（2）設(shè)計(jì)表示：//動(dòng)態(tài)規(guī)劃合并函數(shù)程序intL=256,header=11;intli,pp;//全局變量及常量定義unsignedint*s,*l,*ll,*b;int*kay;//動(dòng)態(tài)規(guī)劃分類函數(shù)intS(inti){ if(i==0)return0; if(s[i]>0)returns[i]; intlsum=l[i],bmax=b[i]; s[i]=S(i-1)+lsum*bmax; kay[i]=1; for(intk=2;k<=i&&lsum+int(l[i-k+1])<=L;k++){ lsum+=int(l[i-k+1]); if(bmax<int(b[i-k+1]))bmax=int(b[i-k+1]); intt=S(i-k); if(int(s[i])>t+lsum*bmax){ s[i]=intunsigned(t+lsum*bmax); kay[i]=k;} } s[i]+=intunsigned(header); returns[i];}//重新標(biāo)記新段落信息voidTraceback(intkay[],intn){ if(n==0)return;Traceback(kay,n-kay[n]); ll[li]=n-kay[n]+1-pp; li++; pp=n-kay[n]+1;}（3）詳細(xì)設(shè)計(jì)表示：主要算法的框架：fp_s=fopen(fname_s,"rb");//fname_s為定義圖像名稱的字符指針，部分信息省略fp_t=fopen(fname_t,"wb");//fname_t為定義壓縮文件名稱的字符指針，部分信息省略fseek(fp_s,0,SEEK_SET);fread(&aa,sizeof(BITMAPFILEHEADER),1,fp_s);fseek(fp_s,14,SEEK_SET);fread(&a,sizeof(BITMAPINFOHEADER),1,fp_s);DataSizePerLine=(a.biWidth*a.biBitCount+31)/8;//一個(gè)掃描行所占的字節(jié)數(shù)DataSizePerLine=DataSizePerLine/4*4;//字節(jié)數(shù)必須是4的倍數(shù)//位圖數(shù)據(jù)的大小(不壓縮情況下):DataSize=DataSizePerLine*a.biHeight;//動(dòng)態(tài)分配空間?。?！image_s=newunsignedchar[DataSize];if(image_s==NULL){printf("mallocimages_serror\n");return-1;}//段落信息等的數(shù)組動(dòng)態(tài)分配空間s=newunsignedint[a.biWidth*a.biHeight+1];kay=newint[a.biWidth*a.biHeight+1];l=newunsignedint[a.biWidth*a.biHeight+1];b=newunsignedint[a.biWidth*a.biHeight+1];//部分省略fseek(fp_s,aa.bfOffBits,SEEK_SET);ofstreamofile("bianma1.txt",ios_base::binary);//圖像原始的二進(jìn)制信息ofstreamomfile("shuju1.txt",ios_base::binary);//圖像原始的十進(jìn)制信息（只是預(yù)覽方便檢查，對(duì)壓縮沒有用處）fread(image_s,sizeof(unsignedchar),DataSize,fp_s);for(y=0;y!=a.biHeight;++y){for(x=0;x!=a.biWidth;++x){pixel=*(image_s+(DataSizePerLine*y+x));omfile<<unsignedlong(pixel)<<'';unsignedlongk=unsignedlong(pixel);bitset<8>obit(k);ofile<<obit;//圖像色階的信息轉(zhuǎn)為二進(jìn)制表示并寫入} }//部分省略ofstreamoomfile("shuju2.txt",ios_base::binary);//圖像二進(jìn)制信息的出合并段落l與位數(shù)b數(shù)組的信息（只是預(yù)覽方便檢查，對(duì)壓縮沒有用處）ifstreamifile("bianma1.txt",ios_base::binary);//原圖像信息的初步分段代碼ll=newunsignedint[a.biWidth*a.biHeight+1];//新段數(shù)組的動(dòng)態(tài)分配空間與初始化b[0]=ll[0]=0;for(intr=0;r<k+1;r++) s[r]=0;cout<<"動(dòng)態(tài)規(guī)劃預(yù)計(jì)壓縮后的理想大?。?<<S(k)<<endl;//調(diào)用動(dòng)態(tài)規(guī)劃的優(yōu)化分段的函數(shù)li=0;pp=1;Traceback(kay,k);//記錄新段落信息//將新段落ll[]和o[]數(shù)據(jù)進(jìn)行統(tǒng)計(jì)的代碼ofstreamoofile("bianma2.txt",ios_base::binary);//將要壓縮的圖像二進(jìn)制信息通過動(dòng)態(tài)規(guī)劃的合并后的二進(jìn)制信息ifile.clear();//重讀取bianma1.txt中得圖像二進(jìn)制信息ifile.seekg(0,ios_base::beg);intzl,zb,zd=0;for(ra=1;ra<=li;ra++){ unsignedlongk1=unsignedlong(ll[ra]-1); unsignedlongk2=unsignedlong(o[ra]-1); bitset<8>obit1(k1); bitset<3>obit2(k2); oofile<<obit1<<obit2; for(zl=0;zl<ll[ra];zl++) { for(intqr=0;qr<8;qr++)ifile.get(ach[qr]);for(zb=8-o[ra];zb<8;zb++) oofile<<ach[zb];}}//開始將bianma2.txt中壓縮信息寫入壓縮文件中ifstreamiifile("bianma2.txt",ios_base::binary);fseek(fp_t,0,SEEK_SET);fwrite(&aa,sizeof(BITMAPFILEHEADER),1,fp_t);//部分省略fseek(fp_t,aa.bfOffBits,SEEK_SET);for(r=0;r<8;r++) ch[r]=0;while(iifile){ for(r=0;r<8;r++){ iifile.get(ch[r]);if(ch[r]=='^'){iifile.get(ch[r]); break;}}if(r) { intl=r; if(l<8) ch[l]='\0'; stringstr(ch); bitset<8>cbit(str); unsignedlongintio; io=cbit.to_ulong(); cc=unsignedchar(io); fwrite(&cc,sizeof(unsignedchar),1,fp_t);}}//解壓縮部分類似3．編碼 通過File類獲取信息時(shí)要不停調(diào)用fseek()函數(shù)來標(biāo)記位置，當(dāng)要統(tǒng)計(jì)壓縮文件結(jié)尾的數(shù)值時(shí)，同時(shí)要在解壓縮時(shí)計(jì)算出壓縮文件中最后一個(gè)字符的有效位數(shù)比較復(fù)雜。統(tǒng)計(jì)壓縮文件結(jié)尾的大小是通過在壓縮文件中更改了頭文件biSizeImage數(shù)值，再在解壓縮時(shí)讀取后并還原給解壓縮文件，而統(tǒng)計(jì)有效位數(shù)則是通過邊還原二進(jìn)制信息邊記錄動(dòng)態(tài)規(guī)劃后信息總數(shù)值Z值來計(jì)算出來最后一個(gè)字符的有效位數(shù)。4．程序及算法分析使用說明：在程序運(yùn)行時(shí)有字幕提示一步一步的操作，也可根據(jù)以下示例圖片來操作。程序運(yùn)行結(jié)果如下圖所示：程序首先對(duì)text8.bmp文件進(jìn)行壓縮生成t8.img壓縮文件,再繼續(xù)對(duì)text0.bmp文件壓縮生成t0.img壓縮文件；最后再將t8.img文件解壓生成t_8.bmp文件與text8.bmp文件相同，實(shí)現(xiàn)了文件的無損壓縮和解壓。 text8.bmp t_8.bmp改進(jìn)設(shè)想：此程序由于是用數(shù)組來進(jìn)行大量數(shù)據(jù)的存儲(chǔ)，同時(shí)又用了多次遞歸棧調(diào)用函數(shù)致使空間內(nèi)存不足，過大的圖像會(huì)由于遞歸棧