數(shù)據(jù)結構適用教程ch08課件

第8章課程實習指導算法書寫規(guī)范實習步驟規(guī)范實習報告范例加密算法實例1第8章課程實習指導算法書寫規(guī)范18.1.1算法書寫規(guī)范1算法說明算法說明以注釋的形式寫在程序首部，說明算法的功能，說明各參數(shù)的含義和使用的方法，說明使用一個函數(shù)需要的入口參數(shù)，還有函數(shù)調用后返回的出口參數(shù)。很多人都依賴算法說明和注解。不好的算法說明不僅不利于他人理解，還可能引起誤導。28.1.1算法書寫規(guī)范1算法說明22.注釋與斷言注釋是很重要的幫助理解算法的手段，但不必要為每句語句都加上注解。當閱讀算法時遇到不明之處時，切中要害的注解能大大減少理解算法的時間，同時也利于程序的排錯。算法書寫規(guī)范32.注釋與斷言算法書寫規(guī)范3算法書寫規(guī)范3.輸入和輸出

算法的輸入和輸出可以通過幾種途徑實現(xiàn)。一般最多的是通過函數(shù)的參數(shù)表進行傳遞，一種不太好的方法是用全局變量或者用公共的存儲區(qū)交換數(shù)據(jù)。這種共享式的交換容易引起岐義和不可控制性，應該盡量少用。

4算法書寫規(guī)范3.輸入和輸出4算法書寫規(guī)范4.語句選用的算法結構算法結構不應該過份追求算法的新奇和花哨，,簡明清晰的程序結構和可靠的程序功能是我們需要的目標。要避免大段代碼（遠大于一頁）的直接出現(xiàn)，一般將一頁左右的代碼分成一個模塊（函數(shù)），控制模塊規(guī)模，并用函數(shù)原型來說明算法的行為。

5算法書寫規(guī)范4.語句選用的算法結構5算法書寫規(guī)范5.基本運算在算法設計過程中，會發(fā)現(xiàn)教材上有很多現(xiàn)成的算法可以使用，但我們在學習過程中希望讀者不要直接利用這些現(xiàn)成的產品。如果算法工作量很大，非用不可，那必須將所有基本運算寫成具體函數(shù)過程加以實現(xiàn)。

6算法書寫規(guī)范5.基本運算6算法書寫規(guī)范(1)建議用圖說明算法。(2)建議在算法書寫完畢后，用邊界條件的輸入?yún)?shù)值驗證一下算法能否正確執(zhí)行。(3)編寫代碼時，養(yǎng)成良好的編碼習慣。

7算法書寫規(guī)范(1)建議用圖說明算法。7算法書寫規(guī)范“匈牙利記法”的變量名在這種記法中，變量具有一個描述性名字，如Count、UserName，并以大寫字母開始。如果變量由多個單詞組成，則每個單詞詞頭需大寫，在描述性名稱前，需加上表示變量類型的字母.8算法書寫規(guī)范“匈牙利記法”的變量名8前綴變量類型注釋AArray數(shù)組BBoolean布爾DDouble雙精度HHandle句柄（windows用）IInteger整數(shù)LLong長型LpfnLongpointertofunction指向函數(shù)的長指針m_Membervariable成員變量NInteger整數(shù)PPointerto指針SString串SzZeroterminnatedstring以零’\0’結尾的串UUnsignedinteger無符號整數(shù)表8-1-1變量的匈牙利記法9前綴變量類型注釋AArray數(shù)組BBoolean布爾DDou8.1.2實習步驟規(guī)范1.問題分析與系統(tǒng)結構設計軟件工程的理論表明，解決一個問題的核心在于了解問題本身設計算法前，首先弄清要求做什么而不是怎么做第二步是按照以數(shù)據(jù)結構為中心的原則劃分模塊，先定義所需要的數(shù)據(jù)結構，然后定義在它上面能進行的操作。最后再進行具體編碼。108.1.2實習步驟規(guī)范1.問題分析與系統(tǒng)結構設計108.1.2實習步驟規(guī)范2詳細設計和編碼寫出程序的框架，用偽碼和接口描述算法，對需求分析做進一步細化。通過較高層次的設計能使流程清晰，而不陷入具體算法之中。詳細設計和編碼是對詳細設計結果的進一步求精。最后用某種高級語言，比如C語言或者C++語言表達出來。118.1.2實習步驟規(guī)范2詳細設計和編碼118.1.2實習步驟規(guī)范3.上機準備和靜態(tài)檢查(以C語言為例)掌握C語言的基本語法掌握C語言的調試方法上機準備的重點應該放在程序的語義方面128.1.2實習步驟規(guī)范3.上機準備和靜態(tài)檢查(以C語言為例8.1.2實習步驟規(guī)范

靜態(tài)檢查，主要有兩種途徑，一是用一組測試數(shù)據(jù)手工執(zhí)行程序(或分模塊進行)；二是通過閱讀或給別人講解自己的程序來全面理解程序邏輯，動態(tài)檢查，即調試程序。一般要在靜態(tài)檢查無誤后，才上機調試。138.1.2實習步驟規(guī)范

靜態(tài)檢查，主要有兩種途徑，一是用一8.1.2實習步驟規(guī)范錯誤是關聯(lián)的，一個錯誤會引起其它多個錯誤。所以當改正一個錯誤點時，可能消除多個編譯錯誤。當某個錯誤看來無法改正的時候，可以先試著改正下一個錯。上機調試時最好分塊進行，自底向上，即先調試低層函數(shù)。必要時可以另寫一個調用驅動程序。148.1.2實習步驟規(guī)范錯誤是關聯(lián)的，一個錯誤會引起其它多個8.1.2實習步驟規(guī)范4整理實習報告的內容(1)需求和規(guī)格說明(2)設計：(3)調試報告(4)附錄158.1.2實習步驟規(guī)范4整理實習報告的內容158.1.2實習步驟規(guī)范6.實驗報告的要求(1)各種文檔資料要在程序開發(fā)過程中逐漸形成，而不能最后再寫(但可以最后謄清)。(2)各種文檔資料要用公文紙或稿紙書寫，也可以打印，不得寫在程序清單上。168.1.2實習步驟規(guī)范6.實驗報告的要求168.2實習報告范例求出一個不帶變量的表達式的值。[問題描述]用一個算法，將一個合法的表達式，如10*3-(4+5)/12轉化成計算機能執(zhí)行的命令或者直接計算出結果。本次設計的算法是遞歸下降語法分析程序，還有對復雜數(shù)值表達式求值所必須的全部支持函數(shù)。主要任務是：輸入一個串，判斷它是否合法，并將其結果算出。178.2實習報告范例求出一個不帶變量的表達式的值。178.2實習報告范例[基本要求]根據(jù)輸入的字符串，判斷其是否是合法的表達式。如果不是，給出出錯信息。否則計算表達式結果并顯示在屏幕上。算法要求體現(xiàn)算符優(yōu)先級，比如先乘除后加減，先次方再乘除，括號提升優(yōu)先級等188.2實習報告范例[基本要求]188.2實習報告范例1需求和規(guī)格說明

雖然表達式可由所有類型的字符串構成，但是這里只研究一種類型：即數(shù)值型表達式。假定數(shù)值型表達式可由下列元素組成：數(shù)字運算符+、-、*、/、^、%括號其中“^”表示指數(shù)，“%”表示求余數(shù)。所有這些項都遵守代數(shù)規(guī)則。每個運算符優(yōu)先級見書本.198.2實習報告范例1需求和規(guī)格說明198.2實習報告范例2設計

（1）設計思想1分解表達式。在設計對表達式求值的語法分析程序之前，先要得到表達式的每一部份，表達式里的每個合乎語法的部份叫一個token。所以返回下一個表達式中元素的函數(shù)稱為get_token。208.2實習報告范例2設計

208.2實習報告范例2表達式語法分析表達式的求值有多種方法，比如算符優(yōu)先文法。本例中，將表達式認為是作用于自身的遞歸的數(shù)據(jù)結構。例如假使表達式中算符只有+、-、*、/和括號，則它可以用以下規(guī)則定義：表達式->項[+項][-項]項->因子[*因子][/因子]因子->變量，數(shù)，或者(表達式)218.2實習報告范例2表達式語法分析218.2實習報告范例（2）設計表示法1本程序采用了多個函數(shù)。其中相繼調用get_exp，level2,level3,level4,level5,level6處理不同優(yōu)先級的運算，優(yōu)先級低的+和-算符放在較高層的level2中，*和/放在level3中，這樣，調用的時候先由level2調用level3，level3先執(zhí)行放在其函數(shù)體內的*、/處理程序，等處理完成，再返回level2處理加減，這樣算符的優(yōu)先級就得以體現(xiàn)。228.2實習報告范例（2）設計表示法228.2實習報告范例2接口函數(shù)功能和說明(略)3調試報告在調試中要特別注意在分析過程中各個函數(shù)的調用順序和調用方法，因為這個順序隱含了優(yōu)先級。還要注意參數(shù)在傳遞過程中的變化。比如參數(shù)result一級一級返回并被計算的過程。調試遇到的語法問題可能有：①漏了分號②關鍵字拼寫錯誤③函數(shù)參數(shù)類型不匹配④花括號不匹配等。具體調試過程因人而異。程序代碼略,見書本.238.2實習報告范例2接口函數(shù)功能和說明(略)238.3加密算法實例在實現(xiàn)算法之前有兩個術語應當熟悉：明文(plaintext)和密文(cipherext)。明文是能讀懂的文本；密文是編了碼的文本形式。本節(jié)算法用來加密和解密文本文件。程序有code()和decode()兩個函數(shù)：函數(shù)decode()用于解碼，是生成密文的code()函數(shù)的反過程。248.3加密算法實例在實現(xiàn)算法之前有兩個術語應當熟悉：明文(8.3加密算法實例天書是一條纏繞在一個園柱體上的布條，信息縱向地寫在布條上。解碼的過程是將布條解開傳送給信息的接收者，接收者有一個同樣大小的園柱體就可以讀懂密碼。從理論上講，沒有這個園柱體就不可能讀懂布條，因為字母順序已經打亂。實際上這個方法還有些漏洞，因為可以用許多不同大小的園柱體去嘗試，直到嘗試成功。258.3加密算法實例天書是一條纏繞在一個園柱體上的布條，信息8.3加密算法實例將信息以一種方式存入數(shù)組，以另一種不同的方式讀出，可以建立一個計算機化的“天書”。例如，以下聯(lián)合unionmessage{chars[100];chars2[20][5];}skytale;268.3加密算法實例將信息以一種方式存入數(shù)組，以另一種不同的8.3加密算法實例如果你把信息meetmeatsunset存入數(shù)組skytale.s，但將它看作一個二維數(shù)組skytale.s2，其形式將如下。278.3加密算法實例如果你把信息27MEEt

ME

at

SUnsET0000000028MEEt

ME

at

SUnsET00000000288.3加密算法實例如果你按列讀出數(shù)組，信息就變成

mm.e...eest...e.u...tan...ts...這里的“.”點號說明了填充的空格。要解密信息，按列填入到skytale.s2，那么數(shù)組skytale.s就能按正常次序顯示。由于信息以空’\0’結束，skytale.s數(shù)組可作為一個字符串顯示。天書密碼程序使用這種方法加密和解密信息。具體代碼從略298.3加密算法實例如果你按列讀出數(shù)組，信息就變成29第8章課程實習指導算法書寫規(guī)范實習步驟規(guī)范實習報告范例加密算法實例30第8章課程實習指導算法書寫規(guī)范18.1.1算法書寫規(guī)范1算法說明算法說明以注釋的形式寫在程序首部，說明算法的功能，說明各參數(shù)的含義和使用的方法，說明使用一個函數(shù)需要的入口參數(shù)，還有函數(shù)調用后返回的出口參數(shù)。很多人都依賴算法說明和注解。不好的算法說明不僅不利于他人理解，還可能引起誤導。318.1.1算法書寫規(guī)范1算法說明22.注釋與斷言注釋是很重要的幫助理解算法的手段，但不必要為每句語句都加上注解。當閱讀算法時遇到不明之處時，切中要害的注解能大大減少理解算法的時間，同時也利于程序的排錯。算法書寫規(guī)范322.注釋與斷言算法書寫規(guī)范3算法書寫規(guī)范3.輸入和輸出

算法的輸入和輸出可以通過幾種途徑實現(xiàn)。一般最多的是通過函數(shù)的參數(shù)表進行傳遞，一種不太好的方法是用全局變量或者用公共的存儲區(qū)交換數(shù)據(jù)。這種共享式的交換容易引起岐義和不可控制性，應該盡量少用。

33算法書寫規(guī)范3.輸入和輸出4算法書寫規(guī)范4.語句選用的算法結構算法結構不應該過份追求算法的新奇和花哨，,簡明清晰的程序結構和可靠的程序功能是我們需要的目標。要避免大段代碼（遠大于一頁）的直接出現(xiàn)，一般將一頁左右的代碼分成一個模塊（函數(shù)），控制模塊規(guī)模，并用函數(shù)原型來說明算法的行為。

34算法書寫規(guī)范4.語句選用的算法結構5算法書寫規(guī)范5.基本運算在算法設計過程中，會發(fā)現(xiàn)教材上有很多現(xiàn)成的算法可以使用，但我們在學習過程中希望讀者不要直接利用這些現(xiàn)成的產品。如果算法工作量很大，非用不可，那必須將所有基本運算寫成具體函數(shù)過程加以實現(xiàn)。

35算法書寫規(guī)范5.基本運算6算法書寫規(guī)范(1)建議用圖說明算法。(2)建議在算法書寫完畢后，用邊界條件的輸入?yún)?shù)值驗證一下算法能否正確執(zhí)行。(3)編寫代碼時，養(yǎng)成良好的編碼習慣。

36算法書寫規(guī)范(1)建議用圖說明算法。7算法書寫規(guī)范“匈牙利記法”的變量名在這種記法中，變量具有一個描述性名字，如Count、UserName，并以大寫字母開始。如果變量由多個單詞組成，則每個單詞詞頭需大寫，在描述性名稱前，需加上表示變量類型的字母.37算法書寫規(guī)范“匈牙利記法”的變量名8前綴變量類型注釋AArray數(shù)組BBoolean布爾DDouble雙精度HHandle句柄（windows用）IInteger整數(shù)LLong長型LpfnLongpointertofunction指向函數(shù)的長指針m_Membervariable成員變量NInteger整數(shù)PPointerto指針SString串SzZeroterminnatedstring以零’\0’結尾的串UUnsignedinteger無符號整數(shù)表8-1-1變量的匈牙利記法38前綴變量類型注釋AArray數(shù)組BBoolean布爾DDou8.1.2實習步驟規(guī)范1.問題分析與系統(tǒng)結構設計軟件工程的理論表明，解決一個問題的核心在于了解問題本身設計算法前，首先弄清要求做什么而不是怎么做第二步是按照以數(shù)據(jù)結構為中心的原則劃分模塊，先定義所需要的數(shù)據(jù)結構，然后定義在它上面能進行的操作。最后再進行具體編碼。398.1.2實習步驟規(guī)范1.問題分析與系統(tǒng)結構設計108.1.2實習步驟規(guī)范2詳細設計和編碼寫出程序的框架，用偽碼和接口描述算法，對需求分析做進一步細化。通過較高層次的設計能使流程清晰，而不陷入具體算法之中。詳細設計和編碼是對詳細設計結果的進一步求精。最后用某種高級語言，比如C語言或者C++語言表達出來。408.1.2實習步驟規(guī)范2詳細設計和編碼118.1.2實習步驟規(guī)范3.上機準備和靜態(tài)檢查(以C語言為例)掌握C語言的基本語法掌握C語言的調試方法上機準備的重點應該放在程序的語義方面418.1.2實習步驟規(guī)范3.上機準備和靜態(tài)檢查(以C語言為例8.1.2實習步驟規(guī)范

靜態(tài)檢查，主要有兩種途徑，一是用一組測試數(shù)據(jù)手工執(zhí)行程序(或分模塊進行)；二是通過閱讀或給別人講解自己的程序來全面理解程序邏輯，動態(tài)檢查，即調試程序。一般要在靜態(tài)檢查無誤后，才上機調試。428.1.2實習步驟規(guī)范

靜態(tài)檢查，主要有兩種途徑，一是用一8.1.2實習步驟規(guī)范錯誤是關聯(lián)的，一個錯誤會引起其它多個錯誤。所以當改正一個錯誤點時，可能消除多個編譯錯誤。當某個錯誤看來無法改正的時候，可以先試著改正下一個錯。上機調試時最好分塊進行，自底向上，即先調試低層函數(shù)。必要時可以另寫一個調用驅動程序。438.1.2實習步驟規(guī)范錯誤是關聯(lián)的，一個錯誤會引起其它多個8.1.2實習步驟規(guī)范4整理實習報告的內容(1)需求和規(guī)格說明(2)設計：(3)調試報告(4)附錄448.1.2實習步驟規(guī)范4整理實習報告的內容158.1.2實習步驟規(guī)范6.實驗報告的要求(1)各種文檔資料要在程序開發(fā)過程中逐漸形成，而不能最后再寫(但可以最后謄清)。(2)各種文檔資料要用公文紙或稿紙書寫，也可以打印，不得寫在程序清單上。458.1.2實習步驟規(guī)范6.實驗報告的要求168.2實習報告范例求出一個不帶變量的表達式的值。[問題描述]用一個算法，將一個合法的表達式，如10*3-(4+5)/12轉化成計算機能執(zhí)行的命令或者直接計算出結果。本次設計的算法是遞歸下降語法分析程序，還有對復雜數(shù)值表達式求值所必須的全部支持函數(shù)。主要任務是：輸入一個串，判斷它是否合法，并將其結果算出。468.2實習報告范例求出一個不帶變量的表達式的值。178.2實習報告范例[基本要求]根據(jù)輸入的字符串，判斷其是否是合法的表達式。如果不是，給出出錯信息。否則計算表達式結果并顯示在屏幕上。算法要求體現(xiàn)算符優(yōu)先級，比如先乘除后加減，先次方再乘除，括號提升優(yōu)先級等478.2實習報告范例[基本要求]188.2實習報告范例1需求和規(guī)格說明

雖然表達式可由所有類型的字符串構成，但是這里只研究一種類型：即數(shù)值型表達式。假定數(shù)值型表達式可由下列元素組成：數(shù)字運算符+、-、*、/、^、%括號其中“^”表示指數(shù)，“%”表示求余數(shù)。所有這些項都遵守代數(shù)規(guī)則。每個運算符優(yōu)先級見書本.488.2實習報告范例1需求和規(guī)格說明198.2實習報告范例2設計

（1）設計思想1分解表達式。在設計對表達式求值的語法分析程序之前，先要得到表達式的每一部份，表達式里的每個合乎語法的部份叫一個token。所以返回下一個表達式中元素的函數(shù)稱為get_token。498.2實習報告范例2設計

208.2實習報告范例2表達式語法分析表達式的求值有多種方法，比如算符優(yōu)先文法。本例中，將表達式認為是作用于自身的遞歸的數(shù)據(jù)結構。例如假使表達式中算符只有+、-、*、/和括號，則它可以用以下規(guī)則定義：表達式->項[+項][-項]項->因子[*因子][/因子]因子->變量，數(shù)，或者(表達式)508.2實習報告范例2表達式語法分析218.2實習報告范例（2）設計表示法1本程序采用了多個函數(shù)。其中相繼調用get_exp，level2,level3,level4,level5,level6處理不同優(yōu)先級的運算，優(yōu)先級低的+和-算符放在較高層的level2中，*和/放在level3中，這樣，調用的時候先由level2調用level3，level3先執(zhí)行放在其函數(shù)體內的*、/處理程序，等處理完成，再返回level2處理加減，這樣算符的優(yōu)先級就得以體現(xiàn)。518.2實習報告范例（2）設計表示法228.2實習報告范例2接口函數(shù)功能和說明(略)3調試報告在調試中要特別注意在分析過程中各個函數(shù)的調用順序和調用方法，因為這個順序隱含了優(yōu)先級。還要注意參數(shù)在傳遞過程中的變化。比如參數(shù)result一級一級返回并被計算的過程。調試遇到的語法問題可能有：①漏了分號②關鍵字拼寫錯誤③函數(shù)參數(shù)類型不匹配④花括號不匹配等。具體調試過程因人而異。程序代碼略,見書本.528.2實習報告范例2接口函數(shù)功能和說明(略)238.3加密算法實例在實現(xiàn)算法之前有兩個術語應當熟悉：明文(plaintext)和密文(