二級公共基礎(chǔ)知識二級公共基礎(chǔ)知識二級公共基礎(chǔ)知識第一章算法與數(shù)據(jù)結(jié)構(gòu)第二章程序設(shè)計(jì)基礎(chǔ)第三章軟件工程基礎(chǔ)第四章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)二級公共基礎(chǔ)知識第一章算法與數(shù)據(jù)結(jié)構(gòu)第一章算法與數(shù)據(jù)結(jié)構(gòu)本章要求算法的基本概念、算法復(fù)雜度的概念和意義（時(shí)間復(fù)雜度與空間復(fù)雜度）。數(shù)據(jù)結(jié)構(gòu)的定義、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的圖形表示、線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。線性表的定義、線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。棧和隊(duì)列的定義、棧和隊(duì)列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。樹的基本概念，二叉樹的定義及其存儲結(jié)構(gòu)，二叉樹的前序、中序和后序遍歷。順序查找與二分法查找算法、基本排序算法（交換類排序、選擇類排序與插入類）。第一章算法與數(shù)據(jù)結(jié)構(gòu)本章要求第一章算法與數(shù)據(jù)結(jié)構(gòu)一、算法二、數(shù)據(jù)結(jié)構(gòu)三、線性表四、棧五、隊(duì)列六、線性鏈表七、樹與二叉樹八、查找技術(shù)九、排序技術(shù)第一章算法與數(shù)據(jù)結(jié)構(gòu)一、算法一、算法1.算法的基本概念算法是指為了解決某類問題而規(guī)定的一個(gè)有限長度的操作（指令）序列。（1）算法的特點(diǎn)：

可行性、確定性、有窮性、擁有足夠的情報(bào)。（2）算法的兩個(gè)基本要素：

一是對數(shù)據(jù)對象的運(yùn)算和操作，具體包括算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算和數(shù)據(jù)傳輸?shù)龋?/p>

二是算法的控制結(jié)構(gòu)，具體包括順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。一、算法2.算法的復(fù)雜度算法的復(fù)雜度(代價(jià))是衡量算法好壞的量度，具體可分為兩種:時(shí)間復(fù)雜度和空間復(fù)雜度。（1）時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，即算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù)。

通常記作：

常見的時(shí)間復(fù)雜度有：（2）空間復(fù)雜度是指執(zhí)行該算法所需要的內(nèi)存空間。具體包括（1）算法程序所占的空間；（2）輸入的初始數(shù)據(jù)所占的存儲空間；（3）算法執(zhí)行過程中的額外空間2.算法的復(fù)雜度二、數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

在此概念中:

（1）數(shù)據(jù)是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號的總稱;

（2）數(shù)據(jù)元素是指數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理;

（3）一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成,數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。二、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算。

2.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)的表示方法

表示數(shù)據(jù)的邏輯結(jié)構(gòu)時(shí)必須表示清楚兩個(gè)關(guān)鍵點(diǎn)，一個(gè)是數(shù)據(jù)元素的集合D，另一個(gè)是數(shù)據(jù)元素之間的前后關(guān)系R。

表示數(shù)據(jù)結(jié)構(gòu)的方法有兩種：二元關(guān)系表和圖形表示方法。數(shù)據(jù)結(jié)構(gòu)有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)A.二元關(guān)系表示方法：一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示為B=（D、R），其中R用二元組來表示(a、b)。

a表示前件，b表示后件。

例如，一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成:

B=（D、R）

D={春，夏，秋，冬}

R={（春，夏），（夏，秋），（秋，冬）}B.在圖形表示方法中，用中間標(biāo)有元素值的方框來表示數(shù)據(jù)元素，稱為數(shù)據(jù)結(jié)點(diǎn)，簡稱為結(jié)點(diǎn)；用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)（注意：有時(shí)可以省略箭頭）來表示元素之間的前后關(guān)系。A.二元關(guān)系表示方法：一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示為B=（D、R），例如，同樣是一年四季的數(shù)據(jù)結(jié)構(gòu)，若用圖形方法表示則如圖所示。數(shù)據(jù)的邏輯結(jié)構(gòu)一般分為兩種:線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

線性結(jié)構(gòu)：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。如：一年四季。

非線性結(jié)構(gòu)：線性以外的數(shù)據(jù)結(jié)構(gòu)。如：反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)。例如，同樣是一年四季的數(shù)據(jù)結(jié)構(gòu)，若用圖形方法表示則如圖A.線性結(jié)構(gòu)

①線性表

例:英文字母表(A,B,C,·······，X,Y,Z)

例:學(xué)生成績表

②棧——后進(jìn)先出③隊(duì)列——先進(jìn)先出86胡孝臣986110395劉忠賞9861107100張卓9861109成績姓名學(xué)號A.線性結(jié)構(gòu)

①線性表

例:英文字母表(A,B.非線性結(jié)構(gòu)

①樹形結(jié)構(gòu)

例:全校學(xué)生檔案管理的組織方式

例:計(jì)算機(jī)文件管理系統(tǒng)也是典型的樹形結(jié)構(gòu)B.非線性結(jié)構(gòu)

①樹形結(jié)構(gòu)

例:全校學(xué)生檔案管理的組織方式②圖形結(jié)構(gòu)——結(jié)點(diǎn)間的連結(jié)是任意的

例:數(shù)據(jù)結(jié)構(gòu)B(D,R)

D={1,2,3,4}

R={(1,2),(1,3),(1,4),

(2,3),(3,4),(2,4)}

例:數(shù)據(jù)結(jié)構(gòu)C(D,R)

D={1,2,3}

R={(1,2),(2,3),(3,2),(1,3)}

1423213②圖形結(jié)構(gòu)——結(jié)點(diǎn)間的連結(jié)是任意的

例:數(shù)據(jù)結(jié)構(gòu)B(D3.數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)(又稱物理結(jié)構(gòu)):是指數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)存中的表示，即數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式。數(shù)據(jù)的存儲結(jié)構(gòu)有4種：順序存儲方式、鏈?zhǔn)酱鎯Ψ绞健⑺饕鎯Ψ绞胶蜕⒘写鎯Ψ绞健?/p>

需要注意的是，對于同一個(gè)邏輯結(jié)構(gòu)來說，采用不同的存儲結(jié)構(gòu)時(shí)，其數(shù)據(jù)處理的效率是不同的。4.數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。3.數(shù)據(jù)的存儲結(jié)構(gòu)三、線性表線性表是最簡單的、最常用的一種線性結(jié)構(gòu)。1.線性表的定義:線性表是n個(gè)元素的有限序列，它們之間的關(guān)系可以排成一個(gè)線性序列：a1，a2，……，ai，……，an，其中n稱作表的長度，當(dāng)n=0時(shí)，稱作空表。線性表（非空線性表）必須同時(shí)滿足以下3個(gè)條件：

（1）有且只有一個(gè)根結(jié)點(diǎn)a1，它無前件。

（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件。

（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。三、線性表如下圖所示的數(shù)據(jù)結(jié)構(gòu)就是線性表

注：線性表的概念是從邏輯結(jié)構(gòu)的角度說的，所以，判斷是否為線性表時(shí)并不考慮其存儲結(jié)構(gòu)，線性表可以用四種不同的存儲結(jié)構(gòu)來表示。2.線性表的順序存儲結(jié)構(gòu)

特點(diǎn)：

（1）線性表中所有元素所占的存儲空間是連續(xù)的;

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

如下圖所示的數(shù)據(jù)結(jié)構(gòu)就是線性表例：正確表示線性表(A1，A2，A3，A4)的順序結(jié)構(gòu)是( )

A)

B)

C)

分析：選C，選項(xiàng)C中線性表各元素的存儲空間是連續(xù)的，而且元素的存儲順序與邏輯順序一致。選項(xiàng)A中各元素的物理順序與邏輯順序不同。選項(xiàng)B中各元素所占的存儲空間并不連續(xù)。A1A2A3A4例：正確表示線性表(A1，A2，A3，A4)的順序結(jié)構(gòu)順序存儲存儲地址存儲內(nèi)容an……..ai……..a2a1ADR(a1)ADR(a1)+kADR(a1)+(i-1)×kADR(a1)+(n-1)×kADR(ai)=ADR(a1)+（i-1)×k每個(gè)元素所占用的存儲單元個(gè)數(shù)首地址起始地址基地址在線性表的順序存儲結(jié)構(gòu)中可以計(jì)算各數(shù)據(jù)元素（數(shù)據(jù)起點(diǎn)）的起始地址。順序存儲存儲地址存儲內(nèi)容an……..ai……..a2a1AD順序存儲結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里,具有以下特點(diǎn):

(1)隨機(jī)存取。

(2)作插入或刪除操作時(shí)，需移動大量元素。

(3)長度變化較大時(shí)，需按最大空間分配。

(4)表的容量難以擴(kuò)充。通常定義一個(gè)一維數(shù)組來表示線性表的順序存儲空間。順序存儲結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單3.線性表的順序存儲結(jié)構(gòu)的插入運(yùn)算

設(shè)順序表的結(jié)構(gòu)如圖所示，其插入運(yùn)算的步驟如下：

(1)判斷是否上溢:首先判斷為線性表開辟的存儲空間是否已滿，如果已滿則不能插入，如果未滿則繼續(xù)做第二步。

(2)空出第i個(gè)位置:從最后一個(gè)元素開始到插入的位置上的元素，將其中的每個(gè)元素均依次往后移動一位。

(3)插入:把新元素放入所插入的位置。3.線性表的順序存儲結(jié)構(gòu)的插入運(yùn)算

設(shè)順序表的結(jié)構(gòu)如圖所示，插入位置與需要移動的元素個(gè)數(shù)之間存在著一定的關(guān)系。當(dāng)線性表很大時(shí)，其插入運(yùn)算的效率是比較低的。具體情況如下所述：

(1)最好的情況:如果插入位置在線性表的末尾，即在第n個(gè)元素之后插入新元素，則不需要移動線性表中的其他任何元素。

(2)最壞的情況:如果插入位置在線性表的第1個(gè)元素之前，則需要移動表中的所有元素。

(3)如果插入位置在第i（1≤i≤n）個(gè)元素之前，則原來的第i個(gè)元素之后(包括第i個(gè)元素)的所有元素都必須移動。

(4)在平均情況下，要在線性表中插入一個(gè)新元素，需要移動線性表中一半的元素。（n/2個(gè)）插入位置與需要移動的元素個(gè)數(shù)之間存在著一定的關(guān)系。當(dāng)線性表很3.線性表的順序存儲結(jié)構(gòu)的刪除運(yùn)算

具體運(yùn)算步驟如下:如果刪除第i（1≤i≤n）個(gè)元素，從第i+1個(gè)元素開始直到最后一個(gè)元素，將其中的每個(gè)元素均依次往前移動一位。此時(shí)，線性表的長度變成了n-1。如下圖：3.線性表的順序存儲結(jié)構(gòu)的刪除運(yùn)算

具體運(yùn)算步驟如下:如果刪在線性表的順序存儲結(jié)構(gòu)的刪除運(yùn)算中，刪除一個(gè)數(shù)據(jù)元素之后，應(yīng)移動原來的元素，而且刪除位置與需要移動的元素個(gè)數(shù)之間存在著一定的關(guān)系。所以當(dāng)線性表很大時(shí)，其刪除運(yùn)算的效率也是比較低的。具體情況如下所述：

(1)最好的情況:如果刪除位置在線性表的末尾，即刪除第n個(gè)元素，則不需要移動線性表中的其他任何元素。

(2)最壞的情況:如果刪除線性表的第1個(gè)元素，則需要移動表中的所有元素。

(3)在平均情況下，要?jiǎng)h除線性表中的一個(gè)元素，需要移動表中的(n-1)/2個(gè)元素。在線性表的順序存儲結(jié)構(gòu)的刪除運(yùn)算中，刪除一個(gè)數(shù)據(jù)元素之后，應(yīng)四、棧1.棧的定義：

棧是一種特殊的線性表，特殊在其數(shù)據(jù)操作上，即限定在一端進(jìn)行插入與刪除的線性表。在棧中，允許插入和刪除的一端稱為棧頂，而不允許插入和刪除的另一端稱為棧底。往棧中插入一個(gè)元素叫入棧運(yùn)算（壓棧）從棧中刪除一個(gè)元素稱為退棧運(yùn)算（彈棧）棧的數(shù)據(jù)操作原則是先進(jìn)后出FILO（First

InLastOut）或后進(jìn)先出LIFO。棧具有

一定的記憶作用。四、棧2.棧的存儲結(jié)構(gòu)

在程序設(shè)計(jì)語言中，與普通線性表一樣，用一維數(shù)組作為棧S(l:m)的順序存儲結(jié)構(gòu)，其中m為棧的最大容量。

通常用指針top來指示棧頂?shù)奈恢茫弥羔榖ottom指向棧底。當(dāng)top=0時(shí)為空棧，當(dāng)top等于數(shù)組的最大下標(biāo)值時(shí)則棧滿。3.棧的基本運(yùn)算

有三種:入棧、退棧和讀棧頂元素。

(1)入棧運(yùn)算的步驟：

首先，判斷棧是否為滿，如果滿則不能入棧(方法top=n)；

其次，將棧頂指針進(jìn)一(即top加1)；

2.棧的存儲結(jié)構(gòu)

在程序設(shè)計(jì)語言中，與普通線性表一樣，用一維最后，將新元素放入棧頂指針指向的位置中。

值得注意的是，在入棧運(yùn)算中應(yīng)避免上溢錯(cuò)誤的出現(xiàn)。上溢錯(cuò)誤是指當(dāng)棧頂指針己經(jīng)指向存儲空間的最后一個(gè)位置時(shí)，說明棧的空間己滿，不能再進(jìn)行入棧操作，這種情況稱為棧“上溢”錯(cuò)誤。(2)退棧運(yùn)算的步驟：

首先，判斷棧是否為空(方法top=0);

其次，將棧頂元素賦值給一個(gè)指定的變量;

最后，棧頂指針退一(即top減1)。

值得注意的是，退棧運(yùn)算中應(yīng)避免"下溢"錯(cuò)誤的出現(xiàn)。最后，將新元素放入棧頂指針指向的位置中。

值得注意的是(3)讀棧頂元素的步驟：

讀棧頂元素是指將棧頂元素賦值給一個(gè)指定的變量。

讀枝頂元素過程中應(yīng)注意的問題有:

第一，讀棧頂元素不是刪除棧頂元素，只是將它的值賦給一個(gè)變量，因此，在這個(gè)運(yùn)算中，棧頂指針不會改變，這是與入棧運(yùn)算的區(qū)別;

第二，當(dāng)棧頂指針為0時(shí)，說明棧為空，讀不到棧頂元素。(3)讀棧頂元素的步驟：

讀棧頂元素是指將棧頂元素賦值給五、隊(duì)列1.隊(duì)列的基本概念：隊(duì)列是一種只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表，它也是一種特殊的線性表。允許插入的一端叫隊(duì)尾(尾指針，Rear，指向隊(duì)尾元素)，允許刪除的一端叫隊(duì)頭(頭指針，F(xiàn)ront，指向隊(duì)頭元素的前一個(gè)位置)。

隊(duì)列的數(shù)據(jù)操作方法:先進(jìn)先出FIFO/LILO。五、隊(duì)列隊(duì)列的一個(gè)重要應(yīng)用是在操作系統(tǒng)中的管理用戶程序上。即在操作系統(tǒng)中，用隊(duì)列來組織管理用戶程序的排隊(duì)執(zhí)行，其原則是:

(1)初始時(shí)該隊(duì)列為空;

(2)當(dāng)有用戶程序到來時(shí)，將該用戶程序加入到隊(duì)列的末尾進(jìn)行等待;

(3)當(dāng)計(jì)算機(jī)系統(tǒng)執(zhí)行完當(dāng)前的用戶程序后，就從隊(duì)列頭部取出一個(gè)用戶程序執(zhí)行。與棧一樣，程序設(shè)計(jì)中用一維數(shù)組作為隊(duì)列的順序存儲空間。隊(duì)列的一個(gè)重要應(yīng)用是在操作系統(tǒng)中的管理用戶程序上。即在操作系2.循環(huán)隊(duì)列

在實(shí)際應(yīng)用中，隊(duì)列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。原理:循環(huán)隊(duì)列是指當(dāng)隊(duì)列存儲空

間的最后一個(gè)位置己被使用而仍

要進(jìn)行入隊(duì)運(yùn)算，這時(shí)只要存儲

空間的第一個(gè)位置空閑，便可以

將元素加入到這個(gè)位置，即將存

儲空間的第一個(gè)位置作為隊(duì)尾，

如圖所示。2.循環(huán)隊(duì)列

在實(shí)際應(yīng)用中，隊(duì)列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊(duì)在循環(huán)隊(duì)列中，從頭指針front指向的后一個(gè)位置直到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。循環(huán)隊(duì)列的初始狀態(tài)為空，即：

rear=front=m，如圖所示。循環(huán)隊(duì)列主要有兩種基本運(yùn)算：

入隊(duì)運(yùn)算與退隊(duì)運(yùn)算。

每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針就進(jìn)一。

當(dāng)隊(duì)尾指針rear=m+1時(shí)，則置rear=1；

每進(jìn)行一次退隊(duì)運(yùn)算，排頭指針就進(jìn)一。

當(dāng)排頭指針front=m+1時(shí)，則置front=1在循環(huán)隊(duì)列中，從頭指針front指向的后一個(gè)位置直到隊(duì)尾指針例：圖（a）是一個(gè)容量為8的循環(huán)隊(duì)列存儲空間，且其中已有6個(gè)元素。圖（b）是在圖（a）的循環(huán)隊(duì)列中又加入了兩個(gè)元素后的狀態(tài)。圖（c）是在圖（b）的循環(huán)隊(duì)列中退出了1個(gè)元素后的狀態(tài)。Q(1:8)8rear→7F6E5D4C3B2Afront→1Q(1:8)8X7F6E5D4C3B2Afront→rear→1YQ(1:8)8X7F6E5D4C3Bfront→

2rear→1Y（a）具有6個(gè)元素的循環(huán)隊(duì)列（b）加入X、Y后的循環(huán)隊(duì)列（c）退出一個(gè)元素后的循環(huán)隊(duì)列從圖（b）可以看出，當(dāng)循環(huán)隊(duì)列滿時(shí)有front=rear，而當(dāng)循環(huán)隊(duì)列空時(shí)也有front=rear。即在循環(huán)隊(duì)列中，當(dāng)front=rear時(shí)，不能確定是隊(duì)列滿還是隊(duì)列空。例：圖（a）是一個(gè)容量為8的循環(huán)隊(duì)列存儲空間，且其中已有6個(gè)為了能區(qū)分隊(duì)列滿還是隊(duì)列空，通常還需增加一個(gè)標(biāo)志s，s值的定義如下：

s=0表示隊(duì)列空

s=1表示隊(duì)列非空

由此可以得出隊(duì)列空與隊(duì)列滿的條件如下：

隊(duì)列空的條件為s=0；

隊(duì)列滿的條件為s=1且front=rear。循環(huán)隊(duì)列入隊(duì)與退隊(duì)的運(yùn)算注意點(diǎn)

當(dāng)循環(huán)隊(duì)列非空（s=1）且front=rear時(shí)，說明循環(huán)隊(duì)列已滿，不能入隊(duì)運(yùn)算，這種情況稱為”上溢“。

當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為”下溢“。為了能區(qū)分隊(duì)列滿還是隊(duì)列空，通常還需增加一個(gè)標(biāo)志s，s值的定六、線性鏈表1.鏈?zhǔn)酱鎯Y(jié)構(gòu)

對于大的線性表或者變動頻繁的線性表不宜用順序存儲，應(yīng)該采用鏈?zhǔn)酱鎯Αｆ準(zhǔn)酱鎯Φ倪^程如圖所示。每個(gè)結(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素值，指針域存放指針。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。六、線性鏈表每個(gè)結(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。注：①鏈?zhǔn)酱鎯Ψ绞街械拇鎯Y(jié)點(diǎn)不一定是連續(xù)的；②各結(jié)點(diǎn)的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致；③鏈?zhǔn)酱鎯Ψ绞娇梢杂糜诰€性結(jié)構(gòu)，也可用于非線性結(jié)構(gòu)。2.線性鏈表

線性鏈表是指線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。為了適應(yīng)線性鏈表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，計(jì)算機(jī)存儲空間被劃分為一個(gè)一個(gè)小塊，每個(gè)小塊占若干個(gè)字節(jié)，通常稱這些小塊為存儲結(jié)點(diǎn)。

注：①鏈?zhǔn)酱鎯Ψ绞街械拇鎯Y(jié)點(diǎn)不一定是連續(xù)的；②各結(jié)點(diǎn)的存儲在線性鏈表中，頭指針(head)很關(guān)鍵，不得丟失；線性鏈表的最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨肗ULL或0來表示；空表(線性鏈表):當(dāng)head(指向線性表的第一個(gè)結(jié)點(diǎn)的指針head稱為頭指針)等于NULL或0時(shí)，稱為空表;單鏈表的缺點(diǎn)是只能找到后件，不能找到前件；為了克服單鏈表的缺點(diǎn)，出現(xiàn)了雙向鏈表的概念。在雙向鏈表中，把每個(gè)結(jié)點(diǎn)修改為由以下3部分組成:左指針數(shù)據(jù)元素右指針在線性鏈表中，頭指針(head)很關(guān)鍵，不得丟失；左指針雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下圖所示：

雙向鏈表克服了單向鏈表的只能找到后件不能找到前件的缺陷。3.棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)（帶鏈的棧）雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下圖所示：

雙向鏈表克服了單向鏈表在實(shí)際應(yīng)用中，帶鏈的棧可以用來收集計(jì)算機(jī)存儲空間中所有空閑的存儲結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。當(dāng)計(jì)算機(jī)系統(tǒng)需要存儲結(jié)點(diǎn)時(shí)，退棧;當(dāng)計(jì)算機(jī)系統(tǒng)釋放存儲結(jié)點(diǎn)時(shí)，入棧。4.隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（帶鏈的隊(duì)列）在實(shí)際應(yīng)用中，帶鏈的棧可以用來收集計(jì)算機(jī)存儲空間中所有空閑的對帶鏈的隊(duì)列的操作如下圖所示：對帶鏈的隊(duì)列的操作如下圖所示：5.線性鏈表的基本運(yùn)算

線性鏈表的基本運(yùn)算有3種:查找、插入和刪除數(shù)據(jù)元素。（1）在線性鏈表中查找指定元素

在對線性鏈表進(jìn)行插入或刪除的運(yùn)算中，總是首先需要找到插入或刪除的位置，這就需要對線性鏈表進(jìn)行掃描查找，在線性鏈表中尋找包含指定元素值的前一個(gè)結(jié)點(diǎn)。當(dāng)找到包含指定元素的前一個(gè)結(jié)點(diǎn)后，就可以在該結(jié)點(diǎn)后插入新結(jié)點(diǎn)或刪除該結(jié)點(diǎn)后的一個(gè)結(jié)點(diǎn)。

在非空線性鏈表中尋找包含指定元素值x的前一個(gè)結(jié)點(diǎn)p的基本方法如下：5.線性鏈表的基本運(yùn)算

線性鏈表的基本運(yùn)算有3種:查找、插入從頭指針指向的結(jié)點(diǎn)開始往后沿指針進(jìn)行掃描，直到后面已沒有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤為止。因此，由這種方法找到的結(jié)點(diǎn)p有兩種可能：

當(dāng)線性鏈表中存在包含元素x的結(jié)點(diǎn)時(shí)，則找到的p為第一次遇到的包含元素x的前一個(gè)結(jié)點(diǎn)序號；

當(dāng)線性鏈表中不存在包含元素x的結(jié)點(diǎn)時(shí)，則找到的p為線性鏈表中的最后一個(gè)結(jié)點(diǎn)號。（2）線性鏈表中的插入運(yùn)算

為了要在線性鏈表中插入一個(gè)新元素，首先要給該元素分配一個(gè)新結(jié)點(diǎn)，以便用于存儲該元素的值。新結(jié)點(diǎn)可以從可利用棧中取得。然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置。從頭指針指向的結(jié)點(diǎn)開始往后沿指針進(jìn)行掃描，直到后面已沒在線性鏈表中包含x的結(jié)點(diǎn)之前插入一個(gè)新元素b。其插入過程如下：

（1）從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號為p（即取得結(jié)點(diǎn)的存儲序號存放在變量p中），并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲。

（2）在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)的存儲序號為q。

（3）將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后。為了實(shí)現(xiàn)這一步，只要改變兩個(gè)結(jié)點(diǎn)的指針域內(nèi)容即可：

①使結(jié)點(diǎn)p指向包含元素x的結(jié)點(diǎn)（即結(jié)點(diǎn)q的后件結(jié)點(diǎn)）。

②使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p。在線性鏈表中包含x的結(jié)點(diǎn)之前插入一個(gè)新元素b。其插入過程如下在線性鏈表中包含x的結(jié)點(diǎn)之前插入一個(gè)新元素b。其插入過程如下圖：在線性鏈表中包含x的結(jié)點(diǎn)之前插入一個(gè)新元素b。其插入過程如下（3）線性鏈表的刪除

為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)，然后將要?jiǎng)h除結(jié)點(diǎn)放回到可利用棧。

在線性鏈表中刪除包含元素x的結(jié)點(diǎn)，其刪除過程如下：

（1）在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)序號為q。

（2）將結(jié)點(diǎn)q后的結(jié)點(diǎn)p從線性鏈表中刪除，即讓結(jié)點(diǎn)q的指針指向包含元素x的結(jié)點(diǎn)p的指針指向的結(jié)點(diǎn)。

（3）將包含元素x的結(jié)點(diǎn)p送回可利用棧。（3）線性鏈表的刪除

為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)在線性鏈表中刪除包含元素x的結(jié)點(diǎn)，其刪除過程如下圖所示：在線性鏈表中刪除包含元素x的結(jié)點(diǎn)，其刪除過程如下圖所示：6.循環(huán)鏈表循環(huán)鏈表與單鏈表的主要區(qū)別:

(1)在循環(huán)鏈表中增加了表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來設(shè)置，指針域?yàn)橹赶蚓€性表的第一個(gè)元素的結(jié)點(diǎn)；

(2)循環(huán)鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域不為空，而是指向表頭結(jié)點(diǎn)。6.循環(huán)鏈表循環(huán)鏈表的特征如下:

(1)循環(huán)鏈表中永遠(yuǎn)至少有一個(gè)結(jié)點(diǎn)存在(表頭結(jié)點(diǎn))；

(2)在對循環(huán)鏈表進(jìn)行插入和刪除的過程中，實(shí)現(xiàn)了空表和非空表的運(yùn)算的統(tǒng)一；

(3)在循環(huán)鏈表中，只要指出表中的任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中的其他所有結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)；

(4)在循環(huán)鏈表的運(yùn)算過程中，不必單獨(dú)考慮對空表和第一結(jié)點(diǎn)的處理問題。循環(huán)鏈表的特征如下:

(1)循環(huán)鏈表中永遠(yuǎn)至少有一個(gè)結(jié)點(diǎn)存在七、樹與二叉樹1.樹樹是一種非線性結(jié)構(gòu)，樹的數(shù)據(jù)結(jié)構(gòu)為B=(D,R)，其中，D代表數(shù)據(jù)對象，是具有相同特性的數(shù)據(jù)元素的集合；R代表數(shù)據(jù)關(guān)系。若D為空集，則稱為空樹，否則：

（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root；

（2）當(dāng)n＞1時(shí)，其余結(jié)點(diǎn)可分為m（m＞0）個(gè)互不相交的有限集T1,T2,…T3,其中每一個(gè)子集本身又是一顆符合本定義的樹，稱為根（root）的子樹。七、樹與二叉樹在樹結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)只有一

個(gè)前件，稱為父結(jié)點(diǎn)，沒有前

件的結(jié)點(diǎn)只有一個(gè)，稱為樹的

根結(jié)點(diǎn)，簡稱為樹的根。如圖

所示的結(jié)點(diǎn)A就是樹的根。在樹結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)可以有

多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。如圖所示的結(jié)點(diǎn)K,L,F,G,M,I,J都是葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。例如圖中結(jié)點(diǎn)D的度為3。在樹結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)只有一

個(gè)前件，稱為父結(jié)點(diǎn)，沒有前

件的在樹中所有結(jié)點(diǎn)中的最大的度稱為

樹的度。如圖示的樹的度為3樹結(jié)構(gòu)具有明顯的層次關(guān)系，即樹

是一種層次結(jié)構(gòu)。在樹結(jié)構(gòu)中，一

般有如下分層:根結(jié)點(diǎn)在第一層，

依次類推。樹的最大層次稱為樹的深度。如圖所示的樹的深度為4。在樹中，以某結(jié)點(diǎn)的子結(jié)點(diǎn)為根構(gòu)成的樹稱為該結(jié)點(diǎn)的一顆子樹。例如在圖所示的樹中B結(jié)點(diǎn)有兩顆子樹在樹中，葉子結(jié)點(diǎn)沒有子樹。樹在計(jì)算機(jī)中通常用多重鏈表來表示。在樹中所有結(jié)點(diǎn)中的最大的度稱為

樹的度。如圖示的樹的度為32.二叉樹（1）二叉樹的定義

二叉樹是一種特殊的樹，非空二叉樹只有一個(gè)根結(jié)點(diǎn)。如圖所示，每個(gè)根結(jié)點(diǎn)最多有兩棵子樹，分別稱為該結(jié)點(diǎn)的左子樹和右子樹。2.二叉樹（2）二叉樹的性質(zhì)：性質(zhì)1:

在二叉樹的第k層上，最多有2k-1（k≥1）個(gè)結(jié)點(diǎn)。423167891011121314155第三層上(k=3)，有23-1=4個(gè)節(jié)點(diǎn)。第四層上(k=4)，有24-1=8個(gè)節(jié)點(diǎn)。（2）二叉樹的性質(zhì)：42316789101112131415性質(zhì)2：深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)。

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

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1。其中，[log2n]表示取log2n的整數(shù)部分。性質(zhì)2：深度為m的二叉樹最多有2m-1個(gè)結(jié)點(diǎn)。

（3）滿二叉樹

滿二叉樹是特殊的二叉樹。滿二叉樹是指除最后一層之外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。性質(zhì)5：滿二叉樹上的第k層上有2k-1個(gè)結(jié)點(diǎn)。

結(jié)構(gòu)如圖所示：（3）滿二叉樹

滿二叉樹是特殊的二叉樹。滿二叉樹是指除最后一（4）完全二叉樹

完全二叉樹也是一種特殊的二叉樹。特殊在:除最后一層之外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到了最大值，在最后一層上只缺少右邊的若干個(gè)結(jié)點(diǎn)。（4）完全二叉樹

完全二叉樹也是一種特殊的二叉樹。特殊在:除性質(zhì)6:設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序(每一層從左到右)用自然數(shù)1，2，3……n給結(jié)點(diǎn)進(jìn)行編號。對于編號為k(k=1，2，3……n)的結(jié)點(diǎn)有以下結(jié)論：

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

②若2k≤n，則編號為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號為2k，否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)，當(dāng)然也沒有右子結(jié)點(diǎn)。

③若2k+1≤n，則編號為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號為2k+1，否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。性質(zhì)6:設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序(例：

k=1，是樹的根,無父結(jié)點(diǎn);其左子結(jié)點(diǎn)為2*k=2,右子結(jié)點(diǎn)為2*k+1=3。

k=6，其父結(jié)點(diǎn)為[k/2]=3；其左子結(jié)點(diǎn)為2*k=12;

∵2*k+1=13>12∴其無右子結(jié)點(diǎn)。

k=9，其父結(jié)點(diǎn)為[k/2]=4；

∵2*k=18>12，2*k+1=19>12∴其無左、右子結(jié)點(diǎn)112345678910121例：

112345678910121性質(zhì)7：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。

例：n=2k=2

n=6k=3

n=7k=3

n=8k=4

n=12k=4112345678910121性質(zhì)7：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。（5）二叉樹的存儲結(jié)構(gòu)

常見的二叉樹的存儲結(jié)構(gòu)有兩種:順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

順序存儲結(jié)構(gòu)：用一組連續(xù)的存儲單元存放二叉樹中的結(jié)點(diǎn)。一般是按照二叉樹結(jié)點(diǎn)從上至下、從左至右的順序存儲。

鏈?zhǔn)酱鎯Y(jié)構(gòu)：用鏈表來表示

一棵二叉樹，即用鏈來指示著元素的邏輯關(guān)系。通常采用二叉鏈表存儲形式。

鏈表中每個(gè)結(jié)點(diǎn)由3個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來給出該結(jié)點(diǎn)左子結(jié)點(diǎn)和右子結(jié)點(diǎn)所在的鏈結(jié)點(diǎn)的存儲地址。LchilddataRchild（5）二叉樹的存儲結(jié)構(gòu)

常見的二叉樹的存儲結(jié)構(gòu)有兩種:順序存二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖（6）二叉樹的遍歷

二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷分為三種：前序遍歷、中序遍歷、后序遍歷。

（1）前序遍歷（根、左、右）

訪問根結(jié)點(diǎn)；前序遍歷左子樹；前序遍歷右子樹。

（2）中序遍歷（左、根、右）

中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。

（3）后續(xù)遍歷（左、右、根）

后續(xù)遍歷左子樹；后續(xù)遍歷右子樹；訪問根結(jié)點(diǎn)。（6）二叉樹的遍歷

二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所例：例：（7）表達(dá)式樹表示表達(dá)式的樹叫表達(dá)式樹。用樹來表示算術(shù)表達(dá)式的原則如下：

（1）表達(dá)式中的每個(gè)運(yùn)算符在樹中對應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)；

（2）運(yùn)算符的每一個(gè)運(yùn)算對象在樹中為該運(yùn)算符結(jié)點(diǎn)的子樹，在樹中的順序?yàn)閺淖蟮接遥?/p>

（3）運(yùn)算對象中的單變量均為葉子結(jié)點(diǎn)；

（4）表達(dá)式樹的表示方法必須按照特定的遍歷方法（7）表達(dá)式樹例如，假設(shè)表達(dá)式為a×(b+c/d)+e×f-g，則其中序遍歷的表達(dá)式樹如圖所示。例如，假設(shè)表達(dá)式為a×(b+c/d)+e×f-g，則其中序遍八、查找技術(shù)查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。通常，根據(jù)不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)采用不同的查找方法。常見的查找方法有兩種：順序查找、二分法查找。查找是數(shù)據(jù)處理中的重要環(huán)節(jié)，一般認(rèn)為查找的效率將直接影響到數(shù)據(jù)處理的效率。（1）順序查找

順序查找是指從線性表的一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示查找成功；若找不到相等的元素則查找失敗。八、查找技術(shù)順序查找的最好的查詢次數(shù)是指所查找的元素是線性表的第一個(gè)元素時(shí)的查詢次數(shù)。

最差的查詢次數(shù)是指所查找的元素是線性表的最后一位元素或者在線性表中根本不存在這個(gè)元素時(shí)的查詢次數(shù)。

順序查找的平均查詢次數(shù)為大約需要與線性表中一半的元素進(jìn)行比較的次數(shù)。

對于龐大的線性表來說，順序查找的效率是很低的。但是在下列兩種情況下只能采用順序查找：

（1）線性表是無序表，即表中的元素的排列是無序的，則不管是順序結(jié)構(gòu)還是鏈?zhǔn)浇Y(jié)構(gòu)，都只能用順序查找；

（2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。順序查找的最好的查詢次數(shù)是指所查找的元素是線性表的第一個(gè)元素（2）二分法查找

二分法查找只適用于順序存儲的有序表。其中，“有序表”是指已對順序存儲結(jié)構(gòu)排序，但允許相鄰元素值相等。

設(shè)有序列表的長度為n，被查找的元素為x，則二分法查找的方法如下：

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

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

若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；

若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。

上述過程一直進(jìn)行到查找成功或子表長度為0(說明線性表中沒有這個(gè)元素)為止。（2）二分法查找

二分法查找只適用于順序存儲的有序表。其中，二分法查找的優(yōu)點(diǎn)主要有兩個(gè):

（1）二分法查找的效率比順序查找高得多；

（2）對于長度為n的有序線性表，在最壞的情況下，二分法查找只需要比較log2n次,而順序查找需要比較n次。二分法查找的優(yōu)點(diǎn)主要有兩個(gè):

（1）二分法查找的效率比順序查九、排序技術(shù)排序是指將一個(gè)無序的列表整理成按值遞減（或遞增）順序排列的有序序列。常見的排序方法有:交換類排序、插入類排序和選擇類排序。（1）交換式排序

交換類排序法是指借助數(shù)據(jù)元素之間的相互交換進(jìn)行排序的一種方法。

典型交換類排序法實(shí)例有兩種：冒泡排序和快速排序。九、排序技術(shù)冒泡排序:通過相鄰數(shù)據(jù)元素交換逐步將線性表變換成有序的。快速排序:將原問題分解成若干個(gè)小規(guī)模的同結(jié)構(gòu)的問題，遞歸解決每個(gè)子問題。（2）插入類排序

插入類排序方法是指將無序列表中的各元素依次插入到已經(jīng)有序的線性表中。

插入類排序的典型實(shí)例有：簡單插入排序法和希爾排序法（Shellsort）。冒泡排序:通過相鄰數(shù)據(jù)元素交換逐步將線性表變換成有序的。簡單插入排序法：將無序列表中的各元素依次插入到已有序的線性表中。希爾排序法:這是對簡單插入排序法的改進(jìn)，先選取第一個(gè)增量，把距離為第一個(gè)增量的倍數(shù)的記錄放在同一組中，在組內(nèi)進(jìn)行直接插入排序，再取小于第一個(gè)增量的第二個(gè)增量，重復(fù)上述操作。（3）選擇類排序

選擇類排序法的典型實(shí)例有:簡單選擇排序方法和堆排序方法。簡單選擇排序:掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最上面。然后對剩下的子表采取相同的方法，直到子表空為止。簡單插入排序法：將無序列表中的各元素依次插入到已有序的線性表（4）各種排序方法的性能

不同排序方法的時(shí)間復(fù)雜度、空間復(fù)雜度可能是不同的。如下表所示：（4）各種排序方法的性能

不同排序方法的時(shí)間復(fù)雜度、空間復(fù)假設(shè)線性表長度為n,在最壞的情況下，各種排序方法的比較次數(shù)如下：

（1）冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2次的從后往前的掃描，需要的比較次數(shù)為n(n-1)/2

（2）快速排序方法的比較次數(shù)為O(n2)=n(n-1)/2

（3）簡單插入排序需要的比較次數(shù)為n(n-1)/2;

（4）希爾排序的比較次數(shù)為O(n1.5)；

（5）簡單選擇排序的比較次數(shù)為n(n-1)/2；

（6）堆排序的比較次數(shù)為O(nlog2n)=nlog2n+nC(1)，其中C(1)表示對長度為1的區(qū)間進(jìn)行快速排序所需的比較次數(shù)。假設(shè)線性表長度為n,在最壞的情況下，各種排序方法的比較次數(shù)第二章程序設(shè)計(jì)基礎(chǔ)本章要求程序設(shè)計(jì)方法與風(fēng)格。結(jié)構(gòu)化程序設(shè)計(jì)。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法，對象、方法、屬性及繼承與多態(tài)性。第二章程序設(shè)計(jì)基礎(chǔ)本章要求第二章程序設(shè)計(jì)基礎(chǔ)一、程序設(shè)計(jì)方法和風(fēng)格二、結(jié)構(gòu)化程序設(shè)計(jì)三、面向?qū)ο蟮某绦蛟O(shè)計(jì)第二章程序設(shè)計(jì)基礎(chǔ)一、程序設(shè)計(jì)方法和風(fēng)格一、程序設(shè)計(jì)方法和風(fēng)格良好的程序設(shè)計(jì)風(fēng)格

良好的程序設(shè)計(jì)風(fēng)格應(yīng)遵循一個(gè)總體原則，即“清晰第一、效率第二”。具體應(yīng)注意以下幾個(gè)問題。

（1）源程序文檔化。

①符號命名的技巧。

應(yīng)具有一定的實(shí)際含義，以便于對程序功能的理解。

②程序注釋。

注釋一般分為序言性注釋和功能型注釋兩種。

序言性注釋通常位于程序的開頭部分，它是對程序進(jìn)行整體說明。

功能性注釋的位置一般嵌在源程序之中，主要描述其后的語句或程序做什么。一、程序設(shè)計(jì)方法和風(fēng)格③視覺組織。

為了使程序的結(jié)構(gòu)一目了然，可以在程序中利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?/p>

(2)數(shù)據(jù)說明的方法。

設(shè)計(jì)原則:易于理解和維護(hù)。

(3)語句的結(jié)構(gòu)。

設(shè)計(jì)原則:清晰第一、效率第二、簡單易懂。

(4)程序的輸入輸出。

設(shè)計(jì)原則:方便用戶的使用。③視覺組織。

為了使程序的結(jié)構(gòu)一目了然，可以在程序中利二、結(jié)構(gòu)化程序設(shè)計(jì)1.結(jié)構(gòu)化程序設(shè)計(jì)的原則

結(jié)構(gòu)化程序設(shè)計(jì)的基本原則是:自頂向下、逐步求精、模塊化、限制使用goto語句。

“自頂向下、逐步求精”是指應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。

“模塊化”是指把一個(gè)總目標(biāo)分為多個(gè)分目標(biāo)，一個(gè)分目標(biāo)進(jìn)一步分為多個(gè)小目標(biāo)，每一個(gè)小目標(biāo)稱為一個(gè)模塊。

二、結(jié)構(gòu)化程序設(shè)計(jì)“限制使用goto語句”是指為了提高程序清晰性，除了以下3種需況，應(yīng)嚴(yán)格限制goto語句的使用。這3種情況如下所述。

(1)用一個(gè)非結(jié)構(gòu)化的程序設(shè)計(jì)語言去實(shí)現(xiàn)一個(gè)結(jié)構(gòu)化的構(gòu)造。

(2)若不使用goto語句會使功能模糊，

(3)在某種可以改善而不是損害程序可讀性的情況下可以使用goto語句。2.結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)

有3種:順序結(jié)構(gòu)、選擇結(jié)構(gòu)和重復(fù)結(jié)構(gòu)

“限制使用goto語句”是指為了提高程序清晰性，除了以3.在結(jié)構(gòu)化程序設(shè)計(jì)的具體實(shí)施中，要注意把握以下幾小問題：

（1）使用程序設(shè)計(jì)語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。

（2）選用的控制結(jié)構(gòu)只準(zhǔn)許一個(gè)入口和一個(gè)出口。

（3）復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn)。

（4）程序語句組成容易識別的塊，每塊只有一個(gè)入口和一個(gè)出口。

（5）語言中所沒有的控制結(jié)構(gòu)，應(yīng)采用前后一致的方法來模擬。

（6）嚴(yán)格控制goto語句的使用。3.在結(jié)構(gòu)化程序設(shè)計(jì)的具體實(shí)施中，要注意把握以下幾小問題：

4.結(jié)構(gòu)化程序設(shè)計(jì)的優(yōu)缺點(diǎn)

優(yōu)點(diǎn):

①易于理解、使用和維護(hù);

②提高了編程的工作效率，降低了軟件開發(fā)成本。

缺點(diǎn):結(jié)構(gòu)化程序設(shè)計(jì)中存一個(gè)嚴(yán)重問題，即對于大型、復(fù)雜的軟件，由于其中內(nèi)在的高耦合、低內(nèi)聚，特別是當(dāng)時(shí)團(tuán)體開發(fā)的管理方法的不足，所以在20世紀(jì)70年代出現(xiàn)了軟件危機(jī)、難以對系統(tǒng)進(jìn)行維護(hù)。

4.結(jié)構(gòu)化程序設(shè)計(jì)的優(yōu)缺點(diǎn)

優(yōu)點(diǎn):

①易于理解、使用和三、面向?qū)ο蟮某绦蛟O(shè)計(jì)1.面向?qū)ο蠓椒ǖ亩x：

面向?qū)ο蠓椒ㄊ且环N運(yùn)用對象、類、繼承、封裝、聚合、關(guān)聯(lián)、消息、多態(tài)性等概念來構(gòu)造系統(tǒng)的軟件開發(fā)方法。

面向?qū)ο蟮姆椒ㄅc技術(shù)開始走向?qū)嵱茫ǔ墒欤┑臉?biāo)志性語言是smalltalk。

傳統(tǒng)結(jié)構(gòu)化程序設(shè)計(jì)方法的核心是算法，面向?qū)ο蟮暮诵氖菍ο螅悾Ｈ⒚嫦驅(qū)ο蟮某绦蛟O(shè)計(jì)2.面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)

面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)如下：

（1）與人類思維習(xí)慣一致:主要強(qiáng)調(diào)模擬現(xiàn)實(shí)世界中的概念而不強(qiáng)調(diào)算法。

（2）穩(wěn)定性好:當(dāng)對系統(tǒng)功能的需求發(fā)生變化時(shí)并不會引起軟件結(jié)構(gòu)的整體變化，往往僅需要作一些局部性的修改即可。

（3）可重用性好:傳統(tǒng)算法中的重用技術(shù)是利用標(biāo)準(zhǔn)庫函數(shù)；在面向?qū)ο蠓椒ㄖ杏袃煞N方法可以重復(fù)使用一個(gè)對象類，一是創(chuàng)建該類的實(shí)例，二是繼承。

（4）易于開發(fā)大型軟件產(chǎn)品。

（5）可維護(hù)性好。2.面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)

面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)如下：

（1）3.對象

對象是軟件系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，它是構(gòu)成軟件系統(tǒng)的一個(gè)基本單位。一個(gè)對象由一組屬性和對這組屬性進(jìn)行操作的一組服務(wù)構(gòu)成。其中，屬性是指事務(wù)的特性，表示事務(wù)的靜態(tài)特征；操作是指事務(wù)的功能，表示事務(wù)的動態(tài)特征。4.類、對象、實(shí)例

類是具有相同屬性和服務(wù)的一組對象的集合，它為屬于該類的全部對象提供了統(tǒng)一的抽象描述，其內(nèi)部包括屬性和服務(wù)兩個(gè)主要部分。類可以用來創(chuàng)建對象，對象是類的一個(gè)實(shí)例。

注意："對象"和"實(shí)例"是兩個(gè)不同的概念。對象既可以指一個(gè)具體的對象，也可以泛指一般的對象；實(shí)例必須是指一個(gè)具體的對象。3.對象

對象是軟件系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，它是構(gòu)5.封裝

封裝是指把對象的屬性和服務(wù)結(jié)合成一個(gè)獨(dú)立的系統(tǒng)單位，并盡可能隱蔽對象的內(nèi)部細(xì)節(jié)。只是它要向外部提供接口，這降低了對象間的耦合度。

（耦合度是指對象和對象之間聯(lián)系的緊密程度。對象之間的聯(lián)系越緊密，其耦合度越大。耦合度越大，程序的可維護(hù)性越差。所以，在程序設(shè)計(jì)中強(qiáng)調(diào)“耦合度越低越好”。封裝機(jī)制降低了對象間的耦合度。）

封裝的目的：是實(shí)現(xiàn)信息隱蔽。

5.封裝

封裝是指把對象的屬性和服務(wù)結(jié)合成一個(gè)獨(dú)立的系統(tǒng)單6.繼承如果類A具有類B的全部屬性和全部服務(wù)，而且具有自己特有的某些屬性或服務(wù)，則A叫做B的特殊類，B叫做A的一般類。繼承是指使用己經(jīng)定義好的類

來定義一個(gè)新類，原類與新類

的關(guān)系是一般類與特殊類的關(guān)

系，被繼承與繼承的關(guān)系。例

如公司人員類、股東類和職員

類之間存在繼承關(guān)系，如圖所

示繼承是一種在多個(gè)類之間共享屬性和操作的機(jī)制。繼承分為兩種：多繼承和單繼承6.繼承7.消息

消息是指一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息，它請求對象執(zhí)行某一處理或回答某一要求的信息，統(tǒng)一了數(shù)據(jù)流和控制流。在面向?qū)ο笾邢⒌氖褂门c傳統(tǒng)程序設(shè)計(jì)方法中函數(shù)的調(diào)用差不多。

例:Mycircle.show(blue)，其中mycircle是接受消息的對象的名字，show是操作名稱，blue是消息的參數(shù)。可見，消息只告訴接收者需要做哪些操作，但并不指示接收者應(yīng)該怎樣完成這些操作。7.消息

消息是指一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息，它請求8.多態(tài)性多態(tài)是指同樣的消息被不同的對象接收時(shí)可導(dǎo)致完全不同的行為。可以通過方法重載和方法重寫來實(shí)現(xiàn)多態(tài)。利用多態(tài)性，用戶能夠發(fā)送一般形式的消息，而將所有的實(shí)現(xiàn)細(xì)節(jié)都留給接收信息的對象。9.關(guān)聯(lián)與鏈

類之間的靜態(tài)聯(lián)系稱作關(guān)聯(lián)。

鏈?zhǔn)顷P(guān)聯(lián)的實(shí)例。

8.多態(tài)性10.總結(jié)

下表是對傳統(tǒng)程序設(shè)計(jì)方法與面向?qū)ο蟪绦蛟O(shè)計(jì)方法之間的對應(yīng)關(guān)系的總結(jié)傳統(tǒng)方法面向?qū)ο蠓椒〝?shù)據(jù)結(jié)構(gòu)+算法+程序設(shè)計(jì)以對象為中心組織數(shù)據(jù)與操作數(shù)據(jù)對象的屬性操作對象的服務(wù)類型與變量類與對象實(shí)例函數(shù)（過程）調(diào)用消息傳遞類型與子類型一般類與特殊類，繼承構(gòu)造類型整體-部分結(jié)構(gòu)(配合)指針關(guān)聯(lián)8910.總結(jié)

下表是對傳統(tǒng)程序設(shè)計(jì)方法與面向?qū)ο蟪绦蛟O(shè)計(jì)方法之第三章軟件工程基礎(chǔ)本章要求軟件工程基本概念、軟件生命周期概念、軟件工具與軟件開發(fā)環(huán)境。結(jié)構(gòu)化分析方法、數(shù)據(jù)流圖、數(shù)據(jù)字典、軟件需求規(guī)格說明書。結(jié)構(gòu)化設(shè)計(jì)方法、總體設(shè)計(jì)與詳細(xì)設(shè)計(jì)。軟件測試的方法、白盒測試與黑盒測試、測試用例設(shè)計(jì)、軟件測試的實(shí)施、單元測試、集成測試和系統(tǒng)測試。程序的調(diào)試、靜態(tài)調(diào)試與動態(tài)調(diào)試。第三章軟件工程基礎(chǔ)本章要求第三章軟件工程基礎(chǔ)一、軟件工程基本概念二、結(jié)構(gòu)化分析方法三、結(jié)構(gòu)化設(shè)計(jì)方法四、軟件測試五、程序調(diào)試第三章軟件工程基礎(chǔ)一、軟件工程基本概念一、軟件工程基本概念1.軟件軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合，相對于硬件產(chǎn)品講，軟件是一種邏輯產(chǎn)品。軟件按功能可以分為應(yīng)用軟件、系統(tǒng)軟件和支撐軟件3種。

（1）應(yīng)用軟件是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件，例如：事務(wù)處理軟件、人工智能軟件與會計(jì)軟件等。

（2）系統(tǒng)軟件是為管理計(jì)算機(jī)本身而開發(fā)的軟件，例如：操作系統(tǒng)、編譯程序、匯編程序、網(wǎng)絡(luò)軟件與數(shù)據(jù)庫軟件等。

（3）支撐軟件是為開發(fā)軟件和維護(hù)軟件的軟件。例如：計(jì)劃進(jìn)度管理軟件、過程控制工具軟件與質(zhì)量管理給配置管理工具軟件等（軟件工程有關(guān)）等。一、軟件工程基本概念2.軟件危機(jī)

20世紀(jì)60年代末以后出現(xiàn)了軟件危機(jī)。

軟件危機(jī)主要表現(xiàn)在成本、質(zhì)量和生產(chǎn)率等3

個(gè)方面。

產(chǎn)生的主要原因是軟件開發(fā)和維護(hù)方法不正確。

為了解決這種軟件危機(jī)，出現(xiàn)了軟件工程的概念。3.軟件工程

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

軟件工程就是試圖用工程、科學(xué)和數(shù)學(xué)的原理與方法研制、維護(hù)計(jì)算機(jī)軟件的有關(guān)技術(shù)及管理方法。2.軟件危機(jī)

20世紀(jì)60年代末以后出現(xiàn)了軟件危機(jī)。

軟軟件工程有3個(gè)要素：方法、工具和過程。

其中，方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具用于支持軟件的開發(fā)、管理、文檔生成；過程用于支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制和管理。軟件工程的核心思想是把軟件產(chǎn)品當(dāng)作是一個(gè)工程產(chǎn)品來處理，即強(qiáng)調(diào)在軟件開發(fā)過程中需要應(yīng)用工程化原則。4.軟件工程過程

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

軟件工程過程通常由4個(gè)基本活動組成：plan

（軟件規(guī)格說明）、do（軟件開發(fā)）、check（軟件確認(rèn)）、action（軟件演進(jìn)）。軟件工程有3個(gè)要素：方法、工具和過程。

其中，方法是完成軟5.軟件生命周期

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

軟件的生命周期分為可行性分析與計(jì)劃制定、需求分析、軟件設(shè)計(jì)、軟件實(shí)現(xiàn)、軟件測試、運(yùn)行和維護(hù)等階段。6.軟件工程的目標(biāo)

軟件工程的目標(biāo)是在給定的成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。5.軟件生命周期

軟件的生命周期是指將軟件產(chǎn)品從提出、實(shí)現(xiàn)、7.軟件工程原則

軟件工程的原則有8個(gè)：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。

（1）抽象：抽取事務(wù)最基本的特征和行為，忽略非本質(zhì)細(xì)節(jié)。

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

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

（4）局部化：保證模塊之間具有松散藕合關(guān)系，模塊內(nèi)部具有較高的內(nèi)聚性。7.軟件工程原則

軟件工程的原則有8個(gè)：抽象、信息隱蔽、模（5）確定性：軟件開發(fā)過程中所有概念的表達(dá)應(yīng)該是明確的，無歧義且規(guī)范的。

（6）一致性：包括程序、數(shù)據(jù)和文檔的整個(gè)軟件系統(tǒng)的各模塊應(yīng)使用已知的概念、符號和術(shù)語；程序內(nèi)外接口應(yīng)保持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持一致。

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

（8）可驗(yàn)證性：開發(fā)大型軟件系統(tǒng)需要對系統(tǒng)自頂向下，逐層分解。系統(tǒng)分解應(yīng)遵循容易檢查、測評、評審的原則，以確保系統(tǒng)的正確性。（5）確定性：軟件開發(fā)過程中所有概念的表達(dá)應(yīng)該是明確的8.軟件工程研究內(nèi)容

軟件工程研究的內(nèi)容是軟件開發(fā)技術(shù)和軟件工程管理兩部分。

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

（2）軟件工程管理包括軟件管理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容。9.軟件開發(fā)工具與軟件開發(fā)環(huán)境

軟件開發(fā)工具和軟件開發(fā)環(huán)境是兩個(gè)不同的概念。8.軟件工程研究內(nèi)容

軟件工程研究的內(nèi)容是軟件開發(fā)技術(shù)和軟件

（1）軟件開發(fā)工具：最初的軟件開發(fā)工具只包含純程序設(shè)計(jì)語言，不含其他環(huán)節(jié)，如需求分析、軟件設(shè)計(jì)等環(huán)節(jié)的工具支持。

軟件開發(fā)工具從單工具支持向集成工具的支持方向發(fā)展。

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

值得注意的是計(jì)算機(jī)輔助軟件工程（CASE,ComputerAidedsoftwareEngineering）是當(dāng)前軟件開發(fā)環(huán)境中富有特色的研究工作和發(fā)展方向。CASE

就是成功的軟件開發(fā)環(huán)境的典型例子之一。（1）軟件開發(fā)工具：最初的軟件開發(fā)工具只包含純程序設(shè)計(jì)二、結(jié)構(gòu)化分析方法1.結(jié)構(gòu)化方法

結(jié)構(gòu)化方法是比較成熟的軟件開發(fā)方法，具體包括以下3個(gè)方面：軟件開發(fā)包括分析法、設(shè)計(jì)法和程序設(shè)計(jì)方法。

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

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

結(jié)構(gòu)化分析方法的常用工具有4種：數(shù)據(jù)流程圖、數(shù)據(jù)字典、判定表與判定樹。二、結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法的實(shí)質(zhì)是著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。3.數(shù)據(jù)流圖（DFD，DataFlowDiagram）

定義：從數(shù)據(jù)傳遞和加工的角度來刻畫數(shù)據(jù)流從輸入到輸出的移動變換過程。

功能：描述數(shù)據(jù)處理過程，也是需求理解的邏輯模型的圖形表示，直接支持系統(tǒng)的功能建模。結(jié)構(gòu)化分析方法的實(shí)質(zhì)是著眼于數(shù)據(jù)流，自頂向下，逐層分解數(shù)據(jù)流圖中的主要圖形元素如下表所示

數(shù)據(jù)流圖中的主要圖形元素如下表所示4.數(shù)據(jù)字典（DD）

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

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

內(nèi)容：數(shù)據(jù)字典通常包含的信息有名稱、別名、使用、內(nèi)容描述與補(bǔ)充信息等。5.判定表與判定樹

（1）判定樹

使用判定樹進(jìn)行描述時(shí)，應(yīng)先從問題定義的文字描述中分清哪些是判定的條件，哪些是判定的結(jié)論，根據(jù)描述材料中的連接詞找出判定條件之間的從屬關(guān)系、并列關(guān)系、選擇關(guān)系，根據(jù)它們構(gòu)造判定樹。4.數(shù)據(jù)字典（DD）

重要性：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心（2）判定表與判定樹相似，當(dāng)數(shù)據(jù)流圖中的加工要依賴于多個(gè)邏輯條件的取值時(shí)，即完成該加工的一組動作是由于某一組條件的組合引發(fā)的，使用判定表描述較適宜。判定表由基本條件、條件項(xiàng)、基本動作和動作項(xiàng)4個(gè)部分組成。6.軟件需求分析

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

需求分析階段主要工作有需求獲取、需求分析、編寫需求規(guī)格說明書和需求評審四種。

常用的需求分析方法有兩種：結(jié)構(gòu)化分析方法和面向?qū)ο蟮姆治龇椒ǎ?）判定表與判定樹相似，當(dāng)數(shù)據(jù)流圖中的加工要依賴于多個(gè)結(jié)構(gòu)化分析方法的具體實(shí)例有：面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法（SA）、面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法（JSD）、面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開發(fā)方法（DSSD）。三、結(jié)構(gòu)化設(shè)計(jì)方法1.軟件設(shè)計(jì)

做好軟件需求分析工作后就可以開始軟件設(shè)計(jì)了。軟件設(shè)計(jì)的基本目標(biāo)是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，也就是說軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。

從不同的角度分析，軟件設(shè)計(jì)的組成部分也不盡相同。結(jié)構(gòu)化分析方法的具體實(shí)例有：面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法（SA

（1）從工程管理角度分析，軟件設(shè)計(jì)需分兩步完成，即概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)(過程設(shè)計(jì))。

（2）從技術(shù)觀點(diǎn)分析，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(shè)計(jì)。軟件設(shè)計(jì)的基本原理有以下4種。

（1）抽象:抽象是思維工具，抽象的層次從概要設(shè)計(jì)到詳細(xì)設(shè)計(jì)逐步降低。

（2）模塊化：把一個(gè)待開發(fā)的軟件分解成若干個(gè)小的、簡單的部分。

（3）信息隱蔽:主要通過封裝來實(shí)現(xiàn)。

（4）模塊獨(dú)立性:每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，與其他模塊的聯(lián)系少且接口簡單。（1）從工程管理角度分析，軟件設(shè)計(jì)需分兩步完成，即概要2.模塊獨(dú)立性

模塊是指把一個(gè)待開發(fā)的軟件分解成若干個(gè)小的簡單的部分，每個(gè)模塊可以完成一個(gè)特定的子功能，各個(gè)模塊可以按一定的方法組織起來成為一個(gè)整體，從而實(shí)現(xiàn)整個(gè)系統(tǒng)的功能。

模塊的獨(dú)立性是評價(jià)設(shè)計(jì)好壞的重要標(biāo)準(zhǔn)。

衡量軟件的模塊獨(dú)立性的方法有兩種，即耦合性和內(nèi)聚性。

內(nèi)聚性是指從功能角度分析模塊內(nèi)部的聯(lián)系；

耦合性是模塊之間的相互聯(lián)系的緊密程度的度量。2.模塊獨(dú)立性

模塊是指把一個(gè)待開發(fā)的軟件分解成若干個(gè)小的簡3.概要設(shè)計(jì)

概要設(shè)計(jì)主要包括以下幾個(gè)方面:

①設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu);

②設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫;

③編寫概要設(shè)計(jì)文檔;

④概要設(shè)計(jì)文擋的審評。常用的軟件結(jié)構(gòu)設(shè)計(jì)工具是結(jié)構(gòu)圖(SC，structurechart)，也稱為程序結(jié)構(gòu)圖。結(jié)構(gòu)圖用于描述軟件系統(tǒng)的層次和分塊結(jié)構(gòu)關(guān)系，反映了整個(gè)系統(tǒng)的功能實(shí)現(xiàn)以及模塊之間的聯(lián)系和通訊，是未來程序中的控制層次體系。 3.概要設(shè)計(jì)

概要設(shè)計(jì)主要包括以下幾個(gè)方面:

①設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)圖中的基本圖形符號如下表所示。從工程管理角度分析，軟件設(shè)計(jì)需分兩步完成：概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)(過程設(shè)計(jì))。結(jié)構(gòu)圖中的基本圖形符號如下表所示。4.詳細(xì)設(shè)計(jì)

詳細(xì)設(shè)計(jì)的任務(wù)是為軟件結(jié)構(gòu)圖中的每個(gè)模塊確定實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用某種選定的表達(dá)工具表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。常見的詳細(xì)設(shè)計(jì)工具有以下3種。

（1）圖形工具:程序流程圖、N-S、PAD、HIPO。

（2）表格工具:判定表。

（3）語言工具:PDL(偽碼)4.詳細(xì)設(shè)計(jì)

詳細(xì)設(shè)計(jì)的任務(wù)是為軟件結(jié)構(gòu)圖中的每個(gè)模塊確定實(shí)程序流程圖用于詳細(xì)設(shè)計(jì)階段，它獨(dú)立于任何一種程序設(shè)計(jì)語言，其基本圖符如下表所示。程序流程圖用于詳細(xì)設(shè)計(jì)階段，它獨(dú)立于任何一種程序設(shè)計(jì)語言，其四、軟件測試做好軟件設(shè)計(jì)和實(shí)現(xiàn)后，接著可以進(jìn)行軟件測試了。軟件測試是軟件生命周期中的重要組成部分，可占總成本40%以上。軟件測試的目的是:檢撿是否滿足規(guī)定的需求或弄清預(yù)期結(jié)果與實(shí)際結(jié)果的差別。注意測試的目的是查找錯(cuò)誤，而不是演示軟件的正確功能。軟件測試有多種分類方法。

第一種分類方法:從是否需要執(zhí)行被測試軟件的角度可分為靜態(tài)測試和動態(tài)測試。

第二種分類方法:從功能劃分則可以分為白盒測試和黑盒測試。 四、軟件測試1.靜態(tài)測試與動態(tài)測試

靜態(tài)測試是不實(shí)際的軟件，主要通過人工進(jìn)行，具體包括代碼檢查、靜態(tài)結(jié)構(gòu)分析與代碼質(zhì)量度量等。

動態(tài)測試是指基于計(jì)算機(jī)的測試，為了發(fā)現(xiàn)錯(cuò)誤而執(zhí)行程序的過程。

動態(tài)測試通常以白盒動態(tài)測試測試為主，輔之以黑盒測試。動態(tài)測試的關(guān)鍵是設(shè)計(jì)高效、合理的測試用例。

測試用例是指為測試設(shè)計(jì)的數(shù)據(jù)，由測試輸入數(shù)據(jù)和與之對應(yīng)的預(yù)期輸出結(jié)果兩部分組成。1.靜態(tài)測試與動態(tài)測試

靜態(tài)測試是不實(shí)際的軟件，主要通過人工2.白盒測試與黑盒測試黑盒測試，又稱為功能測試或數(shù)據(jù)驅(qū)動測試，是對軟件已經(jīng)實(shí)現(xiàn)的功能是否滿足需求進(jìn)行測試和驗(yàn)證。它只測試功能，將其看作是一個(gè)黑盒子，不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特征，只依據(jù)程序的需求和功能規(guī)格說明書進(jìn)行測試。

黑盒測試主要有等價(jià)類劃分法、邊界分析法、錯(cuò)誤推測法、因果圖等。

黑盒測試方法主要用于軟件確認(rèn)測試。2.白盒測試與黑盒測試白盒測試法，又稱為結(jié)構(gòu)設(shè)計(jì)或邏輯驅(qū)動測試，主要用于測試結(jié)構(gòu)。這種方法將被測試對象看作是一個(gè)打開的盒子，允許測試人員利用程序內(nèi)部的邏輯結(jié)構(gòu)及有關(guān)信息來設(shè)計(jì)或選擇用例。它是根據(jù)軟件產(chǎn)品的內(nèi)部工作過程，檢查內(nèi)部成分，以確認(rèn)每種內(nèi)部操作符合設(shè)計(jì)規(guī)格要求。

白盒測試方法是在程序內(nèi)部進(jìn)行，主要用于完成軟件內(nèi)部操作的驗(yàn)證。常用的白盒測試方法有邏輯覆蓋和基本路徑測試等。白盒測試法，又稱為結(jié)構(gòu)設(shè)計(jì)或邏輯驅(qū)動測試，主要用于測試結(jié)構(gòu)。3.軟件測試的具體實(shí)施步驟

軟件測試的具體實(shí)施步驟依次為單元測試、集成測試、驗(yàn)收測試和系統(tǒng)測試。（1）單元測試是對軟件設(shè)計(jì)的最小單位——模塊(程序單元)進(jìn)行正確性檢驗(yàn)的測試。測試的依據(jù)是詳細(xì)設(shè)計(jì)說明書和源程序。（2）集成測試是測試和組裝的過程。它是把模塊在按照設(shè)計(jì)要求組裝的同時(shí)進(jìn)行測試，主要目的是發(fā)現(xiàn)與接口有關(guān)的錯(cuò)誤。測試的依據(jù)是概要設(shè)計(jì)說明書。

集成測試時(shí)將模塊組裝成程序通常采用兩種方法:非增量方式組裝(一次組裝在一起再進(jìn)行整體測試〉和增量方式組裝(邊連接邊測試)。3.軟件測試的具體實(shí)施步驟

軟件測試的具體實(shí)施步驟依次為單元（3）驗(yàn)收測試是驗(yàn)證軟件的功能和性能及其他特征是否滿足需求規(guī)格說明中確定的各種需求，以及軟件配置是否完善、正確。確認(rèn)測試一般以黑盒測試為主。（4）系統(tǒng)測試是將通過確認(rèn)的軟件作為整個(gè)基于計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、外設(shè)、支持軟件、數(shù)據(jù)和人員等其他系統(tǒng)元素組合在一起，在實(shí)際運(yùn)行環(huán)境下對計(jì)算機(jī)系統(tǒng)進(jìn)行一系列的集成測試和驗(yàn)收測試。（3）驗(yàn)收測試是驗(yàn)證軟件的功能和性能及其他特征是否滿足需求規(guī)五、程序調(diào)試程序調(diào)試是在測試成功后開始，程序調(diào)試的任務(wù)是診斷和改正程序中的錯(cuò)誤。程序調(diào)試活動由兩部分組成，

其一是根據(jù)錯(cuò)誤的跡象確定程序中錯(cuò)誤的確切性質(zhì)、原因和位置;

其二是對程序進(jìn)行修改、排除錯(cuò)誤。程序調(diào)試的基本步驟：

是錯(cuò)誤定位，修改設(shè)計(jì)和代碼，以排除錯(cuò)誤。調(diào)試的關(guān)鍵在于推斷程序內(nèi)部的錯(cuò)誤位置及原因。五、程序調(diào)試程序調(diào)試的原則：

（1）確定錯(cuò)誤的性質(zhì)和位置的原則。

要去思考分析與錯(cuò)誤征兆有關(guān)的信息，避開死胡同。只把調(diào)試工具當(dāng)做輔助手段來使用，它可以幫助思考，但不能代替思考。避免用試探法，最多只能把它當(dāng)作最后的手段。（2）修改錯(cuò)誤的原則。

修改所出現(xiàn)的錯(cuò)誤的一個(gè)常見失誤是只修改了這個(gè)錯(cuò)誤的征兆或表現(xiàn)，而沒有修改錯(cuò)誤本身。事實(shí)上，在出現(xiàn)錯(cuò)誤的地方，很可能還有別的錯(cuò)誤:在修正一個(gè)錯(cuò)誤的同時(shí)可能引入新的錯(cuò)誤;修改錯(cuò)誤的過程將迫使人們暫時(shí)回到程序設(shè)計(jì)階段。程序調(diào)試的原則：

（1）確定錯(cuò)誤的性質(zhì)和位置的原則。

要去思常見的調(diào)試方法有以下3種：

（1）強(qiáng)行排錯(cuò)。

這是最常用的但是效率最低的方法，主要思想是通過計(jì)算機(jī)找錯(cuò)。

（2）回溯法。

從出現(xiàn)錯(cuò)誤征兆處開始，人工地沿控制流程往回追蹤，直至發(fā)現(xiàn)出錯(cuò)的根源。

（3）原因排除法。

原因排除法是通過演繹和歸納，以及二分法來消除錯(cuò)誤。

值得注意的是，調(diào)試的成果是排錯(cuò)，為了修改程序中的錯(cuò)誤，往往會采用"補(bǔ)丁程序"來實(shí)現(xiàn)，而這種作法會引起整個(gè)程序質(zhì)量的下降。常見的調(diào)試方法有以下3種：

（1）強(qiáng)行排錯(cuò)。

這是最常用的但第四章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)本章要求數(shù)據(jù)庫的基本概念:數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)與數(shù)據(jù)庫系統(tǒng)。數(shù)據(jù)模型、實(shí)體聯(lián)系模型及E-R圖、從E-R圖導(dǎo)出的關(guān)系數(shù)據(jù)模型。關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理論。數(shù)據(jù)庫設(shè)計(jì)方法和步驟:需求分析、概念設(shè)計(jì)、邏輯設(shè)計(jì)和物理設(shè)計(jì)的相關(guān)策略。第四章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)本章要求第四章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)一、數(shù)據(jù)庫系統(tǒng)的基本概念二、數(shù)據(jù)模型三、關(guān)系代數(shù)四、數(shù)據(jù)庫設(shè)計(jì)與管理第四章數(shù)據(jù)庫設(shè)計(jì)基礎(chǔ)一、數(shù)據(jù)庫系統(tǒng)的基本概念一、數(shù)據(jù)庫系統(tǒng)的基本概念1.數(shù)據(jù)庫

數(shù)據(jù)庫(database)是指長期存儲在計(jì)算機(jī)內(nèi)的、有組織的、可共享的數(shù)據(jù)集合。它具有最小的冗余度，但卻有最高的獨(dú)立性。2.數(shù)據(jù)

數(shù)據(jù)〈data)是指描述事務(wù)的符號記錄。例如，描述一名學(xué)生的方法是(張三，男，1981，北京，黨員)。

數(shù)據(jù)是數(shù)據(jù)庫中存儲的基本對象。

數(shù)據(jù)庫中數(shù)據(jù)的特點(diǎn):按照一定的數(shù)據(jù)模型來組織、描述和儲存，具有較小的冗余度和較高的獨(dú)立性和易擴(kuò)展性，并為各種用戶所共享。

一、數(shù)據(jù)庫系統(tǒng)的基本概念3.數(shù)據(jù)庫系統(tǒng)

數(shù)據(jù)庫系統(tǒng)（DatabaseSystem，DBS）由計(jì)算機(jī)硬件、數(shù)據(jù)庫（數(shù)據(jù)）、數(shù)據(jù)庫管理系統(tǒng)（軟件）、應(yīng)用系統(tǒng)、數(shù)據(jù)庫管理員與用戶等部分組成。數(shù)據(jù)庫系統(tǒng)的發(fā)展有以下3個(gè)階段：

第一階段:20世紀(jì)50年代中期以前為人工管理階段，主要特點(diǎn)是數(shù)據(jù)不能保存、應(yīng)用程序管理數(shù)據(jù)、數(shù)據(jù)不共享、不具有數(shù)據(jù)獨(dú)立性。

第二階段:20世紀(jì)50年代后期到60年代中期的文件系統(tǒng)階段，主要特點(diǎn)是能長期保存數(shù)據(jù)，應(yīng)用文件系統(tǒng)管理數(shù)據(jù)、數(shù)據(jù)共享性差、數(shù)據(jù)獨(dú)立性差。3.數(shù)據(jù)庫系統(tǒng)

數(shù)據(jù)庫系統(tǒng)（DatabaseSystem，第三階段:20世紀(jì)60年代后期開始的數(shù)據(jù)庫系統(tǒng)階段。這時(shí)期的數(shù)據(jù)庫系統(tǒng)的特點(diǎn)如下所述。

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

②數(shù)據(jù)的共享性高、冗余度低、可以擴(kuò)充。

③應(yīng)用程序與數(shù)據(jù)獨(dú)立性高。

④數(shù)據(jù)自DBMS統(tǒng)一管理和控制。值得注意的是:數(shù)據(jù)結(jié)構(gòu)化是數(shù)據(jù)庫與文件系統(tǒng)的根本區(qū)別。4.數(shù)據(jù)庫管理系統(tǒng)

數(shù)據(jù)庫管理系統(tǒng)（DBMS）是指幫助用戶創(chuàng)建和管理數(shù)據(jù)庫的應(yīng)用程序的集合(軟件)。

DBMS是數(shù)據(jù)庫系統(tǒng)的核心。第三階段:20世紀(jì)60年代后期開始的數(shù)據(jù)庫系統(tǒng)階段。常用的數(shù)據(jù)庫管理系統(tǒng)有微軟公司的SQLServer、甲骨文公司的Oracle、IBM公司的DB2和IMS（層次）。5.數(shù)據(jù)庫應(yīng)用系統(tǒng)

數(shù)據(jù)庫應(yīng)用系統(tǒng)(DatabaseApplicationSystem，DBAS)是指利用數(shù)據(jù)庫系統(tǒng)進(jìn)行開發(fā)的一個(gè)應(yīng)用系統(tǒng)，由數(shù)據(jù)庫系統(tǒng)、應(yīng)用軟件及應(yīng)用界面這三者組成，具體包括數(shù)據(jù)庫、數(shù)據(jù)庫管理系統(tǒng)、數(shù)據(jù)庫管理員、硬件平臺、軟件平臺、應(yīng)用軟件與應(yīng)用界面。常用的數(shù)據(jù)庫管理系統(tǒng)有微軟公司的SQLServer、甲骨文6.數(shù)據(jù)庫管理員

由于數(shù)據(jù)庫的共享性，因此對數(shù)據(jù)庫的規(guī)劃、設(shè)計(jì)、維護(hù)、監(jiān)視等需要專人管理，稱他們?yōu)閿?shù)據(jù)庫管理員（DataBaseAdministrator，DBA）。DBA的主要工作是數(shù)據(jù)庫設(shè)計(jì)、數(shù)據(jù)庫維護(hù)、改善系統(tǒng)性能。7.數(shù)據(jù)庫系統(tǒng)的內(nèi)部體系結(jié)構(gòu)

從數(shù)據(jù)庫管理系統(tǒng)的角度看，數(shù)據(jù)庫系統(tǒng)有三級模式結(jié)構(gòu):模式、內(nèi)模式、外模式。

6.數(shù)據(jù)庫管理員

由于數(shù)據(jù)庫的共享性，因此對數(shù)據(jù)庫的規(guī)劃、設(shè)模式、內(nèi)模式、外模式。這3者關(guān)系如圖所示模式、內(nèi)模式、外模式。這3者關(guān)系如圖所示為了實(shí)現(xiàn)三級模式之間的轉(zhuǎn)換，數(shù)據(jù)庫系統(tǒng)在三級模式之間提供了兩個(gè)層次的映像，外模式/模式映像和模式/內(nèi)模式映像數(shù)據(jù)庫的二級映象保證了數(shù)據(jù)庫系統(tǒng)中的數(shù)據(jù)能夠具有較高的邏輯獨(dú)立性和物理獨(dú)立性。

（1）物理獨(dú)立性是指數(shù)據(jù)的物理結(jié)構(gòu)(包括存儲結(jié)構(gòu)、存取方式等)的改變，如存儲設(shè)備的更換、物理存儲的更換、存取方式的改變，都不影響數(shù)據(jù)庫的邏輯結(jié)構(gòu)，從而不致引起應(yīng)用程序的變化（物理結(jié)構(gòu)與應(yīng)用程序）。

（2）邏輯獨(dú)立性是指數(shù)據(jù)庫總體邏輯結(jié)構(gòu)的改變，如修改數(shù)據(jù)模式、增加新的數(shù)據(jù)類型、改變數(shù)據(jù)間聯(lián)系等，不需要相應(yīng)地修改應(yīng)用程序（全體邏輯結(jié)構(gòu)與應(yīng)用程序）。為了實(shí)現(xiàn)三級模式之間的轉(zhuǎn)換，數(shù)據(jù)庫系統(tǒng)在三級模式之間提供了兩二、數(shù)據(jù)模型1.數(shù)據(jù)模型的基本概念數(shù)據(jù)模型是指模擬現(xiàn)實(shí)世界中的實(shí)物及其之間關(guān)系的方法。數(shù)據(jù)模型有數(shù)據(jù)結(jié)構(gòu)（靜態(tài)）、數(shù)據(jù)操作（動態(tài)）和數(shù)據(jù)約束條件3個(gè)要素，其中數(shù)據(jù)結(jié)構(gòu)是最關(guān)鍵的要素。數(shù)據(jù)模型按不同的應(yīng)用層次可分為3種:

概念數(shù)據(jù)模型、邏輯數(shù)據(jù)模型、物理數(shù)據(jù)模型。

（1）概念模型:面向用