計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)-【考試必備

1、二級(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ū)⒃谟邢薜拇螖?shù)下終止。特征包括：（1）可行性；（2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；（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í)行的所有指令的集合

2、?；具\(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)包含

3、：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。線性結(jié)構(gòu)條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。13 線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。在復(fù)雜線性表中，由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個(gè)記錄構(gòu)成的線性表又稱為文件。非空線性表的結(jié)構(gòu)特征：（1）且只有一個(gè)根結(jié)點(diǎn)a1，它無前件；（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件；（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件

4、，也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長度，當(dāng)n=0時(shí)，稱為空表。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：（1）線性表中所有元素的所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。ai的存儲(chǔ)地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個(gè)元素的地址，k代表每個(gè)元素占的字節(jié)數(shù)。順序表的運(yùn)算：插入、刪除。 （詳見14-16頁）14 棧和隊(duì)列棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照“先進(jìn)后出”（FILO）或“后進(jìn)先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。用to

5、p表示棧頂位置，用bottom表示棧底。棧的基本運(yùn)算：（1）插入元素稱為入棧運(yùn)算；（2）刪除元素稱為退棧運(yùn)算；（3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無變化。隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。Rear指針指向隊(duì)尾，front指針指向隊(duì)頭。隊(duì)列是“先進(jìn)行出”（FIFO）或“后進(jìn)后出”（LILO）的線性表。隊(duì)列運(yùn)算包括（1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；（2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。循環(huán)隊(duì)列：s=0表示隊(duì)列空，s=1且front=rear表示隊(duì)列滿15 線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。

6、結(jié)點(diǎn)由兩部分組成：（1）用于存儲(chǔ)數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個(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)系是由指針域來確定的。鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結(jié)點(diǎn)，右指針（Rlink）指向后件結(jié)點(diǎn)。線性鏈表的基本運(yùn)算：查找、插入、刪除。16樹與二叉樹一、樹的基本概念在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的

7、結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱為樹的根。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。葉子結(jié)點(diǎn)的度為0。樹的最大層次稱為樹的深度。在一個(gè)算術(shù)表達(dá)式中，有運(yùn)算符和運(yùn)算對(duì)象。一個(gè)運(yùn)算符可以有若干個(gè)運(yùn)算對(duì)象。例職，取正（+）等只有一個(gè)運(yùn)算對(duì)象，稱為單目運(yùn)算符；二個(gè)運(yùn)算對(duì)象稱為雙目運(yùn)算符，三目運(yùn)算符。用樹來表示算術(shù)表達(dá)式的原則如下：表達(dá)式中的每一個(gè)運(yùn)算符在樹中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)。運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹中為該運(yùn)算符結(jié)點(diǎn)的子樹（在樹中的順序?yàn)閺淖蟮接遥?。運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。二、二

8、叉樹及其基本性質(zhì)1、什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)。二就樹具有以下兩個(gè)特點(diǎn)：非空二叉樹只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。由以上特點(diǎn)可以看出，在二叉樹中，每一個(gè)結(jié)點(diǎn)的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。另外，二叉樹中的每一個(gè)結(jié)點(diǎn)的子樹被明顯地分為左子樹與右子樹?？梢詻]有其中的一個(gè)，也可以全沒有。二叉樹的基本性質(zhì)性質(zhì)1：在二叉樹的第K層上，最多有（K1）個(gè)結(jié)點(diǎn)。性質(zhì)2：濃度為M的二叉樹最多有2m-1 個(gè)結(jié)點(diǎn)。深度為m 的二叉樹是指二叉樹共有m層。性質(zhì)3：在任意一棵二叉樹中度為0的結(jié)點(diǎn)（即

9、葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為 log2n+1,其中 log2n表示取的整數(shù)部分。滿二叉樹與完全二叉樹滿二叉樹與完全二叉樹是兩種特殊形態(tài)的二叉樹。滿二叉樹所謂滿二叉樹是指這樣的一種二叉樹；除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。這就是說，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第K層上有2K-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹有2m-1個(gè)結(jié)點(diǎn)。完全二叉樹所謂完全二叉樹是指這樣的二叉樹，除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)的最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。列確切地說，如果從根結(jié)點(diǎn)起，對(duì)二叉樹的結(jié)點(diǎn)自上而下、自左至右用自

10、然數(shù)進(jìn)行邊疆編號(hào)，則深度為m、且有n 個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹。對(duì)于完全二叉樹來說，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右分支下的子孫結(jié)點(diǎn)的最大層次為p，則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)閜，或?yàn)閜+1。由滿二叉樹與完全二叉樹的特點(diǎn)可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。完全二叉樹還具有以下兩個(gè)性質(zhì)：性質(zhì)5：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n+1。性質(zhì)6：設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，n給結(jié)點(diǎn)進(jìn)行編號(hào)

11、，則對(duì)于編號(hào)為k （k=1,2,n）的結(jié)點(diǎn)有以下結(jié)論：若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。若2kn，則編號(hào)為k 的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k ；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）。若2k+1n，則編號(hào)為k 的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。三、二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。1、前序遍歷（DLR）所謂前序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷

12、左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。F，C，A，D，B，E，G，H，P2、中序遍歷（LDR）所謂中序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。A，C，B，D，F(xiàn)，E，H，G，P3、后序遍歷（LRD）所謂中序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。A，B，D，C，H，P，G，E，F(xiàn)1.7查找技術(shù)一、

13、順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。順序查找的效率是很低的。以下兩種情況只能采用順序查找：如果線性表無序表（即表中元素的排列是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。二、二分法查找二分法查找只適用于存儲(chǔ)的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小

14、到大，但允許相鄰元素值相等）。設(shè)有序線性表的長度為n，被查元素為x，則對(duì)分查找的方法如下：將x與線性表的中間項(xiàng)進(jìn)行比較：若中間項(xiàng)的值等于x，則說明查到，查找結(jié)束；若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。這個(gè)過程一直進(jìn)行到查找成功或子表長度為0（說明線性表中沒有這個(gè)元素）為止。顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，并且，二分查找的效率要比順序查找高得多?？梢宰C明，對(duì)于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。1

15、.8排序技術(shù)一、交換類排隊(duì)序法所謂交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。1、 冒泡排序法基本過程如下：首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個(gè)逆序。放最大值然后，從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，后面的元素大于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。放最小值。重復(fù)上述過程，直到剩下的線性有變空為止，此時(shí)的線性表已經(jīng)變?yōu)橛行颉＜僭O(shè)線性表的長為n，則在最壞情況

16、下，冒泡排序需要經(jīng)過n/2遍的蔥馨往后的掃描和n/2遍的從后往前的掃描，需要的比較的次數(shù)為n(n-1)/2。2、 快速排序法快速排序法也是種互換類的排序法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法?；舅枷肴缦拢簭木€性表中選取一個(gè)元素，設(shè)T，將線性表后面小于T的元素移到前，而前大于T的元素移支后面，結(jié)果就將線性表分成了兩部分（稱為兩個(gè)子表），T插入到其分界線的位置處，這個(gè)過程稱為線性表的分割。通過對(duì)線性表的一次分割，就以T為分界線，將線性表分成了前后兩個(gè)子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。如此反復(fù)，則此時(shí)的線性表就變成了有序表。步驟：首先，在表的

17、第一個(gè)，中間一個(gè)與最后一個(gè)元素中選取中項(xiàng)，設(shè)為P（K），并將P（K）賦給T，再將表中的第一個(gè)元素移到P（K）的位置上。然后設(shè)置兩個(gè)指針i和j分別指向表的起始與最后的位置。反復(fù)操作以下兩步：（4） 將j逐漸減小，并逐次比較P（j）與T，直到發(fā)現(xiàn)一個(gè)P(j)T為止，將P(i)移到P(j)位置上。上述兩個(gè)操作交替進(jìn)行，直到指針i與j 指向同一個(gè)位置（即i=j）為止，此時(shí)將P(i)的位置上。分割需要記憶，用棧來實(shí)現(xiàn)。二、 插入類排序法1、 簡單插入排序法所謂插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。一般來說，假設(shè)線性中前j-1元素已經(jīng)有序，現(xiàn)在要將線性表中第j個(gè)元素插入到前面的有

18、序子表中，插入過程如下：道德將第j個(gè)元素放到一個(gè)變量T中，然后從有序子表的最后一個(gè)元素（即線性表中第j-1個(gè)元素）開始，往前逐個(gè)與T進(jìn)行比較，將大于T的元素均依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)一個(gè)元素不大于T為止，此時(shí)就將T（即原線性表中的第j個(gè)元素）插入到剛移出的空位置上，有序子表的長度就變?yōu)閖了。效率與冒泡法相同在最壞情況下，簡單插入排序需要n(n-1)/2次比較。2、 希爾排序法基本思想如下：將整個(gè)無序序列分割成若干小的子序列分別進(jìn)行插入排序。子序列的分割方法如下：將相隔某個(gè)增量H的元素構(gòu)成一個(gè)子序列。在排序過程中，逐次減小這個(gè)增量，最后當(dāng)H減到1時(shí)，進(jìn)行一次插入排序，排序就完成。增量序列一

19、般取h=n/2k(k=1,2,log2n,其中n為待排序序列的長度。其效率與增量序列有關(guān)。在最壞情況下，需要的比較次數(shù)為O（.）。三、 選擇類排序法、 簡單選擇排序法基本思想：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面；然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。簡單選擇排序法在最壞情況下需要比較n(n-1)/2/次。、 堆排序法方法：（1）首先將一個(gè)無序序列建成堆。（2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。不考慮已經(jīng)換到最后的那個(gè)元素，只考慮前n-1個(gè)元素構(gòu)成的子序，顯然，該子序列已不是堆，但左、右子樹仍為堆，可以將該子序列調(diào)事

20、為堆。反復(fù)做第（2）步，真到剩下的子序列為空為止。適用規(guī)模較大的線性表，在最壞情況下，堆排序需要比較的次數(shù)為O（nlog2n）。 1.7查找技術(shù)一、順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失?。?。順序查找的效率是很低的。以下兩種情況只能采用順序查找：如果線性表無序表（即表中元素的排列是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。即使是有序線

21、性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。二、二分法查找二分法查找只適用于存儲(chǔ)的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。設(shè)有序線性表的長度為n，被查元素為x，則對(duì)分查找的方法如下：將x與線性表的中間項(xiàng)進(jìn)行比較：若中間項(xiàng)的值等于x，則說明查到，查找結(jié)束；若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。這個(gè)過程一直進(jìn)行到查找成功或子表長度為0（說明線性表中沒有這個(gè)元素）為止。顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，

22、并且，二分查找的效率要比順序查找高得多。可以證明，對(duì)于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。1.8排序技術(shù)一、交換類排隊(duì)序法所謂交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。1、 冒泡排序法基本過程如下：首先，從表頭開始往后掃描線性表，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個(gè)逆序。放最大值然后，從后到前掃描剩下的線性表，同樣，在掃描過程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，后面的元素大于前面的元素

23、，則將它們互換，這樣就又消去了一個(gè)逆序。放最小值。重復(fù)上述過程，直到剩下的線性有變空為止，此時(shí)的線性表已經(jīng)變?yōu)橛行?。假設(shè)線性表的長為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的蔥馨往后的掃描和n/2遍的從后往前的掃描，需要的比較的次數(shù)為n(n-1)/2。2、 快速排序法快速排序法也是種互換類的排序法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法?；舅枷肴缦拢簭木€性表中選取一個(gè)元素，設(shè)T，將線性表后面小于T的元素移到前，而前大于T的元素移支后面，結(jié)果就將線性表分成了兩部分（稱為兩個(gè)子表），T插入到其分界線的位置處，這個(gè)過程稱為線性表的分割。通過對(duì)線性表的一次分割，就以T為分界線，將線性

24、表分成了前后兩個(gè)子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。如此反復(fù)，則此時(shí)的線性表就變成了有序表。步驟：首先，在表的第一個(gè)，中間一個(gè)與最后一個(gè)元素中選取中項(xiàng)，設(shè)為P（K），并將P（K）賦給T，再將表中的第一個(gè)元素移到P（K）的位置上。然后設(shè)置兩個(gè)指針i和j分別指向表的起始與最后的位置。反復(fù)操作以下兩步：（4） 將j逐漸減小，并逐次比較P（j）與T，直到發(fā)現(xiàn)一個(gè)P(j)T為止，將P(i)移到P(j)位置上。上述兩個(gè)操作交替進(jìn)行，直到指針i與j 指向同一個(gè)位置（即i=j）為止，此時(shí)將P(i)的位置上。分割需要記憶，用棧來實(shí)現(xiàn)。二、 插入類排序法1、 簡單插入排序法所

25、謂插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。一般來說，假設(shè)線性中前j-1元素已經(jīng)有序，現(xiàn)在要將線性表中第j個(gè)元素插入到前面的有序子表中，插入過程如下：道德將第j個(gè)元素放到一個(gè)變量T中，然后從有序子表的最后一個(gè)元素（即線性表中第j-1個(gè)元素）開始，往前逐個(gè)與T進(jìn)行比較，將大于T的元素均依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)一個(gè)元素不大于T為止，此時(shí)就將T（即原線性表中的第j個(gè)元素）插入到剛移出的空位置上，有序子表的長度就變?yōu)閖了。效率與冒泡法相同在最壞情況下，簡單插入排序需要n(n-1)/2次比較。2、 希爾排序法基本思想如下：將整個(gè)無序序列分割成若干小的子序列分別進(jìn)行插入排序。子

26、序列的分割方法如下：將相隔某個(gè)增量H的元素構(gòu)成一個(gè)子序列。在排序過程中，逐次減小這個(gè)增量，最后當(dāng)H減到1時(shí)，進(jìn)行一次插入排序，排序就完成。增量序列一般取h=n/2k(k=1,2,log2n,其中n為待排序序列的長度。其效率與增量序列有關(guān)。在最壞情況下，需要的比較次數(shù)為O（.）。三、 選擇類排序法、 簡單選擇排序法基本思想：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面；然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。簡單選擇排序法在最壞情況下需要比較n(n-1)/2/次。、 堆排序法方法：（1）首先將一個(gè)無序序列建成堆。（2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最

27、大項(xiàng)應(yīng)該在序列的最后）。不考慮已經(jīng)換到最后的那個(gè)元素，只考慮前n-1個(gè)元素構(gòu)成的子序，顯然，該子序列已不是堆，但左、右子樹仍為堆，可以將該子序列調(diào)事為堆。反復(fù)做第（2）步，真到剩下的子序列為空為止。適用規(guī)模較大的線性表，在最壞情況下，堆排序需要比較的次數(shù)為O（nlog2n）。習(xí)題一一、選擇題1、算法的時(shí)間復(fù)雜度是指（ ）A）執(zhí)行算法程序所需要的時(shí)間 B）算法程序的長度C）算法執(zhí)行過程中所需要的基本運(yùn)算次數(shù) D）算法程序中的指令條數(shù)2、算法的窨復(fù)雜度是指（ ）A、算法程序的長度 B、算法程序中的指令條數(shù)C、算法程序所占的存儲(chǔ)空間 D、算法執(zhí)行過程中所需要的存儲(chǔ)空間3、下列敘述中正確的是（ ）A、

28、線性表是線性結(jié)構(gòu) B、材與隊(duì)列是非線性結(jié)構(gòu)C、線性鏈表是非線性結(jié)構(gòu) D、二叉樹是線性結(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)先出的線性表 D、隊(duì)列是先進(jìn)后出的線性表6、下列關(guān)于棧的敘述中正確的是（ ）A、在棧中只能插入數(shù)據(jù) B、在棧中只能刪除數(shù)據(jù)C、棧是先進(jìn)先出的線性表 D、棧是先進(jìn)后出的線性表7、設(shè)有下列二叉樹：對(duì)此二叉樹中序遍歷的結(jié)果為A、ABCDEF B、DBEAFC C、ABDE

29、CF D、DEBFCA8、在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（ ）A、32 B、31 C、16 D、159、對(duì)長度為 n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為（ ）A、 n+1 B、n C、(n+1)/2 D、n/210、設(shè)樹T的度為4，其中度為1，2，3，4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1。則T中的葉子結(jié)點(diǎn)數(shù)為（ ）A、8 B、7 C、6 D、5二、填空題1、在長度為n 的有序線性表中進(jìn)行二分查找，需要的比較次數(shù)為 。2、設(shè)一棵完全二叉共有700個(gè)結(jié)點(diǎn)，則在該二叉樹中有 個(gè)葉子結(jié)點(diǎn)。3、設(shè)一棵二叉樹中序遍歷結(jié)果為DBEAFC ，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為

30、。4、在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為 。5、在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊(duì)列中共有 個(gè)元第2章 程序設(shè)計(jì)基礎(chǔ)21 程序設(shè)計(jì)方法與風(fēng)格就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)過了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。一般來講。程序設(shè)計(jì)風(fēng)格是指編寫程序時(shí)所表現(xiàn)出的特點(diǎn)、習(xí)慣和邏輯思路。程序是由人來編寫的，為了測試和維護(hù)程序，往往還要新聞?dòng)浾吆透櫝绦?，因此程序設(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)名

31、的命名：符號(hào)名的命名應(yīng)具有一定的實(shí)際含義，以便于對(duì)程序功能的理解。（2） 程序注釋：下克的注釋能夠幫助讀者理解程序。（3） 禮堂組織：為使程序的結(jié)構(gòu)一目了然，可以在程序中利用空格、空行、縮進(jìn)待技巧使程序?qū)哟吻逦?、數(shù)據(jù)說明的方法在編寫程序時(shí)，需要注意數(shù)據(jù)說明的風(fēng)格，以便使程序中的數(shù)據(jù)說明更易于理解和維護(hù)。一般應(yīng)注意如下幾點(diǎn)：（1） 數(shù)據(jù)說明的次序規(guī)范化鑒于程序理解、新聞?dòng)浾吆途S護(hù)的需要，使數(shù)據(jù)說明次序固定，可以使數(shù)據(jù)的發(fā)生容易查找，也有利于測試、排錯(cuò)和維護(hù)。（2） 說明語句中變量安排有序化。當(dāng)一個(gè)說明語句說明多個(gè)變量時(shí)，變量按照字母順序?yàn)楹?。?） 使用注釋來說明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。3、 語句的

32、結(jié)構(gòu)程序應(yīng)該簡單易懂，語句構(gòu)造應(yīng)該簡單直接，不應(yīng)該為提高效率而把語句復(fù)雜化。一般應(yīng)注意如下：（1） 在一行內(nèi)只寫一條語句；（2） 程序編寫應(yīng)優(yōu)先考慮清晰性；（3） 除非對(duì)效率有特殊要求，程序編寫要做清晰第一，效率第二；（4） 首先要保證程序正確，然后才要求提高速度；（5） 避免使用臨時(shí)變量而使程序的可讀性下降；（6） 避免不必要的轉(zhuǎn)移；（7） 盡可能使用庫函數(shù)；（8） 避免采用復(fù)雜的條件語句；（9） 盡量減少使用“否定”條件的條件語句；（10） 數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化；（11） 要模塊化，使模塊功能盡可能單一化；（12） 利用住處隱蔽，確保每一個(gè)模塊的獨(dú)立性；（13） 從數(shù)據(jù)出發(fā)去構(gòu)造程序

33、；（14） 不要修補(bǔ)不好的程序，要重新編寫；4、輸入和輸出無論是批處理的輸入和輸出方式，還是交互式的輸入和輸出方式，在設(shè)計(jì)和編程時(shí)都應(yīng)該考慮如下原則：（1） 對(duì)所有的輸入數(shù)據(jù)都要檢驗(yàn)數(shù)據(jù)的合法性；（2） 檢查輸入項(xiàng)的各種重要組合的合理性；（3） 輸入格式要簡單，以使得輸入的步驟和操作盡可能簡單；（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ù)輸入過程中的輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息。（8） 當(dāng)程序設(shè)計(jì)語言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸

34、入格式與輸入語句的一致性；給所有的輸入出加注釋，并設(shè)計(jì)輸出報(bào)表格式。22結(jié)構(gòu)化程序設(shè)計(jì)一、結(jié)構(gòu)化程序設(shè)計(jì)的原則結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為自頂向下，逐步求精，模塊化，限制使用goto語句。1、 自頂向下：程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開始就過多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開始設(shè)計(jì)，逐步使問題具體化。2、 逐步求精：對(duì)復(fù)雜問題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過渡，逐步細(xì)化。3、 模塊化：一個(gè)復(fù)雜問題，肯定是由若干稍簡單的問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。4、 限制使用goto語

35、句使用goto語句經(jīng)實(shí)驗(yàn)證實(shí)：（1）濫用GOTO語句確實(shí)有害，應(yīng)晝避免；（2）完全避免使用GOTO語句也并非是個(gè)明智的方法，有些地方使用GOTO語句，會(huì)使程序流程更清楚、效率更高；（3）爭論的焦點(diǎn)不應(yīng)該放在是否取消GOTO語句，而應(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)是簡單的程序設(shè)計(jì)，它是最基本、最常用的結(jié)構(gòu)，所謂順序執(zhí)行，就是按照程序語句行的自然順序，一條語句一條語句地執(zhí)行程序程序。2、選擇結(jié)構(gòu)：選擇結(jié)構(gòu)又稱為分支結(jié)構(gòu)，它包括簡單選擇和多分支選擇結(jié)構(gòu)，這種結(jié)構(gòu)可以根據(jù)設(shè)定的條件，判斷應(yīng)該選擇哪

36、一條分支來執(zhí)行相應(yīng)的語句序列。3、重復(fù)結(jié)構(gòu)：重復(fù)結(jié)構(gòu)又稱為循環(huán)結(jié)構(gòu)，它根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類似的程序段，利用重復(fù)結(jié)構(gòu)可簡化大量的程序行。分為兩類：一是先判斷后執(zhí)行，一是先執(zhí)行后判斷。優(yōu)點(diǎn)：一是程序易于理解、使用和維護(hù)。二是編程工作的效率，降低軟件開發(fā)成本。三、結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用要注意把握如下要素：1、 使用程序設(shè)計(jì)語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。2、 選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口；3、 程序語句組成容易識(shí)別的塊，每塊只有一個(gè)入口和一個(gè)出口；4、 復(fù)雜結(jié)構(gòu)應(yīng)該嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn)；5、 語言中所沒有的

37、控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來模擬；6、 嚴(yán)格控制GOTO語句的使用。其意思是指：（1） 用一個(gè)非結(jié)構(gòu)化的程序設(shè)計(jì)語言去實(shí)現(xiàn)一個(gè)結(jié)構(gòu)化的構(gòu)造；（2） 若不使用GOTO語句會(huì)使功能模糊；（3） 在某種可以改善而不損害程序可讀性的情況下。 23面向?qū)ο蟮某绦蛟O(shè)計(jì)一、關(guān)于面向?qū)ο蠓椒嫦驅(qū)ο蠓椒ǖ谋举|(zhì)，就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實(shí)生活中常用的思維方法來認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域，也就是說，系統(tǒng)中的對(duì)象以及對(duì)象之間的關(guān)系能夠如實(shí)地反映問題域中固有事物及其關(guān)系。優(yōu)點(diǎn)：1、與人類習(xí)慣的思維方法一致面向?qū)ο蠓椒ê图夹g(shù)以對(duì)象為核心。對(duì)象是由數(shù)

38、據(jù)和容許的操作組成的封裝體，與客觀實(shí)體有直接的關(guān)系。對(duì)象之間通過傳遞消息互相聯(lián)系，以模擬現(xiàn)實(shí)世界中不同事物彼此之間的聯(lián)系。面向?qū)ο蟮脑O(shè)計(jì)方法與傳統(tǒng)的面向過程的方法有本質(zhì)不同，這種方法的基本原理是：使用現(xiàn)實(shí)世界的概念抽象地思考問題從而自然地解決問題。它強(qiáng)調(diào)模擬現(xiàn)實(shí)世界中的概念而不強(qiáng)調(diào)算法，它鼓勵(lì)開發(fā)者在軟件開發(fā)的絕大部分過程中都用應(yīng)用領(lǐng)域的要領(lǐng)去思考。2、穩(wěn)定性好3、可重用性好軟件重用是指在不同的軟件開發(fā)過程中重復(fù)作用相同或相似軟件元素的過程。重用是提高軟件生產(chǎn)率的最主要的方法。4、易于開發(fā)大型軟件產(chǎn)品5、可維護(hù)性好（1）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件穩(wěn)定性比較好（2）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件比較

39、容易修改；（3）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件比較容易理解。（4）易于測試和調(diào)試。二、面向?qū)ο蠓椒ǖ幕靖拍?、對(duì)象（object）對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。?duì)象可以用來表示客觀世界中的任何實(shí)體，也就是說，應(yīng)用領(lǐng)域中有意義的、與所要解決的問題有關(guān)系的任何事物都可以作為對(duì)象，它既可以是具體的物理實(shí)體的抽象，也可以是人為的概念，或者是任何有明確邊界的意義的東西。總之，對(duì)象是對(duì)問題域中某個(gè)實(shí)體的抽象，設(shè)立某個(gè)對(duì)象就反映軟件系統(tǒng)保存有關(guān)它的信息并具有與它進(jìn)行交互的能力。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對(duì)象是系統(tǒng)中用來描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，它由一組表示其靜態(tài)特征的屬性和它可

40、執(zhí)行的一組操作組成。對(duì)象可以做的操作表示它的動(dòng)態(tài)行為，在面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O(shè)計(jì)中，通常把對(duì)象的操作也稱為方法或服務(wù)。屬性即對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過掛靠對(duì)象的操作來改變。操作描述了對(duì)象執(zhí)行的功能，若通過消息傳遞，還可以為其他對(duì)象使用。操作的過程對(duì)外是封閉的，即用戶只能看到這一操作實(shí)施后的結(jié)果。這相當(dāng)于事先已經(jīng)設(shè)計(jì)好的各種過程，只需要調(diào)用就可以了，用戶不必去關(guān)心這一過程是如何編寫的。事實(shí)上，這個(gè)過程已經(jīng)封裝在對(duì)象中，用戶也看不到。對(duì)的這一特性即是對(duì)象的封裝性。對(duì)象有如下一些基本特點(diǎn)：（1） 標(biāo)識(shí)惟一性。指對(duì)象是可區(qū)分的，并且由對(duì)象有的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)

41、分。（2） 分類性。指可以將具有相同屬性的操作的對(duì)象抽象成類。（3） 多太性。指同一個(gè)操作可以是不同對(duì)象的行為。（4） 封裝性。從外面看只能看到對(duì)象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。對(duì)象的內(nèi)部，即處理能力的實(shí)行和內(nèi)部狀態(tài)，對(duì)外是不可見的。從外面不能直接使用對(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ù)所需做的處理來設(shè)置，沒有無關(guān)的操作從模塊的獨(dú)立性

42、考慮，對(duì)象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強(qiáng)。2、類（Class）和實(shí)例(Instance)將屬性、操作相似的對(duì)象歸為類，也就是說，類是具有共同屬性、共同方法的對(duì)象的集合。所以，類是對(duì)象的抽象，它描述了屬于該對(duì)象類型的所有對(duì)象的性質(zhì)，而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例。要注意的是，當(dāng)使用“對(duì)象”這個(gè)術(shù)語時(shí)，既可以指一個(gè)具體的對(duì)象，也可以泛指一般的對(duì)象，但是，當(dāng)使用“實(shí)例”這個(gè)術(shù)語時(shí)，必然是指一個(gè)具體的對(duì)象。例如：Integer是一個(gè)整數(shù)類，它描述了所有整數(shù)的性質(zhì)。因此任何整數(shù)都是整數(shù)類的對(duì)象，而一個(gè)具體的整數(shù)“123”是類Integer的實(shí)例。由類的定義可知，類是關(guān)于對(duì)象性質(zhì)的描述，它同對(duì)象

43、一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。3、消息（Message）面向?qū)ο蟮氖澜缡峭ㄟ^對(duì)象與對(duì)象間彼此的相互合作來推動(dòng)的，對(duì)象間的這種相互合作需要一個(gè)機(jī)制協(xié)助進(jìn)行，這樣的機(jī)制稱為“消息”。消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞信息，它請(qǐng)示對(duì)象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流的控制流。消息的使用類似于函數(shù)調(diào)用，消息中指定了某一個(gè)實(shí)例，一個(gè)操作名和一個(gè)參數(shù)表（可空）。接收消息的實(shí)例執(zhí)行消息中指定的操作，并將形式參數(shù)數(shù)與參數(shù)表中相應(yīng)的值結(jié)合起來。消息傳遞過程中，由發(fā)送消息的對(duì)象（發(fā)送對(duì)象）的觸發(fā)操作產(chǎn)生輸出結(jié)果，作為消息傳送至接受消息的對(duì)象（接受對(duì)象），引發(fā)接受消息的對(duì)象一系列的

44、操作。所傳送的消息實(shí)質(zhì)上是接受對(duì)象所具有的操作/方法名稱，有時(shí)還包括相應(yīng)參數(shù)。消息中只包含傳遞者的要求，它告訴接受者需要做哪些處理，但并不指示接受者應(yīng)該怎樣完成這些處理。消息完全由接受者解釋，接受者獨(dú)立決定采用什么方式完成所需的處理，發(fā)送者對(duì)接受者不起任何控制作用。一個(gè)對(duì)象能夠接受不同形式、不同內(nèi)容的多個(gè)消息；相同形式的消息可以送往不同的對(duì)象，不同的對(duì)象對(duì)于形式相同的消息可以有不同的解釋，能夠做出不同的反映。一個(gè)對(duì)象可以同時(shí)往多個(gè)對(duì)象傳遞信息，兩個(gè)對(duì)象也可以同時(shí)向某個(gè)對(duì)象傳遞消息。例如，一個(gè)汽車對(duì)象具有“行駛”這項(xiàng)操作，那么要讓汽車以時(shí)速50公里行駛的話，需傳遞給汽車對(duì)象“行駛”及“時(shí)速50公

45、里”的消息。通常，一個(gè)消息由下述三部分組成：（1） 接收消息的對(duì)象的名稱；（2） 消息標(biāo)識(shí)符（也稱為消息名）；（3） 零個(gè)或多個(gè)參數(shù)。4、 繼承（Inheritance）繼承是面向?qū)ο蟮姆椒ǖ囊粋€(gè)主要特征。繼承是使用己有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。已有的類可當(dāng)作基類來引用，則新類相應(yīng)地可當(dāng)作派生類來引用。廣義地說，繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。面向?qū)ο筌浖夹g(shù)的許多強(qiáng)有力的功能和突出的優(yōu)點(diǎn)，都來源于把類組成一個(gè)層次結(jié)構(gòu)的系統(tǒng)：一個(gè)類的上層可以有父類，下層可以有子類。這種層次結(jié)構(gòu)系統(tǒng)的一個(gè)重要性質(zhì)是繼承性，一個(gè)類直接繼承其父類的描述（數(shù)據(jù)和操作）或特性，子類自

46、動(dòng)地共享基類中定義的數(shù)據(jù)和方法。繼承具有傳遞性，如果類C繼承類B，類B繼承類A，則類C繼承類A。因此一個(gè)類實(shí)際上繼承了它上層的全部基類的特性，也就是說，屬于某類的對(duì)象除了具有該類所定義的特性外，還具有該類上層全部基類定義的特性。繼承分為單繼承與多重繼承。單繼承是指，一個(gè)類只允許有一個(gè)父類，即類等級(jí)為樹形結(jié)構(gòu)。多重繼承是指，一個(gè)類允許有多個(gè)父類。多重繼承的類可以組合多個(gè)父類的性質(zhì)構(gòu)成所需要的性質(zhì)。因此，功能更強(qiáng)，使用更方便；便是，使用多重繼承時(shí)要注意避免二義性。繼承性的優(yōu)點(diǎn)是，相似的對(duì)象可以共享程序代碼和數(shù)據(jù)結(jié)構(gòu)，從而大大減少了程序中的冗余信息，提高軟件的可重用性，便于軟件個(gè)性維護(hù)。此外，繼承性

47、便利用戶在開發(fā)新的應(yīng)用系統(tǒng)時(shí)不必完全從零開始，可以繼承原有的相似系統(tǒng)的功能或者從類庫中選取需要的類，再派生出新的類以實(shí)現(xiàn)所需要的功能。5、 多太性（Polymorphism）對(duì)象根據(jù)所接受 的消息而做出動(dòng)作，同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)，該現(xiàn)象稱為多態(tài)性。在面向?qū)ο蟮能浖夹g(shù)中，多態(tài)性是指類對(duì)象可以像父類對(duì)象那樣使用，同樣的消息既可以發(fā)送給父類對(duì)象也可以發(fā)送給子類對(duì)象。多態(tài)性機(jī)制不僅增加了面向?qū)ο筌浖到y(tǒng)的靈活性，進(jìn)一步減少了信息冗余，而且顯著地提高了軟件的可重用性和可擴(kuò)充性。當(dāng)擴(kuò)充系統(tǒng)功能增加新的實(shí)體類型時(shí)，只需派生出與新實(shí)體類相應(yīng)的新的子類，完全無需修改原有的程序代碼，

48、甚至不需要重新編譯原有的程序。利用多態(tài)性，用戶能夠發(fā)送一般形式的消息，而將所有的實(shí)現(xiàn)細(xì)節(jié)都留給接受消息的對(duì)象。 第3章 軟件工程基礎(chǔ)31軟件工程基本概念一、軟件定義與軟件特點(diǎn)計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。基中，程序是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的用程序設(shè)計(jì)語言描述的、適合計(jì)算機(jī)執(zhí)行的指令（語句）序列。數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔是與程序開發(fā)、維護(hù)和使用有關(guān)的圖文資料?？梢娷浖蓛刹糠纸M成：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是機(jī)器不可執(zhí)行的，與軟件開發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。國標(biāo)（GB）中對(duì)計(jì)算機(jī)軟件的定義為：與計(jì)算機(jī)系

49、統(tǒng)的操作有關(guān)的計(jì)算機(jī)程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數(shù)據(jù)。軟件在開發(fā)、生產(chǎn)、維護(hù)和使用等方面與計(jì)算機(jī)硬件相比存在明顯的差異。深入理解軟件的定義需要了解軟件的特點(diǎn)：（1） 軟件是一種邏輯實(shí)體，而不是物理實(shí)體具有抽象性。（2） 軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程。一旦研制開發(fā)成功，可以大量拷貝同一內(nèi)容的副本。所以對(duì)軟件的控制，必須著重在軟件開發(fā)方面下功夫。（3） 軟件在運(yùn)行、使用期間不存在磨損、老化問題。（4） 軟件的開發(fā)運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制這導(dǎo)致了軟件移植的問題。（5） 軟件復(fù)雜性高，成本昂貴。（6） 軟件開發(fā)涉及諸多的社會(huì)因素。軟件按功能可以分為：應(yīng)

50、用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。應(yīng)用軟件是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件。系統(tǒng)軟件是計(jì)算機(jī)管理自身資源，提高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶提供各種服務(wù)的軟件。支撐軟件是介于系統(tǒng)軟件和應(yīng)用軟件之間，協(xié)助用戶開發(fā)軟件的工具性軟件，包括輔助和支持開發(fā)和維護(hù)應(yīng)用軟件的工具軟件。二、軟件危機(jī)與軟件工程軟件工程概念的出現(xiàn)源自軟件危機(jī)。所謂有軟件危機(jī)四伏是泛指在計(jì)算機(jī)軟件開發(fā)和維護(hù)過程中所遇到的嚴(yán)重問題。實(shí)際上，幾科所有的軟件都不同程度地存在這些問題。隨著計(jì)算機(jī)技術(shù)的發(fā)展和應(yīng)用領(lǐng)域的擴(kuò)大，計(jì)算機(jī)硬件性能/價(jià)格比和質(zhì)量穩(wěn)步提高，軟件規(guī)模越來越大，復(fù)雜程度不斷增加，軟件成本逐年上升，質(zhì)量沒有可靠的保證

51、，軟件已成為計(jì)算機(jī)科學(xué)發(fā)展的“瓶頸”。具體地說，在軟件開發(fā)和維護(hù)過程中，軟件危機(jī)主要表現(xiàn)在：（1） 軟件需求的增長得不到滿足。用戶對(duì)系統(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)率等問題。軟件工程就是試圖用工程、科學(xué)和數(shù)學(xué)的大批量與方法研制、維護(hù)計(jì)算機(jī)軟件的有關(guān)技術(shù)及管理方法。關(guān)于軟件工程的定義，國標(biāo)（GB）中指出，軟件工程是應(yīng)用

52、于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具文檔、實(shí)踐標(biāo)準(zhǔn)的工序。1993年IEEE(Institute of Electrical &Electronic Engineers ，電氣和電子工程師學(xué)會(huì))給出了一個(gè)更加綜合的定義：“將系統(tǒng)化的、規(guī)范的、可度量的方法應(yīng)用于軟件的開發(fā)、運(yùn)行和維護(hù)的過程，即將工程化應(yīng)用于軟件中”。軟件工程包括3個(gè)要素：即方法、工具和過程。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。軟件工程的核心思想是把軟件產(chǎn)品看作是一個(gè)工程產(chǎn)品來處理。開發(fā)軟件不能只考慮開發(fā)期間的費(fèi)用，而且應(yīng)考慮軟件生命周期內(nèi)的全部費(fèi)用。因此，軟件生命周期的概念就變得特別重要。在考慮軟件費(fèi)用時(shí)，不僅僅要降低開發(fā)成本，更要降低整個(gè)軟件生命周期的總成本。三、軟件工程過程與軟件生命周期1、軟件工程過程（Software Engineering Process）ISO9000定義：軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。定義支持了軟件工程過程的兩方面內(nèi)涵。其一，軟件工程過程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列軟件工程活動(dòng)。基于這個(gè)方面，軟件工程過程通常包含4種基本活動(dòng)：（1） P（plan）軟件規(guī)格說明。規(guī)定軟件的功能及其運(yùn)行時(shí)的限制。（2） D（do）軟件開發(fā)。產(chǎn)生滿足規(guī)