c程序設(shè)計新視角 周幸妮編第1章

1、1 1第1章 走馬觀花看編程1.1 程序的概念程序的概念1.2 計算機解題過程計算機解題過程1.3 編制程序的全過程編制程序的全過程1.4 程序的構(gòu)成程序的構(gòu)成1.5 算法是如何設(shè)計出來的算法是如何設(shè)計出來的1.6 簡單的簡單的C程序介紹程序介紹1.7 本章小結(jié)本章小結(jié)2 2【主要內(nèi)容】 程序的概念； 算法設(shè)計方法； 程序設(shè)計方法； 簡單的C程序介紹。3 3【學(xué)習(xí)目標(biāo)】 理解程序設(shè)計的基本步驟； 能夠用自頂向下、逐步求精的方法確定算法。4 4為了使計算機能夠按人的意圖工作，人類就必須要將需要解決問題的思路、方法和手段，通過計算機能夠理解的形式告訴它，使得計算機能夠根據(jù)人的指令一步一步去工作，完

2、成特定的任務(wù)。1.1 程程序序的的概概念念5 5編程就是讓計算機為解決某個問題而使用某種程序設(shè)計語言編寫程序代碼，并最終得到結(jié)果的過程。 程序：為了讓計算機解決特定問題而專門設(shè)計的一系列計算機可執(zhí)行的指令集合。 程序設(shè)計語言：即Programming Language，是用于書寫計算機程序的語言。 C語言：Combined Language(組合語言)的中英文混合簡稱，是一種計算機高級語言。6 6 計算機語言計算機語言的種類非常多，總的來說可以分成機器語言、匯編語言和高級語言三大類。目前通用的編程語言有兩種：匯編語言和高級語言。7 71. 機器語言由于計算機內(nèi)部只能處理二進制代碼，因此，用二進

3、制代碼0和1描述的指令稱為機器指令。全部機器指令的集合構(gòu)成計算機的機器語言。用機器語言編寫的程序稱為目標(biāo)程序。只有目標(biāo)程序才能被計算機直接識別和執(zhí)行。但是用機器語言編寫的程序無明顯特征，難以記憶，不便閱讀和書寫，且依賴于具體機種，局限性很大。機器語言屬于低級語言。8 82. 匯編語言匯編語言的實質(zhì)和機器語言是相同的，都是直接對硬件操作，只不過其指令采用了英文縮寫的標(biāo)識符，更容易識別和記憶。它同樣需要編程者將每一步具體的操作用命令的形式寫出來。匯編源程序一般比較冗長、復(fù)雜、容易出錯，而且使用匯編語言編程需要有更多的計算機專業(yè)知識。但匯編語言的優(yōu)點也是顯而易見的，用匯編語言所能完成的操作不是一般高

4、級語言所能實現(xiàn)的，而且源程序經(jīng)匯編生成的可執(zhí)行文件不僅比較小，而且執(zhí)行速度很快。9 93. 高級語言高級語言是目前絕大多數(shù)編程者的選擇。和匯編語言相比，它不但將許多相關(guān)的機器指令合成為單條指令，并且去掉了與具體操作有關(guān)但與完成工作無關(guān)的細節(jié)，這樣就大大簡化了程序中的指令，編程者也就不需要有太多的計算機硬件知識。高級語言主要是相對于匯編語言而言的，它并不是特指某一種具體的語言，而是包括了很多編程語言，如目前流行的VB、C+、Delphi等，這些語言的語法、命令格式都各不相同。 10 10用高級語言所編制的程序不能直接被計算機識別，必須經(jīng)過轉(zhuǎn)換才能被執(zhí)行。按轉(zhuǎn)換方式可將它們分為兩類：(1) 解釋類

5、：執(zhí)行方式類似于我們?nèi)粘Ｉ钪械摹巴暦g”。應(yīng)用程序源代碼一邊由相應(yīng)語言的解釋器“翻譯”成目標(biāo)代碼(機器語言)，一邊執(zhí)行，因此效率比較低，而且不能生成可獨立執(zhí)行的可執(zhí)行文件，應(yīng)用程序不能脫離其解釋器。但這種方式比較靈活，可以動態(tài)地調(diào)整、修改應(yīng)用程序。(2) 編譯類：編譯是指在應(yīng)用源程序執(zhí)行之前，就將程序源代碼“翻譯”成目標(biāo)代碼(機器語言)，11 11因此其目標(biāo)程序可以脫離其語言環(huán)境獨立執(zhí)行，使用比較方便，效率較高。但應(yīng)用程序一旦需要修改，必須先修改源代碼，再重新編譯生成新的目標(biāo)文件(*.OBJ)才能執(zhí)行，如果只有目標(biāo)文件而沒有源代碼，則修改很不方便。現(xiàn)在大多數(shù)的編程語言都是編譯型的，例如C/

6、C+、Delphi等。12 12 軟件與程序的關(guān)系常常聽到這樣的說法，編程(Programming)就是編寫軟件。但程序與軟件在概念上是有區(qū)別的。軟件應(yīng)該包含以下三個方面的含義：13 13(1) 運行時，能夠提供所要求功能和性能的指令或計算機程序集合。(2) 程序能夠滿意地處理信息的數(shù)據(jù)結(jié)構(gòu)。(3) 描述程序功能需求以及程序如何操作和使用所要求的文檔。所以可以認為：軟件=程序+數(shù)據(jù)+文檔14 14從“加工”的角度看，計算機解題的過程可以分成三個步驟，如圖1.1所示。先由系統(tǒng)分析員根據(jù)實際問題建立數(shù)學(xué)模型，當(dāng)這個模型不完全適合計算機時，還要將它轉(zhuǎn)換成計算機能夠“接受”的模型，做這個轉(zhuǎn)換的工作需要

7、有數(shù)據(jù)結(jié)構(gòu)的知識。解題模型建立后，程序員根據(jù)它編制程序，再交由計算機執(zhí)行，得到最終的結(jié)果。1.2 計算機解題過程計算機解題過程15 15圖1.1 計算機解題過程16 16編制程序有三個基本的步驟：定算法、編程序、調(diào)試通。(1) 定算法確定算法：先要明確實際問題要求完成的功能是什么，它要處理的信息有哪些(這些信息是要輸入到計算機中的)；計算機對上述信息處理完畢，實現(xiàn)了指定的功能后，結(jié)果是什么，即輸出的信息有哪些；計算機完成指定功能的具體步驟是什么。1.3 編制程序的全過程編制程序的全過程17 17(2) 編程序代碼實現(xiàn)：根據(jù)前面確定的算法，編寫相應(yīng)的程序代碼。(3) 調(diào)試通調(diào)試通過：在IDE中，

8、將編好的程序通過編譯器翻譯成機器碼，這個過程叫做“編譯”。(注：IDE(Integrated Development Environment)即集成開發(fā)環(huán)境軟件，是用于程序開發(fā)環(huán)境的應(yīng)用程序，一般包括代碼編輯器、編譯器、調(diào)試器和圖形用戶界面工具。該程序可以獨立運行，也可以和其他程序并用。)18 18在編譯過程中，編譯器可以查找程序中的語法錯誤，當(dāng)沒有語法錯誤后，生成后綴為OBJ的目標(biāo)文件；若程序是由多個OBJ組合而成的，則還要把這多個OBJ文件進行鏈接，最后形成一個后綴為EXE的可執(zhí)行文件，這時，就算是編寫好了一個可以在計算機上運行(Run)的程序了。試著運行一下這個程序，計算機會嚴格按照用戶

9、編寫的指令一步步執(zhí)行下去。此時可以去看運行的結(jié)果，若結(jié)果和預(yù)設(shè)的一致，那就完成了任務(wù)。19 19但事情往往沒那么簡單，除非是很簡單的程序，一個很有經(jīng)驗的程序員也不能保證程序首次運行就得到正確的結(jié)果。為什么會這樣呢，編譯完成，程序不是已經(jīng)沒有語法錯誤了嗎？沒有語法錯是程序可以運行的前提，但程序中還會有一種叫做“邏輯錯”的錯誤，它會造成運行結(jié)果的不正確。邏輯錯是需要程序員自己去查找的。找邏輯錯的工作叫做程序調(diào)試，這是一個很需要耐心和專注力的工作，難度往往比編程還要大。調(diào)試的基本方法將在第10章“程序調(diào)試及測試”中專門介紹。2020 程序的邏輯錯程序的邏輯錯主要表現(xiàn)在程序運行后，得到的結(jié)果與預(yù)期設(shè)想

10、的不一致,這就有可能是出現(xiàn)了邏輯錯。比如運算應(yīng)該是先加后乘的處理，如果忘了加括號，運算結(jié)果就會出現(xiàn)錯誤。通常出現(xiàn)邏輯錯的程序都能正常運行，系統(tǒng)不會給出錯誤在哪里的提示信息。21 21如果把數(shù)據(jù)和程序語句看成是原料，程序結(jié)構(gòu)和算法是制作方法和工藝要求，則程序就是最后加工出來的產(chǎn)品，如圖1.2所示。1.4 程程序序的的構(gòu)構(gòu)成成2222圖1.2 程序加工處理示意圖2323程序由程序語句(有一定的語法規(guī)則)和數(shù)據(jù)(要處理的信息)組成，是在符合程序結(jié)構(gòu)的構(gòu)造框架(有一定之規(guī))下，按照事先設(shè)計的完成特定功能要求的執(zhí)行步驟(算法)最終完成的指令序列，將其寫成一般的形式如圖1.3所示。圖1.3 程序組成242

11、4算法是程序的靈魂，用于解決“做什么”、“怎么做”的問題；數(shù)據(jù)是加工的對象；程序結(jié)構(gòu)是設(shè)計方法；語言是工具。25251.4.1 程序的構(gòu)成成分之一數(shù)據(jù)數(shù)據(jù)：計算機可“表現(xiàn)”、“存儲”、“運算”的信息。數(shù)據(jù)的表現(xiàn)形式：常量和變量；數(shù)據(jù)的存儲尺寸：由類型決定；數(shù)據(jù)的運算方式：通過運算符實施。1程序中的數(shù)據(jù) 程序中的數(shù)據(jù)是指計算機可接收，即可存儲到計算機中，并可對其進行加工處理的信息。2626 計算機中的數(shù)據(jù)在計算機中，各種信息如數(shù)字、字符、聲音、圖像等都是以二進制編碼方式存儲的。下面介紹編程中相關(guān)的數(shù)據(jù)知識。27271. 數(shù)據(jù)的存儲單位數(shù)據(jù)的存儲單位見表1.1。表1.1 數(shù)據(jù)的存儲單位一個位(bi

12、t)有多大？位是內(nèi)存的最小單位。二進制數(shù)系統(tǒng)中，每個0或1就是一個位。28282. ASCII碼ASCII碼(American Standard Code for Information Interchange，美國標(biāo)準(zhǔn)信息交換碼)是基于拉丁字母的一套電腦編碼系統(tǒng)。它主要用于顯示現(xiàn)代英語和其他西歐語言。它是現(xiàn)今最通用的單字節(jié)編碼系統(tǒng)。ASCII 碼使用指定的7 位或8 位二進制數(shù)組合來表示128 或256 種可能的字符。標(biāo)準(zhǔn)ASCII 碼也叫基礎(chǔ)ASCII碼，使用7 位二進制數(shù)來表示所有的大寫和小寫字母、數(shù)字09、標(biāo)點符號以及在美式英語中使用的特殊控制字符。2929256種字符中的后128個字

13、符稱為擴展ASCII碼，目前許多基于x86的系統(tǒng)都支持使用擴展(或“高”)ASCII碼。擴展ASCII 碼允許將每個字符的第8 位用于確定附加的128 個特殊符號字符、外來語字母和圖形符號。30303. 漢字編碼為漢字設(shè)計的一種便于輸入計算機的代碼。計算機中漢字的表示也是用二進制編碼，同樣是人為編碼的。根據(jù)應(yīng)用目的的不同，漢字編碼分為外碼、交換碼、機內(nèi)碼和字形碼。 1981年，國家標(biāo)準(zhǔn)局公布了信息交換用漢字編碼字符集基本集(簡稱漢字標(biāo)準(zhǔn)交換碼)，其中共收錄了6763個漢字。這種漢字標(biāo)準(zhǔn)交換碼是計算機的內(nèi)部碼，可以為各種輸入/輸出設(shè)備的設(shè)計提供統(tǒng)一的標(biāo)準(zhǔn)，使各種系統(tǒng)之間的信息交換有共同一致性，從

14、而使信息資源的共享得以保證。31 312數(shù)據(jù)的表現(xiàn)形式常量和變量在許多問題中，都會有有些量固定不變，有些量不斷變化的情形。如物體運動中的速度、時間和距離，圓的半徑、周長和圓周率，購買商品的數(shù)量、單價和總價等。數(shù)據(jù)在程序中的表現(xiàn)形式有兩種：常量和變量。常量是在程序運行過程中，值不能被改變的量；變量是在程序運行過程中，值能被改變的量。C語言中會給變量起一個名字，在內(nèi)存中給它分配一個存儲單元，用來存儲它的值。3232變量的起名和分配存儲單元都是在一個稱做“變量定義”的語句中完成的，存儲變量的值如果在定義時指定，則稱做是對變量進行初始化。初始化：在變量定義時對變量進行賦值的操作。變量沒有初始化，那么它

15、的存儲單元里會是什么數(shù)？答案會在第2章中給出。3333為什么要用變量？答：程序要解決的問題往往是通解。比如，計算n！的程序，n=5時，能給出正確結(jié)果；n=10時，也應(yīng)該能給出正確結(jié)果，即只要輸入的n為一定范圍的正整數(shù)，那么程序都應(yīng)該能計算出結(jié)果，這樣的程序才有實際的意義。34343數(shù)據(jù)的存儲尺寸由類型決定數(shù)據(jù)在機器中存放，需要一定的內(nèi)存空間，變量在內(nèi)存中給它分有存儲單元，那么這個存儲單元的大小是多少呢？實際的情形應(yīng)該是，程序員根據(jù)數(shù)據(jù)實際需要占多少位(bit)，來向計算機系統(tǒng)申請分配相應(yīng)大小的存儲單元。C語言根據(jù)數(shù)據(jù)的各種情形，把它們分成不同的類型，如表1.2所示。3535表1.2 數(shù) 據(jù) 類

16、 型3636不同類型的數(shù)據(jù)對應(yīng)的存儲單元的大小是不同的，計算機系統(tǒng)提供了不同“規(guī)格尺寸”的空間大小基本數(shù)據(jù)類型，構(gòu)造類型是由基本類型組合而成的。變量存儲單元的大小是由其數(shù)據(jù)類型決定的，程序員可以根據(jù)需要選用。為什么要有各種數(shù)據(jù)類型？答： 可解決數(shù)據(jù)的有效存儲空間問題； 不同類型的數(shù)據(jù)其處理規(guī)則、方式不相同。37374數(shù)據(jù)的運算方式通過運算符實施對數(shù)據(jù)的加工處理是通過各種運算符來實施的。C語言中的各種運算符見表1.3，具體使用方法會在第2章中介紹。3838表1.3 C語言中的運算符39391.4.2 程序的構(gòu)成成分之二程序語句程序語句：向機器發(fā)出的操作指令。語句由語句命令字、數(shù)據(jù)、運算符等構(gòu)成。

17、語句命令字有三類，見表1.4。選擇及循環(huán)語句的功能及用法將在第3章中介紹，函數(shù)return語句將在第5章中介紹。4040表1.4 語句命令字41 41圖1.4 順序結(jié)構(gòu)42421.4.3 程序的構(gòu)造框架程序結(jié)構(gòu)任何程序都可由順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)構(gòu)造而成。1順序結(jié)構(gòu)順序結(jié)構(gòu)是最簡單的程序結(jié)構(gòu)，語句按照事前排好的順序，順次執(zhí)行。如圖1.4中，A語句和B語句是依次執(zhí)行的，只有在執(zhí)行完A語句后，才能接著執(zhí)行B語句。A語句和B語句可以是一條語句或一組語句。43432選擇結(jié)構(gòu)在處理實際問題時，只有順序結(jié)構(gòu)是不夠的，經(jīng)常會遇到一些條件的判斷，流程根據(jù)條件是否成立有不同的流向。如圖1.5所示，程序

18、根據(jù)給定的條件Q是否成立而選擇執(zhí)行A操作或B操作。先進行條件Q的判斷，成立，轉(zhuǎn)向Y(Yes)分支；否則，轉(zhuǎn)向N(No)分支。4444圖1.5 選擇結(jié)構(gòu)4545C語言從機制上提供了三類選擇語句，來實現(xiàn)選擇結(jié)構(gòu)的功能。(1) 單路選擇：If(表達式) 語句 A；(2) 雙路選擇：If(表達式)語句 A；else 語句 B；(3) 多路選擇：4646Switch(表達式)case 常量1：語句 A；case 常量2：語句 B；default：語句 C；47473循環(huán)結(jié)構(gòu)需要重復(fù)執(zhí)行同一操作的結(jié)構(gòu)稱為循環(huán)結(jié)構(gòu)，即從某處開始，按照一定條件反復(fù)執(zhí)行某一處理步驟。在解決一些問題時，經(jīng)常需要重復(fù)執(zhí)行一些操作，

19、我們可以利用循環(huán)結(jié)構(gòu)控制程序按照一定的條件或者次數(shù)重復(fù)執(zhí)行。循環(huán)結(jié)構(gòu)有當(dāng)型循環(huán)和直到型循環(huán)兩類形式，如圖1.6所示。4848圖1.6 循環(huán)結(jié)構(gòu)4949 循環(huán)體：反復(fù)執(zhí)行的處理步驟稱為循環(huán)體。 當(dāng)型循環(huán)：當(dāng)條件Q成立時，執(zhí)行語句A，然后再判斷條件Q是否成立，如此循環(huán)，直到Q不滿足，退出循環(huán)。 直到型循環(huán)：先執(zhí)行語句A，然后再判斷條件Q是否成立，如此循環(huán)，直到Q不滿足，退出循環(huán)。C語言從機制上提供了四類循環(huán)語句，來實現(xiàn)循環(huán)結(jié)構(gòu)的功能。5050(1) 形式一：while (表達式) 語句;(2) 形式二：do 語句 ; while (表達式)；(3) 形式三：for(表達式1;表達式2;表達式3)

20、語句;(4) 形式四：if (表達式) goto51 511.4.4 程序的構(gòu)造方法算法有兩種思想，像放在天鵝絨上的寶石一樣熠熠生輝，一個是微積分，另一個就是算法。微積分以及在微積分基礎(chǔ)上建立起來的數(shù)學(xué)分析體系造就了現(xiàn)代科學(xué)，而算法造就了現(xiàn)代世界。 David Berlinski(算法的出現(xiàn)的作者)52521.算法的概念 算法(algorithm)：為解決一個問題而采取的方法和步驟。 計算機算法：計算機能夠執(zhí)行的算法。算法可以理解為由基本運算及規(guī)定的運算順序所構(gòu)成的完整的解題步驟，或者看成按照要求設(shè)計好的有限的確切的計算序列，并且這樣的步驟和序列可以解決一類問題。5353計算機算法解題的方法和

21、步驟要符合計算機的特點，即每一步都很簡單，可以不厭其煩地執(zhí)行簡單的步驟。計算機解題也具有一定的局限性，有時日?？尚械姆桨?，在計算機中卻無法實現(xiàn)。54542算法的表示方法1) 算法的表示方法1流程圖流程圖是用一些圖框表示各種操作。用圖形表示算法直觀形象，易于理解。美國國家標(biāo)準(zhǔn)化協(xié)會ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號，如圖1.7所示。5555圖1.7 流程圖符號56562) 算法的表示方法2N-S圖N-S圖是無線的流程圖，又稱盒圖，1973年由美國學(xué)者I.Nassi和B.Shneiderman提出。N-S圖對三種基本程序結(jié)

22、構(gòu)的描述方法如圖1.8所示。5757圖1.8 N-S圖表示法58583) 算法的表示方法3偽代碼偽代碼(Pseudocode)：用代碼的格式表示程序執(zhí)行過程和算法，但不能在編譯器上通過編譯的代碼。其目的是用易于理解和表述的方式展示程序的執(zhí)行過程。偽代碼是不依賴于具體程序語言的，它只是用程序語言的結(jié)構(gòu)形式來表示程序執(zhí)行過程。用偽代碼描述算法，可以使用任何一種用戶熟悉的文字，關(guān)鍵是把程序的執(zhí)行意圖表達出來。5959 偽代碼偽代碼又稱虛擬代碼，是高層次描述算法的一種方法。它不是一種現(xiàn)實存在的編程語言，它可能綜合使用多種編程語言的語法、保留字，甚至?xí)玫阶匀徽Z言。偽代碼以編程語言的書寫形式指明算法的職

23、能。相比于程序語言(如Java、C+、C、Delphi 等)它更類似自然語言。我們可以將整個算法運行過程的結(jié)構(gòu)用接近自然語言的形式描述出來。6060這里用戶可以使用任何一種熟悉的文字，如中文或英文等，關(guān)鍵是把程序的意思表達出來。使用偽代碼，可以幫助我們更好地表述算法，不用拘泥于具體的實現(xiàn)。人們在用不同的編程語言實現(xiàn)同一個算法時意識到，他們的實現(xiàn)(注意：是實現(xiàn)，不是功能)往往是不同的，尤其是對于那些熟練于某種編程語言的程序員來說，要理解一個用其他編程語言編寫的程序的功能可能很困難，因為程序語言的形式限制了程序員對程序關(guān)鍵部分的理解。偽代碼就這樣應(yīng)運而生了。61 61當(dāng)考慮算法功能(而不是其語言實

24、現(xiàn))時，常常應(yīng)用偽代碼。計算機科學(xué)在教學(xué)中通常使用偽代碼，以使得所有的程序員都能理解。6262【例1-1】 偽代碼的例子。下面是“清晨上課準(zhǔn)備”的兩種算法：由上面的例子可以看出，第二種算法明顯不合理，所以，算法不僅要確定正確的執(zhí)行動作，還要確定正確的動作執(zhí)行的順序。63633算法的闡述方法(1) 程序的質(zhì)量首先取決于它的結(jié)構(gòu)。(2) 程序設(shè)計的基本方法是自頂向下地逐步求精和模塊化。 64641. 結(jié)構(gòu)化程序設(shè)計 結(jié)構(gòu)化程序設(shè)計(Structured Programming)是以模塊功能和處理過程設(shè)計為主的詳細設(shè)計的基本原則。其概念最早是由E.W.Dijikstra在1965年提出的，是軟件發(fā)展

25、的一個重要的里程碑。它的主要觀點是：采用自頂向下、逐步求精的程序設(shè)計方法；使用三種基本控制結(jié)構(gòu)構(gòu)造程序，即任何程序都可由順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)構(gòu)造。結(jié)構(gòu)化程序設(shè)計主要強調(diào)的是程序的易讀性。65652. 自頂向下逐步細化程序設(shè)計時，應(yīng)先考慮總體，后考慮細節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求眾多的細節(jié)，先從最上層總目標(biāo)開始設(shè)計，逐步使問題具體化。對復(fù)雜問題，應(yīng)設(shè)計一些子目標(biāo)作為過渡，逐步細化。 用這種方法設(shè)計程序，似乎復(fù)雜，實際上優(yōu)點很多，可使程序易讀、易寫、易調(diào)試、易維護、易保證其正確性及驗證其正確性，在程序設(shè)計領(lǐng)域引發(fā)了一場革命，成為程序開發(fā)的一個標(biāo)準(zhǔn)方法，尤其是

26、在后來發(fā)展起來的軟件工程中獲得了廣泛應(yīng)用。66663. 模塊化設(shè)計 一個復(fù)雜問題，一般是由若干稍簡單的問題構(gòu)成的。模塊化是把程序要解決的總目標(biāo)分解為子目標(biāo)，再進一步分解為具體的容易實現(xiàn)的小目標(biāo)，每一個小目標(biāo)被稱為一個模塊。67674算法的特性算法應(yīng)具有以下五個重要特性：(1) 輸入性：一個算法有零個或多個輸入。(2) 輸出性：一個算法有一個或多個輸出，且輸出是與輸入有著某些特定關(guān)系的量。(3) 有窮性：一個算法必須在執(zhí)行有窮步之后結(jié)束，且每條指令的執(zhí)行次數(shù)有限。(4) 確定性：算法中每條指令必須確切定義且含義明確，不可有二義性；對于相同的輸入只能得出特定的結(jié)果。6868(5) 可行性：算法中描

27、述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的，即每條指令都應(yīng)在有限的時間內(nèi)完成。69691.5.1 算法與計算機算法我們在日常生活中解決問題的方式方法，有時卻不能直接用到計算機中?！纠?-2】 算法的例子1。將兩個存儲單元的數(shù)據(jù)A、B互換，且互換后的數(shù)據(jù)不損失?！窘狻?(1) 通用法：借助第三個存儲單元，分別按圖1.9中、的順序移動即可。1.5 算法是如何設(shè)計出來的算法是如何設(shè)計出來的7070圖1.9 數(shù)據(jù)交換71 71(2) 另類法：具體可采用以下幾種方法。高空拋物法：把A、B想象成物體，像雜耍一般，將A、B“拋向空中”，然后交換位置。 管子運輸法：把兩個存儲單元用兩個“管道”連

28、接起來，分別輸送A、B至對方單元。原地挪空法：假設(shè)A、B所在的單元空間足夠大，這樣可以把B先放到A所在的單元，然后把A移動到B原先所在的單元。7272對于通用法和另類法，在現(xiàn)實世界里，一定條件下都是可行的，但在計算機世界里，通用法是可以的，另類法中的“原地挪空”在一定條件下也是可行的，其他的方法就是強計算機所難了?！舅惴ńY(jié)論1】 有時在日常能行得通的方法，在計算機中是無法實現(xiàn)的。73731.5.2 算法的通用性現(xiàn)代計算機(20世紀(jì)40年代開始)在誕生之初常被冠以“通用”字樣，以突出其通用性。什么是適合計算機實現(xiàn)的方法呢？那就是規(guī)則要簡單，并對所有的數(shù)據(jù)處理，其操作規(guī)則要“通用”。軟件調(diào)試張銀奎

29、 【例1-3】 算法的例子2。小學(xué)生的除法問題：只考慮兩位數(shù)除以一位數(shù)，且商為一位數(shù)的情形。如：234=53 376=617474對于人腦來說，小學(xué)老師教的試商方法巧妙快捷；但對于計算機來說，小學(xué)老師教的試商方法實現(xiàn)起來還是很復(fù)雜。7575其中：A(被除數(shù))為兩位數(shù)，B(除數(shù))、T(商)、R(余數(shù))均為一位數(shù)?！痉桨敢弧?一律從9開始試商法。我們先用偽代碼的方式來表述處理問題的思路。表1.5給出了方案一的頂部偽代碼描述。7676表1.5 例1-3方案一偽代碼17777圖1.10 頂部偽代碼流程7878寫頂部偽代碼，是把問題及你想要對它進行處理的方法簡要地描述一下，后面的細化可以逐步進行，直至可

30、以方便地寫成程序的形式為止。頂部偽代碼對應(yīng)的流程圖如圖1.10所示。由頂部的偽代碼還無法直接寫出寫出程序，可以再把其中的步驟更進一步地細化描述。表1.6和表1.7給出了方案逐步細化的過程，相應(yīng)的流程圖如圖1.11、圖1.12所示。7979表1.6 例1-3方案一偽代碼28080圖1.11 第一步細化對應(yīng)流程81 81表1.7 例1-3方案一偽代碼28282圖1.12 第二步細化對應(yīng)流程8383處理問題一般分為下面三個階段：(1) 開始的工作：先從9開始試商，然后再細化，要考慮9放在哪里，而且應(yīng)該在程序一開始就得到這個值。(2) 中間處理過程：試商找到合適的結(jié)果；第一步細化為商T與除數(shù)B的乘積，

31、再與被除數(shù)A相比，若商T大，則減1再試，直到滿足B*TA)成立，則循環(huán)執(zhí)行商T的值減1的操作，直到上述條件不滿足，循環(huán)操作停止。(3) 得到結(jié)果：確定最后得到的結(jié)果是哪些項。表1.8中給出了圖1.12 第二步細化對應(yīng)流程圖的逐步執(zhí)行分析步驟。8484表1.8 結(jié)果分析表8585表1.8中的第一列，商T的初始值為9，B為常量4，A為常量23，對條件B*TA是否成立進行判斷。首次B*T為36，故B*TA成立，流程執(zhí)行“yes”分支，T的值減1，變成8(到表格第二列)，再回到條件B*TA的判斷，這樣循環(huán)下去，直到B*TA不成立，流程執(zhí)行“no”分支，輸出結(jié)果后，流程結(jié)束。繪制圖表是調(diào)試過程中任何時候

32、都能使用的啟發(fā)方式。 軟件調(diào)試思想Robert Charles Metzger 8686下面，再給出問題的第二種解法被除數(shù)連續(xù)減除數(shù)，這樣便于比較。同一問題，解題方法可以不同，而表述方式卻是類似的?！痉桨付?被除數(shù)連續(xù)減除數(shù)。本方案的偽代碼細化過程見表1.9表1.11。機器解決問題的特點之一是按部就班，本次計算往往要用到上一次的結(jié)果。8787表1.9 例1-3方案二偽代碼18888表1.10 例1-3方案二偽代碼28989表1.11 例1-3方案二偽代碼39090圖1.13 被除數(shù)連續(xù)減91 91表1.12中列出了處理流程中，每一步執(zhí)行時變量R、T的值的變化和條件R B的判斷結(jié)果。表1.12

33、 運行結(jié)果分析9292【算法結(jié)論2】 日常看似“巧”的方法，對機器而言，不一定是好方法。1.5.3 算法的全面性【例1-4】 算法的例子3。求n！。【解】 為分析問題方便，此處設(shè)n=5。人工計算5！=1*2*3*4*5的通用方法的步驟見表1.13。這里即使是人來計算階乘，也強調(diào)了“通用”的方法，而不是用“巧”的速算的方法，這樣就是用“程序的思維”來看問題了。9393表1.13 n！的計算步驟分析下面再來分析機器計算5！的通用方法。計算機需要知道的信息：(1) 運算方法：乘法。(2) 運算數(shù)據(jù)：1、2、3、4、5。9494如何讓計算機得到上面的運算數(shù)據(jù)呢？答：其實計算機是“很笨”的，你要讓它處理

34、的所有數(shù)據(jù)、所用方法，一點一滴都要你“手把手”地交給它，不然它什么都不會做。方法一：每個數(shù)都可以通過鍵盤輸入到計算機中。方法二：除了1之外，每個數(shù)都是前一個數(shù)加1而來，或者說迭代而來的。9595對于方法一，當(dāng)數(shù)據(jù)較少時可以采用，數(shù)據(jù)多了就顯得很麻煩。方法二則是一個比較好的辦法。 遞推(迭代)法遞推法是指根據(jù)問題的遞推關(guān)系，由已知項，經(jīng)過有限次的遞推迭代，得到待求的未知項。凡是具有遞推公式的一類數(shù)值問題，都可以用迭代法來求解。9696迭代步驟：(1) 列出問題的已知項； (2) 根據(jù)問題的關(guān)系，寫出遞推公式； (3) 對遞推公式進行有限次的遞推迭代，直到待求的未知項，即為所解。根據(jù)n！的計算步驟

35、特點、運算的方法、運算數(shù)據(jù)的獲得方式等，可以寫出計算n！的偽代碼，參見表1.14表1.16。9797表1.14 例1-4偽代碼19898表1.15 例1-4偽代碼2圖1.14所示為求5!的流程，執(zhí)行循環(huán)后變量S和T的變化見表1.17。9999表1.16 例1-4偽代碼3100100圖1.14 求5！的流程101101表1.17 執(zhí)行流程數(shù)據(jù)分析在對5！處理完畢后，從程序的通用性方面還需要考慮一些問題。102102(1) 要計算10！，怎么辦呢？(2) 計算1！時，結(jié)果對嗎？(3) 若要分別計算許多整數(shù)的階乘怎么辦呢？答：問題(1)：可以把圖1.14中的判斷T5改為T10。問題(2)：圖1.14

36、中，計算1！結(jié)果為2，顯然是錯誤的。103103問題(3)：可以把圖1.14中的判斷T5改為Tn，n設(shè)為整數(shù)，可以通過輸入得到n的具體值。在考慮了上述所有問題之后，可以對圖1.14所示的流程進行改進，得到如圖1.15所示的處理流程。討論到此，是不是此問題的解決方案就完善了呢？104104圖1.15 求n！改進的處理流程105105若用戶輸入 n=-1，怎么辦呢？答：當(dāng)用戶有意或無意當(dāng)中輸入了“非法”的數(shù)據(jù)時，程序應(yīng)該有合適的應(yīng)對方法，而不能對此“束手無策”。程序應(yīng)該驗證所有輸入的合法性，以防錯誤信息影響程序的計算。改進后的最終流程如圖1.16所示。106106圖1.16 求n！最終改進流程10

37、7107 【算法結(jié)論3】 算法設(shè)計的一般步驟：(1) 按問題的普遍規(guī)律給出處理的流程。(2) 設(shè)定初始值。(3) 確定程序結(jié)束的條件。(4) 考慮臨界點或特殊點的處理。(5) 考慮異常情況。108108說明：(1) 先按問題的普遍規(guī)律給出處理的流程。對n！而言，根據(jù)它的數(shù)學(xué)定義，可以先找一個一般情形且規(guī)模不太大的值比如5，來考慮算法的實現(xiàn)。(2) 設(shè)定初始值。計算5！，它的起始條件是從1*1開始計算。(3) 確定程序結(jié)束的條件。計算5！，乘數(shù)為5時結(jié)束。109109(4) 考慮臨界點或特殊點的處理。0和1是n！的特例情形，對這些特別“點”的處理，是先把它們作為輸入的數(shù)據(jù)，去測試前面已經(jīng)構(gòu)建好的

38、算法。若測試通過，則程序合格；若沒有通過，再做局部的修改，直至達到預(yù)定的功能。(5) 考慮異常情況。對n！，應(yīng)該對輸入為n0的“非法”情形做限定性處理，以防錯誤信息影響程序的計算。1101101.5.4 算法的驗證從前面做算法的一般性步驟中可以看到，對于做好的算法，它是否完善及能否達到預(yù)期的目標(biāo)，是要經(jīng)過驗證的。對于算法的驗證，要設(shè)計出合適的測試用例，我們可以借鑒軟件測試的一般性方法。測試用例的設(shè)計，應(yīng)該在進行算法設(shè)計時就盡量考慮全面，而不是在程序編完之后隨便找些數(shù)據(jù)來測試它。 軟件測試：在規(guī)定的條件下對程序進行操作，以發(fā)現(xiàn)程序錯誤，衡量軟件品質(zhì)，并對其是否能滿足設(shè)計要求進行評估的過程。這是軟

39、件測試的經(jīng)典定義。111111軟件測試是一種實際輸出與預(yù)期輸出間的稽核或者比較過程。 測試用例：為某個特殊目標(biāo)而編制的一組測試輸入、執(zhí)行條件以及預(yù)期結(jié)果，以便測試某個程序路徑或核實是否滿足某個特定需求。關(guān)于測試的更進一步的介紹，參見第10章。112112【例1-5】 C程序的樣例1。在屏幕上輸出“Welcome to C!”，程序及語句含義解釋見表1.18。1.6 簡單的簡單的C程序介紹程序介紹113113表1.18 C程序樣例1114114程序結(jié)果：Welcome to C!表1.18中，“程序”一列給出的是一個完整的C語言程序，“行號”和“含義”兩列是為方便說明程序而加的，并不是程序的內(nèi)容

40、。表1.18程序完成的功能是在屏幕上輸出“Welcome to C!”這樣一串字符。其中主要幾行的說明如下：第1行：注釋。115115程序注釋：用一組/* */(或 /)括起來的字符串，用于程序語句等含義的說明。在C語言中，所有的注釋由字符/*開始，以*/結(jié)束。在星號及斜杠之間不允許有空格。編譯程序編譯時將忽略注釋的內(nèi)容，即不會把它們翻譯成機器碼。一般情況下，源程序有效注釋量應(yīng)在20以上。注釋的原則是有助于對程序的閱讀理解。注釋語言必須準(zhǔn)確、易懂、簡潔。116116第2行：文件包含。include是c語言的預(yù)編譯命令，表示文件包含的意思；stdio.h 是英文Standard input ou

41、tput head(標(biāo)準(zhǔn)輸入輸出頭文件)的縮寫。第5行：主函數(shù)main。一個C程序總是有一個稱為main的主函數(shù)，主函數(shù)中間的所有語句都被一對大括號包括在內(nèi)。本例的左右大括號分別出現(xiàn)在第6行和第11行。117117函數(shù)：C語言中，把功能相對獨立的程序段稱做“函數(shù)”。第7行：庫函數(shù)printf()。printf是系統(tǒng)提供的庫函數(shù)，它的說明是放在stdio.h這個頭文件中的，功能是把括號內(nèi)雙引號中的內(nèi)容輸出到屏幕上。printf輸出的內(nèi)容可以由程序員根據(jù)需要來填寫。118118庫函數(shù)：庫函數(shù)并不是C語言的一部分，它是由編譯系統(tǒng)把實現(xiàn)常用功能的一組程序放在系統(tǒng)程序庫中，用戶可以通過引用程序庫相應(yīng)的程

42、序說明文件(頭文件)來使用這些程序，即庫函數(shù)。C語言中常見的庫函數(shù)參看附錄C。119119 為什么要建立函數(shù)庫?建立函數(shù)庫是為了把可重復(fù)使用的函數(shù)放在一起，供其他程序員和程序共享。例如，幾個程序可能都會用到一些通用的功能函數(shù)，那就不必在每個程序中都復(fù)制這些源代碼，而只需把這些函數(shù)集中到一個函數(shù)庫中，然后用連接程序把它們連接到程序中。這種方法有利于程序的編寫和維護。120120文件包含：其功能是把指定的文件插入該命令行位置取代該命令行，從而把指定的文件和當(dāng)前的源程序文件連成一個源文件。形式：#include (或者：#include 文件名)121121說明：(1) 被包含的文件可以由系統(tǒng)提供，

43、也可以由程序員自己編寫。(2) 一個include命令只能指定一個被包含文件，若有多個文件要包含，則需用多個include命令。(3) 如果文件名以尖括號括起，在編譯時將會在指定的目錄下查找此頭文件；如果文件名以雙引號括起，在編譯時會首先在當(dāng)前的源文件目錄中查找該頭文件，若找不到才會到系統(tǒng)的指定目錄下去查找。(4) 更多的內(nèi)容參見第9章。122122頭文件：頭文件的目的是把多個C程序文件公用的內(nèi)容單獨放在一個文件里，以減少整體代碼尺寸。頭文件的擴展名為.h。凡是在程序中要用到庫函數(shù)時，都必須包含該函數(shù)原型所在的頭文件。 C語言的頭文件中包括了各個標(biāo)準(zhǔn)庫函數(shù)的說明形式。123123 注釋每個函數(shù)

44、之前都應(yīng)該有一段描述該函數(shù)目的的注釋。每個函數(shù)開始、結(jié)束時應(yīng)該加一注釋，標(biāo)明該函數(shù)開始或結(jié)束。 輸出格式輸出的最后一個字符應(yīng)該是換行符(n)。這種約定有助于軟件的可重用性。 縮進應(yīng)該把函數(shù)體縮進一個級別。這強調(diào)了程序的函數(shù)化結(jié)構(gòu)，使程序更易閱讀。用戶可設(shè)置自己喜歡的縮進大小約定，然后在程序設(shè)計時統(tǒng)一使用這個約定?？捎肨ab鍵來縮進。124124【例1-6】 C程序的樣例2。求兩個數(shù)之和。程序及語句含義解釋見表1.19。125125表1.19 C程序樣例2126126程序結(jié)果：sum is 579【例1-7】 C程序的樣例3。通過鍵盤輸入兩個整數(shù)，計算這兩個整數(shù)的和，并將結(jié)果顯示到屏幕上，程序見表1.20。127127表1.20 C程序樣例3128128程序結(jié)果：Enter first integer6Enter second integer23Sum is 29【例1-8】 C程序的樣例4。含有多個函數(shù)的程序，見表1.21。129129表1.21 C程序樣例4130130表1.21中的這段程序除了有主函數(shù)main外，還有一個子函數(shù)max，它的形式和ma