程序設(shè)計基礎(chǔ)

1、第1章程序設(shè)計基礎(chǔ)1.1程序設(shè)計基本概念計算機(jī)作為一種智能工具正廣泛地應(yīng)用于人類社會的各行 各業(yè)，它由硬件和軟件組成。本節(jié)將介紹軟件的一些基本概念。1 .程序要利用計算機(jī)來處理問題，就必須要事先編寫出使計算機(jī) 按照人的意愿工作的應(yīng)用程序。所謂程序，就是一系列遵循一 定規(guī)則和思想并能正確完成指定工作的代碼（也稱為指令序列）。通常，一個計算機(jī)程序主要描述兩部分內(nèi)容，第一部分 是描述問題的每個對象及它們之間的關(guān)系，第二部分是描述對這些對象進(jìn)行處理的規(guī)則。 其中關(guān)于對象及它們之間的關(guān)系涉 及數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，而處理規(guī)則是指求解某個問題的算法。因 此，對程序的描述有如下等式：程序=數(shù)據(jù)結(jié)構(gòu)+算法一個設(shè)計合

2、理的數(shù)據(jù)結(jié)構(gòu)往往可以簡化算法，而一個好的 程序有可靠性、易讀性、可維護(hù)性等良好特性。2 .程序設(shè)計所謂程序設(shè)計，就是根據(jù)計算機(jī)要完成的任務(wù)提出相應(yīng)的 需求，并在此基礎(chǔ)上設(shè)計數(shù)據(jù)結(jié)構(gòu)和算法，然后再編寫相應(yīng)的 程序代碼并測試該代碼運(yùn)行的正確性，直到能夠得到正確的運(yùn) 行結(jié)果為止。通常，程序設(shè)計是很講究方法的，一個良好的設(shè) 計思想能夠大大提高程序的高效性和合理性。因此有人提出如下關(guān)系：程序設(shè)計=數(shù)據(jù)結(jié)構(gòu)+算法+程序設(shè)計方法學(xué)任何一個程序必須包含這三方面的內(nèi)容。3 .算法所謂算法，就是問題的求解方法。通常，一個算法由一系 列求解步驟組成。正確的算法要求組成算法的規(guī)則和步驟的意 義是唯一確定的，不能存在二

3、義性，而且這些規(guī)則指定的操作 是有序的，按算法指定的操作順序執(zhí)行能夠在有限的執(zhí)行步驟 后給出正確的結(jié)果。上面提到，算法不允許存在二義性，這是非常重要的，如 果算法存在二義性，那么程序的編碼工作將無法進(jìn)行，同時， 算法也不允許存在模糊的概念， 因?yàn)槎x性和模糊性都是不可 操作的。如“加一噸的水”有明確的概念，這在程序的計算或 控制中是可以操作的，但是如果說“加一些水”，那就無法操 作了，因?yàn)槿粘Ｉ钪?，多少才認(rèn)為是“一些”呢？這就沒有 明確的意義，畢竟程序是根據(jù)人的具體要求來完成相應(yīng)工作 的。通常算法的建立過程是逐步求精的，一般是先給出粗略的 計算步驟框架，然后再對框架中的具體內(nèi)容進(jìn)行逐步細(xì)化，

4、添 加必要的細(xì)節(jié)，使之成為較為詳細(xì)的描述，當(dāng)然，細(xì)化可能做 不到一步到位，因此還要進(jìn)行更進(jìn)一步的細(xì)化，直到能夠把需 求通過編程語言完全描述為止。描述算法的常用工具是流程圖，也稱為程序框圖，流程圖 是算法的圖形描述，它往往比程序更直觀，更容易閱讀和理解。 不過它只是一種表現(xiàn)工具，計算機(jī)并不能直接識別和運(yùn)行流程 圖。4 .數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)對象及其相互關(guān)系和構(gòu)造方法，程序中 的數(shù)據(jù)結(jié)構(gòu)描述了程序中的數(shù)據(jù)間的組織形式和結(jié)構(gòu)關(guān)系。數(shù)據(jù)結(jié)構(gòu)與算法密不可分，一個良好的數(shù)據(jù)結(jié)構(gòu)將使算法簡單化；只有明確了問題的算法，才能較好地設(shè)計出數(shù)據(jù)結(jié)構(gòu)， 因此兩者是相輔相成的。對于計算機(jī)程序而言，其構(gòu)成與數(shù)據(jù) 結(jié)構(gòu)

5、關(guān)系密切，程序在實(shí)現(xiàn)算法的同時，還必須完整地體現(xiàn)作 為算法操作對象的數(shù)據(jù)結(jié)構(gòu)。對于復(fù)雜問題的求解，常常會發(fā) 現(xiàn)由于對數(shù)據(jù)的表示方式和結(jié)構(gòu)的差異，對該問題的抽象求解算法也會完全不同。前面已經(jīng)提到，對同一個問題求解，當(dāng)然 允許有不同的算法，也允許存在不同的數(shù)據(jù)結(jié)構(gòu)，而依不同算 法編寫的操作代碼，其執(zhí)行效率也就不一樣。5 .語言算法不僅要通過具體的語言來表述，還要采用合適的方法 來表達(dá)，才能夠形成程序。可以這樣說，算法是程序的靈魂， 是解決“做什么”和“怎樣做”的問題。一個好的程序必須要有一個合理、高效的算法，數(shù)據(jù)結(jié)構(gòu)是程序要處理的具體對象， 語言是描述算法過程的工具。6 .程序設(shè)計的方法程序設(shè)計方

6、法分為兩大類：面向過程的程序設(shè)計方法和面 向?qū)ο蟮某绦蛟O(shè)計方法。面向過程的程序設(shè)計方法是將完成某項工作的每一個步驟 和具體要求都考慮在內(nèi)來設(shè)計程序， 程序主要用于描述完成這 項工作所涉及的數(shù)據(jù)對象和具體操作規(guī)則，如先做什么、后做 什么、怎樣做、如何做。C語言是一種面向過程的程序設(shè)計語 言。面向?qū)ο蟮某绦蛟O(shè)計方法是將任何事物都看成一個對象， 它們之間通過一定的渠道相互聯(lián)系，對象是活動的、相互對立 的，是可以激發(fā)的，每個對象都是由數(shù)據(jù)和操作規(guī)則構(gòu)成的。 在進(jìn)行程序設(shè)計時，主要針對一個個對象，所有數(shù)據(jù)分別屬于 不同的對象，并被封裝在對象內(nèi)，只要激發(fā)每個對象完成相對 獨(dú)立的操作功能，整個程序就會自然完

7、成全部操作。1.2算法和結(jié)構(gòu)化程序設(shè)計1.2.1 算法的概念做任何事情都有一定的步驟。 為解決一個問題而采取的方法和步驟，就稱為算法。計算機(jī)算法：計算機(jī)能夠執(zhí)行的算法。當(dāng)設(shè)計一個程序時，通常先分析程序中需要的數(shù)據(jù)并對數(shù) 據(jù)進(jìn)行描述，即數(shù)據(jù)結(jié)構(gòu)設(shè)計，然后再根據(jù)功能要求設(shè)計解決 問題的方法，即算法設(shè)計，最后用某種計算機(jī)語言將其描述出 來；同時，為了保證程序有很高的正確性、可靠性、可讀性、 可理解性、可修改性和可維護(hù)性，在整個設(shè)計過程中，還必須 采用科學(xué)的程序設(shè)計方法。因此，可以把程序表示為：程序=數(shù)據(jù)結(jié)構(gòu)+算法+程序設(shè)計方法+ 語言工具和環(huán)境數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)的組織形式，并且必須是允許定義和 使用

8、的數(shù)據(jù)結(jié)構(gòu)。根據(jù)數(shù)據(jù)的性質(zhì)和結(jié)構(gòu)，可以把數(shù)據(jù)定義為 某種數(shù)據(jù)類型；同時利用規(guī)定的數(shù)據(jù)類型，還可以構(gòu)建更復(fù)雜 的數(shù)據(jù)結(jié)構(gòu)，如鏈表、堆棧、樹等。算法指的是解決問題的方 法和步驟；程序設(shè)計語言是全部計算機(jī)指令 （語句）的集合；按 照程序設(shè)計語言的詞法、語法和語義規(guī)則設(shè)計的計算機(jī)指令 （語句）序列就是一個程序，而程序也是計算機(jī)算法的體現(xiàn)。當(dāng) 設(shè)計和編寫程序時，并不是簡單地寫一個程序，而是像一個工 程，為了保證其質(zhì)量，就必須采用科學(xué)的程序設(shè)計方法，程序 設(shè)計方法的種類有很多，主要有結(jié)構(gòu)化程序設(shè)計方法、面向?qū)?象程序設(shè)計方法等。算法設(shè)計是程序設(shè)計的主要步驟，沒有高質(zhì)量的算法就沒 有高質(zhì)量的程序。算法（Al

9、gorithm）指的是解決問題的方法和步驟。一個算術(shù)問題的解題過程、一首樂譜、一份菜譜、一個工作計劃等都是 一個算法。人們在工作和生活中做每件事情都有其特定的步驟 和方法。在現(xiàn)代，特別是計算機(jī)誕生之后,人們把計算機(jī)解題步驟稱為計算機(jī)算法，本書談到的算法，沒有特別說明，指的 就是計算機(jī)算法。1.2.2 算法的特性當(dāng)設(shè)計和使用某個算法時，必然要考慮其是否可行。使用 一個沒有價值的算法是沒有任何意義的。因而，算法具有若干 約束特性，具有約束特性的算法才稱其為算法。著名計算機(jī)科 學(xué)家Knuth在其計算機(jī)程序設(shè)計藝術(shù)一書中詳細(xì)描述了算 法的5個特性：(1)有窮性：算法是一組有窮步驟序列，即一個算法必須

10、在執(zhí)行有窮步驟后結(jié)束。一個算法如果永遠(yuǎn)不能結(jié)束或需要運(yùn) 行相當(dāng)長的時間才能結(jié)束，那么這樣的算法是沒有使用價值 的。(2)確定性：算法中的每一個步驟都必須要有明確的定義 , 不能含糊、不能有歧義。如”青面向前方”就有歧義，因?yàn)椤扒?方”在無任何參照物的參照下，可能是東、南、西、北等的任 何一方。(3)大于等于0個輸入：在算法執(zhí)行過程中可以有 0個或 若干個輸入數(shù)據(jù),即算法處理的數(shù)據(jù)既可以不從外部輸入(內(nèi)部生成)，也可以從外部輸入。少量數(shù)據(jù)適合內(nèi)部生成，而大 量數(shù)據(jù)一般需要從外部輸入， 所以多數(shù)算法中要有輸入數(shù)據(jù)的 步驟。(4)大于等于1個輸出：算法在執(zhí)行過程中必須要有 1個 以上的輸出操作，即算

11、法中必須要有輸出數(shù)據(jù)的步驟。一個沒 有輸出步驟的算法是毫無意義的。(5)可行性：算法中的每一步驟都是可實(shí)現(xiàn)的，即在現(xiàn)有 計算機(jī)上是可執(zhí)行的。如：當(dāng) B是一個很小的實(shí)數(shù)時，A/B在 代數(shù)中是正確的，但在算法中卻是不正確的，因?yàn)樗谟嬎銠C(jī)上無法執(zhí)行，而要使 A/B能正確執(zhí)行，就必須在算法中使 B滿 足條件：|B|> 8,其中8是一個計算機(jī)允許的小的實(shí)數(shù)。一個問題可有若干個不同的可行算法。在不同的算法中有 好算法，也有差算法，如：針對同一問題，執(zhí)行10分鐘的算法 要比執(zhí)行1小時的算法好得多。目前，評價算法質(zhì)量主要有4個基本標(biāo)準(zhǔn)：正確性、可讀性、通用性和高效性。一個好的算 法應(yīng)滿足運(yùn)行結(jié)果正確、

12、可讀性好、可適用一類問題的解決并 執(zhí)行速度快、運(yùn)用時間短、占用內(nèi)存少標(biāo)準(zhǔn)。當(dāng)然，高效性和 可讀性往往是矛盾的，可讀性要優(yōu)先于高效性。目前，在計算 機(jī)速度比較快、內(nèi)存比較大的情況下，高效性已處于次要地位。1.2.3算法的描述對于算法，需要選擇一種合適的描述工具進(jìn)行描述。常用 的描述工具有自然語言、流程圖、N-S圖、偽代碼等。1 .用自然語言描述算法用自然語言描述算法就是選擇某種日常使用的語言（如漢語、英語）來描述算法。使用自然語言描述算法的優(yōu)點(diǎn)是描述 自然、通俗易懂而且靈活多樣，但缺點(diǎn)是容易產(chǎn)生歧義；因此， 在算法設(shè)計中應(yīng)少用或不用自然語言描述算法。通常是在設(shè)計初步算法時適當(dāng)采用自然語言描述,然

13、后還需用其他描述工具細(xì)化算法描述。【例1-1】輸入兩個數(shù)a、b的值，然后交換兩數(shù)的值。算法描述如下。S1:輸入兩個數(shù)a、b的值；S2：使a的值賦給c；S3:使b的值賦給a；S4:使c的值賦給b;S5:輸出a、b的值?！纠?-2】輸入兩個正整數(shù) m和n,求兩數(shù)的最大公約數(shù)。算法描述如下。S1:輸入正整數(shù)m n的值；S2:若m小于n,則交換兩個數(shù)的值；S3:求解m整除n的值，弁賦給r；S4:使n的值賦給mS5:使r的值賦給n；S6:當(dāng)r的值不等于0,轉(zhuǎn)S3繼續(xù)執(zhí)行；否則執(zhí)行S7;S7:輸出兩數(shù)的最大公約數(shù)的值 m【例1-3】輸入一個年份，判定其是否為閏年。閏年判定的條件為：能被 4整除但不能被10

14、0整除的年份是閏年；或者能被100整除又能被400整除的年份是閏年。算法描述如下。S1：輸入一個年份y;S2:若y不能被4整除，則輸出“ y不是閏年”；S3:若y能被4整除，但不能被100整除，則輸出“ y是閏年”；S4:若y既能被100整除，又能被400整除，則輸出“ y是 閏年”；否則輸出“ y不是閏年”。2 .用流程圖描述算法流程圖是采用一些框圖來描述算法的一種工具。美國國家 標(biāo)準(zhǔn)化協(xié)會ANSI和國際標(biāo)準(zhǔn)化組織ISO公布的標(biāo)準(zhǔn) （ISO580785）規(guī)定了流程圖采用的一些框圖，如圖1-1所示。其優(yōu)點(diǎn)是描述簡潔、清晰和直觀，缺點(diǎn)是由于轉(zhuǎn)移箭頭可以無 約束使用，所以會影響算法的可靠性。流程圖

15、由以下幾部分組O Q O O（a）開始結(jié)束框 （b） 處理框 （c）輸入輸出框（d） 判斷框流程線 （g） 注釋框 （h）虛線 （i）連接點(diǎn)圖1-1流程圖中常用框圖開始結(jié)束框：表示流程圖的起點(diǎn)或終點(diǎn)，即開始或結(jié)束，框中給出開始或結(jié)束說明。處理框：表示各種處理功能 ，框中給出處理說明或一組操輸入/輸出框：表示數(shù)據(jù)的輸入或輸出 ，框中給出輸入或輸 出數(shù)據(jù)說明。判斷框：表示一個邏輯判斷，框中給出判斷條件說明或條 件。一般情況有兩個出口 ，分別表示條件的成立或不成立（真或 假、是或否，但在執(zhí)行過程中只有一個出口被激活，如圖 1-2 所示。圖1-2判斷框流程線：表示算法的執(zhí)行方向，且一定為單向線。注釋框

16、：表示對流程圖某一部分的解釋、說明。一般繪制在側(cè)面，如圖1-2所示。虛線：表示被注釋的范圍，如圖1-1所示。連接：表示流程線的斷點(diǎn)（去向或來源），在圖中給出斷點(diǎn) 編號，如圖1-3所示。圖1-3連接示意圖1966年，Bohra和Jacopini提出了三種基本結(jié)構(gòu)：順序結(jié) 構(gòu)、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。(1)順序結(jié)構(gòu)。順序結(jié)構(gòu)是一種最簡單、最基本的結(jié)構(gòu)。在這種結(jié)構(gòu)中，各程序塊按照出現(xiàn)的順序依次執(zhí)行，如圖 1-4 所示，表示A框執(zhí)行完后立即執(zhí)行 B框；它只有一個入口 a和 一個出口 b(2)分支結(jié)構(gòu)。也稱為選擇結(jié)構(gòu)，是根據(jù)給定的條件判斷在兩條可能的路徑中選擇哪一條，如圖1-5所示，若條件P為真時執(zhí)行A框處

17、理，為假時執(zhí)行B框處理；當(dāng)然，A、B框可為 空，但不能同時為空。它只有一個入口 a和一個出口 b。在執(zhí)行 時，只可能執(zhí)行A框或者執(zhí)行B框，不可能既執(zhí)行A框又執(zhí)行 B框；但是無論走哪一路徑，都在 b 口結(jié)束。圖1-4順序結(jié)構(gòu)圖1-5分支結(jié)構(gòu)(3)循環(huán)結(jié)構(gòu)。循環(huán)結(jié)構(gòu)也稱為“重復(fù)處理結(jié)構(gòu)”，包括 當(dāng)型循環(huán)結(jié)構(gòu)和直到型循環(huán)結(jié)構(gòu)。當(dāng)型循環(huán)結(jié)構(gòu)是在滿足給定 條件時反復(fù)執(zhí)行某一程序塊 A,否則不執(zhí)行。如圖1-5(a)所示， 先判斷條件 巳當(dāng)P為真時執(zhí)行A框，A框處理完后再判斷條 件P,當(dāng)P為真時再執(zhí)行A框，循環(huán)往復(fù)，直到判斷條件 P為 假時為止。直到型循環(huán)結(jié)構(gòu)是先執(zhí)行程序塊A,直到滿足給定條件時，不再執(zhí)行。

18、如圖1-5(b)所示，先執(zhí)行A框，A框處理 完后再判斷條件P,當(dāng)P為假時再執(zhí)行A框，如此循環(huán)往復(fù)， 直到判斷條件P為真時為止。從圖中可以看出，循環(huán)結(jié)構(gòu)也只有一個入口 a和一個出口 br1圖1-5循環(huán)結(jié)構(gòu)在這三種基本結(jié)構(gòu)中，有以下 4個共同特征。只有一個入口。只有一個出口。結(jié)構(gòu)中的每一部分都有機(jī)會被執(zhí)行到。結(jié)構(gòu)內(nèi)不存在“死循環(huán)”?，F(xiàn)已證明，由上述三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)可以解決任何復(fù)雜的問題。例1-1例1-3用流程圖表示，分別如圖1-6圖1-8所示圖1-6£=mm=nm=c（開始）/輸出入 b的值/【例1-1】流程圖（開始）r=m%nm=nn=rCED圖1-7【例1-2】流程圖/

19、輸入年份y /由出，不是閏均，/輸出y是閨年/（結(jié)束）圖1-8【例1-3】流程圖3 .用偽代碼圖描述算法偽代碼也稱過程描述語言(Program Design Language ,PDL),是介于自然語言和高級程序設(shè)計語言之間的一種文字和 符號描述工具，它不涉及圖形，和寫文章一樣，一行一行、自 上而下地描述算法，書寫方便，格式緊湊，言簡意賅?！纠?-4】把【例1-3】用偽代碼表示。BEGIN (開始)輸入年份yif y 不被4整除print y:“不是閏年”elseif y 不被100整除print y:“是閏年”elseif y 不被400整除print y:“不是閏年”elseprint y

20、:“是閏年”end ifEND轉(zhuǎn)束)上述是用不同的描述工具描述算法，但要真正被計算機(jī)執(zhí)行，還需要用計算機(jī)語言編寫出算法。用高級語言表示結(jié)構(gòu)化 算法的程序就是一個結(jié)構(gòu)化程序，如下面的例1-5就是用C語言編寫的一個結(jié)構(gòu)化程序?！纠?-5】把【例1-1 用c語言實(shí)現(xiàn)。void main() int a,b,c ；printf( " Please input a,b: " )；scanf( "d %d ,&a,&b);c=a ；a=b ；b=c ；printf("a=%d b=%dn' ,a,b);)1.2.2簡單算法舉例【例1-6】求

21、1X2X3X4X5。最原始方法：步驟1:先求1X2,得到結(jié)果2。步驟2:將步驟1得到的乘積2乘以3,得到結(jié)果6。步驟3:將6再乘以4,得24。步驟4:將2砒乘以5,得120。這樣的算法雖然正確，但太繁。改進(jìn)的算法：S1:使 t=1S2:使 i=253: 使t x i,乘積仍然放在在變量t中，可表示為t x i f t54: 使i的值+1,即i+1 T55: 如果i05,返回重新執(zhí)行步驟S3以及其后的S/DS5;否則，算法結(jié)束。C結(jié)束）用df舌表tk :void main()(int i,t; t=1;i=2;while(i<=5)(t=t*i;i=i+1;)printf( "

22、d ,t);如果計算100 !只需將S5:若i 05改成i w 100即可。如果該求1X3X5X7X9X11,算法也只需做很少的改動：51: 1 ft52: 3 7i53: t Xi ft54: i+2 tS5:若i011,返回S3,否則，結(jié)束。該算法不僅正確，而且是計算機(jī)較好的算法，因?yàn)橛嬎銠C(jī)是高速運(yùn)算的自動機(jī)器，實(shí)現(xiàn)循環(huán)輕而易舉。思考：若將S5寫成：55: 若i <11,返回S3;否則，結(jié)束。結(jié)果如何？【例1-7】有50個學(xué)生，要求將他們之中成績在 80分以上者打 印出來。如果，n表示學(xué)生學(xué)號，ni表示第個學(xué)生學(xué)號；g表示學(xué)生成績，gi表示第個學(xué)生成績；則算法可表示如下：51: 1 fi52: 如果gi > 80,則打印ni和gi ,否則不打印53: i+1 - i S4:若i050,返回S2,否則，結(jié)束。Ill1 1【例1-8】求299 100.算法可表示如下：51: sigh=152: sum=153: deno=254: sigh=(- 1) x sigh55: term= sigh x (1/den