【正文】 碼，復原原有文件。試為完成此功能，寫一個壓縮解壓縮軟件?！净疽蟆浚?）壓縮準備。讀取指定被壓縮文件，對文件進行分析，建立哈夫曼樹，并給出分析結果（包括數(shù)據(jù)集大小，每個數(shù)據(jù)的權值，壓縮前后文件的大小），在屏幕上輸出。（2）壓縮。利用已建好的哈夫曼樹，對文件進行編碼，并將哈夫曼編碼及文件編碼后的數(shù)據(jù)一起寫入文件中，形成壓縮文件。（3）解壓縮。打開已有壓縮文件，讀取其中的哈夫曼編碼，構建哈夫曼樹，讀取其中的數(shù)據(jù)，進行譯碼后，寫入文件，完成解壓縮。2．總體分析與設計【設計思想】將一待壓縮的文件以二進制形式進行讀寫。壓縮過程中，將待壓縮文件一次性讀入內存，隨后對其中出現(xiàn)的字符進行判斷和統(tǒng)計，將所得的字符頻率創(chuàng)建HuffMan樹，并對其進行編碼，將源文件的字符用其HuffMan編碼代替，組合成滿字節(jié)寫入壓縮文件。【詳細設計表示】變 量 數(shù)據(jù)類型 Maxsize int *Key input_char KeyNum int *Huffman_node huffmantree 成員函數(shù)說明： char_judge 功能：判斷字符出現(xiàn)的函數(shù)；原型：bool char_judge(char c)。//判斷字符出現(xiàn)的函數(shù)； 返回類型：bool型 參數(shù)：c char型 [in] char_add功能：添加新出現(xiàn)字符的函數(shù)； 原型：void char_add(char c)。返回類型：無參數(shù)：c char型 [in] CreateHuffTree 功能：創(chuàng)建哈夫曼樹原型：void CreateHuffTree()。返回類型：無 參數(shù)：無CreateHuffCode功能：創(chuàng)建哈夫曼編碼原型：void CreateHuffCode()。返回類型：無 參數(shù)：無其它函數(shù)說明： ArrayOpp 功能：將一個字符數(shù)組中的1 字符順序顛倒 原型：void ArrayOpp(char a[],int n)返回類型：無參數(shù)：數(shù)組 a char型 [inamp。out] n int型CompressFile 功能：壓縮文件原型：void CompressFile(FILE *ifp,FILE *ofp)。//壓縮 返回類型：無參數(shù)：指針ifp FILE型 [inamp。out]指針ofp FILE型 [inamp。out]DepressionFile 功能：解壓文件原型：void DepressionFile(FILE *ifp,FILE *ofp)。//解壓 返回類型：無參數(shù)：指針ifp FILE型 [inamp。out]指針ofp FILE型 [inamp。out]FindMax功能：尋找數(shù)組中最大元素下標 原型：void FindMax(int index[],int n,int amp。flag)。//尋找數(shù)組中最大元素下標 返回類型：無參數(shù)：數(shù)組index int型 [inamp。out] n 數(shù)組長度 [in] flag int型 [inamp。out] 3． 編碼【遇到的問題及解決方法】（1）選取合適的數(shù)據(jù)結構對于一個工程的實現(xiàn)，到底采用怎樣的數(shù)據(jù)結構，應該考慮到程序的性能和代碼的可讀性。由于起初對工程的不熟，對于用什么樣的數(shù)據(jù)結構來存儲我一直都處在試探中，缺乏一種長久的考慮，這也使得后面的編碼過程效率不高。最終冷靜下來，自定義了一個文件類和兩個輔助結構體，大體的實現(xiàn)框架在總體設計中已給出。(2)哈夫曼樹該如何建立首先，字符的頻率作為關鍵值，用一個循環(huán)，每次找出關鍵值最小的兩個字符，將其組合加入到哈夫曼樹中，同時將每個哈夫曼樹節(jié)點用結構體huffman_node數(shù)組存放，每個節(jié)點都有其左右孩子和父節(jié)點的下標，這有便于后面的哈夫曼編碼。(3)哈夫曼編碼的具體實現(xiàn)哈夫曼編碼的具體實現(xiàn)方法：由于哈夫曼樹的建立過程中為每個哈夫曼節(jié)點標明了左右孩子和父節(jié)點，可以從關鍵值開始，從下往上通過父節(jié)點與子節(jié)點的關系為子節(jié)點進行編碼，如果父節(jié)點的左孩子是當前子節(jié)點，則子節(jié)點（含關鍵值）的哈夫曼編碼標為0否則標為1，如此循環(huán)下去。這樣得到每個葉節(jié)點對應的哈夫曼編碼的逆序表示，且存放在數(shù)組bits中。然后用一個函數(shù)ArrayOpp將其逆序過來，從而真正得到哈夫曼編碼。(4)文件的二進制形式讀寫操作及其壓縮的實現(xiàn)最主要的還是怎樣實現(xiàn)文件的壓縮，由于壓縮文件中的字符是用其相應的哈夫曼編碼代替的，如果只是把字符的哈夫曼編碼（也使字符型的數(shù)組存放的）寫入，將會適得其反，只有將相鄰字符的編碼組合成一個一個的字節(jié)數(shù)字寫入才能達到節(jié)省空間的效果，例如：某字符哈夫曼編碼為bits 1 1 1 1 1 1 1 這字符數(shù)組內容通過移位可轉化為char型數(shù)128，如果滿一個字節(jié)就寫入，若未滿則繼續(xù)組合。4．程序及算法分析【壓縮】先整體掃描文本，統(tǒng)計文本的字符個數(shù)，種類，以及頻率記錄下來。根據(jù)字符的頻率生成相應的huffman樹，生成huffman樹之后再根據(jù)樹的結構生成huffman編碼。生成壓縮文件，文件頭部分寫入待壓縮文件的字符個數(shù)，字符種類以及相應的頻率，分別用int型，char型數(shù)組以及int型數(shù)組寫入。寫入帶壓縮文件中每個字符對應的huffman編碼，按位寫入。按位寫入采用移位思想，滿8位一寫。如源文件中一段字符“ABC”,A的huffman編碼為001,B的huffman編碼為010，C的為11，剛好滿8位。則定義一個unsigned char型變量如c_out（初值為0），用移位將c_out賦值使其機器編碼為00101011，剛好8位，再將其作為一個字符寫入壓縮文件中，直至將帶壓縮文件的最后一個字符寫滿。要注意的是:若帶壓縮文件最后一個字符的huffman編碼賦值給c_out后c_out不滿8位，則將c_out的其余位都補0。【解壓】讀壓縮文件的頭部分，定義幾個變量記錄字符個數(shù)，種類以及對應的頻率。根據(jù)字符種類及頻率生成huffman樹。，每讀一個字符根據(jù)其8位機器碼來遍歷huffman樹，當遇到huffman樹的葉子節(jié)點時終止，將葉子節(jié)點的字符寫入解壓后的新文件中。當讀完最后一個字符后終止循環(huán)。解壓正文時每讀一個字符，利用移位將該字符的8位機器碼取出存入鏈表中，方便huffman樹的遍歷?！痉治觥恐饕某绦蚣性趦蓚€函數(shù)中：CompressFile和DepressionFile考慮到程序的性能，在對文件的讀寫過程中，我選擇在內存中對文件進行操作，在壓縮時，將待壓縮文件一次性讀入內存，在解壓文件時，將待解壓文件一次性讀入內存，而不是一個字節(jié)一個字節(jié)地讀寫文件。5．小結通過這次課題實驗的程序實踐，我實在獲益匪淺！數(shù)據(jù)結構是上個學期開展的一門學科，學習這門學科也是艱辛的，因為它比較難懂，但是這門學科是非常重要的，在以后的程序設計方面這門學科能給我們很大的幫助。這次的程序設計對我來說無疑是一個具大的考驗，從接起課題后，我就一直為實現(xiàn)程序而努力，翻閱相關書籍、在網(wǎng)上查找資料。因為課本上的基礎知識掌握不好，過程中遇到了不少的阻礙，編寫程序的進度也比較慢。雖然如此，但是通過自己的努力與老師的指導，我對這次實驗的原理有了一定的理解，通過參照從網(wǎng)上找到的源程序，終于在其它源程序的基礎下寫出了本次實驗的核心算法，并使其能夠正常的運行。近兩周的程序設計，讓我體會到了作為一個編程人員的艱難，一個算法到具體實現(xiàn)，再到應用層面的開發(fā)是需要有一段較長的路要走的，不是一朝一夕就可以實現(xiàn)的，而且在編好程序后，編程人員還要花很多的時間去完善它，其中包含的心酸，外人是不會明白的。這次課程設計涉及對大量數(shù)據(jù)的處理，要做到精益求精，不能忽略任何一處，否則結果將會有很大的不同，總之，最大的感受就是完美源于細節(jié)！編程不僅要有一定的理論基礎和實踐經(jīng)驗，還需要一定的毅力和關注細節(jié)的習慣。這次對文件的壓縮和解壓的實習，使我的調試有了進一步的提高。同時也使我在編程中對文件的存儲形式的采取有了一定的了解。希望在以后的實習中，我會有有進一步的提高。6．附錄【部分核心代碼】void CompressFile(FILE *ifp,FILE *ofp){if(!ifp){coutopened!”fseek(ifp, 0, SEEK_END)。//定位到文件結尾處int orignflen = ftell(ifp)。char *orignfile=new char [orignflen+1]。fseek(ifp,0,SEEK_SET)。//定位到文件起始處fread(orignfile,1,orignflen,ifp)。//將文件內容一次性讀到內存中orignfile[orignflen]=0。C_file file(512)。char c。for(int i=0。ic=orignfile[i]。if(!(c))//對原文件字符進行判斷和統(tǒng)計(c)。}for(int i=1。icout} ()。//創(chuàng)建HuffMan樹()。//創(chuàng)建HuffMan編碼//*******************************************************************// //寫入文件信息fseek(ifp,0,SEEK_SET)。fwrite(amp。orignflen,sizeof(int),1,ofp)。fwrite(amp。,sizeof(int),1,ofp)。fwrite(amp。,sizeof(int),1,ofp)。for(int i=1。ifwrite(amp。[i].data,sizeof(char),1,ofp)。fwrite(amp。[i].count,sizeof(int),1,ofp)。}//*******************************************************************//unsigned char o_c=0。//o_c中存入二進制的位數(shù)int bitnum=0。char x。for(int k=0。kc=orignfile[k]。//從內存中取出源文件內容for(inti=1。i{//在文件類對象中檢索出相應的關鍵碼if(c!=[i].data)continue。else{//將哈夫曼編碼組合成char型數(shù)字for(intj=0。j{if(bitnum==8){//若滿8位則構成一字節(jié)寫入fwrite(amp。o_c,1,1,ofp)。bitnum=0。o_c=0。}x=[i].bits[j]。if(x==39。139。)o_c=(o_celse o_c=o_cbitnum++。}break。}} } while(bitnum{o_c=o_cbitnum++。} fwrite(amp。o_c,1,1,ofp)。//將最后一個