【正文】 與技術(shù)專業(yè)學生所具備的科學的工作方法和作風。 、系統(tǒng)設(shè)計、程序編碼、測試等基本技能和方法。基于赫夫曼編碼的文本壓縮程序 一、目的及意義 通過課程設(shè)計的綜合訓練，旨在幫助學生進一步系統(tǒng)的掌握數(shù)據(jù)結(jié)構(gòu)這門課的主要內(nèi)容，并進一步培養(yǎng)學生分析問題和解決問題的能力，主要體現(xiàn)在能夠讓學生針對實際問題有效地組織數(shù)據(jù)，選擇合適的數(shù)據(jù)結(jié)構(gòu)，并進行正確和高效地算法設(shè)計，并用程序?qū)崿F(xiàn)算法。該課的課程設(shè)計是一個良好的程序設(shè)計技能訓練的過程使學生能夠： ，具備初步的獨立分析和設(shè)計能力。 。 二、程序功能描述 程序?qū)崿F(xiàn)的功能：對文本文件進行壓縮以及對壓縮的文本文件進行解壓縮。赫夫曼編碼是一種無損的壓縮算法，一般用來壓縮文本和程序文件。意思是個體符號 (例如，文本文件中的字符 )用一個特定長度的位序列替代。 程序由三個文件組成：頭文件 、函數(shù)實現(xiàn)文件、測試文件 。 利用赫夫曼編碼實現(xiàn)對文本的壓縮的過程大致為：打開要壓縮的文本文件，讀取文件中的字符，統(tǒng)計文件中不同字符出現(xiàn)的頻率 ，建立赫夫曼樹，通過赫夫曼樹對出現(xiàn)的互不相同的字符進行編碼，建立編碼表，接著將將赫夫曼樹 (即解碼表 )寫入壓縮文件中。對壓縮文件的解壓過程為：打開壓縮文件，讀取壓縮文件解碼表部分，讀取壓縮文件的編碼數(shù)據(jù)，將壓縮數(shù)據(jù)通過解碼表進行解碼，將解碼出的字符寫入解碼文件中。當用戶選擇壓縮功能，此時程序要求用戶輸入要壓縮的文本文件的路徑，用戶輸入完成后。檢查完成后，程序?qū)⑽募挠脖P讀入內(nèi)存。例如當文件中存有如下表所示字符。每個漢字占兩個字節(jié)存儲空間，漢字的存儲使用機內(nèi)碼，各字節(jié)的機內(nèi)碼編碼范圍為 160~254。這是因為漢字是通過劃分區(qū)號和位號來表示的，所有漢字被劃分成了 94 個區(qū)， 94個位，所以當漢字屬于同一個區(qū)，那么它的第一字節(jié)機內(nèi)碼就會相同。 在這種情況下，就有必 要為特定的數(shù)據(jù)設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)。采用該數(shù)據(jù)結(jié)構(gòu)對表 1 數(shù)據(jù)進行表示如圖 1。但鄰接表的表結(jié)點采用鏈式存儲，而圖 1的表結(jié)點和頭結(jié)點都采用線性表儲存。 HC[i].count– HC[i– 1].count 等于 HC[i]實際存儲的字符數(shù)量。 程序執(zhí)行壓縮操作詳細過程：當程序從文件中讀取一個字符后，通過字符的編碼范圍分析該字符是屬于 ASCII還是 GB2312,若是 ASCII 編碼，增加編碼表 HC 縱向表長，將該字符的 ASCII 碼按非遞減次序插入到內(nèi)碼 1處，并將當前位置的字符數(shù)加 1，并置內(nèi)碼 2 默認為 0；如果是漢字，首先通過折半查找算法縱向查找編碼表 HC 的內(nèi)碼 1成員，若當前漢字第一字節(jié)機內(nèi)碼已經(jīng)出現(xiàn)過，則折半查找返回該機內(nèi)碼 1 在 HC 表中的位置，增加當前位置的橫向表長，將漢字的第二字節(jié)機內(nèi)碼按非遞減次序插入當前位置的內(nèi)碼 2處。在讀取文件的同時記錄文件中各 字符出現(xiàn)的頻率，當編碼表 HC表構(gòu)建完成，此時 w={3,9,14,3,1,2,17,5,5,13,2,6,20,9,8,5,12}。根據(jù)表 1數(shù)據(jù)構(gòu)建赫夫曼樹如圖 2所示。 圖 2根據(jù)表 1 構(gòu)造的赫夫曼樹 圖 3(a)HT 初始狀態(tài)圖 3(b)HT 終止狀態(tài) 根據(jù)生成的赫夫曼樹對 HC 表中的字符進行編碼，編碼的方法：從 該葉子到根逆向求該字符的編碼。將得到的赫夫曼編碼寫入 HC[i].internal_code_address[j].code 指向的區(qū)域。再次打開要壓縮的文本文件，讀取文件中的字符，根據(jù)編碼的范圍確定該字符是 ASCII 還是GB2312，如果 ASCII 則調(diào)用折半查找函數(shù)，在編碼表 HC 中進行縱向查找，查找此 ASCII 出現(xiàn)的位置 p1，該 字符的編碼為HC[p1].internal_code_address[1].code；如果字符是漢字，則調(diào)用折半查找先縱向查找該漢字的第一字節(jié)機內(nèi)碼在 HC中的位置 p1，然后從HC[p1].internal_code_address 開始橫向查找該漢字的第二字節(jié)機內(nèi)碼的位置p2，這樣就得到了該漢字的赫夫曼編碼為HC[p1].internal_code_address[p2].code 因為赫夫曼編碼在 HC 表中是以字符串形式存放 (因為計算機的基本儲單位是字節(jié)，如果以位存放，需要另設(shè)一個空間來表示未編碼的位空間大小 )。因為每個赫夫曼編碼的長度是不一樣的，假設(shè)某字符的赫夫曼長度為 4，則將該編碼寫入一個字節(jié)后，還剩余 4個位，則下一次可以繼續(xù)從第 5個位開始寫入，當所有字符的編碼都寫入完畢后，最后一個字節(jié)并不一定會用完，所以需要附設(shè)一個字節(jié)來記錄最后一個字符編碼實際寫入的編碼位數(shù)。將字符寫入文件，直至所有 DATA 數(shù)據(jù)處理完畢，整個解壓過程結(jié)束。s1,intamp。HC,int internal_code1,int internal_code2,int(*FrequencyMeter)[255],intamp。HC,int*amp。n)； void xj_CreateHuffmanTree(HuffmanTreeamp。0xFF)； if(key==internal_code) { return mid； } else if(internal_code key) { high=mid1； } else { low=mid+1； } } return 0； } //對 HC表的字符域做插入非遞減排序 template class T void xj_InsertSort(T L,int start,int end) { int i； L[0]=L[end]； i=end1； while(i=startamp。int(L[i].internal_codeamp。0xFF)) { L[i+1]=L[i]； i； } L[i+1]=L[0]； } //尋找權(quán)重最小的兩個結(jié)點 void xj_Select(const HuffmanTree HT,int n,intamp。s2) { int i=0； s1=s2=0； for(i=1； i=n； ++i) { if(HT[i].parent==0) { if(s1==0) { s1=i； } else if(s2==0) { s2=i； } else if(HT[i].weight HT[s1].weight||HT[i].weight HT[s2].weight) { s1=HT[s1].weight HT[s2].weight?s1： s2； s2=i； } } } } //構(gòu)建 以及 結(jié)構(gòu) void xj_Statistics(HuffmanPCodeamp。n) { i