數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-哈夫曼樹

/成績(jī)?cè)u(píng)定教師簽名嘉應(yīng)學(xué)院計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)開課學(xué)期：2017-2018學(xué)年第2學(xué)期班級(jí)：指導(dǎo)老師：實(shí)驗(yàn)題目：哈夫曼樹學(xué)號(hào)：姓名：上機(jī)時(shí)間：一、實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)的目的是通過對(duì)簡(jiǎn)單的哈夫曼編/譯碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)來熟練掌握樹形結(jié)構(gòu)在實(shí)際問題中的應(yīng)用。二、實(shí)驗(yàn)問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高通信利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼，此試驗(yàn)即設(shè)計(jì)這樣的一個(gè)簡(jiǎn)單的編/譯碼系統(tǒng)。系統(tǒng)應(yīng)該具備如下的幾個(gè)功能。1、求出各個(gè)葉子節(jié)點(diǎn)的權(quán)重值輸入一個(gè)字符串，統(tǒng)計(jì)其中各個(gè)字母的個(gè)數(shù)和總的字母?jìng)€(gè)數(shù)。2、構(gòu)造哈夫曼樹統(tǒng)計(jì)出的字母種類為葉子結(jié)點(diǎn)個(gè)數(shù)，每個(gè)字母?jìng)€(gè)數(shù)為相應(yīng)的權(quán)值，建立哈夫曼樹。3、打印哈弗曼樹的功能模塊按照一定形式打印出哈夫曼樹。4、編碼利用已經(jīng)建立好的哈夫曼樹進(jìn)行編碼。5、譯碼根據(jù)編碼規(guī)則對(duì)輸入的代碼進(jìn)行翻譯并將譯碼。三、實(shí)驗(yàn)步驟1、實(shí)驗(yàn)問題分析設(shè)計(jì)一個(gè)結(jié)構(gòu)體數(shù)組保存字母的類型和個(gè)數(shù)。{;字母的種類;字母的個(gè)數(shù)};在構(gòu)造哈夫曼樹時(shí)，設(shè)計(jì)一個(gè)結(jié)構(gòu)體數(shù)組保存哈夫曼樹中各結(jié)點(diǎn)的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個(gè)結(jié)點(diǎn)的哈夫曼樹共有21個(gè)結(jié)點(diǎn)，所以數(shù)組大小設(shè)置為21,描述結(jié)點(diǎn)的數(shù)據(jù)類型為：{; 權(quán)值; 雙親; 左孩子; 右孩子};[]; 定義此類型的數(shù)組求哈夫曼編碼，實(shí)質(zhì)上是在已經(jīng)建立的哈夫曼樹中，從葉子結(jié)點(diǎn)開始，沿著結(jié)點(diǎn)的雙親鏈表域退回到根節(jié)點(diǎn)，每退回一步，就走過了哈夫曼樹的一個(gè)分支，從而得到一位哈夫曼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0、1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼，所以設(shè)計(jì)如下的數(shù)據(jù)類型：10;{[];每個(gè)結(jié)點(diǎn)的哈夫曼編碼;開始位置};設(shè)置全局變量。s;為輸入的字符串0;記錄輸入的字符串中字母的種類，即葉子結(jié)點(diǎn)個(gè)數(shù)0;記錄字符串中字母的總個(gè)數(shù)[]葉子結(jié)點(diǎn)類型功能（函數(shù)）設(shè)計(jì)統(tǒng)計(jì)字母種類和個(gè)數(shù)模塊此模塊的功能為從鍵盤接受一個(gè)字符串，統(tǒng)計(jì)字符串中字母種類即結(jié)點(diǎn)個(gè)數(shù)，每種字母出現(xiàn)次數(shù)即各葉子結(jié)點(diǎn)的權(quán)值。全局變量s保存輸入的字符串，將種類和個(gè)數(shù)保存到[]中。函數(shù)原型：（）如輸入的字符串是“”則顯示如下。哈夫曼樹的建立模塊此模塊的功能為從（1）中計(jì)算出的結(jié)點(diǎn)個(gè)數(shù)和各個(gè)葉子結(jié)點(diǎn)的權(quán)值構(gòu)造一棵哈弗曼樹。函數(shù)原型：*()函數(shù)返回結(jié)點(diǎn)類型的數(shù)組打印哈弗曼樹的功能模塊此模塊的功能是將由(2)建立的哈弗曼樹按照一定規(guī)則<>打印在屏幕上。函數(shù)原型：(*)如輸入的字符串是””，則構(gòu)造的哈夫曼樹為建立哈夫曼編碼的功能模塊此模塊功能為將（2）中建立的哈夫曼樹進(jìn)行哈弗曼編碼，然后將字符與對(duì)應(yīng)的0、1代碼串打印到屏幕上。函數(shù)原型：(*)如輸入的字符串是“”，則每個(gè)字母的代碼和輸入的字符串的哈夫曼編碼是譯碼的功能模塊此模塊的功能為接收需要譯碼的0和1代碼串，按照（4）中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，并將翻譯的結(jié)果在屏幕上打印出來。函數(shù)原型：(*)如輸入的代碼串是“110111100”，則對(duì)應(yīng)的字符串是“”四、實(shí)驗(yàn)結(jié)果（程序）及分析1、實(shí)驗(yàn)主要模塊代碼函數(shù)功能：統(tǒng)計(jì)字母種類和個(gè)數(shù)模塊(){ ;<<"請(qǐng)輸入字符串"<<; >>s;為輸入的字符串 (s[v]){;} <<"共有字符"<<v<<"個(gè)"<<;v是全局變量[0][0][0]1;(1<)統(tǒng)計(jì)s中字母種類和個(gè)數(shù) { (0<) {([m][k]){[m];}} (m>n){[][k][n]1;} } (0<)輸出種類和個(gè)數(shù) <<"字符"<<[m]<<"有"<<[m]<<"個(gè)"<<;}函數(shù)功能:哈弗曼樹的建立模塊*(){*;1212; 1記錄最小的重權(quán)值，m2為次小(0<2*1){結(jié)點(diǎn)初始化[i]1;[i]0;[i]1;[i]1;}(0<)將每個(gè)字母的個(gè)數(shù)當(dāng)做葉子結(jié)點(diǎn)的權(quán)值[i][i];(0<1){m12;x12=0;(0<){([j]1[j]<m1){ m21; x21; m1[j]; x1; 1記錄最小重權(quán)值在數(shù)組中的下標(biāo)} ([j]1[j]<m2){ m2[j]; x2; 2記錄次小重權(quán)值在數(shù)組中的下標(biāo) }}[x1];[x2];[]12;[]1;[]2;}; 返回?cái)?shù)組首地址}函數(shù)功能：打印哈弗曼樹的功能模塊(*){ <<<<<<;界面優(yōu)化<<"哈弗曼樹"<<;<<""<<""<<""<<"" <<""<<""<<""<<""<<; 界面優(yōu)化(0<2*1)<<""<<[i]<<""<<[i]<<""<<[i]<<""<<[i]<<;}函數(shù)功能：建立哈弗曼編碼的功能模塊(*){[];;(0<){ 求每個(gè)結(jié)點(diǎn)的哈弗曼編碼1;;[c];(1){ 由葉子結(jié)點(diǎn)向上直到樹根([p]) []=0; []=1; ; ; [c];}(1<)將結(jié)果保存[i][j][j]保存每位號(hào)碼[i];保存開始位置}<<<<<<;<<"哈弗曼編碼"<<; (0<)打印各個(gè)字母對(duì)應(yīng)的編碼{ <<""<<; <<[i]<<"的代碼是"; ([i]1<) <<[i][j]; <<;}<<""<<;<<<<"輸入的字符串的哈夫曼編碼為："<<;(0<)打印輸入的字符串的編碼結(jié)果 (0<) (s[i][y]) {([y]1<)<<[y][j];}<<;}函數(shù)功能：譯碼的功能模塊(*){;記錄輸入的0，1代碼t;<<<<<<;<<"請(qǐng)輸入代碼串:";>>;0;([]) ;確定0，1代碼長(zhǎng)度*[2*2];<<<<<<;<<"譯碼結(jié)果"<<;(0<){ ([i]'0')從根向下 [>]; [>];(>1>1){如果到達(dá)葉子結(jié)點(diǎn) >;保存葉子結(jié)點(diǎn)的權(quán)值 (0<) ([j]){ <<[j];輸出權(quán)值的對(duì)應(yīng)的字母 ; } [2*2];重新從根節(jié)點(diǎn)開始 }}<<;}2、測(cè)試數(shù)據(jù)實(shí)驗(yàn)結(jié)果截圖調(diào)試過程中出現(xiàn)的問題以及解決策略譯碼模塊中，如果輸入的代碼串無對(duì)應(yīng)的字母，則會(huì)出錯(cuò)。解決辦法：提示用戶輸入時(shí)注意附最終代碼：<><>121223;0;0;s;{;;};[12];{; 權(quán)值;;;};[]; 10;{[];;};(){ ;<<"請(qǐng)輸入字符串"<<; >>s; (s[v]){;} <<"共有字符"<<v<<"個(gè)"<<;[0][0][0]1;(1<) { (0<) {([m][k]){[m];}} (m>n){[][k][n]1;} } (0<) <<"字符"<<[m]<<"有"<<[m]<<"個(gè)"<<;}*(){*;1212; 1記錄最小的重權(quán)值，m2為次小(0<2*1){結(jié)點(diǎn)初始化[i]1;[i]0;[i]1;[i]1;}(0<)將每個(gè)字母的個(gè)數(shù)當(dāng)做葉子結(jié)點(diǎn)的權(quán)值[i][i];(0<1){m12;x12=0;(0<){([j]1[j]<m1){ m21; x21; m1[j]; x1; 1記錄最小重權(quán)值在數(shù)組中的下標(biāo)} ([j]1[j]<m2){ m2[j]; x2; 2記錄次小重權(quán)值在數(shù)組中的下標(biāo) }}[x1];[x2];[]12;[]1;[]2;}; 返回?cái)?shù)組首地址}(*){[];;(0<){ 求每個(gè)結(jié)點(diǎn)的哈弗曼編碼1;;[c];(1){ 由葉子結(jié)點(diǎn)向上直到樹根([p]) []=0; []=1; ; ; [c];}(1<)將結(jié)果保存[i][j][j]保存每位號(hào)碼[i];保存開始位置}<<<<<<;<<"哈弗曼編碼"<<; (0<)打印各個(gè)字母對(duì)應(yīng)的編碼{ <<""<<; <<[i]<<"的代碼是"; ([i]1<) <<[i][j]; <<;}<<""<<;<<<<"輸入的字符串的哈夫曼編碼為："<<;(0<)打印輸入的字符串的編碼結(jié)果 (0<) (s[i][y]) {([y]1<)<<[y][j];}<<;}(*){ <<<<<<;<<"哈弗曼樹"<<;<<""<<""<<""<<"" <<""<<""<<""<<""<<; 界面優(yōu)化 (0<2*1)<<""<<[i]<<""<<[i]<<""<<[i]<<""<<[i]<<;}(*){;記錄輸入的0，1代碼t;<<<<<<;<<"請(qǐng)輸入代碼串:";>>;0;([])