大學(xué)計(jì)算機(jī)基礎(chǔ)(第三版)-第8章-程序設(shè)計(jì)基礎(chǔ)

第八章程序設(shè)計(jì)基礎(chǔ)本章內(nèi)容

程序設(shè)計(jì)的基本概念

算法

軟件開(kāi)發(fā)基礎(chǔ)

常用的程序設(shè)計(jì)語(yǔ)言8.1程序設(shè)計(jì)的基本概念1.程序和程序設(shè)計(jì)2.程序的一般概念

一個(gè)計(jì)算機(jī)程序主要描述兩部分內(nèi)容:

數(shù)據(jù)結(jié)構(gòu)—描述問(wèn)題的每個(gè)對(duì)象之間的關(guān)系

算法—對(duì)問(wèn)題的處理規(guī)則

經(jīng)典公式:程序=數(shù)據(jù)結(jié)構(gòu)+算法

程序設(shè)計(jì)：就是將解決某個(gè)問(wèn)題的過(guò)程用程序設(shè)計(jì)語(yǔ)言描述出來(lái)，計(jì)算機(jī)按這個(gè)描述去逐步實(shí)現(xiàn)。

程序設(shè)計(jì)語(yǔ)言：編寫(xiě)程序的語(yǔ)言。8.1

程序設(shè)計(jì)的基本概念語(yǔ)言

人類交流思想的工具程序設(shè)計(jì)語(yǔ)言

人和計(jì)算機(jī)之間進(jìn)行交流的語(yǔ)言

8.1程序設(shè)計(jì)的基本概念按照程序設(shè)計(jì)語(yǔ)言發(fā)展的過(guò)程，大概分為

機(jī)器語(yǔ)言（第一代語(yǔ)言）

匯編語(yǔ)言（第二代語(yǔ)言）

高級(jí)語(yǔ)言（第三代語(yǔ)言）

面向問(wèn)題的語(yǔ)言（第四代語(yǔ)言）

智能性語(yǔ)言（第五代語(yǔ)言）低級(jí)語(yǔ)言8.1程序設(shè)計(jì)的基本概念

機(jī)器語(yǔ)言機(jī)器語(yǔ)言中的每一條語(yǔ)句實(shí)際上是一條二進(jìn)制形式的指令代碼指令格式如下：操作碼

操作數(shù)

操作碼

要完成的操作類型或性質(zhì)操作數(shù)

操作的內(nèi)容或所在的地址

8.1程序設(shè)計(jì)的基本概念例如:計(jì)算A=7+8的機(jī)器語(yǔ)言程序：

1011000000000111：把7放入累加器AX中0000010000001000：將8與累加器AX中的值相加，結(jié)果仍放入AX中

11110100：結(jié)束停機(jī)8.1

程序設(shè)計(jì)的基本概念

匯編語(yǔ)言匯編語(yǔ)言是使用一種叫做助記符來(lái)代替機(jī)器語(yǔ)言中的二進(jìn)制數(shù)0和1，比如用“ADD”表示加法，“MOV”用來(lái)表示傳送數(shù)據(jù)，等等。讀寫(xiě)程序容易多了，對(duì)程序進(jìn)行糾錯(cuò)和維護(hù)都變得方便了。例如，計(jì)算A=7+8的匯編語(yǔ)言程序：

MOVAX,7：把7放入累加器AX中ADDAX,8：將8與累加器AX中的值相加，結(jié)果仍放入AX中

HLT：結(jié)束停機(jī)8.1

程序設(shè)計(jì)的基本概念高級(jí)語(yǔ)言接近于數(shù)學(xué)語(yǔ)言或人的自然語(yǔ)言，同時(shí)又不依賴于計(jì)算機(jī)硬件。例如，將計(jì)算A=7+8的過(guò)程用高級(jí)語(yǔ)言Basic表示如下:A=7+8‘7+8相加的結(jié)果放入變量A中PRINTA‘輸出A的值END‘程序結(jié)束8.1程序設(shè)計(jì)的基本概念語(yǔ)言處理程序（語(yǔ)言翻譯程序）

因?yàn)橛?jì)算機(jī)只能執(zhí)行機(jī)器語(yǔ)言程序，所以用其他語(yǔ)言編寫(xiě)的程序不能被計(jì)算機(jī)直接執(zhí)行，而必須經(jīng)過(guò)一個(gè)翻譯程序?qū)⑺D(zhuǎn)換成相應(yīng)的機(jī)器語(yǔ)言程序才能被計(jì)算機(jī)直接執(zhí)行。完成這一轉(zhuǎn)換功能的程序就是語(yǔ)言處理程序，語(yǔ)言處理程序是一種系統(tǒng)軟件，有三種：

匯編程序（匯編器）

編譯程序（編譯器）

解釋程序（解釋器）8.1程序設(shè)計(jì)的基本概念

匯編程序（匯編器）匯編程序?qū)ｉT(mén)負(fù)責(zé)把用匯編語(yǔ)言編寫(xiě)的程序翻譯成機(jī)器可直接執(zhí)行的機(jī)器指令程序。機(jī)器語(yǔ)言程序匯編程序匯編語(yǔ)言源程序匯編方式執(zhí)行過(guò)程8.1程序設(shè)計(jì)的基本概念高級(jí)語(yǔ)言翻譯程序

編譯程序——-對(duì)高級(jí)語(yǔ)言書(shū)寫(xiě)的程序進(jìn)行整體上的識(shí)別與理解，將其翻譯成一個(gè)功能等價(jià)的程序。編譯方式執(zhí)行過(guò)程數(shù)據(jù)編

輯源程序(*.cpp)可執(zhí)行程序

(*.exe)結(jié)果目標(biāo)程序（*.obj）連

接運(yùn)行編

譯編輯程序編譯程序連接程序8.1程序設(shè)計(jì)的基本概念高級(jí)語(yǔ)言翻譯程序

解釋程序——對(duì)源程序進(jìn)行逐句分析，若沒(méi)有錯(cuò)誤，將該語(yǔ)句轉(zhuǎn)換成機(jī)器語(yǔ)言指令，并立即執(zhí)行，即翻譯一句執(zhí)行一句。計(jì)算結(jié)果解釋程序高級(jí)語(yǔ)言源程序解釋方式執(zhí)行過(guò)程

一般來(lái)說(shuō)，程序設(shè)計(jì)語(yǔ)言都應(yīng)包含以下四種成分：

數(shù)據(jù)成分

用以描述程序中所涉及的數(shù)據(jù)

運(yùn)算成分

用以描述程序中所包含的運(yùn)算

控制成分

用以描述程序中的控制結(jié)構(gòu)

傳輸成分

用以表達(dá)程序中數(shù)據(jù)的傳輸

程序設(shè)計(jì)語(yǔ)言的組成

程序語(yǔ)言提供的數(shù)據(jù)類型：

基本數(shù)據(jù)類型一般程序設(shè)計(jì)語(yǔ)言中提供了數(shù)值類型（整數(shù)類型、實(shí)數(shù)類型）、字符類型、邏輯類型和指針類型等。

構(gòu)造數(shù)據(jù)類型構(gòu)造數(shù)據(jù)類型是由基本數(shù)據(jù)類型按照某種方式組合而成。一般有：數(shù)組類型、記錄類型、枚舉類型、文件等。

程序設(shè)計(jì)語(yǔ)言的組成

程序語(yǔ)言包含的運(yùn)算

一般程序設(shè)計(jì)語(yǔ)言中都提供了能支持計(jì)算機(jī)進(jìn)行算術(shù)運(yùn)算和邏輯運(yùn)算的運(yùn)算符，一般有以下幾類：

算術(shù)運(yùn)算符——加（+）、減（-）、乘（*）、除（/）、乘方（**）等

關(guān)系運(yùn)算符——大于（>）、小于（<）、大于等于（>=）、小于等于(<=)、等于(==)、不等于(!=)等

邏輯運(yùn)算符——與(&&)、或(||)、非(!)

字符運(yùn)算符——兩個(gè)字符串聯(lián)結(jié)、取子串等

程序設(shè)計(jì)語(yǔ)言的組成

程序語(yǔ)言提供的控制結(jié)構(gòu)

程序設(shè)計(jì)語(yǔ)言的組成

ABAB條件NYA條件YNA條件YN選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)輸入和輸出：程序的輸入/輸出分為兩大類：

以文件形式數(shù)據(jù)傳送

人—機(jī)交互輸入/輸出在不同的程序設(shè)計(jì)語(yǔ)言中由不同的語(yǔ)句或函數(shù)來(lái)實(shí)現(xiàn)。在C++中關(guān)于輸入/輸出的語(yǔ)句有：cin>>變量名1>>變量名2…；cout<<表達(dá)式1<<表達(dá)式2…；

程序設(shè)計(jì)語(yǔ)言的組成過(guò)程將重復(fù)處理程序段或分解的子功能編寫(xiě)成一個(gè)邏輯上獨(dú)立的過(guò)程，當(dāng)程序需要該過(guò)程時(shí)，只需調(diào)用它。使用過(guò)程可降低程序的復(fù)雜度，簡(jiǎn)化程序編寫(xiě)，便于調(diào)試。一般程序設(shè)計(jì)語(yǔ)言中有兩種過(guò)程：

函數(shù)過(guò)程

函數(shù)名有返回值

子過(guò)程

子過(guò)程名沒(méi)有返回值各種語(yǔ)言系統(tǒng)還提供了已定義好的大量標(biāo)準(zhǔn)函數(shù)，如數(shù)學(xué)函數(shù)、字符串函數(shù)、類型轉(zhuǎn)換函數(shù)等，放在系統(tǒng)的函數(shù)庫(kù)中，供用戶直接調(diào)用。

程序設(shè)計(jì)語(yǔ)言的組成先定義后調(diào)用8.2算法

計(jì)算機(jī)語(yǔ)言只是一種工具。光學(xué)習(xí)語(yǔ)言的規(guī)則還不夠，最重要的是學(xué)會(huì)針對(duì)各種類型的問(wèn)題，擬定出有效的解決方法和步驟即算法。有了正確而有效的算法，可以利用任何一種計(jì)算機(jī)高級(jí)語(yǔ)言編寫(xiě)程序，使計(jì)算機(jī)進(jìn)行工作。因此，設(shè)計(jì)算法是程序設(shè)計(jì)的核心。

算法是程序設(shè)計(jì)學(xué)習(xí)的重點(diǎn)。算法的概念

通俗地說(shuō)，算法就是解決問(wèn)題的方法和步驟。程序就是用計(jì)算機(jī)語(yǔ)言表述的算法。算法可以分為兩大類：

數(shù)值計(jì)算算法

求數(shù)值解，其特點(diǎn)是少量的輸入、輸出，復(fù)雜的運(yùn)算，如求高次方程的根、求函數(shù)的定積分等。

非數(shù)值計(jì)算算法

對(duì)數(shù)據(jù)的處理，其特點(diǎn)是大量的輸入、輸出，簡(jiǎn)單的運(yùn)算，例如，對(duì)數(shù)據(jù)的排序、查找等算法算法的概念

例如:求兩個(gè)正整數(shù)M和N的最大公因數(shù)的歐幾里德算法為:第一步:求M除以N的余數(shù)R;第二步:若R=0,算法結(jié)束,即N為M和N的最大公因數(shù)第三步:否則,置M←N,N←R,返回step1算法的概念對(duì)應(yīng)程序如下：#include<iostream.h>voidmain(){intm,n;cin>>m>>n;while(n!=0){r=m%n;m=n;n=r;}cout<<“m和n的最大公因數(shù)為:”<<m;}算法的概念

用計(jì)算機(jī)解決問(wèn)題的算法應(yīng)具有以下特征：

有窮性

能行性

確定性

可輸入輸出信息算法的表示

自然語(yǔ)言——使用人們能讀懂的簡(jiǎn)短語(yǔ)句對(duì)算法的步驟進(jìn)行描述。

流程圖法——用一些圖框、線條以及文字說(shuō)明來(lái)形象地、直觀地描述算法。

N-S流程圖法——去掉了傳統(tǒng)流程圖中帶箭頭的流向線，全部算法以一個(gè)大的矩形框表示，框內(nèi)還可以包含一些從屬于它的小矩形框，適于結(jié)構(gòu)化程序設(shè)計(jì)。

偽代碼法——用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。

計(jì)算機(jī)語(yǔ)言——用計(jì)算機(jī)語(yǔ)言描述算法，只有用計(jì)算機(jī)語(yǔ)言編寫(xiě)的程序才能被計(jì)算機(jī)執(zhí)行。算法的表示及三種基本結(jié)構(gòu)3循環(huán)結(jié)構(gòu)1順序結(jié)構(gòu)2分支結(jié)構(gòu)num1

15；算法的表示及三種基本結(jié)構(gòu)(1)

順序結(jié)構(gòu)【例】

求兩數(shù)之和。塊1塊2塊3流程圖

寄存器35＋顯示結(jié)果：35num115num220sum35num2

20；sum

num1+num2;

演示算法執(zhí)行過(guò)程輸出sum;算法的表示及三種基本結(jié)構(gòu)(2)

分支結(jié)構(gòu)【例】

輸入三個(gè)數(shù)，輸出其中的最大數(shù)。

x

7;y

12;z

10;if(x>y)max

x;elsemax

y;if(z>max)max

z;輸出max;x7y12z10CPUmax12比較比較顯示結(jié)果：12流程圖條件塊1塊2真假演示算法執(zhí)行過(guò)程算法的表示及三種基本結(jié)構(gòu)(3)

循環(huán)結(jié)構(gòu)流程圖條件塊真假【例】求4個(gè)整數(shù)的和。

0sum4count12x顯示結(jié)果：60演示算法執(zhí)行過(guò)程123142621642118600count

4;//整數(shù)個(gè)數(shù)sum

0;//累加和的初值while(count>0){x

輸入一個(gè)整數(shù);sum

sum+x;count

count-1;}輸出sum;算法的概念

對(duì)同一個(gè)問(wèn)題，可以有不同的解題方法和步驟。例如，求1+2+3+…+100，可以先進(jìn)行1+2，再加3，再加4，一直加到100，也可采取100+(1+99)+(2+98)+…+(49+51)+50＝100+50+49×100＝5050。還可以有其它的方法。當(dāng)然，方法有優(yōu)劣之分。有的方法只需進(jìn)行很少的步驟，而有些方法則需要較多的步驟。一般說(shuō)，希望采用方法簡(jiǎn)單，運(yùn)算步驟少的方法。因此，為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。常用算法介紹1.直接法2.枚舉法3.遞推法

解決的問(wèn)題的種類與復(fù)雜程度各不相同決定了算法的多樣性，但從其思想方法上可以將其歸為以下幾種：直接法、枚舉法、遞推法、遞歸法、回溯法等等。本節(jié)將介紹以下三種：常用算法介紹

直接法

直接法就是根據(jù)問(wèn)題給出的條件直接求解，前面的很多例子都是這種算法的運(yùn)用。這里不再舉例。常用算法介紹

枚舉法枚舉法也稱窮舉法，基本思想是，在有限范圍內(nèi)列舉所有可能的結(jié)果，找出其中符合要求的解。枚舉法適合求解的問(wèn)題是：?jiǎn)栴}可能的答案是有限個(gè)且答案是可知的，但又難以用解析法描述。這種算法通常需要用循環(huán)結(jié)構(gòu)來(lái)完成。請(qǐng)看下例：【例】

給定一個(gè)正整數(shù)，判斷其非負(fù)整數(shù)立方根是否存在，若存在，輸出該立方根。常用算法介紹算法如下：分析：設(shè)某正整數(shù)為27，則非負(fù)整數(shù)立方根的取值范圍為1—27，因此可在這一范圍內(nèi)對(duì)所有整數(shù)進(jìn)行檢測(cè)，滿足立方根為27的就是所求整數(shù)?！纠壳蠓秦?fù)整數(shù)立方根算法：常用算法介紹numc271顯示結(jié)果：3演示算法執(zhí)行過(guò)程比較c*c*c2比較c*c*c3比較c*c*cnum

27；c

1；//立方根初值while(c<=num){if(c*c*c==num){輸出c;break;//終止循環(huán)}elsec

c+1;}if(c>num)輸出“無(wú)整數(shù)立方根”;常用算法介紹【例】

判斷一個(gè)正整數(shù)是否素?cái)?shù)，給出相應(yīng)結(jié)果。分析：假設(shè)正整數(shù)num,如果num不是2，需要檢測(cè)它是否含有除1和它本身之外的其他因子，如果有，就不是素?cái)?shù)。檢測(cè)方法是在2

num-1范圍內(nèi)逐個(gè)驗(yàn)證。算法如下：常用算法介紹【例】

判斷一個(gè)數(shù)是否為素?cái)?shù)算法#include<iostream.h>voidmain(){intnum;cin>>num;for(inti=2;i<num;i++)if(num%i==0)break;if(i==num)cout<<num<<“是素?cái)?shù)”；

elsecout<<num<<“不是素?cái)?shù)”；}常用算法介紹

遞推法遞推算法是通過(guò)問(wèn)題的一個(gè)或多個(gè)已知解，用同樣的方法逐個(gè)推算出其他解，如數(shù)列問(wèn)題以及一些近似計(jì)算問(wèn)題等。通常也要借助于循環(huán)。請(qǐng)看下例：

常用算法介紹【例】

求n!

分析：n!=1

2

3

n，因此可以從1開(kāi)始，由1!乘以2得到2!，再乘以3得到3!

，以此推出n!。假定n＝4，算法如下：ni2factorial常用算法介紹【例】

求n!算法：顯示結(jié)果：24演示算法執(zhí)行過(guò)程124比較23比較64比較24比較5factorial

1; //階乘初值i

2;n4;while(i<=n){factorial

factorial*i;i

i+1;}輸出factorial;

8.3軟件開(kāi)發(fā)基礎(chǔ)軟件開(kāi)發(fā)不同于編寫(xiě)小程序，程序并不代表軟件，軟件包括程序和文檔兩部分。應(yīng)該把軟件開(kāi)發(fā)的全過(guò)程視為一項(xiàng)工程來(lái)處理，用工程的思想方法支持軟件的開(kāi)發(fā)，即軟件工程。從而用較小的投入開(kāi)發(fā)出更穩(wěn)定更有效率的高質(zhì)量的軟件。

8.3軟件開(kāi)發(fā)基礎(chǔ)軟件開(kāi)發(fā)的6個(gè)步驟：軟件需求分析問(wèn)題定義編寫(xiě)程序代碼軟件的測(cè)試軟件維護(hù)制作文檔

程序設(shè)計(jì)方法

傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)

SP(StructuredProgramming)

面向?qū)ο蟮某绦蛟O(shè)計(jì)

OOP(ObjectOrientedProgramming)

傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)傳統(tǒng)的程序設(shè)計(jì)方法可以歸結(jié)為“程序=算法+數(shù)據(jù)結(jié)構(gòu)”，將程序定義為處理數(shù)據(jù)的一系列過(guò)程。這種設(shè)計(jì)方法的著眼點(diǎn)是面向過(guò)程的，特點(diǎn)是數(shù)據(jù)與程序分離，即數(shù)據(jù)與數(shù)據(jù)處理分離。

結(jié)構(gòu)化程序設(shè)計(jì)的基本思想是采用自頂向下、逐步細(xì)化的模塊化程序設(shè)計(jì)原則。在代碼編寫(xiě)時(shí)，采用順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)，避免使用GOTO語(yǔ)句。

傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)模塊

22.12.2模塊11.21.11.31.3.11.3.21.3.3模塊

33.13.23.1.13.1.2

程序

傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)

結(jié)構(gòu)化程序設(shè)計(jì)為處理復(fù)雜問(wèn)題提供了有力手段，但到80年代末，這種設(shè)計(jì)方法逐漸暴露出以下缺陷：

難以適應(yīng)大型軟件的設(shè)計(jì)。

程序可重用性差。

面向?qū)ο蟪绦蛟O(shè)計(jì)

面向?qū)ο蟮某绦蛟O(shè)計(jì)方法是另一種程序設(shè)計(jì)方法

基本思想是：使用類把數(shù)據(jù)和處理數(shù)據(jù)的過(guò)程放在一起作為一個(gè)整體。基本方法是：抽象同類型對(duì)象的共性，形成類。類中數(shù)據(jù)通常只能被本類處理，對(duì)象間通過(guò)消息進(jìn)行通信。特征：封裝性、繼承性、多態(tài)性。

面向?qū)ο蟪绦蛟O(shè)計(jì)

對(duì)象的概念是面向?qū)ο蠹夹g(shù)的核心所在。面向?qū)ο蠹夹g(shù)中的對(duì)象就是現(xiàn)實(shí)世界中某個(gè)具體的物理實(shí)體在計(jì)算機(jī)邏輯中的映射和體現(xiàn)。對(duì)象、實(shí)體與類

現(xiàn)實(shí)世界中的實(shí)體可以抽象出類別的概念。對(duì)應(yīng)于計(jì)算機(jī)世界就有一個(gè)類（class）的概念，因?yàn)轭愂且粋€(gè)抽象的概念的對(duì)應(yīng)體，所以計(jì)算機(jī)不給它分配內(nèi)存，只給對(duì)象分配內(nèi)存。左圖表達(dá)了計(jì)算機(jī)世界與現(xiàn)實(shí)世界之間的對(duì)應(yīng)關(guān)系。計(jì)算機(jī)世界現(xiàn)實(shí)世界客觀世界映射對(duì)象類抽象抽象實(shí)例化主觀世界對(duì)象類實(shí)體抽象類別

面向?qū)ο蟪绦蛟O(shè)計(jì)FORTRAN語(yǔ)言FORTRAN語(yǔ)言是世界上第一個(gè)出現(xiàn)的高級(jí)程序設(shè)計(jì)語(yǔ)言FORTRAN是FORmulaTRANslator（公式翻譯器）的縮寫(xiě)，它主要用于科學(xué)計(jì)算，現(xiàn)在仍然廣泛用于數(shù)學(xué)、科學(xué)和工程計(jì)算問(wèn)題領(lǐng)域。

8.4常用的程序設(shè)計(jì)語(yǔ)言PASCAL語(yǔ)言P