《大學計算機基礎(chǔ)》第二層次子課程-C 程序設(shè)計基礎(chǔ)(2010V1)

大學計算機基礎(chǔ)北京航空航天大學教學課件1第二層次子課程——C程序設(shè)計基礎(chǔ)5.3程序設(shè)計步驟與程序設(shè)計方法

5.1程序和程序設(shè)計語言

5.2算法

5.4常用程序設(shè)計語言

5.5程序設(shè)計范型2本課程重點程序的概念程序設(shè)計語言的結(jié)構(gòu)算法的概念與描述方法程序設(shè)計步驟程序設(shè)計方法VC集成開發(fā)環(huán)境35.1程序和程序設(shè)計語言5.1.1程序的一般概念

5.1.2程序設(shè)計語言的概述

5.1.3程序設(shè)計語言的結(jié)構(gòu)

45.1.1程序的一般概念

生活中程序的概念何事？策劃導演例1：年終總結(jié)會的程序：會議主持宣布會議開始領(lǐng)導講話個人或團隊代表發(fā)言領(lǐng)導總結(jié)會議主持宣布會議結(jié)束55.1.1程序的一般概念（續(xù)1）

生活中程序的概念甲地乙地丙地A線8公里B線5公里C線4公里步行騎車開車時間紅綠燈鐵道上坡、下坡依據(jù)實際案例并精心計算

解決該計算問題的方法、步驟就包含了程序的概念。例2：某人從甲地到丙地去。65.1.1程序的一般概念（續(xù)2）

計算機程序的概念：為實現(xiàn)某一算法而編寫的指令序列。宏觀地描述該指令序列，可用計算機的機器語言匯編語言高級語言用經(jīng)典的公式可表示為：程序=算法+數(shù)據(jù)結(jié)構(gòu)1976年NiklausWirth（也是Pascal語言發(fā)明者，1984年獲得圖靈獎）的專著：Algorithms＋DataStructures＝Programs75.1.2程序設(shè)計語言的概述

程序設(shè)計——編寫程序的全過程。有學者認為：程序設(shè)計=算法+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計語言程序設(shè)計語言——人和計算機之間對話和交流的一種工具，用于描述計算機所執(zhí)行的操作。計算機程序設(shè)計語言有幾百種，但是最常用的不過10多種，了解一些程序設(shè)計語言的不同特性，有助于為特定任務而選擇適當?shù)某绦蛟O(shè)計語言。8不同類型的計算機語言機器語言（MachineLanguage）匯編語言（AssemblyLanguage）高級語言（HighLevelLanguage）程序設(shè)計語言的特點

91.機器語言（MachineLanguage）指令——指揮計算機完成某個基本操作的命令。機器語言程序注解1011000000001000001011000000101011110100把8存放到累加器A中。將10與累加器A中的8相加，結(jié)果存在A中。程序結(jié)束。指令系統(tǒng)——所有的指令集合。（第一代程序設(shè)計語言）機器語言——用二進制代碼表示指令系統(tǒng)的語言。機器語言程序——由二進制代碼按一定規(guī)則組成的、能被機器理解和運行的指令序列。（也稱可執(zhí)行程序）例如：計算累加器A=8+10的機器語言程序如下：102.匯編語言（AssemblyLanguage）匯編語言——實質(zhì)就是以容易記憶的代碼或英文單詞來代替約定的機器指令。（第二代程序設(shè)計語言）匯編語言源程序注解MOVA,8ADDA,10HLT把8存放到累加器A中。將10與累加器A中的8相加，結(jié)果存在A中。程序結(jié)束。例如：用ADD表示加、SUB表示減、JMP表示跳轉(zhuǎn)、MOV表示數(shù)據(jù)的傳送指令等。匯編源程序——使用匯編語言編寫的程序。例如：上述計算累加器A=8+10的匯編語言程序如下：113.高級語言（HighLevelLanguage）高級語言——類似數(shù)學語言或人的自然語言，同時又不依賴于某種計算機硬件，使得設(shè)計編制的程序能夠在所有機器上通用。（第三代程序設(shè)計語言）程序設(shè)計語言在不同的系統(tǒng)平臺使用比較普遍的有：FORTRAN、ALGOL、COBOL、LISP、PL/I、BASIC、SIMULA67、Pascal、C、Smalltalk80、Ada、C++、VC、VB、Delphi、Java、JavaScript、C#、VisualBASIC.NET?？梢暬Z言——構(gòu)成了命令式語言中的另一個子類。最流行的可視化語言VisualBASIC（1999年），已被VisualBASIC.NET（2002年）取代。提供拖拉式生成代碼段的功能。一度被認作第四代語言，此說法已不再使用了。12程序設(shè)計語言的特點

機器語言的特點：編程難效率高需要指令系統(tǒng)難讀難維護高級語言的特點：編程容易效率低

需要編譯系統(tǒng)易讀易維護匯編語言的特點：編程不容易效率較高需要匯編程序不易讀不易維護135.1.3程序設(shè)計語言的結(jié)構(gòu)

程序結(jié)構(gòu)的多樣性：結(jié)構(gòu)化程序模塊化程序面向?qū)ο蟮某绦蚪Y(jié)構(gòu)一個良好結(jié)構(gòu)的程序具有以下等特點：結(jié)構(gòu)清晰容易閱讀容易理解容易驗證容易維護1996年，計算機科學家Boehm和Jacopini提出并從數(shù)學上證明任何一個算法，都能以三種基本控制結(jié)構(gòu)表示，即順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。14結(jié)構(gòu)化程序設(shè)計中——順序結(jié)構(gòu)

按照程序語句行的自然順序，一條語句一條語句地執(zhí)行程序。語句A入口語句B出口15結(jié)構(gòu)化程序設(shè)計中——選擇結(jié)構(gòu)

根據(jù)條件的判斷確定應該執(zhí)行哪一條分支的語句序列。（又稱為分支結(jié)構(gòu)）入口出口語句序列A語句序列B條件真假單分支、多分支結(jié)構(gòu)？

16入口假真語句序列出口repeat循環(huán)結(jié)構(gòu)

測試條件結(jié)構(gòu)化程序設(shè)計中——循環(huán)結(jié)構(gòu)

主要用于重復執(zhí)行相同的語句序列（被稱為循環(huán)體），當（直到）測試條件為假時才可終止執(zhí)行循環(huán)體。出口入口語句序列假測試條件真while循環(huán)結(jié)構(gòu)17結(jié)構(gòu)化程序設(shè)計的特點

每種結(jié)構(gòu)，只有一個入口和一個出口，這是結(jié)構(gòu)化設(shè)計的一個原則。遵循結(jié)構(gòu)化程序設(shè)計的原則，按照結(jié)構(gòu)化程序設(shè)計方法設(shè)計出的程序具有明顯的優(yōu)點：其一，程序易讀、理解和維護。程序員用結(jié)構(gòu)化編程方法，將復雜程序分解成若干子結(jié)構(gòu)，便于控制、降低程序的復雜性，因此容易編寫程序，同時便于驗證程序。其二，提高編程工作效率，降低軟件開發(fā)成本。由于結(jié)構(gòu)化編程方法能夠把錯誤控制到最低限度，因此能夠減少調(diào)試和查錯的時間。185.2算法5.2.1算法的定義、分類與特征

5.2.2算法的描述方法5.2.3程序設(shè)計典型算法195.2.1算法的定義、分類與特征

Algorithms＋DataStructures＝Programs1976年N·Wirth的程序概念，在計算機軟件開發(fā)行業(yè)中產(chǎn)生了極為深遠的影響，從而推動了軟件開發(fā)技術(shù)和方法步入正軌，使人們開始深入研究數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計與分析的技術(shù)和方法。#include<stdio.h>voidmain()//c1_5.cpp{

inta,b;

printf("Pleaseenteraandb:");

scanf("%d%d",&a,&b);a=a+b;b=a-b;a=a-b;

printf("a=%d,b=%d\n",a,b);}#include<stdio.h>voidmain()//c1_6.cpp{

inta,b,c;

printf("Pleaseenteraandb:");

scanf("%d%d",&a,&b);c=a;a=b;b=c;

printf("a=%d,b=%d\n",a,b);}201.

算法的定義與分類

CPU所遵循的機器周期與下面這個算法一樣簡單。

只要未發(fā)出停機指令就執(zhí)行以下步驟：取一條指令。解碼該指令。執(zhí)行該指令。生活當中的普通活動——剝豌豆。

獲得一籃子未剝皮的豌豆和一只空碗。只要籃中還有豌豆就執(zhí)行下面的步驟：從籃子里拿出一個豌豆。剝開豌豆的豆莢。把剝落得豆放到碗里面。扔掉空豆莢。211.

算法的定義與分類

（續(xù)1）算法的定義——算法是定義一個可終止過程的一組有序的、無歧義的、可執(zhí)行的步驟的集合。華氏溫度與攝氏溫度的轉(zhuǎn)換問題算法1：用代數(shù)公式表示

算法2：用指令表示將攝氏溫度數(shù)值乘以，然后在乘積上加32。外行則認為該指令是模糊的、有歧義的。算法的細致程度221.

算法的定義與分類

（續(xù)2）用一張正方形的紙折疊成一只鳥該過程通過自然的溝通方式常常會引起誤解。有些時候是因為算法描述中使用的術(shù)語可能擁有多種含義。計算機科學解決歧義性問題的方法建立一組嚴格定義的構(gòu)件塊。利用一系列的構(gòu)件塊來構(gòu)建算法的表示。這種構(gòu)件塊稱作原語（primitive）。231.

算法的定義與分類

（續(xù)3）原語——被用于消除算法表示中的歧義性問題。語法——是原語的符號表示（air）。語義——是指該原語的含義（氣體物質(zhì)）。原語的集合以及說明如何組合這些原語來表示比較復雜的想法的規(guī)則集合就構(gòu)成了一種程序設(shè)計語言。程序、算法和進程既是不同的卻又有關(guān)聯(lián)的。程序是一個算法的表示。進程是執(zhí)行算法的活動。241.

算法的概念算法——解決某個具體問題而采取的方法與步驟的完整和準確的描述。是指令的有限序列，其中每一條指令表示一個或多個操作。是問題的程序化解決方案，這些解決方案本身并不是答案，而是獲得答案的精確指令。算法的分類順序算法：是由馮·諾依曼型計算機體系結(jié)構(gòu)所決定的，其主要思想是指令逐條運行，每次執(zhí)行一步操作。并行算法：要求在一些更新式的計算機中可以在同一時間執(zhí)行多條指令。252.算法的特征一個算法必須具備五項基本特征：有窮性、確定性、數(shù)據(jù)輸入、數(shù)據(jù)輸出和可行性。（1）有窮性——算法是有序指令的集合，并在執(zhí)行有窮步驟后能夠終止。（2）確定性——每條指令必須有確切的含義，且無二義性。在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對于相同的輸入數(shù)據(jù)只能得到相同的輸出數(shù)據(jù)。（3）輸入數(shù)據(jù)——可有零個或多個輸入數(shù)據(jù)。這些輸入數(shù)據(jù)取自于某個特定對象的集合。（4）輸出數(shù)據(jù)——必須有一個或多個輸出數(shù)據(jù)。（5）可行性——描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)，也可以證明整個算法實施后可以得到預期的解。262.算法的特征（續(xù)1）算法的發(fā)現(xiàn)程序開發(fā)由兩個活動組成——發(fā)現(xiàn)潛在的算法和以程序的方式表示算法。問題求解的藝術(shù)數(shù)學家（波利亞G·Polya）在1945年提出非嚴格定義的問題求解階段：第1階段理解問題。第2階段設(shè)計一個解決問題的計劃。第3階段完成計劃。第4階段從準確度及其是否有潛力作為一個解決其他問題的工具這兩方面來評估這個計劃。上述階段移植到程序開發(fā)中變成：第1階段理解問題。第2階段尋找一個可能解決問題的算法過程的思路。第3階段闡明算法并且用程序?qū)⑵浔磉_出來。第4階段從準確度及其是否有潛力作為一個工具解決其他問題這兩方面來評估這個程序。階段與步驟的差異27例.甲承擔了確認乙的3個孩子年齡的任務

乙告訴甲3個孩子的年齡乘積是36。

在考慮了這個線索以后，甲要求乙給出另外的線索。

乙告訴甲3個孩子的年齡之和。

甲再次要求乙給出其他線索。

乙告訴甲：他的最大的一個孩子彈鋼琴。

在得到這個線索之后，甲得到了乙的3個孩子的年齡。（1，1，36）（1，6，6）（1，2，18）（2，2，9）（1，3，12）（2，3，6）（1，4，9）（3，3，4）（a）乘積為36的三元組這種解決問題過程中的不規(guī)則性是開發(fā)問題求解的系統(tǒng)方法的基礎(chǔ)。另一個不規(guī)則性在于，那些還沒有得到明顯成功的問題解決者所得到的神奇靈感可能在完成其他任務的時候突然成為了原來問題的一個解決方法。

1+1+36=381+6+6=13

1+2+18=212+2+9=13

1+3+12=162+3+6=11

1+4+9=143+3+4=10（b）a中的每個三元組的和2+2+9=1328例.求甲乙丙丁賽跑的名次排序

在甲、乙、丙和丁進行賽跑之前，他們分別對結(jié)果進行預測：甲預測乙將會獲勝。乙預測丁將是最后一名。丙預測甲是第三名丁預測甲的預測將是正確的。這幾個預測只有一個是正確的，并且是最后的獲勝者做出的預測。解1：丙、乙、甲、丁解2：丙、丁、甲、乙進入問題后，會發(fā)現(xiàn)：獲得完整的解決方法的過程僅僅是將我們的知識在此處擴展應用。被排除29算法的入門

知道怎樣進入問題并不等于知道如何去做這件事。為了得到立足點，也就是認識到如何把對于問題的初始介入擴展為問題的解決方法，就為要求問題解決者創(chuàng)造一個可能的入口。

對于如何入門？波利亞和其他人提出了很多通用的方法。反方向解決問題（白紙與紙鳥）尋找一個相關(guān)的、解決起來較簡單的并且在此以前已經(jīng)得到解決的問題，然后嘗試把這個解決方法用到當前問題中。逐步求精（stepwiserefinement）數(shù)據(jù)處理中一種重要設(shè)計方法自頂向下方法（top-downmethodology）一般到特殊自底向上方法（bottom-upmethodology）特殊到一般

30算法的入門

（續(xù)1）四個人名（David、Alice、Carol和Bob）按照升序排序指令。交換名字David和Alice。將名字Carol移到Alice和David之間。將名字Bob移到Alice和Carol之間。

通常，程序開發(fā)并不是去解決一個問題的一個特定實例，而是要去尋找一種適用于求解一個問題的所有實例的一般算法?？梢酝ㄟ^考慮一個特殊的情況來進入問題，然后得到一個能夠用于開發(fā)通用算法的一般原則。（三個人名排序指令）

特定實例31例5.1一個非算法的計數(shù)過程①令n為0；②置n為n+1；③返回②。結(jié)論：不能稱為算法。原因：違背了算法特征中（1）、（4）、（5）。有窮性（有效性）：考察下面這條指令:給出一個所有整數(shù)的列表?！痢?2例5.2計數(shù)器算法用自然語言編寫一個不超過1萬次的計數(shù)器算法：①令n為0；②置n為n+1③若n小于10000，則返回②；否則，輸出n之值，且算法到此結(jié)束。結(jié)論：是算法。原因：符合算法特征。在算法設(shè)計過程中，其實還有有關(guān)正確性、可讀性、健壯性、效率與低存儲量需求，以及算法效率的度量等問題。335.2.2算法的描述方法

流程圖（FlowChart）PAD圖（ProblemAnalysisDiafram，問題分析圖）N-S圖自然語言偽代碼UML圖（UnifiedModelingLanguage，統(tǒng)一建模語言）341.流程圖流程圖（框圖）用不同形狀的幾何圖形表示不同性質(zhì)的操作，用流程線指明算法的執(zhí)行方向。ANSI(美國國家標準化協(xié)會)、ISO（國際標準化組織）和我國國家標準中均有類似的規(guī)定。常見的流程圖符號如下：向下或向右的流程線可以不畫出箭頭。當流程線有交叉時，則畫一半圓通過交叉點。35用流程圖描述的計數(shù)器算法362.PAD圖由日立公司推出的PAD圖是一種二維圖。即從上向下順序執(zhí)行，從左到右表示層次關(guān)系。表示三種基本結(jié)構(gòu)的PAD圖如下：373.N-S圖1973年美國兩位學者提出無流程線的N-S圖（盒圖）。結(jié)構(gòu)化程序設(shè)計由三種基本結(jié)構(gòu)而組成，則算法也應采用結(jié)構(gòu)化描述方法，N-S圖的基本單元是矩形框，框內(nèi)可以有三種基本結(jié)構(gòu)，形如堆積木，也只有一個入口和一個出口。三種基本結(jié)構(gòu)的N-S圖如下：38用N-S圖描述的計數(shù)器算法394.自然語言自然語言是人們?nèi)粘Ｉ?、工作和學習中使用的通用語言，使用自然語言的文字描述算法通俗易懂，但也有它的缺陷：（1）容易產(chǎn)生歧義性，因為自然語言經(jīng)常要根據(jù)上下文才能判別其含義，不太嚴格。（2）自然語言很難清楚地表達算法的邏輯流程，對于算法中的條件判斷、循環(huán)，尤其是在這些處理中還有多層嵌套，就很難用清晰而直觀的語言來表達算法的流程。因此僅適于描述簡單問題。405.偽代碼偽代碼是介于自然語言和計算機語言之間的文字和符號，它不能被計算機所理解，但使用偽代碼描述的算法很容易轉(zhuǎn)變成某種編程語言。//用偽代碼描述的計數(shù)器算法如下：

n←0don←n+1whilen<10000

輸出n，且算法到此結(jié)束。常用的偽代碼是用自然語言與類Pascal或類C語言相結(jié)合的方法來描述算法。41流程圖形的繪制工具當使用圖形描述算法時，流程圖形的繪制工具有很多。一般比較簡單的圖形可用Word或PowerPoint中的繪圖工具欄來制作完成，若安裝了功能強大的MicrosoftOfficeVisio2003，則可以更快地繪制具有專業(yè)水平的高質(zhì)量圖形。在Visio2003中：含有豐富的基本流程圖形狀。能夠快速、簡便地建立流程圖、組織圖、日歷時間表和其它多種圖表。支持縮放矢量圖形（SVG），這是一種新的圖形格式標準。集合Internet的運用，可使用不同的語言創(chuàng)建繪圖、創(chuàng)建包含多種語言的繪圖以及跨多種語言共享繪圖和展開協(xié)作。通過支持新的漢字編碼標準GB18030，可從這個新的字符編碼集中創(chuàng)建包含漢字的繪圖。425.2.3程序設(shè)計典型算法算法——數(shù)值算法或非數(shù)值算法：數(shù)值算法——主要用于數(shù)值求解或分析，如：求和、求平方根、解方程、用組合梯形法則求定積分等。非數(shù)值算法——主要用于各領(lǐng)域管理類的信息處理，如：各種排序、查找等。本節(jié)介紹一些簡單的常用算法，并假設(shè)各數(shù)據(jù)均能滿足值域要求。431.求3個整數(shù)的最大值算法為了編寫求3個整數(shù)最大值的通用實現(xiàn)過程，采用主函數(shù)調(diào)用子函數(shù)的形式描述算法。（1）主函數(shù)算法描述如下：①輸入三個整數(shù)a,b,c;②max=max3(a,b,c);③輸出max。（2）max3子函數(shù)算法描述如下：

①從a與b中取大數(shù)送m中;②從m與c中取大數(shù)送m中;③返回m給主函數(shù)。44求3個整數(shù)的最大值的C程序/*使C預編譯包含I/O頭文件，則可用scanf、printf函數(shù)*/#include<stdio.h>voidmain(void){

inta,b,c,max;/*定義4個整型變量*/

intmax3(inta,intb,intc);/*max3函數(shù)原形聲明*/

printf(“Input3integernumbers:”);/*

輸出雙引號中的提示信息*/

scanf(“%d%d%d”,&a,&b,&c);/*

輸入3個整數(shù)*/max=max3(a,b,c);/*調(diào)用max3函數(shù)求最大值*/

printf(“Themaxis:%d\n”,max);/*輸出max中的最大值*/}

/*Endofmainfunction*//*

求3個整數(shù)的最大值的子函數(shù)max3*/intmax3(inta,int

b,intc)/*max3函數(shù)將返回整型值*/{

intm;/*定義m整型變量

*/

if(a>b)m=a;/*從a與b中取大數(shù)送m中*/elsem=b;if(m>c);/*從m與c中取大數(shù)送m中，“；”即m=m*/elsem=c;

return(m);/*返回m給主函數(shù)*/}

/*Endofmax3function*///Lab2.c452.歐幾里得算法求解兩個不全為0的非負整數(shù)m和n的最大公約數(shù)，可以采用以下歐幾里得算法。（1）歐幾里得算法主函數(shù)描述如下：①輸入兩個不全為0的非負整數(shù)m,n;②Ecd=Euclid(m,n);③輸出Ecd，且算法到此結(jié)束。（2）Euclid(m,n)子函數(shù)算法描述如下：

whilen≠0dor←mmodnm←nn←rreturnm463.

兩個變量值的交換算法計算機實現(xiàn)的兩個變量值的交換算法如下：①令a=5,b=10②c←a,a←b,b←c③輸出a和b的值。/*兩個變量值交換算法的C源程序*/voidmain(void){inta=5,b=10,c;/*定義a、b、c3個整型變量*/

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*/三角對換法

474.排序算法給定一個有n個元素可排序的序列，例如數(shù)字數(shù)據(jù)或字符串數(shù)據(jù)等，要求按照升序或降序方式重新排列。排序算法：如冒泡排序法、選擇排序法、插入排序法、合并排序法、快速排序法等等排序算法。48蠻力法中的選擇排序法按照降序方式排序的選擇排序算法：SelectionSort（Array[0..n-1]）/*本算法用選擇排序法對給定數(shù)組按照降序方式排序*//*Array[0..n-1]是有n個元素的可排序數(shù)組*//*本算法的結(jié)果在Array數(shù)組中*/fori←0ton-2domax←iforj←i+1ton-1doifArray[j]>Array[max]max←jswapArray[i]andArray[max]49選擇排序法的

C

程序/*SelectionSort(Array[0..n-1])選擇排序算法的C源程序*/voidSelectionSort(intn,intArray[]){inti,j,max,t;/*定義4個整型變量*/for(i=0;i<=n-2;i++)/*做n-1遍掃描尋找最大元素*/{max=i;/*記錄當前掃描最大元素的位置*/for(j=i+1;j<=n-1;j++)/*在n-i

個元素中找最大元素*/if(Array[j]>Array[max])max=j;/*記錄大數(shù)元素的下標位置*/

/*利用t變量做三角對換*/t=Array[i],Array[i]=Array[max],Array[max]=t;}}/*EndofSelectionSortfunction*/50選擇排序法降序方式排序操作過程例如：對序列89，29，68，90，17，34，45操作。|8929689017344590|2968891734459089|6829173445908968|2917344590896845|1734299089684534|1729908968453429|17每行表示該算法的一次迭代，即從尾部到豎線的一遍掃描；找到的最大元素用黑體字表示，豎線左邊元素已經(jīng)位于它們的最終位置，所以在當前和以后的循環(huán)中，都不必再操作了。排序操作過程如下：51插入排序的基本思想每一步將一個待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當位置上，直到待排序元素插入完為止。初始狀態(tài)：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]排序52在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序法，這里只介紹最簡單的直接插入排序法。直接插入排序排序?qū)⑿彰斜碛脗未a表達的插入排序算法:procedureSort(list)N←2;while(N的值不超過列表的長度）do(把列表的第N項作為主元項；把主元項移到一個臨時位置使該列表留出一個空位置；while(如果這個空位置上面存在一個名字并且那個名字比主元大)do(把這個名字向下移到空位置上使該名字上面留出一個空位置)把主元項插到列表的空位置上；N←N+1)53直接插入排序函數(shù)模板//用直接插入排序法對數(shù)組A中的元素進行升序排列template<classT>//9-11.h源10-1.hvoidInsertionSort(TA[],intn){inti,j;Ttemp;

for(i=1;i<n;i++)

//將下標為1～n-1的元素逐個插入到已排序序列中適當?shù)奈恢?/p>

{

//從A[i-1]開始向A[0]方向掃描各元素,尋找適當位置插入A[i]

j=i;temp=A[i];while(j>0&&temp<A[j-1]){

//逐個比較，直到temp>=A[j-1]時，j便是應插入的位置。

//若達到j==0，則0是應插入的位置。

A[j]=A[j-1];

//將元素逐個后移，以便找到插入位置時可立即插入。

j--;}A[j]=temp;

//插入位置已找到，立即插入。

}}直接插入排序54應用直接插入排序函數(shù)模板排序//9-11.cpp源10-1.cpp#include"10-1.h"voidmain(){ inti,data[]={1,3,5,7,9,2,4,6,8,10};constintMax=10;

cout<<"排序前的原始數(shù)據(jù)："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;

cout<<“開始以直接插入排序。。。"<<endl;

InsertionSort(data,Max);

cout<<“直接插入排序結(jié)果："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;}直接插入排序

//9_11.cpp55選擇排序的基本思想每次從待排序序列中選擇一個關(guān)鍵字最小的元素，（當需要按關(guān)鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。[541020123]初始狀態(tài)：3[41020125]34[1020125]第i次選擇后，將選出的那個記錄與第i個記錄做交換。345[201210]......排序56直接選擇排序在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。排序57直接選擇排序函數(shù)模板template<classT>voidSwap(T&x,T&y){Ttemp;temp=x;x=y;y=temp;}直接選擇排序template<classT>//9-12.hvoidSelectionSort(TA[],intn){int

smallIndex;//每一次選出的最小元素之下標

inti,j;for(i=0;i<n-1;i++){smallIndex=i;

//在元素A[i+1]…A[n-1]中逐個比較顯出最小值

for(j=i+1;j<n;j++)if(A[j]<A[smallIndex])

smallIndex=j;Swap(A[i],A[smallIndex]);}}58應用直接選擇排序函數(shù)模板排序//9-12.cpp#include"10-2.h"voidmain(){ inti,data[]={1,3,5,7,9,2,4,6,8,10};constintMax=10;

cout<<"排序前的原始數(shù)據(jù)："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;

cout<<"開始以直接選擇排序。。。"<<endl;

SelectionSort(data,Max);

cout<<"直接選擇排序結(jié)果："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;}直接選擇排序

//9_12.cpp59交換排序的基本思想兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。最簡單的交換排序方法是起泡排序。排序60對具有n個元素的序列按升序進行起泡排序的步驟：①首先將第1個元素與第2個元素進行比較，若為逆序，則將兩元素交換。然后比較第2、第3個元素，依次類推，直到第n-1和第n個元素進行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟起泡排序，最大的元素便被交換到第n個位置。②對前n-1個元素進行第二趟起泡排序，將其中最大元素交換到第n-1個位置。③如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時，排序完畢。對n個元素的序列，起泡排序最多需要進行n-1趟。起泡排序61起泡排序過程示意圖對整數(shù)序列85243按升序排序起泡排序8524352438243582345823458初始狀態(tài)第一趟結(jié)果第二趟結(jié)果第三趟結(jié)果第四趟結(jié)果小的逐漸上升每趟沉下一個最大的62起泡排序函數(shù)模板//用起泡法對數(shù)組A的n個元素進行排序template<classT>//9-13.hvoidBubbleSort(TA[],intn){inti,j;

int

lastExchangeIndex;

//用于記錄每趟被交換的最后一對元素中較小的下標

i=n-1;

//i是下一趟需參與排序交換的元素之最大下標

while(i>0)

//持續(xù)排序過程，直到最后一趟排序沒有交換發(fā)生，或已達n-1趟

{lastExchangeIndex=0;

//每一趟開始時，設(shè)置交換標志為0（未交換）

for(j=0;j<i;j++)

//每一趟對元素A[0]…A[i]進行比較和交換

if(A[j+1]<A[j])

//如果元素A[j+1]<A[j]，交換之

{Swap(A[j],A[j+1]);

lastExchangeIndex=j;

//記錄被交換的一對元素中較小的下標

}

i=lastExchangeIndex;//將i設(shè)置為本趟被交換的最后一對元素中較小的下標}}起泡排序63應用起泡排序函數(shù)模板排序//9-13.cpp#include"10-3.h"voidmain(){ inti,data[]={1,3,5,7,9,2,4,6,8,10};constintMax=10;

cout<<"排序前的原始數(shù)據(jù)："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;

cout<<"開始以起泡排序。。。"<<endl;

BubbleSort(data,Max);

cout<<"起泡排序結(jié)果："<<endl; for(i=0;i<Max;i++)

cout<<data[i]<<"";

cout<<endl;}起泡排序

//9_13.cpp64順序查找基本思想從數(shù)組的首元素開始，逐個元素與待查找的關(guān)鍵字進行比較，直到找到相等的。若整個數(shù)組中沒有與待查找關(guān)鍵字相等的元素，就是查找不成功。查找65順序查找函數(shù)模板#ifndefSEARCH_METHODS//9-14.h#defineSEARCH_METHODS//用順序查找法在數(shù)組list中查找值為key的元素//若找到，返回該元素下標，否則返回-1template<classT>int

SeqSearch(Tlist[],intn,Tkey){

for(inti=0;i<n;i++)if(list[i]==key)returni;return-1;}#endif

//SEARCH_METHODS查找66用偽代碼表達的順序搜索算法procedureSearch(List,TargetValue)if(List空)then(宣布查找失敗)else(選擇列表中的第一個表項作為TestEntry;while(TargetValue>TestEntry

并且還有表項沒有檢查)

（選擇列表中下一個表項作為TestEntry）；if(TargetValue=TestEntry)then(宣布查找成功)else

(宣布查找失敗))endif順序搜索是以一種循環(huán)的方式重復執(zhí)行一個過程。List：空列表或升序列表67折半查找的基本思想如果是在一個元素排列有序的數(shù)組中進行查找，可采用折半查找方法。對已按關(guān)鍵字排序的序列，經(jīng)過一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。查找68折半查找過程示意圖用折半查找法，在下列序列中查找值為21的元素：513192137566475808892H=11M=(L+H)/2=6513192137L=1H=M-1=5M=(L+H)/2=3M2137HL=M+1=4L21==list[M]MLow——LMid——MHigh——H21>list[M]M=(L+H)/2=4L=121<list[M]查找69折半查找函數(shù)模板//用折半查找方法，在元素呈升序排列的數(shù)組list中查找值為key的元素template<classT>//9-15.hint

BinSearch(Tlist[],intn,Tkey){intmid,low=0,high=n-1;Tmidvalue;while(low<=high)//low<=high表示整個數(shù)組尚未查找完

{mid=(low+high)/2;//求中間元素的下標

midvalue=list[mid];//取出中間元素的值

if(key==midvalue)returnmid;//若找到,返回下標

elseif(key<midvalue)high=mid-1;//若key<midvalue將查找范圍縮小到數(shù)組的前一半

elselow=mid+1;//否則將查找范圍縮小到數(shù)組的后一半

}return-1;//沒有找到返回-1}折半查找70用偽代碼表達的二分搜索算法procedureSearch(List,TargetValue)if(List空)then(報告查找失敗)else[選擇列表的中間項作為TestEntry;

執(zhí)行以下與條件相符case指令塊case1:TargetValue=TestEntry（報告查找成功）case2:TargetValue<TestEntry

(應用Search過程查看TargetValue是否在List中位于TestEntry

項之前的部分，并報告查找結(jié)果)case3:TargetValue>TestEntry

(應用Search過程查看TargetValue是否在List中位于TestEntry

項之后的部分，并報告查找結(jié)果)]endif二分搜索是把每一階段重復當作前一階段的子任務，該技術(shù)被稱作遞歸（recursion）71算法的有效性和準確性盡管當今的計算機每秒可以處理數(shù)百萬條指令，有效性仍舊是算法設(shè)計中所關(guān)注的一個主要問題。通常，在效率高低的兩個算法之間的選擇能夠產(chǎn)生對于問題的實用或者不實用的兩種解。

例如：一個大學的教務主任需要面對檢索和更新學生記錄的任務。假設(shè)：給定一個學生的學號（目標值），要在“當前學生”文件（包括3萬多條學生記錄）中找到。72算法的有效性和準確性（續(xù)）使用順序搜索算法：不能推斷究竟要查找多少條記錄才能得到結(jié)果?？梢约俣ㄔ诙啻尾檎抑?，認為平均查找深度是表的一半長度。所以估計平均每次大概需要尋找15000條記錄。

10ms/一條記錄則：150s1ms/一條記錄則：15s結(jié)論：無法容忍。使用二分搜索算法：通過比較目標值和表的中間項來進行查找。如果不是期望的記錄，則至少將查找限制在原始表的一半。因此,30000、15000、7500、3750……最多15次之后，目標值應該被找到。

10ms/一條記錄則：0.15s結(jié)論：瞬間完成。

73算法的有效性和準確性（續(xù)）總結(jié)：使用搜索方法的選擇將對該應用產(chǎn)生了巨大影響。該例子表現(xiàn)了計算機科學領(lǐng)域中對大家熟知的算法分析的重要性，這種分析包含了對于資源的研究，比如算法需要消耗的時間或者存儲空間資源。這種研究的一個主要應用在于給出了二選一算法之間不同優(yōu)點的評估。算法分析通常包括最優(yōu)情況分析、最差情況分析和平均情況分析。不能關(guān)注于表的特定長度，而是要嘗試列出某種可以表示任何長度的表中進行查找的算法的性能公式。具體而言，當需要在長度為n的表中應用時：順序搜索算法的平均查找長度是——n/2。二分搜索算法在最差情況下的查找長度不超過——lgn

（lgn表示以2為底n的對數(shù)）74插入排序算法的最差情況分析圖執(zhí)行算法所需要的時間列表的長度增加列表長度時時間的長度列表長度均勻增長長度為n的列表中進行最多需要次比較。75二分搜索法的最差情況分析圖執(zhí)行算法所需要的時間列表的長度增加列表長度時時間的長度列表長度均勻增長在長度為n的列表中進行查找的時候最多需要查詢lgn項。76查找算法查找是指從給定的集合（或者是多重集，它允許幾個元素具有相同的值）中查找一個給定的值（稱為查找鍵K）。常用的查找算法有順序查找和折半查找，還有那些將原來的集合表示為另一種形式以方便查找的算法等等。順序查找——直接從頭到尾搜索集合的查找鍵。折半查找——必須首先將集合按照降序或升序排序，然后利用折半技術(shù)搜索集合的查找鍵，所以，當集合是有序的時候，使用折半查找效率高、速度快。77判定哪一種算法是最佳方案針對排序和查找方面的算法更多，例如，采用分治法、減治法、變治法等等方法中的各種排序和查找算法。運用經(jīng)典的算法設(shè)計技術(shù)——時空權(quán)衡、動態(tài)規(guī)劃、貪婪技術(shù)等；算法能力的極限中的決策樹技術(shù)、在多項式的時間內(nèi)求解、數(shù)值分析，超越算法能力的極限中的回溯發(fā)、分支界限法和近似算法設(shè)計技術(shù)。技術(shù)和思維方式都是不可或缺的鞭策學習和掌握程序設(shè)計中的算法設(shè)計與分析技術(shù)托馬斯·愛迪生（1847-1931）的名言：“不斷關(guān)注那些已被他人成功應用的新思路。你的原創(chuàng)思想只應該應用在那些你正在研究的問題上”。785.3程序設(shè)計步驟與程序設(shè)計方法

5.3.1程序設(shè)計步驟

5.3.2程序設(shè)計方法795.3.1程序設(shè)計步驟

一般程序設(shè)計應該包含以下4個步驟：（1）針對具體問題進行分析——了解問題性質(zhì)，明確問題解決所達目標，提供的輸入是什么？最終實現(xiàn)的輸出是什么？執(zhí)行中要做什么？怎么做？并建立相應的數(shù)學模型。（2）確定數(shù)據(jù)結(jié)構(gòu)并設(shè)計相應的算法——對具體問題進行概念抽象，構(gòu)造出解決問題的輪廓，設(shè)計程序的數(shù)據(jù)結(jié)構(gòu)和算法。（3）編寫實現(xiàn)算法的程序——根據(jù)算法確定解決問題的詳細步驟，通常是通過繪制程序流程圖，來描述問題處理的過程；然后按照流程圖的描述選用某種程序設(shè)計語言編寫程序。（4）測試與調(diào)試程序——在程序設(shè)計過程中，經(jīng)常不是那么一帆風順的，尤其是初學者會遇到各種這樣或那樣的問題，還有一些問題可能是不可預測的，往往不得不返到上一步驟中更改或調(diào)整相應的內(nèi)容，并將相應文檔也一并修改，通過舉一反三的方法來解決給定問題。80測試程序與調(diào)試程序測試程序為了發(fā)現(xiàn)程序中的設(shè)計錯誤而運行程序。

——所使用的測試用例尤其重要，因為不僅需要合法值域用例，而且非法值域用例也是必須的。——程序測試的成功與否直接可以體現(xiàn)程序健壯性。

——當軟件項目是由團隊開發(fā)時，測試程序可分為：單元測試、組裝測試和確認測試。調(diào)試程序

錯誤定位和糾錯的過程，這一過程的快慢與程序設(shè)計人員的編程經(jīng)歷和經(jīng)驗是密切相關(guān)的。81高級語言編寫和運行過程yesyes源文件目標文件可執(zhí)行文件其它目標文件庫函數(shù)開始編輯源程序檢查確認有錯？編譯程序有錯？有錯？運行程序有錯？yesnonoyes連接程序no結(jié)束no數(shù)據(jù)825.3.2程序設(shè)計方法早期的程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法面向?qū)ο蟪绦蛟O(shè)計方法831.早期的程序設(shè)計方法早期的程序設(shè)計方法追求程序的高效率，編程過份依賴技巧，忽視程序清晰，而不注重所編寫程序的結(jié)構(gòu)，很少考慮程序的規(guī)范化問題，也就是沒有固定程序設(shè)計方法的時期。程序的可讀性、可重用性都很差。其中典型問題是：頻繁使用goto語句，特意算計如何節(jié)省內(nèi)存空間。雖然這些方法存在很多問題，但當時受限于計算機運行速度慢、內(nèi)存容量小、硬件價格昂貴，程序的規(guī)模也比較小，對于單人完成較為簡單的任務，事實上這些方法還是經(jīng)常被采用的。842.結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法出現(xiàn)在70年代中期。隨著計算機硬件成本急劇下降，軟件需要處理的復雜問題也就越來越多。為了擺脫60~70年代初的軟件危機，因為當時編程無章可循，程序常常帶有強烈的個人色彩，程序的可讀性差，程序的調(diào)試和維護更困難，促使人們認真反省和研究程序設(shè)計中一系列根本性問題：程序的基本結(jié)構(gòu)是什么？程序設(shè)計應當采用什么方法？算法設(shè)計先于程序編碼？清晰第一，效率第二？程序設(shè)計技術(shù)與方法如何規(guī)范化和工程化？解決手工作坊式軟件開發(fā)的弊端85結(jié)構(gòu)化程序設(shè)計方法的特點使得程序?qū)哟畏置?、邏輯清晰、功能獨立，簡化了開發(fā)程序的復雜性，增加了程序的可靠性，能夠充分發(fā)揚團隊精神快速而高效地完成項目開發(fā)，增強系統(tǒng)的可維護性，使程序設(shè)計更加規(guī)范化。結(jié)構(gòu)化程序設(shè)計方法的特點：自頂向下、逐步求精劃分功能模塊結(jié)構(gòu)化編程863.面向?qū)ο蟪绦蛟O(shè)計方法面向?qū)ο蟪绦蛟O(shè)計方法出現(xiàn)在80年代中后期。隨著計算機硬件技術(shù)的高速發(fā)展，計算機的性能也越來越強，用途也更加廣泛。軟件產(chǎn)業(yè)所面臨的問題需求不斷擴大，程序也就越來越龐大而復雜。在面向過程的程序設(shè)計中——軟件設(shè)計的主要工作就是用不同的功能模塊分別描述它們的求解過程。在結(jié)構(gòu)化程序設(shè)計中——數(shù)據(jù)和處理數(shù)據(jù)的過程分離為相互獨立的實體，它只是封裝了各個功能模塊，而每個功能模塊可以隨意修改未加封裝的數(shù)據(jù)。新時期的新問題，以及軟件產(chǎn)業(yè)的更高要求，迫使人們再次尋求更加科學、更加先進的程序設(shè)計方法。87面向?qū)ο蟪绦蛟O(shè)計（OOP）Object-OrientedProgramming是建立在結(jié)構(gòu)化程序設(shè)計基礎(chǔ)上的，但它不再是從功能入手，而是從對象入手。采用的是一種結(jié)構(gòu)模擬的方法。用“類”描述具有相同屬性特征的一組對象，用“封裝”將對象的屬性和行為分別用適當?shù)臄?shù)據(jù)結(jié)構(gòu)和方法來描述，并將它們綁定在一起形成一個可供訪問的基本邏輯單元，利用“繼承”實現(xiàn)類與類之間的數(shù)據(jù)和方法的共享。88面向?qū)ο蟪绦蛟O(shè)計的重要概念面向?qū)ο蟪绦蛟O(shè)計的重要概念：對象（Object）類（Class）消息（Message）方法（Method）89對象（Object）面向?qū)ο蟪绦蛟O(shè)計中的對象——現(xiàn)實世界中的客體在應用程序中的具體體現(xiàn)，其中封裝了客體的屬性信息和行為方式，并用數(shù)據(jù)表示屬性，用方法表示行為方式。對象中的數(shù)據(jù)記錄了客體的屬性狀態(tài)，方法決定了客體所能夠?qū)嵤┑牟僮餍袨楹团c其它對象進行通信的接口方式。對象并非孤立存在，消息傳遞是對象之間相互聯(lián)系的唯一途徑，發(fā)送者發(fā)送消息，接收者通過調(diào)用相應的方法響應消息，這個過程被不斷地重復，從而驅(qū)動整個程序的運轉(zhuǎn)。90類（Class）人類在認知客觀世界時，將眾多的事物歸納、劃分成一些類，這是經(jīng)常采用的思維方法。分類所依據(jù)的原則是抽象。類是具有相同屬性和行為方式的一組對象的集合，或者說，類是指對一組具有相同特征（包括屬性、操作、方法、關(guān)系、行為）的對象的抽象描述，任何對象都是某個類的實例。對象是系統(tǒng)運行時將類作為生成對象實例的模板，通過分配私有存儲空間，然后對相應的屬性賦初始值而創(chuàng)建的，這個過程在面向?qū)ο蟪绦蛟O(shè)計中稱為“實例化”。類與對象的關(guān)系猶如模具與鑄件之間的關(guān)系。91消息（Message）消息——一個對象要求另一個對象實施某項操作的請求。

在一條消息中，需要包含消息的接收者和要求接收者執(zhí)行某項操作的請求，但具體的操作過程由接收者自行決定，這樣可以很好地保證系統(tǒng)的模塊性。消息傳遞是對象之間相互聯(lián)系的唯一途徑。發(fā)送者發(fā)送消息，接收者通過調(diào)用相應的方法響應消息，這個過程被不斷地重復，從而驅(qū)動整個程序的運轉(zhuǎn)。92方法（Method）面向?qū)ο蠹夹g(shù)中的方法——針對對象的屬性的各種操作。將一些通用的過程或函數(shù)編寫好并封裝起來，作為方法直接提供給用戶調(diào)用。93面向?qū)ο蟪绦蛟O(shè)計幾個重要的基本特征面向?qū)ο蟪绦蛟O(shè)計幾個重要的基本特征：抽象（Abstract）封裝（Encapsulation）繼承（Inheritance）多態(tài)（Polymorphism）94抽象（Abstract）抽象——忽略事物的非本質(zhì)特征，只注意那些與當前目標有關(guān)的本質(zhì)特征，從而找出事物的共性，把具有共同性質(zhì)的事物劃分為一類，得出一個抽象的概念。在理解復雜的現(xiàn)實世界和解決復雜的特定問題時，如何從繁雜的信息集中抽取出有用的、能夠反映事物本質(zhì)的東西，降低其復雜程度是解決問題的關(guān)鍵，而抽象正是降低復雜度的最佳途徑。抽象可分為過程抽象和數(shù)據(jù)抽象過程抽象——即功能抽象，舍棄個別功能，抽取共同擁有的功能。數(shù)據(jù)抽象——一種更高級別的抽象，它將現(xiàn)實世界中存在的客體作為抽象單元，其抽象內(nèi)容既包括客體的屬性特征，也包括行為特征（起到信息隱藏的作用）。它是面向?qū)ο蟪绦蛟O(shè)計所采用的核心方法。95封裝（Encapsulation）面向?qū)ο蟪绦蛟O(shè)計中的封裝——將對象的屬性和行為分別使用適當?shù)臄?shù)據(jù)結(jié)構(gòu)和方法來描述，并將它們綁定在一起形成一個可供訪問的基本邏輯單元。用戶對數(shù)據(jù)結(jié)構(gòu)的訪問只能通過使用類提供的外部接口。這樣，將描述這些屬性的數(shù)據(jù)結(jié)構(gòu)和訪問這些數(shù)據(jù)結(jié)構(gòu)的方法封裝在一個對象中，從而使數(shù)據(jù)結(jié)構(gòu)得到隱藏，不允許外界直接訪問。其它對象只能通過封裝提供的外部接口（這些方法）對該對象實施各項操作，保證了數(shù)據(jù)結(jié)構(gòu)的安全，提高了系統(tǒng)的可維護性和可移植性。96繼承（Inheritance）繼承是面向?qū)ο蠹夹g(shù)提高軟件開發(fā)效率的重要措施，如果類與類之間有is-a（是一種）的關(guān)系，則可用繼承機制來表示。其定義是：特殊類的對象擁有其一般類的全部屬性和服務，稱作特殊類對一般類的繼承。它體現(xiàn)了類與類之間的不同抽象級別。根據(jù)繼承與被繼承的關(guān)系，可分為派生類（或稱子類）和基類（或稱父類）。繼承機制其實質(zhì)是反映了從一般到特殊的關(guān)系，父類表現(xiàn)出的是共性和一般性，子類表現(xiàn)出的是個性和特殊性，子類從父類那里獲得所有的屬性和方法，并且可以對這些獲得的屬性和方法加以改造，使之具有自己的特點。繼承對于軟件復用和擴充有著及其重要的意義，利用代碼重用技術(shù)，能夠降低開發(fā)投入，加快軟件開發(fā)速度、提高軟件質(zhì)量，減少維護成本。繼承可分為公有繼承（public）、私有繼承（private）和保護繼承（protected）三種訪問控制方式。97多態(tài)（Polymorphism）多態(tài)——不同層次的類中，以及在一個類的內(nèi)部，同名成員函數(shù)之間的關(guān)系問題，是解決功能和行為的再抽象。多態(tài)是指不同的對象收到相同的消息時產(chǎn)生多種不同的行為方式。它是一種用統(tǒng)一的方式來處理一組各具個性卻同屬一族的不同個體的機制，這就使得同樣的消息被不同的對象接收時，將被解釋為不同的語義。例如：定義了多個“add”相加的同名函數(shù)，但它們的參數(shù)類型各不相同，如果用整型之間、實型之間、雙精度浮點型之間分別表示相加運算，則當同樣的消息（相加）被不同類型的對象（變量）接收后，不同類型的變量將采用不同的方式進行加法運算。985.4常用程序設(shè)計語言

5.4.1科學計算語言

5.4.2結(jié)構(gòu)化程序設(shè)計語言

5.4.3面向?qū)ο蟪绦蛟O(shè)計語言

5.4.4其它程序設(shè)計語言

5.4.5標記式語言HTML和XHTML5.4.6腳本語言995.4.1科學計算語言

FORTRAN（FORmula

TRANslating）可稱之為第一個高級編譯語言，從其用詞及涵義即把應用領(lǐng)域的目標鎖定在科學計算（或稱數(shù)值計算）上。Fortran90中有Pascal特征，如指針、遞歸、動態(tài)數(shù)組等概念。Fortran95中簡化了開發(fā)并行程序的任務，去除了Fortran90中的許多特性，還有一些特性被置入“待廢棄之列”。從JohnBackus（1977年獲得圖靈獎）的Fortran0到目前的Fortran95，版本不斷更新，程序設(shè)計人員只要面對解決科學計算問題時，就會自然想到使用公式翻譯語言。Fortran高級程序設(shè)計語言歷經(jīng)如此漫長的年代變遷，還是具有那么長久的生命力，這與它為適應計算機時代的需求而不斷創(chuàng)新是分不開的。在該語言的發(fā)展歷史中，最為重要的版本如下：FortranⅥFortran66Fortran77Fortran90Fortran951005.4.2結(jié)構(gòu)化程序設(shè)計語言

擺脫60年代末軟件危機的最佳解決方案，使開發(fā)軟件編寫代碼的過程中能夠循規(guī)蹈矩地步入正軌，各類開發(fā)人員能夠不謀而合地使用結(jié)構(gòu)化程序設(shè)計的算法最小集來完成。語言完整性而言，有非結(jié)構(gòu)化語句，例如：goto、continue、break等語句，用到它們的話，也會嚴格按照結(jié)構(gòu)化程序設(shè)計的要求和約定用法限制來使用。結(jié)構(gòu)化程序設(shè)計開發(fā)方法使得軟件代碼可讀性、可維護性、以及可擴充性都得到了有力支持。Pascal、C是最成功的結(jié)構(gòu)化程序設(shè)計語言，既是在面向?qū)ο蟪绦蛟O(shè)計中結(jié)構(gòu)化程序設(shè)計開發(fā)方法依然在發(fā)揮著極其重要的作用。1011.Pascal語言1971年，NiklausWirth推出了Pascal語言（以法國數(shù)學家BlaisePascal為命名），這應該屬于wirth前期研究ALGOL60，以及吸取COBOL和PL/Ⅰ的優(yōu)良特性后，而專門設(shè)計用于程序設(shè)計教學的語言。Pascal語言的語法非常嚴謹，類型豐富，層次分明，易讀易寫，是第一個結(jié)構(gòu)化程序設(shè)計語言，它是簡單性和易于表達的完美結(jié)合。在70年代中期之前，通常在大學的計算機程序設(shè)計課程教學都是采用Fortran、PL/Ⅰ、或ALGOL語言，但以后都被Pascal語言所取代，其主要原因是Pascal語言是最適合于結(jié)構(gòu)化程序設(shè)計的教學。1022.C語言1972年，美國貝爾實驗室的KennethLaneThompson和DennisMacAlistairRitchie（1983年獲得圖靈獎）為了重新改寫UNIX操作系統(tǒng)，而共同設(shè)計、開發(fā)了C語言。C是由CPL、BCPL、B和ALGOL68等繼承發(fā)展而來的。CPL在60年代初開發(fā)于劍橋大學。BCPL是1967年由MartinRichards開發(fā)的一種簡單的系統(tǒng)語言。60年代末Thompson用匯編語言編寫了第一版UNIX操作系統(tǒng)。1970年他以BCPL為基礎(chǔ)，在UNIX下實現(xiàn)了第一個高級語言B。1035.4.3

面向?qū)ο蟪绦蛟O(shè)計語言

面向?qū)ο蟪绦蛟O(shè)計語言經(jīng)歷了一個很長的發(fā)展階段，面向?qū)ο蟪绦蛟O(shè)計概念的許多原始思想都來之于Simula67，但是直到Smalltalk演化到Smalltalk80時（1980年），面向?qū)ο蟪绦蛟O(shè)計才得到了充分的發(fā)展。同時對以前的思想作了新的解釋?？梢哉f面向?qū)ο蟪绦蛟O(shè)計語言與面向?qū)ο笏枷霂缀跏峭桨l(fā)展并相互促進的。早先的面向?qū)ο笳Z言，如：LISP、Simula67、Smalltalk、CLU、CwithClasses、Ada83、Modula-2和Smalltalk80等語言。1041.C++語言1980年，Bjarne

Stroustrup博士（1993年獲得了ACMGraceMurrayHopper獎）在貝爾實驗室開始研究從C到C++的開發(fā)。經(jīng)歷了漫長的5年時間，在1985年推出了第一個可以實現(xiàn)的C++1.0版本，被稱為Cfront。隨后至1990年推出了C++3.0版本。1998年ISO對C++進行了標準化。1990年有了ANSIC++標準。1052.Java語言Java是SunMicrosystems公司在1995年推出的一種編程語言。通常我們以JDK（Sun開發(fā)的一套Java開發(fā)工具）的版本來定義Java的版本。目前最新的版本是6.0。Java是一種簡單、面向?qū)ο?、平臺無關(guān)、分布式、解釋型、安全可靠、性能優(yōu)異、多線程、動態(tài)的高級程序設(shè)計語言，特別適合在網(wǎng)絡環(huán)境下的編程使用。1063.C#語言C#（讀作Csharp）是一種為生成在.NETFramework上運行的多種應用程序而設(shè)計的面向?qū)ο蟮木幊陶Z言。簡單、功能強大、類型安全。