最新計(jì)算機(jī)第10章程序設(shè)計(jì)基礎(chǔ)

1、1第第10章章 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)10.1 程序設(shè)計(jì)的概念程序設(shè)計(jì)的概念10.2 算法算法10.3 程序設(shè)計(jì)語言程序設(shè)計(jì)語言10.4 程序設(shè)計(jì)方法程序設(shè)計(jì)方法210.1 程序設(shè)計(jì)的概念程序設(shè)計(jì)的概念v程序：是解題方法和步驟的描述，是供計(jì)算機(jī)執(zhí)行程序：是解題方法和步驟的描述，是供計(jì)算機(jī)執(zhí)行并能完成特定功能的指令序列。并能完成特定功能的指令序列。v程序的核心：數(shù)據(jù)結(jié)構(gòu)和算法。程序的核心：數(shù)據(jù)結(jié)構(gòu)和算法。v程序設(shè)計(jì)（程序設(shè)計(jì)（Programming）：先對(duì)問題進(jìn)行分析并）：先對(duì)問題進(jìn)行分析并建立數(shù)學(xué)模型，然后考慮數(shù)據(jù)的組織方式和算法，建立數(shù)學(xué)模型，然后考慮數(shù)據(jù)的組織方式和算法，并用某一種程序設(shè)

2、計(jì)語言編寫程序，最后調(diào)試程序，并用某一種程序設(shè)計(jì)語言編寫程序，最后調(diào)試程序，使之運(yùn)行后能產(chǎn)生預(yù)期的結(jié)果。使之運(yùn)行后能產(chǎn)生預(yù)期的結(jié)果。3v程序設(shè)計(jì)的基本步驟：程序設(shè)計(jì)的基本步驟：(1)分析問題，確定數(shù)學(xué)模型或方法。分析問題，確定數(shù)學(xué)模型或方法。(2)設(shè)計(jì)算法，畫出流程圖。設(shè)計(jì)算法，畫出流程圖。(3)選擇編程工具，按算法編寫程序。選擇編程工具，按算法編寫程序。(4)調(diào)試程序，分析輸出結(jié)果。調(diào)試程序，分析輸出結(jié)果。4 10.2 算算 法法 10.2.1 算法的概念算法的概念計(jì)算機(jī)解決問題的方法和步驟，就是計(jì)算機(jī)解題計(jì)算機(jī)解決問題的方法和步驟，就是計(jì)算機(jī)解題的算法的算法(Algorithm)。算法舉例

3、：算法舉例：（1） 將兩個(gè)變量的值互換將兩個(gè)變量的值互換 。 （2）歐幾里德（）歐幾里德（Euclid）算法求兩個(gè)正整數(shù)）算法求兩個(gè)正整數(shù)m和和n的最大公約數(shù)。的最大公約數(shù)。 （3）非數(shù)值計(jì)算算法：有）非數(shù)值計(jì)算算法：有9枚銅幣，其中有枚銅幣，其中有1枚略枚略輕的是假幣，用一臺(tái)沒有砝碼的天平將假幣找出輕的是假幣，用一臺(tái)沒有砝碼的天平將假幣找出來，應(yīng)怎樣找稱來，應(yīng)怎樣找稱 。510.2.2 算法的特性算法的特性(1) 有窮性。算法中執(zhí)行的步驟總是有限次數(shù)的，不有窮性。算法中執(zhí)行的步驟總是有限次數(shù)的，不能無止境地執(zhí)行下去。能無止境地執(zhí)行下去。(2) 確定性。算法中的每一步操作必須具有確切的含確定性

4、。算法中的每一步操作必須具有確切的含義，不能有二義性。義，不能有二義性。(3) 有效性。算法中的每一步操作必須是可執(zhí)行的。有效性。算法中的每一步操作必須是可執(zhí)行的。(4) 要有數(shù)據(jù)輸入。算法中操作的對(duì)象是數(shù)據(jù)，因此要有數(shù)據(jù)輸入。算法中操作的對(duì)象是數(shù)據(jù)，因此應(yīng)提供有關(guān)數(shù)據(jù)。應(yīng)提供有關(guān)數(shù)據(jù)。(5) 要有結(jié)果輸出。要有結(jié)果輸出。610.2.3 算法的評(píng)價(jià)算法的評(píng)價(jià)1算法評(píng)價(jià)標(biāo)準(zhǔn)算法評(píng)價(jià)標(biāo)準(zhǔn) （1）正確性。）正確性。（2）可讀性。）可讀性。（3）通用性。）通用性。（4）高效率。）高效率。2. 算法效率的度量算法效率的度量（1）時(shí)間度量）時(shí)間度量（2）空間度量）空間度量710.2.4 算法的描述算法的描

5、述1. 用傳統(tǒng)的流程圖描述算法用傳統(tǒng)的流程圖描述算法傳統(tǒng)的流程圖是用一些幾何框圖、傳統(tǒng)的流程圖是用一些幾何框圖、流程線和文字說明表示各種類型流程線和文字說明表示各種類型的操作。一般用矩形框表示進(jìn)行的操作。一般用矩形框表示進(jìn)行某種處理，有一個(gè)入口，一個(gè)出某種處理，有一個(gè)入口，一個(gè)出口。用菱形框表示判斷，有一個(gè)口。用菱形框表示判斷，有一個(gè)入口，兩個(gè)出口。在框內(nèi)寫上簡入口，兩個(gè)出口。在框內(nèi)寫上簡明的文字或符號(hào)表示具體的操作，明的文字或符號(hào)表示具體的操作，用帶箭頭的流向線表示操作的先用帶箭頭的流向線表示操作的先后順序。后順序。 8 2. 用結(jié)構(gòu)化流程圖描述算法用結(jié)構(gòu)化流程圖描述算法（1）程序的三種基本

6、結(jié)構(gòu)：順序結(jié)）程序的三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。（2）結(jié)構(gòu)化流程圖（）結(jié)構(gòu)化流程圖（N-S圖）圖）93用偽代碼描述算法用偽代碼描述算法計(jì)算計(jì)算2+4+ +100并輸出，設(shè)計(jì)算法并用并輸出，設(shè)計(jì)算法并用Visual Basic偽代碼描述如下：偽代碼描述如下：0sum1iDo While i100 If i/2的余數(shù)為的余數(shù)為0 THEN sum+isum i+1iLoopPrint sum 1010.2.5 算法示例算法示例1迭代算法迭代算法 迭代是一種建立在循環(huán)基礎(chǔ)上的算法。在數(shù)學(xué)中，迭代是一種建立在循環(huán)基礎(chǔ)上的算法。在數(shù)學(xué)中，迭代經(jīng)常被用來進(jìn)行數(shù)值計(jì)算

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

8、法 窮舉法也叫枚舉法，它的基本思路是對(duì)眾多可能窮舉法也叫枚舉法，它的基本思路是對(duì)眾多可能解，按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從中找解，按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從中找出那些符合要求的可能解，作為問題的解。窮舉出那些符合要求的可能解，作為問題的解。窮舉的計(jì)算量是相當(dāng)大的，但對(duì)于計(jì)算機(jī)來說，做起的計(jì)算量是相當(dāng)大的，但對(duì)于計(jì)算機(jī)來說，做起來很容易。窮舉算法是一種重要的算法設(shè)計(jì)策略，來很容易。窮舉算法是一種重要的算法設(shè)計(jì)策略，可以說是計(jì)算機(jī)解題的一大特點(diǎn)?？梢哉f是計(jì)算機(jī)解題的一大特點(diǎn)。 求方程求方程x+2y+5z=100的整數(shù)解。的整數(shù)解。133排序算法排序算法所謂排序，就是將一組數(shù)據(jù)元素按照某

9、個(gè)關(guān)鍵字所謂排序，就是將一組數(shù)據(jù)元素按照某個(gè)關(guān)鍵字遞增或遞減的次序排列起來。遞增或遞減的次序排列起來。（1）選擇排序）選擇排序(Selection Sort)選擇排序法的實(shí)現(xiàn)過程是：首先找出表中關(guān)鍵字選擇排序法的實(shí)現(xiàn)過程是：首先找出表中關(guān)鍵字最小的元素，將其與第一個(gè)元素進(jìn)行交換，然后，最小的元素，將其與第一個(gè)元素進(jìn)行交換，然后，再在其余元素中找出關(guān)鍵字最小的元素，將其與再在其余元素中找出關(guān)鍵字最小的元素，將其與第二個(gè)元素進(jìn)行交換。依次類推，直到將表中所第二個(gè)元素進(jìn)行交換。依次類推，直到將表中所有關(guān)鍵字按由小到大的順序排列好為止。有關(guān)鍵字按由小到大的順序排列好為止。14 （2）冒泡排序）冒泡排序

10、(Bubble Sort)冒泡法排序法是每趟將相鄰的兩個(gè)數(shù)兩兩進(jìn)行比冒泡法排序法是每趟將相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較，若滿足升序次序，則進(jìn)行下一次比較，若不較，若滿足升序次序，則進(jìn)行下一次比較，若不滿足升序次序，則交換這兩個(gè)數(shù)，直到最后?？倽M足升序次序，則交換這兩個(gè)數(shù)，直到最后?？偟谋容^次數(shù)為的比較次數(shù)為n-1次，此時(shí)最后的元素為最大數(shù)，次，此時(shí)最后的元素為最大數(shù)，此為一趟排序。接著進(jìn)行第二趟排序，方法同前，此為一趟排序。接著進(jìn)行第二趟排序，方法同前，只是這次最后一個(gè)元素不再參與比較，比較次數(shù)只是這次最后一個(gè)元素不再參與比較，比較次數(shù)為為n-2次，依次類推。次，依次類推。15 4查找算法查找算法查

11、找是根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)查找是根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素，若表中存在這其關(guān)鍵字等于給定值的數(shù)據(jù)元素，若表中存在這樣的數(shù)據(jù)元素，稱此查找是成功的。若表中不存樣的數(shù)據(jù)元素，稱此查找是成功的。若表中不存在關(guān)鍵字等于給定值的數(shù)據(jù)元素，稱此查找是不在關(guān)鍵字等于給定值的數(shù)據(jù)元素，稱此查找是不成功的。成功的。（1）順序查找）順序查找順序查找是最常用的查找方法，其查找過程為：順序查找是最常用的查找方法，其查找過程為：從第一個(gè)元素起，逐個(gè)將給定值與數(shù)據(jù)元素的關(guān)從第一個(gè)元素起，逐個(gè)將給定值與數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較，若某個(gè)元素的關(guān)鍵字與給定值相鍵字進(jìn)行比較，若

12、某個(gè)元素的關(guān)鍵字與給定值相等，則認(rèn)為查找是成功的，否則，查找失敗。等，則認(rèn)為查找是成功的，否則，查找失敗。16 （2）折半查找）折半查找作為折半查找的表必須是順序存儲(chǔ)的有序表，即表采作為折半查找的表必須是順序存儲(chǔ)的有序表，即表采用順序結(jié)構(gòu)存儲(chǔ)，表中的元素按關(guān)鍵字值遞增（或遞減）用順序結(jié)構(gòu)存儲(chǔ)，表中的元素按關(guān)鍵字值遞增（或遞減）排列。排列。假設(shè)表中的關(guān)鍵字值遞增排列，則折半查找的實(shí)現(xiàn)方假設(shè)表中的關(guān)鍵字值遞增排列，則折半查找的實(shí)現(xiàn)方法是：首先取整個(gè)有序表的中間元素法是：首先取整個(gè)有序表的中間元素Am的關(guān)鍵字同給定的關(guān)鍵字同給定值值x比較，若相等，則查找成功；否則，若比較，若相等，則查找成功；否則，

13、若Am的關(guān)鍵字小的關(guān)鍵字小于于x，則說明待查元素只可能落在表的后半部分中，接著，則說明待查元素只可能落在表的后半部分中，接著只要在表的后半部分子表中查找即可；若只要在表的后半部分子表中查找即可；若 Am的關(guān)鍵字大的關(guān)鍵字大于于x，則說明待查元素只可能落在表的前半部分中，接著，則說明待查元素只可能落在表的前半部分中，接著只要在表的前半部分子表中查找即可。這樣，經(jīng)過一次關(guān)只要在表的前半部分子表中查找即可。這樣，經(jīng)過一次關(guān)鍵字的比較，就縮小一半的查找空間，重復(fù)進(jìn)行下去，直鍵字的比較，就縮小一半的查找空間，重復(fù)進(jìn)行下去，直到找到關(guān)鍵字為到找到關(guān)鍵字為x的元素，或者表中沒有待查元素（此時(shí)的元素，或者表中

14、沒有待查元素（此時(shí)查找區(qū)間為空）為止。查找區(qū)間為空）為止。1710.3 程序設(shè)計(jì)語言程序設(shè)計(jì)語言10.3.1 程序設(shè)計(jì)語言的分類程序設(shè)計(jì)語言的分類機(jī)器語言機(jī)器語言匯編語言匯編語言高級(jí)語言高級(jí)語言面向過程面向過程面向?qū)ο竺嫦驅(qū)ο?81機(jī)器語言（機(jī)器語言（Machine language）機(jī)器語言：機(jī)器指令的總稱。機(jī)器語言：機(jī)器指令的總稱。特點(diǎn)：繁瑣冗長、不直觀、容易出錯(cuò)、程序不通特點(diǎn)：繁瑣冗長、不直觀、容易出錯(cuò)、程序不通用。用。2匯編語言（匯編語言（Assembly language）用助記符表示的機(jī)器指令。用助記符表示的機(jī)器指令。特點(diǎn)：直觀性增強(qiáng)了，但與機(jī)器指令一一對(duì)應(yīng)。特點(diǎn)：直觀性增強(qiáng)了，但

15、與機(jī)器指令一一對(duì)應(yīng)。3高級(jí)語言（高級(jí)語言（High level language）高級(jí)語言：接近自然語言和數(shù)學(xué)表達(dá)式的一種語高級(jí)語言：接近自然語言和數(shù)學(xué)表達(dá)式的一種語言。言。特點(diǎn)：直觀、通用性，便于推廣交流。特點(diǎn)：直觀、通用性，便于推廣交流。兩種執(zhí)行方式：編譯方式和解釋方式。兩種執(zhí)行方式：編譯方式和解釋方式。19高級(jí)語言程序的編譯執(zhí)行過程：高級(jí)語言程序的編譯執(zhí)行過程：編譯程序工作過程編譯程序工作過程:2010.3.2 高級(jí)語言的基本特征高級(jí)語言的基本特征1數(shù)據(jù)類型數(shù)據(jù)類型各種高級(jí)語言都提供了豐富的數(shù)據(jù)類型，這些數(shù)據(jù)各種高級(jí)語言都提供了豐富的數(shù)據(jù)類型，這些數(shù)據(jù)類型可以分為兩大類：簡單類型和構(gòu)造類

16、型。其中類型可以分為兩大類：簡單類型和構(gòu)造類型。其中簡單類型一般有整型、實(shí)型、字符型、邏輯型、指簡單類型一般有整型、實(shí)型、字符型、邏輯型、指針類型等，構(gòu)造類型有數(shù)組類型、集合類型、記錄針類型等，構(gòu)造類型有數(shù)組類型、集合類型、記錄類型、文件類型等。類型、文件類型等。212運(yùn)算與表達(dá)式運(yùn)算與表達(dá)式（1）常量）常量（2）變量）變量（3）表達(dá)式）表達(dá)式3語句語句（1）賦值語句）賦值語句（2）輸入輸出語句）輸入輸出語句（3）程序的控制結(jié)構(gòu)語句）程序的控制結(jié)構(gòu)語句4子程序、函數(shù)與過程子程序、函數(shù)與過程2210.3.3 常用高級(jí)語言常用高級(jí)語言1. 傳統(tǒng)高級(jí)語言傳統(tǒng)高級(jí)語言（1）FORTRAN語言：語言：F

17、ORTRAN 66、FORTRAN 77、FORTRAN 90。（2）BASIC語言：語言：BASIC、Visual Basic、Visual Basic .NET。（3）PASCAL語言語言（4）C語言：語言：C、C+、C。（5）COBOL語言語言232網(wǎng)絡(luò)編程語言網(wǎng)絡(luò)編程語言（1）Java語言語言（2）腳本語言（）腳本語言（Scripting Language）：）：JavaScript、VBScript、Perl、PHP。 3科學(xué)計(jì)算語言：科學(xué)計(jì)算語言：MATLAB討論：討論：如何學(xué)習(xí)一種高級(jí)語言？如何選擇高級(jí)語言？如何學(xué)習(xí)一種高級(jí)語言？如何選擇高級(jí)語言？24 10.4.1 結(jié)構(gòu)化程序設(shè)

18、計(jì)結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)采用自頂向下、逐步求精和模塊結(jié)構(gòu)化程序設(shè)計(jì)采用自頂向下、逐步求精和模塊化的分析方法，從而有效地將一個(gè)較復(fù)雜的程序化的分析方法，從而有效地將一個(gè)較復(fù)雜的程序系統(tǒng)設(shè)計(jì)任務(wù)分解成許多易于控制和處理的子程系統(tǒng)設(shè)計(jì)任務(wù)分解成許多易于控制和處理的子程序，便于開發(fā)和維護(hù)。序，便于開發(fā)和維護(hù)。10.4 程序設(shè)計(jì)方法程序設(shè)計(jì)方法2510.4.2 面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)(Object-Oriented Programming, OOP)傳統(tǒng)的程序設(shè)計(jì)是基于求解過程來組織程序流程。傳統(tǒng)的程序設(shè)計(jì)是基于求解過程來組織程序流程。在這類程序中，數(shù)據(jù)和施加于數(shù)據(jù)的操作是獨(dú)立設(shè)在這類程

19、序中，數(shù)據(jù)和施加于數(shù)據(jù)的操作是獨(dú)立設(shè)計(jì)的，以對(duì)數(shù)據(jù)進(jìn)行操作的過程作為程序的主體。計(jì)的，以對(duì)數(shù)據(jù)進(jìn)行操作的過程作為程序的主體。面向?qū)ο蟪绦蛟O(shè)計(jì)則以對(duì)象作為程序的主體。對(duì)象面向?qū)ο蟪绦蛟O(shè)計(jì)則以對(duì)象作為程序的主體。對(duì)象是數(shù)據(jù)和操作的是數(shù)據(jù)和操作的“封裝體封裝體”，封裝在對(duì)象內(nèi)的程序，封裝在對(duì)象內(nèi)的程序通過通過“消息消息”來驅(qū)動(dòng)運(yùn)行。在圖形用戶界面上，消來驅(qū)動(dòng)運(yùn)行。在圖形用戶界面上，消息可通過鍵盤或鼠標(biāo)的某種操作來傳遞。息可通過鍵盤或鼠標(biāo)的某種操作來傳遞。26（1）對(duì)象）對(duì)象(Object) 對(duì)象是指現(xiàn)實(shí)世界中具體存對(duì)象是指現(xiàn)實(shí)世界中具體存在的實(shí)體。每一個(gè)對(duì)象都有自己的屬性（包括自在的實(shí)體。每一個(gè)對(duì)象

20、都有自己的屬性（包括自己特有的屬性和同類對(duì)象的共同屬性）。屬性反己特有的屬性和同類對(duì)象的共同屬性）。屬性反映對(duì)象自身狀態(tài)變化，表現(xiàn)為當(dāng)前的屬性值。映對(duì)象自身狀態(tài)變化，表現(xiàn)為當(dāng)前的屬性值。方法是用來描述對(duì)象動(dòng)態(tài)特征的一個(gè)操作序列。方法是用來描述對(duì)象動(dòng)態(tài)特征的一個(gè)操作序列。（2) 類類(Class) 類是具有相同屬性和方法的一組類是具有相同屬性和方法的一組對(duì)象的集合，它為屬于該類的全部對(duì)象提供了統(tǒng)對(duì)象的集合，它為屬于該類的全部對(duì)象提供了統(tǒng)一的抽象描述。一的抽象描述。27OPP與與OOP比較比較輸輸入入一一個(gè)個(gè)整整數(shù)數(shù), ,判判斷斷奇奇偶偶判判斷斷重重置置2810.4.3 可視化程序設(shè)計(jì)可視化程序設(shè)計(jì)讓程序設(shè)計(jì)人員利用語言工具本身所提供的各讓程序設(shè)計(jì)人員利用語言工具本身所提供的各種控件，像搭積木式地構(gòu)造應(yīng)用程序的各種界種控件，像搭積木式地構(gòu)造應(yīng)用程序的各種界面，使得整個(gè)界面設(shè)計(jì)是在面，使得整個(gè)界面設(shè)計(jì)是在“所見即所得所見即所得”的的可視化狀態(tài)下完成。相對(duì)于編寫代碼方式的程可視化狀態(tài)下完成。相對(duì)于編寫代碼方式的程序設(shè)計(jì)而言的，可視化程序設(shè)計(jì)具有直觀形象序設(shè)計(jì)而言的，可視化程序設(shè)計(jì)具有直觀形象、方便高效等優(yōu)點(diǎn)。、方便高效等優(yōu)點(diǎn)。29VB程序設(shè)計(jì)程序設(shè)計(jì)1.