第10章 程序設計基礎

第十章程序設計基礎《大學計算機》（第三版）高等教育出版社10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

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

言10.4程序設計方

法10.1程序設計的概念程序設計的基本步驟：

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

(2)設計算法，畫出流程圖。

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

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

言10.4程序設計方

法10.2算法計算機解決問題的方法和步驟，就是計算機解題的算法(Algorithm)。

算法舉例：

（1）將兩個變量的值互換。

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

言10.4程序設計方

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

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

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

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

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

言10.4程序設計方

法10.2.2算法的特性10.2算法1．算法評價標準（1）正確性。

（2）可讀性。

（3）通用性。

（4）高效率。

2.算法效率的度量

（1）時間度量

（2）空間度量10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

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

10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

法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程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

法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程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

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

言10.4程序設計方

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

10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

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

言10.4程序設計方

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

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

（1）選擇排序(SelectionSort)

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

言10.4程序設計方

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

言10.4程序設計方

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

（1）順序查找

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

言10.4程序設計方

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

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

言10.4程序設計方

法10.2.5算法示例10.3程序設計語言10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

法10.3.1程序設計語言的分類機器語言匯編語言高級語言面向過程面向?qū)ο?0.3程序設計語言10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

法10.3.1程序設計語言的分類1．機器語言（Machinelanguage）

機器語言：機器指令的總稱。

特點：繁瑣冗長、不直觀、容易出錯、程序不通用。

2．匯編語言（Assemblylanguage）

用助記符表示的機器指令。

特點：直觀性增強了，但與機器指令一一對應。

3．高級語言（Highlevellanguage）

高級語言：接近自然語言和數(shù)學表達式的一種語言。

特點：直觀、通用性，便于推廣交流。

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

言10.4程序設計方

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

言10.4程序設計方

法10.3.2高級語言的基本特征1．數(shù)據(jù)類型

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

言10.4程序設計方

法10.3.2高級語言的基本特征2．運算與表達式

（1）常量

（2）變量

（3）表達式

3．語句

（1）賦值語句

（2）輸入輸出語句

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

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

10.3程序設計語言10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

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

（1）FORTRAN語言：FORTRAN66、FORTRAN77、FORTRAN90。

（2）BASIC語言：BASIC、VisualBasic、VisualBasic.NET。

（3）PASCAL語言

（4）C語言：C、C++、C＃。

（5）COBOL語言10.3程序設計語言10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

法10.3.3常用高級語言2．網(wǎng)絡編程語言

（1）Java語言

（2）腳本語言（ScriptingLanguage）：JavaScript、VBScript、Perl、PHP。

3．科學計算語言：MATLAB10.3程序設計語言10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

法10.3.3常用高級語言2．網(wǎng)絡編程語言

（1）Java語言

（2）腳本語言（ScriptingLanguage）：JavaScript、VBScript、Perl、PHP。

3．科學計算語言：MATLAB討論：如何學習一種高級語言？如何選擇高級語言？10.4程序設計方法10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

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

言10.4程序設計方

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

言10.4程序設計方

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

方法是用來描述對象動態(tài)特征的一個操作序列。

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

言10.4程序設計方

法OPP與OOP比較10.4程序設計方法10.1程序設計的概念10.2算法10.3程序設計語

言10.4程序設計方

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