計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)

------------------------------------------------------------------------計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)二級(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í)行的所有指令的集合?；具\(yùn)算和操作包括：算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。算法復(fù)雜度：算法時(shí)間復(fù)雜度和算法空間復(fù)雜度。算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。1.2數(shù)據(jù)結(jié)構(gòu)的基本基本概念數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；（3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。線性結(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)。1．3線性表及其順序存儲(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，它無(wú)前件；（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件；（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱為線性表的長(zhǎng)度，當(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)算：插入、刪除。（詳見(jiàn)14--16頁(yè)）1．4棧和隊(duì)列棧是限定在一端進(jìn)行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照“先進(jìn)后出”（FILO）或“后進(jìn)先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。棧的基本運(yùn)算：（1）插入元素稱為入棧運(yùn)算；（2）刪除元素稱為退棧運(yùn)算；（3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無(wú)變化。隊(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ì)列滿1．5線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元，這種存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。結(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)系是由指針域來(lái)確定的。鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結(jié)點(diǎn)，右指針（Rlink）指向后件結(jié)點(diǎn)。線性鏈表的基本運(yùn)算：查找、插入、刪除。1．6樹(shù)與二叉樹(shù)一、樹(shù)的基本概念在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱為樹(shù)的根。在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。葉子結(jié)點(diǎn)的度為0。樹(shù)的最大層次稱為樹(shù)的深度。在一個(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ù)來(lái)表示算術(shù)表達(dá)式的原則如下：表達(dá)式中的每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)。運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù)（在樹(shù)中的順序?yàn)閺淖蟮接遥?。運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。二、二叉樹(shù)及其基本性質(zhì)1、什么是二叉樹(shù)二叉樹(shù)是一種很有用的非線性結(jié)構(gòu)。二就樹(shù)具有以下兩個(gè)特點(diǎn)：非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。由以上特點(diǎn)可以看出，在二叉樹(shù)中，每一個(gè)結(jié)點(diǎn)的度最大為2，即所有子樹(shù)（左子樹(shù)或右子樹(shù)）也均為二叉樹(shù)，而樹(shù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)的度可以是任意的。另外，二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)的子樹(shù)被明顯地分為左子樹(shù)與右子樹(shù)?？梢詻](méi)有其中的一個(gè)，也可以全沒(méi)有。二叉樹(shù)的基本性質(zhì)性質(zhì)1：在二叉樹(shù)的第K層上，最多有（K≥1）個(gè)結(jié)點(diǎn)。性質(zhì)2：濃度為M的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)。深度為m的二叉樹(shù)是指二叉樹(shù)共有m層。性質(zhì)3：在任意一棵二叉樹(shù)中度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為[log2n]+1,其中[log2n]表示取的整數(shù)部分。滿二叉樹(shù)與完全二叉樹(shù)滿二叉樹(shù)與完全二叉樹(shù)是兩種特殊形態(tài)的二叉樹(shù)。滿二叉樹(shù)所謂滿二叉樹(shù)是指這樣的一種二叉樹(shù)；除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。這就是說(shuō)，在滿二叉樹(shù)中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹(shù)的第K層上有2K-1個(gè)結(jié)點(diǎn)，且深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。完全二叉樹(shù)所謂完全二叉樹(shù)是指這樣的二叉樹(shù)，除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)的最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。列確切地說(shuō)，如果從根結(jié)點(diǎn)起，對(duì)二叉樹(shù)的結(jié)點(diǎn)自上而下、自左至右用自然數(shù)進(jìn)行邊疆編號(hào)，則深度為m、且有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為m的滿二叉樹(shù)中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹(shù)。對(duì)于完全二叉樹(shù)來(lái)說(shuō)，葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；對(duì)于任何一個(gè)結(jié)點(diǎn)，若其右分支下的子孫結(jié)點(diǎn)的最大層次為p，則其左分支下的子孫結(jié)點(diǎn)的最大層次或?yàn)閜，或?yàn)閜+1。由滿二叉樹(shù)與完全二叉樹(shù)的特點(diǎn)可以看出，滿二叉樹(shù)也是完全二叉樹(shù)，而完全二叉樹(shù)一般不是滿二叉樹(shù)。完全二叉樹(shù)還具有以下兩個(gè)性質(zhì)：性質(zhì)5：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1。性質(zhì)6：設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k（k=1,2,…n）的結(jié)點(diǎn)有以下結(jié)論：若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。若2k≤n，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（顯然也沒(méi)有右子結(jié)點(diǎn)）。若2k+1≤n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。三、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。在遍歷二叉樹(shù)的過(guò)程中，一般先遍歷左子樹(shù)，然后再遍歷右子樹(shù)。1、前序遍歷（DLR）所謂前序遍歷是指在訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)與遍歷右子樹(shù)這三者中，首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)；并且，在遍歷左、右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。F，C，A，D，B，E，G，H，P2、中序遍歷（LDR）所謂中序遍歷是指在訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)與遍歷右子樹(shù)這三者中，首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)；并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。A，C，B，D，F(xiàn)，E，H，G，P3、后序遍歷（LRD）所謂中序遍歷是指在訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹(shù)與遍歷右子樹(shù)這三者中，首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)；并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。A，B，D，C，H，P，G，E，F(xiàn)1.7查找技術(shù)一、順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個(gè)元素開(kāi)始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒(méi)有要找的元素（即查找失?。?。順序查找的效率是很低的。以下兩種情況只能采用順序查找：如果線性表無(wú)序表（即表中元素的排列是無(wú)序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。二、二分法查找二分法查找只適用于存儲(chǔ)的有序表。在此所說(shuō)的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。設(shè)有序線性表的長(zhǎng)度為n，被查元素為x，則對(duì)分查找的方法如下：將x與線性表的中間項(xiàng)進(jìn)行比較：若中間項(xiàng)的值等于x，則說(shuō)明查到，查找結(jié)束；若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0（說(shuō)明線性表中沒(méi)有這個(gè)元素）為止。顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，并且，二分查找的效率要比順序查找高得多?？梢宰C明，對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。1.8排序技術(shù)一、交換類排隊(duì)序法所謂交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。1、冒泡排序法基本過(guò)程如下：首先，從表頭開(kāi)始往后掃描線性表，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個(gè)逆序。放最大值然后，從后到前掃描剩下的線性表，同樣，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，后面的元素大于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。放最小值。重復(fù)上述過(guò)程，直到剩下的線性有變空為止，此時(shí)的線性表已經(jīng)變?yōu)橛行?。假設(shè)線性表的長(zhǎng)為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n/2遍的蔥馨往后的掃描和n/2遍的從后往前的掃描，需要的比較的次數(shù)為n(n-1)/2。2、快速排序法快速排序法也是種互換類的排序法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法?；舅枷肴缦拢簭木€性表中選取一個(gè)元素，設(shè)T，將線性表后面小于T的元素移到前，而前大于T的元素移支后面，結(jié)果就將線性表分成了兩部分（稱為兩個(gè)子表），T插入到其分界線的位置處，這個(gè)過(guò)程稱為線性表的分割。通過(guò)對(duì)線性表的一次分割，就以T為分界線，將線性表分成了前后兩個(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(j)移到P(i)位置上。（5）將i逐漸減小，并逐次比較P（i）與T，直到發(fā)現(xiàn)一個(gè)P(i)>T為止，將P(i)移到P(j)位置上。上述兩個(gè)操作交替進(jìn)行，直到指針i與j指向同一個(gè)位置（即i=j）為止，此時(shí)將P(i)的位置上。分割需要記憶，用棧來(lái)實(shí)現(xiàn)。二、插入類排序法1、簡(jiǎn)單插入排序法所謂插入排序，是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中。一般來(lái)說(shuō)，假設(shè)線性中前j-1元素已經(jīng)有序，現(xiàn)在要將線性表中第j個(gè)元素插入到前面的有序子表中，插入過(guò)程如下：道德將第j個(gè)元素放到一個(gè)變量T中，然后從有序子表的最后一個(gè)元素（即線性表中第j-1個(gè)元素）開(kāi)始，往前逐個(gè)與T進(jìn)行比較，將大于T的元素均依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)一個(gè)元素不大于T為止，此時(shí)就將T（即原線性表中的第j個(gè)元素）插入到剛移出的空位置上，有序子表的長(zhǎng)度就變?yōu)閖了。效率與冒泡法相同在最壞情況下，簡(jiǎn)單插入排序需要n(n-1)/2次比較。2、希爾排序法基本思想如下：將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。子序列的分割方法如下：將相隔某個(gè)增量H的元素構(gòu)成一個(gè)子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最后當(dāng)H減到1時(shí)，進(jìn)行一次插入排序，排序就完成。增量序列一般取h=n/2k(k=1,2,…[log2n],其中n為待排序序列的長(zhǎng)度。其效率與增量序列有關(guān)。在最壞情況下，需要的比較次數(shù)為O（Ｎ１.５）。三、選擇類排序法１、簡(jiǎn)單選擇排序法基本思想：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面；然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。簡(jiǎn)單選擇排序法在最壞情況下需要比較n(n-1)/2/次。２、堆排序法方法：（1）首先將一個(gè)無(wú)序序列建成堆。（2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。不考慮已經(jīng)換到最后的那個(gè)元素，只考慮前n-1個(gè)元素構(gòu)成的子序，顯然，該子序列已不是堆，但左、右子樹(shù)仍為堆，可以將該子序列調(diào)事為堆。反復(fù)做第（2）步，真到剩下的子序列為空為止。適用規(guī)模較大的線性表，在最壞情況下，堆排序需要比較的次數(shù)為O（nlog2n）。1.7查找技術(shù)一、順序查找順序查找又稱順序搜索。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個(gè)元素開(kāi)始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒(méi)有要找的元素（即查找失?。ｍ樞虿檎业男适呛艿偷摹Ｒ韵聝煞N情況只能采用順序查找：如果線性表無(wú)序表（即表中元素的排列是無(wú)序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。二、二分法查找二分法查找只適用于存儲(chǔ)的有序表。在此所說(shuō)的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。設(shè)有序線性表的長(zhǎng)度為n，被查元素為x，則對(duì)分查找的方法如下：將x與線性表的中間項(xiàng)進(jìn)行比較：若中間項(xiàng)的值等于x，則說(shuō)明查到，查找結(jié)束；若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0（說(shuō)明線性表中沒(méi)有這個(gè)元素）為止。顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，并且，二分查找的效率要比順序查找高得多。可以證明，對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。1.8排序技術(shù)一、交換類排隊(duì)序法所謂交換類排序法是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。冒泡排序法與快速排序法都屬于交換類的排序方法。1、冒泡排序法基本過(guò)程如下：首先，從表頭開(kāi)始往后掃描線性表，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個(gè)逆序。放最大值然后，從后到前掃描剩下的線性表，同樣，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，后面的元素大于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。放最小值。重復(fù)上述過(guò)程，直到剩下的線性有變空為止，此時(shí)的線性表已經(jīng)變?yōu)橛行颉＜僭O(shè)線性表的長(zhǎng)為n，則在最壞情況下，冒泡排序需要經(jīng)過(guò)n/2遍的蔥馨往后的掃描和n/2遍的從后往前的掃描，需要的比較的次數(shù)為n(n-1)/2。2、快速排序法快速排序法也是種互換類的排序法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法。基本思想如下：從線性表中選取一個(gè)元素，設(shè)T，將線性表后面小于T的元素移到前，而前大于T的元素移支后面，結(jié)果就將線性表分成了兩部分（稱為兩個(gè)子表），T插入到其分界線的位置處，這個(gè)過(guò)程稱為線性表的分割。通過(guò)對(duì)線性表的一次分割，就以T為分界線，將線性表分成了前后兩個(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(j)移到P(i)位置上。（5）將i逐漸減小，并逐次比較P（i）與T，直到發(fā)現(xiàn)一個(gè)P(i)>T為止，將P(i)移到P(j)位置上。上述兩個(gè)操作交替進(jìn)行，直到指針i與j指向同一個(gè)位置（即i=j）為止，此時(shí)將P(i)的位置上。分割需要記憶，用棧來(lái)實(shí)現(xiàn)。二、插入類排序法1、簡(jiǎn)單插入排序法所謂插入排序，是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中。一般來(lái)說(shuō)，假設(shè)線性中前j-1元素已經(jīng)有序，現(xiàn)在要將線性表中第j個(gè)元素插入到前面的有序子表中，插入過(guò)程如下：道德將第j個(gè)元素放到一個(gè)變量T中，然后從有序子表的最后一個(gè)元素（即線性表中第j-1個(gè)元素）開(kāi)始，往前逐個(gè)與T進(jìn)行比較，將大于T的元素均依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)一個(gè)元素不大于T為止，此時(shí)就將T（即原線性表中的第j個(gè)元素）插入到剛移出的空位置上，有序子表的長(zhǎng)度就變?yōu)閖了。效率與冒泡法相同在最壞情況下，簡(jiǎn)單插入排序需要n(n-1)/2次比較。2、希爾排序法基本思想如下：將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。子序列的分割方法如下：將相隔某個(gè)增量H的元素構(gòu)成一個(gè)子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最后當(dāng)H減到1時(shí)，進(jìn)行一次插入排序，排序就完成。增量序列一般取h=n/2k(k=1,2,…[log2n],其中n為待排序序列的長(zhǎng)度。其效率與增量序列有關(guān)。在最壞情況下，需要的比較次數(shù)為O（Ｎ１.５）。三、選擇類排序法１、簡(jiǎn)單選擇排序法基本思想：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面；然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。簡(jiǎn)單選擇排序法在最壞情況下需要比較n(n-1)/2/次。２、堆排序法方法：（1）首先將一個(gè)無(wú)序序列建成堆。（2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。不考慮已經(jīng)換到最后的那個(gè)元素，只考慮前n-1個(gè)元素構(gòu)成的子序，顯然，該子序列已不是堆，但左、右子樹(shù)仍為堆，可以將該子序列調(diào)事為堆。反復(fù)做第（2）步，真到剩下的子序列為空為止。適用規(guī)模較大的線性表，在最壞情況下，堆排序需要比較的次數(shù)為O（nlog2n）。習(xí)題一一、選擇題1、算法的時(shí)間復(fù)雜度是指（）A）執(zhí)行算法程序所需要的時(shí)間B）算法程序的長(zhǎng)度C）算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)D）算法程序中的指令條數(shù)2、算法的窨復(fù)雜度是指（）A、算法程序的長(zhǎng)度B、算法程序中的指令條數(shù)C、算法程序所占的存儲(chǔ)空間D、算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間3、下列敘述中正確的是（）A、線性表是線性結(jié)構(gòu)B、材與隊(duì)列是非線性結(jié)構(gòu)C、線性鏈表是非線性結(jié)構(gòu)D、二叉樹(shù)是線性結(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è)有下列二叉樹(shù)：對(duì)此二叉樹(shù)中序遍歷的結(jié)果為A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA8、在深度為5的滿二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為（）A、32B、31C、16D、159、對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為（）A、n+1B、nC、(n+1)/2D、n/210、設(shè)樹(shù)T的度為4，其中度為1，2，3，4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1。則T中的葉子結(jié)點(diǎn)數(shù)為（）A、8B、7C、6D、5二、填空題1、在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，需要的比較次數(shù)為。2、設(shè)一棵完全二叉共有700個(gè)結(jié)點(diǎn)，則在該二叉樹(shù)中有個(gè)葉子結(jié)點(diǎn)。3、設(shè)一棵二叉樹(shù)中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為。4、在最壞情況下，冒泡排序的時(shí)間復(fù)雜度為。5、在一個(gè)容量為15的循環(huán)隊(duì)列中，若頭指針front=6，尾指針rear=9，則該循環(huán)隊(duì)列中共有個(gè)元第2章程序設(shè)計(jì)基礎(chǔ)2．1程序設(shè)計(jì)方法與風(fēng)格就程序設(shè)計(jì)方法和技術(shù)的發(fā)展而言，主要經(jīng)過(guò)了結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)階段。一般來(lái)講。程序設(shè)計(jì)風(fēng)格是指編寫程序時(shí)所表現(xiàn)出的特點(diǎn)、習(xí)慣和邏輯思路。程序是由人來(lái)編寫的，為了測(cè)試和維護(hù)程序，往往還要新聞?dòng)浾吆透櫝绦颍虼顺绦蛟O(shè)計(jì)的風(fēng)格總體而言應(yīng)該強(qiáng)調(diào)得意和清晰，程序必須是可以理解的。要形成良好的程序設(shè)計(jì)風(fēng)格，主要應(yīng)注重和考慮下述一些因素。1、源程序文檔化2、源程序文檔化應(yīng)考慮如下幾點(diǎn)：（1）符號(hào)名的命名：符號(hào)名的命名應(yīng)具有一定的實(shí)際含義，以便于對(duì)程序功能的理解。（2）程序注釋：下克的注釋能夠幫助讀者理解程序。（3）禮堂組織：為使程序的結(jié)構(gòu)一目了然，可以在程序中利用空格、空行、縮進(jìn)待技巧使程序?qū)哟吻逦?、數(shù)據(jù)說(shuō)明的方法在編寫程序時(shí)，需要注意數(shù)據(jù)說(shuō)明的風(fēng)格，以便使程序中的數(shù)據(jù)說(shuō)明更易于理解和維護(hù)。一般應(yīng)注意如下幾點(diǎn)：（1）數(shù)據(jù)說(shuō)明的次序規(guī)范化鑒于程序理解、新聞?dòng)浾吆途S護(hù)的需要，使數(shù)據(jù)說(shuō)明次序固定，可以使數(shù)據(jù)的發(fā)生容易查找，也有利于測(cè)試、排錯(cuò)和維護(hù)。（2）說(shuō)明語(yǔ)句中變量安排有序化。當(dāng)一個(gè)說(shuō)明語(yǔ)句說(shuō)明多個(gè)變量時(shí)，變量按照字母順序?yàn)楹谩＃?）使用注釋來(lái)說(shuō)明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。3、語(yǔ)句的結(jié)構(gòu)程序應(yīng)該簡(jiǎn)單易懂，語(yǔ)句構(gòu)造應(yīng)該簡(jiǎn)單直接，不應(yīng)該為提高效率而把語(yǔ)句復(fù)雜化。一般應(yīng)注意如下：（1）在一行內(nèi)只寫一條語(yǔ)句；（2）程序編寫應(yīng)優(yōu)先考慮清晰性；（3）除非對(duì)效率有特殊要求，程序編寫要做清晰第一，效率第二；（4）首先要保證程序正確，然后才要求提高速度；（5）避免使用臨時(shí)變量而使程序的可讀性下降；（6）避免不必要的轉(zhuǎn)移；（7）盡可能使用庫(kù)函數(shù)；（8）避免采用復(fù)雜的條件語(yǔ)句；（9）盡量減少使用“否定”條件的條件語(yǔ)句；（10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化；（11）要模塊化，使模塊功能盡可能單一化；（12）利用住處隱蔽，確保每一個(gè)模塊的獨(dú)立性；（13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；（14）不要修補(bǔ)不好的程序，要重新編寫；4、輸入和輸出無(wú)論是批處理的輸入和輸出方式，還是交互式的輸入和輸出方式，在設(shè)計(jì)和編程時(shí)都應(yīng)該考慮如下原則：（1）對(duì)所有的輸入數(shù)據(jù)都要檢驗(yàn)數(shù)據(jù)的合法性；（2）檢查輸入項(xiàng)的各種重要組合的合理性；（3）輸入格式要簡(jiǎn)單，以使得輸入的步驟和操作盡可能簡(jiǎn)單；（4）輸入數(shù)據(jù)時(shí)，應(yīng)允許使用自由格式；（5）應(yīng)允許缺省值；（6）輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志；（7）在以交互式輸入/輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確提示輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入過(guò)程中的輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息。（8）當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性；給所有的輸入出加注釋，并設(shè)計(jì)輸出報(bào)表格式。2．2結(jié)構(gòu)化程序設(shè)計(jì)一、結(jié)構(gòu)化程序設(shè)計(jì)的原則結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為自頂向下，逐步求精，模塊化，限制使用goto語(yǔ)句。1、自頂向下：程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。不要一開(kāi)始就過(guò)多追求眾多的細(xì)節(jié)，先從最上層總目標(biāo)開(kāi)始設(shè)計(jì)，逐步使問(wèn)題具體化。2、逐步求精：對(duì)復(fù)雜問(wèn)題，應(yīng)設(shè)計(jì)一些子目標(biāo)作過(guò)渡，逐步細(xì)化。3、模塊化：一個(gè)復(fù)雜問(wèn)題，肯定是由若干稍簡(jiǎn)單的問(wèn)題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。4、限制使用goto語(yǔ)句使用goto語(yǔ)句經(jīng)實(shí)驗(yàn)證實(shí)：（1）濫用GOTO語(yǔ)句確實(shí)有害，應(yīng)晝避免；（2）完全避免使用GOTO語(yǔ)句也并非是個(gè)明智的方法，有些地方使用GOTO語(yǔ)句，會(huì)使程序流程更清楚、效率更高；（3）爭(zhēng)論的焦點(diǎn)不應(yīng)該放在是否取消GOTO語(yǔ)句，而應(yīng)該放在用什么樣的程序結(jié)構(gòu)上。其中最關(guān)鍵的是，肯定以提高程序清晰性為目標(biāo)的結(jié)構(gòu)化方法。二、結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn)1、順序結(jié)構(gòu)：順序結(jié)構(gòu)是簡(jiǎn)單的程序設(shè)計(jì)，它是最基本、最常用的結(jié)構(gòu)，所謂順序執(zhí)行，就是按照程序語(yǔ)句行的自然順序，一條語(yǔ)句一條語(yǔ)句地執(zhí)行程序程序。2、選擇結(jié)構(gòu)：選擇結(jié)構(gòu)又稱為分支結(jié)構(gòu)，它包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)，這種結(jié)構(gòu)可以根據(jù)設(shè)定的條件，判斷應(yīng)該選擇哪一條分支來(lái)執(zhí)行相應(yīng)的語(yǔ)句序列。3、重復(fù)結(jié)構(gòu)：重復(fù)結(jié)構(gòu)又稱為循環(huán)結(jié)構(gòu)，它根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類似的程序段，利用重復(fù)結(jié)構(gòu)可簡(jiǎn)化大量的程序行。分為兩類：一是先判斷后執(zhí)行，一是先執(zhí)行后判斷。優(yōu)點(diǎn)：一是程序易于理解、使用和維護(hù)。二是編程工作的效率，降低軟件開(kāi)發(fā)成本。三、結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用要注意把握如下要素：1、使用程序設(shè)計(jì)語(yǔ)言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。2、選用的控制結(jié)構(gòu)只準(zhǔn)許有一個(gè)入口和一個(gè)出口；3、程序語(yǔ)句組成容易識(shí)別的塊，每塊只有一個(gè)入口和一個(gè)出口；4、復(fù)雜結(jié)構(gòu)應(yīng)該嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來(lái)實(shí)現(xiàn)；5、語(yǔ)言中所沒(méi)有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來(lái)模擬；6、嚴(yán)格控制GOTO語(yǔ)句的使用。其意思是指：（1）用一個(gè)非結(jié)構(gòu)化的程序設(shè)計(jì)語(yǔ)言去實(shí)現(xiàn)一個(gè)結(jié)構(gòu)化的構(gòu)造；（2）若不使用GOTO語(yǔ)句會(huì)使功能模糊；（3）在某種可以改善而不損害程序可讀性的情況下。2．3面向?qū)ο蟮某绦蛟O(shè)計(jì)一、關(guān)于面向?qū)ο蠓椒嫦驅(qū)ο蠓椒ǖ谋举|(zhì)，就是主張從客觀世界固有的事物出發(fā)來(lái)構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實(shí)生活中常用的思維方法來(lái)認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問(wèn)題域，也就是說(shuō)，系統(tǒng)中的對(duì)象以及對(duì)象之間的關(guān)系能夠如實(shí)地反映問(wèn)題域中固有事物及其關(guān)系。優(yōu)點(diǎn)：1、與人類習(xí)慣的思維方法一致面向?qū)ο蠓椒ê图夹g(shù)以對(duì)象為核心。對(duì)象是由數(shù)據(jù)和容許的操作組成的封裝體，與客觀實(shí)體有直接的關(guān)系。對(duì)象之間通過(guò)傳遞消息互相聯(lián)系，以模擬現(xiàn)實(shí)世界中不同事物彼此之間的聯(lián)系。面向?qū)ο蟮脑O(shè)計(jì)方法與傳統(tǒng)的面向過(guò)程的方法有本質(zhì)不同，這種方法的基本原理是：使用現(xiàn)實(shí)世界的概念抽象地思考問(wèn)題從而自然地解決問(wèn)題。它強(qiáng)調(diào)模擬現(xiàn)實(shí)世界中的概念而不強(qiáng)調(diào)算法，它鼓勵(lì)開(kāi)發(fā)者在軟件開(kāi)發(fā)的絕大部分過(guò)程中都用應(yīng)用領(lǐng)域的要領(lǐng)去思考。2、穩(wěn)定性好3、可重用性好軟件重用是指在不同的軟件開(kāi)發(fā)過(guò)程中重復(fù)作用相同或相似軟件元素的過(guò)程。重用是提高軟件生產(chǎn)率的最主要的方法。4、易于開(kāi)發(fā)大型軟件產(chǎn)品5、可維護(hù)性好（1）用面向?qū)ο蟮姆椒ㄩ_(kāi)發(fā)的軟件穩(wěn)定性比較好（2）用面向?qū)ο蟮姆椒ㄩ_(kāi)發(fā)的軟件比較容易修改；（3）用面向?qū)ο蟮姆椒ㄩ_(kāi)發(fā)的軟件比較容易理解。（4）易于測(cè)試和調(diào)試。二、面向?qū)ο蠓椒ǖ幕靖拍?、對(duì)象（object）對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。?duì)象可以用來(lái)表示客觀世界中的任何實(shí)體，也就是說(shuō)，應(yīng)用領(lǐng)域中有意義的、與所要解決的問(wèn)題有關(guān)系的任何事物都可以作為對(duì)象，它既可以是具體的物理實(shí)體的抽象，也可以是人為的概念，或者是任何有明確邊界的意義的東西。總之，對(duì)象是對(duì)問(wèn)題域中某個(gè)實(shí)體的抽象，設(shè)立某個(gè)對(duì)象就反映軟件系統(tǒng)保存有關(guān)它的信息并具有與它進(jìn)行交互的能力。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中涉及的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，它由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。對(duì)象可以做的操作表示它的動(dòng)態(tài)行為，在面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O(shè)計(jì)中，通常把對(duì)象的操作也稱為方法或服務(wù)。屬性即對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過(guò)掛靠對(duì)象的操作來(lái)改變。操作描述了對(duì)象執(zhí)行的功能，若通過(guò)消息傳遞，還可以為其他對(duì)象使用。操作的過(guò)程對(duì)外是封閉的，即用戶只能看到這一操作實(shí)施后的結(jié)果。這相當(dāng)于事先已經(jīng)設(shè)計(jì)好的各種過(guò)程，只需要調(diào)用就可以了，用戶不必去關(guān)心這一過(guò)程是如何編寫的。事實(shí)上，這個(gè)過(guò)程已經(jīng)封裝在對(duì)象中，用戶也看不到。對(duì)的這一特性即是對(duì)象的封裝性。對(duì)象有如下一些基本特點(diǎn)：（1）標(biāo)識(shí)惟一性。指對(duì)象是可區(qū)分的，并且由對(duì)象有的內(nèi)在本質(zhì)來(lái)區(qū)分，而不是通過(guò)描述來(lái)區(qū)分。（2）分類性。指可以將具有相同屬性的操作的對(duì)象抽象成類。（3）多太性。指同一個(gè)操作可以是不同對(duì)象的行為。（4）封裝性。從外面看只能看到對(duì)象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施加的操作，根本無(wú)需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。對(duì)象的內(nèi)部，即處理能力的實(shí)行和內(nèi)部狀態(tài)，對(duì)外是不可見(jiàn)的。從外面不能直接使用對(duì)象的處理能力，也不能直接修改其內(nèi)部狀態(tài)，對(duì)象的內(nèi)部狀態(tài)只能由其自身改變。（5）模塊獨(dú)立性好。對(duì)象是面向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對(duì)這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對(duì)象是以數(shù)據(jù)為中心的，操作圍繞對(duì)其數(shù)據(jù)所需做的處理來(lái)設(shè)置，沒(méi)有無(wú)關(guān)的操作從模塊的獨(dú)立性考慮，對(duì)象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強(qiáng)。2、類（Class）和實(shí)例(Instance)將屬性、操作相似的對(duì)象歸為類，也就是說(shuō)，類是具有共同屬性、共同方法的對(duì)象的集合。所以，類是對(duì)象的抽象，它描述了屬于該對(duì)象類型的所有對(duì)象的性質(zhì)，而一個(gè)對(duì)象則是其對(duì)應(yīng)類的一個(gè)實(shí)例。要注意的是，當(dāng)使用“對(duì)象”這個(gè)術(shù)語(yǔ)時(shí)，既可以指一個(gè)具體的對(duì)象，也可以泛指一般的對(duì)象，但是，當(dāng)使用“實(shí)例”這個(gè)術(shù)語(yǔ)時(shí)，必然是指一個(gè)具體的對(duì)象。例如：Integer是一個(gè)整數(shù)類，它描述了所有整數(shù)的性質(zhì)。因此任何整數(shù)都是整數(shù)類的對(duì)象，而一個(gè)具體的整數(shù)“123”是類Integer的實(shí)例。由類的定義可知，類是關(guān)于對(duì)象性質(zhì)的描述，它同對(duì)象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。3、消息（Message）面向?qū)ο蟮氖澜缡峭ㄟ^(guò)對(duì)象與對(duì)象間彼此的相互合作來(lái)推動(dòng)的，對(duì)象間的這種相互合作需要一個(gè)機(jī)制協(xié)助進(jìn)行，這樣的機(jī)制稱為“消息”。消息是一個(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é)合起來(lái)。消息傳遞過(guò)程中，由發(fā)送消息的對(duì)象（發(fā)送對(duì)象）的觸發(fā)操作產(chǎn)生輸出結(jié)果，作為消息傳送至接受消息的對(duì)象（接受對(duì)象），引發(fā)接受消息的對(duì)象一系列的操作。所傳送的消息實(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公里”的消息。通常，一個(gè)消息由下述三部分組成：（1）接收消息的對(duì)象的名稱；（2）消息標(biāo)識(shí)符（也稱為消息名）；（3）零個(gè)或多個(gè)參數(shù)。4、繼承（Inheritance）繼承是面向?qū)ο蟮姆椒ǖ囊粋€(gè)主要特征。繼承是使用己有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。已有的類可當(dāng)作基類來(lái)引用，則新類相應(yīng)地可當(dāng)作派生類來(lái)引用。廣義地說(shuō)，繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。面向?qū)ο筌浖夹g(shù)的許多強(qiáng)有力的功能和突出的優(yōu)點(diǎn)，都來(lái)源于把類組成一個(gè)層次結(jié)構(gòu)的系統(tǒng)：一個(gè)類的上層可以有父類，下層可以有子類。這種層次結(jié)構(gòu)系統(tǒng)的一個(gè)重要性質(zhì)是繼承性，一個(gè)類直接繼承其父類的描述（數(shù)據(jù)和操作）或特性，子類自動(dòng)地共享基類中定義的數(shù)據(jù)和方法。繼承具有傳遞性，如果類C繼承類B，類B繼承類A，則類C繼承類A。因此一個(gè)類實(shí)際上繼承了它上層的全部基類的特性，也就是說(shuō)，屬于某類的對(duì)象除了具有該類所定義的特性外，還具有該類上層全部基類定義的特性。繼承分為單繼承與多重繼承。單繼承是指，一個(gè)類只允許有一個(gè)父類，即類等級(jí)為樹(shù)形結(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ù)。此外，繼承性便利用戶在開(kāi)發(fā)新的應(yīng)用系統(tǒng)時(shí)不必完全從零開(kāi)始，可以繼承原有的相似系統(tǒng)的功能或者從類庫(kù)中選取需要的類，再派生出新的類以實(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)的新的子類，完全無(wú)需修改原有的程序代碼，甚至不需要重新編譯原有的程序。利用多態(tài)性，用戶能夠發(fā)送一般形式的消息，而將所有的實(shí)現(xiàn)細(xì)節(jié)都留給接受消息的對(duì)象。第3章軟件工程基礎(chǔ)3．1軟件工程基本概念一、軟件定義與軟件特點(diǎn)計(jì)算機(jī)軟件是計(jì)算機(jī)系統(tǒng)中與硬件相互依存的另一部分，是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合?；校绦蚴擒浖_(kāi)發(fā)人員根據(jù)用戶需求開(kāi)發(fā)的用程序設(shè)計(jì)語(yǔ)言描述的、適合計(jì)算機(jī)執(zhí)行的指令（語(yǔ)句）序列。數(shù)據(jù)是使程序能正常操縱信息的數(shù)據(jù)結(jié)構(gòu)。文檔是與程序開(kāi)發(fā)、維護(hù)和使用有關(guān)的圖文資料?？梢?jiàn)軟件由兩部分組成：一是機(jī)器可執(zhí)行的程序和數(shù)據(jù)；二是機(jī)器不可執(zhí)行的，與軟件開(kāi)發(fā)、運(yùn)行、維護(hù)、使用等有關(guān)的文檔。國(guó)標(biāo)（GB）中對(duì)計(jì)算機(jī)軟件的定義為：與計(jì)算機(jī)系統(tǒng)的操作有關(guān)的計(jì)算機(jī)程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數(shù)據(jù)。軟件在開(kāi)發(fā)、生產(chǎn)、維護(hù)和使用等方面與計(jì)算機(jī)硬件相比存在明顯的差異。深入理解軟件的定義需要了解軟件的特點(diǎn)：（1）軟件是一種邏輯實(shí)體，而不是物理實(shí)體具有抽象性。（2）軟件的生產(chǎn)與硬件不同，它沒(méi)有明顯的制作過(guò)程。一旦研制開(kāi)發(fā)成功，可以大量拷貝同一內(nèi)容的副本。所以對(duì)軟件的控制，必須著重在軟件開(kāi)發(fā)方面下功夫。（3）軟件在運(yùn)行、使用期間不存在磨損、老化問(wèn)題。（4）軟件的開(kāi)發(fā)運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制這導(dǎo)致了軟件移植的問(wèn)題。（5）軟件復(fù)雜性高，成本昂貴。（6）軟件開(kāi)發(fā)涉及諸多的社會(huì)因素。軟件按功能可以分為：應(yīng)用軟件、系統(tǒng)軟件、支撐軟件（或工具軟件）。應(yīng)用軟件是為解決特定領(lǐng)域的應(yīng)用而開(kāi)發(fā)的軟件。系統(tǒng)軟件是計(jì)算機(jī)管理自身資源，提高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶提供各種服務(wù)的軟件。支撐軟件是介于系統(tǒng)軟件和應(yīng)用軟件之間，協(xié)助用戶開(kāi)發(fā)軟件的工具性軟件，包括輔助和支持開(kāi)發(fā)和維護(hù)應(yīng)用軟件的工具軟件。二、軟件危機(jī)與軟件工程軟件工程概念的出現(xiàn)源自軟件危機(jī)。所謂有軟件危機(jī)四伏是泛指在計(jì)算機(jī)軟件開(kāi)發(fā)和維護(hù)過(guò)程中所遇到的嚴(yán)重問(wèn)題。實(shí)際上，幾科所有的軟件都不同程度地存在這些問(wèn)題。隨著計(jì)算機(jī)技術(shù)的發(fā)展和應(yīng)用領(lǐng)域的擴(kuò)大，計(jì)算機(jī)硬件性能/價(jià)格比和質(zhì)量穩(wěn)步提高，軟件規(guī)模越來(lái)越大，復(fù)雜程度不斷增加，軟件成本逐年上升，質(zhì)量沒(méi)有可靠的保證，軟件已成為計(jì)算機(jī)科學(xué)發(fā)展的“瓶頸”。具體地說(shuō)，在軟件開(kāi)發(fā)和維護(hù)過(guò)程中，軟件危機(jī)主要表現(xiàn)在：（1）軟件需求的增長(zhǎng)得不到滿足。用戶對(duì)系統(tǒng)不滿意的情況經(jīng)常發(fā)生。（2）軟件開(kāi)發(fā)成本和進(jìn)度無(wú)法控制。開(kāi)發(fā)成本超出預(yù)算，開(kāi)發(fā)周期大大超過(guò)規(guī)定日期的情況經(jīng)常發(fā)生。（3）軟件質(zhì)量難以保證。（4）軟件不可維護(hù)或護(hù)程度非常低。（5）軟件的成本不斷提高。（6）軟件開(kāi)發(fā)生產(chǎn)率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長(zhǎng)?？傊?，可以將軟件危機(jī)歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問(wèn)題。軟件工程就是試圖用工程、科學(xué)和數(shù)學(xué)的大批量與方法研制、維護(hù)計(jì)算機(jī)軟件的有關(guān)技術(shù)及管理方法。關(guān)于軟件工程的定義，國(guó)標(biāo)（GB）中指出，軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開(kāi)發(fā)和維護(hù)的一整套方法、工具文檔、實(shí)踐標(biāo)準(zhǔn)的工序。1993年IEEE(InstituteofElectrical&ElectronicEngineers，電氣和電子工程師學(xué)會(huì))給出了一個(gè)更加綜合的定義：“將系統(tǒng)化的、規(guī)范的、可度量的方法應(yīng)用于軟件的開(kāi)發(fā)、運(yùn)行和維護(hù)的過(guò)程，即將工程化應(yīng)用于軟件中”。軟件工程包括3個(gè)要素：即方法、工具和過(guò)程。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具支持軟件的開(kāi)發(fā)、管理、文檔生成；過(guò)程支持軟件開(kāi)發(fā)的各個(gè)環(huán)節(jié)的控制、管理。軟件工程的核心思想是把軟件產(chǎn)品看作是一個(gè)工程產(chǎn)品來(lái)處理。開(kāi)發(fā)軟件不能只考慮開(kāi)發(fā)期間的費(fèi)用，而且應(yīng)考慮軟件生命周期內(nèi)的全部費(fèi)用。因此，軟件生命周期的概念就變得特別重要。在考慮軟件費(fèi)用時(shí)，不僅僅要降低開(kāi)發(fā)成本，更要降低整個(gè)軟件生命周期的總成本。三、軟件工程過(guò)程與軟件生命周期1、軟件工程過(guò)程（SoftwareEngineeringProcess）ISO9000定義：軟件工程過(guò)程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。定義支持了軟件工程過(guò)程的兩方面內(nèi)涵。其一，軟件工程過(guò)程是指為獲得軟件產(chǎn)品，在軟件工具支持下由軟件工程師完成的一系列軟件工程活動(dòng)?；谶@個(gè)方面，軟件工程過(guò)程通常包含4種基本活動(dòng)：（1）P（plan）——軟件規(guī)格說(shuō)明。規(guī)定軟件的功能及其運(yùn)行時(shí)的限制。（2）D（do）——軟件開(kāi)發(fā)。產(chǎn)生滿足規(guī)格說(shuō)明的軟件。（3）C（check）——軟件確認(rèn)。確認(rèn)軟件能夠滿足客戶提出的要求。（4）A(action)——軟件演進(jìn)。為滿足客戶的變更要求，軟件必須在使用的過(guò)程中演進(jìn)。通常把用戶的要求轉(zhuǎn)變成軟件產(chǎn)品的過(guò)程也叫做軟件開(kāi)發(fā)過(guò)程。此過(guò)程包括對(duì)用戶的要求進(jìn)行分析，解釋成軟件需求，把需求變換成設(shè)計(jì)，把設(shè)計(jì)用代碼來(lái)實(shí)現(xiàn)并進(jìn)行代碼測(cè)試，有些軟件還需要進(jìn)行代碼安裝和交付運(yùn)行。其二，從軟件開(kāi)發(fā)的觀點(diǎn)看，它就是使用適當(dāng)?shù)馁Y源（包括人員、硬軟件工具、時(shí)間等），為開(kāi)發(fā)軟件進(jìn)行的一組開(kāi)發(fā)活動(dòng)，在過(guò)程結(jié)束時(shí)將輸入（用戶要求）轉(zhuǎn)化為輸出（軟件產(chǎn)品）。所以，軟件工程的過(guò)程是將軟件工程的方法和工具綜合起來(lái)，以達(dá)到合理、及時(shí)地進(jìn)行計(jì)算機(jī)軟件開(kāi)發(fā)的目的。軟件工程過(guò)程應(yīng)確定方法使用的順序、要求交付的文檔資料、為保證質(zhì)量和適應(yīng)變化所需要的管理、軟件開(kāi)發(fā)各個(gè)階段完成的任務(wù)。2、軟件生命周期（softwarelifecycle）通常，將軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過(guò)程稱為軟件生命周期。一般包括可行性研究與需求分析、設(shè)計(jì)、實(shí)現(xiàn)、測(cè)試、交付使用以及維護(hù)等活動(dòng)。還可以將軟件生命周期分為軟件定義、軟件開(kāi)發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段。軟件生命周期的主要活動(dòng)階段是：（1）可行性研究與計(jì)劃制定。確定待開(kāi)發(fā)軟件系統(tǒng)的開(kāi)發(fā)目標(biāo)和總的要求，給出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成開(kāi)發(fā)任務(wù)的實(shí)施計(jì)劃。（2）需求分析。對(duì)待開(kāi)發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)定義。編寫軟件規(guī)格說(shuō)明書及初步的用戶手冊(cè)，提交評(píng)審。（3）軟件設(shè)計(jì)。系統(tǒng)設(shè)計(jì)人員和程序設(shè)計(jì)人員應(yīng)該在反復(fù)理解軟件需求的基礎(chǔ)上，給出軟件的結(jié)構(gòu)、模塊和劃分、功能的分配及處理流程。在系統(tǒng)比軟件復(fù)雜的情況下，設(shè)計(jì)階段可分解成概要設(shè)計(jì)階段和詳細(xì)設(shè)計(jì)階段。編寫概要設(shè)計(jì)說(shuō)明書、詳細(xì)設(shè)計(jì)說(shuō)明書和測(cè)試計(jì)劃初稿，提交評(píng)審。（4）軟件實(shí)現(xiàn)。把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。即完成源程序的編碼，編寫用戶手冊(cè)、操作手冊(cè)等面向用戶的文檔，編寫單元測(cè)試計(jì)劃。（5）軟件測(cè)試。在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上，檢驗(yàn)軟件的各個(gè)組成部分。編寫測(cè)試分析報(bào)告。（6）運(yùn)行和維護(hù)。將已交付的軟件投入運(yùn)行，并在運(yùn)行使用中不斷地維護(hù)，根據(jù)新進(jìn)出的需求進(jìn)行必要而且可能的擴(kuò)充和刪改。四、軟件工程的目標(biāo)與原則1、軟件工程的目標(biāo)軟件工程的目標(biāo)是，在給定成本、進(jìn)度的前提下，開(kāi)發(fā)出具有有效性、可靠性、可理解性、可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：付出較低的開(kāi)發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件性能；開(kāi)發(fā)的軟件易于移植；需要較低的維護(hù)費(fèi)用；能按時(shí)完成開(kāi)發(fā)，及時(shí)交付使用?；谲浖こ痰哪繕?biāo)，軟件工程的理論和技術(shù)性研究的內(nèi)容主要包括：軟件開(kāi)發(fā)技術(shù)和軟件工程管理。（1）軟件開(kāi)發(fā)技術(shù)軟件開(kāi)發(fā)技術(shù)包括：軟件開(kāi)發(fā)法學(xué)、開(kāi)發(fā)過(guò)程、開(kāi)發(fā)工具和軟件工程環(huán)境，其主體內(nèi)容是軟件開(kāi)發(fā)方法學(xué)。軟件開(kāi)發(fā)方法學(xué)是根據(jù)不同的軟件類型，按不同的觀點(diǎn)和原則，對(duì)軟件開(kāi)發(fā)中應(yīng)遵循的策略、原則、步驟和必須產(chǎn)生的文檔資料都做出規(guī)定，從而使軟件的開(kāi)發(fā)能夠進(jìn)入規(guī)范化和工程化的階段，以克服早期的手工方法生產(chǎn)中的隨意性和非規(guī)范性做法。（2）軟件工程管理軟件工程管理包括：軟件管理學(xué)、軟件工程經(jīng)濟(jì)學(xué)、軟件心理學(xué)等內(nèi)容。軟件工程管理是軟件按工程化生產(chǎn)時(shí)的重要環(huán)節(jié)，它要求按照預(yù)選制定的計(jì)劃、進(jìn)度和預(yù)算執(zhí)行，以實(shí)現(xiàn)預(yù)期的經(jīng)濟(jì)效益和社會(huì)效益。軟件工程經(jīng)濟(jì)學(xué)是研究軟件開(kāi)發(fā)中成本的估算、成本效益分析的方法和技術(shù)，用經(jīng)濟(jì)學(xué)的基本原理來(lái)研究軟件工程開(kāi)發(fā)中的經(jīng)濟(jì)效益問(wèn)題。軟件心理學(xué)是軟件工程領(lǐng)域具有挑戰(zhàn)性的一個(gè)全新的研究視角，它是從個(gè)體心理、人類行為、組織行為和企業(yè)文化等角度來(lái)研究軟件管理和軟件工程的。2、軟件工程的原則為了達(dá)到上述的軟件工程目標(biāo)，在軟件開(kāi)發(fā)過(guò)程中，必須遵循軟件工程的基本原則。這些基本原則包括抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。（1）抽象。抽取事物最基本的特性和行為，忽略非本質(zhì)細(xì)節(jié)。采用分層次抽象，自頂向下，逐層細(xì)化的辦法控制軟件開(kāi)發(fā)過(guò)程的復(fù)雜性。（2）信息隱蔽。采用封閉技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱藏起來(lái)，使模塊接口盡量簡(jiǎn)單。（3）模塊化。模塊是程序中相對(duì)獨(dú)立的成分，一個(gè)獨(dú)立的編程單位，應(yīng)有良好的接口定義。模塊的大小要適中，模塊過(guò)大會(huì)使模塊內(nèi)部的復(fù)雜性增加，不得對(duì)模塊的理解和個(gè)性也不得模塊的調(diào)試和重用。模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過(guò)于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性。（4）局部化。要求在一個(gè)物理模塊內(nèi)集中邏輯上相互關(guān)聯(lián)的計(jì)算資源，保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)驟性，這有助于控制角的復(fù)雜性。（5）確定性軟件開(kāi)發(fā)過(guò)程中所有概念的表達(dá)應(yīng)是確定的、無(wú)歧義且規(guī)范的。這有助于人與人的交互不會(huì)產(chǎn)生誤解和遺漏，以保證整個(gè)開(kāi)發(fā)工作的協(xié)調(diào)一致。（6）一致性。揚(yáng)程序、數(shù)據(jù)和文檔的整個(gè)軟件系統(tǒng)的各模塊應(yīng)使用已知的概念、符號(hào)和術(shù)語(yǔ)；程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說(shuō)明與系統(tǒng)行為應(yīng)保持一致。（7）完備性。軟件系統(tǒng)不丟失任何重要成分，完全實(shí)現(xiàn)系統(tǒng)所需的功能。（8）可驗(yàn)證性。開(kāi)發(fā)大型軟件系統(tǒng)需要對(duì)系統(tǒng)自頂向下，逐層分解。系統(tǒng)分解應(yīng)遵循容易檢查、測(cè)評(píng)、評(píng)審的原則，以確保系統(tǒng)的正確性。五、軟件開(kāi)發(fā)工具與軟件開(kāi)發(fā)環(huán)境現(xiàn)代軟件工程方法之所以千里馬實(shí)施，其重要的保證是軟件開(kāi)發(fā)工具的環(huán)境的保證，使軟件在開(kāi)發(fā)效率、工程質(zhì)量等多方面得到改善。軟件工程鼓勵(lì)研制和采用各種先進(jìn)的軟件開(kāi)發(fā)方法、工具和環(huán)境。工具和環(huán)境的使用進(jìn)一步提高了軟件的開(kāi)發(fā)效率、維護(hù)效率和軟件質(zhì)量。1、軟件開(kāi)發(fā)工具2、軟件開(kāi)發(fā)環(huán)境軟件開(kāi)發(fā)環(huán)境或稱軟件工程環(huán)境是全面支持軟件開(kāi)發(fā)全過(guò)程的軟件工具集合。計(jì)算機(jī)輔助軟件工程（CASE，computeraidedsoftwareengineering）是當(dāng)前軟件開(kāi)發(fā)環(huán)境中富有特色的研究工作和發(fā)展方向。CASE將各種軟件工具、開(kāi)發(fā)機(jī)器和一個(gè)慧放開(kāi)發(fā)過(guò)程信息的中心數(shù)據(jù)庫(kù)組合起來(lái)，形成軟件工程環(huán)境。CAS3E的成功產(chǎn)品將最大限度地降低軟件開(kāi)發(fā)的技術(shù)難度并使軟件開(kāi)發(fā)的質(zhì)量得到保證。3．2結(jié)構(gòu)化分析方法軟件開(kāi)發(fā)方法是軟件開(kāi)發(fā)過(guò)程所遵循的方法和步驟，其目的在于有效地得到一些工作產(chǎn)品，即程序和文檔，并且滿足質(zhì)量要求。軟件開(kāi)發(fā)方法包括分析方法、設(shè)計(jì)方法和程序設(shè)計(jì)方法。一、需求分析與需求分析方法1、需求分析軟件需求是指用戶對(duì)目標(biāo)軟件系統(tǒng)在功能、行為、性能、設(shè)計(jì)約束等方面的期望。需求分析的任務(wù)是發(fā)現(xiàn)需求、求精、建模和定義需求的過(guò)程。需求分析將創(chuàng)建所需的數(shù)據(jù)模型、功能模型和控制模型。（1）需求分析的定義A、用戶解決問(wèn)題或達(dá)到目標(biāo)所需的條件或權(quán)能；B、系統(tǒng)或系統(tǒng)部件要滿足合同、標(biāo)準(zhǔn)、規(guī)范或其他正式規(guī)定文檔所需具有的條件或權(quán)能；C、一種所映A、或B所描述的條件或權(quán)能的文檔說(shuō)明。由需求體魄定義可知，需求分析的內(nèi)容包括：提煉、分析和仔細(xì)審查已收集到的需求；確保所有利益相關(guān)者都明白其含義并找出其中的錯(cuò)誤、遺漏或其他不足的地方；從用戶最初的非形式化需求到滿足用戶對(duì)軟件產(chǎn)品的要求的映射；對(duì)用戶意圖不斷進(jìn)行提示和判斷。（2）需求分析階段的工作需求分析階段的工作，可以概括為四個(gè)方面：A、需求獲取需求獲取的目的是確定對(duì)目標(biāo)系統(tǒng)的各方面需求。涉及到的主要任務(wù)是建立獲取用戶需求的方法框架，并支持和監(jiān)控需求獲取的過(guò)程。B、需求分析對(duì)獲取的需求進(jìn)行分析和綜合，最終給出系統(tǒng)的解決方案和目標(biāo)系統(tǒng)的邏輯模型。C、編寫需求規(guī)格說(shuō)明書需求規(guī)格說(shuō)明書作為需求分析的階段成果，可以為用戶、分析人員和設(shè)計(jì)人員之間的交流提供方便，可以直接支持目標(biāo)軟件系統(tǒng)的確認(rèn)又可以作為控制軟件開(kāi)發(fā)進(jìn)程的依據(jù)。D、需求評(píng)審在需求分析的最后一步，對(duì)需求分析階段的工作進(jìn)行得審，驗(yàn)證需求文檔的一致性、可行性、完整性和有效性。2、需求分析方法常見(jiàn)的需求分析方法有：A、結(jié)構(gòu)化分析方法。主要包括：面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法（SA—Structuredanalysis），面向數(shù)據(jù)結(jié)構(gòu)的Jackson方法（JSD—Jacksonsystemdevelopmentmethod），面向數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)化數(shù)據(jù)系統(tǒng)開(kāi)發(fā)方法（DSSD—Datastructuredsystemdevelopmentmethod）。B、面向?qū)ο蟮姆治龇椒ǎ∣OA—Object-Orientedmethod）。從需求分析建立的模型的特性來(lái)分，需求分析方法又分為表態(tài)分析方法和動(dòng)態(tài)分析方法。二、結(jié)構(gòu)化分析方法1、關(guān)于結(jié)構(gòu)化分析方法結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的運(yùn)用。對(duì)于面向數(shù)據(jù)流的結(jié)構(gòu)化分析方法，按照DeMarco的定義，“結(jié)構(gòu)化分析就是使用數(shù)據(jù)流圖（DFD）、數(shù)據(jù)字典（DD）、結(jié)構(gòu)化英語(yǔ)、判定表和羊定樹(shù)等工具，來(lái)建立一種新的、稱為結(jié)構(gòu)化規(guī)格說(shuō)明的目標(biāo)文檔?！苯Y(jié)構(gòu)化分析方法的實(shí)質(zhì)是著眼于數(shù)據(jù)流自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具建立系統(tǒng)的邏輯模型。結(jié)構(gòu)化分析的步驟如下：A、通過(guò)對(duì)用戶的調(diào)查，以軟件的需求為線索，獲得當(dāng)前系統(tǒng)的具體模型；B、去掉具體模型中非本質(zhì)因素，抽象出當(dāng)前系統(tǒng)的邏輯模型；C、根據(jù)計(jì)算機(jī)的特點(diǎn)分析當(dāng)前系統(tǒng)與目標(biāo)系統(tǒng)的差別，建立目標(biāo)系統(tǒng)的邏輯模型；D、完善目標(biāo)系統(tǒng)并補(bǔ)充細(xì)節(jié)，寫出目標(biāo)系統(tǒng)的軟件需求規(guī)格說(shuō)明；E、評(píng)審直到確認(rèn)完全符合用戶對(duì)軟件的需求。2、結(jié)構(gòu)化分析的常用工具(1)數(shù)據(jù)流圖（DFD—DataFlowDiagram）數(shù)據(jù)流圖是描述數(shù)據(jù)處理過(guò)程的工具，是需求理解的邏輯模型的圖形表示，它直接支持系統(tǒng)的功能建模。數(shù)據(jù)流圖從數(shù)據(jù)傳遞和加工的角度，來(lái)刻畫數(shù)據(jù)流從輸入到輸出的移動(dòng)變換過(guò)程。數(shù)據(jù)流圖中的主要圖形元素與說(shuō)明如下：加工（轉(zhuǎn)換）。輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。數(shù)據(jù)流沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。存儲(chǔ)文件（數(shù)據(jù)源）。表示處理過(guò)程中存放各種數(shù)據(jù)的文件。源，潭。表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。一般通過(guò)對(duì)實(shí)際系統(tǒng)的了解和分析后，使用數(shù)據(jù)流圖為系統(tǒng)建立邏輯模型。建立數(shù)據(jù)流圖的步驟如下：第1步：由外向里：先畫系統(tǒng)的輸入輸出，然后畫系統(tǒng)的內(nèi)部。第2步：自頂向下：順序完成頂層、中間層、底層數(shù)據(jù)流圖。第3步：逐層分解。為保證構(gòu)造的數(shù)據(jù)流圖表達(dá)完整、準(zhǔn)確、規(guī)范，應(yīng)遵循以下數(shù)據(jù)流圖的構(gòu)造規(guī)則和注意事項(xiàng)：①對(duì)加工處理建立惟一、層次性的編號(hào)，且每個(gè)加工處理通常要求既有輸入又有輸出；②數(shù)據(jù)存儲(chǔ)之間不應(yīng)該有數(shù)據(jù)流；③數(shù)據(jù)流圖的一致性。④父圖、子圖關(guān)系與平衡規(guī)則。（2）數(shù)據(jù)字典（DD—DataDictionary）數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。數(shù)據(jù)字典是對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶和系統(tǒng)分析員對(duì)于輸入、輸出、存儲(chǔ)成分和中間計(jì)算結(jié)果有共同的理解。數(shù)據(jù)字典把不同的需求文檔和分析模型緊密地結(jié)合在一起，與各模型的圖形表示配合，能清楚地表達(dá)數(shù)據(jù)處理的要求。概括地說(shuō)，數(shù)據(jù)字典的作用是對(duì)DFD中出現(xiàn)的被命名的圖形元素的確切解釋。通常數(shù)據(jù)字典飲食的信息有：名稱，別名、何處作用/如何使用、內(nèi)容描述、補(bǔ)充信息等。（3）判定樹(shù)使用判定樹(shù)進(jìn)行描述時(shí)，應(yīng)先從問(wèn)題定義的文字描述中分清哪些是判定的條件，哪些是判定的結(jié)論，根據(jù)模仿材料中的連接詞找出判定條件之間的從屬關(guān)系、并列關(guān)系、選擇關(guān)系，根據(jù)它們構(gòu)造判定樹(shù)。（4）判定表判定表與判定樹(shù)相似，當(dāng)數(shù)據(jù)流圖中的加工要依賴于多個(gè)邏輯條件的聯(lián)歡會(huì)，即完成該加工的一組動(dòng)作是由于某一組條件聯(lián)歡會(huì)的組合而引發(fā)的，使用判定表描述比較適宜。判定表由四部分組成，基本條件，條件項(xiàng)，基本動(dòng)作，動(dòng)作項(xiàng)三、軟件需求規(guī)格說(shuō)明書軟件需求規(guī)格說(shuō)明書（SRS,softwareRequirementSpecification）是需求分析階段的最后成果，是軟件開(kāi)發(fā)中的文檔之一。1、軟件需求規(guī)格說(shuō)明書的作用①便于用戶、開(kāi)發(fā)人員進(jìn)行理解和交流。②反映出用戶問(wèn)題的結(jié)構(gòu)，可以作為軟件開(kāi)發(fā)工作的基礎(chǔ)和依據(jù)。③作為確認(rèn)測(cè)試的驗(yàn)收的依據(jù)。2、軟件需求規(guī)格說(shuō)明書的內(nèi)容一、概述二、數(shù)據(jù)描述數(shù)據(jù)流圖數(shù)據(jù)字典系統(tǒng)接口說(shuō)明內(nèi)部接口三、功能描述功能處理說(shuō)明設(shè)計(jì)的限制四、性能描述性能參數(shù)測(cè)試種類預(yù)期的軟件響應(yīng)應(yīng)考虎的特殊問(wèn)題五、參考文獻(xiàn)目錄六、附錄其中，概述是從系統(tǒng)的角度描述軟件的目標(biāo)和任務(wù)。數(shù)據(jù)描述是對(duì)軟件系統(tǒng)所必須解決的總是作出的詳細(xì)說(shuō)明功能描述中描述了為解決用戶問(wèn)題所需要的每一項(xiàng)功能的過(guò)程細(xì)節(jié)。對(duì)每一項(xiàng)功能要給出處理說(shuō)明和在設(shè)計(jì)時(shí)需要考慮的限制條件。在性能描述中說(shuō)明系統(tǒng)應(yīng)達(dá)到的性能和應(yīng)該滿足的限制條件，檢測(cè)的方法和標(biāo)準(zhǔn)，預(yù)期的軟件響應(yīng)和可能需要考慮的特殊問(wèn)題。參考文獻(xiàn)目錄中應(yīng)包括與該軟件有關(guān)全部參考文獻(xiàn)，其中包括前期的其他文檔、技術(shù)參考資料、產(chǎn)品目錄手冊(cè)以及標(biāo)準(zhǔn)等。附錄部分包括一些補(bǔ)充資料。3、軟件需求規(guī)格說(shuō)明書的特點(diǎn)①軟件需求規(guī)格說(shuō)明書是確保軟件質(zhì)量的有力措施，衡量軟件需求規(guī)格說(shuō)明書質(zhì)量好壞的標(biāo)準(zhǔn)、標(biāo)準(zhǔn)的優(yōu)先級(jí)及標(biāo)準(zhǔn)的內(nèi)涵是：②正確性。體現(xiàn)待開(kāi)發(fā)系統(tǒng)的真實(shí)要求。③無(wú)歧義性。對(duì)每一個(gè)需求只有一種解釋，其陳述具有惟一性。④完整性。包括全部有意義的需求，功能的、性能的、設(shè)計(jì)的、約束的，屬性或外部接口等方面的需求。⑤可驗(yàn)證性。描述的每一個(gè)需求都是可以驗(yàn)證的，即存在有限代價(jià)的有效過(guò)程驗(yàn)證確認(rèn)。⑥一致性。各個(gè)需求的描述矛盾。⑦可理解性。需求說(shuō)明書必須簡(jiǎn)明易懂，盡量少包含計(jì)算機(jī)的要領(lǐng)和術(shù)語(yǔ)，以便用戶和軟件人員都能接受它。⑧可修改性。每一個(gè)需求的來(lái)源、流向是清晰的，當(dāng)產(chǎn)生和改變文件編制時(shí)，可以方便地引證每一個(gè)需求。3.3結(jié)構(gòu)化設(shè)計(jì)方法一、軟件設(shè)計(jì)的基本概念1、軟件設(shè)計(jì)的基礎(chǔ)軟件設(shè)計(jì)是軟件工程的重要階段，是一個(gè)把軟件需求轉(zhuǎn)換為軟件表示的過(guò)程。軟件設(shè)計(jì)的基本目標(biāo)是用比較抽象概括的方式確定目標(biāo)系統(tǒng)如何完成預(yù)定的任務(wù)，即軟件設(shè)計(jì)是確定系統(tǒng)的物理模型。軟件設(shè)計(jì)的重要性和地位概括為以下幾點(diǎn)：①軟件開(kāi)發(fā)階段（設(shè)計(jì)、編碼、測(cè)試）占據(jù)軟件項(xiàng)目開(kāi)發(fā)總成本絕大部分，是在軟件開(kāi)發(fā)中形成質(zhì)量的關(guān)鍵五一節(jié)；②軟件設(shè)計(jì)是開(kāi)發(fā)階段最重要的步驟，是將需求準(zhǔn)確地轉(zhuǎn)化為完整的軟件產(chǎn)品或系統(tǒng)的惟一途徑；③軟件設(shè)計(jì)作出的決策，最終影響軟件實(shí)現(xiàn)的成??；④設(shè)計(jì)是軟件工程和軟件維護(hù)的基礎(chǔ)。從技術(shù)觀點(diǎn)來(lái)看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過(guò)程設(shè)計(jì)。其中，結(jié)構(gòu)設(shè)計(jì)是定義軟件系統(tǒng)各主要部件之間的關(guān)系；數(shù)據(jù)設(shè)計(jì)是將分析時(shí)創(chuàng)建的模型轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義；接口設(shè)計(jì)是描述軟件內(nèi)部、軟件和協(xié)作系統(tǒng)之間以及軟件與人之間如何通信；過(guò)程設(shè)計(jì)則是把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過(guò)程性描述。從工程管理角度來(lái)看，軟件設(shè)計(jì)分兩步完成：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。概要設(shè)計(jì)（又稱結(jié)構(gòu)設(shè)計(jì)）將軟件需求轉(zhuǎn)化為軟件體系結(jié)構(gòu)、確定系統(tǒng)級(jí)接口、全局?jǐn)?shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)庫(kù)模式；詳細(xì)設(shè)計(jì)確立每個(gè)模塊的實(shí)現(xiàn)算法和局部數(shù)據(jù)結(jié)構(gòu)，用適當(dāng)方法表示算法和數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)。軟件設(shè)計(jì)的一般過(guò)程是：軟件設(shè)計(jì)是一個(gè)迭代的過(guò)程；先進(jìn)行高層次的結(jié)構(gòu)設(shè)計(jì)；后進(jìn)行低層次的過(guò)程設(shè)計(jì)；穿插進(jìn)行數(shù)據(jù)設(shè)計(jì)和接口設(shè)計(jì)。2、軟件設(shè)計(jì)的基本原理軟件設(shè)計(jì)遵循軟件工程的基本目標(biāo)和原則，建立了適用于在軟件設(shè)計(jì)中應(yīng)該遵循的基本原理和與軟件設(shè)計(jì)有關(guān)的概念。（1）抽象抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取出來(lái)而不考慮其他細(xì)節(jié)。軟件設(shè)計(jì)中考慮模塊化解決方案時(shí)，可以定出多個(gè)抽象級(jí)別。抽象的層次從概要設(shè)計(jì)到詳細(xì)設(shè)計(jì)逐步聊低。在軟件概要設(shè)計(jì)中的模塊分層也是由抽象到具體逐步分析和構(gòu)造出來(lái)的。（2）模塊化模塊化是指把一個(gè)待開(kāi)發(fā)的軟件分解成若干個(gè)小的簡(jiǎn)單的部分。如高級(jí)語(yǔ)言中的過(guò)程、函數(shù)、子程序等。每個(gè)模塊可以完成一個(gè)特定的子功能，各個(gè)模塊可以按一定的方法組裝起來(lái)成為一個(gè)整體，從而實(shí)現(xiàn)整個(gè)系統(tǒng)的功能。模塊化是指解決一個(gè)復(fù)雜問(wèn)題時(shí)自頂向下逐層把軟件系統(tǒng)劃分成若干模塊的過(guò)程。為了解決復(fù)雜的問(wèn)題，在軟件設(shè)計(jì)中必須把整個(gè)問(wèn)題進(jìn)行分解來(lái)降低復(fù)雜性，這樣就可以減少開(kāi)發(fā)工作量并降低開(kāi)發(fā)成本和提高軟件生產(chǎn)率。但是劃分模塊并不是越多越好，因?yàn)檫@會(huì)增加模塊之間接口的工作量，所以劃分模塊層次和數(shù)量應(yīng)該避免過(guò)多或過(guò)少。（3）信息隱蔽信息隱蔽是指，在一個(gè)模塊內(nèi)包含的信息（過(guò)程或數(shù)據(jù)），對(duì)于不需要這些信息的其他模塊來(lái)說(shuō)是不能訪問(wèn)的。（4）模塊獨(dú)立性模塊獨(dú)立性是指，每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，并且與其他模塊的聯(lián)系最少且接口簡(jiǎn)單。是評(píng)價(jià)設(shè)計(jì)好壞的重要度量標(biāo)準(zhǔn)。衡量軟件的模塊獨(dú)立性作用耦合性和內(nèi)聚性兩個(gè)定性的度量標(biāo)準(zhǔn)○1內(nèi)聚性：內(nèi)聚性是一個(gè)模塊內(nèi)部各個(gè)元素間彼此結(jié)合的緊密程度的度量。內(nèi)聚是從功能角度來(lái)度量模塊內(nèi)的聯(lián)系。內(nèi)聚有如下的種類，它們之間的內(nèi)聚性由弱到強(qiáng)排列為：偶然內(nèi)聚邏輯內(nèi)聚時(shí)間內(nèi)聚過(guò)程通信內(nèi)聚順序內(nèi)聚功能內(nèi)聚內(nèi)聚性是信息隱蔽和局部化概念的自然擴(kuò)展。一個(gè)模塊的內(nèi)聚性越強(qiáng)則該模塊的模塊獨(dú)立性越強(qiáng)。作為軟件結(jié)構(gòu)設(shè)計(jì)的設(shè)計(jì)原則，要求生一個(gè)模塊的內(nèi)部都具有很強(qiáng)的內(nèi)聚性，它的各個(gè)組成部分彼此都密切相關(guān)?！?耦合性：耦合性是模塊間互相連接的緊密程度的度量。耦合性取決于各個(gè)模塊之間接口的復(fù)雜度、調(diào)用方式以及哪些信息通過(guò)接口。耦合可以分為下列幾種，它們之間的耦合度由高到低排列為：內(nèi)容耦合：如一個(gè)模塊直接訪問(wèn)另一模塊的內(nèi)容，則這兩個(gè)模塊稱為內(nèi)容耦合。公共耦合：若一組模塊都有訪問(wèn)同一全局?jǐn)?shù)據(jù)結(jié)構(gòu)，則它之間的耦合稱之為公共耦合。外部耦合：一組模塊都訪問(wèn)同一全局簡(jiǎn)單變量（而不是同一全局?jǐn)?shù)據(jù)結(jié)構(gòu)），且不通過(guò)參數(shù)表傳遞該全局變量的信息，則稱為外部耦合?？刂岂詈希喝粢荒K明顯地把開(kāi)頭量、名字等信息送入另一模塊，控制另一模塊的功能，則為控制耦合。標(biāo)記耦合：若兩個(gè)以上的模塊都需要其余某一數(shù)據(jù)結(jié)構(gòu)子結(jié)構(gòu)時(shí)，不使用其余全局變量的方式而是用記錄傳遞的方式，即兩模塊間通過(guò)數(shù)據(jù)結(jié)構(gòu)變換信息，這樣的耦合稱為標(biāo)記耦合。數(shù)據(jù)耦合：若一個(gè)模塊訪問(wèn)另一個(gè)模塊，被訪問(wèn)模塊的輸入和輸出都數(shù)據(jù)項(xiàng)參數(shù)，即兩模塊間通過(guò)數(shù)據(jù)參數(shù)交換信息，則這兩個(gè)模塊為數(shù)據(jù)耦合。非直接耦合：若兩個(gè)模塊沒(méi)有直接關(guān)系，它們之間的聯(lián)系完全是通過(guò)主模塊的控制和調(diào)用來(lái)實(shí)現(xiàn)的，則稱這兩個(gè)模塊為非直接耦合。非直接耦合獨(dú)立性最強(qiáng)。耦合性越強(qiáng)，獨(dú)立性越弱，希望模塊之間的耦合表現(xiàn)為非直接耦合方式。但是，由于問(wèn)題所固有的復(fù)雜性和結(jié)構(gòu)化設(shè)計(jì)的原則，非直接耦合往往是不存在的。耦合性與內(nèi)聚性是模塊獨(dú)立性的兩個(gè)定性標(biāo)準(zhǔn)，耦合與內(nèi)聚是相互關(guān)聯(lián)的。在程序結(jié)構(gòu)中，各模塊的內(nèi)聚性越強(qiáng)，則耦合性越弱。一般較優(yōu)秀的軟件設(shè)計(jì)，應(yīng)盡量做到高內(nèi)聚，低耦合，即減弱模塊之間的耦合性和提高模塊內(nèi)的內(nèi)聚性，有得提高模塊的獨(dú)立性。3、結(jié)構(gòu)設(shè)計(jì)方法與結(jié)構(gòu)化需求分析方法相對(duì)應(yīng)的是結(jié)構(gòu)化設(shè)計(jì)方法。結(jié)構(gòu)化設(shè)計(jì)就是采用最佳的可能方法設(shè)計(jì)系統(tǒng)的各個(gè)組成部分以及各成分之間的內(nèi)部聯(lián)系的技術(shù)。也就是說(shuō)，結(jié)構(gòu)設(shè)計(jì)是這樣一個(gè)過(guò)程，它決定用哪些方法把哪些部分聯(lián)系起來(lái)，才能解決好某個(gè)具體有清楚定義的問(wèn)題。結(jié)構(gòu)化設(shè)計(jì)方法的基本思想是將軟件設(shè)計(jì)成由相對(duì)獨(dú)立、單一功能的模塊組成的結(jié)構(gòu)。二、概要設(shè)計(jì)1、概要設(shè)計(jì)的任務(wù)軟件概要設(shè)計(jì)的基本任務(wù)是：（1）設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)在需求分析階段，已經(jīng)把系統(tǒng)分解成層次結(jié)構(gòu)，而在概要設(shè)計(jì)階段，需要過(guò)去時(shí)一步分解，劃分為模塊以及模塊的層次結(jié)構(gòu)。劃分的具體過(guò)程是：①采用某種設(shè)計(jì)方法，將一個(gè)復(fù)雜的系統(tǒng)按功能劃分成模塊。②確定每個(gè)模塊的功能。③確定模塊之間的調(diào)用關(guān)系。④確定模塊之間的接口，即模塊之間傳遞的信息。⑤評(píng)價(jià)模塊結(jié)構(gòu)的質(zhì)量。（2）數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫(kù)設(shè)計(jì)數(shù)據(jù)設(shè)計(jì)是實(shí)現(xiàn)需求定義和規(guī)格說(shuō)明過(guò)程中提出的數(shù)據(jù)對(duì)象的邏輯表示。數(shù)據(jù)設(shè)計(jì)的具體任務(wù)是：確定輸入、輸出文件的詳細(xì)數(shù)據(jù)結(jié)構(gòu)；結(jié)合算法設(shè)計(jì)，確定算法所必需的邏輯數(shù)據(jù)結(jié)構(gòu)及其操作；確定對(duì)邏輯數(shù)據(jù)結(jié)構(gòu)所必須的那些操作的程序模塊，限制和確定各個(gè)數(shù)據(jù)設(shè)計(jì)決策的影響范圍；需要與操作系統(tǒng)或調(diào)試程序接口所必需的控制表進(jìn)行數(shù)據(jù)交換時(shí)，確定其詳細(xì)的數(shù)據(jù)結(jié)構(gòu)和使用規(guī)則；數(shù)據(jù)的保護(hù)性設(shè)計(jì)：防衛(wèi)性、一致性、冗余性設(shè)計(jì)。數(shù)據(jù)設(shè)計(jì)中應(yīng)注意掌握以下設(shè)計(jì)原則：①用于功能和行為的系統(tǒng)分析原則也應(yīng)用于數(shù)據(jù)。②應(yīng)該標(biāo)識(shí)所有的數(shù)據(jù)結(jié)構(gòu)以及其上的操作。③應(yīng)當(dāng)建立數(shù)據(jù)字典，并用于數(shù)據(jù)設(shè)計(jì)和程序設(shè)計(jì)。④低層的設(shè)計(jì)決策應(yīng)該推遲到設(shè)計(jì)過(guò)程的后期。⑤只有那些需要直接使用數(shù)據(jù)結(jié)構(gòu)、內(nèi)部數(shù)據(jù)的模塊才能看該數(shù)據(jù)的表示。⑥應(yīng)該開(kāi)發(fā)一個(gè)由有用的數(shù)據(jù)結(jié)構(gòu)和應(yīng)用于其上的操作組成的庫(kù)。⑦軟件設(shè)計(jì)和程序設(shè)計(jì)語(yǔ)言應(yīng)該支持抽象數(shù)據(jù)類型的規(guī)格說(shuō)明和實(shí)現(xiàn)。（3）編定概要設(shè)計(jì)文檔。在概要設(shè)計(jì)階段，需要編寫的文檔有，概要設(shè)計(jì)說(shuō)明書、數(shù)據(jù)庫(kù)設(shè)計(jì)說(shuō)明書、集成測(cè)試計(jì)劃等。（4）概要設(shè)計(jì)文檔評(píng)審。在概要設(shè)計(jì)中，對(duì)設(shè)計(jì)部分是否完整地實(shí)現(xiàn)了需求中規(guī)定的功能、性能等要求，設(shè)計(jì)方案的可行性，關(guān)鍵的處理及內(nèi)外部接口定義正確性、有效性、各部分之間的一致性等都要進(jìn)行評(píng)審，以免在以后的設(shè)計(jì)中出現(xiàn)大的問(wèn)題而返工。常用的軟件結(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)系與通訊，是未來(lái)程序中的控制層次體系。結(jié)構(gòu)圖是描述軟件結(jié)構(gòu)的圖形工具。如圖3。8所示。模塊用一個(gè)矩形表示，矩形內(nèi)注明模塊的功能和名字；箭頭表示模塊間的調(diào)用關(guān)系。在結(jié)構(gòu)圖中還可以用帶注釋的箭頭表示模塊調(diào)用過(guò)程中來(lái)回傳遞的信息。如果希望進(jìn)一步標(biāo)明傳遞的信息是數(shù)據(jù)還是控制信息