二級(jí)共公基礎(chǔ)知識(shí)教程

第?章數(shù)據(jù)構(gòu)造與算法

1.1算法

算法：是指解題方案的精確而完整的描述。

算法不等于程序，也不等計(jì)算機(jī)措施，程序的編制不也許優(yōu)于算法的設(shè)計(jì)。

算法的基本特性：是一組叫謹(jǐn)?shù)囟x運(yùn)算次序的規(guī)則，每一種規(guī)則都是有效的，是明確的，

本次序?qū)⒃谟邢薜拇螖?shù)下終止。特性包括：

（1）可行性；

（2）確定性，算法中每一環(huán)節(jié)都必須有明確定義，不充許有模棱兩可的解釋?zhuān)蝗菰S有多

義性；

（3）有窮性，算法必須能在有限的時(shí)間內(nèi)做完，即能在執(zhí)行有限個(gè)環(huán)節(jié)后終止，包括合理

的執(zhí)行時(shí)間的含義；

（4）擁有足夠的情報(bào)。

算法的基本要素：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；二是算法的控制構(gòu)造。

指令系統(tǒng)：一種計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合。

基本運(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳播。

算法的控制構(gòu)造；次序構(gòu)造、選擇構(gòu)造、循環(huán)構(gòu)造。

算法基本設(shè)計(jì)措施：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。

算法復(fù)雜度：算法時(shí)間復(fù)雜度和算法空間復(fù)雜度。

算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。

算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。

1.2數(shù)據(jù)構(gòu)造的基本基本概念

數(shù)據(jù)構(gòu)造研究的三個(gè)方面：

（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯構(gòu)造；

（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)構(gòu)造：

（3）對(duì)多種數(shù)據(jù)構(gòu)造進(jìn)行的運(yùn)算。

數(shù)據(jù)構(gòu)造是指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

數(shù)據(jù)的邏輯構(gòu)造包括：

（1）表達(dá)數(shù)據(jù)元素的信息；

（2）表達(dá)各數(shù)據(jù)元素之間的前后件關(guān)系。

數(shù)據(jù)的存儲(chǔ)構(gòu)造有次序、族接、索引等。

線(xiàn)性構(gòu)造條件：

（1）有且只有一種根結(jié)點(diǎn)；

（2）每一種結(jié)點(diǎn)最多有一種前件，也最多有一種后件。

非線(xiàn)性構(gòu)造：不滿(mǎn)足線(xiàn)性構(gòu)造條件的數(shù)據(jù)構(gòu)造。

1.3線(xiàn)性表及另一方面序存儲(chǔ)構(gòu)造

線(xiàn)性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是

線(xiàn)性的。

在復(fù)雜線(xiàn)性表中，由若干項(xiàng)數(shù)據(jù)元素構(gòu)成的數(shù)據(jù)元素稱(chēng)為記錄，而由多種記錄構(gòu)成的線(xiàn)性表

又稱(chēng)為文獻(xiàn)。

非空線(xiàn)性表的構(gòu)造特性：

（1）且只有一種根結(jié)點(diǎn)al,它無(wú)前件；

（2）有且只有一種終端結(jié)點(diǎn)an,它無(wú)后件：

（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一種前件，也有且只有一種后件。結(jié)

點(diǎn)個(gè)數(shù)n稱(chēng)為線(xiàn)性表的長(zhǎng).度，當(dāng)『0時(shí)，稱(chēng)為空表。

線(xiàn)性表的次序存儲(chǔ)構(gòu)造具有如下兩個(gè)基本特點(diǎn)：

（1）線(xiàn)性表中所有元素的所占的存儲(chǔ)空間是持續(xù)的；

（2）線(xiàn)性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯次序依次寄存的。

ai的存儲(chǔ)地址為：ADR（ai）=ADR（al）+（i-l）k?ADR（al）為第一種元素的地址，k代表每個(gè)元

素占的字節(jié)數(shù)。

次序表的運(yùn)算：插入、刪除。（詳見(jiàn)I4--16頁(yè)）

1.4棧和隊(duì)列

棧是限定在一端進(jìn)行插入與刪除的線(xiàn)性表，容許插入與刪除的一端稱(chēng)為棧頂，不容許插入與

刪除的另一端稱(chēng)為棧底。

棧按照“先進(jìn)后出“（FILO）或“后進(jìn)先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。用top表達(dá)

棧頂位.置.，用bottom表達(dá)棧底。

棧的基本運(yùn)算：（1）插入元素稱(chēng)為入棧運(yùn)算；（2）刪除元素稱(chēng)為退棧運(yùn)算；（3）讀棧頂元素

是將棧頂元素賦給一種指定的變量，此時(shí)指針無(wú)變化。

隊(duì)列是指容許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線(xiàn)性表。Rear指

針指向隊(duì)尾，front指針指向隊(duì)頭。

隊(duì)列是“先進(jìn)行出"（HFO）或“后進(jìn)后出”（LILO）的線(xiàn)性表。

隊(duì)列運(yùn)算包括（1）入隊(duì)運(yùn)算：從隊(duì)尾插入一種元素；（2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一種元素。

循環(huán)隊(duì)列：s=0表達(dá)隊(duì)列空，s=l且front=rear表達(dá)隊(duì)列滿(mǎn)

1.5線(xiàn)性鏈表

數(shù)據(jù)構(gòu)造中的每一種結(jié)點(diǎn)對(duì)應(yīng)于一種存儲(chǔ)單元，這種存儲(chǔ)單元稱(chēng)為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱(chēng)結(jié)點(diǎn)。

結(jié)點(diǎn)由兩部分構(gòu)成：（1）用于存儲(chǔ)數(shù)據(jù)元素值，稱(chēng)為數(shù)據(jù)域；（2）用于寄存指針，稱(chēng)為指針

域，用于指向前一種或后一種結(jié)點(diǎn)。

在鏈?zhǔn)酱鎯?chǔ)構(gòu)造中，存儲(chǔ)數(shù)據(jù)構(gòu)造的存儲(chǔ)空間可以不持續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)次序與數(shù)據(jù)元

素之間的邏輯關(guān)系可以不-?致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。

鏈?zhǔn)酱鎯?chǔ)方式即可用于表達(dá)線(xiàn)性構(gòu)造，也可用于表達(dá)非線(xiàn)性構(gòu)造。

線(xiàn)性鏈表，HEAD稱(chēng)為頭指針，HEAD二NULL（或0）稱(chēng)為空表，假如是兩指針：左指針（Llink）

指向前件結(jié)點(diǎn)，右指針（Rlink）指向后件結(jié)點(diǎn)。

線(xiàn)性鏈表的基本運(yùn)算：查找、插入、刪除。

1.6樹(shù)與二叉樹(shù)

一、樹(shù)的基本概念

在樹(shù)構(gòu)造中，每一種結(jié)點(diǎn)只有一種前件，稱(chēng)為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一種，稱(chēng)為樹(shù)的

根結(jié)點(diǎn)，簡(jiǎn)稱(chēng)為樹(shù)的根。

在樹(shù)構(gòu)造中，每一種結(jié)點(diǎn)可以有多種后件，它們都稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱(chēng)

為葉子結(jié)點(diǎn)。

在樹(shù)構(gòu)造中，一種結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。

葉子結(jié)點(diǎn)的度為0。

樹(shù)的最大層次稱(chēng)為樹(shù)的深度。

在一種算術(shù)體現(xiàn)式中，有運(yùn)算符和運(yùn)算對(duì)象。一種運(yùn)算符可以有若干個(gè)運(yùn)算對(duì)象。例職，取

正（+）等只有一種運(yùn)算對(duì)象，稱(chēng)為單目運(yùn)算符：二個(gè)運(yùn)算對(duì)象稱(chēng)為雙目運(yùn)算符，三目運(yùn)算

符。

用樹(shù)來(lái)表達(dá)算術(shù)體現(xiàn)式的原則如下：

體現(xiàn)式中的每一種運(yùn)算符在樹(shù)中對(duì)應(yīng)一種結(jié)點(diǎn)，稱(chēng)為運(yùn)算符結(jié)點(diǎn)。

運(yùn)算符的每一種運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù)（在樹(shù)中的次序?yàn)閺淖蟮接遥?/p>

運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。

二、二叉樹(shù)及其基本性質(zhì)

1、什么是二叉樹(shù)

二叉樹(shù)是i種很有用的非線(xiàn)性構(gòu)造。二就樹(shù)具有如下兩個(gè)特點(diǎn)：

非空二叉樹(shù)只有一種根結(jié)點(diǎn)；

每一種結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。

由以上特點(diǎn)可以看出，在二叉樹(shù)中，每一種結(jié)點(diǎn)的度最大為2,即所有子樹(shù)（左子樹(shù)或右子

樹(shù)）也均為二叉樹(shù)，而樹(shù)構(gòu)造中的每一種結(jié)點(diǎn)的度可以是任意的。此外，二叉樹(shù)中的福一種

結(jié)點(diǎn)的子樹(shù)被明顯地分為左子樹(shù)與右子樹(shù)?？梢詻](méi)有其中的一-種，也可以全沒(méi)有。

二叉樹(shù)的基本性質(zhì)

性質(zhì)1：在二叉樹(shù)的第K層上，最多有（KN1）個(gè)結(jié)點(diǎn)。

性質(zhì)2：濃度為M的二叉樹(shù)最多有2m-l個(gè)結(jié)點(diǎn)。

深度為m的二叉樹(shù)是指二叉樹(shù)共有m層。

性質(zhì)3：在任意一棵二叉樹(shù)中度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一和。

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為［log2n］+l,其中［Iog2n］表達(dá)取的整數(shù)部分。

滿(mǎn)二叉樹(shù)與完全二叉樹(shù)

滿(mǎn)二叉樹(shù)與完全二義樹(shù)是兩種特殊形態(tài)的二叉樹(shù)。

滿(mǎn)二叉樹(shù)

所謂滿(mǎn)二叉樹(shù)是指這樣的一種二叉樹(shù);除最終一層外，每一層上的所有結(jié)點(diǎn)均有兩個(gè)子結(jié)點(diǎn)。

這就是說(shuō)，在滿(mǎn)二叉樹(shù)中，每一層上的結(jié)點(diǎn)數(shù)都到達(dá)最大值，即在滿(mǎn)二叉樹(shù)的第K層上有

2K-I個(gè)結(jié)點(diǎn)，且深度為m的滿(mǎn)二叉樹(shù)有2m-l個(gè)結(jié)點(diǎn)。

完全二叉樹(shù)

所謂完全二叉樹(shù)是指這樣的二叉樹(shù)，除最終一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)的最大值；在最

終一層上只缺乏右邊的若干結(jié)點(diǎn)。

列確切地說(shuō)，假如從根結(jié)點(diǎn)起，對(duì)二叉樹(shù)的結(jié)點(diǎn)自上而限自左至右用自然數(shù)進(jìn)行邊疆編號(hào),

則深度為m、且有n個(gè)結(jié)點(diǎn)的一又樹(shù)，當(dāng)且僅當(dāng)其每一種結(jié)點(diǎn)都與深度為m的滿(mǎn)一叉樹(shù)中

編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱(chēng)之為完全二叉樹(shù)。

對(duì)于完全二叉樹(shù)來(lái)說(shuō)，葉子結(jié)點(diǎn)只也許在層次最大的兩層上出現(xiàn)；對(duì)于?任何一種結(jié)點(diǎn)，若其

右分支下的子孫結(jié)點(diǎn)的最大層次為P，則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)镻，或?yàn)镻+1。

由滿(mǎn)二叉樹(shù)與完全二叉樹(shù)的特點(diǎn)可以看出，滿(mǎn)二叉樹(shù)也是完全二叉樹(shù)，而完全二叉樹(shù)一般不

是滿(mǎn)二叉樹(shù)。

完全二叉樹(shù)還具有如下兩個(gè)性質(zhì)：

性質(zhì)5：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為［log2n］+l.

性質(zhì)6：設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。假如從根結(jié)點(diǎn)開(kāi)始，按層序（每一層從左到右）用自

然數(shù)1,2,n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k（k=l,2,...n）的結(jié)點(diǎn)有如下結(jié)論：

若k=l,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k>l,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT（k，2）。

若2k'n,則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（顯然也沒(méi)有

右子結(jié)點(diǎn)）。

若2k+l$,則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+l：否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。

三、二叉樹(shù)的存儲(chǔ)構(gòu)造

二叉樹(shù)的遍歷

二叉樹(shù)的遍歷是指不反復(fù)地訪(fǎng)問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。

在遍歷二叉樹(shù)的過(guò)程中，一般先遍歷左子樹(shù)，然后再遍歷右子樹(shù)。

值

然后，從后到前掃描剩余的線(xiàn)性表，同樣，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若

相鄰兩個(gè)元素中，背面的元素不小于前面的元素，則將它們互換，這樣就又消去了?種逆序。

放最小值。

反復(fù)上述過(guò)程，直到剩余的線(xiàn)性有變空為止，此時(shí)的線(xiàn)性表已經(jīng)變?yōu)橛行颉?/p>

假設(shè)線(xiàn)性表的長(zhǎng)為n,則在最壞狀況下，冒泡排序需要通過(guò)n/2遍的蔥馨往后的掃描和n/2

遍的從后往前的掃描，需要的比較的次數(shù)為n(n-l)/2o

2、迅速排序法

迅速排序法也是種互換類(lèi)的排序法，但由于它比冒泡排序法的速度快，因此稱(chēng)之為迅速排序

法。

基本思想如下：

從線(xiàn)性表中選用一種元素，設(shè)T,將線(xiàn)性表背面不不小于T的元素移到前，而前不小于T

的元素移支背面，成果就將線(xiàn)性表提成了兩部分(稱(chēng)為兩個(gè)子表)，T插入到其分界線(xiàn)的位

置處，這個(gè)過(guò)程稱(chēng)為線(xiàn)性表的分割。通過(guò)對(duì)線(xiàn)性表的一次分割，就以T為分界線(xiàn)，相線(xiàn)性

表提成了前后兩個(gè)子表，旦前面子表中的所有元素均不不小于T,而背面子表中的所有元素

均不不不小于T。

如此反復(fù)，則此時(shí)的線(xiàn)性表就變成了有序表。

環(huán)節(jié)：首先，在表的第一種，中間一種與最終一種元素中選用中項(xiàng)，設(shè)為P(K),并將P

(K)賦給T,再將表中的第一種元素移到P(K)的位置上。

然后設(shè)置兩個(gè)指針i和j分別指向表的起始與最終的位置。反復(fù)操作如下兩步：

(4)將j逐漸減小，并逐次比較P(j)與T,直到發(fā)現(xiàn)一種P(j)<T為止，將P(j)

移到P①位置上。

(5)將i逐漸減小，并逐次比較P(i)與T,直到發(fā)現(xiàn)一種P(i)>T為止，將P(i)

移到P(j)位置上。

上述兩個(gè)操作交替進(jìn)行，直到指針i與j指向同一種位置(即i=j)為止，此時(shí)將P(i)的位置

上。

分割需要記憶，用棧來(lái)實(shí)現(xiàn)。

二、插入類(lèi)排序法

I、簡(jiǎn)樸插入排序法

所謂插入排序，是指將無(wú)序序列中的各元素依次插入到己經(jīng)有序的線(xiàn)性表中。

一般來(lái)說(shuō)，假設(shè)線(xiàn)性中前j-1元素已經(jīng)有序，目前要將線(xiàn)性表中第j個(gè)元素插入到前面的有

序子表中，插入過(guò)程如下：

道德將第j個(gè)元素放到一種變量T中，然后從有序子表的最終一種元素(即線(xiàn)性表中第j-1

個(gè)元素)開(kāi)始，往前逐一與T進(jìn)行比較，將不小于T的元素均依次向后移動(dòng)一種位置，直

到發(fā)現(xiàn)一種元素不不小于T為止，此時(shí)就將T(即原線(xiàn)性表中的第j個(gè)元素)插入到夙移出

的空位置上，有序子表的長(zhǎng)度就變?yōu)閖了。效率與冒泡法相似

在最壞狀況下，簡(jiǎn)樸插入排序需要n(n-l)/2次比較。

2、希爾排序法

基本思想如下：

將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。

子序列的分割措施如下：

將相隔某個(gè)增量H的元素構(gòu)成?種子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最終當(dāng)H

減到1時(shí)，進(jìn)行一次插入排序，排序就完畢。增量序列一般取h=n/2k(k=l,2,...[k)g2n],其中n

為待排序序列的長(zhǎng)度。

其效率與增量序列有關(guān)。在最壞狀況下，需要的比較次數(shù)為O（N1.5）。

三、選擇類(lèi)排序法

1、簡(jiǎn)樸選擇排序法

基本思想：掃描整個(gè)線(xiàn)性表，從中選出最小的元素，將它互換到表的最前面；然后對(duì)剩余的

子表采用同樣的措施，直到子表空為止。

簡(jiǎn)樸選擇排序法在最壞狀況下需要比較n（n-l）/2/次。

2、堆排序法

措施：（I）首先將一種無(wú)序序列建成堆。

（2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最終一種元素互換（最大項(xiàng)應(yīng)當(dāng)在序列的

最終）。不考慮已經(jīng)換到最終的那個(gè)元素，只考慮前n-1個(gè)元素構(gòu)成的子序，顯然，該子序

列已不是堆，但左、右子樹(shù)仍為堆，可以將該子序列調(diào)事為堆。反復(fù)做第（2）步，真到剩

余的子序列為空為止。合用規(guī)模較大的線(xiàn)性表，在最壞狀況下，堆排序需要比較的次數(shù)為0

（nlog2n）。

1.7查找技術(shù)

一、次序查找

次序查找又稱(chēng)次序搜索。次序查找一般是指在線(xiàn)性表中查找指定的元素，其基本措施如下：

從線(xiàn)性表的第一種元素開(kāi)始，依次將線(xiàn)性表中的元素與被查元素進(jìn)行比較，若相等則表達(dá)找

到（即杳找成功）；若線(xiàn)性表中所有的元素都與被杳元素進(jìn)行了比較但都不相等，則表達(dá)線(xiàn)

性表中沒(méi)有要找的元素（即查找失?。?/p>

次序查找的效率是很低的，如下兩種狀況只能采用次序查找：

假如線(xiàn)性表無(wú)序表（即表中元素的排列是無(wú)序的），則不管是次序存儲(chǔ)構(gòu)造還是鏈?zhǔn)酱鎯?chǔ)構(gòu)

造，都只能用次序查找。

雖然是有序線(xiàn)性表，假如采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造，也只能用次序查找。

二、二分法查找

二分法查找只合用于存儲(chǔ)的有序表。在此所說(shuō)的有序表是指線(xiàn)性表的中元素按值非遞減排列

（即從小到大，但容許相鄰元素值相等）。

設(shè)有序線(xiàn)性表的長(zhǎng)度為n,被有元素為x,則對(duì)分查找的措施如下：

將x與線(xiàn)性表的中間項(xiàng)進(jìn)行比較：

若中間項(xiàng)的值等于x,則闡明查到，查找結(jié)束；

若x不不小于中間項(xiàng)的值，則在線(xiàn)性表的前半部分（即中間項(xiàng)此前的部分）以相似的措施進(jìn)

行查找；

若x不小于中間項(xiàng)的值，則在線(xiàn)性表的后半部分（即中間項(xiàng)后來(lái)的部分）以相似的措施進(jìn)行

查找。

這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0（闡明線(xiàn)性表中沒(méi)有這個(gè)元素）為止。

顯然，當(dāng)有序線(xiàn)性表為次序存儲(chǔ)時(shí)才能采用二分查找，并且，二分查找的效率要比次序查找

高得多?？梢宰C明，對(duì)于長(zhǎng)度為n的有序線(xiàn)性表，在最壞狀況下，二分查找只需要比較log2n

次，而次序查找需要比較n次。

1.8排序技術(shù)

一、互換類(lèi)排隊(duì)序法

所謂互換類(lèi)排序法是指借助數(shù)據(jù)元素之間的互相互換進(jìn),亍排序的一種措施。冒泡排序法與迅

速排序法都屬于互換類(lèi)的排序措施。

1、冒泡排序法

基本過(guò)程如下：

首先，從表頭開(kāi)始往后掃描線(xiàn)性表，在掃描過(guò)程中逐次匕較相鄰兩個(gè)元素的大小。若相鄰兩

個(gè)元素中，前面的元素不小于背面的元素，則將它們互換，稱(chēng)之為消去了一種逆序。放最大

值

然后，從后到前掃描剩余的線(xiàn)性表，同樣，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若

相鄰兩個(gè)元素中，背面的元素不小于前面的元素，則將它們互換，這樣就乂消去了一種逆序。

放最小值。

反復(fù)上述過(guò)程，直到剩余的線(xiàn)性有變空為止，此時(shí)的線(xiàn)性表已經(jīng)變?yōu)橛行颉?/p>

假設(shè)線(xiàn)性表的長(zhǎng)為n,則在最壞狀況下，冒泡排序需要通過(guò)n/2遍的蔥馨往后的掃描和n/2

遍的從后往前的掃描，需要的比較的次數(shù)為n(n-l)/2o

2、迅速排序法

迅速排序法也是種互換類(lèi)的排序法，但由于它比冒泡排序法的速度快，因此稱(chēng)之為迅速排序

法。

基本思想如下：

從線(xiàn)性表中選用一種元素，設(shè)T,將線(xiàn)性表背面不不小于T的元素移到前，而前不小于T

的元素移支背面，成果就將線(xiàn)性表提成了兩部分(稱(chēng)為兩個(gè)子表)，T插入到其分界線(xiàn)的位

置處，這個(gè)過(guò)程稱(chēng)為線(xiàn)性表的分割。通過(guò)對(duì)線(xiàn)性表的一次分割，就以T為分界線(xiàn)，招線(xiàn)性

表提成了前后兩個(gè)子表，且前面子表中的所有元素均不不小于T,而背面子表中的所有元素

均不不不小于T。

如此反復(fù)，則此時(shí)的線(xiàn)性表就變成了有樣表。

環(huán)節(jié)：首先，在表的第一-種，中間一種與最終一種元素中選用中項(xiàng)，設(shè)為P(K),并將P

(K)賦給T,再將表中的第一種元素移到P(K)的位置上。

然后設(shè)置兩個(gè)指針i和j分別指向表的起始與最終的位置。反復(fù)操作如下兩步：

(4)將j逐漸減小，并逐次比較P(j)與T,直到發(fā)現(xiàn)一種P(j)<T為止，將P(j)

移到P(i)位置上。

(5)將i逐漸減小，并逐次比較P(i)與T,直到發(fā)現(xiàn)一種P(i)>T為止，將P(i)

移到P(j)位置上。

上述兩個(gè)操作交替進(jìn)行，直到指針i與j指向同一種位置(即i=j)為止，此時(shí)將P(i)的位置

上。

分割需要記憶，用棧來(lái)實(shí)現(xiàn)。

二、插入類(lèi)排序法

1、簡(jiǎn)樸插入排序法

所謂插入排序，是指將無(wú).序序列中的各元素依次插入到已經(jīng)有序的線(xiàn)性表中。

一般來(lái)說(shuō)，假設(shè)線(xiàn)性中前j-1元素已經(jīng)有序，目前要將線(xiàn)性表中第j個(gè)元素插入到前面的有

序子表中，插入過(guò)程如下：

道德將第j個(gè)元素放到一種變量T中，然后從有序子表的最終一種元素(即線(xiàn)性表中第j-1

個(gè)元素)開(kāi)始，往前逐一與T進(jìn)行比較，將不小于T的元素均依次向后移動(dòng)一種位置，直

到發(fā)現(xiàn)一種元素不不小于T為止，此時(shí)就將T(即原線(xiàn)性表中的第j個(gè)元素)插入到即移出

的空位置上，有序子表的長(zhǎng)度就變?yōu)閖了。效率與冒泡法相似

在最壞狀況下，簡(jiǎn)樸插入排序需要n(n-l)/2次比較。

2、希爾排序法

基本思想如下：

將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。

子序列的分割措施如下：

將相隔某個(gè)增量H的元素構(gòu)成一種子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最終當(dāng)H

減至lj1時(shí)，進(jìn)行一次插入排序，排序就完畢。增量序列一般取h=n/2k(k=l,2，…[log2n],其中n

為待排序序列的長(zhǎng)度。

其效率與增量序列有關(guān)。在最壞狀況下，需要的比較次數(shù)為O（N1.5）。

三、選擇類(lèi)排序法

1、簡(jiǎn)樸選擇排序法

基本思想：掃描整個(gè)線(xiàn)性表，從中選出最小的元素，將它互換到表的最前面；然后對(duì)剩余的

子表采用同樣的措施，直到子表空為止。

簡(jiǎn)樸選擇排序法在最壞狀況下需要比較n（n-l）/2/次。

2、堆排序法

措施：（1）首先將一種無(wú)序序列建成堆。

（2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最終一種元素互換（最大項(xiàng)應(yīng)當(dāng)在序列的

最終）。不考慮已經(jīng)換到最終的那個(gè)元素，只考慮前n-l個(gè)元素構(gòu)成的子序，顯然，該子序

列已不是堆，但左、右子樹(shù)仍為堆，可以將該子序列調(diào)事為堆。反復(fù)做第（2）步，真到剩

余的子序列為空為止。合用規(guī)模較大的線(xiàn)性表，在最壞狀況下，堆排序需要比較的次數(shù)為0

(nlog2n)o

習(xí)題一

一、選擇題

1、算法的時(shí)間復(fù)雜度是指（)

A）執(zhí)行算法程序所需要的時(shí)間D）算法程序的長(zhǎng)度

C）算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)D）算法程序中的指令條數(shù)

2、算法的害復(fù)雜度是指〔）

A、算法程序的長(zhǎng)度B、算法程序中的指令條數(shù)

C、算法程序所占的存儲(chǔ)空間D、算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間

3、下列論述中對(duì)的的是

A、線(xiàn)性表是線(xiàn)性構(gòu)造B、材與隊(duì)列是非線(xiàn)性構(gòu)造

C、線(xiàn)性鏈表是非線(xiàn)性構(gòu)造D、二又樹(shù)是線(xiàn)性構(gòu)造

4、數(shù)據(jù)的存儲(chǔ)構(gòu)造是指）

A、數(shù)據(jù)所占的存儲(chǔ)空間量B、數(shù)據(jù)的邏輯構(gòu)造在計(jì)算機(jī)中的表

達(dá)

C、數(shù)據(jù)在計(jì)算機(jī)中的次序存儲(chǔ)方式D、存儲(chǔ)在外存中的數(shù)據(jù)

5、下列有關(guān)隊(duì)列的論述中對(duì)的的是（）

A、在隊(duì)列中只能插入數(shù)據(jù)B、在隊(duì)列中只能刪除數(shù)據(jù)

C、隊(duì)列是先進(jìn)先出的線(xiàn)性表D、隊(duì)列是先進(jìn)后出的線(xiàn)性表

6、下列有關(guān)棧的論述中對(duì)的的是（）

A、在棧中只能插入數(shù)據(jù)B、在棧中只能刪除數(shù)據(jù)

C、棧是先進(jìn)先出的線(xiàn)性表D、棧是先進(jìn)后出的線(xiàn)性表

7、設(shè)有下列二叉樹(shù)：

對(duì)此二叉樹(shù)中序遍歷的成果為

A、ABCDEFB、DBEAFCC、ABDECF

D、DEBFCA

8、在深度為5的滿(mǎn)二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（）

A、32B、31C、16

D、15

9、對(duì)長(zhǎng)度為n的線(xiàn)性表進(jìn)行次序查找，在最壞狀況下所需要的比較次數(shù)為

（）

A、n+lB、nC、（n+l）/2

D、n/2

10、設(shè)樹(shù)T的度為4,其中度為1,2,3,4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1。則T中的葉子

結(jié)點(diǎn)數(shù)為（）

A、8B、7C、6

D、5

二、填空題

1、在長(zhǎng)度為n的有序線(xiàn)性表中進(jìn)行二分查找，需要的比較次數(shù)為。

2、設(shè)一棵完全二叉共有700個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中有個(gè)葉子結(jié)點(diǎn)。

3、設(shè)一-棵二叉樹(shù)中序遍歷成果為DBEAFC,前序遍歷成果為ABDECF,則后序遍歷成果

為。

4、在最壞狀況下，冒泡排序的時(shí)間復(fù)雜度為。

5、在一種容量為15的循環(huán)隊(duì)列中，若頭指針front=6,尾指針rear=9,則該循環(huán)隊(duì)列中共

有個(gè)元

第2章程序設(shè)計(jì)基礎(chǔ)

2.1程序設(shè)計(jì)措施與風(fēng)格

就程序設(shè)計(jì)措施和技術(shù)的發(fā)展而言，重要通過(guò)了構(gòu)造化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階

段。

一般來(lái)講。程序設(shè)計(jì)風(fēng)格是指編寫(xiě)程序時(shí)所體現(xiàn)出的特點(diǎn)、習(xí)慣和邏輯思緒。程序是由人來(lái)

編寫(xiě)的，為了測(cè)試和維護(hù)程序，往往還要新聞?dòng)浾吆透櫝绦?，因此程序設(shè)計(jì)的風(fēng)格總體而

言應(yīng)當(dāng)強(qiáng)調(diào)得意和清晰，程序必須是可以理解的。

要形成良好的程序設(shè)計(jì)風(fēng)格，重要應(yīng)重視和考慮下述某些原因。

1、源程序文檔化

2、源程序文檔化應(yīng)考慮如下幾點(diǎn)：

（1）符號(hào)名的命名：符號(hào)名的命名應(yīng)具有一定的實(shí)際含義，以便于對(duì)程序功能的

理解。

（2）程序注釋?zhuān)合驴说淖⑨尶梢詤f(xié)助讀者理解程序。

（3）禮堂組織：為使程序的構(gòu)造一目了然，可以在程序中運(yùn)用空格、空行、縮進(jìn)

待技巧使程序?qū)哟吻逦?/p>

2、數(shù)聽(tīng)闡明的措施

在編寫(xiě)程序時(shí)，需要注意數(shù)聽(tīng)闡明的風(fēng)格，以便使程序中的數(shù)聽(tīng)闡明更易于理解和維護(hù)。一

般應(yīng)注意如下幾點(diǎn)：

（1）數(shù)聽(tīng)闡明的次序規(guī)范化鑒于程序理解、新聞?dòng)浾吆途S護(hù)的需要，使數(shù)聽(tīng)闡明

次序固定，可以使數(shù)據(jù)的發(fā)生輕易查找，也有助于測(cè)試、排錯(cuò)和維護(hù)。

（2）闡明語(yǔ)句中變量安排有序化。當(dāng)一種闡明語(yǔ)句闡明多種變量時(shí)，變量按照字

母次序?yàn)楹谩?/p>

（3）使用注釋來(lái)闡明兔雜數(shù)據(jù)的構(gòu)造。

3、語(yǔ)句的構(gòu)造

程序應(yīng)當(dāng)簡(jiǎn)樸易懂，語(yǔ)句構(gòu)造應(yīng)當(dāng)簡(jiǎn)樸直接，不應(yīng)當(dāng)為提高效率而把語(yǔ)句復(fù)雜化。一般應(yīng)注

意如下：

（1）在一行內(nèi)只寫(xiě)一條語(yǔ)句；

（2）程序編寫(xiě)應(yīng)優(yōu)先考慮清晰性；

（3）除非對(duì)效率有特殊規(guī)定，程序編寫(xiě)要做清晰第一，效率第二；

（4）首先要保證程序?qū)Φ?，然后才?guī)定提高速度；

（5）防止使用臨時(shí)變量而使程序的可讀性下降；

（6）防止不必要的轉(zhuǎn)移；

（7）盡量使用庫(kù)函數(shù)；

（8）防止采用復(fù)雜的條件語(yǔ)句：

（9）盡量減少使用“否認(rèn)”條件的條件語(yǔ)句；

（10）數(shù)據(jù)構(gòu)造要有助于程序的簡(jiǎn)化；

（11）要模塊化，使模塊功能盡量單一化；

（12）運(yùn)用住處急蔽，保證每一種模塊的獨(dú)立性；

（13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；

（14）不要修補(bǔ)不好的程序，要重新編寫(xiě)；

4、輸入和輸出

無(wú)論是批處理的輸入和輸出方式，還是交互式的輸入和輸出方式，在設(shè)計(jì)和編程時(shí)都應(yīng)當(dāng)考

慮如下原則：

（1）對(duì)所有的輸入數(shù)據(jù)都要檢查數(shù)據(jù)的合法性；

（2）檢查輸入項(xiàng)的多種重要組合的合理性；

（3）輸入格式要簡(jiǎn)樸，以使得輸入的環(huán)節(jié)和操作盡量簡(jiǎn)樸；

（4）輸入數(shù)據(jù)時(shí)，應(yīng)容許使用自由格式；

（5）應(yīng)容許缺省值；

（6）輸入一批數(shù)據(jù)時(shí)，最佳使用輸入結(jié)束標(biāo)志；

（7）在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提醒符明確提醒輸入

的祈求，同步在數(shù)據(jù)輸入過(guò)程中的輸入結(jié)束時(shí)，應(yīng)在屏舞上給出狀態(tài)信息、。

（8）當(dāng)程序設(shè)L語(yǔ)言對(duì)輸入格式有嚴(yán)格規(guī)定期，應(yīng)保持輸入格式與輸入語(yǔ)句的一

致性：給所有的輸入出加注釋?zhuān)⒃O(shè)計(jì)輸出報(bào)表格式。

2.2構(gòu)造化程序設(shè)計(jì)

一、構(gòu)造化程序設(shè)計(jì)的原則

構(gòu)造化程序設(shè)計(jì)措施的重要原則可以概括為自頂向下，逐漸求精，模塊化，限制使用goto

語(yǔ)句。

1、自頂向下：程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目的，后考

慮局部目的。不要一開(kāi)始就過(guò)多追求眾多的細(xì)節(jié)，先從最上層總目的開(kāi)始設(shè)計(jì)，逐漸使問(wèn)題

詳細(xì)化。

2、逐漸求精：對(duì)復(fù)雜問(wèn)題，應(yīng)設(shè)計(jì)某些子目的作過(guò)渡，逐漸細(xì)化。

3、模塊化：一種復(fù)雜問(wèn)題，肯定是由若干稍簡(jiǎn)樸的問(wèn)題構(gòu)成。模塊化是把程序要

處理的總目的分解為分目的，再深入分解為詳細(xì)的小目的，把每個(gè)小目的稱(chēng)為一種模塊。

4、限制使用got。語(yǔ)句

使用goto語(yǔ)句經(jīng)試驗(yàn)證明：（1）濫用GOTO語(yǔ)句確實(shí)有害，應(yīng)晝防止；

（2）完全防止使用GOTO語(yǔ)句也并非是個(gè)明智的措施，有些地方使用GOTO語(yǔ)句，會(huì)使程

序流程更清晰、效率更高；

（3）爭(zhēng)論的焦點(diǎn)不應(yīng)當(dāng)放在與否取消GOTO語(yǔ)句，而應(yīng)當(dāng)放在用什么樣的程序構(gòu)造上。

其中最關(guān)鍵的是，肯定以提高程序清晰性為目的的構(gòu)造化措施。

二、構(gòu)造化程序的基本構(gòu)造與特點(diǎn)

1、次序構(gòu)造：次序構(gòu)造是簡(jiǎn)樸的程序設(shè)計(jì)，它是最基本、最常用的構(gòu)造，所謂次序執(zhí)行，

就是按照程序語(yǔ)句行的自然次序，一條語(yǔ)句一條語(yǔ)句地執(zhí)行程序程序。

2、選擇構(gòu)造：選擇構(gòu)造又稱(chēng)為分支構(gòu)造，它包括簡(jiǎn)樸選擇和多分支選擇構(gòu)造，這種構(gòu)造可

以根據(jù)設(shè)定的條件，判斷應(yīng)當(dāng)選擇哪一條分支來(lái)執(zhí)行對(duì)應(yīng)的語(yǔ)句序列。

3、反復(fù)構(gòu)造：反復(fù)構(gòu)造又稱(chēng)為循環(huán)構(gòu)造，它根據(jù)給定的條件，判斷與否需要反復(fù)執(zhí)行某一

相似的或類(lèi)似的程序段，運(yùn)用反第構(gòu)造可簡(jiǎn)化大量的程序行。分為兩類(lèi)：?是先判斷后執(zhí)行,

一是先執(zhí)行后判斷。

長(zhǎng)處：一是程序易于理解?、使用和維護(hù)。二是編程工作的效率，減少軟件開(kāi)發(fā)成本。

三、構(gòu)造化程序設(shè)計(jì)原則和措施的應(yīng)用

要注意把握如下要素：

1、使用程序設(shè)干語(yǔ)言中的次序、選擇、循環(huán)等有限的控制構(gòu)造表達(dá)程序的控制邏

輯。

2、選用的控制構(gòu)造只準(zhǔn)許有一種入口和一種出口；

3、程序語(yǔ)句構(gòu)成輕易識(shí)別的塊，每塊只有一種入口和一種出口；

4、復(fù)雜構(gòu)造應(yīng)當(dāng)嵌套的基本控制構(gòu)造進(jìn)行組合嵌套來(lái)實(shí)現(xiàn)；

5、語(yǔ)言中所沒(méi)有的控制構(gòu)造，應(yīng)當(dāng)采用前后一致的措施來(lái)模擬；

6、嚴(yán)格控制GOTO語(yǔ)句的使用。其意思是指：

（1）用一種非構(gòu)造化的程序設(shè)計(jì)語(yǔ)言去實(shí)現(xiàn)一種構(gòu)造化的構(gòu)造；

（2）若不使用GOTO語(yǔ)句會(huì)使功能模糊；

（3）在某種可以改善而不損害程序可讀性的狀況下。

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

一、有關(guān)面向?qū)ο蟠胧?/p>

面向?qū)ο蟠胧┑谋举|(zhì)，就是主張從客觀世界固有的事物已發(fā)來(lái)構(gòu)造系統(tǒng)，倡導(dǎo)用人類(lèi)在現(xiàn)實(shí)

生活中常用的思維措施來(lái)認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)可以映射問(wèn)題域,

也就是說(shuō)，系統(tǒng)中的對(duì)象以及對(duì)象之間的關(guān)系可以如實(shí)地反應(yīng)問(wèn)題域中固有事物及其關(guān)系。

長(zhǎng)處：1、與人類(lèi)習(xí)慣的思維措施一致

面向?qū)ο蟠胧┖图夹g(shù)以對(duì)象為關(guān)鍵。對(duì)象是由數(shù)據(jù)和容許的操作構(gòu)成的封裝體，與客觀實(shí)體

有直接的關(guān)系。對(duì)象之間通過(guò)傳遞消息互相聯(lián)絡(luò)，以模擬現(xiàn)實(shí)世界中不一樣事物彼此之間的

聯(lián)絡(luò)。

面向?qū)ο蟮脑O(shè)計(jì)措施與老式的面向過(guò)程的措施有小質(zhì)不一樣，這種措施的基小原理是：使用

現(xiàn)實(shí)世界的概念抽象地思索問(wèn)題從而自然地處理問(wèn)題。它強(qiáng)調(diào)模擬現(xiàn)實(shí)世界中的概念而不強(qiáng)

調(diào)算法，它鼓勵(lì)開(kāi)發(fā)者在軟件開(kāi)發(fā)的絕大部分過(guò)程中都用應(yīng)用領(lǐng)域的要領(lǐng)去思索。

2、穩(wěn)定性好

3、可重用性好

軟件重用是指在不一樣的軟件開(kāi)發(fā)過(guò)程中反復(fù)作用相似或相似軟件元素的過(guò)程。重用是提高

軟件生產(chǎn)率的最重要的措施。

4、易于開(kāi)發(fā)大型軟件產(chǎn)品

5、可維護(hù)性好

（1）用面向?qū)ο蟮拇胧┥l(fā)的軟件穩(wěn)定性比很好

（2）用面向?qū)ο蟮拇胧┊a(chǎn)發(fā)的軟件比較輕易修改；

（3）用面向?qū)ο蟮拇胧╅_(kāi)發(fā)的軟件比較輕易理解。

（4）易于測(cè)試和調(diào)試。

二、面向?qū)ο蟠胧┑幕靖拍?/p>

1、對(duì)象（object）

對(duì)象是面向?qū)ο蟠胧┲凶罨镜母拍睢?duì)象可以用來(lái)表達(dá)客觀世界中的任何實(shí)體，也就是說(shuō),

應(yīng)用領(lǐng)域中故意義的、與所要處理的問(wèn)題有關(guān)系的任何尋物都可以作為對(duì)象，它既可以是詳

細(xì)的物理實(shí)體的抽象，也可以是人為的概念，或者是任何有明確邊界的意義的東西?？傊?，

對(duì)象是對(duì)問(wèn)題域中某個(gè)實(shí)體的抽象，設(shè)置某個(gè)對(duì)象就反應(yīng)軟件系統(tǒng)保留有關(guān)它的信息并具有

與它進(jìn)行交互的能力。

面向?qū)ο蟮某绦蛟O(shè)計(jì)措施中波及的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的?種實(shí)體，是構(gòu)成系統(tǒng)

的一種基本單位，它由一組表達(dá)其靜態(tài)特性的屬性和它可執(zhí)行的一組操作構(gòu)成。

對(duì)象可以做的操作表達(dá)它的動(dòng)態(tài)行為，在面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O(shè)計(jì)中，i般把對(duì)象的操

作也稱(chēng)為措施或服務(wù)。

屬性即對(duì)象所包括的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過(guò)掛靠對(duì)象的操作來(lái)變化。

操作描述了對(duì)象執(zhí)行的功能，若通過(guò)消息傳遞，還可認(rèn)為其他對(duì)象使用。操作的過(guò)程對(duì)外是

封閉的，即顧客只能看到這一操作實(shí)行后的成果。這相稱(chēng)于事先已經(jīng)設(shè)計(jì)好的多種過(guò)程，只

需要調(diào)用就可以了，顧客不必去關(guān)懷這一過(guò)程是怎樣編寫(xiě)的。實(shí)際上，這個(gè)過(guò)程已經(jīng)封裝在

對(duì)象中，顧客也看不到。對(duì)的這一特性即是對(duì)象的封裝性。

對(duì)象有如下某些基本特點(diǎn)：

（1）標(biāo)識(shí)惟一性。指對(duì)象是可辨別的，并且由對(duì)象有的內(nèi)在本質(zhì)來(lái)辨別，而不是

通過(guò)描述來(lái)辨別。

（2）分類(lèi)性。指可以將具有相似屬性的操作的對(duì)象抽象成類(lèi)。

（3）多太性。指同一種操作可以是不一樣對(duì)象的行為。

（4）封裝性。從外面看只能看到對(duì)象的外部特性，即只需懂得數(shù)據(jù)的取值范圍和

可以對(duì)該數(shù)據(jù)施加的操作，主線(xiàn)無(wú)需懂得數(shù)據(jù)的詳細(xì)構(gòu)造以及實(shí)現(xiàn)操作的算法。對(duì)象的內(nèi)部，

即處理能力的實(shí)行和內(nèi)部狀態(tài)，對(duì)外是不可見(jiàn)的。從外面不能直接使用對(duì)象的處理能力，也

不能直接修改其內(nèi)部狀態(tài)，對(duì)象的內(nèi)部狀態(tài)只能由其自身變化。

（5）模塊獨(dú)立性好。對(duì)象是面向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對(duì)這

些數(shù)據(jù)施加的操作所構(gòu)成的統(tǒng)一體，并且對(duì)象是以數(shù)據(jù)為中心的，操作圍繞對(duì)其數(shù)據(jù)所需做

的處理來(lái)設(shè)置，沒(méi)有無(wú)關(guān)的操作從模塊的獨(dú)立性考慮，對(duì)象內(nèi)部多種元素彼此結(jié)合得很緊密，

內(nèi)聚性強(qiáng)。

2、類(lèi)（Class）和實(shí)例（Instance）

將屬性、操作相似的對(duì)象歸為類(lèi)，也就是說(shuō)，類(lèi)是具有共同屬性、共同措施的對(duì)象的集合。

因此，類(lèi)是對(duì)象的抽象，它描述了屬于該對(duì)象類(lèi)型的所有對(duì)象的性質(zhì)，而一種對(duì)象則是其對(duì)

應(yīng)類(lèi)的一種實(shí)例。

要注意的是，當(dāng)使用“對(duì)象，這個(gè)術(shù)語(yǔ)時(shí)，既可以指一種詳細(xì)的對(duì)象，也可以泛指一般的對(duì)象,

不過(guò)，當(dāng)使用“實(shí)例”這個(gè)術(shù)語(yǔ)時(shí)，必然是指一種詳細(xì)的對(duì)象。

例如：Integer是一種整數(shù)類(lèi)，它描述了所有整數(shù)的性質(zhì)。因此任何整數(shù)都是整數(shù)類(lèi)的對(duì)象,

而一種詳細(xì)的整數(shù)力23”是類(lèi)Integer的實(shí)例。

由類(lèi)的定義可知，類(lèi)是有關(guān)對(duì)象性質(zhì)的描述，它同對(duì)象同樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上

的一組合法操作。

3、消息（Message）

面向?qū)ο蟮氖澜缡峭ㄟ^(guò)對(duì)象與對(duì)象間彼此的互相合作來(lái)推進(jìn)的，對(duì)象間的這種互相合作需要

一種機(jī)制協(xié)助進(jìn)行，這樣的機(jī)制稱(chēng)為“消息消息是一種實(shí)例與另一種實(shí)例之間傳遞信息，

它請(qǐng)示對(duì)象執(zhí)行某一處理或回答某一規(guī)定的信息、，它統(tǒng)一了數(shù)據(jù)流的控制流。消息的使用類(lèi)

似于函數(shù)調(diào)用，消息中指定了某一種實(shí)例，一種操作名和一種參數(shù)表（可空）。接受消息的

實(shí)例執(zhí)行消息中指定的操作，并將形式參數(shù)數(shù)與參數(shù)表口對(duì)應(yīng)的值結(jié)合起來(lái)。消息傳遞過(guò)程

中，由發(fā)送消息的對(duì)象（發(fā)送對(duì)象）的觸發(fā)操作產(chǎn)生輸出成果，作為消息傳送至接受消息的

對(duì)象（接受對(duì)象），引起接受消息的對(duì)象?系列的操作。所傳送的消息實(shí)質(zhì)上是接受對(duì)象所

具有的操作/措施名稱(chēng)，有時(shí)還包括對(duì)應(yīng)參數(shù)。

消息中只包括傳遞者的規(guī)定，它告訴接受者需要做哪些處理，但并不指示接受者應(yīng)當(dāng)怎樣完

畢這些處理。消息完全由接受者解釋?zhuān)邮苷擢?dú)立決定采用什么方式完畢所需的處理，發(fā)送

者對(duì)接受者不起任何控制作用。一種對(duì)象可以接受不一樣形式、不一樣內(nèi)容的多種消息；相

似形式的消息可以送往不?樣的對(duì)象，不一樣的對(duì)象對(duì)于形式相似的消息可以有不?樣的解

釋?zhuān)梢宰龀霾灰粯拥姆磻?yīng)。一種對(duì)象可以同步往多種對(duì)象傳遞信息，兩個(gè)對(duì)象也可以同步

向某個(gè)對(duì)象傳遞消息。

例如，一種汽車(chē)對(duì)象具有“行駛”這項(xiàng)操作，那么要讓汽車(chē)以時(shí)速50公里行駛的話(huà)，需傳遞

給汽車(chē)對(duì)象“行駛”及“時(shí)速50公里”的消息。

一般，一種消息由下述三部分構(gòu)成：

（1）接受消息的對(duì)象的名稱(chēng)：

（2）消息標(biāo)識(shí)符（也稱(chēng)為消息名）；

（3）零個(gè)或多種參數(shù)。

4、繼承（Inheritance）

繼承是面向?qū)ο蟮拇胧┑囊环N重要特性。繼承是使用己有的類(lèi)定義作為基礎(chǔ)建立新類(lèi)的定義

技術(shù)。已經(jīng)有的類(lèi)可當(dāng)作基類(lèi)來(lái)引用，則新類(lèi)對(duì)應(yīng)地可當(dāng)作派生類(lèi)來(lái)引用。

廣義地說(shuō)，繼承是指可以直接獲得已經(jīng)有的性質(zhì)和特性，而不必反復(fù)定義它們。

面向?qū)ο筌浖夹g(shù)的許多強(qiáng)有力的功能和突出的長(zhǎng)處，都來(lái)源于把類(lèi)構(gòu)成一種層次構(gòu)造的系

統(tǒng)：一種類(lèi)的上層可以有父類(lèi)，下層可以有子類(lèi)。這種層次構(gòu)造系統(tǒng)的一種重要性質(zhì)是繼承

性，一種類(lèi)直接繼承其父類(lèi)的描述（數(shù)據(jù)和操作）或特性，子類(lèi)自動(dòng)地共享基類(lèi)中定義的數(shù)

據(jù)和措施。

繼承具有傳遞性，假如類(lèi)C繼承類(lèi)B,類(lèi)B繼承類(lèi)A,則類(lèi)C繼承類(lèi)A。因此一種類(lèi)實(shí)際

上繼承了它上層的所有基類(lèi)的特性，也就是說(shuō)，屬于某類(lèi)的對(duì)象除了具有該類(lèi)所定義的特性

外，還具有該類(lèi)上層所有基類(lèi)定義的特性。

繼承分為單繼承與多重繼承。單繼承是指，一種類(lèi)只容許有一種父類(lèi)，即類(lèi)等級(jí)為樹(shù)形構(gòu)造。

多重繼承是指，一種類(lèi)容許有多種父類(lèi)。多重繼承的類(lèi)可以組合多種父類(lèi)的性質(zhì)構(gòu)成所需要

的性質(zhì)。因此，功能更強(qiáng)，使用更以便；便是，使用多重繼承時(shí)要注意防止二義性。繼承性

的長(zhǎng)處是，相似的對(duì)象可以共享程序代碼和數(shù)據(jù)構(gòu)造，從而大大減少了程序中的冗余信息，

提高軟件的可重用性，便于軟件個(gè)性維護(hù)。此外，繼承性便利顧客在開(kāi)發(fā)新的應(yīng)用系統(tǒng)時(shí)不

必完全從零開(kāi)始，可以繼承原有的相似系統(tǒng)的功能或者從類(lèi)庫(kù)中選用需要的類(lèi)，再派生出新

的類(lèi)以實(shí)現(xiàn)所需要的功能。

5、多太性（Polymorphism）

對(duì)象根據(jù)所接受的消息而做出動(dòng)作，同樣的消息被不一樣的對(duì)象接受時(shí)可導(dǎo)致完全不一樣

的行動(dòng)，該現(xiàn)象稱(chēng)為多態(tài)性。在面向?qū)ο蟮能浖夹g(shù)中，多態(tài)性是指類(lèi)對(duì)象可以像父類(lèi)對(duì)象

那樣使用，同樣的消息既可以發(fā)送給父類(lèi)對(duì)象也可以發(fā)送給子類(lèi)對(duì)象。

多態(tài)性機(jī)制不僅增長(zhǎng)了面向?qū)ο筌浖到y(tǒng)的靈活性，深入減少了信息冗余，并且明顯地提高

了軟件的可重用性和可擴(kuò)充性。當(dāng)擴(kuò)充系統(tǒng)功能增長(zhǎng)新的實(shí)體類(lèi)型時(shí)，只需派生出與新實(shí)體

類(lèi)對(duì)應(yīng)的新的子類(lèi)，完全無(wú)需修改原有的程序代碼，甚至不需要重新編譯原有的程序。運(yùn)用

多態(tài)性，顧客可以發(fā)送一般形式的消息，而將所有的實(shí)現(xiàn)細(xì)節(jié)都留給接受消息的對(duì)象。

第3章軟件工程基礎(chǔ)

3.1軟件工程基本概念

一、軟件定義與軟件特點(diǎn)

計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件互相依存的另一部分，是包括程序、數(shù)據(jù)及有關(guān)文檔的完

整集合?；校绦蚴擒浖_(kāi)發(fā)人員根據(jù)顧客需求開(kāi)發(fā)的用程序設(shè)計(jì)語(yǔ)言描述的、適合計(jì)算

機(jī)執(zhí)行的指令（語(yǔ)句）序列。數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)構(gòu)造。文檔是與程序開(kāi)發(fā)、

維護(hù)和使用有關(guān)的圖文資料。可見(jiàn)軟件由兩部分構(gòu)成：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是

機(jī)器不可執(zhí)行的，與軟件開(kāi)發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。

國(guó)標(biāo)（GB）中對(duì)計(jì)算機(jī)軟件的定義為：與計(jì)算機(jī)系統(tǒng)的操作有關(guān)的計(jì)算機(jī)程序、規(guī)程、規(guī)

則，以及也許有的文獻(xiàn)、文檔及數(shù)據(jù)。

軟件在開(kāi)發(fā)、生產(chǎn)、維護(hù)和使用等方面與計(jì)算機(jī)硬件相匕存在明顯的差異。深入理解軟件的

定義需要理解軟件的特點(diǎn)：

（1）軟件是一種邏輯實(shí)體，而不是物理實(shí)體具有抽象性。

（2）軟件的生產(chǎn)與硬件不一樣，它沒(méi)有明顯的制作過(guò)程。一旦研制開(kāi)發(fā)成功，可

以大量拷貝同一內(nèi)容的副木。因此對(duì)軟件的控制，必須著重在軟件開(kāi)發(fā)方面下功夫.

（3）軟件在運(yùn)行、有效期間不存在磨損、老化問(wèn)題。

（4）軟件的開(kāi)發(fā)運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴(lài)性，受計(jì)算機(jī)系統(tǒng)的限制這導(dǎo)致了軟

件移植的問(wèn)題。

（5）軟件復(fù)雜性高，成本昂貴。

（6）軟件開(kāi)發(fā)波及諸多的社會(huì)原因。

軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。應(yīng)用軟件是為處理

特定領(lǐng)域的應(yīng)用而開(kāi)發(fā)的軟件。系統(tǒng)軟件是計(jì)算機(jī)管理自身資源，提高計(jì)算機(jī)使用效率并為

計(jì)算機(jī)顧客提供多種服務(wù)的軟件。支撐軟件是介于系統(tǒng)軟件和應(yīng)用軟件之間，協(xié)助顧客開(kāi)發(fā)

軟件的工具性軟件，包括輔助和支持開(kāi)發(fā)和維護(hù)應(yīng)用軟件的工具軟件。

二、軟件危機(jī)與軟件工程

軟件工程概念的出現(xiàn)源自軟件危機(jī)。

所謂有軟件危機(jī)四伏是泛指在計(jì)算機(jī)軟件開(kāi)發(fā)和維護(hù)過(guò)程中所碰到的嚴(yán)重問(wèn)題。實(shí)際上，幾

科所有的軟件都不一樣程度地存在這些問(wèn)題。

伴隨計(jì)算機(jī)技術(shù)的發(fā)展和應(yīng)川領(lǐng)域的擴(kuò)大，計(jì)算機(jī)硬件性能/價(jià)格比和質(zhì)量穩(wěn)步提高，軟件

規(guī)模越來(lái)越大，復(fù)雜程度不停增長(zhǎng)，軟件成本逐年上升，質(zhì)量沒(méi)有可靠的保證，軟件已成為

計(jì)算機(jī)科學(xué)發(fā)展的“瓶頸

詳細(xì)地說(shuō)，在軟件開(kāi)發(fā)和維護(hù)過(guò)程中，軟件危機(jī)重要表目前：

（I）軟件需求的增長(zhǎng)得不到滿(mǎn)足。顧客對(duì)系統(tǒng)不滿(mǎn)意的狀況常常發(fā)生。

（2）軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制。開(kāi)發(fā)成本超過(guò)預(yù)算，開(kāi)發(fā)周期大大超過(guò)規(guī)定

日期的狀況常常發(fā)生。

（3）軟件質(zhì)量難以保證。

（4）軟件不可維護(hù)或護(hù)程度非常低。

（5）軟件的成本不停提高。

（6）軟件開(kāi)發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)。

總之，可以將軟件危機(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。

軟件工程就是試圖用工程、科學(xué)和數(shù)學(xué)的大批量與措施研制、維護(hù)計(jì)算機(jī)軟件的有關(guān)技術(shù)及

管理措施。

有關(guān)軟件工程的定義，國(guó)標(biāo)（GB）中指出，軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和

維護(hù)的一整套措施、工具文檔、實(shí)踐原則的工序。

1993年IEEE（InstituteofElectrical&ElectronicEngineers,電氣和電子工程師學(xué)會(huì)）給出了一

種愈加綜合的定義：”將系統(tǒng)化的、規(guī)范的、可度量的措施應(yīng)用于軟件的開(kāi)發(fā)、運(yùn)行和維護(hù)

的過(guò)程，即將工程化應(yīng)用于軟件中“。

軟件工程包括3個(gè)要素：即措施、工具和過(guò)程。措施是完畢軟件工程項(xiàng)目的技術(shù)手段；工具

支持軟件的開(kāi)發(fā)、管理、文檔生成；過(guò)程支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制、管理。

軟件工程的關(guān)鍵思想是把軟件產(chǎn)品看作是一種工程產(chǎn)品來(lái)處理。

開(kāi)發(fā)軟件不能只考慮開(kāi)發(fā)期間的費(fèi)用，并且應(yīng)考慮軟件生命周期內(nèi)的所有費(fèi)用。因此，軟件

生命周期的概念就變得尤其重要。在考慮軟件費(fèi)用時(shí)，不僅僅要減少開(kāi)發(fā)成本，更要減少整

個(gè)軟件生命周期的總成本。

三、軟件工程過(guò)程與軟件生命周期

1、軟件工程過(guò)程（SoftwareEngineeringProcess）

IS09000定義：軟件工程過(guò)程是把輸入轉(zhuǎn)化為輸出的一組彼此有關(guān)的資源和活動(dòng)。

定義支持了軟件工程過(guò)程的兩方面內(nèi)涵。其一，軟件工程過(guò)程是指為獲得軟件產(chǎn)品，在軟件

工具支持下由軟件工程師完畢的一系列軟件工程活動(dòng)?；谶@個(gè)方面，軟件工程過(guò)程一般包

括4種基木活動(dòng)：

（1）P（plan）——軟件規(guī)格闡明。規(guī)定軟件的功能及其運(yùn)行時(shí)的限制。

（2）D（do）——軟件開(kāi)發(fā)。產(chǎn)生滿(mǎn)足規(guī)格闡明的軟件。

（3）C（check）——軟件確認(rèn)。確認(rèn)軟件可以滿(mǎn)足客戶(hù)提出的規(guī)定。

（4）A（action）—軟件演進(jìn)。為滿(mǎn)足客戶(hù)的變更規(guī)定，軟件必須在使用的過(guò)程中

演進(jìn)。

一般把顧客的規(guī)定轉(zhuǎn)變成軟件產(chǎn)品的過(guò)程也叫做軟件開(kāi)發(fā)過(guò)程。此過(guò)程包括對(duì)顧客的規(guī)定進(jìn)

行分析，解釋成軟件需求，把需求變換成設(shè)計(jì)，把設(shè)計(jì)用代碼來(lái)實(shí)現(xiàn)并進(jìn)行代碼測(cè)試，有些

軟件還需要進(jìn)行代碼安裝和交付運(yùn)行。

其二，從軟件開(kāi)發(fā)的觀點(diǎn)看，它就是使用合適的斐源（包括人員、硬軟件工具、時(shí)間等），

為開(kāi)發(fā)軟件進(jìn)行的一組開(kāi)發(fā)活動(dòng)，在過(guò)程結(jié)束時(shí)將輸入（顧客規(guī)定）轉(zhuǎn)化為輸出（軟件產(chǎn)品）。

因此，軟件工程的過(guò)程是洛軟件工程的措施和工具綜合起來(lái)，以到達(dá)合理、及時(shí)地進(jìn)行計(jì)算

機(jī)軟件開(kāi)發(fā)的F1的。軟件工程過(guò)程應(yīng)確定措施使用的次序、規(guī)定交付的文檔資料、為保證質(zhì)

量和適應(yīng)變化所需要的管理、軟件開(kāi)發(fā)各個(gè)階段完畢的任務(wù)。

2^軟件生命周期（softwarelifecycle）

一般，將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退伍的過(guò)程稱(chēng)為軟件生命周期。一般

包括可行性研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試、交付使用以及維護(hù)等活動(dòng)。

還可以將軟件生命周期分為軟件定義、軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段。軟件生命周期的

重要活動(dòng)階段是：

（1）可行性研究與計(jì)劃制定。確定待開(kāi)發(fā)軟件系統(tǒng)的開(kāi)發(fā)目的和總的規(guī)定，給出

它的功能、性能、可靠性以及接口等方面的也許方案，制定完畢開(kāi)發(fā)任務(wù)的實(shí)行計(jì)劃。

（2）需求分析?？创_(kāi)發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)定義。編寫(xiě)軟件規(guī)

格闡明書(shū)及初步的顧客手冊(cè)，提交評(píng)審。

（3）軟件設(shè)計(jì)。系統(tǒng)設(shè)計(jì)人員和程序設(shè)計(jì)人員應(yīng)當(dāng)在反復(fù)理解軟件需求的基礎(chǔ)上,

給出軟件的構(gòu)造、模塊和劃分、功能的分派及處理流程。在系統(tǒng)比軟件復(fù)雜的狀況卜，設(shè)計(jì)

階段可分解成概要設(shè)計(jì)階段和詳細(xì)設(shè)計(jì)階段。編寫(xiě)概要設(shè)計(jì)闡明書(shū)、詳細(xì)設(shè)計(jì)闡明書(shū)和測(cè)試

計(jì)劃草稿，提交評(píng)審。

（4）軟件實(shí)現(xiàn)。把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。即完畢源程序的

編碼，編寫(xiě)顧客手冊(cè)、操作手冊(cè)等面向顧客的文檔，編寫(xiě)單元測(cè)試計(jì)劃。

（5）軟件測(cè)試。在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上，檢查軟件的各個(gè)構(gòu)成部分。編寫(xiě)測(cè)試

分析匯報(bào)。

（6）運(yùn)行和維護(hù)。將已交付的軟件投入運(yùn)行，并在運(yùn)行使用中不停地維護(hù)，根據(jù)

新進(jìn)出的需求進(jìn)行必要并且也許的擴(kuò)充和刪改。

四、軟件工程的目的與原則

I、軟件工程的目的

軟件工程的目的是，在給定成本、進(jìn)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、

可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿(mǎn)足顧客需求的產(chǎn)品。

軟件工程需要到達(dá)的基本目的應(yīng)是：付出較低的開(kāi)發(fā)成本；到達(dá)規(guī)定的軟件功能；獲得很好

的軟件性能：開(kāi)發(fā)的軟件易于移植：需要較低的維護(hù)費(fèi)用；能準(zhǔn)時(shí)完畢開(kāi)發(fā)，及時(shí)交付使用。

基于軟件工程的1=1的，軟件工程的理論和技術(shù)性研窕的內(nèi)容重要包括：軟件開(kāi)發(fā)技術(shù)和軟件

工程管理。

(1)軟件開(kāi)發(fā)技術(shù)

軟件開(kāi)發(fā)技術(shù)包括：軟件開(kāi)發(fā)法學(xué)、開(kāi)發(fā)過(guò)程、開(kāi)發(fā)工具和軟件工程環(huán)境，其主體內(nèi)容是軟

件開(kāi)發(fā)措施學(xué)。軟件開(kāi)發(fā)措施學(xué)是根據(jù)不一樣的軟件類(lèi)型，按不一樣的觀點(diǎn)和原則，對(duì)軟件

開(kāi)發(fā)中應(yīng)遵照的方略、原則、環(huán)節(jié)和必須產(chǎn)生的文檔資料都做出規(guī)定，從而使軟件的開(kāi)發(fā)可

以進(jìn)入規(guī)范化和工程化的階段，以克服初期的手工措施生產(chǎn)中的隨意性和非規(guī)范性做法。

(2)軟件工程管理

軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容。

軟件工程管理是軟件按工程化生產(chǎn)時(shí)的重要環(huán)節(jié)，它規(guī)定按照預(yù)選制定的計(jì)劃、進(jìn)度和預(yù)算

執(zhí)行，以實(shí)現(xiàn)預(yù)期的經(jīng)濟(jì)效益和社會(huì)效益。

軟件工程經(jīng)濟(jì)學(xué)是研究軟件開(kāi)發(fā)中成本的估算、成本效益分析的措施和技術(shù)，用經(jīng)濟(jì)學(xué)的基

本原理來(lái)研究軟件工程開(kāi)發(fā)中的經(jīng)濟(jì)效益問(wèn)題。

軟件心理學(xué)是軟件工程領(lǐng)域具有挑戰(zhàn)性的一種全新的研究視角，它是從個(gè)體心理、人類(lèi)行為、

組織行為和企業(yè)文化等角展來(lái)研究軟件管理和軟件工程的。

2、軟件工程的原則

為了到達(dá)上述的軟件工程目的，在軟件開(kāi)發(fā)過(guò)程中，必須遵照軟件工程的基本原則。這些基

本原則包括抽象、信息隱版、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。

(1)抽象。抽取事物最基本的特性和行為，忽視非本質(zhì)細(xì)節(jié)。采用分層次抽象，

自頂向下，逐層細(xì)化的措施控制軟件開(kāi)發(fā)過(guò)程的復(fù)雜性。

(2)信息隱蔽。采用封閉技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱藏起來(lái)，使模塊接口盡

量簡(jiǎn)樸。

(3)模塊化。模塊是程序中相對(duì)獨(dú)立的成分，一種獨(dú)立的編程單位，應(yīng)有良好的

接口定義。模塊的大小要適中，模塊過(guò)大會(huì)使模塊內(nèi)部的復(fù)雜性增長(zhǎng)，不得對(duì)模塊的理解和

個(gè)性也不得模塊的調(diào)試和重用。模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表達(dá)過(guò)于復(fù)雜，不利于控制系統(tǒng)的

復(fù)雜性。

(4)局部化。規(guī)定在一種物理模塊內(nèi)集中邏輯上互相關(guān)聯(lián)的計(jì)算資源，保證模塊

間具有松散的耦合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)驟性，這有助于控制角的復(fù)雜性。

(5)確定性軟件開(kāi)發(fā)過(guò)程中所有概念的體現(xiàn)應(yīng)是確定的、無(wú)歧義且規(guī)范的。這有

助于人與人的交互不會(huì)產(chǎn)生誤解和遺漏，以保證整個(gè)開(kāi)發(fā)工作的協(xié)調(diào)一致。

(6)一致性。揚(yáng)程序、數(shù)據(jù)和文檔的整個(gè)軟件系統(tǒng)的各模塊應(yīng)使用已知的概念、

符號(hào)和術(shù)語(yǔ)；程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格闡明與系統(tǒng)行為應(yīng)保持一致。

(7)完備性。軟件系統(tǒng)不丟失任何重要成分，完全實(shí)現(xiàn)系統(tǒng)所需的功能。

(8)可驗(yàn)證性。開(kāi)發(fā)大型軟件系統(tǒng)需要對(duì)系統(tǒng)自頂向下，逐層分解。系統(tǒng)分解應(yīng)

遵照輕易檢查、測(cè)評(píng)、評(píng)審的原則，以保證系統(tǒng)的對(duì)的性。

五、軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境

現(xiàn)代軟件工程措施之因此千里馬實(shí)行，其重要的保證是軟件開(kāi)發(fā)工具的環(huán)境的保證，使軟件

在開(kāi)發(fā)效率、工程質(zhì)量等多方面得到改善。軟件工程鼓勵(lì)研制和采用多種先進(jìn)的軟件開(kāi)發(fā)措

施、工具和環(huán)境。工具和環(huán)境的使用深入提高了軟件的開(kāi)發(fā)效率、維護(hù)效率和軟件質(zhì)量。

1、軟件開(kāi)發(fā)工具

2、軟件開(kāi)發(fā)環(huán)境

軟件開(kāi)發(fā)環(huán)境或稱(chēng)軟件工程環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合。

計(jì)算機(jī)輔助軟件工程(CASE,computeraidedsoftwareengineering)是目前軟件開(kāi)發(fā)環(huán)境中

富有特色的研究工作和發(fā)展方向。CASE將多種軟件工具、開(kāi)發(fā)機(jī)器和?種慧放開(kāi)發(fā)過(guò)程信

息的中心數(shù)據(jù)庫(kù)組合起來(lái)，形成軟件工程環(huán)境。CAS3E的成功產(chǎn)品將最大程度地減少軟件

開(kāi)發(fā)的技術(shù)難度并使軟件開(kāi)發(fā)的質(zhì)量得到保證。

3.2構(gòu)造化分析措施

軟件開(kāi)發(fā)措施是軟件開(kāi)發(fā)過(guò)程所遵照的措施和環(huán)節(jié)，其目的在「有效地得到某些工作產(chǎn)品，

即程序和文檔，并且滿(mǎn)足質(zhì)量規(guī)定。軟件開(kāi)發(fā)措施包括分析措施、設(shè)計(jì)措施和程序設(shè)計(jì)措施。

一、需求分析與需求分析措施

1、需求分析

軟件需求是指顧客對(duì)目的軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。需求分析

的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求的過(guò)程。需求分析將創(chuàng)立所需的數(shù)據(jù)模型、功能

模型和控制模型。

(1)需求分析的定義

A、顧客處理問(wèn)題或到達(dá)目的所需的條件或權(quán)能；

B、系統(tǒng)或系統(tǒng)部件要滿(mǎn)足協(xié)議、原則、規(guī)范或其他正式規(guī)定文檔所需具有的條件或權(quán)能；

C、一種所映A、或B所描述的條件或權(quán)能的文檔闡明。

由需求體魄定義可知，需求分析的內(nèi)容包括：提煉、分析和仔細(xì)審查已搜集到的需求；保

證所有利益有關(guān)者都明白其含義并找出其中的錯(cuò)誤、遺漏或其他局限性的地方；從顧客最初

的非形式化需求到滿(mǎn)足顧客對(duì)軟件產(chǎn)品的規(guī)定的映射；對(duì)顧客意圖不停進(jìn)行提醒和判斷。

(2)需求分析階段的工作

需求分析階段的工作，可以概括為四個(gè)方面：

A、需求獲取需求獲取的目的是確定對(duì)目的系統(tǒng)的各方面需求。波及到的重要任

務(wù)是建立獲取顧客需求的措施框架，并支持和監(jiān)控需求獲取的過(guò)程。

B、需求分析對(duì)獲取的需求進(jìn)行分析和綜合，最終給出系統(tǒng)的處理方案和目的系

統(tǒng)的邏輯模型。

C、編寫(xiě)需求規(guī)格闡明書(shū)需求規(guī)格闡明書(shū)作為需求分析的階段成果，可認(rèn)為顧

客、分析人員和設(shè)計(jì)人員之間的交流提供以便，可以直接支持目的軟件系統(tǒng)確實(shí)認(rèn)又可以作

為控制軟件開(kāi)發(fā)進(jìn)程的根據(jù)。

D、需求評(píng)審在需求分析的最終一步，對(duì)需求分析階段的工作進(jìn)行得審，驗(yàn)證

需求文檔的一致性、可行性、完整性和有效性。

2、需求分析措施

常見(jiàn)的需求分析措施有：

A、構(gòu)造化分析措施。重要包括：面向數(shù)據(jù)流的構(gòu)造化分析措施(SA—Structured

analysis)>面向數(shù)據(jù)構(gòu)造的Jackson措施(JSD—Jacksonsystemdevelopmentmethod),面向

數(shù)據(jù)構(gòu)造的構(gòu)造化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)措施(DSSD—Datastructuredsystemdevelopmentmethod)o

B、面向?qū)ο蟮姆治龃胧?OOA—Object-Orientedmethod)(>

從需求分析建立的模型的特性來(lái)分，需求分析措施又分為表態(tài)分析措施和動(dòng)態(tài)分析措施。

二、構(gòu)造化分析措施

1、有關(guān)構(gòu)造化分析措施

構(gòu)造化分析措施是構(gòu)造化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用。

對(duì)于面向數(shù)據(jù)流的構(gòu)造化分析措施，按照DeMarco的定義，”構(gòu)造化分析就是使用數(shù)據(jù)流圖

(DFD)、數(shù)據(jù)字典(DD)、構(gòu)造化英語(yǔ)、鑒定表和羊定樹(shù)等工具，來(lái)建立一種新的、稱(chēng)為

構(gòu)造化規(guī)格闡明的目的文檔。”

構(gòu)造化分析措施的實(shí)質(zhì)是著眼于數(shù)據(jù)流自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)

流圖和數(shù)據(jù)字典為重要工具建立系統(tǒng)的邏輯模型。

構(gòu)造化分析的環(huán)節(jié)如下：

A、通過(guò)對(duì)顧客的調(diào)查，以軟件的需求為線(xiàn)索，獲得目前系統(tǒng)的詳細(xì)模型；

B、去掉詳細(xì)模型中非本質(zhì)原因，抽象出目前系統(tǒng)的邏輯模型；

C、根據(jù)計(jì)算機(jī)的特點(diǎn)分析目前系統(tǒng)與目的系統(tǒng)的差異，建立H的系統(tǒng)的邏輯模型;

D、完善目的系統(tǒng)并補(bǔ)充細(xì)節(jié)，寫(xiě)出目的系統(tǒng)的軟件需求規(guī)格闡明；

E,評(píng)審直到確認(rèn)完全符合顧客對(duì)軟件的需求。

2、構(gòu)造化分析的常用工具

(I)數(shù)據(jù)流圖(DFD—DataFlowDiagram)

數(shù)據(jù)流圖是描述數(shù)據(jù)處理過(guò)程的工具，是需求理解的邏輯模型的圖形表達(dá)，它直接支持系統(tǒng)

的功能建模。

數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度，來(lái)刻畫(huà)數(shù)據(jù)流從輸入到輸出的移動(dòng)變換過(guò)程。數(shù)掂流圖

中的重要圖形元素與闡明如下：

加工(轉(zhuǎn)換)。輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。

數(shù)據(jù)流沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。

存儲(chǔ)文獻(xiàn)(數(shù)據(jù)源)。表達(dá)處理過(guò)程中寄存多種數(shù)據(jù)的文獻(xiàn).

源，潭。表達(dá)系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。

一般通過(guò)對(duì)實(shí)際系統(tǒng)的理解和分析后，使用數(shù)據(jù)流圖為系統(tǒng)建立邏輯模型。建立數(shù)據(jù)流圖的

環(huán)節(jié)如下：

第I步：由外向里：先畫(huà)系統(tǒng)的輸入輸出，然后畫(huà)系統(tǒng)的內(nèi)部。

第2步：自頂向下：次序完畢頂層、中間層、底層數(shù)據(jù)流圖。

第3步：逐層分解。

為保證構(gòu)造的數(shù)據(jù)流圖體現(xiàn)完整、精確、規(guī)范，應(yīng)遵照如下數(shù)據(jù)流圖的構(gòu)造規(guī)則和注意事項(xiàng):

①

對(duì)加工處理建立惟一、層次性的編號(hào)，且每個(gè)加工處理一般規(guī)定既有輸入又有輸

出

②

數(shù)據(jù)存儲(chǔ)之間不應(yīng)當(dāng)有數(shù)據(jù)流；

③

④數(shù)據(jù)流圖的一致性。

父圖、子圖關(guān)系與平衡規(guī)則。

(2)數(shù)據(jù)字典(DD—DataDictionary)

數(shù)據(jù)字典是構(gòu)造化分析措施的關(guān)鍵。數(shù)據(jù)字典是對(duì)所有與系統(tǒng)有關(guān)的數(shù)據(jù)元素的一種有組織

的列表，以及精確的、嚴(yán)格的定義，使得顧客和系統(tǒng)分析員對(duì)于輸入、輸出、存儲(chǔ)成分和中

間計(jì)算成果有共同的理解，數(shù)據(jù)字典把不一樣的需求文檔和分析模型緊密地結(jié)合在一起，與

各模型的圖形表達(dá)配合，能清晰地體現(xiàn)數(shù)據(jù)處理的規(guī)定。

概括地說(shuō)，數(shù)據(jù)字典的作用是對(duì)DFD中出現(xiàn)的被命名的圖形元素確實(shí)切解釋。一般數(shù)據(jù)字

典飲食的信息有：名稱(chēng)，別名、何處作用/怎樣使用、內(nèi)容描述、補(bǔ)充信息等。

(3)鑒定樹(shù)

使用鑒定樹(shù)進(jìn)行描述時(shí)，應(yīng)先從問(wèn)題定義的文字描述中分清哪些是鑒定的條件，哪些是鑒定

的結(jié)論，根據(jù)模仿材料中的連接詞找出鑒定條件之間的附屬關(guān)系、并列關(guān)系、選擇關(guān)系，根

據(jù)它們構(gòu)造鑒定樹(shù)。

(4)鑒定表

鑒定表與鑒定樹(shù)相似，當(dāng)數(shù)據(jù)流圖中的加工要依賴(lài)于多種邏輯條件的聯(lián)歡會(huì)，即完畢該加工

的一組動(dòng)作是由于某一組條件聯(lián)歡會(huì)的組合而引起的，使用鑒定表描述比較合適。鑒定表由

四部分構(gòu)成，基本條件，條件項(xiàng)，基本動(dòng)作，動(dòng)作項(xiàng)

三、軟件需求規(guī)格闡明書(shū)

軟件需求規(guī)格闡明書(shū)(SRS,softwareRequirementSpecification)是需求分析階段的最終成

果，是軟件開(kāi)發(fā)中的文檔之一。

L

軟件需求規(guī)格闡明書(shū)的作用

①

便于顧客、開(kāi)發(fā)人員進(jìn)行理解和交流。

②

③反應(yīng)出顧客問(wèn)題的構(gòu)造，可以作為軟件開(kāi)發(fā)工作的基礎(chǔ)和根據(jù)。

作為確認(rèn)測(cè)試的驗(yàn)收的根據(jù)。

軟件需求規(guī)格闡明書(shū)的內(nèi)容

概述

二、數(shù)據(jù)描述

數(shù)據(jù)流圖

數(shù)據(jù)字典

系統(tǒng)接口闡明

內(nèi)部接口

三、功能描述

功能

處理闡明

設(shè)計(jì)的限制

四、性能描述

性能參數(shù)

測(cè)試種類(lèi)

預(yù)期的軟件響應(yīng)

應(yīng)考虎的特殊問(wèn)題

五、參照文獻(xiàn)目錄

六、附錄

其中，概述是從系統(tǒng)的角度描述軟件的目的和任務(wù)。

數(shù)據(jù)描述是對(duì)軟件系統(tǒng)所必須處理的總是作出的詳細(xì)闡明

功能描述中描述了為處理頤客問(wèn)題所需要的每一項(xiàng)功能的過(guò)程細(xì)節(jié)。對(duì)每一項(xiàng)功能要給出處

理闡明和在設(shè)計(jì)時(shí)需要考慮的限制條件。

在性能描述中闡明系統(tǒng)應(yīng)到達(dá)的性能和應(yīng)當(dāng)滿(mǎn)足的限制條件，檢測(cè)的措施和原則，預(yù)期的軟

件響應(yīng)和也許需要考慮的特殊問(wèn)題。

參照文獻(xiàn)目錄中應(yīng)包括與該軟件有關(guān)所有參照文獻(xiàn)，其口包括前期的其他文檔、技術(shù)參照資

料、產(chǎn)品目錄手冊(cè)以及原則等。

附錄部分包括某些補(bǔ)充資料。

3、軟件需求規(guī)格闡明書(shū)的特點(diǎn)

①軟件需求規(guī)格闡明書(shū)是保證軟件質(zhì)量的有力措施，衡量軟件需求規(guī)格闡明書(shū)質(zhì)量好壞的

原則、原則的優(yōu)先級(jí)及原則的內(nèi)涵是：

②對(duì)的性。體現(xiàn)待開(kāi)發(fā)系統(tǒng)的真實(shí)規(guī)定。

③無(wú)歧義性。對(duì)每一種需求只有一種解釋?zhuān)潢愓f(shuō)具有惟一性。

④完整性。包括所有故意義的需求，功能的、性能的、設(shè)計(jì)的、約束的，屬性或外部接口

等方面的需求。

⑤可驗(yàn)證性。描述的每一種需求都是可以驗(yàn)證的，即存在有限代價(jià)的有效過(guò)程驗(yàn)證確認(rèn)。

@一致性。各個(gè)需求的描述矛盾。

⑦可理解性。需求闡明書(shū)必須簡(jiǎn)要易懂，盡量少包括計(jì)算機(jī)的要領(lǐng)和術(shù)語(yǔ)，以使顧客和軟

件人員都能接受它。

⑧