c程序設(shè)計(jì) 譚浩強(qiáng) 第02章課件

1、2.1算法的概念算法的概念2.3算法的特性算法的特性2.4怎樣表示一個(gè)算法怎樣表示一個(gè)算法2.5結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法第第2 2章章 程序的靈魂程序的靈魂算法算法 一個(gè)程序應(yīng)包括以下兩方面內(nèi)容一個(gè)程序應(yīng)包括以下兩方面內(nèi)容:(1) 對(duì)數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和對(duì)數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的數(shù)據(jù)的組織形式組織形式，即數(shù)據(jù)結(jié)構(gòu)，即數(shù)據(jù)結(jié)構(gòu)(data structure)。(2) 對(duì)操作的描述。即操作步驟，對(duì)操作的描述。即操作步驟， 也就是算法也就是算法(algorithm)。數(shù)據(jù)是操作的對(duì)象，操作的目的是對(duì)數(shù)據(jù)進(jìn)行加工數(shù)據(jù)是操作的對(duì)象，操作的目的是對(duì)數(shù)據(jù)進(jìn)行

2、加工處理，以得到期望的結(jié)果。作為程序設(shè)計(jì)人員，必處理，以得到期望的結(jié)果。作為程序設(shè)計(jì)人員，必須認(rèn)真考慮和設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和操作步驟須認(rèn)真考慮和設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和操作步驟(即算法即算法)。因此，因此，Pascal之父沃思之父沃思(Nikiklaus Wirth)提出一提出一個(gè)公式個(gè)公式: 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 算法算法 = 程序程序n 實(shí)際上，一個(gè)程序除了以上兩個(gè)主要要素之外，還應(yīng)當(dāng)采實(shí)際上，一個(gè)程序除了以上兩個(gè)主要要素之外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程序設(shè)計(jì)方法進(jìn)行程序設(shè)計(jì)，并且用某一種計(jì)算機(jī)用結(jié)構(gòu)化程序設(shè)計(jì)方法進(jìn)行程序設(shè)計(jì)，并且用某一種計(jì)算機(jī)語(yǔ)言表示。因此，可以這樣表示：語(yǔ)言表示。因此，可以這樣表示：程序程序

3、 = 算法算法 + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 程序設(shè)計(jì)方法程序設(shè)計(jì)方法 + 語(yǔ)言工具和環(huán)語(yǔ)言工具和環(huán)境境也就是說(shuō)，以上也就是說(shuō)，以上4個(gè)方面是一個(gè)程序設(shè)計(jì)人員所應(yīng)具備的知個(gè)方面是一個(gè)程序設(shè)計(jì)人員所應(yīng)具備的知識(shí)。在設(shè)計(jì)一個(gè)程序時(shí)要綜合運(yùn)用這幾方面的知識(shí)。識(shí)。在設(shè)計(jì)一個(gè)程序時(shí)要綜合運(yùn)用這幾方面的知識(shí)。n 在這在這4個(gè)方面中，算法是靈魂，數(shù)據(jù)結(jié)構(gòu)是加工對(duì)象，語(yǔ)言個(gè)方面中，算法是靈魂，數(shù)據(jù)結(jié)構(gòu)是加工對(duì)象，語(yǔ)言是工具，編程需要采用合適的方法。算法是解決是工具，編程需要采用合適的方法。算法是解決“做什么做什么”和和“怎么做怎么做”的問(wèn)題。程序中的操作語(yǔ)句，實(shí)際上就是算法的問(wèn)題。程序中的操作語(yǔ)句，實(shí)際上就是算法

4、的體現(xiàn)。顯然，不了解算法就談不上程序設(shè)計(jì)。的體現(xiàn)。顯然，不了解算法就談不上程序設(shè)計(jì)。 2.1 算算 法法 的的 概概 念念n 問(wèn)題一：有兩個(gè)杯子問(wèn)題一：有兩個(gè)杯子A和和B，分別放有酒精和純凈水，試著，分別放有酒精和純凈水，試著將兩個(gè)杯子中的液體進(jìn)行互換。將兩個(gè)杯子中的液體進(jìn)行互換。 n 問(wèn)題二：有三個(gè)牧師和三個(gè)野人過(guò)河，只有一條能裝下兩問(wèn)題二：有三個(gè)牧師和三個(gè)野人過(guò)河，只有一條能裝下兩個(gè)人的船，在河的任何一方或者船上，如果野人的人數(shù)大于個(gè)人的船，在河的任何一方或者船上，如果野人的人數(shù)大于牧師的人數(shù)，那么牧師就會(huì)有被吃掉的危險(xiǎn)。請(qǐng)找出一種安牧師的人數(shù)，那么牧師就會(huì)有被吃掉的危險(xiǎn)。請(qǐng)找出一種安全的

5、渡河方案。全的渡河方案。兩個(gè)野人先過(guò)河，一個(gè)野人回來(lái)；兩個(gè)野人先過(guò)河，一個(gè)野人回來(lái)；再兩個(gè)野人過(guò)河，一個(gè)野人回來(lái)；再兩個(gè)野人過(guò)河，一個(gè)野人回來(lái)；兩個(gè)牧師過(guò)河，一個(gè)野人和一個(gè)牧師回來(lái)；兩個(gè)牧師過(guò)河，一個(gè)野人和一個(gè)牧師回來(lái)；兩個(gè)牧師過(guò)河，一個(gè)野人回來(lái)；兩個(gè)牧師過(guò)河，一個(gè)野人回來(lái)；兩個(gè)野人過(guò)河，一個(gè)野人回來(lái)；兩個(gè)野人過(guò)河，一個(gè)野人回來(lái)；兩個(gè)野人過(guò)河。兩個(gè)野人過(guò)河。n 算法算法是指為解決一個(gè)問(wèn)題而采取的方法和是指為解決一個(gè)問(wèn)題而采取的方法和步驟步驟。算法并不。算法并不是問(wèn)題的結(jié)果，而是是問(wèn)題的結(jié)果，而是解題的過(guò)程和策略解題的過(guò)程和策略。n又例：對(duì)又例：對(duì)有序表有序表關(guān)鍵字序列關(guān)鍵字序列5，10，19，

6、21，31，37，42，48，50，52，查找查找k為為50的記錄。的記錄。 n解一：順序查找，從第解一：順序查找，從第1個(gè)元素到最后個(gè)元素到最后1個(gè)元素，逐個(gè)進(jìn)個(gè)元素，逐個(gè)進(jìn)行比較，直至找到為止。共比較行比較，直至找到為止。共比較9次次n解二：折半查找，算法步驟：解二：折半查找，算法步驟：step1 首先確定整個(gè)查找區(qū)間的中間位置，首先確定整個(gè)查找區(qū)間的中間位置，mid = （ left + right ）/ 2；step2 用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較：用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較：若相等，則查找成功；若大于，則在后半?yún)^(qū)域繼續(xù)進(jìn)行若相等，則查找成功；若大于，則在

7、后半?yún)^(qū)域繼續(xù)進(jìn)行二分查找；若小于，則在前半?yún)^(qū)域繼續(xù)進(jìn)行二分查找。二分查找；若小于，則在前半?yún)^(qū)域繼續(xù)進(jìn)行二分查找。Step3 對(duì)確定的縮小區(qū)域再按二分公式，重復(fù)上述步驟；對(duì)確定的縮小區(qū)域再按二分公式，重復(fù)上述步驟；最后最后 得到結(jié)果：要么，查找成功，要么，查找失敗。得到結(jié)果：要么，查找成功，要么，查找失敗。 上例共比較上例共比較3次次n對(duì)同一個(gè)問(wèn)題，可以有不同的解題方法和步驟，即不同對(duì)同一個(gè)問(wèn)題，可以有不同的解題方法和步驟，即不同算法算法。n如何判斷一個(gè)算法（程序）的優(yōu)劣？時(shí)空復(fù)雜如何判斷一個(gè)算法（程序）的優(yōu)劣？時(shí)空復(fù)雜度（時(shí)間復(fù)雜度、空間復(fù)雜度）。度（時(shí)間復(fù)雜度、空間復(fù)雜度）。n一般來(lái)說(shuō)，希望

8、采用一般來(lái)說(shuō)，希望采用簡(jiǎn)單簡(jiǎn)單的和的和運(yùn)算步驟少運(yùn)算步驟少的方的方法。法。n如果一個(gè)算法對(duì)其如果一個(gè)算法對(duì)其每一個(gè)每一個(gè)輸入實(shí)例，都能輸出輸入實(shí)例，都能輸出正確的結(jié)果并停止，則稱它是正確的。正確的結(jié)果并停止，則稱它是正確的。n因此因此 ，為了有效地進(jìn)行解題，為了有效地進(jìn)行解題，不僅需要保證不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。算法。 計(jì)算機(jī)算法可分為兩類：計(jì)算機(jī)算法可分為兩類：n 數(shù)值算法數(shù)值算法: 數(shù)值運(yùn)算的目的是求數(shù)值解，如求方根、數(shù)值運(yùn)算的目的是求數(shù)值解，如求方根、求定積分等。研究深入，算法成熟，求定積分等。研究深入，算法成熟，

9、“數(shù)學(xué)程序數(shù)學(xué)程序庫(kù)庫(kù)”。n 非數(shù)值算法非數(shù)值算法: 最常見的是用于事務(wù)管理領(lǐng)域，如排最常見的是用于事務(wù)管理領(lǐng)域，如排序和檢索（查找）。參考已有類似算法，重新設(shè)計(jì)。序和檢索（查找）。參考已有類似算法，重新設(shè)計(jì)。時(shí)間復(fù)雜度的轉(zhuǎn)換n時(shí)間復(fù)雜度 運(yùn)行算法所需要的時(shí)間 以語(yǔ)句的執(zhí)行次數(shù)來(lái)代替時(shí)間 以語(yǔ)句執(zhí)行次數(shù)的數(shù)量值來(lái)代替執(zhí)行的次數(shù)(通常用數(shù)量級(jí)來(lái)表示) 2.3 算法的特性算法的特性1.有窮性有窮性一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無(wú)限的。一個(gè)算一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無(wú)限的。一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；法必須保證執(zhí)行有限步之后結(jié)束； 2.確定性確定性算法的每一步驟必須有確

10、切的定義；算法的每一步驟必須有確切的定義；3.有零個(gè)或多個(gè)輸入有零個(gè)或多個(gè)輸入所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。一所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。一個(gè)算法也可以沒(méi)有輸入。個(gè)算法也可以沒(méi)有輸入。4. 有一個(gè)或多個(gè)輸出有一個(gè)或多個(gè)輸出算法的目的是為了求解，算法的目的是為了求解，“解解” 就是輸出。沒(méi)有輸出的算法就是輸出。沒(méi)有輸出的算法是沒(méi)有意義的。是沒(méi)有意義的。 5. 有效性有效性算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。果。 2.4 怎樣表示一個(gè)算法怎樣表示一個(gè)算法常用的有自然語(yǔ)言、傳統(tǒng)流程圖、結(jié)

11、構(gòu)化流程圖、常用的有自然語(yǔ)言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼、偽代碼、PAD圖等。圖等。2.4.1 用自然語(yǔ)言表示算法用自然語(yǔ)言表示算法n 通俗易懂，但文字冗長(zhǎng)，通俗易懂，但文字冗長(zhǎng)， 容易出現(xiàn)容易出現(xiàn)“歧義性歧義性”。自然語(yǔ)言表示的含義往往不太嚴(yán)格，要根據(jù)上下文自然語(yǔ)言表示的含義往往不太嚴(yán)格，要根據(jù)上下文才能判斷其正確含義。才能判斷其正確含義。n 此外，用自然語(yǔ)言描述包含分支和循環(huán)的算法，此外，用自然語(yǔ)言描述包含分支和循環(huán)的算法，不很方便。不很方便。n 因此，除了很簡(jiǎn)單的問(wèn)題以外，一般不用自然語(yǔ)因此，除了很簡(jiǎn)單的問(wèn)題以外，一般不用自然語(yǔ)言描述算法。言描述算法。 2.4.2 用流程圖表示算法

12、用流程圖表示算法流程圖是用一些圖框表示各種操作。用圖形表示算流程圖是用一些圖框表示各種操作。用圖形表示算法，直觀形象，易于理解。美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)法，直觀形象，易于理解。美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號(hào)規(guī)定了一些常用的流程圖符號(hào)(見圖見圖2.3)。 n 圖圖2.3中中菱形框菱形框的作用是對(duì)一個(gè)給定的條件進(jìn)行判的作用是對(duì)一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的條件是否成立來(lái)決定如何執(zhí)行其后斷，根據(jù)給定的條件是否成立來(lái)決定如何執(zhí)行其后的哪一個(gè)操作。它有一個(gè)入口，兩個(gè)出口。見圖的哪一個(gè)操作。它有一個(gè)入口，兩個(gè)出

13、口。見圖2.4。n 連接點(diǎn)連接點(diǎn)(小圓圈小圓圈)是用于將畫在不同地方的流程線連是用于將畫在不同地方的流程線連接起來(lái)。如圖接起來(lái)。如圖2.5中有兩個(gè)以中有兩個(gè)以為標(biāo)志的連接點(diǎn)，它為標(biāo)志的連接點(diǎn)，它表示這兩個(gè)點(diǎn)是互相連接在一起的表示這兩個(gè)點(diǎn)是互相連接在一起的, 實(shí)際上它們是同實(shí)際上它們是同一個(gè)點(diǎn)。用連接點(diǎn)，可以避免流程線的交叉或過(guò)長(zhǎng)，一個(gè)點(diǎn)。用連接點(diǎn)，可以避免流程線的交叉或過(guò)長(zhǎng)，使流程圖清晰。使流程圖清晰。 圖 2.3 圖 2.4 圖 2.5 n需要提醒的是流程線不要忘記畫需要提醒的是流程線不要忘記畫箭頭箭頭，因?yàn)樗欠?，因?yàn)樗欠从沉鞒痰膱?zhí)行先后次序的。映流程的執(zhí)行先后次序的。n 用流程圖表示算

14、法用流程圖表示算法直觀形象直觀形象，比較清楚地顯示出，比較清楚地顯示出各個(gè)框之間的邏輯關(guān)系。各個(gè)框之間的邏輯關(guān)系。n 但是但是占用占用篇幅較多篇幅較多，尤其當(dāng)算法比較復(fù)雜時(shí)，畫，尤其當(dāng)算法比較復(fù)雜時(shí)，畫流程圖既費(fèi)時(shí)又不方便。流程圖既費(fèi)時(shí)又不方便。n 在結(jié)構(gòu)化程序設(shè)計(jì)方法推廣之后，許多書刊已用在結(jié)構(gòu)化程序設(shè)計(jì)方法推廣之后，許多書刊已用 N-S結(jié)構(gòu)化流程圖結(jié)構(gòu)化流程圖代替這種傳統(tǒng)的流程圖。但是每代替這種傳統(tǒng)的流程圖。但是每一個(gè)程序編制人員都應(yīng)當(dāng)熟練掌握傳統(tǒng)流程圖。一個(gè)程序編制人員都應(yīng)當(dāng)熟練掌握傳統(tǒng)流程圖。2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖三種基本結(jié)構(gòu)和改進(jìn)的流程圖1. 傳統(tǒng)流程圖的弊端傳統(tǒng)流程

15、圖的弊端傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒(méi)有嚴(yán)格限制。因此，使用者可以不受程線的使用沒(méi)有嚴(yán)格限制。因此，使用者可以不受限制地使流程限制地使流程隨意隨意地轉(zhuǎn)來(lái)轉(zhuǎn)去，使流程圖變得毫無(wú)地轉(zhuǎn)來(lái)轉(zhuǎn)去，使流程圖變得毫無(wú)規(guī)律。這種情況如圖規(guī)律。這種情況如圖2.13所示。所示。這種算法難以閱讀，也難以修改，從而使算法的可這種算法難以閱讀，也難以修改，從而使算法的可靠性和可維護(hù)性難以保證。如果我們寫出的算法能靠性和可維護(hù)性難以保證。如果我們寫出的算法能限制限制流程的無(wú)規(guī)律任意轉(zhuǎn)向流程的無(wú)規(guī)律任意轉(zhuǎn)向，閱讀起來(lái)就很方便。，閱讀起來(lái)就很方便。圖2.1

16、3為了解決這個(gè)問(wèn)題，人們?cè)O(shè)想，為了解決這個(gè)問(wèn)題，人們?cè)O(shè)想，規(guī)定出幾種基本結(jié)規(guī)定出幾種基本結(jié)構(gòu)構(gòu)，然后，然后按一定規(guī)律按一定規(guī)律將各個(gè)將各個(gè)基本結(jié)構(gòu)順序排列基本結(jié)構(gòu)順序排列起來(lái)起來(lái)組成一個(gè)算法結(jié)構(gòu)組成一個(gè)算法結(jié)構(gòu)(如同用一些基本預(yù)制構(gòu)件來(lái)搭成如同用一些基本預(yù)制構(gòu)件來(lái)搭成房屋一樣房屋一樣) 。2. 三種基本結(jié)構(gòu)三種基本結(jié)構(gòu)1966年，年，Bohra和和Jacopini提出了以下三種基本結(jié)構(gòu)，作提出了以下三種基本結(jié)構(gòu)，作為表示一個(gè)良好算法的基本單元。為表示一個(gè)良好算法的基本單元。(1) 順序結(jié)構(gòu)，如圖順序結(jié)構(gòu)，如圖2.14所示。所示。(2) 選擇結(jié)構(gòu)，或稱分支結(jié)構(gòu)，如圖選擇結(jié)構(gòu)，或稱分支結(jié)構(gòu)，如圖2

17、.15、 2.16所示。所示。圖圖2.14圖圖2.16圖圖2.15 (3) 循環(huán)結(jié)構(gòu)。有兩類循環(huán)結(jié)構(gòu)：循環(huán)結(jié)構(gòu)。有兩類循環(huán)結(jié)構(gòu)： 當(dāng)型當(dāng)型(While型型)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)見圖見圖2.17(a)。它的功能是。它的功能是先判斷先判斷給定的給定的條件條件p1，成立時(shí)，成立時(shí)，再執(zhí)行再執(zhí)行A框操作框操作，執(zhí)行完，執(zhí)行完A后，再判斷條件后，再判斷條件p1是否成立，如是否成立，如果仍然成立，再執(zhí)行果仍然成立，再執(zhí)行A框，如此反復(fù)執(zhí)行框，如此反復(fù)執(zhí)行A框，框，直到直到某一次某一次p1條件不成立條件不成立為止，此時(shí)不執(zhí)行為止，此時(shí)不執(zhí)行A框，而從框，而從b點(diǎn)脫離循環(huán)結(jié)點(diǎn)脫離循環(huán)結(jié)構(gòu)。構(gòu)。 直到型直到型(Un

18、til型型)循環(huán)循環(huán)見圖見圖2.17(b)。它的功能是。它的功能是先執(zhí)行先執(zhí)行A框框，然后判斷然后判斷給定的給定的p2條件條件是否成立，如果是否成立，如果p2條件不成立，則再執(zhí)行條件不成立，則再執(zhí)行A，然后再對(duì)，然后再對(duì)p2條件作判斷，如果條件作判斷，如果p2條件仍然不成立，又執(zhí)行條件仍然不成立，又執(zhí)行A如此如此反復(fù)執(zhí)行反復(fù)執(zhí)行A，直到直到給定的給定的p2條件成立條件成立為止，此時(shí)不再執(zhí)行為止，此時(shí)不再執(zhí)行A，從從b點(diǎn)脫離本循環(huán)結(jié)構(gòu)。點(diǎn)脫離本循環(huán)結(jié)構(gòu)。 圖圖2.18是當(dāng)型循環(huán)是當(dāng)型循環(huán) 圖圖2.19是直到型循環(huán)是直到型循環(huán) 圖2.17 圖2.18 圖2.192.4.4 用用N-S流程圖表示算法

19、流程圖表示算法n 1973年美國(guó)學(xué)者年美國(guó)學(xué)者I.Nassi和和B.Shneiderman提出提出了一種新的流程圖形式。在這種流程圖中，了一種新的流程圖形式。在這種流程圖中，完全去完全去掉了帶箭頭的流程線掉了帶箭頭的流程線。n 全部算法寫在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包全部算法寫在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框，或者說(shuō)，含其他的從屬于它的框，或者說(shuō)，由一些基本的框由一些基本的框組成一個(gè)大的框組成一個(gè)大的框。這種流程圖又稱。這種流程圖又稱N-S結(jié)構(gòu)化流程結(jié)構(gòu)化流程圖。圖。n 這種流程圖這種流程圖適于結(jié)構(gòu)化程序設(shè)計(jì)適于結(jié)構(gòu)化程序設(shè)計(jì)，因而很受歡迎。，因而很受歡迎。n N-S流程

20、圖用以下的流程圖符號(hào)：流程圖用以下的流程圖符號(hào)：(1) 順序結(jié)構(gòu)順序結(jié)構(gòu): 用圖用圖2.24形式表示。形式表示。(2) 選擇結(jié)構(gòu)：用圖選擇結(jié)構(gòu)：用圖2.25表示。表示。圖2.24 圖2.25 (3) 循環(huán)結(jié)構(gòu)：循環(huán)結(jié)構(gòu)： 當(dāng)型循環(huán)結(jié)構(gòu)用圖當(dāng)型循環(huán)結(jié)構(gòu)用圖2.26形式表形式表示。示。圖圖2.26表示當(dāng)表示當(dāng)p1條件成立時(shí)反復(fù)執(zhí)行條件成立時(shí)反復(fù)執(zhí)行A操作，直到操作，直到p1條件不成立為止。條件不成立為止。直到型循環(huán)結(jié)構(gòu)用圖直到型循環(huán)結(jié)構(gòu)用圖2.27形式表示。形式表示。用以上用以上3種種N-S流程圖中的基本框，可以組成復(fù)雜的流程圖中的基本框，可以組成復(fù)雜的N-S流程圖，以表示算法。流程圖，以表示算法

21、。當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)n可以看出用可以看出用N-S圖表示算法的優(yōu)點(diǎn)。圖表示算法的優(yōu)點(diǎn)。n它比文字描述直觀、形象、它比文字描述直觀、形象、 易于理解；易于理解；n比傳統(tǒng)流程圖緊湊易畫，尤其是它廢除了流程線；比傳統(tǒng)流程圖緊湊易畫，尤其是它廢除了流程線；nN-S流程圖中的上下順序就是執(zhí)行時(shí)的順序，即圖流程圖中的上下順序就是執(zhí)行時(shí)的順序，即圖中位置在上面的先執(zhí)行，位置在下面的后執(zhí)行。寫中位置在上面的先執(zhí)行，位置在下面的后執(zhí)行。寫算法和看算法只需從上到下進(jìn)行就可以了，十分方算法和看算法只需從上到下進(jìn)行就可以了，十分方便。便。n用用N-S圖表示的算法都是結(jié)構(gòu)化的算法圖表示的

22、算法都是結(jié)構(gòu)化的算法(不可能出不可能出現(xiàn)流程無(wú)規(guī)律的跳轉(zhuǎn)現(xiàn)流程無(wú)規(guī)律的跳轉(zhuǎn))。n歸納起來(lái)可知，一個(gè)結(jié)構(gòu)化的算法是由一些基本歸納起來(lái)可知，一個(gè)結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的；每個(gè)基本結(jié)構(gòu)又可以包含其他結(jié)構(gòu)順序組成的；每個(gè)基本結(jié)構(gòu)又可以包含其他的基本結(jié)構(gòu)；在基本結(jié)構(gòu)之間不存在向前或向后的基本結(jié)構(gòu)；在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個(gè)基本結(jié)構(gòu)范圍的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個(gè)基本結(jié)構(gòu)范圍之內(nèi)之內(nèi)(如循環(huán)中流程的跳轉(zhuǎn)如循環(huán)中流程的跳轉(zhuǎn))；n一個(gè)非結(jié)構(gòu)化的算法一個(gè)非結(jié)構(gòu)化的算法(如圖如圖2.12)可以用一個(gè)等可以用一個(gè)等價(jià)的結(jié)構(gòu)化算法價(jià)的結(jié)構(gòu)化算法(如圖如圖2.35)代替

23、，其功能不變。代替，其功能不變。n如果一個(gè)算法不能分解為若干個(gè)基本結(jié)構(gòu)，則它如果一個(gè)算法不能分解為若干個(gè)基本結(jié)構(gòu)，則它必然不是一個(gè)結(jié)構(gòu)化的算法。必然不是一個(gè)結(jié)構(gòu)化的算法。nN-S圖如同一個(gè)多層的盒子，又稱盒圖圖如同一個(gè)多層的盒子，又稱盒圖(box diagram)。2.4.5 用偽代碼表示算法用偽代碼表示算法n 用傳統(tǒng)的流程圖和用傳統(tǒng)的流程圖和N-S圖表示算法，直觀易懂，但圖表示算法，直觀易懂，但畫起來(lái)比較費(fèi)事。畫起來(lái)比較費(fèi)事。n 為了設(shè)計(jì)算法時(shí)方便，常用一種稱為為了設(shè)計(jì)算法時(shí)方便，常用一種稱為偽代碼偽代碼(pseudo code)的工具。的工具。n 偽代碼是用偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)

24、言之間介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文的文字和符號(hào)來(lái)描述算法。它不用圖形符號(hào)，因此書寫字和符號(hào)來(lái)描述算法。它不用圖形符號(hào)，因此書寫方便方便 、格式緊湊，也比較好懂，便于向計(jì)算機(jī)語(yǔ)言、格式緊湊，也比較好懂，便于向計(jì)算機(jī)語(yǔ)言算法算法(即程序即程序)過(guò)渡。過(guò)渡。例如，例如， “打印打印x的絕對(duì)值的絕對(duì)值”的算法可以用偽代碼表的算法可以用偽代碼表示如下：示如下：IF x is positive THENprint xELSEprint xn也可以用漢字偽代碼，如：也可以用漢字偽代碼，如：若若 x為正為正打印打印 x否則否則打印打印 xn也可以中英文混用，如：也可以中英文混用，如：IF x 為正為正pr

25、int xELSEprint xn用偽代碼寫算法并用偽代碼寫算法并無(wú)固定的、嚴(yán)格的語(yǔ)法規(guī)則無(wú)固定的、嚴(yán)格的語(yǔ)法規(guī)則，只，只要把意思表達(dá)清楚，并且書寫的格式要寫成要把意思表達(dá)清楚，并且書寫的格式要寫成清晰易清晰易讀讀的形式。的形式。偽代碼的特點(diǎn)：偽代碼的特點(diǎn)：n偽代碼書寫偽代碼書寫格式比較自由格式比較自由，容易表達(dá)出設(shè)計(jì)者的思，容易表達(dá)出設(shè)計(jì)者的思想。想。n同時(shí)，用偽代碼寫的算法很同時(shí)，用偽代碼寫的算法很容易修改容易修改。n用偽代碼很用偽代碼很容易寫出結(jié)構(gòu)化的算法容易寫出結(jié)構(gòu)化的算法。n但是用偽代碼寫算法但是用偽代碼寫算法不如流程圖直觀不如流程圖直觀，可能會(huì)出現(xiàn)，可能會(huì)出現(xiàn)邏輯上的邏輯上的錯(cuò)誤錯(cuò)

26、誤。軟件專業(yè)人員一般習(xí)慣使用偽代碼，為便于理解，本軟件專業(yè)人員一般習(xí)慣使用偽代碼，為便于理解，本書在以后各章中主要采用形象化的書在以后各章中主要采用形象化的N-S圖表示算法。圖表示算法。2.4.6 用計(jì)算機(jī)語(yǔ)言表示算法用計(jì)算機(jī)語(yǔ)言表示算法n 要完成一件工作，包括要完成一件工作，包括設(shè)計(jì)設(shè)計(jì)算法和算法和實(shí)現(xiàn)實(shí)現(xiàn)算法兩個(gè)算法兩個(gè)部分。部分。n在用流程圖或偽代碼描述出一個(gè)算法后，還要將它在用流程圖或偽代碼描述出一個(gè)算法后，還要將它轉(zhuǎn)換成計(jì)算機(jī)語(yǔ)言程序，才能編譯執(zhí)行。轉(zhuǎn)換成計(jì)算機(jī)語(yǔ)言程序，才能編譯執(zhí)行。 2.5 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法（STRUCTURED PROGRAMING，簡(jiǎn)稱，簡(jiǎn)

27、稱SP）n SP方法主張使用順序、選擇、循環(huán)三種基本結(jié)構(gòu)方法主張使用順序、選擇、循環(huán)三種基本結(jié)構(gòu)來(lái)嵌套連結(jié)成具有復(fù)雜層次的來(lái)嵌套連結(jié)成具有復(fù)雜層次的“結(jié)構(gòu)化程序結(jié)構(gòu)化程序” 。 SP方法是方法是面向過(guò)程面向過(guò)程的設(shè)計(jì)方法。的設(shè)計(jì)方法。n 面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì) (ObjectOrient Programming，OOP) n 結(jié)構(gòu)化程序設(shè)計(jì)方法的結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路基本思路是，把一個(gè)復(fù)雜問(wèn)是，把一個(gè)復(fù)雜問(wèn)題的求解過(guò)程題的求解過(guò)程分階段分階段進(jìn)行，每個(gè)階段處理的問(wèn)題都進(jìn)行，每個(gè)階段處理的問(wèn)題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)?？刂圃谌藗?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。n 結(jié)構(gòu)化程序

28、設(shè)計(jì)的步驟：結(jié)構(gòu)化程序設(shè)計(jì)的步驟：(1) 自頂向下；自頂向下；(2) 逐步逐步細(xì)化；細(xì)化；(3) 模塊化設(shè)計(jì)；模塊化設(shè)計(jì)；(4) 結(jié)構(gòu)化編碼。結(jié)構(gòu)化編碼。n 在接受一個(gè)任務(wù)后應(yīng)怎樣著手進(jìn)行呢在接受一個(gè)任務(wù)后應(yīng)怎樣著手進(jìn)行呢?有兩種不同有兩種不同的方法：的方法：n一種是一種是自頂向下，逐步細(xì)化自頂向下，逐步細(xì)化；n一種是自下而上，逐步積累。一種是自下而上，逐步積累。n 以寫文章為例。如圖以寫文章為例。如圖2.36示意。示意。圖2.36n 顯然，采用顯然，采用“自頂向下，自頂向下， 逐步細(xì)化逐步細(xì)化” 的方法的方法n 考慮周全，結(jié)構(gòu)清晰，層次分明；考慮周全，結(jié)構(gòu)清晰，層次分明；n 如果發(fā)現(xiàn)有需要修改的部分，只需相關(guān)段落即如果發(fā)現(xiàn)有需要修改的部分，只需相關(guān)段落即可，與其他部分無(wú)關(guān)?？?，與其他部分無(wú)關(guān)。n 我們提倡用這種方法設(shè)計(jì)程序，即用我們提倡用這種方法設(shè)計(jì)程序，即用工程的方法工程的方法設(shè)計(jì)程序。設(shè)計(jì)程序。n 在程序設(shè)計(jì)中常采用在程序設(shè)計(jì)中常