【正文】 軟 件 學(xué) 院 課程設(shè)計報告書 課程名稱 數(shù)據(jù)結(jié)構(gòu) 設(shè)計題目 赫夫曼編碼系統(tǒng) 專業(yè)班級 學(xué) 號 姓 名 指導(dǎo)教師 2021 年 1 月 2目錄 1 設(shè)計時間 ..................................................................................................................... 3 2 設(shè)計目的 ..................................................................................................................... 3 3 設(shè)計任務(wù) ...................................................................................................................... 3 4 設(shè)計內(nèi)容 ..................................................................................................................... 3 需求分析 ............................................................................................................ 3 總體設(shè)計 ............................................................................................................ 4 詳細設(shè)計 ............................................................................................................ 6 測試與分析 ...................................................................................................... 10 測試 .......................................................................................................... 10 分 析 .......................................................................................................... 11 附錄 ................................................................................................................... 11 5 總結(jié)與展望 ............................................................................................................... 16 參考文獻 ....................................................................................................................... 18 31 設(shè)計時間 2021年 1 月 2 日到 2021 年 1 月 6 日 2 設(shè)計目的 1) 鞏固赫夫曼樹的算法； 2) 實現(xiàn)赫夫曼樹的建立； 3) 赫夫曼編碼的生成； 4) 赫夫曼文件的譯碼； 3 設(shè)計任務(wù) 設(shè)計時間一周，對輸入的一串電文字符實現(xiàn)赫夫曼編碼，再對 赫夫曼編碼生成的代碼串進行譯碼，輸出電文字符串。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。設(shè)計實現(xiàn)的功能： (1) 赫夫曼樹的建立； (2) 赫夫曼編碼的生成； (3) 編碼文件的譯碼。 4 設(shè)計內(nèi)容 需求分析 哈夫曼編碼是一種編碼方式，以哈夫曼樹 —即最優(yōu)二叉樹，帶權(quán)路徑長度最小的二叉樹，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。 稱為赫夫曼編碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為 Wi，編碼長度為 Li，電文中有 n 種字符，則電文編碼總 長度為 ∑WiLi。若將此對應(yīng)到二叉樹上， Wi 為葉結(jié)點的權(quán)， Li為根結(jié)點到葉結(jié)點的路徑長度。那么， ∑WiLi 恰好為二叉樹上帶權(quán)路徑長度。因此 ，設(shè)計電文總長最短的二進制前綴編碼，就是以 n 種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵赫夫曼樹 。 哈弗曼編碼使用一張?zhí)厥獾木幋a表將源字符進行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。赫夫曼編碼的應(yīng)用很廣泛，利 用赫夫曼樹求得的用于通信的二進制編碼稱為赫夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示 “0”碼，指向右子樹的分支表示 “1”碼，取每條路徑上的 “0”或 “1”的序列作為和各個葉子對應(yīng)的字符的編碼，這就是赫夫曼編碼。哈弗曼譯碼輸入字符串可以把它編譯成二進制代碼，輸入二進制代碼時可以編譯成字符串。 假設(shè)輸入字符 ? BCD ?編碼成二進制代碼應(yīng)與特殊的編碼表上的二進制編碼相同輸出應(yīng) 為 40010100000，若出 現(xiàn) 其他情況的結(jié)果，錯誤；假設(shè)輸入二進制代碼 0010100000，則編譯 成字符串正確應(yīng)為 ? BCD ?， 若出先其他情況的結(jié)果，錯誤。 總體 設(shè)計 （ 1）、程序中用到的所有抽象數(shù)據(jù)類型的定義 預(yù)定義常量 define N 50 define M 2*N1 define MAXSIZE 100 輸入輸出語句 輸入語句 scanf ([格式串 ]，變量 1，變量 2。變量 n)。 輸出語句 printf([格式串 ]，變量 1，變量 2。變量 n)。 賦值語句 變量名 =表達式； 循環(huán)語句 for(賦初值表 達式序列；條件；修改表達式序列 ) 結(jié)束語句 return 表達式； 類型定義 Typedef int status （ 2）、 赫夫曼編碼 要求電文的赫夫曼編碼，必須先定義赫夫曼編碼類型，根據(jù)設(shè)計要求和實際需要定義的類型如下： typedef struct { char a[N]。 int start。 }HCode。 進行赫夫曼編碼譯碼之前建立赫夫曼二叉樹，新建立赫夫曼樹，建立赫夫曼編碼，進行主函數(shù)時，輸入 A 到 F 所有的字 符，并輸入其權(quán)值，將其進行編碼；將 data 的權(quán)值賦給 ht,判斷結(jié)點是否大于 1，輸出根結(jié)點及權(quán)值。比較 i2*N1。若是調(diào)用調(diào)用 SELECT 函數(shù)算出算出父親結(jié)點然后輸出兩子結(jié)點及父親結(jié)點。 5 開始 N1 將 data 和 weigth 賦給 HT 輸出根結(jié)點和權(quán)值 調(diào)用 SELECT 函數(shù) 計算根結(jié)點函數(shù) 雙親為兩結(jié)點之和 輸出兩子結(jié)點和雙親結(jié)點 是否為根結(jié)點？ 左子樹為空 此時編碼為 0 I2*N1? I++ 編碼為 1 結(jié)束 否 否 否 右子樹為空 是 是 否 否 是 是 是 圖 6 詳細 設(shè)計 （ 1）、 主函數(shù) void main() { int n=6,i。 char str[]={39。A39。,39。B39。,39。C39。,39。D39。,39。E39。,39。F39。}。 //初始化 int b[]={3,7,4,5,9,1}。 //初始化 HTNode HT[M]。 //建立結(jié)構(gòu)體 HCode hcd[N]。 //建立結(jié)構(gòu)體 for (i=0。in。i++) //把初始化的數(shù)據(jù)存入 HT 結(jié)構(gòu)體中 { ht[i].data=str[i]。 ht[i].weight=b[i]。 } CreateHffumanTree(HT,n)。 CreateHffumanCode (HT,hcd,n)。 DipHffumanCode(HT,hcd,n)。 printf(請輸入要進行編碼的字符串 (以 結(jié)束 ):\n)。 HffumanCode (HT,hcd,n)。 printf(請輸入編碼 (以 結(jié)束 ):\n)。 HffumanCodeTranslate (HT,hcd,n)。 （ 2）、