-.z.-----總結(jié)資料**師范大學(xué)"數(shù)據(jù)構(gòu)造"課程設(shè)計報告**：**：學(xué)院：計算機(jī)科學(xué)與技術(shù)學(xué)院題目：排序算法比擬與壓縮軟件的實(shí)現(xiàn)指導(dǎo)教師：二〇一四年九月一日目錄必做題3一、設(shè)計內(nèi)容3二、設(shè)計思想描述31希爾排序32快速排序33堆排序44二路歸并排序7三、程序構(gòu)造81類設(shè)計82主程序設(shè)計83流程圖9四、系統(tǒng)環(huán)境與程序測試案例9五、設(shè)計中遇到的問題及解決方案121測時間的函數(shù)不準(zhǔn)確12其他測試運(yùn)行時間的方式：132什么是"真隨機(jī)〞，什么是"偽隨機(jī)〞？143如何根據(jù)文檔構(gòu)造圖生成目錄14六、參考文獻(xiàn)15選做題15一、設(shè)計內(nèi)容15二、設(shè)計思想描述151Huffman樹與Huffman編碼152Huffman算法的思想153現(xiàn)有的壓縮軟件及其壓縮比16三、程序構(gòu)造171類設(shè)計172主程序設(shè)計183流程圖20四、系統(tǒng)環(huán)境與程序測試案例20五、設(shè)計中遇到的問題及解決方案23六、收獲與體會24七、參考文獻(xiàn)24必做題設(shè)計內(nèi)容編程實(shí)現(xiàn)希爾、快速、堆排序、歸并排序算法。要求隨機(jī)產(chǎn)生10000個數(shù)據(jù)存入磁盤文件，然后讀入數(shù)據(jù)文件，分別采用不同的排序方法進(jìn)展排序，并將結(jié)果存入文件中。設(shè)計思想描述1希爾排序希爾排序是對直接插入排序的改良。根本思想是先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分組，所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進(jìn)展直接插人排序；然后，取第二個增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)展直接插入排序?yàn)橹埂Ｔ摲椒▽?shí)質(zhì)上是一種分組插入方法。舉例數(shù)據(jù)序列為〔12，5，9，20，6，31，24〕，對該數(shù)據(jù)序列進(jìn)展希爾排序：12125 9 20 6 3124125 9206 312456 9122024 31初始鍵值序列第一趟排序結(jié)果〔d1=3〕〕第二趟排序結(jié)果〔d2=1〕〕具體代碼見Sort代碼.t*t！2快速排序根本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩局部，其中一局部的所有數(shù)據(jù)都比另外一局部的所有數(shù)據(jù)都要小，然后再按此方法對這兩局部數(shù)據(jù)分別進(jìn)展快速排序，整個排序過程可以遞歸進(jìn)展，以此到達(dá)整個數(shù)據(jù)變成有序序列。舉例數(shù)據(jù)序列為〔12，5，9，20，6，31，24〕，對該數(shù)據(jù)序列進(jìn)展快速排序：一次劃分12125 9 20 6 31 24125 9 20 6 31 24125 9 20 6 31 2465 9 20 1231 2465 9 20 1231 2465 9 20 1231 2465 9 12 2031 24對軸值兩側(cè)分別進(jìn)展快速排序665 965 9569 592031 242031 2431 24242431 3堆排序堆排序〔Heapsort〕是指利用堆這種數(shù)據(jù)構(gòu)造所設(shè)計的一種排序算法。堆是一個近似完全二叉樹的構(gòu)造，并同時滿足堆性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于〔或者大于〕它的父結(jié)點(diǎn)。舉例數(shù)據(jù)序列為〔12，5，9，20，6，31，24〕，對該數(shù)據(jù)序列進(jìn)展堆排序：初始：512初始：512924206311調(diào)整成小根堆659242012312525與24換624952012313調(diào)整成小根堆126952024311231195202465調(diào)整成小根堆1293152024646與31換121224195203167調(diào)整成小根堆2093152412669與24換202024195123169調(diào)整成小根堆24931524206812與24換24319512206820與31換10調(diào)整成小根堆31241124和31換951220631241212排序結(jié)果9512206244二路歸并排序?qū)蓚€按值有序序列合并成一個按值有序序列，則稱之為二路歸并排序?！?〕歸并子算法：把位置相鄰的兩個按值有序序列合并成一個按值有序序列。voidMerge(intr[],intr1[],ints,intm,intt); //一次歸并算法〔2〕一趟歸并掃描子算法：將參加排序的序列分成假設(shè)干個長度為t的，且各自按值有序的子序列，然后屢次調(diào)用歸并子算法merge將所有兩兩相鄰成對的子序列合并成假設(shè)干個長度為2t的，且各自按值有序的子序列。假設(shè)*一趟歸并掃描到最后，剩下的元素個數(shù)缺乏兩個子序列的長度時：?假設(shè)剩下的元素個數(shù)大于一個子序列的長度t時，則再調(diào)用一次歸并子算法merge將剩下的兩個不等長的子序列合并成一個有序子序列?假設(shè)剩下的元素個數(shù)小于或者等于一個子序列的長度t時，只須將剩下的元素依次復(fù)制到前一個子序列后面。voidMergePass(intr[],intr1[],intn,inth); //一趟歸并排序算法〔3〕二路歸并排序算法：將參加排序的初始序列分成長度為1的子序列使用MergePass函數(shù)進(jìn)展第一趟排序，得到n/2個長度為2的各自有序的子序列〔假設(shè)n為奇數(shù)，還會存在一個最后元素的子序列〕，再一次調(diào)用mergePass函數(shù)進(jìn)展第二趟排序，得到n/4個長度為4的各自有序的子序列，第i趟排序就是兩兩歸并長度為2^(i-1)的子序列得到n/(2^i)長度為2^i的子序列，直到最后只剩一個長度為n的子序列。由此看出，一共需要log2n趟排序，每一趟排序的時間復(fù)雜度是O(n)。voidMergeSort1(intr[],intr1[],intn); //歸并排序非遞歸算法舉例數(shù)據(jù)序列為〔12，5，9，20，6，31，24〕，對該數(shù)據(jù)序列進(jìn)展堆排序：1212592063124512920631245912206243156912202431程序構(gòu)造1類設(shè)計本程序中只含有一個類，即測執(zhí)行時間的類CTimer：classCTimer //測執(zhí)行時間的類{public: CTimer() { QueryPerformanceFrequency(&m_Frequency); Start(); } voidStart() { QueryPerformanceCounter(&m_StartCount); } doubleEnd() { LARGE_INTEGERCurrentCount; QueryPerformanceCounter(&CurrentCount); returndouble(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart; } voidShowNow() { LARGE_INTEGERCurrentCount; QueryPerformanceCounter(&CurrentCount); cout<<"TimerCountis:"<<double(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart<<endl; }private: LARGE_INTEGERm_Frequency; LARGE_INTEGERm_StartCount;};2主程序設(shè)計Sort.h文件中包含所有排序算法，具體代碼見Sort.h文件。test.cpp文件中包含產(chǎn)生隨機(jī)數(shù)，讀寫文件，main函數(shù)和菜單控制程序。函數(shù)聲明如下：intMenu();voidMainMenuCtrl();voidWriteFile(intn);voidSaveFile(intr[],intn,charfilename[]);voidReadFile(intr[],intn);voidPrint(intr[],intn);測試時間的代碼如下：CTimert;t.Start();ShellSort(r,n); //希爾排序cout<<"希爾排序執(zhí)行時間為:"<<t.End()<<"s"<<endl;3流程圖菜單菜單產(chǎn)生隨機(jī)數(shù)并寫入文件讀文件希爾排序快速排序堆排序歸并排序?qū)⑴判蚪Y(jié)果寫入文件開場完畢系統(tǒng)環(huán)境與程序測試案例硬件環(huán)境截圖如下：軟件環(huán)境：MicrosoftVisualC++6.0110000個隨機(jī)數(shù)排序220000個隨機(jī)數(shù)排序3100000個隨機(jī)數(shù)排序測試結(jié)果數(shù)據(jù)分析：時間復(fù)雜度10000個數(shù)據(jù)20000個數(shù)據(jù)100000個數(shù)據(jù)希爾排序O(n2)0.00276598秒0.0060197秒0.0395745秒快速排序O(n)0.00172446秒0.00374468秒0.021415秒堆排序O(n)0.00263925秒0.00568505秒0.0337188秒非遞歸的歸并排序O(n)0.00174817秒0.00374692秒0.0208593秒遞歸的歸并排序O(n)0.00266666秒0.00581711秒0.0313498秒表1、各種排序執(zhí)行時間比照表圖1、各種排序執(zhí)行時間比照圖由上圖得，快速排序和非遞歸的歸并排序的排序效率高，其他3種排序速度較慢。設(shè)計中遇到的問題及解決方案1測時間的函數(shù)不準(zhǔn)確不準(zhǔn)確的函數(shù)如下：clock_tstart,finish;//定義開場，完畢時間doubleduration; //持續(xù)時間//測量一個事件持續(xù)的時間start=clock();ShellSort(r,n); //希爾排序finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;//CLK_TCK毫秒CLOCKS_PER_SEC秒cout<<"希爾排序執(zhí)行時間為:"<<duration<<"ms"<<endl;截圖如下：分析：使用clock_tclock()得到的是CPU時間，準(zhǔn)確到1/CLOCKS_PER_SEC秒，但實(shí)際上會有誤差。clock()函數(shù)clock()定義于time.h中，clock()返回從程序運(yùn)行時刻開場的時鐘周期數(shù)，CLOCKS_PER_SEC定義了每秒鐘包含多少了時鐘單元數(shù)。所以得到的時間差其實(shí)是從時鐘周期數(shù)轉(zhuǎn)換過來的。CPU執(zhí)行時間=程序所含時鐘周期數(shù)×?xí)r鐘周期程序總時鐘周期數(shù)=程序所含指令條數(shù)=此時的CPI是該機(jī)器指令集中的所有指令執(zhí)行所用的平均時鐘周期數(shù)，是一個平均數(shù)，即可近似的認(rèn)為三次排序時的CPI一樣。時鐘周期即CPU主頻的倒數(shù)，為一個定值。所以三次排序下此條件一樣。所以得到如下結(jié)論：當(dāng)程序所含的指令條數(shù)越多時，此種方法測到的時鐘周期數(shù)越多，所反映的時間越長，造成了實(shí)驗(yàn)結(jié)果的不準(zhǔn)確。其他測試運(yùn)行時間的方式：〔1〕GetTickCount()函數(shù)：GetTickCount記錄了從系統(tǒng)啟動時經(jīng)過的時間，準(zhǔn)確到毫秒。在windows下實(shí)現(xiàn)(毫秒級)：注意要添加頭文件<windows.h>。DWORDdwStart=GetTickCount(); //取windows啟動到現(xiàn)在的流逝時間(毫秒)Run_Your_Func(...);//運(yùn)行你的函數(shù)DWORDdwUsed=GetTickCount()-dwStart; //計算該函數(shù)所消耗的時間〔2〕對于一般的實(shí)時控制，使用GetTickCount()函數(shù)就可以滿足精度要求，但要進(jìn)一步提高計時精度，就要采用QueryPerformanceFrequency()函數(shù)和QueryPerformanceCounter()函數(shù)。這兩個函數(shù)是VC提供的僅供Windows9*使用的高精度時間函數(shù)，并要求計算機(jī)從硬件上支持高精度計時器。CTimer類如下：classCTimer //測執(zhí)行時間的類{public: CTimer() { QueryPerformanceFrequency(&m_Frequency); Start(); } voidStart() { QueryPerformanceCounter(&m_StartCount); } doubleEnd() { LARGE_INTEGERCurrentCount; QueryPerformanceCounter(&CurrentCount); returndouble(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart; } voidShowNow() { LARGE_INTEGERCurrentCount; QueryPerformanceCounter(&CurrentCount); cout<<"TimerCountis:"<<double(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart<<endl; }private: LARGE_INTEGERm_Frequency; LARGE_INTEGERm_StartCount;};〔3〕寫一個測試執(zhí)行時間的宏#include"window.h"#defineBEGIN_RECORD\{\long____temp_begin_time___;\____temp_begin_time___=::GetTickCount();#defineEND_RECORD(dtime)\dtime=::GetTickCount()-____temp_begin_time___;\}用法:longtim;BEGIN_RECORD被測函數(shù)；END_RECORD(tim); //tim就是所求的時間差！2什么是"真隨機(jī)〞，什么是"偽隨機(jī)〞？(1)、偽隨機(jī)數(shù)：一方面它是可以預(yù)先確定的，并且是可以重復(fù)地生產(chǎn)和復(fù)制的；一方面它又具有*種隨機(jī)序列的隨機(jī)特性。(2)、真隨機(jī)數(shù)：它是相對于偽隨機(jī)數(shù)而言的，不具有規(guī)律，但計算機(jī)不會產(chǎn)生絕對隨機(jī)的隨機(jī)數(shù)。MicrosoftVC++產(chǎn)生隨機(jī)數(shù)的原理： Srand()和Rand()函數(shù)。它本質(zhì)上是利用線性同余法，y=a*+b(modm)。其中a，b，m都是常數(shù)。因此rand的產(chǎn)生決定于*，*被稱為Seed。Seed需要程序中設(shè)定，一般情況下取系統(tǒng)時間作為種子。它產(chǎn)生的隨機(jī)數(shù)之間的相關(guān)性很小，取值范圍是0—32767〔int〕，即雙字節(jié)〔16位數(shù)〕，假設(shè)用unsignedint雙字節(jié)是65535，四字節(jié)是4294967295，一般可以滿足要求。一樣種子下產(chǎn)生的隨機(jī)尋列是一樣的。3如何根據(jù)文檔構(gòu)造圖生成目錄 電子版文檔點(diǎn)擊"視圖〞→"文檔構(gòu)造圖〞編成目錄，點(diǎn)擊可快速，且目錄隨時能夠看到；紙質(zhì)版文檔點(diǎn)擊"插入〞→"引用〞→"索引和目錄〞。二者前提都要點(diǎn)擊"視圖〞→"大綱〞，編輯標(biāo)題級別。參考文獻(xiàn)[1]DoubleLi——c++計算代碼執(zhí)行時間的方法〔毫秒級〕：.blogs./lidabo/archive/2013/01/08/2850418.html[2]aaronalan的專欄——GetTickCount()用法：[3]許明吉博客——GetTickCount()函數(shù)的作用和用法.blogs./j*soft/archive/2011/10/17/2215366.html選做題設(shè)計內(nèi)容設(shè)有一個文本文件A〔可以是C源程序〕，統(tǒng)計該文件中各字符的頻率，對各字符進(jìn)展Huffman編碼，將該文件翻譯成Huffman編碼文件B，再將Huffman編碼文件譯碼成文件C，并對文件A與C進(jìn)展比擬。設(shè)計思想描述1Huffman編碼Huffman樹是在葉子結(jié)點(diǎn)集合確定的前提下，所有可能的二叉樹形態(tài)中樹的帶權(quán)路徑長度最小的二叉樹。當(dāng)Huffman樹應(yīng)用于信息編碼領(lǐng)域時，葉子結(jié)點(diǎn)被用于表示待編碼的符號。將每個結(jié)點(diǎn)的左分支記作0，右分支記作1，則每個葉子結(jié)點(diǎn)的路徑可以用一個0/1串的編碼來表示，稱為Huffman編碼。Huffman編碼是一種可變長編碼方式，編碼的原理是：將使用次數(shù)多的代碼轉(zhuǎn)換成長度較短的代碼，而使用次數(shù)少的可以使用較長的編碼，并且保持編碼的唯一可解性。Huffman算法的最根本的原則是：累計的(字符的統(tǒng)計數(shù)字*字符的編碼長度)為最小，也就是權(quán)值(字符的統(tǒng)計數(shù)字*字符的編碼長度)的和最小。2Huffman算法的思想Huffman算法的思想可以概括為2次掃描。第一次是根據(jù)輸入的字符計算各個字符的頻率，并根據(jù)頻率給每個字符編碼；第二次掃描時對每個輸入的字符進(jìn)展匹配，并把輸入的字符轉(zhuǎn)換為編碼輸出到壓縮文件中。為了得到文本中字符出現(xiàn)的頻率，一般的做法是掃描整個文本進(jìn)展統(tǒng)計，編寫程序統(tǒng)計文本中各個字符出現(xiàn)的頻率。由于一個字符的范圍在[0-255]之間，即共有256個狀態(tài)。所以直接向系統(tǒng)靜態(tài)的申請一個長度為256的整數(shù)數(shù)組，用于存放相應(yīng)的頻率。得到頻率后進(jìn)展哈夫曼編碼，然后將數(shù)據(jù)輸出到文件保存。3現(xiàn)有的壓縮軟件及其壓縮比〔1〕WinZIPZIP是最常見的壓縮文件格式，Windows系統(tǒng)已經(jīng)集成了對ZIP壓縮格式的支持。經(jīng)歷過DOS時代的用戶可能還記得ARJ格式，它根本就是DOS時代的ZIP，直到ZIP格式出現(xiàn)，以更高的壓縮效率取代了ARJ，成為用戶的首選?，F(xiàn)在大多數(shù)操作系統(tǒng)都會集成對ZIP文件的支持，而所有的壓縮軟件也都會提供對ZIP文件的支持，這些足以表達(dá)出ZIP格式的地位。ZIP時代最知名的壓縮軟件就要數(shù)WinZIP了，它幾乎是當(dāng)時每臺電腦都必備的軟件。直到Windows系統(tǒng)開場集成了對ZIP文件的支持，以及后起之秀RAR格式的出現(xiàn)，使得WinZIP不再是則必要，才讓它逐漸淡出了大家的視線。〔2〕WinRARRAR格式的文件壓縮率比ZIP更高。同樣的文件使用RAR格式進(jìn)展壓縮后得到的大小通常都會比使用ZIP壓縮后更小，而用戶對文件進(jìn)展壓縮的主要目的就是要減小文件大小以便于網(wǎng)絡(luò)傳輸，正巧RAR格式又出現(xiàn)在網(wǎng)絡(luò)剛剛開場普及之時，所以RAR逐漸取代ZIP的地位也就是情理之中的事了。對RAR文件進(jìn)展壓縮或者解壓縮，首選的軟件當(dāng)然是WinRAR。與之前的WinZIP一樣，它幾乎也是現(xiàn)在每臺電腦都必裝的軟件。圖2WinZip12.0和WinRAR壓縮視頻文件最終結(jié)果圖表圖3WinZip12.0和WinRAR壓縮視頻文件最終結(jié)果圖表圖4WinZip12.0和WinRAR壓縮文檔文件最終結(jié)果圖表〔3〕7Z作為壓縮格式的后起新秀，7Z有著比RAR更高的壓縮率，能夠?qū)⑽募嚎s得更加小巧。不過因?yàn)镽AR格式已經(jīng)高度普及，7Z想要取代RAR目前的地位相當(dāng)不容易。與之前兩種格式一樣，7Z也有著專門支持它的軟件：7-zip。使用7-zip可以解壓縮RAR格式的壓縮文件，而WinRAR也同樣可以解壓縮7Z格式的壓縮文件。大概因?yàn)橹苯邮褂矛F(xiàn)有的Win-RAR就可以處理網(wǎng)絡(luò)上下載到的7Z格式文件，而要將文件壓縮成7Z格式的話卻需要額外安裝7-zip，所以也間接阻礙了7Z格式的普及。〔4〕CABCAB是微軟的一種安裝文件壓縮格式，主要應(yīng)用于軟件的安裝程序中。因?yàn)樯婕暗桨惭b程序，所以CAB文件中包含的文件通常都不是簡單的直接壓縮，而是對文件名等都進(jìn)展了處理，所以雖然可以對其直接解壓縮，但解壓后得到的文件通常都無法直接使用。和ZIP一樣，Windows系統(tǒng)自身就可以翻開CAB格式的文件，而幾乎所有壓縮軟件也都可以對CAB文件進(jìn)展解壓?！?〕WinMount最后單獨(dú)介紹一個軟件：Win-Mount。當(dāng)解壓縮一個文件時，就必然會多占用一些磁盤空間，因?yàn)榇疟P上同時存在了壓縮文件和解壓后的文件。而WinMount的特點(diǎn)就是能夠?qū)嚎s文件以類似虛擬光驅(qū)的方式掛接為一個虛擬磁盤供用戶使用，因?yàn)樗械牟僮鞫际窃趦?nèi)存中進(jìn)展的，并沒有實(shí)際執(zhí)行任何的解壓縮操作，所以不會占用額外的磁盤空間。這對于一些用戶來說，可能還是很有幫助的。程序構(gòu)造1類設(shè)計哈夫曼樹的結(jié)點(diǎn)構(gòu)造如下：structHuffNode //哈夫曼樹結(jié)點(diǎn)的定義{ chardata; //待編碼的符號 doubleweight; //符號出現(xiàn)的頻率 intlchild,rchild,parent; //父結(jié)點(diǎn)左右孩子結(jié)點(diǎn)的位置};哈夫曼樹類的構(gòu)造如下：classHuffTree{public: HuffTree(vector<HuffNode>&leaves); //構(gòu)造函數(shù) vector<int>Getcode(inti); //取編碼 stringDecode(vector<int>&source); //譯碼 stringDecode(string&source); //譯碼 ~HuffTree(){} intGetn(){returnn;} //返回葉子結(jié)點(diǎn)數(shù) charGetData(inti){returnhufftree[i].data;} //返回葉子結(jié)點(diǎn)的值 HuffNodeGetNode(inti){returnhufftree[i];}private: voidSelectSmall(int&least,int&less,inti);private: vector<HuffNode>hufftree; //所有結(jié)點(diǎn)的存儲空間 intn; //葉子結(jié)點(diǎn)數(shù)};哈夫曼樹類有2個私有成員vector<HuffNode>類型的hufftree〔所有結(jié)點(diǎn)的存儲空間〕和int類型的n〔葉子結(jié)點(diǎn)數(shù)〕。有1個編碼函數(shù)vector<int>Getcode(inti)和2個譯碼函數(shù)，如下：stringDecode(vector<int>&source); //哈夫曼編碼是vector<int>類型stringDecode(string&source); //哈夫曼編碼是string類型2主程序設(shè)計主程序中有4個重要函數(shù)，如下：〔1〕計算待解壓字符出現(xiàn)的頻度voidGetFrequency(intfrequency[],charfilename[]); //統(tǒng)計各字符出現(xiàn)的頻度。先初始化用于統(tǒng)計每個ASCII碼字符個數(shù)的數(shù)組frequencyvoidGetFrequency(intfrequency[],charfilename[]){ for(inti=0;i<256;i++) frequency[i]=0; //初始化frequency數(shù)組 charch; //用于讀入每個字符 ifstreaminfile(filename); //翻開待壓縮的文件 infile>>noskipws; //noskipws:不忽略空白，把每行最后那個‘\n‘也讀進(jìn)來 while(infile>>ch) frequency[ch]++; //統(tǒng)計每個ASCII碼字符的個數(shù) infile.close(); //關(guān)閉文件}〔2〕壓縮voidpression(HuffTreehf,vector<HuffNode>leaves,charfilename[],charfilename2[]);//壓縮voidpression(HuffTreehf,vector<HuffNode>leaves,charfilename[],charfilename2[]){ ifstreaminfile2(filename); //翻開待壓縮文件 ofstreamoutfile; outfile.open(filename2); //翻開壓縮后文件 charch; infile2>>noskipws; //noskipws:不忽略空白，把每行最后那個‘\n‘也讀進(jìn)來 while(infile2>>ch) //逐個讀入字符 { for(inti=0;i<leaves.size();i++) if(ch==leaves[i].data) //找到字符對應(yīng)的葉子結(jié)點(diǎn) { for(intj=0;j<hf.Getcode(i).size();j++) outfile<<hf.Getcode(i)[j]; //將對應(yīng)Huffman編碼寫入文件 } } infile2.close(); //關(guān)閉待壓縮文件 outfile.close(); //關(guān)閉壓縮后文件 cout<<endl<<endl<<endl; cout<<"壓縮文件"<<filename<<"成功,"; cout<<"生成了已壓縮文件"<<filename2<<"!"<<endl<<endl<<endl;}〔3〕解壓1voidDepression1(HuffTreehf,charfilename2[],charfilename3[]);解壓方法1:Huffman編碼儲存為vector<int>類型從壓縮后的文件中讀入Huffman編碼,使用HuffTree類中的解碼函數(shù)將Huffman編碼轉(zhuǎn)換成對應(yīng)的ASCII碼字符寫入解壓后的文件。voidDepression1(HuffTreehf,charfilename2[],charfilename3[]){ charc; //暫時儲存讀入的字符 intt; //儲存讀入字符對應(yīng)的整數(shù) vector<int>source; //儲存Huffman編碼 ifstreaminfile(filename2); //翻開壓縮后的文件 while(infile>>c) //逐個讀入Huffman碼的0/1符 { t=c-'0'; //將字符轉(zhuǎn)換成整數(shù) source.push_back(t); //將整數(shù)插入Huffman編碼中 } infile.close(); //關(guān)閉壓縮后的文件 stringtarget; target=hf.Decode(source); //得到Huffman編碼對應(yīng)的字符 ofstreamoutfile(filename3); outfile<<target; //解壓后的字符串寫入解壓后文件 outfile.close(); //關(guān)閉解壓后的文件 cout<<"已成功解壓生成文件"<<filename3<<"!"<<endl<<endl<<endl;}〔4〕解壓2voidDepression2(HuffTreehf,charfilename2[],charfilename3[]); 解壓方法2:Huffman編碼儲存為string類型voidDepression2(HuffTreehf,charfilename2[],charfilename3[]){ charc; //暫時儲存讀入的字符 stringsource; //儲存Huffman編碼 ifstreaminfile(filename2); //翻開壓縮后的文件 while(infile>>c) //逐個讀入Huffman碼的0/1符 { source=source+c; } //將整數(shù)插入Huffman編碼中 infile.close(); //關(guān)閉壓縮后的文件 stringtarget; target=hf.Decode(source); //得到Huffman編碼對應(yīng)的字符 ofstreamoutfile(filename3); outfile<<target; //解壓后的字符串寫入解壓后文件 outfile.close(); //關(guān)閉解壓后的文件 cout<<"已成功解壓生成文件"<<filename3<<"!"<<endl<<endl<<endl;}3流程圖讀取文本中待壓縮的數(shù)據(jù)讀取文本中待壓縮的數(shù)據(jù)開場完畢統(tǒng)計各字符的頻率建哈夫曼樹得到哈夫曼編碼通過哈夫曼樹解碼系統(tǒng)環(huán)境與程序測試案例硬件環(huán)境截圖如下：軟件環(huán)境：MicrosoftVisualC++6.0軟件使用界面：1待壓縮的文件為Data.t*t，如下：壓縮后的文件為：pressionData.t*t解壓后的文件為：DepressionData1.t*t中