計算機(jī)二級C語言基礎(chǔ)知識與習(xí)題

目錄

全國二級C語言考試大綱

全國二級公共基礎(chǔ)知識考試大綱

公共基礎(chǔ)知識講義

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

第二講數(shù)據(jù)庫設(shè)計基礎(chǔ)

第三講軟件工程基礎(chǔ)

第四講程序設(shè)計基礎(chǔ)

公共基礎(chǔ)知識習(xí)題

數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題

數(shù)據(jù)庫設(shè)計基礎(chǔ)習(xí)題

軟件工程基礎(chǔ)習(xí)題

程序設(shè)計基礎(chǔ)習(xí)題

2009年3月二級C語言筆試真題

2009年3月二級C語言筆試答案

2008年9月二級C語言筆試真題

2008年9月二級C語言筆試答案

2008年4月二級C語言筆試真題

2008年4月二級C語言筆試答案

2007年9月二級C語言筆試真題

2007年9月二級C語言筆試答案

全國二級C語言考試大綱

?基本要求

1.熟悉VisualC++6.0集成開發(fā)環(huán)境。

2.掌握結(jié)構(gòu)化程序設(shè)計的方法，具有良好的程序設(shè)計風(fēng)格。

3.掌握程序設(shè)計中簡單的數(shù)據(jù)結(jié)構(gòu)和算法并能閱讀簡單的程序。

4.在VisualC++6.0集成環(huán)境下，能夠編寫簡單的C程序，并具有基本的糾錯和調(diào)試程

序的能力

?考試內(nèi)容

一、C語言程序的結(jié)構(gòu)

1.程序的構(gòu)成，main函數(shù)和其他函數(shù)。

2.頭文件，數(shù)據(jù)說明，函數(shù)的開始和結(jié)束標(biāo)志以及程序中的注釋。

3.源程序的書寫格式。

4.C語言的風(fēng)格。

二、數(shù)據(jù)類型及其運(yùn)算

1.C的數(shù)據(jù)類型（基本類型，構(gòu)造類型，指針類型，無值類型）及其定義方法。

2.C運(yùn)算符的種類、運(yùn)算優(yōu)先級和結(jié)合性。

3.不同類型數(shù)據(jù)間的轉(zhuǎn)換與運(yùn)算。

4.C表達(dá)式類型（賦值表達(dá)式，算術(shù)表達(dá)式，關(guān)系表達(dá)式，邏輯表達(dá)式，條件表達(dá)式，

逗號表達(dá)式）和求值規(guī)則。

三、基本語句

1.表達(dá)式語句，空語句，復(fù)合語句。

2.輸入輸出函數(shù)的調(diào)用，正確輸入數(shù)據(jù)并正確設(shè)計輸出格式。

四、選擇結(jié)構(gòu)程序設(shè)計

1.用if語句實(shí)現(xiàn)選擇結(jié)構(gòu)。

2.用switch語句實(shí)現(xiàn)多分支選擇結(jié)構(gòu)。

3.選擇結(jié)構(gòu)的嵌套。

五、循環(huán)結(jié)構(gòu)程序設(shè)計

l.for循環(huán)結(jié)構(gòu)。

2.while和do-while循環(huán)結(jié)構(gòu)。

3.continue語句和break語句。

4.循環(huán)的嵌套。

六、數(shù)組的定義和引用

1.一維數(shù)組和二維數(shù)組的定義、初始化和數(shù)組元素的引用。

2.字符串與字符數(shù)組。

七、函數(shù)

1.庫函數(shù)的正確調(diào)用。

2

2.函數(shù)的定義方法。

3.函數(shù)的類型和返回值。

4.形式參數(shù)與實(shí)在參數(shù)，參數(shù)值傳遞。

5.函數(shù)的正確調(diào)用，嵌套調(diào)用，遞歸調(diào)用。

6.局部變量和全局變量。

7.變量的存儲類別（自動，靜態(tài)，寄存器，外部），變量的作用域和生存期。

八、編譯預(yù)處理

1.宏定義和調(diào)用（不帶參數(shù)的宏，帶參數(shù)的宏）。

2.“文件包含”處理。

九、指針

1.地址與指針變量的概念，地址運(yùn)算符與間址運(yùn)算符。

2.一維、二維數(shù)組和字符串的地址以及指向變量、數(shù)組、字符串、函數(shù)、結(jié)構(gòu)體的指針

變量的定義。通過指針引用以上各類型數(shù)據(jù)。

3.用指針作函數(shù)參數(shù)。

4.返回地址值的函數(shù)。

5.指針數(shù)組，指向指針的指針。

十、結(jié)構(gòu)體（即“結(jié)構(gòu)”）與共同體（即“聯(lián)合”）

1.用typedef說明一個新類型。

2.結(jié)構(gòu)體和共用體類型數(shù)據(jù)的定義和成員的引用。

3.通過結(jié)構(gòu)體構(gòu)成鏈表，單向鏈表的建立，結(jié)點(diǎn)數(shù)據(jù)的輸出、刪除與插入。

十一、位運(yùn)算

1.位運(yùn)算符的含義和使用。

2.簡單的位運(yùn)算。

十二、文件操作

只要求緩沖文件系統(tǒng)（即高級磁盤I/O系統(tǒng)），對非標(biāo)準(zhǔn)緩沖文件系統(tǒng)（即低級磁盤I/O

系統(tǒng)）不要求。

1.文件類型指針（FILE類型指針）。

2.文件的打開與關(guān)閉（fopen,fclose）。

3.文件的讀寫（fputc,fgetc,fputs,fgets.fread,fwrite.fprintf,fscanf函數(shù)的應(yīng)用），

文件的定位（rewind,fseek函數(shù)的應(yīng)用）。

?考試方式

1.筆試：90分鐘，滿分100分，其中含公共基礎(chǔ)知識部分的30分。

2.上機(jī):90分鐘,滿分100分

3、上機(jī)操作包括：

（1）填空。

（2）改錯。

（3）編程。

3

全國二級公共基礎(chǔ)知識考試大綱

?基本要求

1.掌握算法的基本概念。

2.掌握基本數(shù)據(jù)結(jié)構(gòu)及其操作。

3.掌握基本排序和查找算法。

4.掌握逐步求精的結(jié)構(gòu)化程序設(shè)計方法。

5.掌握軟件工程的基本方法，具有初步應(yīng)用相關(guān)技術(shù)進(jìn)行軟件開發(fā)的能力。

6.掌握數(shù)據(jù)庫的基本知識，了解關(guān)系數(shù)據(jù)庫的設(shè)計。

?考試內(nèi)容

一、基本數(shù)據(jù)結(jié)構(gòu)與算法

I.算法的基本概念；算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。

2.數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與

非線性結(jié)構(gòu)的概念。

3.線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入叮刪除運(yùn)算。

4.棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。

5.線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。

6.樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)：二叉樹的前序、中序和后序遍歷。

7.順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排

序）。

二、程序設(shè)計基礎(chǔ)

1.程序設(shè)計方法與風(fēng)格。

2.結(jié)構(gòu)化程序設(shè)計。

3.面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。

三、軟件工程基礎(chǔ)

1.軟件工程基本概念，軟件生命周期概念，軟件工具與軟件開發(fā)環(huán)境。

2.結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。

3.結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細(xì)設(shè)計。

4.軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實(shí)施，單元測

試、集成測試和系統(tǒng)測試。

5.程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。

四、數(shù)據(jù)庫設(shè)計基礎(chǔ)

1.數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。

2.數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。

3.關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理論。

4.數(shù)據(jù)庫設(shè)計方法和步驟：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略。

?考試方式

公共基礎(chǔ)知識有10道選擇題和5道填空題共三十分

4

公共基礎(chǔ)知識講義

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

1.1算法

1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說，算法是對特定問題求解步驟的

一種描述。

*:算法不等于程序，也不等于計算方法。程序的編制不可能優(yōu)于算法的設(shè)計。

2、算法的基本特征

（1）可行性。針對實(shí)際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。

（2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一

的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。

（3）有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義，一是算法中的操作步驟為

有限個，二是每個步驟都能在有限時間內(nèi)完成。

（4）擁有足夠的情報。算法中各種運(yùn)算總是要施加到各個運(yùn)算對象上，而這些運(yùn)算對

象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。因此，一個算法執(zhí)行的結(jié)

果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入

錯誤時，算法將無法執(zhí)行或執(zhí)行有錯。一般說來，當(dāng)算法擁有足夠的情報時.，此算法才

是有效的；而當(dāng)提供的情報不夠時，算法可能無效。

*:綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有

效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。

3、算法復(fù)雜度主要包括時間更雜度和空間復(fù)雜度。

（1）算法時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，可以用執(zhí)行算法的過程中所

需基本運(yùn)算的執(zhí)行次數(shù)來度量。

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

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

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

2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個方面的問題：

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

數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。

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

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

1）順序存儲。它是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置相鄰的存儲單元里，結(jié)點(diǎn)間的

邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。

2）鏈接存儲。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是

由附加的指針字段表示的。由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。

3）索引存儲：除建立存儲結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識結(jié)點(diǎn)的地址。

5

*：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理

結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以

采用不同的存儲結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。

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

3、數(shù)據(jù)結(jié)構(gòu)的圖形表示

一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表

示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為

數(shù)據(jù)結(jié)點(diǎn)，并簡稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R

中的每一個二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。

4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

（1）線性結(jié)構(gòu)（非空的數(shù)據(jù)結(jié)構(gòu)）條件：1）有且只有一個根結(jié)點(diǎn)；2）每一個結(jié)點(diǎn)最

多有一個前件，也最多有一個后件。

*：常見的線性結(jié)構(gòu)有線性表、棧、隊列和線性鏈表等。

（2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。

*：常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。

1.3線性表及其順序存儲結(jié)構(gòu)

1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相

對位置是線性的。線性表是由n（n2O）個數(shù)據(jù)元素組成的一個有限序列，表中的每一個

數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。

線性表中數(shù)據(jù)元素的個數(shù)稱為線性表的長度。線性表可以為空表。

*：線性表是一種存儲結(jié)構(gòu)，它的存儲方式：順序和鏈?zhǔn)健?/p>

2、線性表的順序存儲結(jié)構(gòu)具有兩個基本特點(diǎn)：（1）線性表中所有元素所占的存儲空間

是連續(xù)的：（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。

*：由此可以看出，在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊

鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機(jī)直接確定第i個結(jié)點(diǎn)的

存儲地址。

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

（1）順序表的插入運(yùn)算：在一般情況下，要在第i（1WiWn）個元素之前插入個新

元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元

素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第

i項(xiàng)。插入結(jié)束后，線性表的長度就增加了1。

*：順性表的插入運(yùn)算時需要移動元素，在等概率情況下，平均需要移動n/2個元素。

（2）順序表的刪除運(yùn)算：在一般情況下，要刪除第i（1WiWn）個元素時，則要從第

i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束

后，線性表的長度就減小了1。

*：進(jìn)行順性表的刪除運(yùn)算時也需要移動元素，在等概率情況下，平均需要移動（n-1）

/2個元素。插入、刪除運(yùn)算不方便。

1.4棧和隊列

1、棧及其基本運(yùn)算

6

棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表。

在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂

元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)后

出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。

棧具有記憶作用。

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

素是將棧頂元素賦給一個指定的變量，此時指針無變化。

棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈?zhǔn)綏！?/p>

2、隊列及其基本運(yùn)算

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

指針（Rear）指向隊尾元素，頭指針（front）指向排頭元素的前一個位置（隊頭）。

隊列是“先進(jìn)先出”或“后進(jìn)后出”的線性表。

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

素。

循環(huán)隊列及其運(yùn)算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位

置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向

隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從頭指針

front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中

的元素。

*：循環(huán)隊列中元素的個數(shù)=e2用0也

1.5線性鏈表

1、線性表順序存儲的缺點(diǎn)：（1）插入或刪除的運(yùn)算效率很低。在順序存儲的線性表中,

插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素；（2）線性表的順序存儲結(jié)構(gòu)下，線

性表的存儲空間不便于擴(kuò)充；（3）線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分

配。

2、線性鏈表：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)、

非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實(shí)現(xiàn)的。因此，在

鏈?zhǔn)酱鎯Ψ绞街校總€結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域;

另一部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一個或后一個結(jié)點(diǎn)（即前件

或后件），如下圖所示：

線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。

在單鏈表中，每一個結(jié)點(diǎn)只有?個指針域，由這個指針只能找到其后件結(jié)點(diǎn)，而不能找

到其前件結(jié)點(diǎn)。因此，在某些應(yīng)用中，對于線性鏈表中的每個結(jié)點(diǎn)設(shè)置兩個指針，一個

稱為左指針，指向其前件結(jié)點(diǎn)；另一個稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱為雙

向鏈表，如下圖所示：

datanext

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

HEADchai???an.\an

⑻結(jié)點(diǎn)結(jié)構(gòu)（b）一個非空的線性鏈表示意圖

左指針數(shù)據(jù)域右指針

（a）結(jié)點(diǎn)結(jié)構(gòu)

AA

HEADa\ai…?n

（b）一個非空的雙向鏈表示意圖

7

3、線性鏈表的基本運(yùn)算

（1）在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個新元素。

*：在線性鏈表中插入元素時，不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，

也不會出現(xiàn)“上溢”現(xiàn)象。

（2）在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。

*：在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可。

（3）將兩個線性鏈表按要求合并成一個線性鏈表。

（4）將一個線性鏈表按要求進(jìn)行分解。

（5）逆轉(zhuǎn)線性鏈表。

（6）復(fù)制線性鏈表。

（7）線性鏈表的排序。

（8）線性鏈表的查找。

*：線性鏈表不能隨機(jī)存取。

4、循環(huán)鏈表及其基本運(yùn)算

在線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個問題，在運(yùn)算過程中

對于空表和對第一個結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。為了克

服線性鏈表的這個缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表。

與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個特點(diǎn)：1）在鏈表中增加了一個

表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)

點(diǎn)，而循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)；2）循環(huán)鏈表中最后一個結(jié)點(diǎn)的指針域不是空,

而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個環(huán)狀鏈。

下圖a是一個非空的循環(huán)鏈表，圖b是一個空的循環(huán)鏈表：

循環(huán)鏈表的優(yōu)點(diǎn)主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指出表中任何一個結(jié)點(diǎn)

的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)：二

是由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點(diǎn)，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點(diǎn)

存在，從而使空表與非空表的運(yùn)算統(tǒng)一。

*：循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個表頭結(jié)點(diǎn)，其插入和刪除運(yùn)算與單鏈表相

同。但它可以從任一結(jié)點(diǎn)出發(fā)來訪問表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空表的運(yùn)算的

統(tǒng)一。

1.6樹與二叉樹

1、樹的基本概念

樹是種簡單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明

顯的層次特性。

在樹結(jié)構(gòu)中，每一個結(jié)點(diǎn)只有一個前件，稱為父結(jié)點(diǎn)。沒有前件的結(jié)點(diǎn)只有一個，稱

8

為樹的根結(jié)點(diǎn)，簡稱樹的根。每一個結(jié)點(diǎn)可以有多個后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒

有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。

在樹結(jié)構(gòu)中，一個結(jié)點(diǎn)所擁有的后件的個數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱

為樹的度。樹的最大層次稱為樹的深度。

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

（1）什么是二叉樹

二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個特點(diǎn)：1）非空二叉樹只有一個根

結(jié)點(diǎn)；2）每一個結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹;

*：根據(jù)二叉樹的概念可知，二叉樹的度可以為0（葉結(jié)點(diǎn)）、1（只有一棵子樹）或2

（有2棵子樹）。

（2）二叉樹的基本性質(zhì)

性質(zhì)1在二叉樹的第k層上，最多有個結(jié)點(diǎn)。

性質(zhì)2深度為m的二叉樹最多有個個結(jié)點(diǎn)。

性質(zhì)3在任意一棵二叉樹中，度數(shù)為0的結(jié)點(diǎn)總比度為2的結(jié)點(diǎn)多一個。

性質(zhì)4具有n個結(jié)點(diǎn)的二叉樹，其深度至少為，其中表示取

的整數(shù)部分。

3、滿二叉樹與完全二叉樹

滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)。

完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右

邊的若干結(jié)點(diǎn)。

*：根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點(diǎn)的個數(shù)為0或1。

下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹：

完全二叉樹還具有如下兩個特性：

性質(zhì)5具有n個結(jié)點(diǎn)的完全二叉樹深度為。

性質(zhì)6設(shè)完全二叉樹共有n個結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）

用自然數(shù)1,2,n給結(jié)點(diǎn)進(jìn)行編號，則對于編號為k（k=1,2,…，n）的結(jié)點(diǎn)有

以下結(jié)論：

①若k=1,則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k>1,則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號為

INT（k/2）?

2m—1

[log]127?+[log]inn2log

789

11121314

356

12

0

4

10789

35

6

12

0

4（a）滿二叉樹（b）完全二叉樹

[10g11277+

9

②若2kWn,則編號為k的左子結(jié)點(diǎn)編號為2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右

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

③若2k+1Wn,則編號為k的右子結(jié)點(diǎn)編號為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。

4、二叉樹的存儲結(jié)構(gòu)

在計算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。

與線性鏈表類似，用于存儲二叉樹中各元素的存儲結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域和指針

域。但在二叉樹中，由于每一個元素可以有兩個后件（即兩個子結(jié)點(diǎn)），因此，用于存

儲二叉樹的存儲結(jié)點(diǎn)的指針域有兩個：一個用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲地址，稱

為左指針域：另一個用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲地址，稱為右指針域。

*：一般二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于滿二叉樹與完全二叉樹來說，可以按層序

進(jìn)行順序存儲。

5、二叉樹的遍歷

二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為以下三

種：

（1）前序遍歷（DLR）：若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點(diǎn)，然后遍

歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時.，仍然先訪問根結(jié)點(diǎn)，然后遍歷

左子樹，最后遍歷右子樹。

（2）中序遍歷（LDR）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪

問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪

問根_____36719結(jié)點(diǎn)，最后遍歷右子樹。A

（3）后序遍歷（LRD）：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍

歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍

歷右子樹，最后訪問根結(jié)點(diǎn)。

1.7查找技術(shù)

查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。

查找結(jié)果：（查找成功：找到；查找不成功：沒找到。）

平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。

1、順序查找

基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進(jìn)行比較，

直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。

在平均情況下，利用順序查找法在線性表中查找?個元素，大約要與線性表中一半的元

素進(jìn)行比較，最壞情況下需要比較n次。

順序查找一個具有n個元素的線性表，其平均復(fù)雜度為。（n）。

下列兩種情況下只能采用順序查找：

1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)?/p>

存儲結(jié)構(gòu)，都只能用順序查找。

2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。

2、二分法查找

10

思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記

錄為止。

前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進(jìn)行。

查找過程：

1）若中間項(xiàng)（中間項(xiàng)mid=（n-1）/2,mid的值四舍五入取整）的值等于x,則說明已查

到；

2）若X小于中間項(xiàng)的值，則在線性表的前半部分查找；

3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。

特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。

*：二分法查找只適用于順序存儲的線性表，且表中元素必須按關(guān)鍵字有序（升序）排

列。對于無序線性表和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用順序查找。在長度為n的有序線性

表中進(jìn)行二分法查找，其時間復(fù)雜度為0（Iog2n）。

1.8排序技術(shù)

排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序

列調(diào)整為有序記錄序列的一種操作。

1、交換類排序法（方法：冒泡排序，快速排序）。

2、插入類排序法（方法：簡單插入排序，希爾排序）。

3、選擇類排序法（方法：簡單選擇排序，堆排序）。

總結(jié)：各種排序法比較：

11

第二講數(shù)據(jù)庫設(shè)計基礎(chǔ)

2.1數(shù)據(jù)庫系統(tǒng)的基本概念

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

（1）數(shù)據(jù)：實(shí)際上就是描述事物的符號記錄。

數(shù)據(jù)的特點(diǎn)：有一定的結(jié)構(gòu)，有型與值之分。數(shù)據(jù)的型給出了數(shù)據(jù)表示的類型，如整型、

實(shí)型、字符型等。而數(shù)據(jù)的值給出了符合給定型的值，如整型（INT）值15。

（2）數(shù)據(jù)庫（DB）：是數(shù)據(jù)的集合，具有統(tǒng)一的結(jié)構(gòu)形式并存放于統(tǒng)一的存儲介質(zhì)內(nèi)，

是多種應(yīng)用數(shù)據(jù)的集成，并可被各個應(yīng)用程序所共享。

數(shù)據(jù)庫存放數(shù)據(jù)是按數(shù)據(jù)所提供的數(shù)據(jù)模式存放的，具有集成與共享的特點(diǎn)，亦即是數(shù)

據(jù)庫集中了各種應(yīng)用的數(shù)據(jù)，進(jìn)行統(tǒng)一的構(gòu)造和存儲，而使它們可被不同應(yīng)用程序所使

用。

（3）數(shù)據(jù)庫管理系統(tǒng)（DBMS）：一種系統(tǒng)軟件，負(fù)責(zé)數(shù)據(jù)庫中的數(shù)據(jù)組織、數(shù)據(jù)操縱、

數(shù)據(jù)維護(hù)、控制及保護(hù)和數(shù)據(jù)服務(wù)等，是數(shù)據(jù)庫的核心。

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

1）數(shù)據(jù)模式定義。數(shù)據(jù)庫管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)庫構(gòu)建模式，也就是為數(shù)據(jù)庫構(gòu)建其數(shù)

據(jù)框架。

2）數(shù)據(jù)存取的物理構(gòu)建。數(shù)據(jù)庫管理系統(tǒng)負(fù)責(zé)為數(shù)據(jù)模式的物理存取與構(gòu)建提供有效

的存取方法與手段。

3）數(shù)據(jù)操縱。數(shù)據(jù)庫管理系統(tǒng)為用戶使用數(shù)據(jù)庫中的數(shù)據(jù)提供方便，它一般提供如查

詢、插入、修改以及刪除數(shù)據(jù)的功能。此外，它自身還具有做簡單的算術(shù)運(yùn)算及統(tǒng)計的

能力，而且還可以與某些過程性語言結(jié)合，使其具有強(qiáng)大的過程性操作能力。

4）數(shù)據(jù)的完整性、安生性定義與檢查。數(shù)據(jù)庫中的數(shù)據(jù)具有內(nèi)在語義上的關(guān)聯(lián)性與一

致性，它們構(gòu)成了數(shù)據(jù)的完整性，數(shù)據(jù)的完整性是保證數(shù)據(jù)庫中數(shù)據(jù)正確的必要條件，

因此必須經(jīng)常檢查以維護(hù)數(shù)據(jù)正確。數(shù)據(jù)庫中的數(shù)據(jù)具有共享性，而數(shù)據(jù)共享可能會引

發(fā)數(shù)據(jù)的非法使用，因此必須要對數(shù)據(jù)正確使用做出必要的規(guī)定，并在使用時做檢查，

這就是數(shù)據(jù)的安全性。數(shù)據(jù)完整性與安全性的維護(hù)是數(shù)據(jù)庫系統(tǒng)的基本功能。

5）數(shù)據(jù)庫的并發(fā)控制與故障恢復(fù)。數(shù)據(jù)庫是一個集成、共享的數(shù)據(jù)集合體，它能為多

個應(yīng)用程序服務(wù)，所以就存在著多個應(yīng)用程序?qū)?shù)據(jù)庫的并發(fā)操作。在并發(fā)操作中如果

不加控制和管理，多個應(yīng)用程序間就會相互干擾，從而對數(shù)據(jù)庫中的數(shù)據(jù)造成破壞。因

此，數(shù)據(jù)庫管理系統(tǒng)必須對多個應(yīng)用程序的并發(fā)操作做必要的控制以保證數(shù)據(jù)不受破

壞，這就是數(shù)據(jù)庫的并發(fā)控制。數(shù)據(jù)庫中的數(shù)據(jù)一旦遭到破壞，數(shù)據(jù)庫管理系統(tǒng)必須有

能力及時進(jìn)行恢復(fù)，這就是數(shù)據(jù)庫的故障恢復(fù)。

6）數(shù)據(jù)的服務(wù)。數(shù)據(jù)庫管理系統(tǒng)提供對數(shù)據(jù)庫中數(shù)據(jù)的多種服務(wù)功能，如數(shù)據(jù)拷貝、

轉(zhuǎn)存、重組、性能監(jiān)測、分析等。

（4）數(shù)據(jù)庫管理員（DBA）：對數(shù)據(jù)庫進(jìn)行規(guī)劃、設(shè)計、維護(hù)、監(jiān)視等的專業(yè)管理人

員。

（5）數(shù)據(jù)庫系統(tǒng)（DBS）：由數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、數(shù)據(jù)庫管

理員（人員）、硬件平臺（硬件）、軟件平臺（軟件）五個部分構(gòu)成的運(yùn)行實(shí)體。

12

（6）數(shù)據(jù)庫應(yīng)用系統(tǒng)：由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面三者組成。

*：數(shù)據(jù)庫技術(shù)的根本目標(biāo)是解決數(shù)據(jù)的共享問題。

2、數(shù)據(jù)庫系統(tǒng)的發(fā)展

數(shù)據(jù)庫管理發(fā)展至今已經(jīng)歷了三個階段：人工管理階段、文件系統(tǒng)階段和數(shù)據(jù)庫系統(tǒng)階

段。

下表是數(shù)據(jù)管理三個階段的比較：

人工管理階段文件系統(tǒng)階段數(shù)據(jù)庫系統(tǒng)階段

應(yīng)用背景科學(xué)計算科學(xué)計算、管理大規(guī)模管理

硬件背景無直接存取存儲設(shè)

備

磁盤、磁鼓大容量磁備盤

軟件背景沒有操作系統(tǒng)有文件系統(tǒng)有數(shù)據(jù)庫管理系統(tǒng)

背

景

處理方式批處理聯(lián)機(jī)實(shí)時處理、批處理聯(lián)機(jī)實(shí)時處理、分布處理

批處理

數(shù)據(jù)的管理者用戶（程序員）文件系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)

數(shù)據(jù)面向的對

象

某一應(yīng)用程序某一應(yīng)用現(xiàn)實(shí)世界

數(shù)據(jù)的共享程

度

無共享，冗余度極

大

共享性差，冗余度大共享性高，冗余度小

數(shù)據(jù)的獨(dú)立性不獨(dú)立，完全依賴

于程序

獨(dú)立性差具有高度的物理獨(dú)立性和一

定的邏輯獨(dú)立性

數(shù)據(jù)的結(jié)構(gòu)化無結(jié)構(gòu)記錄內(nèi)有結(jié)構(gòu)，整體無結(jié)

構(gòu)

整體結(jié)構(gòu)化，用數(shù)據(jù)模型描

述

特

點(diǎn)

數(shù)據(jù)控制能力應(yīng)用程序自己控制應(yīng)用程序自己控制由數(shù)據(jù)庫管理系統(tǒng)提供數(shù)據(jù)

安全性、完整性、并發(fā)控制

和恢復(fù)能力

3、數(shù)據(jù)庫系統(tǒng)的基本特點(diǎn)

（1）數(shù)據(jù)的高集成性。

（2）數(shù)據(jù)的高共享性與低冗余性。

*：數(shù)據(jù)庫系統(tǒng)可以減少數(shù)據(jù)冗余，但無法避免?切冗余。

（3）數(shù)據(jù)獨(dú)立性：數(shù)據(jù)獨(dú)立性是數(shù)據(jù)與程序間的互不依賴性，即數(shù)據(jù)庫中數(shù)

據(jù)獨(dú)立于

應(yīng)用程序而不依賴于應(yīng)用程序。也就是說，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)與存取方式的改

變不會影響應(yīng)用程序。

數(shù)據(jù)獨(dú)立性一般分為物理獨(dú)立性與邏輯獨(dú)立性兩級。

1）物理獨(dú)立性：物理獨(dú)立性即是數(shù)據(jù)的物理結(jié)構(gòu)（包括存儲結(jié)構(gòu)，存取方式等）的改

變，如存儲設(shè)備的更換、物理存儲的更換、存取方式改變等都不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu)，

從而不致引起應(yīng)用程序的變化。

2）邏輯獨(dú)立性：數(shù)據(jù)庫總體邏輯結(jié)構(gòu)的改變，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、

改變數(shù)據(jù)間聯(lián)系等，不需要相應(yīng)修改應(yīng)用程序，這就是數(shù)據(jù)的邏輯獨(dú)立性。

13

（4）數(shù)據(jù)統(tǒng)一管理與控制。

數(shù)據(jù)統(tǒng)一管理與控制主要包含以下三個方面：

1）數(shù)據(jù)的完整性檢查：檢查數(shù)據(jù)庫中數(shù)據(jù)的正確性以保證數(shù)據(jù)的正確。

2）數(shù)據(jù)的安全性保護(hù)：檢查數(shù)據(jù)庫訪問者以防止非法訪問。

3）并發(fā)控制：控制多個應(yīng)用的并發(fā)訪問所產(chǎn)生的相互干擾以保證其正確性。

4,數(shù)據(jù)庫系統(tǒng)的內(nèi)部結(jié)構(gòu)體系

（1）數(shù)據(jù)庫系統(tǒng)的三級模式：

1）概念模式：數(shù)據(jù)庫系統(tǒng)中全局?jǐn)?shù)據(jù)邏輯結(jié)構(gòu)的描述，是全體用戶（應(yīng)用）公共數(shù)據(jù)

視圖。

2）外模式：也稱子模式或用戶模式，它是用戶的數(shù)據(jù)視圖，也就是用戶所見到的數(shù)據(jù)

模式，它由概念模式推導(dǎo)而出。

3）內(nèi)模式：又稱物理模式，它給出了數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法。內(nèi)模式的

物理性主要體現(xiàn)在操作系統(tǒng)及文件級上，它還未深入到設(shè)備級上（如磁盤及磁盤操作）。

內(nèi)模式對一般用戶是透明的，但它的設(shè)計直接影響數(shù)據(jù)庫的性能。

（2）數(shù)據(jù)庫系統(tǒng)的兩級映射：

1）概念模式/內(nèi)模式的映射：實(shí)現(xiàn)了概念模式到內(nèi)模式之間的相互轉(zhuǎn)換。當(dāng)數(shù)據(jù)庫的

存儲結(jié)構(gòu)發(fā)生變化時，通過修改相應(yīng)的概念模式/內(nèi)模式的映射，使得數(shù)據(jù)庫的邏輯模

式不變，其外模式不變，應(yīng)用程序不用修改，從而保證數(shù)據(jù)具有很高的物理獨(dú)立性。

2）外模式/概念模式的映射：實(shí)現(xiàn)了外模式到概念模式之間的相互轉(zhuǎn)換。當(dāng)邏輯模式

發(fā)生變化時，通過修改相應(yīng)的外模式/邏輯模式映射，使得用戶所使用的那部分外模式

不變，從而應(yīng)用程序不必修改，保證數(shù)據(jù)具有較高的邏輯獨(dú)立性。

2.2數(shù)據(jù)模型

1、數(shù)據(jù)模型

（1）數(shù)據(jù)模型的概念：是數(shù)據(jù)特征的抽象，它從抽象層次上描述了系統(tǒng)的靜態(tài)特征、

動態(tài)行為和約束條件，為數(shù)據(jù)庫系統(tǒng)的信息表示與操作提供一個抽象的框架。

（2）數(shù)據(jù)模型所描述的內(nèi)容有三個部分，它們是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作與數(shù)據(jù)約束。

1）數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是所研究的對象類型的集合，包括與數(shù)據(jù)類型、內(nèi)容、性質(zhì)有

關(guān)的對象，以及與數(shù)據(jù)之間聯(lián)系有關(guān)的對象。它用于描述系統(tǒng)的靜態(tài)特性。

2）數(shù)據(jù)操作：數(shù)據(jù)操作是對數(shù)據(jù)庫中各種對象（型）的實(shí)例（值）允許執(zhí)行的操作的

集合，包括操作的含義、符號、操作規(guī)則及實(shí)現(xiàn)操作的語句等。它用于描述系統(tǒng)的動態(tài)

特性。

3）數(shù)據(jù)的約束條件：數(shù)據(jù)的約束條件是一組完整性規(guī)則的集合。完整性規(guī)則是給定的

數(shù)據(jù)模型中數(shù)據(jù)及其聯(lián)系所具有的制約和依存規(guī)則，用以限定符號數(shù)據(jù)模型的數(shù)據(jù)庫狀

態(tài)及狀態(tài)的變化，以保證數(shù)據(jù)的正確、有效和相容。

（3）數(shù)據(jù)模型分為概念模型、邏輯數(shù)據(jù)模型和物理模型三類：

1）概念數(shù)據(jù)模型：簡稱概念模型，是對客觀世界復(fù)雜事物的結(jié)構(gòu)描一述及它

們之間的內(nèi)

在聯(lián)系的刻畫。概念模型主要有：E-R模型（實(shí)體聯(lián)系模型）、擴(kuò)充的E-R模型、面向?qū)?/p>

象模型及謂詞模型等。

14

2）邏輯數(shù)據(jù)模型：又稱數(shù)據(jù)模型，是一種面向數(shù)據(jù)庫系統(tǒng)的模型，該模型著重于在數(shù)

據(jù)庫系統(tǒng)一級的實(shí)現(xiàn)。邏輯數(shù)據(jù)模型主要有：層次模型、網(wǎng)狀模型、關(guān)系模型、面向?qū)?/p>

象模型等。

3）物理數(shù)據(jù)模型：又稱物理模型，它是一種面向計算機(jī)物理表示的模型，此模型給出

了數(shù)據(jù)模型在計算機(jī)上物理結(jié)構(gòu)的表示。

2、實(shí)體聯(lián)系模型及E-R圖

（1）E-R模型的基本概念：

1）實(shí)體：現(xiàn)實(shí)世界中的事物。

2）屬性：事物的特性。

3）聯(lián)系：現(xiàn)實(shí)世界中事物間的關(guān)系。實(shí)體集的關(guān)系有一對一、一對多、多對多的聯(lián)系。

E-R模型三個基本概念之間的聯(lián)接關(guān)系：1）實(shí)體集（聯(lián)系）與屬性間的聯(lián)接關(guān)系；2）

實(shí)體（集）與聯(lián)系。

*：E-R模型的基本成分是實(shí)體和聯(lián)系。

（2）E-R模型的圖示法：

1）實(shí)體集：用矩形表示。

2）屬性：用橢圓形表示。

3）聯(lián)系：用菱形表示。

4）實(shí)體集與屬性間的聯(lián)接關(guān)系：用無向線段表示。

5）實(shí)體集與聯(lián)系間的聯(lián)接關(guān)系：用無向線段表示。

（3）數(shù)據(jù)庫管理系統(tǒng)常見的數(shù)據(jù)模型有層次模型、網(wǎng)狀模型和關(guān)系模型三種。

1)層次模型的基本結(jié)構(gòu)是樹形結(jié)構(gòu)，具有以下特點(diǎn)：A、每棵樹有且僅有一個無雙親結(jié)

點(diǎn)，稱為根；B、樹中除根外所有結(jié)點(diǎn)有且僅有一個雙親。

學(xué)生M選課N課程

學(xué)號

姓名

性別

出生年月

系課號課程名學(xué)分

成績選修時間

管理

部門

銷售

員工商品

15

2)網(wǎng)狀模型是層次模型的一個特例，從圖論上看，網(wǎng)狀模型是??個不加任何條件限制

的無向圖。

3)關(guān)系模型采用二維表來表示，簡稱表，由表框架及表的元組組成。?個二維表就是

一個關(guān)系。

二維表的表框架由n個命名的屬性組成，n稱為屬性元數(shù)。每個屬性有一個取值范圍稱

為值域。表框架對應(yīng)了關(guān)系的模式，即類型的概念。在表框架中按行可以存放數(shù)據(jù)，每

行數(shù)據(jù)稱為元組，實(shí)際上，一個元組是由n個元組分量所組成，每個元組分量是表框架

中每個屬性的

投影值。

學(xué)號姓名性別出生年月班級籍貫

2007102張潔然男07-07-8807動畫1班天津

2007203李一明男05-01-8707播音5班廣西南寧

2007305王麗女04-09-8807管理4班遼寧沈陽

2007406劉宏男10-11-8807新聞3班江蘇南京

*：同一個關(guān)系模型的任兩個元組值不能完全相同。

主碼：或稱為關(guān)鍵字、主鍵，簡稱碼、鍵，表中的一個屬性或幾個屬性的組合、其值能

唯一地標(biāo)識表中一個元組的，稱為關(guān)系的主碼或關(guān)鍵字。例如，學(xué)生的學(xué)號。主碼屬性

不能取空值。

外部關(guān)鍵字：或稱為外鍵，在一個關(guān)系中含有與另一個關(guān)系的關(guān)鍵字相對應(yīng)的屬性組稱

為該關(guān)系的外部關(guān)鍵字。外部關(guān)鍵字取空值或?yàn)橥獠勘碇袑?yīng)的關(guān)鍵字值。例如，在學(xué)

生表中含有的所屬班級名字，是班級表中的關(guān)鍵字屬性，它是學(xué)生表中的外部關(guān)鍵字。

設(shè)備

工人

使用維護(hù)

(a)教學(xué)關(guān)系E-R圖(b)工作與設(shè)備

領(lǐng)導(dǎo)

學(xué)校

領(lǐng)導(dǎo)

教師班組

教學(xué)管理

學(xué)生

16

（4）關(guān)系中的數(shù)據(jù)約束：

1）實(shí)體完整性約束：要求關(guān)系的主鍵中屬性值不能為空值，因?yàn)橹麈I是唯?決定元組

的，如為空值則其唯一性就成為不可能的了。

2）參照完整性約束：關(guān)系之間相互關(guān)聯(lián)的基本約束，不允許關(guān)系引用不存在的元組，

即在關(guān)系中的外鍵要么是所關(guān)聯(lián)關(guān)系中實(shí)際存在的元組，要么為空值。

3）用戶定義的完整性約束：反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語義要求。例

如某個屬性的取值范圍在0—100之間等。

3、從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型

數(shù)據(jù)庫的邏輯設(shè)計的主要工作是將E-R圖轉(zhuǎn)換成指定RDBMS（關(guān)系數(shù)據(jù)庫管理系統(tǒng)）中

的關(guān)系模式。首先，從E-R圖到關(guān)系模式的轉(zhuǎn)換是比較直接的，實(shí)體與聯(lián)系都可以表示

成關(guān)系，E-R圖中屬性也可以轉(zhuǎn)換成關(guān)系的屬性。實(shí)體集也可以轉(zhuǎn)換成關(guān)系。

2.3關(guān)系代數(shù)

1、關(guān)系的數(shù)據(jù)結(jié)構(gòu)

關(guān)系是由若干個不同的元組所組成，因此關(guān)系可視為元組的集合。n元關(guān)系是一個n元

有序組的集合。

關(guān)系模型的基本運(yùn)算：1）插入；2）刪除；3）修改；4）查詢（包括投影、選擇、笛卡

爾積運(yùn)算）。

2、關(guān)系操縱

關(guān)系模型的數(shù)據(jù)操縱即是建立在關(guān)系上的數(shù)據(jù)操縱，一般有查詢、增加、刪除和修改四

種操作。

3、集合運(yùn)算及選擇、投影、連接運(yùn)算

（1）并（U）：關(guān)系R和S具有相同的關(guān)系模式，R和S的并是由屬于R或?qū)儆赟的

元組構(gòu)成的集合。

（2）差（一）：關(guān)系R和S具有相同的關(guān)系模式，R和S的差是由屬于R但不屬于S

的元組構(gòu)成的集合。

（3）交（C）：關(guān)系R和S具有相同的關(guān)系模式，R和S的交是由屬于R且屬于S的

元組構(gòu)成的集合。

（4）廣義笛卡爾積（義）：設(shè)關(guān)系R和S的屬性個數(shù)分別為n、m,則R和S的廣義笛

卡爾

積是一個有（n+m）列的元組的集合。每個元組的前n列來自R的一個元組，后m列來

自S

的一個元組，記為RXS。

*：根據(jù)笛卡爾積的定義：有n元關(guān)系R及m元關(guān)系S,它們分別有p、q個元組，則關(guān)

系R與S經(jīng)笛卡爾積記為RXS,該關(guān)系是一個n+m元關(guān)系，元組個數(shù)是pXq,由R與

S的有序組組合而成。

例：有兩個關(guān)系R和S,分別進(jìn)行并、差、交和廣義笛卡爾積運(yùn)算。

I7

（5）在關(guān)系型數(shù)據(jù)庫管理系統(tǒng)中，基本的關(guān)系運(yùn)算有選擇、投影與聯(lián)接三種操作：

1）選擇：選擇指的是從二維關(guān)系表的全部記錄中，把那些符合指定條件的記錄挑出來。

2）投影：投影是從所有字段中選取一部分字段及其值進(jìn)行操作，它是一種縱向操作。

3）聯(lián)接：聯(lián)接將兩個關(guān)系模式拼接成一個更寬的關(guān)系模式，生成的新關(guān)系中包含滿足

聯(lián)接條件的元組。

2.4數(shù)據(jù)庫設(shè)計方法和步驟

（1）數(shù)據(jù)庫設(shè)計階段包括：需求分析、概念分析、邏輯設(shè)計、物理設(shè)計。

（2）數(shù)據(jù)庫設(shè)計的每個階段都有各自的任務(wù)：

1）需求分析階段：這是數(shù)據(jù)庫設(shè)計的第一個階段，任務(wù)主要是收集和分析數(shù)據(jù)，這一

階段收集到的基礎(chǔ)數(shù)據(jù)和數(shù)據(jù)流圖是下一步設(shè)計概念結(jié)構(gòu)的基礎(chǔ)。

2）概念設(shè)計階段：分析數(shù)據(jù)間內(nèi)在語義關(guān)聯(lián)，在此基礎(chǔ)上建立一個數(shù)據(jù)的抽象模型，

即形成E-R圖。

*：數(shù)據(jù)庫概念設(shè)計的過程包括選擇局部應(yīng)用、視圖設(shè)計和視圖集成。

3）邏輯設(shè)計階段：將E-R圖轉(zhuǎn)換成指定RDBMS中的關(guān)系模式。

4）物理設(shè)計階段：對數(shù)據(jù)庫內(nèi)部物理結(jié)構(gòu)作調(diào)整并選擇合理的存取路徑，以提高數(shù)據(jù)

庫訪問速度及有效利用存儲空間。

18

第三講軟件工程基礎(chǔ)

3.1軟件工程基本概念

1、軟件的相關(guān)概念

計算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。

軟件的特點(diǎn)包括：1）軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性；2）軟件的

生產(chǎn)與硬件不同，它沒有明顯的制作過程；3）軟件在運(yùn)行、使用期間不存在磨損、老

化問題：4）軟件的開發(fā)、運(yùn)行對計算機(jī)系統(tǒng)具有依賴性，受計算機(jī)系統(tǒng)的限制，這導(dǎo)

致了軟件移植的問題；5）軟件復(fù)雜性高，成本昂貴；6）軟件開發(fā)涉及諸多的社會因素。

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

軟件工程源自軟件危機(jī)。所謂軟件危機(jī)是泛指在計算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到

的一系列嚴(yán)重問題。具體的說，在軟件開發(fā)和維護(hù)過程中，軟件危機(jī)主要表現(xiàn)在：

1）軟件需求的增長得不到滿足。用戶對系統(tǒng)不滿意的情況經(jīng)常發(fā)生。

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

情況經(jīng)常發(fā)生。

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

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

5）軟件的成本不斷提高。

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

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

軟件工程是應(yīng)用于計算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐

標(biāo)準(zhǔn)利工序。軟件工程的目的就是要建造一個優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為

以下兩點(diǎn)：

1）軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。

2）軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。

軟件工程的主要思想是將工程化原則運(yùn)用到軟件開發(fā)過程，它包括3個要素：方法、工

具和過程。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具是支持軟件的開發(fā)、管理、文檔

生成；過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理。

軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動。

3、軟件生命周期

軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程。

軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)三個階段：

1）軟件定義階段：包括制定計劃和需求分析。

制定計劃：確定總目標(biāo)；可行性研究；探討解決方案；制定開發(fā)計劃。

需求分析：對待開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)的定義。

2）軟件開發(fā)階段：

軟件設(shè)計：分為概要設(shè)計和詳細(xì)設(shè)計兩個部分。

軟件實(shí)現(xiàn)：把軟件設(shè)計轉(zhuǎn)換成計算機(jī)可以接受的程序代碼。

軟件測試：在設(shè)計測試用例的基礎(chǔ)上檢驗(yàn)軟件的各個組成部分。

19

3）軟件運(yùn)行維護(hù)階段：軟件投入運(yùn)行，并在使用中不斷地維護(hù)，進(jìn)行必要的擴(kuò)充和刪

改。

*：軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階段。

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

（1）軟件工程目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理

解性、

可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的

產(chǎn)品。

（2）軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：付出較低的開發(fā)成本；達(dá)到要求的軟件功能;

取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護(hù)費(fèi)用；能按時完成開發(fā)，

及時交付使用。

（3）軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和

可驗(yàn)證性。

1）抽象：抽象是事物最基本的特性和行為，忽略非本質(zhì)細(xì)節(jié)，采用分層次抽象，自頂

向下，逐層細(xì)化的辦法控制軟件開發(fā)過程的復(fù)雜性。

2）信息隱蔽：采用封裝技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱蔽起來，使模塊接口盡量簡單。

3）模塊化：模塊是程序中相對獨(dú)立的成分，一個獨(dú)立的編程單位，應(yīng)有良好的接口定

義。模塊的大小要適中，模塊過大會使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修

改，也不利于模塊的調(diào)試和重用；模塊太小會導(dǎo)致整個系統(tǒng)表示過于復(fù)雜，不利于控制

系統(tǒng)的復(fù)雜性。

4）局部化：保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)聚性。

5）確定性：軟件開發(fā)過程中所有概念的表達(dá)應(yīng)是確定、無歧義且規(guī)范的。

6）一致性：程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持一致。

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

8）可驗(yàn)證性：應(yīng)遵循容易檢查、測評、評審的原則，以確保系統(tǒng)的正確性。

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

（1）軟件開發(fā)工具

軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開發(fā)的高速度

和高質(zhì)量。軟件開發(fā)工具的發(fā)展是從單項(xiàng)工具的開發(fā)逐步向集成工具發(fā)展的，軟件開發(fā)

工具為軟件工程方法提供了自動的或半自動的軟件支撐環(huán)境。同時，軟件開發(fā)方法的有

效應(yīng)用也必須得到相應(yīng)工具的支持，否則方法將難以有效的實(shí)施。

（2）軟件開發(fā)環(huán)境

軟件開發(fā)環(huán)境（或稱軟件工程環(huán)境）是全面支持軟件開發(fā)全過程的軟件工具集合。

計算機(jī)輔助軟件工程（CASE,ComputerAidedSoftwareEngineering）將各種軟件工

具、開發(fā)機(jī)器和一個存放開發(fā)過程信息的中心數(shù)據(jù)庫組合起來，形成軟件工程環(huán)境。它

將極大降低軟件開發(fā)的技術(shù)難度并保證軟件開發(fā)的質(zhì)量。

3.2結(jié)構(gòu)化分析方法

結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計理論。

1、需求分析

20

需求分析方法有：1）結(jié)構(gòu)化需求分析方法；2）面向?qū)ο蟮姆治龇椒ā?/p>

*：需求分析的任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型，解決“做什么”的問題。

*：需求分析般分為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審四個步驟

進(jìn)行。

2、結(jié)構(gòu)化分析方法

結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計理論在軟件需求分析階段的應(yīng)用。

結(jié)構(gòu)化分析方法的實(shí)質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，

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

結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD）；2）數(shù)據(jù)字典（DD）；3）判定樹；4）判

定表。

數(shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動和處理的過程，它反映了系統(tǒng)必須完成

的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。

上圖是數(shù)據(jù)流圖的基本圖形元素：

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

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

存儲文件（數(shù)據(jù)源）：表示處理過程中存放各種數(shù)據(jù)的文件。

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

畫數(shù)據(jù)流圖的基本步驟：自外向內(nèi)，自頂向下，逐層細(xì)化，完善求精。

下圖是一個數(shù)據(jù)流圖的示例：

數(shù)據(jù)字典：對所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個有組織的列表，以及精確的、嚴(yán)格的

定義，使得用戶和系統(tǒng)分析員對于輸入、輸出、存儲成分和中間計算結(jié)果有共同的理解。

*：數(shù)據(jù)字典的作用是對數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。

*：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。

3、軟件需求規(guī)格說明書（SRS）

軟件需求規(guī)格說明書是需求分析階段的最后成果，通過建立完整的信息描述、詳細(xì)的

功能和行為描述、性能需求和設(shè)計約束的說明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對目標(biāo)軟件的各

種需求。

加工數(shù)據(jù)流存儲文件源、潭

2I

3.3結(jié)構(gòu)化設(shè)計方法

1、軟件設(shè)計的基礎(chǔ)

*：需求分析主要解決“做什么”的問題，而軟件設(shè)計主要解決“怎么做”的問題。

從技術(shù)觀點(diǎn)來看，軟件設(shè)計包括軟件結(jié)構(gòu)設(shè)計、數(shù)據(jù)設(shè)計、接口設(shè)計、過程設(shè)計。

結(jié)構(gòu)設(shè)計：定義軟件系統(tǒng)各主要部件之間的關(guān)系。

數(shù)據(jù)設(shè)計：將分析時創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。

接口設(shè)計：描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信。

過程設(shè)計：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述。

從工程角度來看，軟件設(shè)計分兩步完成，即概要設(shè)計和詳細(xì)設(shè)計。

概要設(shè)計：又稱結(jié)構(gòu)設(shè)計，將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)，確定系統(tǒng)級接口、全局

數(shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫模式。

詳細(xì)設(shè)計：確定每個模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)

構(gòu)的細(xì)節(jié)。

軟件設(shè)計的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨(dú)立性。

1）抽象。抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取出來而不考慮其他細(xì)

節(jié)。

2）模塊化。解決一個復(fù)雜問題時自頂向下逐步把軟件系統(tǒng)劃分成一個個較小的、相對

獨(dú)立但又不相互關(guān)聯(lián)的模塊的過程。

3）信息隱蔽。每個模塊的實(shí)施細(xì)節(jié)對于其他模塊來說是隱蔽的。

4）模塊獨(dú)立性。軟件系統(tǒng)中每個模塊只涉及軟件要求的具體的子功能，而和軟件系統(tǒng)

中其他的模塊的接口是簡單的。

*：模塊分解的主要指導(dǎo)思想是信息隱蔽和模塊獨(dú)立性。

模塊的耦合性和內(nèi)聚性是衡量軟件的模塊獨(dú)立性的兩個定性指標(biāo)。

內(nèi)聚性：是一個模塊內(nèi)部各個元素間彼此結(jié)合的緊密程度的度量。

*：按內(nèi)聚性由弱到強(qiáng)排列，內(nèi)聚可以分為以下幾種：偶然內(nèi)聚、邏輯內(nèi)聚、時間內(nèi)聚、

過程內(nèi)聚、通信內(nèi)聚、順序內(nèi)聚及功能內(nèi)聚。

耦合性：是模塊間互相連接的緊密程度的度量。

*：按耦合性由高到低排列，耦合可以分為以下幾種：內(nèi)容耦合、公共耦合、外部耦合、

控制耦合、標(biāo)記耦合、數(shù)據(jù)耦合以及非直接耦合。

一個設(shè)計良好的軟件系統(tǒng)應(yīng)具有高內(nèi)聚、低耦合的特征。

在結(jié)構(gòu)化程序設(shè)計中，模塊劃分的原則是：模塊內(nèi)具有高內(nèi)聚度，模塊間具有低耦合度。

2、總體設(shè)計（概要設(shè)計）和詳細(xì)設(shè)計

（1）總體設(shè)計（概要設(shè)計）

軟件概要設(shè)計的基本任務(wù)是：1）設(shè)計軟件系統(tǒng)結(jié)構(gòu)；2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計；3）

編寫概要設(shè)計文檔：4）概要設(shè)計文檔評審。

常用的軟件結(jié)構(gòu)設(shè)計工具是結(jié)構(gòu)圖，也稱程序結(jié)構(gòu)圖。程序結(jié)構(gòu)圖的基本圖符：

模塊用一個矩形表示，箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭

表示模塊調(diào)用過程中來回傳遞的信息。還可用帶實(shí)心圓的箭頭表示傳遞的是控制信息，

空心圓箭心表示傳遞的是數(shù)據(jù)信息。

一般模塊數(shù)據(jù)信息控制信息

22

經(jīng)常使用的結(jié)構(gòu)圖有四種模塊類型：傳入模塊、傳出模塊、變換模塊和協(xié)調(diào)模塊。其表

示形式如下圖：

它們的含義分別是：

傳入模塊：從下屬模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給上級模塊。

傳出模塊：從上級模塊取得數(shù)據(jù)，經(jīng)處理再將其傳送給下屬模塊。

變換模塊：從上級模塊取得數(shù)據(jù)，進(jìn)行特定的處理，轉(zhuǎn)換成其他形式，再傳送給上級

模塊。

協(xié)調(diào)模塊：對所有下屬模塊進(jìn)行協(xié)調(diào)和管理的模塊。

程序結(jié)構(gòu)圖的例圖及有關(guān)術(shù)語列舉如下：

深度：表示控制的層數(shù)。

上級模塊、從屬模塊：上、下兩層模塊a和b,且有a調(diào)用b,貝Ua是上級模塊，b是

從屬模塊。

寬度：整體控制跨度（最大模塊數(shù)的層）的表示。

扇入：調(diào)用?個給定模塊的模塊個數(shù)。

扇出：一個模塊直接調(diào)用的其他模塊數(shù)。

原子模塊：樹中位于葉子結(jié)點(diǎn)的模塊。

面向數(shù)據(jù)流的設(shè)計方法定義了一些不同的映射方法，利用這些方法可以把數(shù)據(jù)流圖變換

成結(jié)構(gòu)圖表示軟件的結(jié)構(gòu)。

數(shù)據(jù)流的類型：大體可以分為兩種類型，變換型和事務(wù)型。

A、變換型：變換型數(shù)據(jù)處理問題的工作過程大致分為三步，即取得數(shù)據(jù)、變換數(shù)據(jù)和

輸出數(shù)據(jù)。變換型系統(tǒng)結(jié)構(gòu)圖由輸入、中心變換、輸出三部分組成。

B、事務(wù)型：事務(wù)型數(shù)據(jù)處理問題的工作機(jī)理是接受一項(xiàng)事務(wù)，根據(jù)事務(wù)處理的特點(diǎn)和

性質(zhì)，選擇分派一個適當(dāng)?shù)奶幚韱卧?，然后給出結(jié)果。

23

（2）詳細(xì)設(shè)計

詳細(xì)設(shè)計是為軟件結(jié)構(gòu)圖中的每一個模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的

表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。

*：詳細(xì)設(shè)計的任務(wù)是確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，不同于編碼或編程。

常用的過程設(shè)計（即詳細(xì)設(shè)計）工具有以下幾種：

圖形工具：程序流程圖、N-S（方盒圖）、PAD（問題分析圖）和HIPO（層次圖+輸入/處

理/輸出圖）。

表格工具：判定表。

語言工具：PDL（偽碼）

3.4軟件測試

1、軟件測試定義：使用人工或自動手段來運(yùn)行或測定某個系統(tǒng)的過程，其目的在于檢

驗(yàn)它是否滿足規(guī)定的需求或是弄清預(yù)期結(jié)果與實(shí)際結(jié)果之間的差別。

*：軟件測試的目的：盡可能地多發(fā)現(xiàn)程序中的錯誤，不能也不可能證明程序沒有錯誤。

軟件測試的關(guān)鍵是設(shè)計測試用例，?個好的測試用例能找到迄今為止尚未發(fā)現(xiàn)的錯誤。

2、軟件測試方法：靜態(tài)測試和動態(tài)測試。

靜態(tài)測試：包括代碼檢查、靜態(tài)結(jié)構(gòu)分析、代碼質(zhì)量度量。不實(shí)際運(yùn)行軟件，主要通

過人工進(jìn)行。

動態(tài)測試：是基于計算機(jī)的測試，主要包括白盒測試方法和黑盒測試方法。

（1）白盒測試

白盒測試方法也稱為結(jié)構(gòu)測試或邏輯驅(qū)動測試。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢

查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計規(guī)格要求。

白盒測試的基本原則：保證所測模塊中每一獨(dú)立路徑至少執(zhí)行?次：保證所測模塊所有

判斷的每一分支至少執(zhí)行一次；保證所測模塊每?循環(huán)都在邊界條件和一般條件下至少

各執(zhí)行一次；驗(yàn)證所有內(nèi)部數(shù)據(jù)結(jié)構(gòu)的有效性。

*：白盒測試法的測試用例是根據(jù)程序的內(nèi)部邏輯來設(shè)計的，主要用軟件的單元測試，

主要方法有邏輯覆蓋、基本路徑測試等。

A、邏輯覆蓋。邏輯覆蓋泛指?系列以程序內(nèi)部的邏輯結(jié)構(gòu)為基礎(chǔ)的測試用例設(shè)計技術(shù)。

通常程序中的邏輯表示有判斷、分支、條件等幾種表示方法。

語句覆蓋：選擇足夠的測試用例，使得程序中每一個語句至少都能被執(zhí)行一次。

路徑覆蓋：執(zhí)行足夠的測試用例，使程序中所有的可能的路徑都至少經(jīng)歷一次。

判定覆蓋：使設(shè)計的測試用例保證程序中每個判斷的每個取值分支（T或F）至少經(jīng)歷

一次。

條件覆蓋：設(shè)計的測試用例保證程序中每個判斷的每個條件的可能取值至少執(zhí)行一次。

判斷-條件覆蓋：設(shè)計足夠的測試用例，使判斷中每個條件的所有可能取值至少執(zhí)行一

次，同時每個判斷的所有可能取值分支至少執(zhí)行一次。

*:邏輯覆蓋的強(qiáng)度依次是：語句覆蓋〈路徑覆蓋〈判定覆蓋〈條件覆蓋〈判斷-條件覆蓋。

B、基本路徑測試。其思想和步驟是，根據(jù)軟件過程性描述中的控制流程確定程序的環(huán)

路復(fù)雜性度量，用此度量定義基本路徑集合，并由此導(dǎo)出一組測試用例，對每一條獨(dú)立

執(zhí)行路徑進(jìn)行測試。

24

（2）黑盒測試

黑盒測試方法也稱為功能測試或數(shù)據(jù)驅(qū)動測試。黑盒測試是對軟件已經(jīng)實(shí)現(xiàn)的功能是否

滿足需求進(jìn)行測試和驗(yàn)證。

黑盒測試主要診斷功能不對或遺漏、接口錯誤、數(shù)據(jù)結(jié)構(gòu)或外部數(shù)據(jù)庫訪問錯誤、性能

錯誤、初始化和終止條件錯誤。

黑盒測試不關(guān)心程序內(nèi)部的邏輯，只是根據(jù)程序的功能說明來設(shè)計測試用例，主要方法

有等價類劃分法、邊界值分析法、錯誤推測法等，主要用軟件的確認(rèn)測試。

A、等價類劃分法。這是一種典型的黑盒測試方法，它是將程序的所有可能的輸入數(shù)據(jù)

劃分成若干部分（及若干等價類），然后從每個等價類中選取數(shù)據(jù)作為測試用例。

B、邊界值分析法。它是對各種輸入、輸出范圍的邊界情況設(shè)計測試用例的方法。

C、錯誤推測法。人們可以靠經(jīng)驗(yàn)和直覺推測程序中可能存在的各種錯誤，從而有針對

性地編寫檢查這些錯誤的用例。

3、軟件測試過程一般按4個步驟進(jìn)行：單元測試、集成測試、確認(rèn)測試和系統(tǒng)測試。

（1）單元測試

單元測試是對軟件設(shè)計的最小單位——模塊（程序單元）進(jìn)行正確性檢測的測試，目

的是發(fā)現(xiàn)各模塊內(nèi)部可能存在的各種錯誤。

單元測試根據(jù)程序的內(nèi)部結(jié)構(gòu)來設(shè)計測試用例，其依據(jù)是詳細(xì)設(shè)計說明書和源程序。單

元測試的技術(shù)可以采用靜態(tài)分析和動態(tài)測試。對動態(tài)測試通常以白盒測試為主，輔之以

黑盒測試。

單元測試的內(nèi)容包括：模塊接口測試、局部數(shù)據(jù)結(jié)構(gòu)測試、借誤處理測試和邊界測試。

*：在進(jìn)行單元測試時，要用一些輔助模塊去模擬與被測模塊相聯(lián)系的其他模塊，即為

被測模塊設(shè)計和搭建驅(qū)動模塊和樁模塊。其中，驅(qū)動模塊相當(dāng)于被測模塊的主程序，

它接收測試數(shù)據(jù)，并傳給被測模塊，輸出實(shí)際測試結(jié)果；而樁模塊是模擬其他被調(diào)用

模塊，不必將子模塊的所有功能帶入。

（2）集成測試

集成測試是測試和組裝軟件的過程，它是把模塊在按照設(shè)計要求組裝起來的同時進(jìn)行

測試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯誤。

集成測試的依據(jù)是概要設(shè)計說明書。

集成測試所涉及的內(nèi)容包括：軟件單元的接口測試、全局?jǐn)?shù)據(jù)結(jié)構(gòu)測試、邊界條件和非

法輸入的測試等。

集成測試通常采用兩種方式：非增量方式組裝與增量方式組裝。

非增量方式組裝：也稱為一次性組裝方式。首先對每個模塊分別進(jìn)行模塊測試，然后

再把所有模塊組裝在一起進(jìn)行測試，最終得到要求的軟件系統(tǒng)。

增量方式組裝：又稱漸增式集成方式。首先對一個個模塊進(jìn)行模塊測試，然后將這些

模塊逐步組裝成較大的系統(tǒng)，在組裝的過程中邊連接邊測試，以發(fā)現(xiàn)連接過程中產(chǎn)生的

問題。最后通過增殖逐步組裝成要求的軟件系統(tǒng)。增量方式組裝又包括自頂向下、自底

向上、自頂向下與自底向上相結(jié)合等三種方式。

（3）確認(rèn)測試

確認(rèn)測試的任務(wù)是驗(yàn)證軟件的有效性，即驗(yàn)證軟件的功能和性能及其他特性是否叮用

25

戶的要求一致。

確認(rèn)測試的主要依據(jù)是軟件需求規(guī)格說明書。

確認(rèn)測試主要運(yùn)用黑盒測試法。

（4）系統(tǒng)測試

系統(tǒng)測試的目的在于通過與系統(tǒng)的需求定義進(jìn)行比較，發(fā)現(xiàn)軟件與系統(tǒng)定義不符合或

與之矛盾的地方。

系統(tǒng)測試的測試用例應(yīng)根據(jù)需求分析規(guī)格說明來設(shè)計，并在實(shí)際使用環(huán)境下來運(yùn)行。

系統(tǒng)測試的具體實(shí)施一般包括：功能測試、性能測試、操作測試、配置測試、外部接口

測試、安全性測試等。

3.5程序的調(diào)試

程序調(diào)試的任務(wù)是診斷和改正程序中的錯誤，主要在開發(fā)階段進(jìn)行，調(diào)試程序應(yīng)該由編

制源程序的程序員來完成。

程序調(diào)試的基本步驟：（1）錯誤定位；（2）糾正錯誤；（3）回歸測試。

*：軟件的調(diào)試后要進(jìn)行回歸測試，防止引進(jìn)新的錯誤。

軟件調(diào)試可分為靜態(tài)調(diào)試和動態(tài)調(diào)試。靜態(tài)調(diào)試主要是指通過人的思維來分析源程序代

碼和排錯，是主要的調(diào)試手段，而動態(tài)調(diào)試是輔助靜態(tài)調(diào)試。

對軟件主要的調(diào)試方法可以采用：

（1）強(qiáng)行排錯法?主要方法有：通過內(nèi)存全部打印來排錯：在程序特定部位設(shè)置打印

語句；自動調(diào)試工具。

（2）回溯法。發(fā)現(xiàn)了借誤，分析錯誤征兆，確定發(fā)現(xiàn)“癥狀”的位置。一般用于小程

序。

（3）原因排除法。是通過演繹、歸納和二分法來實(shí)現(xiàn)的。

1）演繹法。根據(jù)已有的測試用例，設(shè)想及枚舉出所有可能出錯的原因作為假設(shè)；然后

再用原始測試數(shù)據(jù)或新的測試，從中逐個排除不可能正確的假設(shè)；最后，再用測試數(shù)據(jù)

驗(yàn)證余下的假設(shè)確定出錯的原因。

2）歸納法。從錯誤征兆著手，通過分析它們之間的關(guān)系來找出錯誤。大致分四步：收

集有關(guān)的數(shù)據(jù)；組織數(shù)據(jù)；提出假一設(shè)；證明假設(shè)。

3）二分法。在程序的關(guān)鍵點(diǎn)給變量賦正確值，然后運(yùn)行程序并檢查程序的輸出。如果

輸出結(jié)果正確，則錯誤原因在程序的前半部分；反之，錯誤原因在程序的后半部分。

第四講程序設(shè)計基礎(chǔ)

4.1程序設(shè)計風(fēng)格

程序設(shè)計的風(fēng)格主要強(qiáng)調(diào)：“清晰第一，效率第二”。主要應(yīng)注重和考慮下述一些因素:

（1）源程序文檔化。

1）符號名的命名。符號名能反映它所代表的實(shí)際東西，應(yīng)有一定的實(shí)際含義。

2）程序的注釋。分為序言性注釋和功能性注釋。

序言性注釋：位于程序開頭部分，包括程序標(biāo)題、程序功能說明、主要算法、接口說明、

26

程序位置、開發(fā)簡歷、程序設(shè)計者、復(fù)審者、復(fù)審日期及修改日期等。

功能性注釋：嵌在源程序體之中，用于描述其后的語句或程序的主要功能。

3）視覺組織。利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?/p>

（2）數(shù)據(jù)說明。1）數(shù)據(jù)說明的次序規(guī)范化；2）說明語句中變量安排有序化；3）使用

注釋來說明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。

（3）語句的結(jié)構(gòu)。1）在一行內(nèi)只寫一條語句；2）程序編寫應(yīng)優(yōu)先考慮清晰性；3）程

序編寫要做到清晰第一，效率第二；4）在保證程序正確的基礎(chǔ)上再要求提高效率；5）

避免使用臨時變量而使程序的可讀性下降；6）避免不必要的轉(zhuǎn)移；7）盡量使用庫函數(shù)；

8）避免采用復(fù)雜的條件語句；9）盡量減少使用“否定”條件語句；10）數(shù)據(jù)結(jié)構(gòu)要有

利于程序的簡化；11）要模塊化，使模塊功能盡可能單一化；12）利用信息隱蔽，確保

每一個模塊的獨(dú)立性：13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；14）不要修補(bǔ)不好的程序，要重新

編寫。

（4）輸入和輸出。1）對輸入數(shù)據(jù)檢驗(yàn)數(shù)據(jù)的合法性；2）檢查輸入項(xiàng)的各種重要組合

的合法性；3）輸入格式要簡單，使得輸入的步驟和操作盡可能簡單；4）輸入數(shù)據(jù)時，

應(yīng)允許使用自由格式；5）應(yīng)允許缺省值；6）輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標(biāo)志；

7）在以交互式輸入/輸出方式進(jìn)行輸入時，要在屏幕上使用提示符明確提示輸入的請求，

同時在數(shù)據(jù)輸入過程中和輸入結(jié)束時，應(yīng)在屏幕上給出狀態(tài)信息；8