計算機輔助工程基礎(chǔ)

第二章計算機輔助工程基礎(chǔ)

■數(shù)據(jù)結(jié)構(gòu)和算法

■計算機圖形學(xué)

■工程數(shù)據(jù)庫

■軟件工程

■新技術(shù)趨勢

>

2.1數(shù)據(jù)結(jié)構(gòu)和算法

y

交叉口信號相位的設(shè)置問題

信號相位是指在一個交叉口某個方向的交通流（或幾個交通流的組合）

同時得到的通行權(quán)及被分配得到這些通行權(quán)的時間帶。

在多叉路口需設(shè)幾個相位才能既使車輛相互之間不沖突而又達到最大的

流通呢？

假設(shè)有如圖所示的五叉路，其中C和E為

單行道，在路口有13條可行的通路，其

中有的可以同時通行而不發(fā)生沖突，如

A-B和E—C,而有的在同時通行時一

定會沖突，如E-B和A—D,那末，在

該交叉口應(yīng)如何設(shè)置相位？這個問題可

以轉(zhuǎn)換成一個圖的染色問題。

A

交叉口信號相位的設(shè)置問題

——圖的染色問題

.?在圖上以一個圓圈表示一條通路,在不能同時通行的兩個圓圈之

間畫一連線，對圖中的圓圈上色，要求同一連線上的兩個圓圈不同

色且顏色種類最少；

?一種解決方案，圖中13個圓圈表示13條通路，四種顏色分別表示

A

基本概念

數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元

素的集合。在任何問題中，數(shù)據(jù)元素都不是孤立存在的,

而是在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之

間的關(guān)系稱為結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)就是一門研究非數(shù)值性程序設(shè)計中計算機操作

的對象以及它們之間的關(guān)系和運算等的學(xué)科

基本概念

■數(shù)據(jù):對客觀事物的符號表示，在計算機科學(xué)中是指所

有能輸入到計算機中并被計算機程序處理的符號的總稱

■數(shù)據(jù)元素:數(shù)據(jù)的基本單位，在計算機程序中通常作為

一個整體進行考慮和處理

■數(shù)據(jù)對象:性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個

子集

■數(shù)據(jù)結(jié)構(gòu):相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元

素的集合

四類基本結(jié)構(gòu)

■集合數(shù)據(jù)元素1數(shù)據(jù)元素2

-線性結(jié)構(gòu)數(shù)據(jù)元素1數(shù)據(jù)元素2

■

■樹形結(jié)構(gòu)數(shù)據(jù)元素2

數(shù)據(jù)元素1

數(shù)據(jù)元素3

■網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素2

數(shù)據(jù)元素1

數(shù)據(jù)元素3

線性表

線性表是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)，它是屬同一數(shù)

據(jù)對象的〃個數(shù)據(jù)元素的有限序列

■若將線性表記為，稱與］是由的

直接前趨元素，火［震％的苴于芟盾Z度尤第

■線性表中元素的個數(shù)〃（心=0）定義為線性表的長度，片0時

稱為空表。

■在非空表中的每個數(shù)據(jù)元素都有一個確定的位置，比如《

是第Z?個數(shù)據(jù)元素，稱Z?為生在線性表中的位序

線性表1—順序表

順序表以一組地址連續(xù)的存儲單元依次存儲線性表的

數(shù)據(jù)元素，由此在邏輯上相鄰的兩個元素在物理位置上

也是相鄰的。只要給定了存儲線性表的起始位置，表中

任一數(shù)據(jù)元素都可以隨機存取，因此順序表是一種隨機

存取的存儲結(jié)構(gòu)。順序表通常用數(shù)組類型來實現(xiàn).

12...n-1n

ai的地址計算函數(shù)為：

addr(aj=addr(aT)+(i-1)*d

線性表2—鏈表

■鏈表使用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這

組存儲單元可以是連續(xù)的，也可以是不連續(xù)的，即邏輯上

相鄰的兩個元素在物理位置不一定相鄰）。

■數(shù)據(jù)元素生的存儲映象（稱為結(jié)點）包括兩個域：①存儲

數(shù)據(jù)元素信息的數(shù)據(jù)域；②存儲直接后繼位置信息的指針

域，〃個結(jié)點鏈接成一個鏈表。鏈表在高級程序語言中可用

指針來實現(xiàn)

線性表2—鏈表

數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指針

刪除元素

添加元素

數(shù)據(jù)指針

棧

■棧是限定在表尾進行插入或刪除操作的特殊線性表。先

進后出的線性表.

■%為棧底元素，%為棧頂元素。

■棧中元素按％,…,瑪?shù)拇涡蜻M棧，出棧的第一個元素

應(yīng)為棧頂元素心。

棧

基本運算有：

■建立一個棧

■檢查棧中剩余容量

■從棧頂推入一個元素

■從棧頂取出一個元素

-刪除一個棧

應(yīng)用舉例：常用軟件中的撤銷9與恢復(fù)Q操作

隊列

■隊列是一種先進先出的線性表。

■它只允許在表的一端進行插入，而在表的另一端進行

刪除。在隊列中，允許插入的一端叫做隊尾，允許刪除

的一端則稱為隊首。

■假設(shè)隊列為Q=

■則稱為為隊首元素，4為隊尾元素。

■隊中元素按％,出，…，程的次序進入

■退出隊列也只能按這個次序依次進行。

隊列

基本運算有：

-建立一個隊列

■檢查隊列狀態(tài)

■從隊尾插入一個元素

■從隊首刪除一個元素

-刪除一個隊列

應(yīng)用舉例：生活中的排隊

例一交叉口仿真系統(tǒng)控制結(jié)構(gòu)

■當(dāng)采用仿真方法分析一系列交叉口所發(fā)生的交通狀態(tài)時,

需要采用分時處理技術(shù)分別逐個改變每一個交叉口的狀

態(tài)，同時系統(tǒng)整體環(huán)境也在發(fā)生著一些具有時間先后次

序的情況。

系統(tǒng)環(huán)境信息管道

控制結(jié)構(gòu)

□

9交叉口信息管道

3交叉口4交叉口5

樹

■結(jié)點A為樹的根，根的每個分

支稱為子樹，子樹也是一棵樹

■結(jié)點子樹的根為結(jié)點的孩子，

如B、C、D為結(jié)點A的孩子，

而A為B、C、D的雙親

■同一個雙親的孩子之間為兄

弟關(guān)系，如B、C、D

■沒有孩子的結(jié)點為樹的葉子，

H、F、G、D為樹的葉子

樹的基本運算

-初始化一棵樹

■得到樹的根

-得到一個結(jié)點的雙親

■得到一個結(jié)點的兄弟

■得到一個結(jié)點的孩子

■插入子樹

-刪除子樹

■遍歷樹

■清空樹

特殊的樹

■二叉樹

■二叉搜索樹

■哈夫曼樹用于具有層次結(jié)構(gòu)的數(shù)

■B樹據(jù)的組織、搜索和比較

■AVL樹

■紅-黑樹

各種特定的樹結(jié)構(gòu)被廣泛應(yīng)用于交通

CAE軟件中，它們可以加快查找的速度

和分析處理的效率。

二叉樹

二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用

■對二叉樹的許多操作算法簡單；

-而任何樹都可以與二叉樹相互轉(zhuǎn)換，解決了樹的存儲結(jié)構(gòu)及其運

算中存在的復(fù)雜性。

定義：二叉樹是由n(n>=0)個結(jié)點的有限集合構(gòu)成，此集

合或者為空集，或者由一個根結(jié)點及兩棵互不相交的左

右子樹組成，并且左右子樹都是二叉樹。

這也是一個定義。二叉樹可以是空集合，根可以有

空的左子樹或空的右子樹。

二叉樹結(jié)點的子樹要區(qū)分左子樹和右子樹即使只有一

棵子樹也要進行區(qū)分，說明它是左子樹，還是右子樹。

這是二叉樹與樹的最主要的差別。

二叉樹的5種形式

⑹

根和空的左

空二叉樹

右子樹

(c)

根和左子樹根和右子樹根和左右子樹

遍歷二叉樹

在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)

點，或者對樹中全部結(jié)點逐一進行某種處理。這就引入了遍歷二

叉樹的問題，即如何按某條搜索路徑巡訪樹中的每一個結(jié)點，使

得每一個結(jié)點均被訪問一次，而且僅被訪問一次。

遍歷對線性結(jié)構(gòu)是容易解決的，而二叉樹是非線性的，因而

需要尋找一種規(guī)律，以便使二叉樹上的結(jié)點能排列在一個線性隊

列上，從而便于遍歷。

（根結(jié)點）

一（右子樹）

由二叉樹的遞歸定義，二叉樹的

三個基本組成單元是：根結(jié)點、

（左子樹）

左子樹和右子樹。

假如以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點和遍歷

右子樹，遍歷整個二叉樹則有DLR、LDR、LRD、DRL、RDL、

RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分

別規(guī)定為：

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

LRD——后（根）序遍歷。

先序遍歷二叉樹

先序遍歷二叉樹的操作定義為：

若二叉樹為空，則空操作；否則

(1)訪問根結(jié)點；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。

124537

中序遍歷二叉樹

中序遍歷二叉樹的操作定義為：

若二叉樹為空，則空操作；否則

(1)中序遍歷左子樹；

(2)訪問根結(jié)點；

(3)中序遍歷右子樹。

425137

后序遍歷二叉樹

后序遍歷二叉樹的操作定義為：

若二叉樹為空，則空操作；否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點。

452731

4例題

例如圖(1)所示的二叉樹表達式

(a+b*(c-d)-e/f)

按先序遍歷：-+a*b-cd/ef

按中序遍歷：a+b*c-d-e/f

按后序遍歷：abcd-*+ef/-

冽題

已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHU,中序遍

歷的結(jié)果是EBCDAFHIGJ,試畫出這棵二叉樹。

當(dāng)前序序列為ABECDFGH口，中序序列為EBCDAFHIGJ時,

逐步形成二叉樹的過程如下圖所示：

樹的路徑長度(PL)

PL是指從根到其它各結(jié)點的路徑長度(分支數(shù))

之和。

(a)PL=13(b)PL=15

完全二叉樹各結(jié)點的路徑長度分別是數(shù)列

0,1,122,2,2,3,3,3,3,3,3,3,3,4,4,4,…其路徑長度為前n項之和,

具有最小值：戶乙=三口。名2。一+1）」

z=o

霍夫曼樹

具有最小WPL的擴充二叉樹叫霍夫曼樹

n—i

亞包=>^乜

7=0

(a)WPL=36(b)WPL=46(c)WPL=35(霍夫曼樹)

霍夫曼樹的構(gòu)造方法

將n個權(quán)值視為具有n棵擴充二叉樹的森林F,然后重復(fù)以

下步驟，直到F中只有一棵樹為止：

①在F中選根的權(quán)值最小的兩棵作為左右子樹構(gòu)造一棵新

的二叉樹，其根的權(quán)為左右子樹根的權(quán)值之和。

②在F中刪除那兩棵樹，并把新的二叉樹加入。

J霍夫曼樹的構(gòu)造方法

⑦，②，⑤，④⑦，⑤,

(b)

霍夫曼編碼——霍夫曼樹應(yīng)用事例

1、最小冗余編碼問題

☆設(shè)用0,I碼來對一串字符信息進行等長編碼：

T——00,A——01,D——10,S——11

☆對于信息串“ATTSTATADT”所得至U的編碼為

01,00,00,11,00,01,00,01,10,00共20位編碼

☆字母集合｛T,A,D,S｝出現(xiàn)的頻度W=｛5,3,1,1),

若采用不等長編碼表示

T——0,A——10,D——110,S——111所得到的

編碼是10,0,0,111,0,10,0,10,110,0共17位，這是最小冗

余編碼。

霍夫曼編碼——霍夫曼樹應(yīng)用事例

☆以字符的頻度為權(quán)構(gòu)造霍夫曼樹

☆左分支表示0,右分支表示1

☆從根到各外結(jié)點路徑上經(jīng)由的數(shù)

字序列構(gòu)成各字符的編碼

一^霍夫曼編碼—霍夫曼樹應(yīng)用事例

3、霍夫曼樹編碼的優(yōu)越性

☆是最小冗余碼

☆非前綴碼——碼Ci不是碼Q的前綴

☆譯碼簡單唯一——不斷從根開始沿霍夫曼編碼樹查找。

10001110100101100譯碼得到的只能是報文串：|

ATTSTATADT

習(xí)題

■給定權(quán)值集合｛15,03,14,02,06,09,16,17),構(gòu)

造相應(yīng)的霍夫曼樹，并計算它的帶權(quán)外部路徑長度。

■假定用于通信的電文僅由8個字母cl,c2,c3,c4,c5,

c6,c7,c8組成，各字母在電文中出現(xiàn)的頻率分別為5,

25,3,6,10,11,36,4o試為這8個字母設(shè)計不等長

Huffman編碼，并給出該電文的總碼數(shù)。

05

0203

(VI)

0203

此樹的帶權(quán)路徑長度WPL229

y答_

已知字母集{cl,c2,c3,c4,c5,c6,c7,c8},頻率<5,25,3,6,

10,11,36,4},則Huffman編碼為:

clc2c3c4c5c6c7c8

01101000000111001010110001

00

電文總碼數(shù)為01

4*5+2*25+4*3+4*6+3*10961

0

+3*11+2*36+4*4=2570

17,2156

00

C2

70

00

C

345

C3C8C4

例：路網(wǎng)規(guī)劃

在路網(wǎng)規(guī)劃過程中，需在現(xiàn)狀路網(wǎng)的基礎(chǔ)上不斷改造、完善，由近及遠

地提出各個規(guī)劃特征年的路網(wǎng)規(guī)劃方案；類似這種由單個初始路網(wǎng)經(jīng)過多個

階段的演變而衍生成的一系列有著直接或間接派生關(guān)系的路網(wǎng)方案可稱之為

動態(tài)路網(wǎng)。在動態(tài)路網(wǎng)中，不同路網(wǎng)方案的數(shù)據(jù)存在大量的重復(fù)部分。

傳統(tǒng)的交通分析軟件，對動態(tài)路網(wǎng)大多是按多個獨立路網(wǎng)建立和分析的。

不但造成數(shù)據(jù)冗余過大，更致命的是掩蓋了路網(wǎng)動態(tài)演變的過程?；跇浣Y(jié)

構(gòu)的方案樹可有效描述動態(tài)路網(wǎng)的動態(tài)性，揭示路網(wǎng)方案之間的聯(lián)系。

-方案樹的每個結(jié)點代表一個路網(wǎng)方案;

■根結(jié)點即為初始路網(wǎng)；

■連接結(jié)點的邊代表方案間的直接派生關(guān)系；

■雙親結(jié)點即為基礎(chǔ)方案，孩子結(jié)點即為派生方案，兄弟結(jié)點代表了不同

的比選方案；

-樹的高度代表動態(tài)路網(wǎng)的層次數(shù)，一個層次代表動態(tài)路網(wǎng)的一個演變階

段。

圖一有向圖

■有向圖G=(N,4)由節(jié)點集N和弧集/構(gòu)成。N中的每個元素z?稱為節(jié)點

(或頂點)。4中的每個元素?？捎蒒中的有序節(jié)點對?,/)表示，稱為從2

到J的弧(或邊)

■對于弧&/),z.和/稱為。的端點，其中，.稱為起點，/稱為終點，并稱/鄰

才妾至加

■對于弧(V)，稱(zj)關(guān)聯(lián)于環(huán)明稱?,/)為泊勺出弧、)的入弧

-一個節(jié)點的出弧的數(shù)目稱為該節(jié)點的出度，入孤的數(shù)目稱為該節(jié)點的

入度，出度與入度之和稱為該節(jié)點的度

■起點和終點均相同的2條及2條以上的弧稱為多重弧，起點和終點為同

一節(jié)點的弧稱為環(huán)。一個無環(huán)、無多重弧的有向圖稱為簡單有向圖，一

個無環(huán)、但允許有多重弧的有向圖稱為多重有向圖。沒有任何弧與之關(guān)

聯(lián)的節(jié)點稱為孤立點

圖一有向圖

節(jié)點集N={1,2,3},弧集4={(1,2),

(1,3),(2,1),(2,3),(3,2)}

節(jié)點1是弧(1,2)的起點，節(jié)點2是該

弧的終點，節(jié)點2鄰接到節(jié)點1

弧(1,2)關(guān)聯(lián)于節(jié)點1和2,弧(1,2)為

節(jié)點1的出弧、節(jié)點2的入弧

節(jié)點1的出度為2,入度為1,度為3

■無向圖的定義類似于有向圖，根本的區(qū)別在于無向圖中組

成弧的節(jié)點對是無序的，即連接節(jié)點環(huán)9的弧既可以記成

(4)，也可記成(//)。有向圖的相關(guān)概念都可自然地推廣到

無向圖上來，但在涉及方向性的概念時會有一些微小的差異,

比如無向圖的一條弧的端點不再有起點和終點之分。

■有向網(wǎng)絡(luò)就是賦予節(jié)點和弧一定數(shù)值、權(quán)重的有向圖，也

就是賦權(quán)有向圖；對應(yīng)地，無向網(wǎng)絡(luò)就是賦權(quán)無向圖。網(wǎng)絡(luò)

和圖的區(qū)別在于：它不僅代表著一種數(shù)學(xué)形式，而且具有物

理結(jié)構(gòu)。但是，由于圖都是可以賦權(quán)的，因此在一般場合下,

對圖和網(wǎng)絡(luò)的概念都不加細分，兩者可以通用。

有向圖的表示法一關(guān)聯(lián)矩陣

有向圖G=（N,4）的關(guān)聯(lián)矩陣B是一個〃XM的矩陣（〃為節(jié)點數(shù)目，加為弧

數(shù)目），每行對應(yīng)于一個節(jié)點，每列對應(yīng)于一條弧。若節(jié)點，是弧。的起

點，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；若，是。的終點，則對應(yīng)的元素為T；

若，.與。不關(guān)聯(lián)，則對應(yīng)的元素為0。對于簡單圖，關(guān)聯(lián)矩陣每列只含有兩

個非零元（一個1,一個-1）。在關(guān)聯(lián)矩陣中，每行元素1的個數(shù)正好是

對應(yīng)節(jié)點的出度，每行元素-1的個數(shù)正好是對應(yīng)頂點的入度。

(1,2)(1,3)(2,1)(2,3)(3,2)

1「11—1001

1

2T011T

30—10—11

有向圖的表示法一鄰接矩陣

有向圖G=(N,⑷的鄰接矩陣C是一個“X〃的矩陣，每行、每列均對應(yīng)一個

節(jié)點；如果兩節(jié)點之間有一條弧，則鄰接矩陣中對應(yīng)的元素為1;否則

為零。每行元素之和正好是對應(yīng)節(jié)點的出度，每列元素之和正好是對應(yīng)

節(jié)點的入度。

123

1「0111

2j101[

3010

有向圖的表示法一鄰接表

有向圖的鄰接表就是所有節(jié)點的鄰接節(jié)點集的列表。鄰接表可以用多種

數(shù)據(jù)結(jié)構(gòu)加以實現(xiàn)，通常采用數(shù)組加鏈表的混合形式。在這樣的鄰接表

中，節(jié)點存儲在數(shù)組中，對每個節(jié)點用一個單向鏈表列出該節(jié)點的所有

鄰接節(jié)點，鏈表中每個單元實際對應(yīng)于一條?。ㄔ摶〉钠瘘c取決于鏈表

頭，終點取決于該單元存儲的節(jié)點）。

A

2332

有向圖的表示法一方法比較

有向圖的關(guān)聯(lián)矩陣和鄰接矩陣的表示法非常簡單、直接。但

是，在關(guān)聯(lián)矩陣的所有〃X加個元素中，只有2加個為非零元；

在鄰接矩陣的所有層個元素中，只有加個為非零元，它們屬

于稀疏矩陣。對于比較稀疏的網(wǎng)絡(luò)（比如交通網(wǎng)絡(luò)，節(jié)點的

平均出度在3左右），這兩種表示法會浪費大量的存儲空間。

而鄰接表的存儲效率最高，只需要什加個存儲單位，尤其適

合于稀疏網(wǎng)絡(luò)。

其他的有向圖表示法包括：星形表、雙向鄰接表、鄰接多重

表等，可參考相關(guān)文獻。

土最短路徑

求最短路徑的Dijkstra算法

■設(shè)有向圖出(V,E),其中，V={0,1,2」……，n),

cost是表不G的鄰接矩陣，cost[i][jj表不有向邊〈i,j＞的

權(quán)。若不存在有向邊＜i,j＞,則cost的權(quán)為無窮大。

-設(shè)S是一個集合，其中的每個元素表示一個頂點，從源點

到這些頂點的最短距離已經(jīng)求出。設(shè)頂點1為源點，集合

初態(tài)s={0}。

■數(shù)組dist記錄從源點到其他各項點當(dāng)前的最短距離，其初

值為dist[i]=cost[0]ji],i=l,2,???,no

■從s之外的頂點集合V-S中選出一個頂點w,使dist[w]的值

最小。于是從源點到達w只通過s中的頂點，把w加入集合s

中，調(diào)整dist中從源點至(JV-S中每個頂點v的距離：

dist[v]=min{dist[v]，dist(w)+cost[w][v]}

最短路徑

.重復(fù)上述過程，直到S中包含V中其余各項點的最短路徑。

-最終結(jié)果是：S記錄了存在叢鹿更臚算照件單熟空魯獲

數(shù)組dist記錄了從源點到V中到其余各項點N間的最短路徑.

Example

45

50

201015

50

15

3

Answer

sdist

Answer(Con1)

-最后的輸出結(jié)果如下:

■—3-235

■20

■3-215

■"3-230

■5-210

■6-2oo

算法及其復(fù)雜度分析

(1)有窮性：一個算法必須總是(對任何合法的輸入值)在執(zhí)行有窮步

之后結(jié)束，且每一步都可在有窮時間內(nèi)完成。

(2)確定性：算法中每一條指令必須有確切的含義,讀者理解時不會產(chǎn)

生二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對于

相同的輸入只能得出相同的輸出。

(3)可行性：一個算法是可行的,即算法中描述的操作都是可以通過已

經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。

(4)輸入：一個算法有零個或多個的輸入,這些輸入取自于某個特定的

對象的集合。

(5)輸出：一個算法有一個或多個的輸出。這些輸出是同輸入有著某些

特定關(guān)系的量。

4算法及其復(fù)雜度分析_

Fs常設(shè)計一個“好”的算法應(yīng)考慮達到以下目標(biāo)：

-(1)正確性：算法應(yīng)當(dāng)滿足具體問題的需求。通常一個大型問題的需求，要

以特定的規(guī)格說明方式給出，而一個不那么嚴(yán)格的問題至少應(yīng)當(dāng)包括對于輸

入、輸出和加工處理等明確的無歧義性的描述。設(shè)計或選擇的算法應(yīng)當(dāng)能正

確地反映這種需求。

-(2)可讀性：算法主要是為了人的閱讀與交流,其次才是機器執(zhí)行?？勺x性

好有助于人對算法的理解；晦澀難懂的程序易于隱藏較多錯誤，難以調(diào)試和

修改。

-(3)健壯性：當(dāng)輸入數(shù)據(jù)非法時,算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或進行處理，而

不會產(chǎn)生莫明其妙的輸出結(jié)果。

-(4)效率與低存儲量需求：通俗地說,效率指的是算法執(zhí)行時間。存儲量需

求指算法執(zhí)行過程中所需要的最大存儲空間。一個好算法要有高的執(zhí)行效率

和低的存儲量需求。

4算法及其復(fù)雜度分析_

Fs常設(shè)計一個“好”的算法應(yīng)考慮達到以下目標(biāo)：

-(1)正確性：算法應(yīng)當(dāng)滿足具體問題的需求。通常一個大型問題的需求，要

以特定的規(guī)格說明方式給出，而一個不那么嚴(yán)格的問題至少應(yīng)當(dāng)包括對于輸

入、輸出和加工處理等明確的無歧義性的描述。設(shè)計或選擇的算法應(yīng)當(dāng)能正

確地反映這種需求。

-(2)可讀性：算法主要是為了人的閱讀與交流,其次才是機器執(zhí)行?？勺x性

好有助于人對算法的理解；晦澀難懂的程序易于隱藏較多錯誤，難以調(diào)試和

修改。

-(3)健壯性：當(dāng)輸入數(shù)據(jù)非法時,算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或進行處理，而

不會產(chǎn)生莫明其妙的輸出結(jié)果。

-(4)效率與低存儲量需求：通俗地說,效率指的是算法執(zhí)行時間。存儲量需

求指算法執(zhí)行過程中所需要的最大存儲空間。一個好算法要有高的執(zhí)行效率

和低的存儲量需求。

2?2計算機圖形學(xué)

概念

計算機圖形學(xué)主要研究用計算機及其圖形

設(shè)備來輸入、表示、變換、運算和輸出圖

形的原理、算法及系統(tǒng)。

圖形主要分為兩類，一類是基于線條信息

表示的，如工程圖、等高線地圖、曲面的

線框圖等，另一類是明暗圖，也就是通常

所說的真實感圖形。

概念

計算機圖形學(xué)主要研究用計算機及其圖形

設(shè)備來輸入、表示、變換、運算和輸出圖

形的原理、算法及系統(tǒng)。

圖形主要分為兩類，一類是基于線條信息

表示的，如工程圖、等高線地圖、曲面的

線框圖等，另一類是明暗圖，也就是通常

所說的真實感圖形。

圖形生成和變換:曲線繪年

規(guī)則曲線的繪制

最小二乘法擬合

三次樣條曲線

貝齊爾(Bezier)

曲線B樣條曲線

圖形生成和變換：曲面繪

雙線性曲面

直紋曲面

回轉(zhuǎn)曲面

孔思(coons)曲面

圖形生成和變換:男

平面裁剪（線段裁剪、曲線裁剪和多邊形裁

剪）——分區(qū)編碼剪裁

三維裁剪

圖形生成和變換：二維幾何

變換、三維幾何變換等??????

例

100110001010

000100000010

010101000110

---------------------------------------------------------

2?3工程數(shù)據(jù)庫

數(shù)據(jù)庫系統(tǒng)基礎(chǔ)

數(shù)據(jù)庫是通用化的相關(guān)數(shù)據(jù)的集合，它不僅包

括數(shù)據(jù)本身，而且包括關(guān)于數(shù)據(jù)之間的聯(lián)系。

因此，一個數(shù)據(jù)庫有四個主要成分：數(shù)據(jù)、聯(lián)

系、約束和模式。數(shù)據(jù)是所存儲的邏輯實體在

計算機中的二進制表示；聯(lián)系表示數(shù)據(jù)項之間

的某種對應(yīng)；約束是定義正確數(shù)據(jù)狀態(tài)的斷言;

一種模式描述數(shù)據(jù)庫中數(shù)據(jù)的組織和聯(lián)系。

數(shù)據(jù)

聯(lián)系

數(shù)據(jù)庫

約束

模式

數(shù)據(jù)庫系統(tǒng)基礎(chǔ)

模式為數(shù)據(jù)庫管理系統(tǒng)各個組成部分的使用和應(yīng)

用的安全定義數(shù)據(jù)庫的各種視圖。模式將數(shù)據(jù)存

儲的物理外表與邏輯表示分開。內(nèi)部模式定義數(shù)

據(jù)在物理數(shù)據(jù)存儲區(qū)中如何組織以及放在何處。

概念模式按照適當(dāng)?shù)臄?shù)據(jù)庫數(shù)據(jù)模型（如關(guān)系模

型或?qū)ο竽Ｐ停┒x所存儲數(shù)據(jù)的結(jié)構(gòu)。外部模

式為特定用戶們定義數(shù)據(jù)庫的一個或多個視圖。

外部模式1外部模式1外部模式n

物理數(shù)據(jù)庫

數(shù)據(jù)庫的數(shù)據(jù)模型一層次模型

層次模型是一種基本層次聯(lián)系的集合，它實際上是一種有

根定向的有序樹。層次模型的基本結(jié)構(gòu)是樹結(jié)構(gòu)——根、

枝、葉結(jié)構(gòu)，數(shù)據(jù)存放的基本單位是片斷（即層），片斷

是內(nèi)在有邏輯聯(lián)系的一組數(shù)據(jù)，總的來說，層次模型按照

樹形結(jié)構(gòu)以片斷為單位存放數(shù)據(jù)。層次模型比較容易實現(xiàn),

但是查找比較麻煩，數(shù)據(jù)的冗余度也比較大。

2層

層

數(shù)據(jù)庫的數(shù)據(jù)模型一網(wǎng)狀模型

所謂網(wǎng)狀模型是指一個連通的基本層次聯(lián)系的集合。復(fù)雜

的網(wǎng)總可以分解成若干個基本結(jié)構(gòu)，即分解成系。系有系

主（只有一個）和系屬（可以有多個），系主和系屬之間

有關(guān)系，而且關(guān)系是雙向的。

網(wǎng)狀模型存放的基本單位是記錄，也就是按記錄存放，查

詢時，從系（系主和系屬）查起。網(wǎng)狀模型查找時間較省,

數(shù)據(jù)和冗余度比層次模型小，但比關(guān)系模型要大。

RiR2R3R4

數(shù)據(jù)庫的數(shù)據(jù)模型一關(guān)系模型

關(guān)系模型是目前最為流行的數(shù)據(jù)模型，它是由許

多二維關(guān)系表組成的集合。下表就是一張關(guān)系表,

R是關(guān)系名，Aj是屬性名，關(guān)系和屬性

(R,A],A2…4)組成了數(shù)據(jù)表的模式；Vjj叫做分

量，表中的一列是一個屬性，相當(dāng)于一個數(shù)據(jù)項,

一行叫做一個元組，相當(dāng)于一條記錄。

u?S￡§

<>>>**>

?:::

?一?中

<r

?:?:

1峪

<>>>,>>

A—>

（中國地圖，面積，周長，名稱）

ESMOND

54.447168.4888黑龍江省

4129.113129.933內(nèi)蒙古自治區(qū)

175.59184.9053新強維吾爾自治區(qū)

21.314541.1859吉林省

15.602838.3792遼寧省

41.507776.7812的省

1.733218.49791北京巾

15.961124.7842山西省

1.213677.26263天津市

20.393638.5711陜西省

5.2717718.5204寧夏回族自治區(qū)

71.36359.5622青海省

15.388140.9005山東省

114.33176.6291西藏目治區(qū)

16.13530.9113河南省

9.7358727.8925江蘇省

13.365129.4915安徽省

關(guān)系表的操作可以分為以下四種：

■通用的集合操作，如并、交、差運算等；

■去除關(guān)系表的某些部分的操作，包括選擇和投影，前者

去除某些元組，后者則用于除去某些屬性；

■兩個關(guān)系表的合并，包括“笛卡爾積”以及各種方式的

連接運算；

■更名操作，即對關(guān)系表屬性名稱的修改，它不改變元組,

但是改變了關(guān)系表的模式。

這些操作以及相關(guān)的都是通過結(jié)構(gòu)化查詢語言SQL完成的

Query1瀏覽窗口-In]x|

.數(shù)據(jù)庫的數(shù)據(jù)模型—面向?qū)ο竽Ｐ?/p>

網(wǎng)絡(luò)和層次以及關(guān)系模型都適合那些結(jié)構(gòu)簡單以及訪問有

規(guī)律的數(shù)據(jù)。

面向?qū)ο髷?shù)據(jù)庫的引入就是為了滿足一再出現(xiàn)的復(fù)雜信息

的共享。在復(fù)雜數(shù)據(jù)進入數(shù)據(jù)庫以后，數(shù)據(jù)庫提供了存貯

信息的統(tǒng)一視圖，與具體存貯結(jié)構(gòu)無關(guān)。把物理數(shù)據(jù)結(jié)構(gòu)

與邏輯數(shù)據(jù)結(jié)構(gòu)分開，同時控制數(shù)據(jù)的共享及保持?jǐn)?shù)據(jù)的

正確性、完整性和一致性，大大方便了應(yīng)用程序的開發(fā)和

維護，減少生命周期內(nèi)的各種費用。通過一組優(yōu)化的程序

來管理數(shù)據(jù)，使得整體效果更優(yōu)，性能更穩(wěn)定。

.數(shù)據(jù)庫管理系統(tǒng)

品據(jù)庫管理系統(tǒng)是為數(shù)據(jù)庫訪問提供服務(wù)的軟件,同時維

護所有數(shù)據(jù)必需的特性。數(shù)據(jù)庫管理系統(tǒng)提供下列服務(wù)：

1）事務(wù)處理

有三種特定的事務(wù)操作：啟動指示將開始一個新事務(wù)，提

交指示事務(wù)已正常終止且其作用結(jié)果將持久存在，以及放

棄指示事務(wù)被異常終止，其所有結(jié)果將被放棄。

2）并發(fā)控制

并發(fā)控制是一種數(shù)據(jù)庫管理活動，它協(xié)調(diào)數(shù)據(jù)庫操作進程

的并發(fā)操作和對共享數(shù)據(jù)的訪問，并且解決它們之間可能

發(fā)生的潛在沖突。

數(shù)據(jù)庫管理系統(tǒng)

3）恢復(fù)

數(shù)據(jù)庫中恢復(fù)的目標(biāo)是確保異常終止或出錯的事務(wù)不會對

數(shù)據(jù)庫或其它事務(wù)產(chǎn)生不利影響?；謴?fù)可使得數(shù)據(jù)庫在事

務(wù)異常終止后返回某個一致狀態(tài)。

4）安全

安全是保護數(shù)據(jù)免受非授權(quán)的泄露、更改或破壞。每個用

戶和應(yīng)用程序都有特定的數(shù)據(jù)訪問特權(quán)。這些過程中最常

用的是注冊名和口令保護服務(wù)。

數(shù)據(jù)庫管理系統(tǒng)

5）語言接口

提供對用于定義和操作數(shù)據(jù)的語言的支持。數(shù)據(jù)定義語言

用于描述數(shù)據(jù)、數(shù)據(jù)間聯(lián)系和對數(shù)據(jù)和聯(lián)系的約束的表示

法；數(shù)據(jù)操縱語言用于表達數(shù)據(jù)庫上的操作。

6）容錯性

不管發(fā)生什么故障仍能繼續(xù)提供可靠服務(wù)的能力稱為容錯

性?；謴?fù)與容錯性密切相關(guān)。

.數(shù)據(jù)庫管理系統(tǒng)

7）數(shù)據(jù)目錄

也稱數(shù)據(jù)字典，是一個系統(tǒng)數(shù)據(jù)庫，含有主數(shù)據(jù)庫中數(shù)據(jù)

的描述。

8）存儲管理

提供數(shù)據(jù)持久存儲的管理機制。

2.4軟件工程基礎(chǔ)

軟件與軟件危機

您什么是軟件軟件=程序？

@什么是軟件危機

軟件危機首次爆發(fā)于二十世紀(jì)六十年代。

在大型程序設(shè)計中，人們發(fā)現(xiàn)投入大量的

人力、物力、時間開發(fā)出的軟件，其成本、

效率、質(zhì)量等方面卻處于失控狀態(tài)，尤其

軟件維護異常困難。程序的修改擴充往往

需要大量重復(fù)性投入。

軟件與軟件危機

軟件危機產(chǎn)生的原因主要有三個:

口軟件開發(fā)者不熟悉用戶問題的領(lǐng)域，或沒有理解用戶

需求，軟件產(chǎn)品與要求不一致。

口軟件是一種邏輯產(chǎn)品而非物理產(chǎn)品，軟件的開發(fā)過程

本質(zhì)上是人的思考過程。

口人的智力在面對越來越復(fù)雜的問題時，處理問題的效

率會越來越低。

軟件工程

軟件危機的出現(xiàn)迫使人們重新認識軟

件和軟件開發(fā)過程。

大型軟件開發(fā)也應(yīng)該借鑒建筑、機械

等行業(yè)的發(fā)展過程，由“手工方式”

向“工程化”方向發(fā)展。1968年在北

大西洋公約組織(NATO)的年會上首次

提出軟件工程的概念，此后又逐步提

出軟件生命期的概念。

0軟件工程

O軟件工程的提出和軟件的定義

軟件是程序、方法、規(guī)則、相關(guān)文檔以及在計算機上運行

所必需的數(shù)據(jù)的集合。而軟件工程是開發(fā)、運行、維護軟件

的系統(tǒng)方法。

O軟件生命期

軟件生命期指從開始研制到廢棄不用的整個期間，可劃分

為五個階段：需求分析、設(shè)計、編程、測試和運行維護。

O軟件的質(zhì)量標(biāo)準(zhǔn)

F確性肄壯忤可維護忤

可用性可重用性效率等

y軟件工程

正確性

軟件的正確性指的是軟件系統(tǒng)在正

常條件下能夠正確工作，完成規(guī)定功能。

這是軟件的首要指標(biāo)。

例如，要求設(shè)計程序，輸入一批數(shù)據(jù),

計算它們的累加和。在這里，正確性就

是正確能正確計算累加和。

、■軟件工程

~r^

健壯性

軟件的健壯性指的是在意外情況下(如輸入數(shù)據(jù)不合理或

某些硬件故障)，軟件系統(tǒng)仍能適當(dāng)?shù)毓ぷ?，并對意外情況

進行適當(dāng)處理，而不致于導(dǎo)致錯誤結(jié)果甚至系統(tǒng)的癱瘓或死

機。

例如，要求設(shè)計程序，根據(jù)輸入的三邊a、b、c的長度判別

三角形類型?，F(xiàn)有如下設(shè)計思想：若a、b、c中只有兩個量相

等，則為等腰三角形，若三個量均相等，則為等邊三角形，

否則為一般三角形。如果輸入為(-2,-2,-2)時，程序輸

出為：等邊三角形。這個結(jié)果顯然是錯誤的。這是由于程序

對不合理數(shù)據(jù)不能進行適當(dāng)處理，我們就說這個程序的健壯

性不好。

軟件工程

可維護性

軟件的維護包括發(fā)現(xiàn)并改正軟件的錯誤，以

及由于軟件運行環(huán)境發(fā)生變化或軟件功能擴充

而對軟件進行的改動。

軟件的可維護性指的是軟件容易維護的程度。

一般地說，軟件的可讀性好，容易理解，維護

起來也就比較容易。因此可讀性是可維護性的

基礎(chǔ)。

軟件工程框架

軟件工程的目標(biāo)可以概括為“生產(chǎn)具有正確性、可用性

以及開銷合宜的產(chǎn)品”，其活動包括需求、設(shè)計、實現(xiàn)、

確認以及支持等活動，圍繞工程設(shè)計、支持以及管理，

有以下的四條基本原則：①選取適宜的開發(fā)模型；②采

用合適的設(shè)計方法；③提供高質(zhì)量的工程支持；④重視

開發(fā)過程的管理。

'I軟件工程框架

*軟件工程活動一需求分析

需求分析階段處于軟件開發(fā)的前期，其基本活動是準(zhǔn)確

定義未來系統(tǒng)的目標(biāo)，確定為了滿足用戶的需求必須做

什么。需求分析又劃分為兩個階段，即需求獲取和需求

規(guī)約，前者是用自然語言清楚地描述用戶的要求，而需

求規(guī)約的目的是消除獲取需求的二義性和不一致性。

建立需求面臨著以下三個方面的困難：①問題空間的理

解；②人與人之間的通信；③需求的不斷變化。面向?qū)?/p>

象的分析方法被認為是解決上述困難較好的技術(shù)。

*軟件工程活動-系統(tǒng)設(shè)計

需求分析階段的主要任務(wù)是確定系統(tǒng)“做什么”，而設(shè)

計階段則要解決“怎么做”的問題。

通常設(shè)計階段又劃分為總體設(shè)計和詳細設(shè)計，總體設(shè)計

確定系統(tǒng)的總體結(jié)構(gòu)框架；而詳細設(shè)計要具體地描述如

何具體地實現(xiàn)系統(tǒng)，通常可以依據(jù)詳細設(shè)計的結(jié)果進行

編碼。詳細設(shè)計包括：詳細的算法；數(shù)據(jù)表示和數(shù)據(jù)結(jié)

構(gòu)；實施的功能和使用數(shù)據(jù)之間的關(guān)系。

軟件工程活動一實現(xiàn)階段

在軟件實現(xiàn)階段，要將設(shè)計的結(jié)果變換成程序設(shè)計語言

編寫的程序。在實現(xiàn)階段，首先要確定程序設(shè)計語言，

其影響因素包括：開發(fā)人員對語言的熟悉程度，語言的

可移植性，編譯程序的效率，編譯工具的支持等等。目

前，C++語言是普遍被采用的構(gòu)造系統(tǒng)軟件的編程語言,

而Java則更多地應(yīng)用于編寫網(wǎng)絡(luò)程序。

無論采用哪一種編程語言，都要求編寫高質(zhì)量的源程序

代碼。

.軟件工程活動一確認活動

系統(tǒng)完成后的軟件測試是主要的確認活動。軟件測試是

指按照特定規(guī)程，發(fā)現(xiàn)軟件錯誤的過程。軟件測試的技

術(shù)大體上可以分為兩類，即白盒測試技術(shù)和黑盒測試技

術(shù)，前者依據(jù)的是程序邏輯結(jié)構(gòu)，后者依據(jù)的是軟件行

為描述。根據(jù)測試的步驟，測試活動又可以劃分為單元

測試，集成測試，確認測試和系統(tǒng)測試。

軟件工程活動一軟件維護

當(dāng)軟件開發(fā)完成并交付用戶使用后，就進入運行/維護階

段，在運行/維護階段仍需要對軟件進行修改，稱為軟件

維護。

軟件維護活動可以分為以下幾類：①正性維護；②適應(yīng)

性維護；③完善性維護；④預(yù)防性維護。

軟件工程活動一軟件維護

當(dāng)軟件開發(fā)完成并交付用戶使用后，就進入運行/維護階

段，在運行/維護階段仍需要對軟件進行修改，稱為軟件

維護。

軟件維護活動可以分為以下幾類：①正性維護；②適應(yīng)

性維護；③完善性維護；④預(yù)防性維護。

軟件開發(fā)過程模型

軟件開發(fā)模型是軟件開發(fā)全部過程、活動和任務(wù)的結(jié)構(gòu)框架。軟件

開發(fā)模型能夠清晰、直觀的表達軟件開發(fā)過程，明確規(guī)定要完成的

主要活動和任務(wù)，可以作為軟件項目工作的基礎(chǔ)。

主要模型有：

■瀑布模型一將各項活動規(guī)定為依照固定順序連接的若干階段工作,

形如瀑布流水

■演化模型一當(dāng)開發(fā)人員將核心需求實現(xiàn)后，用戶提出反饋意見，

以支持系統(tǒng)的最終設(shè)計和實現(xiàn)

-螺旋模型一在瀑布模型以及演化模型的基礎(chǔ)上，加入風(fēng)險分析所

建立的模型

-噴泉模型一體現(xiàn)了軟件開發(fā)過程中所固有的迭代和無間隙的特征

面向過程的程序開發(fā)方法

傳統(tǒng)的程序設(shè)計方法可以歸結(jié)為“程序=算法+數(shù)據(jù)結(jié)

構(gòu)”，將程序定義為處理數(shù)據(jù)的一系列過程。這種設(shè)計

方法的著眼點是面向過程的，特點是數(shù)據(jù)與程序分離，

即數(shù)據(jù)與數(shù)據(jù)處理分離。

結(jié)構(gòu)化程序設(shè)計的基本思想是采用自頂向下、逐步細化

的設(shè)計方法和單人單出的控制結(jié)構(gòu)。

程序

模塊1模塊2模塊3

1.22.12.2

1.3.11.3.21.3.33.1.13.1.2

舉一個簡單的例子，要求讀入一組整數(shù)，統(tǒng)計其中

正整數(shù)和負整數(shù)的個數(shù)。

該任務(wù)的模塊結(jié)構(gòu)及細化過程如下：

1.讀入數(shù)據(jù)

一正整數(shù)個數(shù)為0；負整數(shù)個數(shù)0

—取第一個整數(shù)

2.統(tǒng)計正數(shù)、負數(shù)

的個數(shù)；—重復(fù)j2.1如數(shù)大于0,正整數(shù)個數(shù)加1

至統(tǒng)/2.2如數(shù)小于0,負整數(shù)個數(shù)加1

3.輸出結(jié)果

I2.3:取下一個整數(shù)

這種設(shè)計方法的優(yōu)缺點在于：

?結(jié)構(gòu)化程序設(shè)計可以把一個較為復(fù)雜的程序設(shè)

計任務(wù)分解為許多易于控制和處理的子任務(wù)，

分塊解決，具有很大優(yōu)點。

?但它把數(shù)據(jù)和處理數(shù)據(jù)的過程分離開來，當(dāng)數(shù)

據(jù)結(jié)構(gòu)改變時，所有相關(guān)的處理數(shù)據(jù)過程都要

進行相應(yīng)的修改，程序的可重用性較差，對大

型程序設(shè)計很難適應(yīng)。

.面向?qū)ο蟮某绦蜷_發(fā)方法

-面向過程程序設(shè)計缺點的根源在于數(shù)據(jù)與數(shù)據(jù)處理分

離。

面向?qū)ο蟪绦蛟O(shè)計模擬自然界認識和處理事物的方法,

將數(shù)據(jù)和對數(shù)據(jù)的操作方法放在一起，形成一個相對獨

立的整體——對象(object),同類對象還可抽象出共

性，形成類(class)o一個類中的數(shù)據(jù)通常只能通過

本類提供的方法進行處理，這些方法成為該類與外部的

接口。對象之間通過消息(message)進行通訊。

念

寸1t

表針

旋鈕

其他機械機構(gòu)

調(diào)節(jié)旋鈕

基本輟念

-1

是一個抽象的概念，用來描述某一類對象所共

有的、本質(zhì)的屬性和行為。

類的一個具體實現(xiàn)，稱為實例

描述這類對象共有的、本質(zhì)的屬性和行為

具體到一只圓形的或方形的鬧鐘

鬧鐘共有的屬性（表針、旋鈕、內(nèi)部結(jié)構(gòu)）

和行為（調(diào)節(jié)旋鈕）

［寒有槐念

I

消息

我們把對象之間產(chǎn)生相互作用所傳遞的信息稱做消息。

計算機世

界

對象

類

對象、實體與類

“面向?qū)ο蟆睔{本開或清點

對象是一個封裝體，在其中封裝了該

對象的屬性和操作。通過限制對屬性和操

作的訪問權(quán)限，可以將屬性“隱藏”在對

動

機

讀

象內(nèi)部，對外提供一定的接口，在對象之調(diào)

作

表

械

外只能通過接口對對象進行操作。節(jié)

盤

旋

零

鈕

件

對象的獨立性

數(shù)據(jù)的可靠性

獨立模塊

“面向?qū)ο蟆睔埐砰_發(fā)特支

健宗鳥源金

面向?qū)ο蟪绦蛟O(shè)計提供了類似的機制:汽車

當(dāng)定義了一個類后，又需定義

一個新類，這個新類與原來的類客車貨車

相比，只是增加或修改了部分屬

性和操作，這時可以用原來的類

派生出新類，新類中只需描述自小轎車大客車

己所特有的屬性和操作。

新類稱為子類或派生類，原來的類稱為基類。派生可以一直

進行下去，形成一個派生樹。

“面向?qū)ο蟆惫鸶裢饣蚯蹇?/p>

多態(tài)性指，同一個消息被不同對象接收時,

產(chǎn)生不同結(jié)果，即實現(xiàn)同一接口，不同方法。

計算大學(xué)生高數(shù)、英語、計算機、線

平均成績性代數(shù)

“面向?qū)ο蟆睆姳鹃_或清點

繼承和多態(tài)性組合，可以生成很多相

似但又獨一無二的對象。繼承性使得這

些對象可以共享許多相似特性，而多態(tài)

又使同一個操作對不同對象產(chǎn)生不同表

現(xiàn)形式。這樣不僅提高了程序設(shè)計的靈

活性，而且減輕了分別設(shè)計的負擔(dān)。

I.面向?qū)ο蟮某绦蜷_發(fā)過程

面向?qū)ο筌浖_發(fā)的根本合理性在于它符

合客觀世界的組成方式和大腦的思維方式。

在大型程序開發(fā)過程中，編碼只是其中很

小一部分，應(yīng)當(dāng)采用工程化的方法，并將面

向?qū)ο蟮乃枷胴灤┯谲浖_發(fā)全過程，這就

是面向?qū)ο蟮能浖こ獭?/p>

面相對象的軟件工程同樣遵循分層抽象、

逐步細化的原則。軟件開發(fā)過程包括以下五

個階段：分析、設(shè)計、編程、測試和維護

面向?qū)ο蟮某绦蜷_發(fā)過程一1

面向?qū)ο蟮姆治觯簭膯栴}的陳述開始，逐步建立起客觀

事物的模型，分析模型中的對象，使得對象的描述與客

觀事物相一致。相同特性的對象為一類，一般類和特殊

類之間有繼承關(guān)系。

面向?qū)ο蟮脑O(shè)計：主要是把在面向?qū)ο蠓治鲭A段建立的

模型，用面向?qū)ο蟮姆椒óa(chǎn)生一個具體實現(xiàn)。包括：把

面向?qū)ο蟮姆治瞿Ｐ椭苯拥矫嫦驅(qū)ο蟮脑O(shè)計作為面向?qū)?/p>

象設(shè)計的一部分；針對具體實現(xiàn)中的人機界面、數(shù)據(jù)存

儲、任務(wù)管理等因素補充一些與實現(xiàn)有關(guān)的部分。

面向?qū)ο蟮某绦蜷_發(fā)過程一2

面向?qū)ο蟮木幊蹋壕幊淌敲嫦驅(qū)ο蟮能浖_發(fā)最終落實

的重要階段。它主要是要用面向?qū)ο蟮恼Z言實現(xiàn)面向?qū)?/p>

象設(shè)計方案中的每個成員。

面向?qū)ο蟮恼{(diào)試：調(diào)試的任務(wù)是發(fā)現(xiàn)軟件中的錯誤。以

對象的類作為一個基本測試單位，查錯范圍是類定義之

內(nèi)的屬性和服務(wù)以及接口所涉及的部分。這樣可以更準(zhǔn)

確地發(fā)現(xiàn)錯誤，提高測試效率。

面向?qū)ο蟮木S護：軟件作為一件產(chǎn)品，無論經(jīng)過多么嚴(yán)

格的測試，總還會存在一些錯誤。所以，軟件的維護是

不能省略和停止的。

2.5新技術(shù)趨勢

人工智能

■專家系統(tǒng)是人工智能研究中的一個重要方面。

專家系統(tǒng)與CAD技術(shù)的結(jié)合，形成設(shè)計型的專

家系統(tǒng)，又稱為智能化CAD。

■在交通CAE領(lǐng)域中，人工智能和專家系統(tǒng)的應(yīng)

用已成為研究的熱點，但要真正能投入實際應(yīng)

用，尚有很多工作要做。國內(nèi)曾對公路選線專

家系統(tǒng)以及用專家系統(tǒng)的方法改進道路CAD系

統(tǒng)方面做過探索性研究。

數(shù)據(jù)挖掘

個于專家系統(tǒng)工具過分依賴用戶或?qū)＜胰斯?/p>

地將知識輸入知識庫中，而且分析結(jié)果往往

帶有偏差和錯誤，再加上耗時、費用高，故

不可行。

■產(chǎn)生了一個新的研究方向

■基于數(shù)據(jù)庫的知識發(fā)現(xiàn)(KnowledgeDiscovery

inDatabase),以及相應(yīng)的數(shù)據(jù)挖梅(Data

Mining)理論和技術(shù)的研究

數(shù)據(jù)挖掘工具

數(shù)據(jù)礦山信息金塊

in州』帆Utubtss

1988199019952004

ExpertSystemsExpertSystems

數(shù)據(jù)挖掘是多學(xué)科的產(chǎn)物

、KDD已經(jīng)成為人工智能研究熱點

■目前，關(guān)于KDD的研究工作已經(jīng)被眾多

領(lǐng)域所關(guān)注，如過程控制、信息管理、

商業(yè)、醫(yī)療、金融等領(lǐng)域。

■作為大規(guī)模數(shù)據(jù)庫中先進的數(shù)據(jù)分析工

具，KDD的研究已經(jīng)成為數(shù)據(jù)庫及人工

智能領(lǐng)域研究的一個熱點。

數(shù)據(jù)挖掘算法

?支持向量機

?決策樹學(xué)習(xí)

?Bayes分類

?聚類

?主分量分析方法

?人工神經(jīng)網(wǎng)絡(luò)

?EM算法

?模糊邏輯

?智能優(yōu)化

機器學(xué)習(xí)

-人工智能目前的研究熱點是機器學(xué)習(xí)。機器學(xué)習(xí)是一

種使獲取知識自動化的計算方法的學(xué)習(xí)。機器學(xué)習(xí)在

人工智能的研究中具有十分重要的地位。其應(yīng)用已遍

及人工智能的各個分支，如專家系統(tǒng)、自動推理、自

然語言理解、模式識別、計算機視覺、智能機器人等

領(lǐng)域。

-機器學(xué)習(xí)方法

■特征選擇

■分類方法

■決策樹

■人工神經(jīng)網(wǎng)絡(luò)與遺傳算法

■支持向量機

■圖論與聚類方法

網(wǎng)格技術(shù)

■網(wǎng)格(Grid)概念源于電力公用網(wǎng)，其基本思想是

使用戶在應(yīng)用網(wǎng)格技術(shù)時，就像日常生活從電

力網(wǎng)中獲取電能那樣，可以方便地獲取網(wǎng)絡(luò)上

高性能的計算能力。根據(jù)Foster和Kesselman

的定義，網(wǎng)格是構(gòu)筑在互聯(lián)網(wǎng)上的一組新興技

術(shù)，它將高速互聯(lián)網(wǎng)、計算機、大型數(shù)據(jù)庫、

傳感器、遠程設(shè)備等融為一體，為科技人員和

普通老百姓提供更多的資源、功能和服務(wù)。

網(wǎng)格的概念

網(wǎng)格計算

■網(wǎng)格計算(Gridcomputing)是利用互聯(lián)網(wǎng)

技術(shù)，把分散在不同地理位置的計算機

組成一臺虛擬超級計算機。

IBM的網(wǎng)格遠景：現(xiàn)在的計算機

Storage

___Applications

未來：因特網(wǎng)是計算機！

TheInternetasaComputingPlatform

Data

n--------

?優(yōu)勢：計算能力強，費用低

在實質(zhì)上來說“網(wǎng)格計算”是一種分布式應(yīng)用,

網(wǎng)