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

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

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

算法

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

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

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

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

算法—對問題的處理規(guī)則

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

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

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

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

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

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

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

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

匯編語言（第二代語言）

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

面向問題的語言（第四代語言）

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

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

操作數(shù)

操作碼

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

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

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

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

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

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

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

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

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

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

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

匯編程序（匯編器）

編譯程序（編譯器）

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

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

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

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

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

接運(yùn)行編

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

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

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

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

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

運(yùn)算成分

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

控制成分

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

傳輸成分

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

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

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

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

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

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

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

一般程序設(shè)計(jì)語言中都提供了能支持計(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ì)語言的組成

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

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

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

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

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

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

函數(shù)過程

函數(shù)名有返回值

子過程

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

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

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

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

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

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

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

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

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

例如:求兩個(gè)正整數(shù)M和N的最大公因數(shù)的歐幾里德算法為:第一步:求M除以N的余數(shù)R;第二步:若R=0,算法結(jié)束,即N為M和N的最大公因數(shù)第三步:否則,置M←N,N←R,返回step1算法的概念對應(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ī)解決問題的算法應(yīng)具有以下特征：

有窮性

能行性

確定性

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

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

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

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

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

計(jì)算機(jī)語言——用計(jì)算機(jī)語言描述算法，只有用計(jì)算機(jī)語言編寫的程序才能被計(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í)行過程輸出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í)行過程算法的表示及三種基本結(jié)構(gòu)(3)

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

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

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

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

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

sum+x;count

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

對同一個(gè)問題，可以有不同的解題方法和步驟。例如，求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)行很少的步驟，而有些方法則需要較多的步驟。一般說，希望采用方法簡單，運(yùn)算步驟少的方法。因此，為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。常用算法介紹1.直接法2.枚舉法3.遞推法

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

直接法

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

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

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

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

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

常用算法介紹【例】

求n!

分析：n!=1

2

3

n，因此可以從1開始，由1!乘以2得到2!，再乘以3得到3!

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

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

1; //階乘初值i

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

factorial*i;i

i+1;}輸出factorial;

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

8.3軟件開發(fā)基礎(chǔ)軟件開發(fā)的6個(gè)步驟：軟件需求分析問題定義編寫程序代碼軟件的測試軟件維護(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ù)的一系列過程。這種設(shè)計(jì)方法的著眼點(diǎn)是面向過程的，特點(diǎn)是數(shù)據(jù)與程序分離，即數(shù)據(jù)與數(shù)據(jù)處理分離。

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

傳統(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ù)雜問題提供了有力手段，但到80年代末，這種設(shè)計(jì)方法逐漸暴露出以下缺陷：

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

程序可重用性差。

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

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

基本思想是：使用類把數(shù)據(jù)和處理數(shù)據(jù)的過程放在一起作為一個(gè)整體?；痉椒ㄊ牵撼橄笸愋蛯ο蟮墓残?，形成類。類中數(shù)據(jù)通常只能被本類處理，對象間通過消息進(jìn)行通信。特征：封裝性、繼承性、多態(tài)性。

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

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

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

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

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