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

大學(xué)計(jì)算機(jī)基礎(chǔ)北京航空航天大學(xué)教學(xué)課件1第二層次子課程——C程序設(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ì)范型2本課程重點(diǎn)程序的概念程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)算法的概念與描述方法程序設(shè)計(jì)步驟程序設(shè)計(jì)方法VC集成開(kāi)發(fā)環(huán)境35.1程序和程序設(shè)計(jì)語(yǔ)言5.1.1程序的一般概念

5.1.2程序設(shè)計(jì)語(yǔ)言的概述

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

45.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é)束55.1.1程序的一般概念（續(xù)1）

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

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

計(jì)算機(jī)程序的概念：為實(shí)現(xiàn)某一算法而編寫(xiě)的指令序列。宏觀(guān)地描述該指令序列，可用計(jì)算機(jī)的機(jī)器語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言用經(jīng)典的公式可表示為：程序=算法+數(shù)據(jù)結(jié)構(gòu)1976年NiklausWirth（也是Pascal語(yǔ)言發(fā)明者，1984年獲得圖靈獎(jiǎng)）的專(zhuān)著：Algorithms＋DataStructures＝Programs75.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ǔ)言。8不同類(lèi)型的計(jì)算機(jī)語(yǔ)言機(jī)器語(yǔ)言（MachineLanguage）匯編語(yǔ)言（AssemblyLanguage）高級(jí)語(yǔ)言（HighLevelLanguage）程序設(shè)計(jì)語(yǔ)言的特點(diǎn)

91.機(jī)器語(yǔ)言（MachineLanguage）指令——指揮計(jì)算機(jī)完成某個(gè)基本操作的命令。機(jī)器語(yǔ)言程序注解1011000000001000001011000000101011110100把8存放到累加器A中。將10與累加器A中的8相加，結(jié)果存在A(yíng)中。程序結(jié)束。指令系統(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ǔ)言程序如下：102.匯編語(yǔ)言（AssemblyLanguage）匯編語(yǔ)言——實(shí)質(zhì)就是以容易記憶的代碼或英文單詞來(lái)代替約定的機(jī)器指令。（第二代程序設(shè)計(jì)語(yǔ)言）匯編語(yǔ)言源程序注解MOVA,8ADDA,10HLT把8存放到累加器A中。將10與累加器A中的8相加，結(jié)果存在A(yíng)中。程序結(jié)束。例如：用ADD表示加、SUB表示減、JMP表示跳轉(zhuǎn)、MOV表示數(shù)據(jù)的傳送指令等。匯編源程序——使用匯編語(yǔ)言編寫(xiě)的程序。例如：上述計(jì)算累加器A=8+10的匯編語(yǔ)言程序如下：113.高級(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。可視化語(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ù)135.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í)行程序。語(yǔ)句A入口語(yǔ)句B出口15結(jié)構(gòu)化程序設(shè)計(jì)中——選擇結(jié)構(gòu)

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

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

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

主要用于重復(fù)執(zhí)行相同的語(yǔ)句序列（被稱(chēng)為循環(huán)體），當(dāng)（直到）測(cè)試條件為假時(shí)才可終止執(zhí)行循環(huán)體。出口入口語(yǔ)句序列假測(cè)試條件真while循環(huán)結(jié)構(gòu)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í)間。185.2算法5.2.1算法的定義、分類(lèi)與特征

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

Algorithms＋DataStructures＝Programs1976年N·Wirth的程序概念，在計(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ù)和方法。#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.

算法的定義與分類(lèi)

CPU所遵循的機(jī)器周期與下面這個(gè)算法一樣簡(jiǎn)單。

只要未發(fā)出停機(jī)指令就執(zhí)行以下步驟：取一條指令。解碼該指令。執(zhí)行該指令。生活當(dāng)中的普通活動(dòng)——?jiǎng)兺愣埂?/p>

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

算法的定義與分類(lèi)

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

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

算法的定義與分類(lèi)

（續(xù)2）用一張正方形的紙折疊成一只鳥(niǎo)該過(guò)程通過(guò)自然的溝通方式常常會(huì)引起誤解。有些時(shí)候是因?yàn)樗惴枋鲋惺褂玫男g(shù)語(yǔ)可能擁有多種含義。計(jì)算機(jī)科學(xué)解決歧義性問(wèn)題的方法建立一組嚴(yán)格定義的構(gòu)件塊。利用一系列的構(gòu)件塊來(lái)構(gòu)建算法的表示。這種構(gòu)件塊稱(chēng)作原語(yǔ)（primitive）。231.

算法的定義與分類(lèi)

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

算法的概念算法——解決某個(gè)具體問(wèn)題而采取的方法與步驟的完整和準(zhǔn)確的描述。是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。是問(wèn)題的程序化解決方案，這些解決方案本身并不是答案，而是獲得答案的精確指令。算法的分類(lèi)順序算法：是由馮·諾依曼型計(jì)算機(jī)體系結(jié)構(gòu)所決定的，其主要思想是指令逐條運(yùn)行，每次執(zhí)行一步操作。并行算法：要求在一些更新式的計(jì)算機(jī)中可以在同一時(shí)間執(zhí)行多條指令。252.算法的特征一個(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ù)期的解。262.算法的特征（續(xù)1）算法的發(fā)現(xiàn)程序開(kāi)發(fā)由兩個(gè)活動(dòng)組成——發(fā)現(xiàn)潛在的算法和以程序的方式表示算法。問(wèn)題求解的藝術(shù)數(shù)學(xué)家（波利亞G·Polya）在1945年提出非嚴(yán)格定義的問(wèn)題求解階段：第1階段理解問(wèn)題。第2階段設(shè)計(jì)一個(gè)解決問(wèn)題的計(jì)劃。第3階段完成計(jì)劃。第4階段從準(zhǔn)確度及其是否有潛力作為一個(gè)解決其他問(wèn)題的工具這兩方面來(lái)評(píng)估這個(gè)計(jì)劃。上述階段移植到程序開(kāi)發(fā)中變成：第1階段理解問(wèn)題。第2階段尋找一個(gè)可能解決問(wèn)題的算法過(guò)程的思路。第3階段闡明算法并且用程序?qū)⑵浔磉_(dá)出來(lái)。第4階段從準(zhǔn)確度及其是否有潛力作為一個(gè)工具解決其他問(wèn)題這兩方面來(lái)評(píng)估這個(gè)程序。階段與步驟的差異27例.甲承擔(dān)了確認(rèn)乙的3個(gè)孩子年齡的任務(wù)

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

在考慮了這個(gè)線(xiàn)索以后，甲要求乙給出另外的線(xiàn)索。

乙告訴甲3個(gè)孩子的年齡之和。

甲再次要求乙給出其他線(xiàn)索。

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

在得到這個(gè)線(xiàn)索之后，甲得到了乙的3個(gè)孩子的年齡。（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的三元組這種解決問(wèn)題過(guò)程中的不規(guī)則性是開(kāi)發(fā)問(wèn)題求解的系統(tǒng)方法的基礎(chǔ)。另一個(gè)不規(guī)則性在于，那些還沒(méi)有得到明顯成功的問(wèn)題解決者所得到的神奇靈感可能在完成其他任務(wù)的時(shí)候突然成為了原來(lái)問(wèn)題的一個(gè)解決方法。

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中的每個(gè)三元組的和2+2+9=1328例.求甲乙丙丁賽跑的名次排序

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

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

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

30算法的入門(mén)

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

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

特定實(shí)例31例5.1一個(gè)非算法的計(jì)數(shù)過(guò)程①令n為0；②置n為n+1；③返回②。結(jié)論：不能稱(chēng)為算法。原因：違背了算法特征中（1）、（4）、（5）。有窮性（有效性）：考察下面這條指令:給出一個(gè)所有整數(shù)的列表?！痢?2例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)題。335.2.2算法的描述方法

流程圖（FlowChart）PAD圖（ProblemAnalysisDiafram，問(wèn)題分析圖）N-S圖自然語(yǔ)言偽代碼UML圖（UnifiedModelingLanguage，統(tǒng)一建模語(yǔ)言）341.流程圖流程圖（框圖）用不同形狀的幾何圖形表示不同性質(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)。35用流程圖描述的計(jì)數(shù)器算法362.PAD圖由日立公司推出的PAD圖是一種二維圖。即從上向下順序執(zhí)行，從左到右表示層次關(guān)系。表示三種基本結(jié)構(gòu)的PAD圖如下：373.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圖如下：38用N-S圖描述的計(jì)數(shù)器算法394.自然語(yǔ)言自然語(yǔ)言是人們?nèi)粘Ｉ?、工作和學(xué)習(xí)中使用的通用語(yǔ)言，使用自然語(yǔ)言的文字描述算法通俗易懂，但也有它的缺陷：（1）容易產(chǎn)生歧義性，因?yàn)樽匀徽Z(yǔ)言經(jīng)常要根據(jù)上下文才能判別其含義，不太嚴(yán)格。（2）自然語(yǔ)言很難清楚地表達(dá)算法的邏輯流程，對(duì)于算法中的條件判斷、循環(huán)，尤其是在這些處理中還有多層嵌套，就很難用清晰而直觀(guān)的語(yǔ)言來(lái)表達(dá)算法的流程。因此僅適于描述簡(jiǎn)單問(wèn)題。405.偽代碼偽代碼是介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)，它不能被計(jì)算機(jī)所理解，但使用偽代碼描述的算法很容易轉(zhuǎn)變成某種編程語(yǔ)言。//用偽代碼描述的計(jì)數(shù)器算法如下：

n←0don←n+1whilen<10000

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

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

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

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

printf(“Input3integernumbers:”);/*

輸出雙引號(hào)中的提示信息*/

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

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

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

/*Endofmainfunction*//*

求3個(gè)整數(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.歐幾里得算法求解兩個(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←rreturnm463.

兩個(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ì)換法

474.排序算法給定一個(gè)有n個(gè)元素可排序的序列，例如數(shù)字?jǐn)?shù)據(jù)或字符串?dāng)?shù)據(jù)等，要求按照升序或降序方式重新排列。排序算法：如冒泡排序法、選擇排序法、插入排序法、合并排序法、快速排序法等等排序算法。48蠻力法中的選擇排序法按照降序方式排序的選擇排序算法：SelectionSort（Array[0..n-1]）/*本算法用選擇排序法對(duì)給定數(shù)組按照降序方式排序*//*Array[0..n-1]是有n個(gè)元素的可排序數(shù)組*//*本算法的結(jié)果在A(yíng)rray數(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個(gè)整型變量*/for(i=0;i<=n-2;i++)/*做n-1遍掃描尋找最大元素*/{max=i;/*記錄當(dāng)前掃描最大元素的位置*/for(j=i+1;j<=n-1;j++)/*在n-i

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

/*利用t變量做三角對(duì)換*/t=Array[i],Array[i]=Array[max],Array[max]=t;}}/*EndofSelectionSortfunction*/50選擇排序法降序方式排序操作過(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ò)程如下：51插入排序的基本思想每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。初始狀態(tài)：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]排序52在插入排序過(guò)程中，由于尋找插入位置的方法不同又可以分為不同的插入排序法，這里只介紹最簡(jiǎn)單的直接插入排序法。直接插入排序排序?qū)⑿彰斜碛脗未a表達(dá)的插入排序算法:procedureSort(list)N←2;while(N的值不超過(guò)列表的長(zhǎng)度）do(把列表的第N項(xiàng)作為主元項(xiàng)；把主元項(xiàng)移到一個(gè)臨時(shí)位置使該列表留出一個(gè)空位置；while(如果這個(gè)空位置上面存在一個(gè)名字并且那個(gè)名字比主元大)do(把這個(gè)名字向下移到空位置上使該名字上面留出一個(gè)空位置)把主元項(xiàng)插到列表的空位置上；N←N+1)53直接插入排序函數(shù)模板//用直接插入排序法對(duì)數(shù)組A中的元素進(jìn)行升序排列template<classT>//9-11.h源10-1.hvoidInsertionSort(TA[],intn){inti,j;Ttemp;

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

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

{

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

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

//逐個(gè)比較，直到temp>=A[j-1]時(shí)，j便是應(yīng)插入的位置。

//若達(dá)到j(luò)==0，則0是應(yīng)插入的位置。

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

//將元素逐個(gè)后移，以便找到插入位置時(shí)可立即插入。

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

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

}}直接插入排序54應(yīng)用直接插入排序函數(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<<“開(kāi)始以直接插入排序。。。"<<endl;

InsertionSort(data,Max);

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

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

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

//9_11.cpp55選擇排序的基本思想每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。[541020123]初始狀態(tài)：3[41020125]34[1020125]第i次選擇后，將選出的那個(gè)記錄與第i個(gè)記錄做交換。345[201210]......排序56直接選擇排序在選擇類(lèi)排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡(jiǎn)單的是通過(guò)順序比較找出待排序序列中的最小元素，稱(chēng)為直接選擇排序。排序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;//每一次選出的最小元素之下標(biāo)

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

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

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

smallIndex=j;Swap(A[i],A[smallIndex]);}}58應(yīng)用直接選擇排序函數(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<<"開(kāi)始以直接選擇排序。。。"<<endl;

SelectionSort(data,Max);

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

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

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

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

int

lastExchangeIndex;

//用于記錄每趟被交換的最后一對(duì)元素中較小的下標(biāo)

i=n-1;

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

while(i>0)

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

{lastExchangeIndex=0;

//每一趟開(kāi)始時(shí)，設(shè)置交換標(biāo)志為0（未交換）

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

//每一趟對(duì)元素A[0]…A[i]進(jìn)行比較和交換

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

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

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

lastExchangeIndex=j;

//記錄被交換的一對(duì)元素中較小的下標(biāo)

}

i=lastExchangeIndex;//將i設(shè)置為本趟被交換的最后一對(duì)元素中較小的下標(biāo)}}起泡排序63應(yīng)用起泡排序函數(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<<"開(kāi)始以起泡排序。。。"<<endl;

BubbleSort(data,Max);

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

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

cout<<endl;}起泡排序

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

SeqSearch(Tlist[],intn,Tkey){

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

//SEARCH_METHODS查找66用偽代碼表達(dá)的順序搜索算法procedureSearch(List,TargetValue)if(List空)then(宣布查找失敗)else(選擇列表中的第一個(gè)表項(xiàng)作為T(mén)estEntry;while(TargetValue>TestEntry

并且還有表項(xiàng)沒(méi)有檢查)

（選擇列表中下一個(gè)表項(xiàng)作為T(mén)estEntry）；if(TargetValue=TestEntry)then(宣布查找成功)else

(宣布查找失敗))endif順序搜索是以一種循環(huán)的方式重復(fù)執(zhí)行一個(gè)過(guò)程。List：空列表或升序列表67折半查找的基本思想如果是在一個(gè)元素排列有序的數(shù)組中進(jìn)行查找，可采用折半查找方法。對(duì)已按關(guān)鍵字排序的序列，經(jīng)過(guò)一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。查找68折半查找過(guò)程示意圖用折半查找法，在下列序列中查找值為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表示整個(gè)數(shù)組尚未查找完

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

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

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

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

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

}return-1;//沒(méi)有找到返回-1}折半查找70用偽代碼表達(dá)的二分搜索算法procedureSearch(List,TargetValue)if(List空)then(報(bào)告查找失敗)else[選擇列表的中間項(xiàng)作為T(mén)estEntry;

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

(應(yīng)用Search過(guò)程查看TargetValue是否在List中位于TestEntry

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

(應(yīng)用Search過(guò)程查看TargetValue是否在List中位于TestEntry

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

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

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

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

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

（lgn表示以2為底n的對(duì)數(shù)）74插入排序算法的最差情況分析圖執(zhí)行算法所需要的時(shí)間列表的長(zhǎng)度增加列表長(zhǎng)度時(shí)時(shí)間的長(zhǎng)度列表長(zhǎng)度均勻增長(zhǎng)長(zhǎng)度為n的列表中進(jìn)行最多需要次比較。75二分搜索法的最差情況分析圖執(zhí)行算法所需要的時(shí)間列表的長(zhǎng)度增加列表長(zhǎng)度時(shí)時(shí)間的長(zhǎng)度列表長(zhǎng)度均勻增長(zhǎng)在長(zhǎng)度為n的列表中進(jìn)行查找的時(shí)候最多需要查詢(xún)lgn項(xiàng)。76查找算法查找是指從給定的集合（或者是多重集，它允許幾個(gè)元素具有相同的值）中查找一個(gè)給定的值（稱(chēng)為查找鍵K）。常用的查找算法有順序查找和折半查找，還有那些將原來(lái)的集合表示為另一種形式以方便查找的算法等等。順序查找——直接從頭到尾搜索集合的查找鍵。折半查找——必須首先將集合按照降序或升序排序，然后利用折半技術(shù)搜索集合的查找鍵，所以，當(dāng)集合是有序的時(shí)候，使用折半查找效率高、速度快。77判定哪一種算法是最佳方案針對(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)題上”。785.3程序設(shè)計(jì)步驟與程序設(shè)計(jì)方法

5.3.1程序設(shè)計(jì)步驟

5.3.2程序設(shè)計(jì)方法795.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)題。80測(cè)試程序與調(diào)試程序測(cè)試程序?yàn)榱税l(fā)現(xiàn)程序中的設(shè)計(jì)錯(cuò)誤而運(yùn)行程序。

——所使用的測(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)的。81高級(jí)語(yǔ)言編寫(xiě)和運(yùn)行過(guò)程yesyes源文件目標(biāo)文件可執(zhí)行文件其它目標(biāo)文件庫(kù)函數(shù)開(kāi)始編輯源程序檢查確認(rèn)有錯(cuò)？編譯程序有錯(cuò)？有錯(cuò)？運(yùn)行程序有錯(cuò)？yesnonoyes連接程序no結(jié)束no數(shù)據(jù)825.3.2程序設(shè)計(jì)方法早期的程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法面向?qū)ο蟪绦蛟O(shè)計(jì)方法831.早期的程序設(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)常被采用的。842.結(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ā)的弊端85結(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)化編程863.面向?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ì)方法。87面向?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ù)和方法的共享。88面向?qū)ο蟪绦蛟O(shè)計(jì)的重要概念面向?qū)ο蟪绦蛟O(shè)計(jì)的重要概念：對(duì)象（Object）類(lèi)（Class）消息（Message）方法（Method）89對(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)。90類(lèi)（Class）人類(lèi)在認(rèn)知客觀(guā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)系。91消息（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)。92方法（Method）面向?qū)ο蠹夹g(shù)中的方法——針對(duì)對(duì)象的屬性的各種操作。將一些通用的過(guò)程或函數(shù)編寫(xiě)好并封裝起來(lái)，作為方法直接提供給用戶(hù)調(diào)用。93面向?qū)ο蟪绦蛟O(shè)計(jì)幾個(gè)重要的基本特征面向?qū)ο蟪绦蛟O(shè)計(jì)幾個(gè)重要的基本特征：抽象（Abstract）封裝（Encapsulation）繼承（Inheritance）多態(tài)（Polymorphism）94抽象（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ì)所采用的核心方法。95封裝（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ù)性和可移植性。96繼承（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)控制方式。97多態(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)算。985.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ǔ)言995.4.1科學(xué)計(jì)算語(yǔ)言

FORTRAN（FORmula

TRANslating）可稱(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ⅥFortran66Fortran77Fortran90Fortran951005.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ā)揮著極其重要的作用。1011.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é)。1022.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。1035.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ǔ)言。1041.C++語(yǔ)言1980年，Bjarne

Stroustrup博士（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)。1052.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)境下的編程使用。1063.C#語(yǔ)言C#（讀作Csharp）是一種為生成在.NETFramework上運(yùn)行的多種應(yīng)用程序而設(shè)計(jì)的面向?qū)ο蟮木幊陶Z(yǔ)言。簡(jiǎn)單、功能強(qiáng)大、類(lèi)型安全。