第10章 程序設(shè)計(jì)基礎(chǔ)

第十章程序設(shè)計(jì)基礎(chǔ)《大學(xué)計(jì)算機(jī)》（第三版）高等教育出版社10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.1程序設(shè)計(jì)的概念程序：是解題方法和步驟的描述，是供計(jì)算機(jī)執(zhí)行并能完成特定功能的指令序列。程序的核心：數(shù)據(jù)結(jié)構(gòu)和算法。程序設(shè)計(jì)（Programming）：先對(duì)問(wèn)題進(jìn)行分析并建立數(shù)學(xué)模型，然后考慮數(shù)據(jù)的組織方式和算法，并用某一種程序設(shè)計(jì)語(yǔ)言編寫(xiě)程序，最后調(diào)試程序，使之運(yùn)行后能產(chǎn)生預(yù)期的結(jié)果。10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.1程序設(shè)計(jì)的概念程序設(shè)計(jì)的基本步驟：

(1)分析問(wèn)題，確定數(shù)學(xué)模型或方法。

(2)設(shè)計(jì)算法，畫(huà)出流程圖。

(3)選擇編程工具，按算法編寫(xiě)程序。

(4)調(diào)試程序，分析輸出結(jié)果。10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2算法計(jì)算機(jī)解決問(wèn)題的方法和步驟，就是計(jì)算機(jī)解題的算法(Algorithm)。

算法舉例：

（1）將兩個(gè)變量的值互換。

（2）歐幾里德（Euclid）算法求兩個(gè)正整數(shù)m和n的最大公約數(shù)。（3）非數(shù)值計(jì)算算法：有9枚銅幣，其中有1枚略輕的是假幣，用一臺(tái)沒(méi)有砝碼的天平將假幣找出來(lái)，應(yīng)怎樣找稱。10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.1算法的概念10.2算法(1)有窮性。算法中執(zhí)行的步驟總是有限次數(shù)的，不能無(wú)止境地執(zhí)行下去。

(2)確定性。算法中的每一步操作必須具有確切的含義，不能有二義性。

(3)有效性。算法中的每一步操作必須是可執(zhí)行的。

(4)要有數(shù)據(jù)輸入。算法中操作的對(duì)象是數(shù)據(jù)，因此應(yīng)提供有關(guān)數(shù)據(jù)。

(5)要有結(jié)果輸出。10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.2算法的特性10.2算法1．算法評(píng)價(jià)標(biāo)準(zhǔn)（1）正確性。

（2）可讀性。

（3）通用性。

（4）高效率。

2.算法效率的度量

（1）時(shí)間度量

（2）空間度量10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.3算法的評(píng)價(jià)10.2算法用傳統(tǒng)的流程圖描述算法傳統(tǒng)的流程圖是用一些幾何框圖、流程線和文字說(shuō)明表示各種類型的操作。一般用矩形框表示進(jìn)行某種處理，有一個(gè)入口，一個(gè)出口。用菱形框表示判斷，有一個(gè)入口，兩個(gè)出口。在框內(nèi)寫(xiě)上簡(jiǎn)明的文字或符號(hào)表示具體的操作，用帶箭頭的流向線表示操作的先后順序。

10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.4算法的描述10.2算法2.用結(jié)構(gòu)化流程圖描述算法

（1）程序的三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

（2）結(jié)構(gòu)化流程圖（N-S圖）10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.4算法的描述10.2算法2.用結(jié)構(gòu)化流程圖描述算法

（1）程序的三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

（2）結(jié)構(gòu)化流程圖（N-S圖）10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.4算法的描述10.2算法3．用偽代碼描述算法計(jì)算2+4+…+100并輸出，設(shè)計(jì)算法并用VisualBasic偽代碼描述如下：0→sum1→iDoWhilei≤100Ifi/2的余數(shù)為0THENsum+i→sumi+1→iLoopPrintsum10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.4算法的描述10.2算法1．迭代算法迭代是一種建立在循環(huán)基礎(chǔ)上的算法。在數(shù)學(xué)中，迭代經(jīng)常被用來(lái)進(jìn)行數(shù)值計(jì)算，例如求方程的解，不斷用變量原來(lái)的值遞推求新的值的過(guò)程。討論求若干個(gè)數(shù)之和或乘積的問(wèn)題。

10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.5算法示例10.2算法2．窮舉算法窮舉法也叫枚舉法，它的基本思路是對(duì)眾多可能解，按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從中找出那些符合要求的可能解，作為問(wèn)題的解。窮舉的計(jì)算量是相當(dāng)大的，但對(duì)于計(jì)算機(jī)來(lái)說(shuō)，做起來(lái)很容易。窮舉算法是一種重要的算法設(shè)計(jì)策略，可以說(shuō)是計(jì)算機(jī)解題的一大特點(diǎn)。求方程x+2y+5z=100的整數(shù)解。10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.5算法示例10.2算法3．排序算法

所謂排序，就是將一組數(shù)據(jù)元素按照某個(gè)關(guān)鍵字遞增或遞減的次序排列起來(lái)。

（1）選擇排序(SelectionSort)

選擇排序法的實(shí)現(xiàn)過(guò)程是：首先找出表中關(guān)鍵字最小的元素，將其與第一個(gè)元素進(jìn)行交換，然后，再在其余元素中找出關(guān)鍵字最小的元素，將其與第二個(gè)元素進(jìn)行交換。依次類推，直到將表中所有關(guān)鍵字按由小到大的順序排列好為止。10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.5算法示例10.2算法（2）冒泡排序(BubbleSort)冒泡法排序法是每趟將相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較，若滿足升序次序，則進(jìn)行下一次比較，若不滿足升序次序，則交換這兩個(gè)數(shù)，直到最后?？偟谋容^次數(shù)為n-1次，此時(shí)最后的元素為最大數(shù)，此為一趟排序。接著進(jìn)行第二趟排序，方法同前，只是這次最后一個(gè)元素不再參與比較，比較次數(shù)為n-2次，依次類推。10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.5算法示例10.2算法4．查找算法查找是根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素，若表中存在這樣的數(shù)據(jù)元素，稱此查找是成功的。若表中不存在關(guān)鍵字等于給定值的數(shù)據(jù)元素，稱此查找是不成功的。

（1）順序查找

順序查找是最常用的查找方法，其查找過(guò)程為：從第一個(gè)元素起，逐個(gè)將給定值與數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較，若某個(gè)元素的關(guān)鍵字與給定值相等，則認(rèn)為查找是成功的，否則，查找失敗。10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.5算法示例10.2算法（2）折半查找作為折半查找的表必須是順序存儲(chǔ)的有序表，即表采用順序結(jié)構(gòu)存儲(chǔ)，表中的元素按關(guān)鍵字值遞增（或遞減）排列。

假設(shè)表中的關(guān)鍵字值遞增排列，則折半查找的實(shí)現(xiàn)方法是：首先取整個(gè)有序表的中間元素Am的關(guān)鍵字同給定值x比較，若相等，則查找成功；否則，若Am的關(guān)鍵字小于x，則說(shuō)明待查元素只可能落在表的后半部分中，接著只要在表的后半部分子表中查找即可；若Am的關(guān)鍵字大于x，則說(shuō)明待查元素只可能落在表的前半部分中，接著只要在表的前半部分子表中查找即可。這樣，經(jīng)過(guò)一次關(guān)鍵字的比較，就縮小一半的查找空間，重復(fù)進(jìn)行下去，直到找到關(guān)鍵字為x的元素，或者表中沒(méi)有待查元素（此時(shí)查找區(qū)間為空）為止。10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.2.5算法示例10.3程序設(shè)計(jì)語(yǔ)言10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.3.1程序設(shè)計(jì)語(yǔ)言的分類機(jī)器語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言面向過(guò)程面向?qū)ο?0.3程序設(shè)計(jì)語(yǔ)言10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.3.1程序設(shè)計(jì)語(yǔ)言的分類1．機(jī)器語(yǔ)言（Machinelanguage）

機(jī)器語(yǔ)言：機(jī)器指令的總稱。

特點(diǎn)：繁瑣冗長(zhǎng)、不直觀、容易出錯(cuò)、程序不通用。

2．匯編語(yǔ)言（Assemblylanguage）

用助記符表示的機(jī)器指令。

特點(diǎn)：直觀性增強(qiáng)了，但與機(jī)器指令一一對(duì)應(yīng)。

3．高級(jí)語(yǔ)言（Highlevellanguage）

高級(jí)語(yǔ)言：接近自然語(yǔ)言和數(shù)學(xué)表達(dá)式的一種語(yǔ)言。

特點(diǎn)：直觀、通用性，便于推廣交流。

兩種執(zhí)行方式：編譯方式和解釋方式。10.3程序設(shè)計(jì)語(yǔ)言10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.3.1程序設(shè)計(jì)語(yǔ)言的分類高級(jí)語(yǔ)言程序的編譯執(zhí)行過(guò)程：編譯程序工作過(guò)程:10.3程序設(shè)計(jì)語(yǔ)言10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.3.2高級(jí)語(yǔ)言的基本特征1．?dāng)?shù)據(jù)類型

各種高級(jí)語(yǔ)言都提供了豐富的數(shù)據(jù)類型，這些數(shù)據(jù)類型可以分為兩大類：簡(jiǎn)單類型和構(gòu)造類型。其中簡(jiǎn)單類型一般有整型、實(shí)型、字符型、邏輯型、指針類型等，構(gòu)造類型有數(shù)組類型、集合類型、記錄類型、文件類型等。10.3程序設(shè)計(jì)語(yǔ)言10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.3.2高級(jí)語(yǔ)言的基本特征2．運(yùn)算與表達(dá)式

（1）常量

（2）變量

（3）表達(dá)式

3．語(yǔ)句

（1）賦值語(yǔ)句

（2）輸入輸出語(yǔ)句

（3）程序的控制結(jié)構(gòu)語(yǔ)句

4．子程序、函數(shù)與過(guò)程

10.3程序設(shè)計(jì)語(yǔ)言10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.3.3常用高級(jí)語(yǔ)言1.傳統(tǒng)高級(jí)語(yǔ)言

（1）FORTRAN語(yǔ)言：FORTRAN66、FORTRAN77、FORTRAN90。

（2）BASIC語(yǔ)言：BASIC、VisualBasic、VisualBasic.NET。

（3）PASCAL語(yǔ)言

（4）C語(yǔ)言：C、C++、C＃。

（5）COBOL語(yǔ)言10.3程序設(shè)計(jì)語(yǔ)言10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.3.3常用高級(jí)語(yǔ)言2．網(wǎng)絡(luò)編程語(yǔ)言

（1）Java語(yǔ)言

（2）腳本語(yǔ)言（ScriptingLanguage）：JavaScript、VBScript、Perl、PHP。

3．科學(xué)計(jì)算語(yǔ)言：MATLAB10.3程序設(shè)計(jì)語(yǔ)言10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.3.3常用高級(jí)語(yǔ)言2．網(wǎng)絡(luò)編程語(yǔ)言

（1）Java語(yǔ)言

（2）腳本語(yǔ)言（ScriptingLanguage）：JavaScript、VBScript、Perl、PHP。

3．科學(xué)計(jì)算語(yǔ)言：MATLAB討論：如何學(xué)習(xí)一種高級(jí)語(yǔ)言？如何選擇高級(jí)語(yǔ)言？10.4程序設(shè)計(jì)方法10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.4.1結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)采用自頂向下、逐步求精和模塊化的分析方法，從而有效地將一個(gè)較復(fù)雜的程序系統(tǒng)設(shè)計(jì)任務(wù)分解成許多易于控制和處理的子程序，便于開(kāi)發(fā)和維護(hù)。10.4程序設(shè)計(jì)方法10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.4.2面向?qū)ο蟪绦蛟O(shè)計(jì)(Object-OrientedProgramming,OOP)傳統(tǒng)的程序設(shè)計(jì)是基于求解過(guò)程來(lái)組織程序流程。在這類程序中，數(shù)據(jù)和施加于數(shù)據(jù)的操作是獨(dú)立設(shè)計(jì)的，以對(duì)數(shù)據(jù)進(jìn)行操作的過(guò)程作為程序的主體。面向?qū)ο蟪绦蛟O(shè)計(jì)則以對(duì)象作為程序的主體。對(duì)象是數(shù)據(jù)和操作的“封裝體”，封裝在對(duì)象內(nèi)的程序通過(guò)“消息”來(lái)驅(qū)動(dòng)運(yùn)行。在圖形用戶界面上，消息可通過(guò)鍵盤(pán)或鼠標(biāo)的某種操作來(lái)傳遞。10.4程序設(shè)計(jì)方法10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.4.2面向?qū)ο蟪绦蛟O(shè)計(jì)(Object-OrientedProgramming,OOP)（1）對(duì)象(Object)對(duì)象是指現(xiàn)實(shí)世界中具體存在的實(shí)體。每一個(gè)對(duì)象都有自己的屬性（包括自己特有的屬性和同類對(duì)象的共同屬性）。屬性反映對(duì)象自身狀態(tài)變化，表現(xiàn)為當(dāng)前的屬性值。

方法是用來(lái)描述對(duì)象動(dòng)態(tài)特征的一個(gè)操作序列。

（2)類(Class)類是具有相同屬性和方法的一組對(duì)象的集合，它為屬于該類的全部對(duì)象提供了統(tǒng)一的抽象描述。10.4程序設(shè)計(jì)方法10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法OPP與OOP比較10.4程序設(shè)計(jì)方法10.1程序設(shè)計(jì)的概念10.2算法10.3程序設(shè)計(jì)語(yǔ)

言10.4程序設(shè)計(jì)方

法10.4.3可視化程序設(shè)計(jì)讓程序設(shè)計(jì)人員利用語(yǔ)言工具本身所提供的各種控件，像搭積木式地構(gòu)造應(yīng)用程序的各種界面，使得整個(gè)界面設(shè)計(jì)是在“所見(jiàn)即所得”的可視化狀態(tài)下完成。相對(duì)于編寫(xiě)代碼方式的程序設(shè)計(jì)而言的，可視化程序設(shè)計(jì)具有直觀形象、方便高效等優(yōu)點(diǎn)。10.