《大學(xué)計(jì)算機(jī)基礎(chǔ)》第5章-程序設(shè)計(jì)基礎(chǔ).ppt

《《大學(xué)計(jì)算機(jī)基礎(chǔ)》第5章-程序設(shè)計(jì)基礎(chǔ).ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《《大學(xué)計(jì)算機(jī)基礎(chǔ)》第5章-程序設(shè)計(jì)基礎(chǔ).ppt（103頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1,大學(xué)計(jì)算機(jī)基礎(chǔ),北京航空航天大學(xué),教學(xué)課件,2,第5章程序設(shè)計(jì)基礎(chǔ),5.3程序設(shè)計(jì)步驟與程序設(shè)計(jì)方法,5.1程序和程序設(shè)計(jì)語(yǔ)言,5.2算法,5.4常用程序設(shè)計(jì)語(yǔ)言,5.5程序設(shè)計(jì)范型,,,,,,3,本章重點(diǎn),程序的概念程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)算法的概念與描述方法程序設(shè)計(jì)步驟程序設(shè)計(jì)方法,4,5.1程序和程序設(shè)計(jì)語(yǔ)言,5.1.1程序的一般概念5.1.2程序設(shè)計(jì)語(yǔ)言的概述5.1.3程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu),5,5.1.1程序的一般概念,生活中程序的概念,何事？,策劃,導(dǎo)演,例1：年終總結(jié)會(huì)的程序：會(huì)議主持宣布會(huì)議開(kāi)始領(lǐng)導(dǎo)講話(huà)個(gè)人或團(tuán)隊(duì)代表發(fā)言領(lǐng)導(dǎo)總結(jié)會(huì)議主持宣布會(huì)議結(jié)束,6,5.1.1程序的一般概念（續(xù)1）,生活中程序的概念,步行騎車(chē)開(kāi)車(chē)時(shí)間紅綠燈鐵道,依據(jù)實(shí)際案例并精心計(jì)算,解決該計(jì)算問(wèn)題的方法、步驟就包含了程序的概念。,例2：某人從甲地到丙地去。,7,5.1.1程序的一般概念（續(xù)2）,計(jì)算機(jī)程序的概念：,為實(shí)現(xiàn)某一算法而編寫(xiě)的指令序列。宏觀地描述該指令序列，可用計(jì)算機(jī)的機(jī)器語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言用經(jīng)典的公式可表示為：程序=算法+數(shù)據(jù)結(jié)構(gòu),8,5.1.2程序設(shè)計(jì)語(yǔ)言的概述,程序設(shè)計(jì)——編寫(xiě)程序的全過(guò)程。有學(xué)者認(rèn)為：程序設(shè)計(jì)=算法+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計(jì)語(yǔ)言,程序設(shè)計(jì)語(yǔ)言——人和計(jì)算機(jī)之間對(duì)話(huà)和交流的一種工具，用于描述計(jì)算機(jī)所執(zhí)行的操作。,計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言有幾百種，但是最常用的不過(guò)10多種，了解一些程序設(shè)計(jì)語(yǔ)言的不同特性，有助于為特定任務(wù)而選擇適當(dāng)?shù)某绦蛟O(shè)計(jì)語(yǔ)言。,9,1.機(jī)器語(yǔ)言（MachineLanguage）,指令——指揮計(jì)算機(jī)完成某個(gè)基本操作的命令。,指令系統(tǒng)——所有的指令集合。（第一代程序設(shè)計(jì)語(yǔ)言）機(jī)器語(yǔ)言——用二進(jìn)制代碼表示指令系統(tǒng)的語(yǔ)言。機(jī)器語(yǔ)言程序——由二進(jìn)制代碼按一定規(guī)則組成的、能被機(jī)器理解和運(yùn)行的指令序列。（也稱(chēng)可執(zhí)行程序）例如：計(jì)算累加器A=8+10的機(jī)器語(yǔ)言程序如下：,10,2.匯編語(yǔ)言（AssemblyLanguage）,匯編語(yǔ)言——實(shí)質(zhì)就是以容易記憶的代碼或英文單詞來(lái)代替約定的機(jī)器指令。（第二代程序設(shè)計(jì)語(yǔ)言）,例如：用ADD表示加、SUB表示減、JMP表示跳轉(zhuǎn)、MOV表示數(shù)據(jù)的傳送指令等。匯編源程序——使用匯編語(yǔ)言編寫(xiě)的程序。例如：上述計(jì)算累加器A=8+10的匯編語(yǔ)言程序如下：,11,3.高級(jí)語(yǔ)言（HighLevelLanguage）,高級(jí)語(yǔ)言——類(lèi)似數(shù)學(xué)語(yǔ)言或人的自然語(yǔ)言，同時(shí)又不依賴(lài)于某種計(jì)算機(jī)硬件，使得設(shè)計(jì)編制的程序能夠在所有機(jī)器上通用。（第三代程序設(shè)計(jì)語(yǔ)言）,程序設(shè)計(jì)語(yǔ)言在不同的系統(tǒng)平臺(tái)使用比較普遍的有：FORTRAN、ALGOL、COBOL、LISP、PL/I、BASIC、SIMULA67、Pascal、C、Smalltalk80、Ada、C++、VC、VB、Delphi、Java、JavaScript、C#、VisualBASIC.NET?？梢暬Z(yǔ)言——構(gòu)成了命令式語(yǔ)言中的另一個(gè)子類(lèi)。最流行的可視化語(yǔ)言VisualBASIC（1999年），已被VisualBASIC.NET（2002年）取代。提供拖拉式生成代碼段的功能。一度被認(rèn)作第四代語(yǔ)言，此說(shuō)法已不再使用了。,12,程序設(shè)計(jì)語(yǔ)言的特點(diǎn),機(jī)器語(yǔ)言的特點(diǎn)：編程難效率高需要指令系統(tǒng)難讀難維護(hù),高級(jí)語(yǔ)言的特點(diǎn)：編程容易效率低需要編譯系統(tǒng)易讀易維護(hù),匯編語(yǔ)言的特點(diǎn)：編程不容易效率較高需要匯編程序不易讀不易維護(hù),13,5.1.3程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu),程序結(jié)構(gòu)的多樣性：結(jié)構(gòu)化程序模塊化程序面向?qū)ο蟮某绦蚪Y(jié)構(gòu),一個(gè)良好結(jié)構(gòu)的程序具有以下等特點(diǎn)：結(jié)構(gòu)清晰容易閱讀容易理解容易驗(yàn)證容易維護(hù)1996年，計(jì)算機(jī)科學(xué)家Boehm和Jacopini提出并從數(shù)學(xué)上證明任何一個(gè)算法，都能以三種基本控制結(jié)構(gòu)表示，即順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。,14,結(jié)構(gòu)化程序設(shè)計(jì)中——順序結(jié)構(gòu),按照程序語(yǔ)句行的自然順序，一條語(yǔ)句一條語(yǔ)句地執(zhí)行程序。,15,結(jié)構(gòu)化程序設(shè)計(jì)中——選擇結(jié)構(gòu),根據(jù)條件的判斷確定應(yīng)該執(zhí)行哪一條分支的語(yǔ)句序列。（又稱(chēng)為分支結(jié)構(gòu)）,單分支、多分支結(jié)構(gòu)？,16,結(jié)構(gòu)化程序設(shè)計(jì)中——循環(huán)結(jié)構(gòu),主要用于重復(fù)執(zhí)行相同的語(yǔ)句序列（被稱(chēng)為循環(huán)體），直到判定條件為假（或?yàn)檎妫r(shí)才可終止執(zhí)行循環(huán)體。,17,結(jié)構(gòu)化程序設(shè)計(jì)的特點(diǎn),,每種結(jié)構(gòu)，只有一個(gè)入口和一個(gè)出口，這是結(jié)構(gòu)化設(shè)計(jì)的一個(gè)原則。,遵循結(jié)構(gòu)化程序設(shè)計(jì)的原則，按照結(jié)構(gòu)化程序設(shè)計(jì)方法設(shè)計(jì)出的程序具有明顯的優(yōu)點(diǎn)：其一，程序易讀、理解和維護(hù)。程序員用結(jié)構(gòu)化編程方法，將復(fù)雜程序分解成若干子結(jié)構(gòu)，便于控制、降低程序的復(fù)雜性，因此容易編寫(xiě)程序，同時(shí)便于驗(yàn)證程序。其二，提高編程工作效率，降低軟件開(kāi)發(fā)成本。由于結(jié)構(gòu)化編程方法能夠把錯(cuò)誤控制到最低限度，因此能夠減少調(diào)試和查錯(cuò)的時(shí)間。,18,5.2算法,5.2.1算法的概念與特征5.2.2算法的描述方法5.2.3程序設(shè)計(jì)典型算法,19,5.2.1算法的概念與特征,1976年NiklausWirth（也是Pascal語(yǔ)言發(fā)明者，1984年獲得圖靈獎(jiǎng)）的專(zhuān)著：,Algorithms＋DataStructures＝Programs（算法十?dāng)?shù)據(jù)結(jié)構(gòu)=程序）在計(jì)算機(jī)軟件開(kāi)發(fā)行業(yè)中產(chǎn)生了極為深遠(yuǎn)的影響，從而推動(dòng)了軟件開(kāi)發(fā)技術(shù)和方法步入正軌，使人們開(kāi)始深入研究數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)與分析的技術(shù)和方法。,20,1.算法的概念,算法——解決某個(gè)具體問(wèn)題而采取的方法與步驟的完整和準(zhǔn)確的描述。是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。是問(wèn)題的程序化解決方案，這些解決方案本身并不是答案，而是獲得答案的精確指令。,算法的分類(lèi)順序算法：是由馮諾依曼型計(jì)算機(jī)體系結(jié)構(gòu)所決定的，其主要思想是指令逐條運(yùn)行，每次執(zhí)行一步操作。并行算法：要求在一些更新式的計(jì)算機(jī)中可以在同一時(shí)間執(zhí)行多條指令。,21,2.算法的特征,一個(gè)算法必須具備五項(xiàng)基本特征：有窮性、確定性、數(shù)據(jù)輸入、數(shù)據(jù)輸出和可行性。,（1）有窮性——算法是有序指令的集合，并在執(zhí)行有窮步驟后能夠終止。（2）確定性——每條指令必須有確切的含義，且無(wú)二義性。在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對(duì)于相同的輸入數(shù)據(jù)只能得到相同的輸出數(shù)據(jù)。（3）輸入數(shù)據(jù)——可有零個(gè)或多個(gè)輸入數(shù)據(jù)。這些輸入數(shù)據(jù)取自于某個(gè)特定對(duì)象的集合。（4）輸出數(shù)據(jù)——必須有一個(gè)或多個(gè)輸出數(shù)據(jù)。（5）可行性——描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)，也可以證明整個(gè)算法實(shí)施后可以得到預(yù)期的解。,22,例5.1一個(gè)非算法的計(jì)數(shù)過(guò)程,①令n為0；②置n為n+1；③返回②。,結(jié)論：不能稱(chēng)為算法。原因：違背了算法特征中（1）、（4）、（5）。,23,例5.2計(jì)數(shù)器算法,用自然語(yǔ)言編寫(xiě)一個(gè)不超過(guò)1萬(wàn)次的計(jì)數(shù)器算法：①令n為0；②置n為n+1③若n小于10000，則返回②；否則，輸出n之值，且算法到此結(jié)束。,結(jié)論：是算法。原因：符合算法特征。,在算法設(shè)計(jì)過(guò)程中，其實(shí)還有有關(guān)正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求，以及算法效率的度量等問(wèn)題。,24,5.2.2算法的描述方法,流程圖（FlowChart）PAD圖（ProblemAnalysisDiafram，問(wèn)題分析圖）N-S圖自然語(yǔ)言偽代碼UML圖（UnifiedModelingLanguage，統(tǒng)一建模語(yǔ)言）,25,1.流程圖,流程圖（框圖）用不同形狀的幾何圖形表示不同性質(zhì)的操作，用流程線(xiàn)指明算法的執(zhí)行方向。ANSI(美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì))、ISO（國(guó)際標(biāo)準(zhǔn)化組織）和我國(guó)國(guó)家標(biāo)準(zhǔn)中均有類(lèi)似的規(guī)定。常見(jiàn)的流程圖符號(hào)如下：,向下或向右的流程線(xiàn)可以不畫(huà)出箭頭。當(dāng)流程線(xiàn)有交叉時(shí)，則畫(huà)一半圓通過(guò)交叉點(diǎn)。,26,用流程圖描述的計(jì)數(shù)器算法,27,2.PAD圖,由日立公司推出的PAD圖是一種二維圖。即從上向下順序執(zhí)行，從左到右表示層次關(guān)系。表示三種基本結(jié)構(gòu)的PAD圖如下：,28,3.N-S圖,1973年美國(guó)兩位學(xué)者提出無(wú)流程線(xiàn)的N-S圖（盒圖）。,結(jié)構(gòu)化程序設(shè)計(jì)由三種基本結(jié)構(gòu)而組成，則算法也應(yīng)采用結(jié)構(gòu)化描述方法，N-S圖的基本單元是矩形框，框內(nèi)可以有三種基本結(jié)構(gòu)，形如堆積木，也只有一個(gè)入口和一個(gè)出口。三種基本結(jié)構(gòu)的N-S圖如下：,29,用N-S圖描述的計(jì)數(shù)器算法,30,4.自然語(yǔ)言,自然語(yǔ)言是人們?nèi)粘Ｉ睢⒐ぷ骱蛯W(xué)習(xí)中使用的通用語(yǔ)言，使用自然語(yǔ)言的文字描述算法通俗易懂，但也有它的缺陷：,（1）容易產(chǎn)生歧義性，因?yàn)樽匀徽Z(yǔ)言經(jīng)常要根據(jù)上下文才能判別其含義，不太嚴(yán)格。（2）自然語(yǔ)言很難清楚地表達(dá)算法的邏輯流程，對(duì)于算法中的條件判斷、循環(huán)，尤其是在這些處理中還有多層嵌套，就很難用清晰而直觀的語(yǔ)言來(lái)表達(dá)算法的流程。因此僅適于描述簡(jiǎn)單問(wèn)題。,31,5.偽代碼,偽代碼是介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)，它不能被計(jì)算機(jī)所理解，但使用偽代碼描述的算法很容易轉(zhuǎn)變成某種編程語(yǔ)言。,//用偽代碼描述的計(jì)數(shù)器算法如下：n←0don←n+1whilenb)m=a;/*從a與b中取大數(shù)送m中*/elsem=b;if(m>c);/*從m與c中取大數(shù)送m中，“；”即m=m*/elsem=c;return(m);/*返回m給主函數(shù)*/}/*Endofmax3function*/,36,2.歐幾里得算法,求解兩個(gè)不全為0的非負(fù)整數(shù)m和n的最大公約數(shù)，可以采用以下歐幾里得算法。,,（1）歐幾里得算法主函數(shù)描述如下：①輸入兩個(gè)不全為0的非負(fù)整數(shù)m,n;②Ecd=Euclid(m,n);③輸出Ecd，且算法到此結(jié)束。,（2）Euclid(m,n)子函數(shù)算法描述如下：whilen≠0dor←mmodnm←nn←rreturnm,37,3.兩個(gè)變量值的交換算法,計(jì)算機(jī)實(shí)現(xiàn)的兩個(gè)變量值的交換算法如下：,①令a=5,b=10②c←a,a←b,b←c③輸出a和b的值。,/*兩個(gè)變量值交換算法的C源程序*/voidmain(void){inta=5,b=10,c;/*定義a、b、c3個(gè)整型變量*/printf(“交換前:a=%d,b=%d\n”,a,b);/*交換前輸出a和b的值*/c=a;/*將a中的值賦值給c*/a=b;/*將b中的值賦值給a*/b=c;/*將c中的值賦值給b*/printf(“交換后:a=%d,b=%d\n”,a,b);/*交換后輸出a和b的值*/}/*Endofmainfunction*/,三角對(duì)換法,38,4.排序算法,給定一個(gè)有n個(gè)元素可排序的序列，例如數(shù)字?jǐn)?shù)據(jù)或字符串?dāng)?shù)據(jù)等，要求按照升序或降序方式重新排列。,排序算法：如冒泡排序法、選擇排序法、插入排序法、合并排序法、快速排序法等等排序算法。,39,蠻力法中的選擇排序法,按照降序方式排序的選擇排序算法：,SelectionSort（Array[0..n-1]）/*本算法用選擇排序法對(duì)給定數(shù)組按照降序方式排序*//*Array[0..n-1]是有n個(gè)元素的可排序數(shù)組*//*本算法的結(jié)果在Array數(shù)組中*/fori←0ton-2domax←iforj←i+1ton-1doifArray[j]>Array[max]max←jswapArray[i]andArray[max],40,選擇排序法的C程序,/*SelectionSort(Array[0..n-1])選擇排序算法的C源程序*/voidSelectionSort(intn,intArray[]){inti,j,max,t;/*定義4個(gè)整型變量*/for(i=0;iArray[max])max=j;/*記錄大數(shù)元素的下標(biāo)位置*//*利用t變量做三角對(duì)換*/t=Array[i],Array[i]=Array[max],Array[max]=t;}}/*EndofSelectionSortfunction*/,41,選擇排序法降序方式排序操作過(guò)程,例如：對(duì)序列89，29，68，90，17，34，45操作。,|8929689017344590|2968891734459089|6829173445908968|2917344590896845|1734299089684534|1729908968453429|17,每行表示該算法的一次迭代，即從尾部到豎線(xiàn)的一遍掃描；找到的最大元素用黑體字表示，豎線(xiàn)左邊元素已經(jīng)位于它們的最終位置，所以在當(dāng)前和以后的循環(huán)中，都不必再操作了。排序操作過(guò)程如下：,42,5.查找算法,查找是指從給定的集合（或者是多重集，它允許幾個(gè)元素具有相同的值）中查找一個(gè)給定的值（稱(chēng)為查找鍵K）。,常用的查找算法有順序查找和折半查找，還有那些將原來(lái)的集合表示為另一種形式以方便查找的算法等等。順序查找——直接從頭到尾搜索集合的查找鍵。折半查找——必須首先將集合按照降序或升序排序，然后利用折半技術(shù)搜索集合的查找鍵，所以，當(dāng)集合是有序的時(shí)候，使用折半查找效率高、速度快。,43,判定哪一種算法是最佳方案,針對(duì)排序和查找方面的算法更多，例如，采用分治法、減治法、變治法等等方法中的各種排序和查找算法。,,運(yùn)用經(jīng)典的算法設(shè)計(jì)技術(shù)——時(shí)空權(quán)衡、動(dòng)態(tài)規(guī)劃、貪婪技術(shù)等；算法能力的極限中的決策樹(shù)技術(shù)、在多項(xiàng)式的時(shí)間內(nèi)求解、數(shù)值分析，超越算法能力的極限中的回溯發(fā)、分支界限法和近似算法設(shè)計(jì)技術(shù)。,技術(shù)和思維方式都是不可或缺的,鞭策學(xué)習(xí)和掌握程序設(shè)計(jì)中的算法設(shè)計(jì)與分析技術(shù),托馬斯愛(ài)迪生（1847-1931）的名言：“不斷關(guān)注那些已被他人成功應(yīng)用的新思路。你的原創(chuàng)思想只應(yīng)該應(yīng)用在那些你正在研究的問(wèn)題上”。,44,5.3程序設(shè)計(jì)步驟與程序設(shè)計(jì)方法,5.3.1程序設(shè)計(jì)步驟5.3.2程序設(shè)計(jì)方法,45,5.3.1程序設(shè)計(jì)步驟,一般程序設(shè)計(jì)應(yīng)該包含以下4個(gè)步驟：,（1）針對(duì)具體問(wèn)題進(jìn)行分析——了解問(wèn)題性質(zhì)，明確問(wèn)題解決所達(dá)目標(biāo)，提供的輸入是什么？最終實(shí)現(xiàn)的輸出是什么？執(zhí)行中要做什么？怎么做？并建立相應(yīng)的數(shù)學(xué)模型。（2）確定數(shù)據(jù)結(jié)構(gòu)并設(shè)計(jì)相應(yīng)的算法——對(duì)具體問(wèn)題進(jìn)行概念抽象，構(gòu)造出解決問(wèn)題的輪廓，設(shè)計(jì)程序的數(shù)據(jù)結(jié)構(gòu)和算法。（3）編寫(xiě)實(shí)現(xiàn)算法的程序——根據(jù)算法確定解決問(wèn)題的詳細(xì)步驟，通常是通過(guò)繪制程序流程圖，來(lái)描述問(wèn)題處理的過(guò)程；然后按照流程圖的描述選用某種程序設(shè)計(jì)語(yǔ)言編寫(xiě)程序。（4）測(cè)試與調(diào)試程序——在程序設(shè)計(jì)過(guò)程中，經(jīng)常不是那么一帆風(fēng)順的，尤其是初學(xué)者會(huì)遇到各種這樣或那樣的問(wèn)題，還有一些問(wèn)題可能是不可預(yù)測(cè)的，往往不得不返到上一步驟中更改或調(diào)整相應(yīng)的內(nèi)容，并將相應(yīng)文檔也一并修改，通過(guò)舉一反三的方法來(lái)解決給定問(wèn)題。,46,測(cè)試程序與調(diào)試程序,測(cè)試程序,為了發(fā)現(xiàn)程序中的設(shè)計(jì)錯(cuò)誤而運(yùn)行程序?！褂玫臏y(cè)試用例尤其重要，因?yàn)椴粌H需要合法值域用例，而且非法值域用例也是必須的?！绦驕y(cè)試的成功與否直接可以體現(xiàn)程序健壯性?！?dāng)軟件項(xiàng)目是由團(tuán)隊(duì)開(kāi)發(fā)時(shí)，測(cè)試程序可分為：?jiǎn)卧獪y(cè)試、組裝測(cè)試和確認(rèn)測(cè)試。調(diào)試程序錯(cuò)誤定位和糾錯(cuò)的過(guò)程，這一過(guò)程的快慢與程序設(shè)計(jì)人員的編程經(jīng)歷和經(jīng)驗(yàn)是密切相關(guān)的。,47,高級(jí)語(yǔ)言編寫(xiě)和運(yùn)行過(guò)程,48,5.3.2程序設(shè)計(jì)方法,早期的程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法面向?qū)ο蟪绦蛟O(shè)計(jì)方法,49,1.早期的程序設(shè)計(jì)方法,早期的程序設(shè)計(jì)方法追求程序的高效率，編程過(guò)份依賴(lài)技巧，忽視程序清晰，而不注重所編寫(xiě)程序的結(jié)構(gòu)，很少考慮程序的規(guī)范化問(wèn)題，也就是沒(méi)有固定程序設(shè)計(jì)方法的時(shí)期。,程序的可讀性、可重用性都很差。其中典型問(wèn)題是：頻繁使用goto語(yǔ)句，特意算計(jì)如何節(jié)省內(nèi)存空間。雖然這些方法存在很多問(wèn)題，但當(dāng)時(shí)受限于計(jì)算機(jī)運(yùn)行速度慢、內(nèi)存容量小、硬件價(jià)格昂貴，程序的規(guī)模也比較小，對(duì)于單人完成較為簡(jiǎn)單的任務(wù)，事實(shí)上這些方法還是經(jīng)常被采用的。,50,2.結(jié)構(gòu)化程序設(shè)計(jì)方法,結(jié)構(gòu)化程序設(shè)計(jì)方法出現(xiàn)在70年代中期。,隨著計(jì)算機(jī)硬件成本急劇下降，軟件需要處理的復(fù)雜問(wèn)題也就越來(lái)越多。為了擺脫60~70年代初的軟件危機(jī)，因?yàn)楫?dāng)時(shí)編程無(wú)章可循，程序常常帶有強(qiáng)烈的個(gè)人色彩，程序的可讀性差，程序的調(diào)試和維護(hù)更困難，促使人們認(rèn)真反省和研究程序設(shè)計(jì)中一系列根本性問(wèn)題：,程序的基本結(jié)構(gòu)是什么？程序設(shè)計(jì)應(yīng)當(dāng)采用什么方法？算法設(shè)計(jì)先于程序編碼？清晰第一，效率第二？程序設(shè)計(jì)技術(shù)與方法如何規(guī)范化和工程化？,解決手工作坊式軟件開(kāi)發(fā)的弊端,51,結(jié)構(gòu)化程序設(shè)計(jì)方法的特點(diǎn),使得程序?qū)哟畏置?、邏輯清晰、功能?dú)立，簡(jiǎn)化了開(kāi)發(fā)程序的復(fù)雜性，增加了程序的可靠性，能夠充分發(fā)揚(yáng)團(tuán)隊(duì)精神快速而高效地完成項(xiàng)目開(kāi)發(fā)，增強(qiáng)系統(tǒng)的可維護(hù)性，使程序設(shè)計(jì)更加規(guī)范化。,結(jié)構(gòu)化程序設(shè)計(jì)方法的特點(diǎn)：自頂向下、逐步求精劃分功能模塊結(jié)構(gòu)化編程,52,3.面向?qū)ο蟪绦蛟O(shè)計(jì)方法,面向?qū)ο蟪绦蛟O(shè)計(jì)方法出現(xiàn)在80年代中后期。,隨著計(jì)算機(jī)硬件技術(shù)的高速發(fā)展，計(jì)算機(jī)的性能也越來(lái)越強(qiáng)，用途也更加廣泛。軟件產(chǎn)業(yè)所面臨的問(wèn)題需求不斷擴(kuò)大，程序也就越來(lái)越龐大而復(fù)雜。在面向過(guò)程的程序設(shè)計(jì)中——軟件設(shè)計(jì)的主要工作就是用不同的功能模塊分別描述它們的求解過(guò)程。在結(jié)構(gòu)化程序設(shè)計(jì)中——數(shù)據(jù)和處理數(shù)據(jù)的過(guò)程分離為相互獨(dú)立的實(shí)體，它只是封裝了各個(gè)功能模塊，而每個(gè)功能模塊可以隨意修改未加封裝的數(shù)據(jù)。新時(shí)期的新問(wèn)題，以及軟件產(chǎn)業(yè)的更高要求，迫使人們?cè)俅螌で蟾涌茖W(xué)、更加先進(jìn)的程序設(shè)計(jì)方法。,53,面向?qū)ο蟪绦蛟O(shè)計(jì)（OOP）,Object-OrientedProgramming是建立在結(jié)構(gòu)化程序設(shè)計(jì)基礎(chǔ)上的，但它不再是從功能入手，而是從對(duì)象入手。,采用的是一種結(jié)構(gòu)模擬的方法。用“類(lèi)”描述具有相同屬性特征的一組對(duì)象，用“封裝”將對(duì)象的屬性和行為分別用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和方法來(lái)描述，并將它們綁定在一起形成一個(gè)可供訪(fǎng)問(wèn)的基本邏輯單元，利用“繼承”實(shí)現(xiàn)類(lèi)與類(lèi)之間的數(shù)據(jù)和方法的共享。,54,面向?qū)ο蟪绦蛟O(shè)計(jì)的重要概念,面向?qū)ο蟪绦蛟O(shè)計(jì)的重要概念：對(duì)象（Object）類(lèi)（Class）消息（Message）方法（Method）,55,對(duì)象（Object）,面向?qū)ο蟪绦蛟O(shè)計(jì)中的對(duì)象——現(xiàn)實(shí)世界中的客體在應(yīng)用程序中的具體體現(xiàn)，其中封裝了客體的屬性信息和行為方式，并用數(shù)據(jù)表示屬性，用方法表示行為方式。,對(duì)象中的數(shù)據(jù)記錄了客體的屬性狀態(tài)，方法決定了客體所能夠?qū)嵤┑牟僮餍袨楹团c其它對(duì)象進(jìn)行通信的接口方式。對(duì)象并非孤立存在，消息傳遞是對(duì)象之間相互聯(lián)系的唯一途徑，發(fā)送者發(fā)送消息，接收者通過(guò)調(diào)用相應(yīng)的方法響應(yīng)消息，這個(gè)過(guò)程被不斷地重復(fù)，從而驅(qū)動(dòng)整個(gè)程序的運(yùn)轉(zhuǎn)。,56,類(lèi)（Class）,人類(lèi)在認(rèn)知客觀世界時(shí)，將眾多的事物歸納、劃分成一些類(lèi)，這是經(jīng)常采用的思維方法。分類(lèi)所依據(jù)的原則是抽象。,類(lèi)是具有相同屬性和行為方式的一組對(duì)象的集合，或者說(shuō)，類(lèi)是指對(duì)一組具有相同特征（包括屬性、操作、方法、關(guān)系、行為）的對(duì)象的抽象描述，任何對(duì)象都是某個(gè)類(lèi)的實(shí)例。對(duì)象是系統(tǒng)運(yùn)行時(shí)將類(lèi)作為生成對(duì)象實(shí)例的模板，通過(guò)分配私有存儲(chǔ)空間，然后對(duì)相應(yīng)的屬性賦初始值而創(chuàng)建的，這個(gè)過(guò)程在面向?qū)ο蟪绦蛟O(shè)計(jì)中稱(chēng)為“實(shí)例化”。類(lèi)與對(duì)象的關(guān)系猶如模具與鑄件之間的關(guān)系。,57,消息（Message）,消息——一個(gè)對(duì)象要求另一個(gè)對(duì)象實(shí)施某項(xiàng)操作的請(qǐng)求。,在一條消息中，需要包含消息的接收者和要求接收者執(zhí)行某項(xiàng)操作的請(qǐng)求，但具體的操作過(guò)程由接收者自行決定，這樣可以很好地保證系統(tǒng)的模塊性。消息傳遞是對(duì)象之間相互聯(lián)系的唯一途徑。發(fā)送者發(fā)送消息，接收者通過(guò)調(diào)用相應(yīng)的方法響應(yīng)消息，這個(gè)過(guò)程被不斷地重復(fù)，從而驅(qū)動(dòng)整個(gè)程序的運(yùn)轉(zhuǎn)。,58,方法（Method）,面向?qū)ο蠹夹g(shù)中的方法——針對(duì)對(duì)象的屬性的各種操作。,將一些通用的過(guò)程或函數(shù)編寫(xiě)好并封裝起來(lái)，作為方法直接提供給用戶(hù)調(diào)用。,59,面向?qū)ο蟪绦蛟O(shè)計(jì)幾個(gè)重要的基本特征,面向?qū)ο蟪绦蛟O(shè)計(jì)幾個(gè)重要的基本特征：抽象（Abstract）封裝（Encapsulation）繼承（Inheritance）多態(tài)（Polymorphism）,60,抽象（Abstract）,抽象——忽略事物的非本質(zhì)特征，只注意那些與當(dāng)前目標(biāo)有關(guān)的本質(zhì)特征，從而找出事物的共性，把具有共同性質(zhì)的事物劃分為一類(lèi)，得出一個(gè)抽象的概念。,在理解復(fù)雜的現(xiàn)實(shí)世界和解決復(fù)雜的特定問(wèn)題時(shí)，如何從繁雜的信息集中抽取出有用的、能夠反映事物本質(zhì)的東西，降低其復(fù)雜程度是解決問(wèn)題的關(guān)鍵，而抽象正是降低復(fù)雜度的最佳途徑。抽象可分為過(guò)程抽象和數(shù)據(jù)抽象過(guò)程抽象——即功能抽象，舍棄個(gè)別功能，抽取共同擁有的功能。數(shù)據(jù)抽象——一種更高級(jí)別的抽象，它將現(xiàn)實(shí)世界中存在的客體作為抽象單元，其抽象內(nèi)容既包括客體的屬性特征，也包括行為特征（起到信息隱藏的作用）。它是面向?qū)ο蟪绦蛟O(shè)計(jì)所采用的核心方法。,61,封裝（Encapsulation）,面向?qū)ο蟪绦蛟O(shè)計(jì)中的封裝——將對(duì)象的屬性和行為分別使用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和方法來(lái)描述，并將它們綁定在一起形成一個(gè)可供訪(fǎng)問(wèn)的基本邏輯單元。,用戶(hù)對(duì)數(shù)據(jù)結(jié)構(gòu)的訪(fǎng)問(wèn)只能通過(guò)使用類(lèi)提供的外部接口。這樣，將描述這些屬性的數(shù)據(jù)結(jié)構(gòu)和訪(fǎng)問(wèn)這些數(shù)據(jù)結(jié)構(gòu)的方法封裝在一個(gè)對(duì)象中，從而使數(shù)據(jù)結(jié)構(gòu)得到隱藏，不允許外界直接訪(fǎng)問(wèn)。其它對(duì)象只能通過(guò)封裝提供的外部接口（這些方法）對(duì)該對(duì)象實(shí)施各項(xiàng)操作，保證了數(shù)據(jù)結(jié)構(gòu)的安全，提高了系統(tǒng)的可維護(hù)性和可移植性。,62,繼承（Inheritance）,繼承是面向?qū)ο蠹夹g(shù)提高軟件開(kāi)發(fā)效率的重要措施，如果類(lèi)與類(lèi)之間有is-a（是一種）的關(guān)系，則可用繼承機(jī)制來(lái)表示。,其定義是：特殊類(lèi)的對(duì)象擁有其一般類(lèi)的全部屬性和服務(wù)，稱(chēng)作特殊類(lèi)對(duì)一般類(lèi)的繼承。它體現(xiàn)了類(lèi)與類(lèi)之間的不同抽象級(jí)別。根據(jù)繼承與被繼承的關(guān)系，可分為派生類(lèi)（或稱(chēng)子類(lèi)）和基類(lèi)（或稱(chēng)父類(lèi)）。繼承機(jī)制其實(shí)質(zhì)是反映了從一般到特殊的關(guān)系，父類(lèi)表現(xiàn)出的是共性和一般性，子類(lèi)表現(xiàn)出的是個(gè)性和特殊性，子類(lèi)從父類(lèi)那里獲得所有的屬性和方法，并且可以對(duì)這些獲得的屬性和方法加以改造，使之具有自己的特點(diǎn)。繼承對(duì)于軟件復(fù)用和擴(kuò)充有著及其重要的意義，利用代碼重用技術(shù)，能夠降低開(kāi)發(fā)投入，加快軟件開(kāi)發(fā)速度、提高軟件質(zhì)量，減少維護(hù)成本。繼承可分為公有繼承（public）、私有繼承（private）和保護(hù)繼承（protected）三種訪(fǎng)問(wèn)控制方式。,63,多態(tài)（Polymorphism）,多態(tài)——不同層次的類(lèi)中，以及在一個(gè)類(lèi)的內(nèi)部，同名成員函數(shù)之間的關(guān)系問(wèn)題，是解決功能和行為的再抽象。,多態(tài)是指不同的對(duì)象收到相同的消息時(shí)產(chǎn)生多種不同的行為方式。它是一種用統(tǒng)一的方式來(lái)處理一組各具個(gè)性卻同屬一族的不同個(gè)體的機(jī)制，這就使得同樣的消息被不同的對(duì)象接收時(shí)，將被解釋為不同的語(yǔ)義。例如：定義了多個(gè)“add”相加的同名函數(shù)，但它們的參數(shù)類(lèi)型各不相同，如果用整型之間、實(shí)型之間、雙精度浮點(diǎn)型之間分別表示相加運(yùn)算，則當(dāng)同樣的消息（相加）被不同類(lèi)型的對(duì)象（變量）接收后，不同類(lèi)型的變量將采用不同的方式進(jìn)行加法運(yùn)算。,,64,5.4常用程序設(shè)計(jì)語(yǔ)言,5.4.1科學(xué)計(jì)算語(yǔ)言5.4.2結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言5.4.3面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言5.4.4其它程序設(shè)計(jì)語(yǔ)言5.4.5標(biāo)記式語(yǔ)言HTML和XHTML5.4.6腳本語(yǔ)言,65,5.4.1科學(xué)計(jì)算語(yǔ)言,FORTRAN（FORmulaTRANslating）可稱(chēng)之為第一個(gè)高級(jí)編譯語(yǔ)言，從其用詞及涵義即把應(yīng)用領(lǐng)域的目標(biāo)鎖定在科學(xué)計(jì)算（或稱(chēng)數(shù)值計(jì)算）上。,Fortran90中有Pascal特征，如指針、遞歸、動(dòng)態(tài)數(shù)組等概念。Fortran95中簡(jiǎn)化了開(kāi)發(fā)并行程序的任務(wù)，去除了Fortran90中的許多特性，還有一些特性被置入“待廢棄之列”。,從JohnBackus（1977年獲得圖靈獎(jiǎng)）的Fortran0到目前的Fortran95，版本不斷更新，程序設(shè)計(jì)人員只要面對(duì)解決科學(xué)計(jì)算問(wèn)題時(shí)，就會(huì)自然想到使用公式翻譯語(yǔ)言。Fortran高級(jí)程序設(shè)計(jì)語(yǔ)言歷經(jīng)如此漫長(zhǎng)的年代變遷，還是具有那么長(zhǎng)久的生命力，這與它為適應(yīng)計(jì)算機(jī)時(shí)代的需求而不斷創(chuàng)新是分不開(kāi)的。在該語(yǔ)言的發(fā)展歷史中，最為重要的版本如下：FortranⅥFortran66Fortran77Fortran90Fortran95,66,5.4.2結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言,擺脫60年代末軟件危機(jī)的最佳解決方案，使開(kāi)發(fā)軟件編寫(xiě)代碼的過(guò)程中能夠循規(guī)蹈矩地步入正軌，各類(lèi)開(kāi)發(fā)人員能夠不謀而合地使用結(jié)構(gòu)化程序設(shè)計(jì)的算法最小集來(lái)完成。,語(yǔ)言完整性而言，有非結(jié)構(gòu)化語(yǔ)句，例如：goto、continue、break等語(yǔ)句，用到它們的話(huà)，也會(huì)嚴(yán)格按照結(jié)構(gòu)化程序設(shè)計(jì)的要求和約定用法限制來(lái)使用。結(jié)構(gòu)化程序設(shè)計(jì)開(kāi)發(fā)方法使得軟件代碼可讀性、可維護(hù)性、以及可擴(kuò)充性都得到了有力支持。Pascal、C是最成功的結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言，既是在面向?qū)ο蟪绦蛟O(shè)計(jì)中結(jié)構(gòu)化程序設(shè)計(jì)開(kāi)發(fā)方法依然在發(fā)揮著極其重要的作用。,67,1.Pascal語(yǔ)言,1971年，NiklausWirth推出了Pascal語(yǔ)言（以法國(guó)數(shù)學(xué)家BlaisePascal為命名），這應(yīng)該屬于wirth前期研究ALGOL60，以及吸取COBOL和PL/Ⅰ的優(yōu)良特性后，而專(zhuān)門(mén)設(shè)計(jì)用于程序設(shè)計(jì)教學(xué)的語(yǔ)言。,Pascal語(yǔ)言的語(yǔ)法非常嚴(yán)謹(jǐn)，類(lèi)型豐富，層次分明，易讀易寫(xiě)，是第一個(gè)結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言，它是簡(jiǎn)單性和易于表達(dá)的完美結(jié)合。在70年代中期之前，通常在大學(xué)的計(jì)算機(jī)程序設(shè)計(jì)課程教學(xué)都是采用Fortran、PL/Ⅰ、或ALGOL語(yǔ)言，但以后都被Pascal語(yǔ)言所取代，其主要原因是Pascal語(yǔ)言是最適合于結(jié)構(gòu)化程序設(shè)計(jì)的教學(xué)。,68,2.C語(yǔ)言,1972年，美國(guó)貝爾實(shí)驗(yàn)室的KennethLaneThompson和DennisMacAlistairRitchie（1983年獲得圖靈獎(jiǎng)）為了重新改寫(xiě)UNIX操作系統(tǒng)，而共同設(shè)計(jì)、開(kāi)發(fā)了C語(yǔ)言。,C是由CPL、BCPL、B和ALGOL68等繼承發(fā)展而來(lái)的。CPL在60年代初開(kāi)發(fā)于劍橋大學(xué)。BCPL是1967年由MartinRichards開(kāi)發(fā)的一種簡(jiǎn)單的系統(tǒng)語(yǔ)言。60年代末Thompson用匯編語(yǔ)言編寫(xiě)了第一版UNIX操作系統(tǒng)。1970年他以BCPL為基礎(chǔ)，在UNIX下實(shí)現(xiàn)了第一個(gè)高級(jí)語(yǔ)言B。,69,5.4.3面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言,面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言經(jīng)歷了一個(gè)很長(zhǎng)的發(fā)展階段，面向?qū)ο蟪绦蛟O(shè)計(jì)概念的許多原始思想都來(lái)之于Simula67，但是直到Smalltalk演化到Smalltalk80時(shí)（1980年），面向?qū)ο蟪绦蛟O(shè)計(jì)才得到了充分的發(fā)展。同時(shí)對(duì)以前的思想作了新的解釋。,可以說(shuō)面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言與面向?qū)ο笏枷霂缀跏峭桨l(fā)展并相互促進(jìn)的。早先的面向?qū)ο笳Z(yǔ)言，如：LISP、Simula67、Smalltalk、CLU、CwithClasses、Ada83、Modula-2和Smalltalk80等語(yǔ)言。,70,1.C++語(yǔ)言,1980年，BjarneStroustrup博士（1993年獲得了ACMGraceMurrayHopper獎(jiǎng)）在貝爾實(shí)驗(yàn)室開(kāi)始研究從C到C++的開(kāi)發(fā)。,經(jīng)歷了漫長(zhǎng)的5年時(shí)間，在1985年推出了第一個(gè)可以實(shí)現(xiàn)的C++1.0版本，被稱(chēng)為Cfront。隨后至1990年推出了C++3.0版本。1998年ISO對(duì)C++進(jìn)行了標(biāo)準(zhǔn)化。1990年有了ANSIC++標(biāo)準(zhǔn)。,71,2.Java語(yǔ)言,Java是SunMicrosystems公司在1995年推出的一種編程語(yǔ)言。通常我們以JDK（Sun開(kāi)發(fā)的一套Java開(kāi)發(fā)工具）的版本來(lái)定義Java的版本。目前最新的版本是6.0。,Java是一種簡(jiǎn)單、面向?qū)ο蟆⑵脚_(tái)無(wú)關(guān)、分布式、解釋型、安全可靠、性能優(yōu)異、多線(xiàn)程、動(dòng)態(tài)的高級(jí)程序設(shè)計(jì)語(yǔ)言，特別適合在網(wǎng)絡(luò)環(huán)境下的編程使用。,72,3.C#語(yǔ)言,C#（讀作Csharp）是一種為生成在.NETFramework上運(yùn)行的多種應(yīng)用程序而設(shè)計(jì)的面向?qū)ο蟮木幊陶Z(yǔ)言。,簡(jiǎn)單、功能強(qiáng)大、類(lèi)型安全。起源于C語(yǔ)言家族，憑借它的許多創(chuàng)新，在保持C樣式語(yǔ)言的表示形式和優(yōu)美的同時(shí)，實(shí)現(xiàn)了應(yīng)用程序的快速開(kāi)發(fā)。語(yǔ)法表現(xiàn)力強(qiáng)，易學(xué)。語(yǔ)法方面簡(jiǎn)化了C++的諸多復(fù)雜性，同時(shí)提供了很多強(qiáng)大的功能，例如，可為空的值類(lèi)型、枚舉、委托、匿名方法和直接內(nèi)存訪(fǎng)問(wèn)，這些都是Java所不具備的。支持泛型方法和類(lèi)型，從而提供了更出色的類(lèi)型安全和性能。提供了迭代器，允許集合類(lèi)的實(shí)現(xiàn)者自定義迭代方法，簡(jiǎn)化了客戶(hù)端代碼對(duì)它的使用。,73,5.4.4其它程序設(shè)計(jì)語(yǔ)言,ALGOL語(yǔ)言COBOL語(yǔ)言BASIC語(yǔ)言Ada語(yǔ)言L(fǎng)ISP函數(shù)型程序設(shè)計(jì)語(yǔ)言Prolog邏輯程序設(shè)計(jì)語(yǔ)言,74,1.ALGOL語(yǔ)言,ALGOL（ALGOrithmicLanguage）稱(chēng)為算法語(yǔ)言。,ALGOL語(yǔ)言的版本58、60、68，它是第一種國(guó)際性的團(tuán)體GAMM（SocietyforAppliedMathematicsandMechanics的德文縮寫(xiě)）和ACM（AssociationforComputingMachinery，美國(guó)計(jì)算機(jī)學(xué)會(huì)）共同設(shè)計(jì)的程序設(shè)計(jì)語(yǔ)言，也是第一種與機(jī)器無(wú)關(guān)的語(yǔ)言。第一種語(yǔ)法得到正式描述的語(yǔ)言。巴科斯范式（Backus-Naurform，BNF）形式化的成功應(yīng)用促進(jìn)了計(jì)算機(jī)科學(xué)許多重要領(lǐng)域的發(fā)展。其地位維持了長(zhǎng)達(dá)二十余年之久。從1960年以來(lái)所設(shè)計(jì)的每一種命令式程序設(shè)計(jì)語(yǔ)言都與ALGOL60不無(wú)干系。實(shí)際上，它們大多數(shù)都可直接或間接地算是ALGOL60的新版本。例如，PL/Ⅰ、SIMULA67、ALGOL68、C、Pascal、Ada、C++、Java等。,75,2.COBOL語(yǔ)言,COBOL（COmmonBusinessOrientedLanguage）稱(chēng)為商業(yè)應(yīng)用通用語(yǔ)言。,1959年5月，美國(guó)國(guó)防部提供資助，由一個(gè)委員會(huì)通過(guò)會(huì)議在相當(dāng)短的時(shí)間內(nèi)設(shè)計(jì)出來(lái)的。首次實(shí)現(xiàn)了層次數(shù)據(jù)結(jié)構(gòu)。每個(gè)變量都在數(shù)據(jù)劃分中詳細(xì)定義，包括小數(shù)位數(shù)和小數(shù)點(diǎn)的位置。文件記錄的描述也同樣詳細(xì)，它們被描述為輸出至打印機(jī)的行，這就使COBOL非常適合于打印報(bào)表。支持長(zhǎng)名（30個(gè)字符）和連字符，使編寫(xiě)出的程序能夠望文生義。經(jīng)歷了不同版本的更新，1968年、1974年和1985年都有ANSI標(biāo)準(zhǔn)化。導(dǎo)致財(cái)會(huì)電算化，從任何意義上講，這都是一個(gè)極其重要的革新。目前，我國(guó)還有不少群體在使用該語(yǔ)言，國(guó)外使用則依然比較普遍，而該語(yǔ)言本身仍然在繼續(xù)發(fā)展中。,76,3.BASIC語(yǔ)言,BASIC（BeginnersAll-purposeSymbolicInstructionCode）語(yǔ)言是一種得到廣泛使用但聲譽(yù)不太高的程序設(shè)計(jì)語(yǔ)言。,數(shù)學(xué)家JohnKemeny和ThomasKurtz在新漢普郡的Dartmouth學(xué)院（現(xiàn)為大學(xué)）設(shè)計(jì)出來(lái)的（60年代初曾參與過(guò)許多版本的Fortran和ALGOL60編譯器的研制）。早期BASIC是第一種通過(guò)連接至遠(yuǎn)程終端加以使用的語(yǔ)言，當(dāng)時(shí)終端剛剛出現(xiàn)，而在此之前，大多數(shù)程序都只能通過(guò)打孔卡片或紙帶輸入計(jì)算機(jī)。1964年5月1號(hào)凌晨4點(diǎn)，終于誕生了第一個(gè)使用分時(shí)BASIC的程序。隨著微機(jī)的誕生，BASIC又被配置在微機(jī)上，以解釋性或編譯性方式運(yùn)行程序，因?yàn)橐讓W(xué)，對(duì)計(jì)算機(jī)的推廣應(yīng)用起到了重要作用。BASIC也經(jīng)歷了各種版本，例如，TurboBASIC、QuickBASIC等，由于用BASIC編寫(xiě)的程序結(jié)構(gòu)性很差，在其發(fā)展過(guò)程中幾乎沒(méi)有進(jìn)行過(guò)標(biāo)準(zhǔn)化。,77,VisualBASIC的出現(xiàn),直到1991年，微軟推出基于Windows環(huán)境，采用可視化界面設(shè)計(jì)和事件驅(qū)動(dòng)的編程機(jī)制，以及基于對(duì)象的開(kāi)發(fā)工具VisualBASIC1.0版本之后，才又激發(fā)了廣大計(jì)算機(jī)愛(ài)好者的興趣。,VB已經(jīng)更新到VisualBASIC6.0版本。微軟現(xiàn)在的VisualBASIC.NET網(wǎng)絡(luò)功能更強(qiáng)（它還只是微軟VisualStudio.NET中的成員之一），是VB的替代品。因?yàn)樗鼈兇嬖谥@著的不同差異，有些使用者開(kāi)始轉(zhuǎn)向使用C#。,78,4.Ada語(yǔ)言,Ada語(yǔ)言是為美國(guó)國(guó)防部（DepartmentofDefense，DoD）開(kāi)發(fā)的。,1975年，美國(guó)國(guó)防部研究和工程部主任MalcolmCurrie成立了高級(jí)語(yǔ)言工作組，其成員來(lái)自軍界各個(gè)行業(yè)，另外還與英國(guó)、法國(guó)和西德保持著聯(lián)系。Ada語(yǔ)言的研究與開(kāi)發(fā)可分為：前三個(gè)階段（1983年之前）圍繞Ada83版本。后三個(gè)階段（1988年之后）圍繞Ada9X版本。中間Ada語(yǔ)言設(shè)計(jì)則封凍了至少5年。,79,5.LISP函數(shù)型程序設(shè)計(jì)語(yǔ)言,LISP（ListProcessor）是一個(gè)全面而強(qiáng)大的語(yǔ)言。,早期人們視其為一個(gè)外觀和表現(xiàn)很奇怪的語(yǔ)言，而且認(rèn)為使用LISP的開(kāi)銷(xiāo)相當(dāng)大。LISP的開(kāi)發(fā)是為了用于符號(hào)計(jì)算和表處理應(yīng)用，主要是AI（ArtificialIntelligence，人工智能）領(lǐng)域的計(jì)算。在許多AI應(yīng)用中，LISP及其以后的版本仍是標(biāo)準(zhǔn)語(yǔ)言。在AI中，許多領(lǐng)域都已經(jīng)得到開(kāi)發(fā)，這主要?dú)w功于LISP的應(yīng)用。盡管也可以使用其它類(lèi)型的語(yǔ)言（主要是邏輯程序設(shè)計(jì)語(yǔ)言），但大多數(shù)現(xiàn)有的專(zhuān)家系統(tǒng)都是用LISP開(kāi)發(fā)的。LISP還在知識(shí)表示、機(jī)器學(xué)習(xí)、智能訓(xùn)練系統(tǒng)和語(yǔ)音建模等領(lǐng)域占據(jù)著主導(dǎo)地位。,80,在AI領(lǐng)域之外,在AI領(lǐng)域之外，LISP也相當(dāng)成功。,例如，EMACS文本編輯器就是用LISP編寫(xiě)的，符號(hào)數(shù)學(xué)系統(tǒng)MACSYMA也是用LISP編寫(xiě)的，此系統(tǒng)除了提供其它功能外，還可以完成符號(hào)區(qū)分和集成。LISP機(jī)器是一種個(gè)人計(jì)算機(jī)，其整個(gè)系統(tǒng)軟件均用LISP編寫(xiě)。LISP還成功地用于為大量應(yīng)用領(lǐng)域構(gòu)造專(zhuān)家系統(tǒng)。,81,6.Prolog邏輯程序設(shè)計(jì)語(yǔ)言,邏輯程序設(shè)計(jì)起源要?dú)w功于Robinson為邏輯推導(dǎo)所開(kāi)發(fā)的規(guī)約規(guī)則。,Prolog主要由Aix-Marseille大學(xué)的AlainColmeraur和PhillippeRoussel所開(kāi)發(fā)，并得到了Edinburgh大學(xué)的RobertKowalski的一些幫助。關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)（RelationalDatabaseManagementSystems，RDBMS）以表的形式存儲(chǔ)數(shù)據(jù)。查詢(xún)通常用關(guān)系算子表示，這是一種符號(hào)邏輯形式。這些系統(tǒng)查詢(xún)語(yǔ)言是非過(guò)程性的，而邏輯程序設(shè)計(jì)也是非過(guò)程性的，因此二者從這個(gè)意義上講是相同的，用戶(hù)不必描述如何檢索出答案，只需描述答案的特征即可。,82,6.Prolog邏輯程序設(shè)計(jì)語(yǔ)言（續(xù)）,邏輯程序設(shè)計(jì)和RDBMS之間的關(guān)聯(lián)是很顯然的。,簡(jiǎn)單的信息表可以由Prolog結(jié)構(gòu)來(lái)描述，而表之間的關(guān)系則可以方便而容易地描述為Prolog規(guī)則。檢索過(guò)程交由規(guī)約操作完成，Prolog的目標(biāo)語(yǔ)句提供了對(duì)RDBMS的查詢(xún)。因此，邏輯程序設(shè)計(jì)恰能滿(mǎn)足RDBMS實(shí)現(xiàn)的需求。符號(hào)邏輯提供了邏輯程序設(shè)計(jì)和語(yǔ)言的基礎(chǔ)。邏輯程序設(shè)計(jì)的方法是將一組事實(shí)和規(guī)則（表示事實(shí)間關(guān)系）用作為一個(gè)數(shù)據(jù)庫(kù)，并使用一個(gè)自動(dòng)推導(dǎo)過(guò)程來(lái)檢查新命題的合法性，在此假設(shè)數(shù)據(jù)庫(kù)中的事實(shí)和規(guī)則均為真，這種方法正是為自動(dòng)定理證明開(kāi)發(fā)的。,83,5.4.5標(biāo)記式語(yǔ)言HTML和XHTML,HTML（HypertextMarkupLanguage）即超文本標(biāo)記語(yǔ)言。XHTML（eXtensibleHTML）是一種在HTML基礎(chǔ)上優(yōu)化和改進(jìn)的新語(yǔ)言。,84,1.HTML超文本標(biāo)記語(yǔ)言,HTML（超文本標(biāo)記語(yǔ)言）是WWW（WorldWideWeb）的描述語(yǔ)言。由TimBerners-lee提出。,設(shè)計(jì)目的能把存放在一臺(tái)電腦中的文本或圖形與另一臺(tái)電腦中的文本或圖形方便地聯(lián)系在一起，形成有機(jī)的整體，人們不用考慮具體信息是在當(dāng)前電腦上還是在網(wǎng)絡(luò)的其它電腦上。用鼠標(biāo)在某一文檔中點(diǎn)取一個(gè)圖標(biāo)，Internet就會(huì)馬上轉(zhuǎn)到與此圖標(biāo)相關(guān)的內(nèi)容上去，而這些信息可能存放在網(wǎng)絡(luò)的另一臺(tái)電腦中。HTML是由HTML命令組成的描述性文本，HTML命令可以說(shuō)明文字、圖形、動(dòng)畫(huà)、聲音、表格、鏈接等。HTML的結(jié)構(gòu)包括頭部（Head）、主體（Body）兩大部分。頭部描述瀏覽器所需的信息，主體包含所要說(shuō)明的具體內(nèi)容。,85,2.XHTML,2000年底，國(guó)際W3C（WWWConsortium）組織公布發(fā)行了XHTML1.0版本。XHTML1.0是一種在HTML4.0基礎(chǔ)上優(yōu)化和改進(jìn)的新語(yǔ)言。,設(shè)計(jì)目的基于XML（eXtensibleMarkupLanguage）應(yīng)用。XHTML（eXtensibleHTML）是一種增強(qiáng)了的HTML。它的可擴(kuò)展性和靈活性將適應(yīng)未來(lái)網(wǎng)絡(luò)應(yīng)用更多的需求。,86,HTML三個(gè)主要缺點(diǎn),XHTML解決HTML語(yǔ)言所存在的嚴(yán)重制約其發(fā)展的問(wèn)題。,HTML發(fā)展到今天存在三個(gè)主要缺點(diǎn)：不能適應(yīng)現(xiàn)在越來(lái)越多的網(wǎng)絡(luò)設(shè)備和應(yīng)用的需要。（手機(jī)、PDA、信息家電都不能直接顯示HTML）HTML代碼不規(guī)范、臃腫。（瀏覽器需要足夠智能和龐大才能夠正確顯示HTML）數(shù)據(jù)與表現(xiàn)混雜。（頁(yè)面要改變顯示，就必須重新編寫(xiě)HTML）W3C的XHTML是HTML向XML過(guò)渡的一個(gè)橋梁。,87,XML是Web發(fā)展的趨勢(shì),XHTML是當(dāng)前替代HTML4.0標(biāo)記語(yǔ)言的標(biāo)準(zhǔn)。,使用XHTML1.0，只要你小心遵守一些簡(jiǎn)單規(guī)則，就可以設(shè)計(jì)出既適合XML系統(tǒng)，又適合當(dāng)前大部分HTML瀏覽器的頁(yè)面。也就是說(shuō)，你可以立刻設(shè)計(jì)使用XML，而不需要等到人們都使用支持XML的瀏覽器?？梢允箇eb平滑的過(guò)渡到XML。,88,XHTML的優(yōu)勢(shì),XHTML非常嚴(yán)密。,早期的瀏覽器接受私有的HTML標(biāo)簽，所以人們?cè)陧?yè)面設(shè)計(jì)完畢后必須使用各種瀏覽器來(lái)檢測(cè)頁(yè)面，看是否兼容，往往會(huì)有許多莫名其妙的差異，人們不得不修改設(shè)計(jì)以便適應(yīng)不同的瀏覽器。XHTML能與其它基于XML的標(biāo)記語(yǔ)言、應(yīng)用程序及協(xié)議進(jìn)行良好的交互工作。XHTML是Web標(biāo)準(zhǔn)家族的一部分，能很好地應(yīng)用在無(wú)線(xiàn)設(shè)備等其它用戶(hù)代理上。,89,5.4.6腳本語(yǔ)言,2種不同形式的腳本語(yǔ)言JavaScript（1998年）：是一種嵌入到HTML中的客戶(hù)端腳本語(yǔ)言。PHP（PersonalHomePage，2000年）：是嵌入到HTML中的服務(wù)器腳本語(yǔ)言。,腳本語(yǔ)言（ScriptingLanguage）是以腳本的形式定義一項(xiàng)任務(wù)，以此控制操作環(huán)境，擴(kuò)展應(yīng)用程序的性能。,90,1.JavaScript腳本語(yǔ)言,JavaScript是WWW上的一種功能強(qiáng)大的編程語(yǔ)言。,由瀏覽器中的解釋器來(lái)解釋執(zhí)行。它不僅可以直接應(yīng)用于HTML文檔以獲得交互式效果或其他動(dòng)態(tài)效果，而且可以運(yùn)行于服務(wù)器端，從而替代傳統(tǒng)的CGI程序。JavaScript腳本程序的特點(diǎn)：開(kāi)發(fā)客戶(hù)端Web應(yīng)用程序，也就是開(kāi)發(fā)所謂的客戶(hù)端腳本?？蛻?hù)端腳本程序通常都是解釋執(zhí)行的。被嵌入到HTML文件中。,91,1.JavaScript腳本語(yǔ)言（續(xù)）,隨著HTML文件一同下載到瀏覽器端。,瀏覽器讀HTML文件，然后解釋執(zhí)行并顯示其中的元素。讀取HTML文件并分辨其中的元素的過(guò)程稱(chēng)為語(yǔ)法分析或解析（parsing）。如果解析到JavaScript腳本，則瀏覽器執(zhí)行其腳本語(yǔ)句。是最流行的Web腳本語(yǔ)言，其主要原因在于它具有最廣泛的兼容性，可以運(yùn)行于多個(gè)瀏覽器平臺(tái)上。VBScript也是一種通用的Web腳本語(yǔ)言，由微軟公司開(kāi)發(fā)，但由于它只能被IE瀏覽器所支持，所以無(wú)法與JavaScript抗衡。至于VBScript以外的其他Web腳本語(yǔ)言就更是影響微弱了。,92,2.PHP腳本語(yǔ)言,PHP是嵌入到HTML文件中的服務(wù)器端腳本語(yǔ)言。,PHP腳本語(yǔ)言的特點(diǎn)專(zhuān)門(mén)用于Web應(yīng)用。在Web服務(wù)器上解釋PHP代碼。（當(dāng)某個(gè)瀏覽器請(qǐng)求了PHP代碼所在的HTML文件后）PHP代碼通常會(huì)生成HTML代碼作為輸出。Web瀏覽器絕對(duì)不會(huì)看到PHP代碼。,,93,5.5程序設(shè)計(jì)范型,5.5.1命令型程序設(shè)計(jì)語(yǔ)言5.5.2函數(shù)型程序設(shè)計(jì)語(yǔ)言5.5.3邏輯程序設(shè)計(jì)語(yǔ)言5.5.4面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言,94,交互式語(yǔ)言和非交互式語(yǔ)言,按照使用方式，程序設(shè)計(jì)語(yǔ)言有交互式語(yǔ)言和非交互式語(yǔ)言之分：,交互式語(yǔ)言——反映人機(jī)交互作用的語(yǔ)言（BASIC）。非交互式語(yǔ)言——不反映人機(jī)交互作用的語(yǔ)言。如FORTRAN、COBOL、ALGOL69、Pascal、C等都是非交互式語(yǔ)言。,95,程序設(shè)計(jì)范型,程序設(shè)計(jì)范型（Paradigm）是指設(shè)計(jì)程序的規(guī)范、模型和風(fēng)格，它是一類(lèi)程序設(shè)計(jì)語(yǔ)言的基礎(chǔ)。,成功的程序設(shè)計(jì)語(yǔ)言最初都是為某一特殊用途而設(shè)計(jì)的。盡管在很多程序設(shè)計(jì)語(yǔ)言中都含有命令結(jié)構(gòu)和聲明結(jié)構(gòu)，但程序設(shè)計(jì)語(yǔ)言還是可以被劃分為4大類(lèi)型：命令型程序設(shè)計(jì)語(yǔ)言。函數(shù)型程序設(shè)計(jì)語(yǔ)言。邏輯程序設(shè)計(jì)語(yǔ)言。面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言。有些程序設(shè)計(jì)語(yǔ)言（例如，C++、Java等)既是面向?qū)ο笥质敲钚统绦蛟O(shè)計(jì)語(yǔ)言，也可稱(chēng)為多范型程序設(shè)計(jì)語(yǔ)言。,96,5.5.1命令型程序設(shè)計(jì)語(yǔ)言,命令型語(yǔ)言的特點(diǎn)算法必須詳細(xì)指定。賦值語(yǔ)句、變量。包括指令或語(yǔ)句的具體執(zhí)行順序。絕大多數(shù)程序設(shè)計(jì)語(yǔ)言只要不是純函數(shù)型、邏輯和面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言，都具有命令型語(yǔ)言的特性。較有影響力或常用的命令型程序設(shè)計(jì)語(yǔ)言有：FORTRAN、ALGOL、COBOL、PL/I、SIMULA67、BASIC、Pascal、C、Ada、C++、Delphi、Java等。,在執(zhí)行命令型程序設(shè)計(jì)語(yǔ)言的時(shí)候，每次只能執(zhí)行一步計(jì)算，因?yàn)槌绦蛑械拿恳徊蕉家蕾?lài)于它前面的步驟。,97,5.5.2函數(shù)型程序設(shè)計(jì)語(yǔ)言,函數(shù)型程序設(shè)計(jì)語(yǔ)言的特點(diǎn)所有計(jì)算都是通過(guò)將函數(shù)應(yīng)用參數(shù)來(lái)實(shí)現(xiàn)的。不再需要賦值語(yǔ)句和變量。迭代過(guò)程可用遞歸函數(shù)調(diào)用來(lái)指定。語(yǔ)義比命令型語(yǔ)言的語(yǔ)義簡(jiǎn)單得多。目前通常使用的兩個(gè)LISP版本為Scheme（1975）和COMMONLISP（1984）。由RobinMilner于愛(ài)丁堡大學(xué)設(shè)計(jì)的ML（MetaLanguage）元語(yǔ)言，它基本上是一種函數(shù)型語(yǔ)言，但是也支持命令型程序設(shè)計(jì)。而Haskell（1992）是一種純函數(shù)型語(yǔ)言，它的特點(diǎn)是使用了“懶計(jì)算”，即表達(dá)式的值只在需要時(shí)才會(huì)計(jì)算得出，這為該語(yǔ)言增添了一些令人意想不到的功能。,1958年的LISP即為函數(shù)型程序設(shè)計(jì)語(yǔ)言的典型代表。,98,5.5.3邏輯程序設(shè)計(jì)語(yǔ)言,在人工智能應(yīng)用領(lǐng)域早期主要使用LISP語(yǔ)言，后來(lái)到70年代初期有了Prolog。邏輯程序設(shè)計(jì)語(yǔ)言的特點(diǎn)是基于規(guī)則的語(yǔ)言的一個(gè)例子。規(guī)則的指定可以采用任何順序。由語(yǔ)言實(shí)現(xiàn)環(huán)境選擇一種執(zhí)行順序，以生成所需的結(jié)果。這種軟件開(kāi)發(fā)方法與其它三類(lèi)語(yǔ)言所用的方法大不相同，顯然需要一種截然不同的語(yǔ)言。簡(jiǎn)而言之，用邏輯程序設(shè)計(jì)語(yǔ)言編程是非過(guò)程性的，邏輯程序設(shè)計(jì)是用一種形式化的邏輯表示法來(lái)指導(dǎo)計(jì)算機(jī)完成計(jì)算處理。謂詞算子即為當(dāng)前邏輯程序設(shè)計(jì)語(yǔ)言中所用的表示法。謂詞算子提供了與計(jì)算機(jī)通信的基本形式，證明方法（用有限歸約）則提供了推導(dǎo)技術(shù)。,Prolog就是最為通用的一種邏輯程序設(shè)計(jì)語(yǔ)言。,99,5.5.4面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言,面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的特點(diǎn)：將客觀事物都視作為具有屬性和行為的對(duì)象。抽象類(lèi)、繼承與多態(tài)。對(duì)象訪(fǎng)問(wèn)機(jī)制。異常處理機(jī)制。增強(qiáng)了程序的復(fù)用能力、開(kāi)發(fā)效率和可維護(hù)性等。支持面向?qū)ο蟪绦蛟O(shè)計(jì)的語(yǔ)言目前已經(jīng)成為主流，大部分語(yǔ)言都出現(xiàn)過(guò)支持面向?qū)ο蟪绦蛟O(shè)計(jì)的版本。面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言有：Smalltalk、CLOS、VB、VC、Delphi、Java、JavaScript、C#。對(duì)于不同的語(yǔ)言，其對(duì)面向?qū)ο蟪绦蛟O(shè)計(jì)的特定支持也各不相同，有的也支持函數(shù)型程序設(shè)計(jì)，或者仍然采用了某些基本結(jié)構(gòu)，并且看上去仍象是原來(lái)的命令型語(yǔ)言。,C++是目前應(yīng)用最廣泛的語(yǔ)言，并支持多種范型，包括OOP、類(lèi)屬程序設(shè)計(jì)和過(guò)程式程序設(shè)計(jì)。,Smalltalk是絕無(wú)僅有的純面向?qū)ο笳Z(yǔ)言,100,腳本語(yǔ)言和特殊用途語(yǔ)言,JavaScript、PHP腳本語(yǔ)言。用于生成商業(yè)報(bào)表的RPG。用于控制可編程的機(jī)器工具的APT。用于系統(tǒng)仿真的GPSS等。,101,BjarneStroustrup曾經(jīng)說(shuō)過(guò)的一番話(huà)語(yǔ),“對(duì)于軟件領(lǐng)域堪稱(chēng)專(zhuān)業(yè)的人士來(lái)說(shuō)，了解多種語(yǔ)言和多種程序設(shè)計(jì)范型是至關(guān)重要的。目前，C++是多范型程序設(shè)計(jì)的最佳語(yǔ)言，而且也是學(xué)習(xí)多種不同形式程序設(shè)計(jì)的很好的語(yǔ)言。不過(guò)，只了解C++并不好，更不用說(shuō)只了解某一種單范型語(yǔ)言了。這有些像色盲或只會(huì)說(shuō)一種語(yǔ)言的人；你很難知道你遺漏了什么。學(xué)習(xí)和掌握了多種程序設(shè)計(jì)風(fēng)格，并了解在不同語(yǔ)言中該如何加以使用，往往是促成好的程序設(shè)計(jì)的源動(dòng)力”。,,102,5.6習(xí)題（1/2）,1.什么是計(jì)算機(jī)程序？你能列出計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言有哪些？2.結(jié)構(gòu)化程序設(shè)計(jì)中的基本結(jié)構(gòu)有哪些？3.什么叫算法？算法的特征是什么？4.算法的描述方法有哪些？哪些是常用的？區(qū)別在何處？5.分別用不同的描述方法描述結(jié)構(gòu)化程序的3種基本結(jié)構(gòu)。6.編寫(xiě)求最大值的算法。7.什么是結(jié)構(gòu)化程序設(shè)計(jì)？為何要采用結(jié)構(gòu)化程序設(shè)計(jì)？8.結(jié)構(gòu)化程序設(shè)計(jì)方法有哪些特點(diǎn)？9.什么是面向?qū)ο蟪绦蛟O(shè)計(jì)？為何要采用面向?qū)ο蟪绦蛟O(shè)計(jì)？10.面向?qū)ο蟪绦蛟O(shè)計(jì)方法有哪些重要概念和基本特征？,103,5.6習(xí)題（2/2）,11.分別描述常用程序設(shè)計(jì)語(yǔ)言的共同點(diǎn)和不同點(diǎn)。12.什么是程序設(shè)計(jì)范型？程序設(shè)計(jì)范型有哪些？13.有多范型的程序設(shè)計(jì)語(yǔ)言嗎？若有，是何種程序設(shè)計(jì)語(yǔ)言？14.在不同的應(yīng)用領(lǐng)域，你能想到使用什么程序設(shè)計(jì)語(yǔ)言嗎？15.將5.1.1中的步行從甲地到丙地，改為開(kāi)車(chē)從甲地到丙地，并且設(shè)A線(xiàn)含有5個(gè)紅綠燈，B和C線(xiàn)上只有1個(gè)紅綠燈。則當(dāng)交通高峰期就開(kāi)車(chē)走B和C線(xiàn)，非交通高峰期就開(kāi)車(chē)走A線(xiàn)。試用不同的算法描述方法編寫(xiě)該算法。16.進(jìn)一步改寫(xiě)第6題。附加條件是：非交通高峰期時(shí)，并且時(shí)間段為0點(diǎn)至5點(diǎn)時(shí)，就開(kāi)車(chē)走A線(xiàn)。否則，開(kāi)車(chē)走B和C線(xiàn)。試用不同的算法描述方法重新編寫(xiě)該算法。17.現(xiàn)有10個(gè)整數(shù)已經(jīng)按升序排列。請(qǐng)編寫(xiě)算法，要求用折半查找算法查找第一次出現(xiàn)的鍵K值。18．標(biāo)準(zhǔn)建模語(yǔ)言UML有哪五類(lèi)圖？19．簡(jiǎn)單敘述C++、Java、C#語(yǔ)言的共同點(diǎn)和不同點(diǎn)。20．什么是標(biāo)記語(yǔ)言？什么是腳本語(yǔ)言？腳本語(yǔ)言有哪些？,