1、數據結構實驗報告題目：專業：班級：組別：組長：完成日期：年 月 日評分依據及結果態度（A-D）規范性（A-D）完成度（A-D）總評（A-D）評語代碼分工情況姓名工作內容實驗報告分工情況姓名耿麗麗工作內容需求分析概要分析一、 需求分析利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。本次設計要求對輸入的一串電文字符實現哈夫曼編碼，再對哈夫曼編碼生成的代碼串進行譯碼，輸出電文字符串。系統應具有如下的幾個功能：1、初始化（Init）：能夠對輸入的任意長度的字符串s進行統計，統計每個字符的頻度，并建立哈夫曼樹2、建立編碼表（CreateTable）利用已經建好的哈夫曼樹進行

2、編碼，并將每個字符的編碼輸出。3、編碼（Encoding）:根據編碼表對輸入的字符串進行編碼，并將編碼后的字符串輸出。4、譯碼（Decoding）:利用已經建好的哈夫曼樹對編碼后的字符串進行譯碼，并輸出譯碼結果。5、打印（Print）:以直觀的方式打印哈夫曼樹.二、 概要設計本程序的數據類型定義為typedef structint weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char* HuffmanCode;/ 把字母和相應的權值放在一起typedef structchar ch;int wht;WeNu;所實現的功

3、能函數如下/ 統計葉子結點的權值void CountWeight(char*str);/ 選擇 parent 為 0，且weight 最小的兩個節點序號為 s1， s2void Select(HuffmanTree HT,int len,int &s1,int &s2);/ 構造哈夫曼樹HTvoid CreatHuffmanTree(HuffmanTree &HT, int n)/從葉子到根逆向求每個字符的赫夫曼編碼，存儲在編碼表HC中void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)/ 輸出編碼void ShowCode

4、(HuffmanTree HT, HuffmanCode HC, int n)/ 輸出哈夫曼void ShowHuffman(HuffmanTree HT, HuffmanCode HC, char *str)/ 輸出字符串void ShowStr(char *str)/ 選擇解碼方式void DeCoding();/主函數void main();主要結構如圖所示三、詳細設計1.統計字符頻度 自然語言描述：(1)取出字符串中的一個字符(2)遍歷所有初始化的哈夫曼樹結點(3)如果結點中有記錄代表的字符且字符等于取出的字符，說明該字符的葉子存在，則將該結點的權值加1(4)如果所有結點記錄的字符均沒

5、有與取出的字符一致，說明該字符的葉子不存在，則將結點的字符記為取出字符，并將權重設為1(5)重復以上步驟，直至字符串中所有字符全部遍歷偽代碼描述：1. for(int i=0;ilength;i+)1.1 for (int j=0;jlength;j+)1.1.1if (WordStri=HuffTreej.word)/ 若 字 符 已 被 統 計 ， 則 增 加 權 值 即 可1.1.1.1 權重 +;1.1.1.2 break;1.1.2 else if(!HuffTreej.word)/ 否 則 需 要 一 個 新 結 點 儲 存 這 個 字 符1.1.2.1 HuffTreej.wor

6、d=WordStri;1.1.2.3 HuffTreej.weight=1；1.1.2.4 break；時間復雜度O( N2) ，空間復雜度S( 0)2. 構造哈夫曼樹：自然語言描述：(1) 選出權值最小的兩個結點，其權值和作為其根結點的權值，最小的結點作為左子樹；(2) 次小的做為右子樹，不斷將兩棵子樹合升為一棵樹。重復及上述過程，直至所有結點全被遍歷完。3. 為每個葉子結點編碼自然語言描述：(1)初始化一個字符數組Code暫存每個葉子節點的編碼；( 2)前序遍歷哈夫曼樹；(3)若結點左右子樹都為-1,則將Code復制到編碼的Code串，準備返回上一層,編碼相位少一位，Code長度-1,返回

7、；( 4)否則按照從左到右的順序前序遍歷根結點的所有子樹；(5)若訪問左子樹，則進入下一層，編碼相位多一位，Code長度加1并將最后一位賦值為0,訪問右子樹，進入下一層，Code長度加1并將最后一位賦值為0。4、編碼自然語言描述：(1)定義字符串CodeStr儲存編碼( 2) 遍 歷輸入字符串的每一個字符(3)對每一個字符，將其與HuffTree前n個葉子節點的word逐個比較，相同則 將該節點的編碼串Code連接到CodeStr。5、譯碼自然語言描述：(1)從編碼串CodeStr的第一個字符串開始于 HuffTree的第一個節點的編碼域第一個字符比較( 2)相等則比較后面的字符(3)否則，從

8、CodeStr第一個字符與HuffTree第二個結點的編碼比較(4)重復上述過程，將CodeStr中的所有字符比較完畢四、調試分析1. 在寫程序與調試的過程中，發現自己對于函數的調用與參數的傳遞的方面還是存在很多問題，從參數的類型等等方面都出現了很多問題。2. 關于這個程序的要求比較復雜，剛開始做的時候沒有任何思路，最后分模塊一點點的進行。3遞歸函數中的參數傳遞在給每個字符編碼時，由于編碼是從根結點開始，所以選用與前序遍歷相似的遞歸遍歷形式。其中需要一個字符型數組來記錄路徑和編碼，由于遞歸一次才有一位編碼，所以這個數組也要隨著遞歸函數的進行而不斷修改。開始時我們沒有用指針最為參數而是直接將數組

9、作為參數. 結果發現每次調用遞歸函數時數組都是空。原來我用的是值傳遞， 數組就算修改了也無法返回。這提醒了我們之后運用遞歸函數時如果需要某個變量隨函數遞歸而修改時應該使用地址傳遞而并非值傳遞。心得體會：哈夫曼樹又稱做最優叉樹，它是 n 個帶權的葉子結點構成的所有二叉樹中，帶權路徑長度WPLt小的二叉樹。在n個帶權的葉子結點所構成的二叉樹中，滿二叉樹或完全二叉樹不一定是最優二叉樹。權值越大的結點離樹根越近的二叉樹才是最優叉樹。哈夫曼樹是根據字符出現的概率來構造平均長度最短的編碼。它是- 種變長的編碼。在編碼中，若各碼字長度亞格按照碼字所對應符號出現概率的大小的逆序排列，則編碼的平均長度是最小的。

10、哈夫曼樹的應用非常廣泛，在通信中，采用 0.1 的不同排列來表示不同的字符，而哈夫曼樹在數據編碼中的應用，若每個字符出現的頻率相同，則可以采用等長的二進制編碼， 若頻率不同，則可以采用不等長的二進編碼，頻率較大的采用位數較少的編碼，頻率較小的字符采用位數較多的編碼，這樣可以使字符的整體編碼長度最小，哈夫曼編碼就是一種不等長的二進制編碼，且哈夫曼樹是一種最優二叉樹， 它的編碼也是-種最優編碼，在哈夫曼樹中，規定往左編碼為0, 往右編碼為1, 則得到葉子結點編碼為從根結點到葉子結點中所有路徑中0 和 1 的順序排列。下一步的改進程序中多次使用了遍歷數組或對數據進行逐個比對，循環的次數可以通過計算再

11、減少，提高時間效率。五、 用戶守則請使用 Windows 系統來打開，平臺為Visual Studio。要注意文本的打開方式和設置六、測試結果（及截圖）七、附錄（源代碼）頭文件#define _CRT_SECURE_NO_WARNINGS#include#include#include#includeusing namespace std;#define NUM 26typedef structchar ch;int wht;WeNu;把字母和相應的權值放在一起 typedef structint weight;int parent, lchild, rchild;HTNode, *Huffm

12、anTree; typedef char *HuffmanCode;源文件/#includeweight.cpp#includeHuffman.hWeNu weightNUM + 1;void CountWeight(char*str)for (int i = 1; i = NUM; i+)出過錯char cha = (char)(i + 96);weighti.ch = cha;/簡短代碼出過錯/*switch (i)case 1:weight1.ch = a;break;case 2:weight2.ch = b;break;case 3:weight3.ch = c;break;case

13、 4:weight4.ch = d;break;case 5:weight5.ch = e;break;case 6:weight6.ch = f;break;case 7:weight7.ch = g;break;case 8:weight8.ch = h;break;case 9:weight9.ch = i;break;case 10:weight10.ch = j;break;case 11:weight11.ch = k; break;case 12:weight12.ch = l;break;case 13:weight13.ch = m; break;case 14:weight

14、14.ch = n; break;case 15:weight15.ch = o; break;case 16:weight16.ch = p;break;case 17:weight17.ch = q;break;case 18:weight18.ch = r;break;case 19:weight19.ch = s;break;case 20:weight20.ch = t;break;case 21:weight21.ch = u;break;case 22:weight22.ch = v;break;case 23:weight23.ch = w; break;case 24:wei

15、ght24.ch = x; break;case 25:weight25.ch = y;break;case 26:weight26.ch = z;break;default:cout error! endl;*/weighti.wht = 0;int n = strlen(str);for (int i = 0; i n; i+)char c = stri;weight(int)c) - 96.wht+;/減短代碼/switch (c) /case a:/ weight1.wht+;/ break;/case b:/ weight2.wht+;/ break;/case c:/ weight

16、3.wht+;/ break;/case d:/ weight4.wht+;/ break;/case e:/ weight5.wht+;/ break;/case f:/ weight6.wht+;/ break;/case g:/ weight7.wht+;/ break;/case h:/ weight8.wht+;/ break;/case i:/ weight9.wht+;/ break;/case j:/ weight10.wht+;/ break;/case k:/ weight11.wht+;/ break;/case l:/ weight12.wht+;/ break;/ca

17、se m:/ weight13.wht+;/ break;/case n:/ weight14.wht+;/ break;/case o:/ weight15.wht+;/ break;/case p:/ weight16.wht+;/ break;/case q:/ weight17.wht+;/ break;/case r:/ weight18.wht+;/ break;/case s:/ weight19.wht+;/ break;/case t:/ weight20.wht+;/ break;/case u:/ weight21.wht+;/ break;/case v:/ weigh

18、t22.wht+;/ break;/case w:/ weight23.wht+;/ break;/case x:/ weight24.wht+;/ break;/case y:/ weight25.wht+;/ break;/case z:/ weight26.wht+;/ break;/default:/ cout error! endl;/*/void Select(HuffmanTree HT, int len, int &s1, int &s2) int i, min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f;/ 先賦予最大值for (i = 1; i = l

19、en; i+) if (HTi.weight min1&HTi.parent = 0)min1 = HTi.weight;s1 = i;int temp = HTs1.weight;/ 將原值存放起來，然后先賦予最大值，防止s1 被重復選擇HTs1.weight = 0x3f3f3f3f;for (i = 1; i = len; i+) if (HTi.weight min2&HTi.parent = 0)min2 = HTi.weight;s2 = i;HTs1.weight = temp;/ 恢復原來的值void CreatHuffmanTree(HuffmanTree &HT, int

20、n)/ 構造赫夫曼樹HTint m, s1, s2, i;if (n = 1) return;m = 2 * n - 1;HT = new HTNodem + 1;/0號單元未用，所以需要動態分配m+1個單元，HTm表示根結點for (i = 1; i = m; +i)/ 將 1m 號單元中的雙親、左孩子，右孩子的下標都初始化為0HTi.parent = 0; HTi.lchild = -(96 + i); HTi.rchild = -(96 + i);/a 的 ASCII 是 97！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！ ！

21、！ ！ ！ ！ ！ ！ ！ ！ /cout 請輸入葉子結點的權值：n;for (i = 1; i = n; +i)/ 輸入前 n 個單元中葉子結點的權值HTi.weight = weighti.wht;/*初始化工作結束，下面開始創建赫夫曼樹 */for (i = n + 1; i = m; +i)/ 通過 n-1 次的選擇、刪除、合并來創建赫夫曼樹Select(HT, i - 1, s1, s2);/在HTk(1 & k i-1)中選擇兩個其雙親域為0且權值最小的結點,/并返回它們在 HT中的序號si和s2HTs1.parent = i;HTs2.parent = i;得到新結點i,從森林中

22、刪除si, s2,將si和s2的雙親域由0改為iHTi.lchild = s1;HTi.rchild = s2;/si,s2 分別作為i 的左右孩子HTi.weight = HTsi.weight + HTs2.weight; /i 的權值為左右孩子權值之和/for/ CreatHuffmanTree void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) 從葉子到根逆向求每個字符的赫夫曼編碼，存儲在編碼表HC中int i, start, c, f;HC = new char*n + i;char *cd = new char

23、n;cdn - i = 0;for (i = i; i = n; +i)start = n - i;c = i;f = HTi.parent;while (f != 0)-start;if (HTf.lchild = c) cdstart = 0;elsecdstart = i;c = f;f = HTf.parent;HCi = new charn - start; strcpy(HCi, &cdstart);delete cd;/ 分配 n 個字符編碼的頭指針矢量/ 分配臨時存放編碼的動態數組空間/ 編碼結束符/ 逐個字符求赫夫曼編碼/start 開始時指向最后，即編碼結束符位置/f 指向

24、結點c 的雙親結點/ 從葉子結點開始向上回溯，直到根結點/ 回溯一次start 向前指一個位置/ 結點 c 是 f 的左孩子，則生成代碼0結點c是f的右孩子，則生成代碼 1/ 繼續向上回溯/ 求出第 i 個字符的編碼/ 為第 i 個字符編碼分配空間將求得的編碼從臨時空間cd復制到HC的當前行中/ 釋放臨時空間void ShowCode(HuffmanTree HT, HuffmanCode HC, int n)for (int i = 1; i = n; i+)cout weighti.ch ( HTi.weight ) 編碼為 HCi ttt; if (i % 2 = 0) printf(n

25、);void ShowHuffman(HuffmanTree HT, HuffmanCode HC, char *str)int i = 0;while (stri != 0) char c = stri;cout HC(int)c) - 96;/簡短代碼/*switch (c) case a:cout HC1;break; case b:cout HC2;break;case c:cout HC3;break;case d:cout HC4;break;case e:cout HC5;break;case f:cout HC6;break;case g:cout HC7;break; cas

26、e h:cout HC8;break;case i:cout HC9;break;case j:cout HC10; break;case k:cout HC11; break;case l:cout HC12; break;case m:cout HC13; break;case n:cout HC14; break;case o:cout HC15; break;case p:cout HC16; break;case q:cout HC17; break;case r:cout HC18; break;case s:cout HC19; break;case t:cout HC20; break;case u:cout HC21; break;case v:cout HC22; break;case w:cout HC23;break;case x:cout HC24;break;case y:cout HC25;break;c