二級(jí)共

公基礎(chǔ)知識(shí)教程

第一章數(shù)據(jù)結(jié)構(gòu)與算法

1.1算法

算法：是指解題方案的準(zhǔn)確而完整的

描述。

算法不等于程序，也不等計(jì)算機(jī)方

法，程序的編制不可能優(yōu)于算法的設(shè)

計(jì)。

算法的基本特征：是一組嚴(yán)謹(jǐn)?shù)囟x

運(yùn)算順序的規(guī)則，每一個(gè)規(guī)則都是有

效的，是明確的，此順序?qū)⒃谟邢薜?/p>

次數(shù)下終止。特征包括：

(1)可行性；

(2)確定性，算法中每一步驟都必

須有明確定義，不充許有模棱兩可的

解釋?zhuān)辉试S有多義性；

(3)有窮性，算法必須能在有限的

時(shí)間內(nèi)做完，即能在執(zhí)行有限個(gè)步驟

后終止，包括合理的執(zhí)行時(shí)間的含

義；

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

算法的基本要素：一是對(duì)數(shù)據(jù)對(duì)象的

運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。

指令系統(tǒng)：一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的

所有指令的集合。

基本運(yùn)算和操作包括：算術(shù)運(yùn)算、邏

輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。

算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)

構(gòu)、循環(huán)結(jié)構(gòu)。

算法基本設(shè)計(jì)方法：列舉法、歸納法、

遞推、遞歸、減斗遞推技術(shù)、回溯法。

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

空間復(fù)雜度。

算法時(shí)間復(fù)雜度是指執(zhí)行算法所需

要的計(jì)算工作量。

算法空間復(fù)雜度是指執(zhí)行這個(gè)算法

所需要的內(nèi)存空間。

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

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

（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所

固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)

構(gòu)；

（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)

元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)

的存儲(chǔ)結(jié)構(gòu)；

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

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元

素的集合。

數(shù)據(jù)的邏輯結(jié)構(gòu)包含：

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

（2）表示各數(shù)據(jù)元素之間的前后件

關(guān)系。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引

等。

線(xiàn)性結(jié)構(gòu)條件：

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

（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，

也最多有一個(gè)后件。

非線(xiàn)性結(jié)構(gòu)：不滿(mǎn)足線(xiàn)性結(jié)構(gòu)條件的

數(shù)據(jù)結(jié)構(gòu)。

1.3線(xiàn)性表及其順序存儲(chǔ)結(jié)構(gòu)

線(xiàn)性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元

素的位置只取決于自己的序號(hào)，元素

之間的相對(duì)位置是線(xiàn)性的。

在復(fù)雜線(xiàn)性表中，由若干項(xiàng)數(shù)據(jù)元素

組成的數(shù)據(jù)元素稱(chēng)為記錄，而由多個(gè)

記錄構(gòu)成的線(xiàn)性表又稱(chēng)為文件。

非空線(xiàn)性表的結(jié)構(gòu)特征：

(1)且只有一個(gè)根結(jié)點(diǎn)al,它無(wú)前

件；

(2)有且只有一個(gè)終端結(jié)點(diǎn)an,它

無(wú)后件；

(3)除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他

所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且

只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱(chēng)為線(xiàn)性

表的長(zhǎng)度，當(dāng)n=0時(shí)，稱(chēng)為空表。

線(xiàn)性表的順序存儲(chǔ)結(jié)構(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)

為第一個(gè)元素的地址，k代表每個(gè)元

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

順序表的運(yùn)算：插入、刪除。(詳

見(jiàn)14—16頁(yè))

1.4棧和隊(duì)列

棧是限定在一端進(jìn)行插入與刪除的

線(xiàn)性表，允許插入與刪除的一端稱(chēng)為

棧頂，不允許插入與刪除的另一端稱(chēng)

為棧底。

棧按照“先進(jìn)后出"（FILO）或“后進(jìn)

先出”（LIFO）組織數(shù)據(jù)，棧具有記

憶作用。用top表示棧頂位置，用

bottom表示棧底。

棧的基本運(yùn)算：（1）插入元素稱(chēng)為入

棧運(yùn)算；（2）刪除元素稱(chēng)為退棧運(yùn)算;

（3）讀棧頂元素是將棧頂元素賦給

一個(gè)指定的變量，此時(shí)指針無(wú)變化。

隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插

入，而在另一端（隊(duì)頭）進(jìn)行刪除的

線(xiàn)性表。Rear指針指向隊(duì)尾,front

指針指向隊(duì)頭。

隊(duì)列是“先進(jìn)行出"（FIFO）或“后進(jìn)

后出”（LILO）的線(xiàn)性表。

隊(duì)列運(yùn)算包括（1）入隊(duì)運(yùn)算：從隊(duì)

尾插入一個(gè)元素；（2）退隊(duì)運(yùn)算：從

隊(duì)頭刪除一個(gè)元素。

循環(huán)隊(duì)列：s=0表示隊(duì)列空，s=l且

front二rear表示隊(duì)列滿(mǎn)

1.5線(xiàn)性鏈表

數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一

個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱(chēng)為存儲(chǔ)

結(jié)點(diǎn)，簡(jiǎn)稱(chēng)結(jié)點(diǎn)。

結(jié)點(diǎn)由兩部分組成：（1）用于存儲(chǔ)數(shù)

據(jù)元素值，稱(chēng)為數(shù)據(jù)域；（2）用于存

放指針，稱(chēng)為指針域，用于指向前一

個(gè)或后一個(gè)結(jié)點(diǎn)。

在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的

存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的

存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)

系可以不一致，而數(shù)據(jù)元素之間的邏

輯關(guān)系是由指針域來(lái)確定的。

鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線(xiàn)性結(jié)

構(gòu)，也可用于表示非線(xiàn)性結(jié)構(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ù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前

件，稱(chēng)為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只

有一個(gè)，稱(chēng)為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱(chēng)為樹(shù)

的根。

在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)

后件，它們都稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。

沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)。

在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件

個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。

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

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

在一個(gè)算術(shù)表達(dá)式中，有運(yùn)算符和運(yùn)

算對(duì)象。一個(gè)運(yùn)算符可以有若干個(gè)運(yùn)

算對(duì)象。例職，取正（+）等只有一

個(gè)運(yùn)算對(duì)象，稱(chēng)為單目運(yùn)算符；二個(gè)

運(yùn)算對(duì)象稱(chēng)為雙目運(yùn)算符，三目運(yùn)算

符。

用樹(shù)來(lái)表示算術(shù)表達(dá)式的原則如下：

表達(dá)式中的每一個(gè)運(yùn)算符在樹(shù)中對(duì)

應(yīng)一個(gè)結(jié)點(diǎn)，稱(chēng)為運(yùn)算符結(jié)點(diǎn)。

運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為

該運(yùn)算符結(jié)點(diǎn)的子樹(shù)（在樹(shù)中的順序

為從左到右）。

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

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

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

二叉樹(shù)是一種很有用的非線(xiàn)性結(jié)構(gòu)。

二就樹(shù)具有以下兩個(gè)特點(diǎn)：

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

每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別

稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。

由以上特點(diǎn)可以看出，在二叉樹(shù)中，

每一個(gè)結(jié)點(diǎn)的度最大為2,即所有子

樹(shù)（左子樹(shù)或右子樹(shù)）也均為二叉樹(shù),

而樹(shù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以

是任意的。另外，二叉樹(shù)中的每一個(gè)

結(jié)點(diǎn)的子樹(shù)被明顯地分為左子樹(shù)與

右子樹(shù)?？梢詻](méi)有其中的一個(gè)，也可

以全沒(méi)有。

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

性質(zhì)1：在二叉樹(shù)的第K層上，最多

有（KN1）個(gè)結(jié)點(diǎn)。

性質(zhì)2：濃度為M的二叉樹(shù)最多有

2m-1個(gè)結(jié)點(diǎn)。

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

m層。

性質(zhì)3：在任意一棵二叉樹(shù)中度為0

的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2

的結(jié)點(diǎn)多一個(gè)。

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其

深度至少為［log2n］+l,其中［log2n］表

示取的整數(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-1個(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)其每

一個(gè)結(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ì)于任

何一個(gè)結(jié)點(diǎn)，若其右分支下的子孫結(jié)

點(diǎn)的最大層次為p,則其左分支下的

子孫結(jié)點(diǎn)的最大層次或?yàn)閜,或?yàn)?/p>

P+lO

由滿(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(V2)o

若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<n,則編號(hào)為k的結(jié)點(diǎn)的右

子結(jié)點(diǎn)編號(hào)為2k+l；否則該結(jié)點(diǎn)無(wú)右

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

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

二叉樹(shù)的遍歷

二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二

叉樹(shù)的所有結(jié)點(diǎn)。

在遍歷二叉樹(shù)的過(guò)程中，一般先遍歷

左子樹(shù)，然后再遍歷右子樹(shù)。

1、前序遍歷（DLR）

所謂前序遍歷是指在訪問(wèn)根結(jié)點(diǎn)、遍

歷左子樹(shù)與遍歷右子樹(shù)這三者中，首

先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最

后遍歷右子樹(shù)；并且，在遍歷左、右

子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍

歷左子樹(shù)，最后遍歷右子樹(shù)。F,C,

A,D,B,E,G,H,P

2、中序遍歷（LDR）

所謂中序遍歷是指在訪問(wèn)根結(jié)點(diǎn)、遍

歷左子樹(shù)與遍歷右子樹(shù)這三者中，首

先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最

后遍歷右子樹(shù)；并且，在遍歷左、右

子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后訪

問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。A,C,

B,D,F,E,H,G,P

3、后序遍歷(LRD)

所謂中序遍歷是指在訪問(wèn)根結(jié)點(diǎn)、遍

歷左子樹(shù)與遍歷右子樹(shù)這三者中，首

先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最

后訪問(wèn)根結(jié)點(diǎn)；并且，在遍歷左、右

子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后遍

歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。A,B,

D,C,H,P,G,E,F

1.7查找技術(shù)

一、順序查找

順序查找又稱(chēng)順序搜索。順序查找一

般是指在線(xiàn)性表中查找指定的元素，

其基本方法如下：從線(xiàn)性表的第一個(gè)

元素開(kāi)始，依次將線(xiàn)性表中的元素與

被查元素進(jìn)行比較，若相等則表示找

到（即查找成功）；若線(xiàn)性表中所有

的元素都與被查元素進(jìn)行了比較但

都不相等，則表示線(xiàn)性表中沒(méi)有要找

的元素（即查找失?。?。

順序查找的效率是很低的。以下兩種

情況只能采用順序查找：

如果線(xiàn)性表無(wú)序表（即表中元素的排

列是無(wú)序的），則不管是順序存儲(chǔ)結(jié)

構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序

查找。

即使是有序線(xiàn)性表，如果采用鏈?zhǔn)酱?/p>

儲(chǔ)結(jié)構(gòu)，也只能用順序查找。

二、二分法查找

二分法查找只適用于存儲(chǔ)的有序表。

在此所說(shuō)的有序表是指線(xiàn)性表的中

元素按值非遞減排列（即從小到大，

但允許相鄰元素值相等）。

設(shè)有序線(xiàn)性表的長(zhǎng)度為n,被查元素

為x,則對(duì)分查找的方法如下：

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

若中間項(xiàng)的值等于X,則說(shuō)明查到，

查找結(jié)束；

若X小于中間項(xiàng)的值，則在線(xiàn)性表的

前半部分（即中間項(xiàng)以前的部分）以

相同的方法進(jìn)行查找；

若X大于中間項(xiàng)的值，則在線(xiàn)性表的

后半部分（即中間項(xiàng)以后的部分）以

相同的方法進(jìn)行查找。

這個(gè)過(guò)程一直進(jìn)行到查找成功或子

表長(zhǎng)度為0（說(shuō)明線(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)之為消去了一個(gè)逆序。放最大

值

然后，從后到前掃描剩下的線(xiàn)性表，

同樣，在掃描過(guò)程中逐次比較相鄰兩

個(gè)元素的大小。若相鄰兩個(gè)元素中，

后面的元素大于前面的元素，則將它

們互換，這樣就又消去了一個(gè)逆序。

放最小值。

重復(fù)上述過(guò)程，直到剩下的線(xiàn)性有變

空為止，此時(shí)的線(xiàn)性表已經(jīng)變?yōu)橛?/p>

序。

假設(shè)線(xiàn)性表的長(zhǎng)為n,則在最壞情況

下，冒泡排序需要經(jīng)過(guò)n/2遍的蔥馨

往后的掃描和n/2遍的從后往前的掃

描，需要的比較的次數(shù)為n(n-l)/2。

2、快速排序法

快速排序法也是種互換類(lèi)的排序法，

但由于它比冒泡排序法的速度快，因

此稱(chēng)之為快速排序法。

基本思想如下：

從線(xiàn)性表中選取一個(gè)元素，設(shè)T,將

線(xiàn)性表后面小于T的元素移到前，而

前大于T的元素移支后面，結(jié)果就將

線(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,而

后面子表中的所有元素均不小于To

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

有序表。

步驟：首先，在表的第一個(gè)，中間一

個(gè)與最后一個(gè)元素中選取中項(xiàng)，設(shè)為

P(K),并將P(K)賦給T,再將表

中的第一個(gè)元素移到P(K)的位置

±o

然后設(shè)置兩個(gè)指針i和j分別指向表

的起始與最后的位置。反復(fù)操作以下

兩步：

(4)將j逐漸減小，并逐次

比較P(j)與T,直到發(fā)現(xiàn)一個(gè)P(j)<T

為止，將P(j)移到P(i)位置上。

(5)將i逐漸減小，并逐次

比較P⑴與T,直到發(fā)現(xiàn)一個(gè)P(i)>T

為止，將P(i)移到P(j)位置上。

上述兩個(gè)操作交替進(jìn)行，直到指針i

與j指向同一個(gè)位置(即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)在要將線(xiàn)性表中第j個(gè)元

素插入到前面的有序子表中，插入過(guò)

程如下：

道德將第j個(gè)元素放到一個(gè)變量T中,

然后從有序子表的最后一個(gè)元素（即

線(xiàn)性表中第j-1個(gè)元素）開(kāi)始，往前

逐個(gè)與T進(jìn)行比較，將大于T的元素

均依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)

一個(gè)元素不大于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)成一個(gè)子

序列。在排序過(guò)程中，逐次減小這個(gè)

增量，最后當(dāng)H減到1時(shí)，進(jìn)行一次

插入排序，排序就完成。增量序列一

般取h=n/2k(k=l,2,...[log2n]，其中n為

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

其效率與增量序列有關(guān)。在最壞情況

下，需要的比較次數(shù)為O（N1.5）o

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

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

基本思想：掃描整個(gè)線(xiàn)性表，從中選

出最小的元素，將它交換到表的最前

面；然后對(duì)剩下的子表采用同樣的方

法，直到子表空為止。

簡(jiǎn)單選擇排序法在最壞情況下需要

比較n（n-l）/2/次。

2、堆排序法

方法：（1）首先將一個(gè)無(wú)序序列建成

堆。

（2）然后將堆頂元素（序列中的最

大項(xiàng)）與堆中最后一個(gè)元素交換（最

大項(xiàng)應(yīng)該在序列的最后）。不考慮已

經(jīng)換到最后的那個(gè)元素，只考慮前n-l

個(gè)元素構(gòu)成的子序，顯然，該子序列

已不是堆，但左、右子樹(shù)仍為堆，可

以將該子序列調(diào)事為堆。反復(fù)做第

（2）步，真到剩下的子序列為空為

止。適用規(guī)模較大的線(xiàn)性表，在最壞

情況下，堆排序需要比較的次數(shù)為0

（nlog2n）o

L7查找技術(shù)

一、順序查找

順序查找又稱(chēng)順序搜索。順序查找一

般是指在線(xiàn)性表中查找指定的元素，

其基本方法如下：從線(xiàn)性表的第一個(gè)

元素開(kāi)始，依次將線(xiàn)性表中的元素與

被查元素進(jìn)行比較，若相等則表示找

到（即查找成功）；若線(xiàn)性表中所有

的元素都與被查元素進(jìn)行了比較但

都不相等，則表示線(xiàn)性表中沒(méi)有要找

的元素（即查找失?。?。

順序查找的效率是很低的。以下兩種

情況只能采用順序查找：

如果線(xiàn)性表無(wú)序表（即表中元素的排

列是無(wú)序的），則不管是順序存儲(chǔ)結(jié)

構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序

查找。

即使是有序線(xiàn)性表，如果采用鏈?zhǔn)酱?/p>

儲(chǔ)結(jié)構(gòu)，也只能用順序查找。

二、二分法查找

二分法查找只適用于存儲(chǔ)的有序表。

在此所說(shuō)的有序表是指線(xiàn)性表的中

元素按值非遞減排列（即從小到大，

但允許相鄰元素值相等）。

設(shè)有序線(xiàn)性表的長(zhǎng)度為n,被查元素

為x,則對(duì)分查找的方法如下：

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

若中間項(xiàng)的值等于X,則說(shuō)明查到，

查找結(jié)束；

若X小于中間項(xiàng)的值，則在線(xiàn)性表的

前半部分（即中間項(xiàng)以前的部分）以

相同的方法進(jìn)行查找；

若X大于中間項(xiàng)的值，則在線(xiàn)性表的

后半部分（即中間項(xiàng)以后的部分）以

相同的方法進(jìn)行查找。

這個(gè)過(guò)程一直進(jìn)行到查找成功或子

表長(zhǎng)度為0（說(shuō)明線(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)之為消去了一個(gè)逆序。放最大

值

然后，從后到前掃描剩下的線(xiàn)性表，

同樣，在掃描過(guò)程中逐次比較相鄰兩

個(gè)元素的大小。若相鄰兩個(gè)元素中，

后面的元素大于前面的元素，則將它

們互換，這樣就又消去了一個(gè)逆序。

放最小值。

重復(fù)上述過(guò)程，直到剩下的線(xiàn)性有變

空為止，此時(shí)的線(xiàn)性表已經(jīng)變?yōu)橛?/p>

序。

假設(shè)線(xiàn)性表的長(zhǎng)為n,則在最壞情況

下，冒泡排序需要經(jīng)過(guò)n/2遍的蔥馨

往后的掃描和n/2遍的從后往前的掃

描，需要的比較的次數(shù)為n(n-l)/2。

2、快速排序法

快速排序法也是種互換類(lèi)的排序法，

但由于它比冒泡排序法的速度快，因

此稱(chēng)之為快速排序法。

基本思想如下：

從線(xiàn)性表中選取一個(gè)元素，設(shè)T,將

線(xiàn)性表后面小于T的元素移到前，而

前大于T的元素移支后面，結(jié)果就將

線(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,而

后面子表中的所有元素均不小于To

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

有序表。

步驟：首先，在表的第一個(gè)，中間一

個(gè)與最后一個(gè)元素中選取中項(xiàng)，設(shè)為

P(K),并將P(K)賦給T,再將表

中的第一個(gè)元素移到P(K)的位置

上。

然后設(shè)置兩個(gè)指針i和j分別指向表

的起始與最后的位置。反復(fù)操作以下

兩步：

(4)將j逐漸減小，并逐次

比較P⑴與T,直到發(fā)現(xiàn)一個(gè)P(j)<T

為止，將P(j)移到P⑴位置上。

(5)將i逐漸減小，并逐次

比較P(i)與T,直到發(fā)現(xiàn)一個(gè)P(i)>T

為止，將P(i)移到P(j)位置上。

上述兩個(gè)操作交替進(jìn)行，直到指針i

與j指向同一個(gè)位置(即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-l元素已

經(jīng)有序，現(xiàn)在要將線(xiàn)性表中第j個(gè)元

素插入到前面的有序子表中，插入過(guò)

程如下：

道德將第j個(gè)元素放到一個(gè)變量T中,

然后從有序子表的最后一個(gè)元素（即

線(xiàn)性表中第j-l個(gè)元素）開(kāi)始，往前

逐個(gè)與T進(jìn)行比較，將大于T的元素

均依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)

一個(gè)元素不大于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)成一個(gè)子

序列。在排序過(guò)程中，逐次減小這個(gè)

增量，最后當(dāng)H減到1時(shí)，進(jìn)行一次

插入排序，排序就完成。增量序列一

般取h=n/2k(k=1,2,...[log2n]淇中n為

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

其效率與增量序列有關(guān)。在最壞情況

下，需要的比較次數(shù)為O(N1.5)o

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

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

基本思想：掃描整個(gè)線(xiàn)性表，從中選

出最小的元素，將它交換到表的最前

面；然后對(duì)剩下的子表采用同樣的方

法，直到子表空為止。

簡(jiǎn)單選擇排序法在最壞情況下需要

比較n（n-1）/2/次。

2、堆排序法

方法：（1）首先將一個(gè)無(wú)序序列建成

堆。

（2）然后將堆頂元素（序列中的最

大項(xiàng)）與堆中最后一個(gè)元素交換（最

大項(xiàng)應(yī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í)間

B)算法程序的長(zhǎng)度

C)算法執(zhí)行過(guò)程中所需要的基本運(yùn)

算次數(shù)D)算法程序中的指令條數(shù)

2、算法的客復(fù)雜度是指

A、算法程序的長(zhǎng)度B、算

法程序中的指令條數(shù)

C、算法程序所占的存儲(chǔ)空間D、算

法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間

3、下列敘述中正確的是

()

A、線(xiàn)性表是線(xiàn)性結(jié)構(gòu)

B、材與隊(duì)列是非線(xiàn)性結(jié)構(gòu)

C、線(xiàn)性鏈表是非線(xiàn)性結(jié)構(gòu)

D、二叉樹(shù)是線(xiàn)性結(jié)構(gòu)

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

()

A、數(shù)據(jù)所占的存儲(chǔ)空間量

B、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表

示

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

D、存儲(chǔ)在外存中的數(shù)據(jù)

5、下列關(guān)于隊(duì)列的敘述中正確的是

()

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

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

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

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

6、下列關(guān)于棧的敘述中正確的是

()

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

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

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

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

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

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

A、ABCDEF

B、DBEAFCC、

ABDECFD、

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+1B、n

C、(n+1)/2

D、n/2

10、喇T的度為4,其中度為1,2,

3,4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,lo

則T中的葉子結(jié)點(diǎn)數(shù)為（）

A、8B、7

C、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ù)中序遍歷結(jié)果為

DBEAFC,前序遍歷結(jié)果為

ABDECF,則后序遍歷結(jié)果

為。

4、在最壞情況下，冒泡排序的時(shí)間

復(fù)雜度為。

5、在一個(gè)容量為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ā)展而言，

主要經(jīng)過(guò)了結(jié)構(gòu)化程序設(shè)計(jì)和面向

對(duì)象的程序設(shè)計(jì)階段。

一般來(lái)講。程序設(shè)計(jì)風(fēng)格是指編寫(xiě)程

序時(shí)所表現(xiàn)出的特點(diǎn)、習(xí)慣和邏輯思

路。程序是由人來(lái)編寫(xiě)的，為了測(cè)試

和維護(hù)程序，往往還要新聞?dòng)浾吆透?/p>

蹤程序，因此程序設(shè)計(jì)的風(fēng)格總體而

言應(yī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)合驴说淖?/p>

釋能夠幫助讀者理解程序。

(3)禮堂組織：為使程序

的結(jié)構(gòu)一目了然，可以在程序中利用

空格、空行、縮進(jìn)待技巧使程序?qū)哟?/p>

清晰。

2、數(shù)據(jù)說(shuō)明的方法

在編寫(xiě)程序時(shí)，需要注意數(shù)據(jù)說(shuō)明的

風(fēng)格，以便使程序中的數(shù)據(jù)說(shuō)明更易

于理解和維護(hù)。一般應(yīng)注意如下幾

八占、、??

(1)數(shù)據(jù)說(shuō)明的次序規(guī)范

化鑒于程序理解、新聞?dòng)浾吆途S護(hù)的

需要，使數(shù)據(jù)說(shuō)明次序固定，可以使

數(shù)據(jù)的發(fā)生容易查找，也有利于測(cè)

試、排錯(cuò)和維護(hù)。

(2)說(shuō)明語(yǔ)句中變量安排

有序化。當(dāng)一個(gè)說(shuō)明語(yǔ)句說(shuō)明多個(gè)變

量時(shí)，變量按照字母順序?yàn)楹谩?/p>

(3)使用注釋來(lái)說(shuō)明復(fù)雜

數(shù)據(jù)的結(jié)構(gòu)。

3、語(yǔ)句的結(jié)構(gòu)

程序應(yīng)該簡(jiǎn)單易懂，語(yǔ)句構(gòu)造應(yīng)該簡(jiǎn)

單直接，不應(yīng)該為提高效率而把語(yǔ)句

復(fù)雜化。一般應(yīng)注意如下：

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

句；

(2)程序編寫(xiě)應(yīng)優(yōu)先考慮

清晰性；

(3)除非對(duì)效率有特殊要

求，程序編寫(xiě)要做清晰第一，效率第

(4)首先要保證程序正確,

然后才要求提高速度；

(5)避免使用臨時(shí)變量而

使程序的可讀性下降；

(6)避免不必要的轉(zhuǎn)移；

(7)盡可能使用庫(kù)函數(shù)；

(8)避免采用復(fù)雜的條件

語(yǔ)句；

(9)盡量減少使用“否定”

條件的條件語(yǔ)句；

(10)數(shù)據(jù)結(jié)構(gòu)要有利于程

序的簡(jiǎn)化；

(11)要模塊化，使模塊功

能盡可能單一化；

(12)利用住處隱蔽，確保

每一個(gè)模塊的獨(dú)立性；

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

序；

(14)不要修補(bǔ)不好的程

序，要重新編寫(xiě)；

4、輸入和輸出

無(wú)論是批處理的輸入和輸出方式，還

是交互式的輸入和輸出方式，在設(shè)計(jì)

和編程時(shí)都應(yīng)該考慮如下原則：

(1)對(duì)所有的輸入數(shù)據(jù)都

要檢驗(yàn)數(shù)據(jù)的合法性；

(2)檢查輸入項(xiàng)的各種重

要組合的合理性；

(3)輸入格式要簡(jiǎn)單，以

使得輸入的步驟和操作盡可能簡(jiǎn)單；

(4)輸入數(shù)據(jù)時(shí)，應(yīng)允許

使用自由格式；

(5)應(yīng)允許缺省值；

(6)輸入一批數(shù)據(jù)時(shí)，最

好使用輸入結(jié)束標(biāo)志；

(7)在以交互式輸入/輸出

方式進(jìn)行輸入時(shí)，要在屏幕上使用提

示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)

據(jù)輸入過(guò)程中的輸入結(jié)束時(shí)，應(yīng)在屏

幕上給出狀態(tài)信息。

(8)當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸

入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格

式與輸入語(yǔ)句的一致性；給所有的輸

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

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

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

結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可

以概括為自頂向下，逐步求精，模塊

化，限制使用goto語(yǔ)句。

1、自頂向下：程序設(shè)計(jì)時(shí),

應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮

全局目標(biāo)，后考慮局部目標(biāo)。不要一

開(kāi)始就過(guò)多追求眾多的細(xì)節(jié)，先從最

上層總目標(biāo)開(kāi)始設(shè)計(jì)，逐步使問(wèn)題具

體化。

2、逐步求精：對(duì)復(fù)雜問(wèn)題,

應(yīng)設(shè)計(jì)一些子目標(biāo)作過(guò)渡，逐步細(xì)

化。

3、模塊化：一個(gè)復(fù)雜問(wèn)題,

肯定是由若干稍簡(jiǎn)單的問(wèn)題構(gòu)成。模

塊化是把程序要解決的總目標(biāo)分解

為分目標(biāo)，再進(jìn)一步分解為具體的小

目標(biāo)，把每個(gè)小目標(biāo)稱(chēng)為一個(gè)模塊。

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

使用goto語(yǔ)句經(jīng)實(shí)驗(yàn)證實(shí)：(1)濫用

GOTO語(yǔ)句確實(shí)有害，應(yīng)晝避免；

(2)完全避免使用GOTO語(yǔ)句也并

非是個(gè)明智的方法，有些地方使用

GOTO語(yǔ)句，會(huì)使程序流程更清楚、

效率更局；

(3)爭(zhēng)論的焦點(diǎn)不應(yīng)該放在是否取

消GOTO語(yǔ)句，而應(yīng)該放在用什么樣

的程序結(jié)構(gòu)上。

其中最關(guān)鍵的是，肯定以提高程序清

晰性為目標(biāo)的結(jié)構(gòu)化方法。

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

1、順序結(jié)構(gòu)：順序結(jié)構(gòu)是簡(jiǎn)單的程

序設(shè)計(jì)，它是最基本、最常用的結(jié)構(gòu),

所謂順序執(zhí)行，就是按照程序語(yǔ)句行

的自然順序，一條語(yǔ)句一條語(yǔ)句地執(zhí)

行程序程序。

2、選擇結(jié)構(gòu)：選擇結(jié)構(gòu)又稱(chēng)為分支

結(jié)構(gòu)，它包括簡(jiǎn)單選擇和多分支選擇

結(jié)構(gòu)，這種結(jié)構(gòu)可以根據(jù)設(shè)定的條

件，判斷應(yīng)該選擇哪一條分支來(lái)執(zhí)行

相應(yīng)的語(yǔ)句序列。

3、重復(fù)結(jié)構(gòu)：重復(fù)結(jié)構(gòu)又稱(chēng)為循環(huán)

結(jié)構(gòu)，它根據(jù)給定的條件，判斷是否

需要重復(fù)執(zhí)行某一相同的或類(lèi)似的

程序段，利用重復(fù)結(jié)構(gòu)可簡(jiǎn)化大量的

程序行。分為兩類(lèi)：一是先判斷后執(zhí)

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

優(yōu)點(diǎn)：一是程序易于理解、使用和維

護(hù)。二是編程工作的效率，降低軟件

開(kāi)發(fā)成本。

三、結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)

用

要注意把握如下要素：

1、使用程序設(shè)計(jì)語(yǔ)言中的

順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)

表示程序的控制邏輯。

2、選用的控制結(jié)構(gòu)只準(zhǔn)許

有一個(gè)入口和一個(gè)出口；

3、程序語(yǔ)句組成容易識(shí)別

的塊，每塊只有一個(gè)入口和一個(gè)出

□;

4、復(fù)雜結(jié)構(gòu)應(yīng)該嵌套的基

本控制結(jié)構(gòu)進(jìn)行組合嵌套來(lái)實(shí)現(xiàn)；

5、語(yǔ)言中所沒(méi)有的控制結(jié)

構(gòu)，應(yīng)該采用前后一致的方法來(lái)模

擬；

6、嚴(yán)格控制GOTO語(yǔ)句的

使用。其意思是指：

(1)用一個(gè)非結(jié)構(gòu)化的程

序設(shè)計(jì)語(yǔ)言去實(shí)現(xiàn)一個(gè)結(jié)構(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)，

提倡用人類(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í)地反映問(wèn)

題域中固有事物及其關(guān)系。

優(yōu)點(diǎn)：1、與人類(lèi)習(xí)慣的思維方法一

致

面向?qū)ο蠓椒ê图夹g(shù)以對(duì)象為核心。

對(duì)象是由數(shù)據(jù)和容許的操作組成的

封裝體，與客觀實(shí)體有直接的關(guān)系。

對(duì)象之間通過(guò)傳遞消息互相聯(lián)系，以

模擬現(xiàn)實(shí)世界中不同事物彼此之間

的聯(lián)系。

面向?qū)ο蟮脑O(shè)計(jì)方法與傳統(tǒng)的面向

過(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ū)ο蟮姆椒ㄩ_(kāi)發(fā)的軟件

穩(wěn)定性比較好

(2)用面向?qū)ο蟮姆椒ㄩ_(kāi)發(fā)的軟件

比較容易修改；

(3)用面向?qū)ο蟮姆椒ㄩ_(kāi)發(fā)的軟件

比較容易理解。

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

二、面向?qū)ο蠓椒ǖ幕靖拍?/p>

1、對(duì)象(object)

對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母?/p>

念。對(duì)象可以用來(lái)表示客觀世界中的

任何實(shí)體，也就是說(shuō)，應(yīng)用領(lǐng)域中有

意義的、與所要解決的問(wèn)題有關(guān)系的

任何事物都可以作為對(duì)象，它既可以

是具體的物理實(shí)體的抽象，也可以是

人為的概念，或者是任何有明確邊界

的意義的東西?？傊?，對(duì)象是對(duì)問(wèn)題

域中某個(gè)實(shí)體的抽象，設(shè)立某個(gè)對(duì)象

就反映軟件系統(tǒng)保存有關(guān)它的信息

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

面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的

對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的

一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單

位，它由一組表示其靜態(tài)特征的屬性

和它可執(zhí)行的一組操作組成。

對(duì)象可以做的操作表示它的動(dòng)態(tài)行

為，在面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O(shè)計(jì)

中，通常把對(duì)象的操作也稱(chēng)為方法或

服務(wù)。

屬性即對(duì)象所包含的信息，它在設(shè)計(jì)

對(duì)象時(shí)確定，一般只能通過(guò)掛靠對(duì)象

的操作來(lái)改變。

操作描述了對(duì)象執(zhí)行的功能，若通過(guò)

消息傳遞，還可以為其他對(duì)象使用。

操作的過(guò)程對(duì)外是封閉的，即用戶(hù)只

能看到這一操作實(shí)施后的結(jié)果。這相

當(dāng)于事先已經(jīng)設(shè)計(jì)好的各種過(guò)程，只

需要調(diào)用就可以了，用戶(hù)不必去關(guān)心

這一過(guò)程是如何編寫(xiě)的。事實(shí)上，這

個(gè)過(guò)程已經(jīng)封裝在對(duì)象中，用戶(hù)也看

不到。對(duì)的這一特性即是對(duì)象的封裝

性。

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

(1)標(biāo)識(shí)惟一性。指對(duì)象

是可區(qū)分的，并且由對(duì)象有的內(nèi)在本

質(zhì)來(lái)區(qū)分，而不是通過(guò)描述來(lái)區(qū)分。

(2)分類(lèi)性。指可以將具

有相同屬性的操作的對(duì)象抽象成類(lèi)。

(3)多太性。指同一個(gè)操

作可以是不同對(duì)象的行為。

(4)封裝性。從外面看只

能看到對(duì)象的外部特性，即只需知道

數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施

加的操作，根本無(wú)需知道數(shù)據(jù)的具體

結(jié)構(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ù)施加的操

作所組成的統(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ì)，而一個(gè)對(duì)象則是其對(duì)

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

要注意的是，當(dāng)使用“對(duì)象”這個(gè)術(shù)語(yǔ)

時(shí)，既可以指一個(gè)具體的對(duì)象，也可

以泛指一般的對(duì)象，但是，當(dāng)使用“實(shí)

例”這個(gè)術(shù)語(yǔ)時(shí)，必然是指一個(gè)具體的

對(duì)象。

例如：Integer是一個(gè)整數(shù)類(lèi)，它描述

了所有整數(shù)的性質(zhì)。因此任何整數(shù)都

是整數(shù)類(lèi)的對(duì)象，而一個(gè)具體的整數(shù)

“123”是類(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)推動(dòng)的，對(duì)象間

的這種相互合作需要一個(gè)機(jī)制協(xié)助

進(jìn)行，這樣的機(jī)制稱(chēng)為“消息”。消息

是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞

信息，它請(qǐng)示對(duì)象執(zhí)行某一處理或回

答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流

的控制流。消息的使用類(lèi)似于函數(shù)調(diào)

用，消息中指定了某一個(gè)實(shí)例，一個(gè)

操作名和一個(gè)參數(shù)表（可空）。接收

消息的實(shí)例執(zhí)行消息中指定的操作，

并將形式參數(shù)數(shù)與參數(shù)表中相應(yīng)的

值結(jié)合起來(lái)。消息傳遞過(guò)程中，由發(fā)

送消息的對(duì)象（發(fā)送對(duì)象）的觸發(fā)操

作產(chǎn)生輸出結(jié)果，作為消息傳送至接

受消息的對(duì)象（接受對(duì)象），引發(fā)接

受消息的對(duì)象一系列的操作。所傳送

的消息實(shí)質(zhì)上是接受對(duì)象所具有的

操作/方法名稱(chēng)，有時(shí)還包括相應(yīng)參

數(shù)。

消息中只包含傳遞者的要求，它告訴

接受者需要做哪些處理，但并不指示

接受者應(yīng)該怎樣完成這些處理。消息

完全由接受者解釋?zhuān)邮苷擢?dú)立決定

采用什么方式完成所需的處理，發(fā)送

者對(duì)接受者不起任何控制作用。一個(gè)

對(duì)象能夠接受不同形式、不同內(nèi)容的

多個(gè)消息；相同形式的消息可以送往

不同的對(duì)象，不同的對(duì)象對(duì)于形式相

同的消息可以有不同的解釋?zhuān)軌蜃?/p>

出不同的反映。一個(gè)對(duì)象可以同時(shí)往

多個(gè)對(duì)象傳遞信息，兩個(gè)對(duì)象也可以

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

例如，一個(gè)汽車(chē)對(duì)象具有“行駛”這項(xiàng)

操作，那么要讓汽車(chē)以時(shí)速50公里

行駛的話(huà)，需傳遞給汽車(chē)對(duì)象“行駛”

及“時(shí)速50公里”的消息。

通常，一個(gè)消息由下述三部分組成：

(1)接收消息的對(duì)象的名

稱(chēng)；

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

消息名);

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

4、繼承(Inheritance)

繼承是面向?qū)ο蟮姆椒ǖ囊粋€(gè)主要

特征。繼承是使用己有的類(lèi)定義作為

基礎(chǔ)建立新類(lèi)的定義技術(shù)。已有的類(lèi)

可當(dāng)作基類(lèi)來(lái)引用，則新類(lèi)相應(yīng)地可

當(dāng)作派生類(lèi)來(lái)引用。

廣義地說(shuō)，繼承是指能夠直接獲得已

有的性質(zhì)和特征，而不必重復(fù)定義它

們。

面向?qū)ο筌浖夹g(shù)的許多強(qiáng)有力的

功能和突出的優(yōu)點(diǎn)，都來(lái)源于把類(lèi)組

成一個(gè)層次結(jié)構(gòu)的系統(tǒng)：一個(gè)類(lèi)的上

層可以有父類(lèi)，下層可以有子類(lèi)。這

種層次結(jié)構(gòu)系統(tǒng)的一個(gè)重要性質(zhì)是

繼承性，一個(gè)類(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,貝嚶C繼承類(lèi)Ao因

此一個(gè)類(lèi)實(shí)際上繼承了它上層的全

部基類(lèi)的特性，也就是說(shuō)，屬于某類(lèi)

的對(duì)象除了具有該類(lèi)所定義的特性

外，還具有該類(lèi)上層全部基類(lèi)定義的

特性。

繼承分為單繼承與多重繼承。單繼承

是指，一個(gè)類(lèi)只允許有一個(gè)父類(lèi)，即

類(lèi)等級(jí)為樹(shù)形結(jié)構(gòu)。多重繼承是指，

一個(gè)類(lèi)允許有多個(gè)父類(lèi)。多重繼承的

類(lèi)可以組合多個(gè)父類(lèi)的性質(zhì)構(gòu)成所

需要的性質(zhì)。因此，功能更強(qiáng)，使用

更方便；便是，使用多重繼承時(shí)要注

意避免二義性。繼承性的優(yōu)點(diǎn)是，相

似的對(duì)象可以共享程序代碼和數(shù)據(jù)

結(jié)構(gòu)，從而大大減少了程序中的冗余

信息，提高軟件的可重用性，便于軟

件個(gè)性維護(hù)。止匕外，繼承性便利用戶(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ī)制不僅增加了面向?qū)ο筌?/p>

件系統(tǒng)的靈活性，進(jìn)一步減少了信息

冗余，而且顯著地提高了軟件的可重

用性和可擴(kuò)充性。當(dāng)擴(kuò)充系統(tǒng)功能增

加新的實(shí)體類(lèi)型時(shí)，只需派生出與新

實(shí)體類(lèi)相應(yīng)的新的子類(lèi)，完全無(wú)需修

改原有的程序代碼，甚至不需要重新

編譯原有的程序。利用多態(tài)性，用戶(hù)

能夠發(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ù)用戶(hù)需求

開(kāi)發(fā)的用程序設(shè)計(jì)語(yǔ)言描述的、適合

計(jì)算機(jī)執(zhí)行的指令（語(yǔ)句）序列。數(shù)

據(jù)是使程序能正常操縱信息的數(shù)據(jù)

結(jié)構(gòu)。文檔是與程序開(kāi)發(fā)、

維護(hù)和使用有關(guān)的圖文資料?？梢?jiàn)軟

件由兩部分組成：一是機(jī)器可執(zhí)行的

程序和數(shù)據(jù)；二是機(jī)器不可執(zhí)行的，

與軟件開(kāi)發(fā)、運(yùn)行、維護(hù)、使用等有

關(guān)的文檔。

渤(GB)中對(duì)計(jì)算機(jī)軟件的定義為:

與計(jì)算機(jī)系統(tǒng)的操作有關(guān)的計(jì)算機(jī)

程序、規(guī)程、規(guī)則，以及可能有的文

件、文檔及數(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ù)雜性高，成本

日申.

了貝O

(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ī)用戶(hù)提供各種服務(wù)的軟件。

支撐軟件是介于系統(tǒng)軟件和應(yīng)用軟

件之間，協(xié)助用戶(hù)開(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ì)量沒(méi)有可靠的保證，軟件已成

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

具體地說(shuō)，在軟件開(kāi)發(fā)和維護(hù)過(guò)程

中，軟件危機(jī)主要表現(xiàn)在：

(1)軟件需求的增長(zhǎng)得不

到滿(mǎn)足。用戶(hù)對(duì)系統(tǒng)不滿(mǎn)意的情況經(jīng)

常發(fā)生。

(2)軟件開(kāi)發(fā)成本和進(jìn)度

無(wú)法控制。開(kāi)發(fā)成本超出預(yù)算，開(kāi)發(fā)

周期大大超過(guò)規(guī)定日期的情況經(jīng)常

發(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í)踐標(biāo)準(zhǔn)的工序。

1993年IEEE（InstituteofElectrical

&ElectronicEngineers,電氣和電子

工程師學(xué)會(huì)）給出了一個(gè)更加綜合的

定義：“將系統(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é)的控制、管理。

軟件工程的核心思想是把軟件產(chǎn)品

看作是一個(gè)工程產(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ò)程(Software

EngineeringProcess)

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ī)

格說(shuō)明。規(guī)定軟件的功能及其運(yùn)行時(shí)

的限制。

(2)D(do)——軟件開(kāi)發(fā)。

產(chǎn)生滿(mǎn)足規(guī)格說(shuō)明的軟件。

(3)C(check)——軟件

確認(rèn)。確認(rèn)軟件能夠滿(mǎn)足客戶(hù)提出的

要求。

(4)A(action)軟件演

進(jìn)。為滿(mǎn)足客戶(hù)的變更要求，軟件必

須在使用的過(guò)程中演進(jìn)。

通常把用戶(hù)的要求轉(zhuǎn)變成軟件產(chǎn)品

的過(guò)程也叫做軟件開(kāi)發(fā)過(guò)程。此過(guò)程

包括對(duì)用戶(hù)的要求進(jìn)行分析，解釋成

軟件需求，把需求變換成設(shè)計(jì)，把設(shè)

計(jì)用代碼來(lái)實(shí)現(xiàn)并進(jìn)行代碼測(cè)試，有

些軟件還需要進(jìn)行代碼安裝和交付

運(yùn)行。

其二，從軟件開(kāi)發(fā)的觀點(diǎn)看，它就是

使用適當(dāng)?shù)馁Y源（包括人員、硬軟件

工具、時(shí)間等），為開(kāi)發(fā)軟件進(jìn)行的

一組開(kāi)發(fā)活動(dòng)，在過(guò)程結(jié)束時(shí)將輸入

（用戶(hù)要求）轉(zhuǎn)化為輸出（軟件產(chǎn)

品O

所以，軟件工程的過(guò)程是將軟件工程

的方法和工具綜合起來(lái)，以達(dá)到合

理、及時(shí)地進(jìn)行計(jì)算機(jī)軟件開(kāi)發(fā)的目

的。軟件工程過(guò)程應(yīng)確定方法使用的

順序、要求交付的文檔資料、為保證

質(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ā)目標(biāo)

和總的要求，給出它的功能、性能、

可靠性以及接口等方面的可能方案，

制定完成開(kāi)發(fā)任務(wù)的實(shí)施計(jì)劃。

(2)需求分析。對(duì)待開(kāi)發(fā)

軟件提出的需求進(jìn)行分析并給出詳

細(xì)定義。編寫(xiě)軟件規(guī)格說(shuō)明書(shū)及初步

的用戶(hù)手冊(cè)，提交評(píng)審。

(3)軟件設(shè)計(jì)。系統(tǒng)設(shè)計(jì)

人員和程序設(shè)計(jì)人員應(yīng)該在反復(fù)理

解軟件需求的基礎(chǔ)上，給出軟件的結(jié)

構(gòu)、模塊和劃分、功能的分配及處理

流程。在系統(tǒng)比軟件復(fù)雜的情況下，

設(shè)計(jì)階段可分解成概要設(shè)計(jì)階段和

詳細(xì)設(shè)計(jì)階段。編寫(xiě)概要設(shè)計(jì)說(shuō)明

書(shū)、詳細(xì)設(shè)計(jì)說(shuō)明書(shū)和測(cè)試計(jì)劃初

稿，提交評(píng)審。

(4)軟件實(shí)現(xiàn)。把軟件設(shè)

計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代

碼。即完成源程序的編碼，編寫(xiě)用戶(hù)

手冊(cè)、操作手冊(cè)等面向用戶(hù)的文檔，

編寫(xiě)單元測(cè)試計(jì)劃。

(5)軟件測(cè)試。在設(shè)計(jì)測(cè)

試用例的基礎(chǔ)上，檢驗(yàn)軟件的各個(gè)組

成部分。編寫(xiě)測(cè)試分析報(bào)告。

(6)運(yùn)行和維護(hù)。將已交

付的軟件投入運(yùn)行，并在運(yùn)行使用中

不斷地維護(hù)，根據(jù)新進(jìn)出的需求進(jìn)行

必要而且可能的擴(kuò)充和刪改。

四、軟件工程的目標(biāo)與原則

1、軟件工程的目標(biāo)

軟件工程的目標(biāo)是，在給定成本、進(jìn)

度的前提下，開(kāi)發(fā)出具有有效性、可

靠性、可理解性、可維護(hù)性、可重用

性、可適應(yīng)性、可移植性、可追蹤性

和可互操作性且滿(mǎn)足用戶(hù)需求的產(chǎn)

品。

軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：

付出較低的開(kāi)發(fā)成本；達(dá)到要求的軟

件功能；取得較好的軟件性能；開(kāi)發(fā)

的軟件易于移植；需要較低的維護(hù)費(fèi)

用；能按時(shí)完成開(kāi)發(fā)，及時(shí)交付使用。

基于軟件工程的目標(biāo)，軟件工程的理

論和技術(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)遵循的策略、原則、步驟和

必須產(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é)，它要求按照預(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è)全新的研究視角，它是從

個(gè)體心理、人類(lèi)行為、組織行為和企

業(yè)文化等角度來(lái)研究軟件管理和軟

件工程的。

2、軟件工程的原則

為了達(dá)到上述的軟件工程目標(biāo)，在軟

件開(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ú)立的成分，一個(gè)獨(dú)立的編程

單位，應(yīng)有良好的接口定義。模塊的

大小要適中，模塊過(guò)大會(huì)使模塊內(nèi)部

的復(fù)雜性增加，不得對(duì)模塊的理解和

個(gè)性也不得模塊的調(diào)試和重用。模塊

太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過(guò)于復(fù)雜，

不利于控制系統(tǒng)的復(fù)雜性。

(4)局部化。要求在一個(gè)

物理模塊內(nèi)集中邏輯上相互關(guān)聯(lián)的

計(jì)算資源，保證模塊間具有松散的耦

合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)驟性，

這有助于控制角的復(fù)雜性。

(5)確定性軟件開(kāi)發(fā)過(guò)程

中所有概念的表達(dá)應(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ī)格

說(shuō)明與系統(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)的正確

性。

五、軟件開(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)境的

使用進(jì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)

是當(dāng)前軟件開(kāi)發(fā)環(huán)境中富有特色的

研究工作和發(fā)展方向。CASE將各種

軟件工具、開(kāi)發(fā)機(jī)器和一個(gè)慧放開(kāi)發(fā)

過(guò)程信息的中心數(shù)據(jù)庫(kù)組合起來(lái)，形

成軟件工程環(huán)境。CAS3E的成功產(chǎn)品

將最大限度地降低軟件開(kāi)發(fā)的技術(shù)

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

3.2結(jié)構(gòu)化分析方法

軟件開(kāi)發(fā)方法是軟件開(kāi)發(fā)過(guò)程所遵

循的方法和步驟，其目的在于有效地

得到一些工作產(chǎn)品，即程序和文檔，

并且滿(mǎn)足質(zhì)量要求。軟件開(kāi)發(fā)方法包

括分析方法、設(shè)計(jì)方法和程序設(shè)計(jì)方

法。

一、需求分析與需求分析方

法

1、需求分析

軟件需求是指用戶(hù)對(duì)目標(biāo)軟件系統(tǒng)

在功能、行為、性能、設(shè)計(jì)約束等方

面的期望。需求分析的任務(wù)是發(fā)現(xiàn)需

求、求精、建模和定義需求的過(guò)程。

需求分析將創(chuàng)建所需的數(shù)據(jù)模型、功

能模型和控制模型。

(1)需求分析的定義

A、用戶(hù)解決問(wèn)題或達(dá)到目標(biāo)所需的

條件或權(quán)能；

B、系統(tǒng)或系統(tǒng)部件要滿(mǎn)足合同、標(biāo)

準(zhǔn)、規(guī)范或其他正式規(guī)定文檔所需具

有的條件或權(quán)能；

C、一種所映A、或B所描述的條件

或權(quán)能的文檔說(shuō)明。

由需求體魄定義可知，需求分析的

內(nèi)容包括：提煉、分析和仔細(xì)審查已

收集到的需求；確保所有利益相關(guān)者

都明白其含義并找出其中的錯(cuò)誤、遺

漏或其他不足的地方；從用戶(hù)最初的

非形式化需求到滿(mǎn)足用戶(hù)對(duì)軟件產(chǎn)

品的要求的映射；對(duì)用戶(hù)意圖不斷進(jìn)

行提示和判斷。

（2）需求分析階段的工作

需求分析階段的工作，可以概括為四

個(gè)方面：

A、需求獲取需求獲取的

目的是確定對(duì)目標(biāo)系統(tǒng)的各方面需

求。涉及到的主要任務(wù)是建立獲取用

戶(hù)需求的方法框架，并支持和監(jiān)控需

求獲取的過(guò)程。

B、需求分析對(duì)獲取的需

求進(jìn)行分析和綜合，最終給出系統(tǒng)的

解決方案和目標(biāo)系統(tǒng)的邏輯模型。

C、編寫(xiě)需求規(guī)格說(shuō)明書(shū)

需求規(guī)格說(shuō)明書(shū)作為需求分析的階

段成果，可以為用戶(hù)、分析人員和設(shè)

計(jì)人員之間的交流提供方便，可以直

接支持目標(biāo)軟件系統(tǒng)的確認(rèn)又可以

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

D、需求評(píng)審在需求分析

的最后一步，對(duì)需求分析階段的工作

進(jìn)行得審，驗(yàn)證需求文檔的一致性、

可行性、完整性和有效性。

2、需求分析方法

常見(jiàn)的需求分析方法有：

A、結(jié)構(gòu)化分析方法。主要

包括：面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法

(SA一Structuredanalysis),面向數(shù)據(jù)

結(jié)構(gòu)的Jackson方法(JSD—Jackson

systemdevelopmentmethod),面向數(shù)

據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法

(DSSD-Datastructuredsystem

developmentmethod)。

B、面向?qū)ο蟮姆治龇椒?/p>

(OOA-Object-Orientedmethod)。

從需求分析建立的模型的特性來(lái)分，

需求分析方法又分為表態(tài)分析方法

和動(dòng)態(tài)分析方法。

二、結(jié)構(gòu)化分析方法

1、關(guān)于結(jié)構(gòu)化分析方法

結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)

理論在軟件需求分析階段的運(yùn)用。

對(duì)于面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法，

按照DeMarco的定義，“結(jié)構(gòu)化分析

就是使用數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字

典（DD）、結(jié)構(gòu)化英語(yǔ)、判定表和羊

定樹(shù)等工具，來(lái)建立一種新的、稱(chēng)為

結(jié)構(gòu)化規(guī)格說(shuō)明的目標(biāo)文檔?！?/p>

結(jié)構(gòu)化分析方法的實(shí)質(zhì)是著眼于數(shù)

據(jù)流自頂向下，逐層分解，建立系統(tǒng)

的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典

為主要工具建立系統(tǒng)的邏輯模型。

結(jié)構(gòu)化分析的步驟如下：

A、通過(guò)對(duì)用戶(hù)的調(diào)查，以

軟件的需求為線(xiàn)索，獲得當(dāng)前系統(tǒng)的

具體模型；

B、去掉具體模型中非本質(zhì)

因素，抽象出當(dāng)前系統(tǒng)的邏輯模型；

C、根據(jù)計(jì)算機(jī)的特點(diǎn)分析

當(dāng)前系統(tǒng)與目標(biāo)系統(tǒng)的差別，建立目

標(biāo)系統(tǒng)的邏輯模型；

D、完善目標(biāo)系統(tǒng)并補(bǔ)充細(xì)

節(jié)，寫(xiě)出目標(biāo)系統(tǒng)的軟件需求規(guī)格說(shuō)

明；

E、評(píng)審直到確認(rèn)完全符合

用戶(hù)對(duì)軟件的需求。

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

(1)數(shù)據(jù)流圖(DFD—Data

FlowDiagram)

數(shù)據(jù)流圖是描述數(shù)據(jù)處理過(guò)程的工

具，是需求理解的邏輯模型的圖形表

示，它直接支持系統(tǒng)的功能建模。

數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度，

來(lái)刻畫(huà)數(shù)據(jù)流從輸入到輸出的移動(dòng)

變換過(guò)程。數(shù)據(jù)流圖中的主要圖形元

素與說(shuō)明如下：

加工（轉(zhuǎn)換）。輸入數(shù)據(jù)經(jīng)加工變換

產(chǎn)生輸出。

數(shù)據(jù)流沿箭頭方向傳送數(shù)據(jù)的

通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。

存儲(chǔ)文件（數(shù)據(jù)源）。表示處理過(guò)程

中存放各種數(shù)據(jù)的文件。

源，潭。表示系統(tǒng)和環(huán)境的接口，屬

系統(tǒng)之外的實(shí)體。

一般通過(guò)對(duì)實(shí)際系統(tǒng)的了解和分析

后，使用數(shù)據(jù)流圖為系統(tǒng)建立邏輯模

型。建立數(shù)據(jù)流圖的步驟如下：

第1步：由外向里：先畫(huà)系統(tǒng)的輸入

輸出，然后畫(huà)系統(tǒng)的內(nèi)部。

第2步：自頂向下：順序完成頂層、

中間層、底層數(shù)據(jù)流圖。

第3步：逐層分解。

為保證構(gòu)造的數(shù)據(jù)流圖表達(dá)完整、準(zhǔn)

確、規(guī)范，應(yīng)遵循以下數(shù)據(jù)流圖的構(gòu)

造規(guī)則和注意事項(xiàng)：

①對(duì)加工處理建立惟一、層

次性的編號(hào)，且每個(gè)加工處理通常要

求既有輸入又有輸出；

②數(shù)據(jù)存儲(chǔ)之間不應(yīng)該有

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

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

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

則。

(2)數(shù)據(jù)字典(口口一DataDictionary)

數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。

數(shù)據(jù)字典是對(duì)所有與系統(tǒng)相關(guān)的數(shù)

據(jù)元素的一個(gè)有組織的列表，以及精

確的、嚴(yán)格的定義，使得用戶(hù)和系統(tǒng)

分析員對(duì)于輸入、輸出、存儲(chǔ)成分和

中間計(jì)算結(jié)果有共同的理解。數(shù)據(jù)字

典把不同的需求文檔和分析模型緊

密地結(jié)合在一起，與各模型的圖形表

示配合，能清楚地表達(dá)數(shù)據(jù)處理的要

求。

概括地說(shuō)，數(shù)據(jù)字典的作用是對(duì)DFD

中出現(xiàn)的被命名的圖形元素的確切

解釋。通常數(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)于多個(gè)邏輯條件的聯(lián)

歡會(huì)，即完成該加工的一組動(dòng)作是由

于某一組條件聯(lián)歡會(huì)的組合而引發(fā)

的，使用判定表描述比較適宜。判定

表由四部分組成，基本條件，條件項(xiàng),

基本動(dòng)作，動(dòng)作項(xiàng)

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

軟件需求規(guī)格說(shuō)明書(shū)(SRS,software

RequirementSpecification)是需求分

析階段的最后成果，是軟件開(kāi)發(fā)中的

文檔之一。

1、軟件需求規(guī)格說(shuō)明書(shū)的

作用

①便于用戶(hù)、開(kāi)發(fā)人員進(jìn)行

理解和交流。

②反映出用戶(hù)問(wèn)題的結(jié)構(gòu)，

可以作為軟件開(kāi)發(fā)工作的基礎(chǔ)和依

據(jù)。

③作為確認(rèn)測(cè)試的驗(yàn)收的

依據(jù)。

2、軟件需求規(guī)格說(shuō)明書(shū)的

內(nèi)容

一、概述

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

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

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

系統(tǒng)接口說(shuō)明

內(nèi)部接口

三、功能描述

功能

處理說(shuō)明

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

四、性能描述

性能參數(shù)

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

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

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

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

六、附錄

其中，概述是從系統(tǒng)的角度描述軟件

的目標(biāo)和任務(wù)。

數(shù)據(jù)描述是對(duì)