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