數(shù)據(jù)結構課程設計(哈夫曼編碼)

1、目 錄錯誤!未定義書簽。 1課程設計的目的和意義錯誤!未定義書簽。 2需求分析錯誤!未定義書簽。 3系統(tǒng)設計錯誤!未定義書簽。 (1) 設計思路及方案錯誤!未定義書簽。 (2) 模塊的設計及介紹錯誤!未定義書簽。 (3) 主要模塊程序流程圖錯誤!未定義書簽。 4系統(tǒng)實現(xiàn)錯誤!未定義書簽。 (1) 主調函數(shù)錯誤!未定義書簽。 (2) 建立HuffmanTree錯誤!未定義書簽。 (3) 生成Huffman編碼并寫入文件錯誤!未定義書簽。 (4) 電文譯碼錯誤!未定義書簽。 5系統(tǒng)調試錯誤!未定義書簽。 小結錯誤!未定義書簽。 參考文獻錯誤!未定義書簽。 附錄源程序錯誤!未定義書簽。 1課程設計的

2、目的和意義 在當今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術來節(jié)省數(shù)據(jù)文件的存儲空間 和計算機網(wǎng)絡的傳送時問已越來越引起人們的重視。哈夫曼編碼正是一種應用廣泛且 非常有效的數(shù)據(jù)壓縮技術。 哈夫曼編碼的應用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫 曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的 分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1的 序列作為和各個對應的字符的編碼，這就是哈夫曼編碼。 通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞 文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最

3、短，即采用 最短碼。 作為軟件工程專業(yè)的學生，我們應該很好的掌握這門技術。在課堂上，我們能過 學到許多的理論知識，但我們很少有過自己動手實踐的機會！課程設計就是為解決這 個問題提供了一個平臺。 在課程設計過程中，我們每個人選擇一個課題，認真研究，根據(jù)課堂講授內容， 借助書本，自己動手實踐。這樣不但有助于我們消化課堂所講解的內容，還可以增強 我們的獨立思考能力和動手能力；通過編寫實驗代碼和調試運行，我們可以逐步積累 調試C程序的經(jīng)驗并逐漸培養(yǎng)我們的編程能力、用計算機解決實際問題的能力。 在課程設計過程中，我們不但有自己的獨立思考，還借助各種參考文獻來幫助我 們完成系統(tǒng)。更為重要的是，我們同學之間

4、加強了交流，在對問題的認識方面可以交 換不同的意見。同時，師生之間的互動也隨之改善，我們可以通過具體的實例來從老 師那學到更多的實用的知識。 數(shù)據(jù)結構課程具有比較強的理論性，同時也具有較強的可應用性和實踐性。課程 設計是一個重要的教學環(huán)節(jié)。我們在一般情況下都能夠重視實驗環(huán)節(jié)，但是容易忽略 實驗的總結，忽略實驗報告的撰寫。通過這次實驗讓我們明白：作為一名大學生必須 嚴格訓練分析總結能力、書面表達能力。需要逐步培養(yǎng)書寫科學實驗報告以及科技論 文的能力。只有這樣，我們的綜合素質才會有好的提高。 2需求分析 題 目：哈夫曼編碼/譯碼器 問題描述： 利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短

5、信息傳輸時 間，降低傳輸成本。但是這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預 先編碼；在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可 以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣 的信息收發(fā)站寫一個哈夫曼碼的編譯碼系統(tǒng)。 具體要求： 1）初始化：鍵盤輸入字符集大小n及n個字符和ni個權值，建立哈夫 曼樹，并將它存于文件hfmtree中。 2）編碼：利用建好的哈夫曼樹，對文件tobetrans中的正文進行編碼, 然后將結果存入文件codefile中。 3）解碼：利用建好的哈夫曼樹將文件codefile中的代碼進行譯碼，結 果存入文件textfile中。 4）打印代

6、碼文件：將文件codefile以緊湊格式顯示在終端上，每行 50個代碼。同時將此字符形式的編碼文件寫入文件codeprint中。 5） 6）打印哈夫曼樹：將已在內存中的哈夫曼樹以直觀的方式（樹或凹入 表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件 treeprint 中。 7）設字符集及頻度如下表: 字符 空 格 A B C D E G H I J K I. M 頻度 186 64 23 22 32 103 21 15 47 57 1 5 32 20 字符 N 0 P Q R S T V W X Y Z 頻度 20 . 56 19 2 50 51 55 30 $ 10 11 2 21

7、 2 3系統(tǒng)設計 (1) 設計思路及方案 本課題是用最優(yōu)二叉樹即哈夫曼樹來實現(xiàn)哈夫曼編碼譯碼器的功能。假設每種字 符在電文中出現(xiàn)的次數(shù)為Wi,編碼長度為Li,電文中有n種字符，則電文編碼總長 度為(Wl*Ll) + (W2*L2)+-+(Wi*Li) 0若將此對應到二叉樹上，Wi為葉結點，Li為根 結點到葉結點的路徑長度。那么，(Wl*Ll) + (W2*L2)+-+(Wi*Li)恰好為二叉樹上帶權 路徑長度。 因此，設計電文總長最短的二進制前綴編碼，就是以n種字符出現(xiàn)的頻率作權， 構造一棵哈夫曼樹，此構造過程稱為哈夫曼編碼。 該系統(tǒng)將實現(xiàn)以下幾大功能：從硬盤讀取字符串，建立哈夫曼樹，輸出哈夫

8、曼樹 的存儲結構的初態(tài)和終態(tài)，輸出各種字符出現(xiàn)的次數(shù)以及哈夫曼編碼的譯碼等。 (2) 模塊的設計及介紹 從硬盤讀取字符串 fileopen (參數(shù)) 實現(xiàn)命令； 打印輸出； 建立 HuffmanTree 通過三個函數(shù)來實現(xiàn)： void select (參數(shù)) 初始化； for 接受命令； 處理命令； 說明：在htl. k中選擇parent為0且權值最小的兩個根結點的算法 int jsq(參數(shù)) 初始化； for 接受命令； 處理命令； 說明：統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類 void ChuffmanTreeO 初始化； for 接受命令； 處理命令； 輸出字符統(tǒng)計情況； 說明：構造哈

9、夫曼樹 輸出哈夫曼樹的存儲結構的初態(tài)和終態(tài) 分別調用printl ()和print2()來實現(xiàn) void printl (參數(shù)) 初始化； 輸出初態(tài)； 說明：輸出哈夫曼樹的初態(tài) void print2（參數(shù)） for 輸出終態(tài)； ） 說明：輸出哈夫曼樹的終態(tài) 哈夫曼編碼和譯碼 void HuffmanEncoding（參數(shù)） 定義變量； 處理命令； ） 說明：哈夫曼編碼 char*decode （參數(shù)） 定義變量； wh訂e 接受命令； 處理命令； 說明：哈夫曼譯碼 (3)主要模塊程序流程圖 下面介紹三個主要的程序模塊流程圖: 主函數(shù)流程圖: 圖 流程圖注釋： 該圖比較簡單，主要是調用各個函數(shù)

10、模塊，首先代開已經(jīng)存在的文件，然后統(tǒng)計總的 字符數(shù)以及出現(xiàn)的各個字符和頻率。然后才開始建立哈夫曼樹，接著在哈夫曼樹的基 礎上對其進行編碼，編碼之后才是譯碼。最后輸出結束。 構造哈夫曼樹: 流程圖注釋： 該圖是表示構造哈夫曼樹的過程。首先輸入num個葉結點的權值，當i=num是循環(huán)結束。然后進行哈夫曼樹的構建，當i=2相inn-l是循環(huán)結束。最后輸出所得到的字符統(tǒng) 計情況。 哈夫曼編碼: Cd一一start=O.start=n Cd 一一startCd start 否 流程圖解釋: 該流程圖表四哈夫曼編碼情況。首先初始化，Cd-start=O, start=numo然后進行 編碼，使用了一個三目

11、運算符。cd-start = (Tp.lchild=c) : i,即當 cd-start=Tp. lchild= =c 時，cd-start=O；當 cd-start=TI p l.lchild ! =c時，cd-start=l這個編碼循環(huán)一直到i=num時結束。 4系統(tǒng)實現(xiàn) 各模塊關鍵代碼及算法的解釋： (1)主調函數(shù) 代碼解釋：這是main函數(shù)里的各個函數(shù)調用情況。 fileopen(string) ；. k中選擇parent為0且權值最小的兩個根結 點的算法，其序號為si和s2。 void select(HuffmanTree T,int k,int int minl=101: for(

12、i=l；i=k；i+) if (Tl.i. weightminl $ FILE *fp； fp=fopen(”,； while(*str) for(i=l；i=num；i+) if (HCiJ. ch*str) for(j=0；j=HCi. len； j+) fputc(HCi. bitsj,fp)； break； str+； fclose(fp)； (4)電文譯碼 代碼解釋：代碼文件的譯碼，將翻譯的二進制碼譯成原來的字符。 char*decode(HuffmanCode HC) FILE *fp； char str254:its,cd)=0) strk=HCj.ch； k+; cjs=l；b

13、reak； |讀岀文本為： FAVOKITE ITHIS program IS UY f ”iiFFnianTry 巳的初態(tài)二 2 0 21111332134212 s =i=m-M =瓠熱蝕瓶熱蝕熱熱瓠= aefghimoprstuy 宀x-s-i-x-Ti-s-s-i-s-i-x-s-子 17 17 20 20 13 24 16 24 17 27 27 27 mrawsv hHIS PRO GRAM IS MY FAU OR ITE DPress any key to continue： 據(jù)結構（C語言版）清華大學岀版社，2007 蘇仕華數(shù)據(jù)結構課程設計機械工業(yè)出版社，2007 3譚浩強.

14、C語言程序設計教程髙等教育岀版社，2006 附錄源程序 #include include include #include .k中選擇parent為0且權值最小的兩個根結點的算法 eightminl p=str； return p； arent=0： HTx. lchild=0； HTx.rchild=O； printf(%lld %dt %dt %dn.HTxweightrHTx. parent JITx. lch訂d.HTxrc hild)； void prin12(HuffmanTree HT) int k； for(k=l；k=stril) HTi. weight=(char)*; /

15、*r4* int fileopen(char stringE) FILE *fp； if(fp=fopen(wE：數(shù)據(jù)結構課程設計Mr-)=NULL) printf 不能打開文件! n); exit (1)； while(fgets(string,100,fp)!=NULL) printf(n%sn,string)； fclose(fp)； return 0； /* 調函 l* void main() char string100: char *s,str27: int ent27: UuffmanTree HT： HuffmanCode HC； printf 讀出文本為：nn): fileopen(string)； num=jsq (string, ent, str);/統(tǒng)計字符的種類及各類字符出現(xiàn)的頻率 DhuffmanTree(HT,ent, str)； -nn)； /建立哈夫曼樹 /生成哈夫曼編碼 /建立電文哈夫曼編碼文件 printf(n printf (