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

1、.1.1 算法  1、算法是指解題方案的準(zhǔn)確而完整的描述。換句話說，算法是對(duì)特定問題求解步驟的一種描述。  *：算法不等于程序，也不等于計(jì)算方法。程序的編制不可能優(yōu)于算法的設(shè)計(jì)（注釋1）。  2、算法的基本特征  （1）可行性。針對(duì)實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。  （2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。  （3）有窮性。算法必須在有限的時(shí)間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個(gè)，二是每個(gè)步驟都能在有限時(shí)間內(nèi)完成。

2、  （4）擁有足夠的情報(bào)。算法中各種運(yùn)算總是要施加到各個(gè)運(yùn)算對(duì)象上，而這些運(yùn)算對(duì)象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點(diǎn)或依據(jù)。因此，一個(gè)算 法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會(huì)有不同的結(jié)果輸出。當(dāng)輸入不夠或輸入錯(cuò)誤時(shí)，算法將無法執(zhí)行或執(zhí)行有錯(cuò)。一般說來，當(dāng)算法擁有足夠 的情報(bào)時(shí)，此算法才是有效的；而當(dāng)提供的情報(bào)不夠時(shí)，算法可能無效。  *：綜上所述，所謂算法，是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。  3、算法復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。  （1）算法時(shí)間復(fù)雜度是

3、指執(zhí)行算法所需要的計(jì)算工作量，可以用執(zhí)行算法的過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量。  （2）算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。  例：1) 算法的復(fù)雜度主要包括_復(fù)雜度和空間復(fù)雜度。 答：時(shí)間 （注釋1）這是因?yàn)椋涸诰帉懗绦驎r(shí)要受到計(jì)算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制，程序通常還要考慮很多與方法和分析無關(guān)的細(xì)節(jié)問題。 1.2數(shù)據(jù)結(jié)構(gòu)的基本概念1、數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。2、數(shù)據(jù)結(jié)構(gòu)主要研究和討論以下三個(gè)方面的問題：（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：1）表示數(shù)據(jù)元素的信息；2）表示各數(shù)據(jù)

4、元素之間的前后件關(guān)系（注釋1）。（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。1）順序存儲(chǔ)。它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。2）鏈接存儲(chǔ)。它不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3）索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外，還建立附加的索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。*：數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）是數(shù)據(jù)的邏輯結(jié)構(gòu)在

5、計(jì)算機(jī)存儲(chǔ)空間中的存放形式。同一種邏輯結(jié)構(gòu)的數(shù)據(jù)可以采用不同的存儲(chǔ)結(jié)構(gòu)，但影響數(shù)據(jù)處理效率。例：(2)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的_。答：模式#邏輯模式#概念模式（3）對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。3、數(shù)據(jù)結(jié)構(gòu)的圖形表示 一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對(duì)于數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示， 一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡(jiǎn)稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對(duì)于關(guān)系R中的每一個(gè)二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。4、數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（1）線性結(jié)構(gòu)（非空的數(shù)

6、據(jù)結(jié)構(gòu)）條件：1）有且只有一個(gè)根結(jié)點(diǎn)（注釋2）；2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。*：常見的線性結(jié)構(gòu)有線性表、棧、隊(duì)列和線性鏈表等。（2）非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。*：常見的非線性結(jié)構(gòu)有樹、二叉樹和圖等。（注釋1）前后件關(guān)系：一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡(jiǎn)單地用前后件關(guān)系（即直接前驅(qū)與直接后繼關(guān)系）來描述。（注釋2）在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)。1.3 線性表及其順序存儲(chǔ)結(jié)構(gòu) 1、線性表由一組數(shù)據(jù)元素

7、構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。線性表是由n(n0)個(gè)數(shù)據(jù)元素組成的一個(gè) 有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長(zhǎng)度。線性表 可以為空表。 *：線性表是一種存儲(chǔ)結(jié)構(gòu)，它的存儲(chǔ)方式：順序和鏈?zhǔn)健?2、線性表的順序存儲(chǔ)結(jié)構(gòu)具有兩個(gè)基本特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。 *：由此可以看出，在線性表的順序存儲(chǔ)結(jié)構(gòu)中，其前后件兩個(gè)元素在存儲(chǔ)空間中是緊鄰的，且前件元素一定存儲(chǔ)在后件元素的前面，可以通過

8、計(jì)算機(jī)直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。 3、順序表的插入、刪除運(yùn)算（學(xué)吧學(xué)吧獨(dú)家稿件） （1）順序表的插入運(yùn)算：在一般情況下，要在第i（1in）個(gè)元素之前插入一個(gè)新元素時(shí)，首先要從最后一個(gè)（即第n個(gè)）元素開始， 直到第i個(gè)元素之間共n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，第i個(gè)位置就被空出，然后將新元素插入到第i項(xiàng)。插入結(jié)束后，線性表的長(zhǎng)度就增 加了1。 *：順性表的插入運(yùn)算時(shí)需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)n/2個(gè)元素。 （2）順序表的刪除運(yùn)算：在一般情況下，要?jiǎng)h除第i（1in）個(gè)元素時(shí)，則要從第i+1個(gè)元素開始，直到第n個(gè)元素之間共n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。刪除結(jié)

9、束后，線性表的長(zhǎng)度就減小了1。 *：進(jìn)行順性表的刪除運(yùn)算時(shí)也需要移動(dòng)元素，在等概率情況下，平均需要移動(dòng)（n-1）/2個(gè)元素。插入、刪除運(yùn)算不方便。 1.4 棧和隊(duì)列 1、棧及其基本運(yùn)算 棧是限定在一端進(jìn)行插入與刪除運(yùn)算的線性表。 在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，棧底元素總是最先被插入的元素。即棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。 棧具有記憶作用。 棧的基本運(yùn)算：1）插入元素稱為入棧運(yùn)算；2）刪除元素稱為退棧運(yùn)算；3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無變化。 棧的存儲(chǔ)方式和線性表類似，也有兩種

10、，即順序棧和鏈?zhǔn)綏！?2、隊(duì)列及其基本運(yùn)算 隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。尾指針（Rear）指向隊(duì)尾元素，頭指針（front）指向排頭元素的前一個(gè)位置（隊(duì)頭）。 隊(duì)列是“先進(jìn)先出”或“后進(jìn)后出”的線性表。 隊(duì)列運(yùn)算包括：1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。 循環(huán)隊(duì)列及其運(yùn)算：所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。在循環(huán)隊(duì) 列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從頭指針front指向的后一個(gè)位置直到隊(duì)尾

11、指針 rear指向的位置之間，所有的元素均為隊(duì)列中的元素。 *：循環(huán)隊(duì)列中元素的個(gè)數(shù)=rear-front。 1.5 線性鏈表1、線性表順序存儲(chǔ)的缺點(diǎn)：(1)插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素;(2)線性表的順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充;(3)線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對(duì)存儲(chǔ)空間的動(dòng)態(tài)分配。 2、線性鏈表：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表，是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實(shí)現(xiàn) 的。因此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域;另一

12、部分用于存放指針，稱為指針域，用于指向該結(jié)點(diǎn)的前一 個(gè)或后一個(gè)結(jié)點(diǎn)(即前件或后件)，如下圖所示：線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。在單鏈表中，每一個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到其后件結(jié)點(diǎn)，而不能找到其前件結(jié)點(diǎn)。因此，在某些應(yīng)用中，對(duì)于線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針，指向其前件結(jié)點(diǎn);另一個(gè)稱為右指針，指向其后件結(jié)點(diǎn)，這種鏈表稱為雙向鏈表，如下圖所示：3、線性鏈表的基本運(yùn)算(1)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。*：在線性鏈表中插入元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可，也不會(huì)出現(xiàn)“上溢（注釋1）”現(xiàn)象。(2)在線性鏈表中刪

13、除包含指定元素的結(jié)點(diǎn)。*：在線性鏈表中刪除元素時(shí)，也不需要移動(dòng)數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點(diǎn)指針即可。(3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。(4)將一個(gè)線性鏈表按要求進(jìn)行分解。(5)逆轉(zhuǎn)線性鏈表。(6)復(fù)制線性鏈表。(7)線性鏈表的排序。(8)線性鏈表的查找。*：線性鏈表不能隨機(jī)存?。ㄗ⑨?）。4、循環(huán)鏈表及其基本運(yùn)算在線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問題，在運(yùn)算過程中對(duì)于空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。為了克服線性鏈表的這個(gè)缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表。 與前面所討論的線性鏈表相比，循環(huán)鏈表具有以下兩個(gè)特點(diǎn)：1)在鏈

14、表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蛘吒鶕?jù)需要來設(shè)置，指針域指向線性表的第一 個(gè)元素的結(jié)點(diǎn)，而循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn);2)循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一 個(gè)環(huán)狀鏈。下圖a是一個(gè)非空的循環(huán)鏈表，圖b是一個(gè)空的循環(huán)鏈表： 循環(huán)鏈表的優(yōu)點(diǎn)主要體現(xiàn)在兩個(gè)方面：一是在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到 這一點(diǎn);二是由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。*：循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個(gè)表

15、頭結(jié)點(diǎn)，其插入和刪除運(yùn)算與單鏈表相同。但它可以從任一結(jié)點(diǎn)出發(fā)來訪問表中其他所有結(jié)點(diǎn)，并實(shí)現(xiàn)空表與非空表的運(yùn)算的統(tǒng)一。注釋1：當(dāng)為一個(gè)線性表分配順序存儲(chǔ)結(jié)構(gòu)后，如果出現(xiàn)線性表的存儲(chǔ)空間已滿，但還需要插入新的元素時(shí)，就會(huì)發(fā)生“上溢”現(xiàn)象。注釋2：在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號(hào)i，也不能像順序表中那樣直接按序號(hào)i訪問結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順著鏈域逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存儲(chǔ)結(jié)構(gòu)。1.6 樹與二叉樹 1、樹的基本概念 樹是一種簡(jiǎn)單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。 在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)

16、點(diǎn)。沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱樹的根。每一個(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)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。 2、二叉樹及其基本性質(zhì) (1)什么是二叉樹 二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個(gè)特點(diǎn)：1)非空二叉樹只有一個(gè)根結(jié)點(diǎn);2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。 *：根據(jù)二叉樹的概念可知，二叉樹的度可以為0(葉結(jié)點(diǎn))、1(只有一棵子樹)或2(有2棵子樹)。 (2)二叉樹的基本性質(zhì)(學(xué)吧學(xué)吧獨(dú)家稿件) 性質(zhì)1 在二叉樹的第k層

17、上，最多有2k-1(k1)個(gè)結(jié)點(diǎn)。 性質(zhì)2 深度為m的二叉樹最多有個(gè)2m-1個(gè)結(jié)點(diǎn)。 性質(zhì)3 在任意一棵二叉樹中，度數(shù)為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總比度為2的結(jié)點(diǎn)多一個(gè)。 性質(zhì)4 具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為log2n+1，其中l(wèi)og2n表示取log2n的整數(shù)部分。 3、滿二叉樹與完全二叉樹 滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。 完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值;在最后一層上只缺少右邊的若干結(jié)點(diǎn)。 *：根據(jù)完全二叉樹的定義可得出：度為1的結(jié)點(diǎn)的個(gè)數(shù)為0或1。 下圖a表示的是滿二叉樹，下圖b表示的是完全二叉樹： 完全二叉樹還具有如下兩個(gè)特性： 性質(zhì)5

18、 具有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)，則對(duì)于編號(hào)為k(k=1，2，n)的結(jié)點(diǎn)有以下結(jié)論： 若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn);若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT(k/2)。 若2kn，則編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k;否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)(顯然也沒有右子結(jié)點(diǎn))。 若2k+1n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+1;否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。 4、二叉樹的存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 與線性鏈表類似，用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)也由兩部分組

19、成：數(shù)據(jù)域和指針域。但在二叉樹中，由于每一個(gè)元素可以有兩個(gè)后件(即兩個(gè)子結(jié)點(diǎn))，因 此，用于存儲(chǔ)二叉樹的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域;另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為 右指針域。 *：一般二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹與完全二叉樹來說，可以按層序進(jìn)行順序存儲(chǔ)（注釋1） 。 5、二叉樹的遍歷 二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為以下三種： (1)前序遍歷(DLR)：若二叉樹為空，則結(jié)束返回。否則：首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹;并且，在遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷

20、左子樹，最后遍歷右子樹。 (2)中序遍歷(LDR)：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹;并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。 (3)后序遍歷(LRD)：若二叉樹為空，則結(jié)束返回。否則：首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。 注釋1：這樣，不僅節(jié)省了存儲(chǔ)空間，又能方便地確定每一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)與左右子結(jié)點(diǎn)的位置，但順序存儲(chǔ)結(jié)構(gòu)對(duì)于一般的二叉樹不適用。1.7 查找技術(shù) 查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)

21、據(jù)元素。 查找結(jié)果：（查找成功：找到；查找不成功：沒找到。） 平均查找長(zhǎng)度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。 1、順序查找 基本思想：從表中的第一個(gè)元素開始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。 在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情況下需要比較n次。 順序查找一個(gè)具有n個(gè)元素的線性表，其平均復(fù)雜度為O（n）。 下列兩種情況下只能采用順序查找： 1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。

22、2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。 2、二分法查找 思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。 前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。 查找過程： 1）若中間項(xiàng)（中間項(xiàng)mid=(n-1)/2，mid的值四舍五入取整）的值等于x，則說明已查到； 2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找； 3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。 特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。 *：二分法查找只適用于順序存儲(chǔ)的線性表，且表中元素必須按關(guān)鍵字有序（升序）排列（注釋1）。對(duì)于無序線性表和線性

23、表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找。在長(zhǎng)度為n的有序線性表中進(jìn)行二分法查找，其時(shí)間復(fù)雜度為O（log2n）。 注釋1：允許相鄰元素值相等。 1.8 排序技術(shù) 排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。 1、交換類排序法（方法：冒泡排序，快速排序）。 2、插入類排序法（方法：簡(jiǎn)單插入排序，希爾排序）。 3、選擇類排序法（方法：簡(jiǎn)單選擇排序，堆排序）。 總結(jié)：各種排序法比較： 2.1 程序設(shè)計(jì)風(fēng)格  程序設(shè)計(jì)的風(fēng)格主要強(qiáng)調(diào)：“清晰第一，效率第二”（注釋1）。主要應(yīng)注重和考慮下述一些因素：  （1）源程序文檔

24、化。  1）符號(hào)名的命名。符號(hào)名能反映它所代表的實(shí)際東西，應(yīng)有一定的實(shí)際含義。  2）程序的注釋。分為序言性注釋和功能性注釋。  序言性注釋：位于程序開頭部分，包括程序標(biāo)題、程序功能說明、主要算法、接口說明、程序位置、開發(fā)簡(jiǎn)歷、程序設(shè)計(jì)者、復(fù)審者、復(fù)審日期及修改日期等。  功能性注釋：嵌在源程序體之中，用于描述其后的語(yǔ)句或程序的主要功能。  3）視覺組織。利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?#160; （2）數(shù)據(jù)說明。  1）數(shù)據(jù)說明的次序規(guī)范化；  2）說明語(yǔ)句中變量安排有序化；  3）使用注釋來說明復(fù)雜

25、數(shù)據(jù)的結(jié)構(gòu)。  （3）語(yǔ)句的結(jié)構(gòu)。  1）在一行內(nèi)只寫一條語(yǔ)句；  2）程序編寫應(yīng)優(yōu)先考慮清晰性；  3）程序編寫要做到清晰第一，效率第二；  4）在保證程序正確的基礎(chǔ)上再要求提高效率；  5）避免使用臨時(shí)變量而使程序的可讀性下降；  6）避免不必要的轉(zhuǎn)移；  7）盡量使用庫(kù)函數(shù)；  8）避免采用復(fù)雜的條件語(yǔ)句；  9）盡量減少使用“否定”條件語(yǔ)句；  10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化；  11）要模塊化，使模塊功能盡可能單一化；  12）利用信息隱蔽（注釋2），&

26、#160; 確保每一個(gè)模塊的獨(dú)立性；  13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；  14）不要修補(bǔ)不好的程序，要重新編寫。  （4）輸入和輸出。  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ù)輸入過程中和輸入結(jié)束時(shí)，應(yīng)在屏幕

27、上給出狀態(tài)信息；  8）當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性；給所有的輸出加注釋，并設(shè)計(jì)輸出報(bào)表格式。  注釋1：“清晰第一，效率第二” 是當(dāng)今主導(dǎo)的程序設(shè)計(jì)風(fēng)格。  注釋2：信息隱蔽是指采用封裝技術(shù)，將程序模塊的實(shí)施細(xì)節(jié)隱藏起來，使模塊接口盡量簡(jiǎn)單。即指在設(shè)計(jì)和確定模塊時(shí)，使得一個(gè)模塊內(nèi)包含的信息（過程或數(shù)據(jù)），對(duì)于不需要這些信息的其它模塊來說，是不能訪問的。2.2 結(jié)構(gòu)化程序設(shè)計(jì)（面向過程的程序設(shè)計(jì)方法） 1、結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則可以概括為：自頂向下，逐步求精，模塊化，限制使用goto語(yǔ)句。 （1）自頂向下。

28、程序設(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ù)雜問題，肯定是由若干稍簡(jiǎn)單的問題構(gòu)成。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。 （4）限制使用goto語(yǔ)句。 2、結(jié)構(gòu)化程序的基本結(jié)構(gòu)：順序結(jié)構(gòu)，選擇結(jié)構(gòu)，重復(fù)結(jié)構(gòu)。 1）順序結(jié)構(gòu)。一種簡(jiǎn)單的程序設(shè)計(jì)，即按照程序語(yǔ)句行的自然順序，一條語(yǔ)句一條語(yǔ)句地執(zhí)行程序，它是最基本、最常用的結(jié)構(gòu)。 2）選擇結(jié)構(gòu)。又稱分支結(jié)構(gòu)

29、，包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)，可根據(jù)條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語(yǔ)句序列。 3）重復(fù)結(jié)構(gòu)。又稱循環(huán)結(jié)構(gòu)，可根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類似的程序段。 僅僅使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)就足以表達(dá)各種其他形式結(jié)構(gòu)，從而實(shí)現(xiàn)任何單入口/單出口的程序。2.3 面向?qū)ο蟮某绦蛟O(shè)計(jì) 客觀世界中任何一個(gè)事物都可以被看成是一個(gè)對(duì)象，面向?qū)ο蠓椒ǖ谋举|(zhì)就是主 張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡人們?cè)诂F(xiàn)實(shí)生活中常用的思維來認(rèn)識(shí)、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域。也就是說，系統(tǒng) 中的對(duì)象及對(duì)象之間的關(guān)系能夠如實(shí)地反映問題域中固有的事物及其關(guān)系。

30、面向?qū)ο蠓椒ǖ闹饕獌?yōu)點(diǎn)： （1）與人類習(xí)慣的思維方法一致； （2）穩(wěn)定性好； （3）可重用（注釋1） 性好； （4）易于開發(fā)大型軟件產(chǎn)品； （5）可維護(hù)性好。 *：面向?qū)ο蟮某绦蛟O(shè)計(jì)主要考慮的是提高軟件的可重用性。 對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睿梢杂脕肀硎究陀^世界中的任何實(shí)體，對(duì)象是實(shí)體的抽象。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中的對(duì)象是系統(tǒng)中用來描述客觀事物的 一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。對(duì)象是屬性和方法的封裝體。 屬性即對(duì)象所包含的信息，它在設(shè)計(jì)對(duì)象時(shí)確定，一般只能通過執(zhí)行對(duì)象的操作來改變。 操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服

31、務(wù)。操作是對(duì)象的動(dòng)態(tài)屬性。 *：一個(gè)對(duì)象由對(duì)象名、屬性和操作三部分組成。 對(duì)象的基本特點(diǎn)：標(biāo)識(shí)惟一性，分類性，多態(tài)性，封裝性，模塊獨(dú)立性好。 （1）標(biāo)識(shí)惟一性。指對(duì)象是可區(qū)分的，并且由對(duì)象的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分。 （2）分類性。指可以將具有相同屬性的操作的對(duì)象抽象成類。 （3）多態(tài)性。指同一個(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ì)

32、象的內(nèi)部狀態(tài)只能由其自身改 變。 *：信息隱蔽是通過對(duì)象的封裝性來實(shí)現(xiàn)的。 （5）模塊獨(dú)立性好。對(duì)象是面向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對(duì)這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對(duì)象是以數(shù)據(jù)為中心的，操作圍繞對(duì)其數(shù)據(jù)所需做的處理來設(shè)置，沒有無關(guān)的操作。從模塊的獨(dú)立性考慮，對(duì)象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強(qiáng)。 類是指具有共同屬性、共同方法的對(duì)象的集合。所以類是對(duì)象的抽象，對(duì)象是對(duì)應(yīng)類的一個(gè)實(shí)例。 消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞的信息。消息的組成包括：（1）接收消息的對(duì)象的名稱；（2）消息標(biāo)識(shí)符，也稱消息名；（3）零個(gè)或多個(gè)參數(shù)。 *：在面向?qū)ο蠓椒ㄖ?，一個(gè)對(duì)象請(qǐng)求另一個(gè)對(duì)象為其

33、服務(wù)的方式是通過發(fā)送消息。 繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義他們。繼承分單繼承和多重繼承。單繼承指一個(gè)類只允許有一個(gè)父類，多重繼承指一個(gè)類允許有多個(gè)父類。 *：類的繼承性是類之間共享屬性和操作的機(jī)制，它提高了軟件的可重用性。 多態(tài)性是指同樣的消息被不同的對(duì)象接受時(shí)可導(dǎo)致完全不同的行動(dòng)的現(xiàn)象。 本章應(yīng)考點(diǎn)撥：本章在考試中會(huì)出現(xiàn)約1個(gè)題目，所占分值大約占2分，是出題量較小的一章。本章內(nèi)容比較少，也很簡(jiǎn)單，掌握住基本的概念就可以輕松應(yīng)對(duì)考試了，所以在這部分丟分，比較可惜。 注釋1：軟件的重用是指在不同的軟件開發(fā)過程中重復(fù)使用相同或相似軟件的過程。3.1 軟件工程基本概念

34、  1、軟件的相關(guān)概念  計(jì)算機(jī)軟件是包括程序、數(shù)據(jù)及相關(guān)文檔的完整集合。  軟件的特點(diǎn)包括：1）軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性（注釋1） ；2）軟件的生產(chǎn)與硬件不同，它沒有明顯的制作過程；3）軟件在運(yùn)行、使用期間不存在磨損、老化問題；4）軟件的開發(fā)、運(yùn)行對(duì)計(jì)算機(jī)系統(tǒng)具有依賴性，受計(jì)算機(jī)系統(tǒng)的限制，這導(dǎo)致了軟件移植的問題；5）軟件復(fù)雜性高，成本昂貴；6）軟件開發(fā)涉及諸多的社會(huì)因素（注釋2）。  2、軟件危機(jī)與軟件工程  軟件工程源自軟件危機(jī)。所謂軟件危機(jī)是泛指在計(jì)算機(jī)軟件的開發(fā)和維護(hù)過程中所遇到的一系列嚴(yán)重問題。具體的

35、說，在軟件開發(fā)和維護(hù)過程中，軟件危機(jī)主要表現(xiàn)在：  1）軟件需求的增長(zhǎng)得不到滿足。用戶對(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)用需求的增長(zhǎng)。  總之，可以將軟件危機(jī)可以歸結(jié)為成本、質(zhì)量、生產(chǎn)率等問題。  軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具、文檔、實(shí)踐標(biāo)準(zhǔn)和工序。軟件工程

36、的目的就是要建造一個(gè)優(yōu)良的軟件系統(tǒng)，它所包含的內(nèi)容概括為以下兩點(diǎn)：  1）軟件開發(fā)技術(shù)，主要有軟件開發(fā)方法學(xué)、軟件工具、軟件工程環(huán)境。  2）軟件工程管理，主要有軟件管理、軟件工程經(jīng)濟(jì)學(xué)。  軟件工程的主要思想是將工程化原則運(yùn)用到軟件開發(fā)過程，它包括3個(gè)要素：方法、工具和過程。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具是支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。  軟件工程過程是把輸入轉(zhuǎn)化為輸出的一組彼此相關(guān)的資源和活動(dòng)。  3、軟件生命周期  軟件生命周期：軟件產(chǎn)品從提出、實(shí)現(xiàn)、使用維護(hù)到停止使用退役的過程

37、。  軟件生命周期分為軟件定義、軟件開發(fā)及軟件運(yùn)行維護(hù)三個(gè)階段：  1）軟件定義階段：包括制定計(jì)劃和需求分析。  制定計(jì)劃：確定總目標(biāo)；可行性研究；探討解決方案；制定開發(fā)計(jì)劃。  需求分析：對(duì)待開發(fā)軟件提出的需求進(jìn)行分析并給出詳細(xì)的定義。  2）軟件開發(fā)階段：  軟件設(shè)計(jì)：分為概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩個(gè)部分。  軟件實(shí)現(xiàn)：把軟件設(shè)計(jì)轉(zhuǎn)換成計(jì)算機(jī)可以接受的程序代碼。  軟件測(cè)試：在設(shè)計(jì)測(cè)試用例的基礎(chǔ)上檢驗(yàn)軟件的各個(gè)組成部分。  3）軟件運(yùn)行維護(hù)階段：軟件投入運(yùn)行，并在使用中不斷地維護(hù)，進(jìn)行必要的擴(kuò)充和刪改。&#

38、160; *：軟件生命周期中所花費(fèi)最多的階段是軟件運(yùn)行維護(hù)階段。  4、軟件工程的目標(biāo)和與原則  （1）軟件工程目標(biāo)：在給定成本、進(jìn)度的前提下，開發(fā)出具有有效性、可靠性、可理解性、  可維護(hù)性、可重用性、可適應(yīng)性、可移植性、可追蹤性和可互操作性且滿足用戶需求的產(chǎn)品。  （2）軟件工程需要達(dá)到的基本目標(biāo)應(yīng)是：付出較低的開發(fā)成本；達(dá)到要求的軟件功能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護(hù)費(fèi)用；能按時(shí)完成開發(fā)，及時(shí)交付使用。  （3）軟件工程原則：抽象、信息隱蔽、模塊化、局部化、確定性、一致性、完備性和可驗(yàn)證性。  1)抽象

39、：抽象是事物最基本的特性和行為，忽略非本質(zhì)細(xì)節(jié)，采用分層次抽象，自頂向下，逐層細(xì)化的辦法控制軟件開發(fā)過程的復(fù)雜性。  2）信息隱蔽：采用封裝技術(shù)，將程序模塊的實(shí)現(xiàn)細(xì)節(jié)隱蔽起來，使模塊接口盡量簡(jiǎn)單。  3）模塊化：模塊是程序中相對(duì)獨(dú)立的成分，一個(gè)獨(dú)立的編程單位，應(yīng)有良好的接口定義。模塊的大小要適中，模塊過大會(huì)使模塊內(nèi)部的復(fù)雜性增加，不利于模塊的理解和修改，也不利于模塊的調(diào)試和重用；模塊太小會(huì)導(dǎo)致整個(gè)系統(tǒng)表示過于復(fù)雜，不利于控制系統(tǒng)的復(fù)雜性。  4）局部化：保證模塊間具有松散的耦合關(guān)系，模塊內(nèi)部有較強(qiáng)的內(nèi)聚性。  5）確定性：軟件開發(fā)過程中所有概念的表達(dá)應(yīng)是

40、確定、無歧義且規(guī)范的。  6）一致性：程序內(nèi)外部接口應(yīng)保持一致，系統(tǒng)規(guī)格說明與系統(tǒng)行為應(yīng)保持一致。  7）完備性：軟件系統(tǒng)不丟失任何重要成分，完全實(shí)現(xiàn)系統(tǒng)所需的功能。  8）可驗(yàn)證性：應(yīng)遵循容易檢查、測(cè)評(píng)、評(píng)審的原則，以確保系統(tǒng)的正確性。  5、軟件開發(fā)工具與軟件開發(fā)環(huán)境  (1)軟件開發(fā)工具  軟件開發(fā)工具的完善和發(fā)展將促使軟件開發(fā)方法的進(jìn)步和完善，促進(jìn)軟件開發(fā)的高速度和高質(zhì)量。軟件開發(fā)工具的發(fā)展是從單項(xiàng)工具的開發(fā)逐步向集成工具發(fā)展 的，軟件開發(fā)工具為軟件工程方法提供了自動(dòng)的或半自動(dòng)的軟件支撐環(huán)境。同時(shí)，軟件開發(fā)方法的有效應(yīng)用也必須

41、得到相應(yīng)工具的支持，否則方法將難以有效的實(shí) 施。  （2）軟件開發(fā)環(huán)境  軟件開發(fā)環(huán)境（或稱軟件工程環(huán)境）是全面支持軟件開發(fā)全過程的軟件工具集合。  計(jì)算機(jī)輔助軟件工程（CASE，Computer Aided Software Engineering）將各種軟件工具、開發(fā)機(jī)器和一個(gè)存放開發(fā)過程信息的中心數(shù)據(jù)庫(kù)組合起來，形成軟件工程環(huán)境。它將極大降低軟件開發(fā)的技術(shù)難度并保證軟件開發(fā)的質(zhì)量。  注釋1：軟件的這個(gè)特點(diǎn)使它與其它工程對(duì)象有著明顯的差異。人們可以把它記錄在存儲(chǔ)介質(zhì)上，但卻無法看到軟件本身的形態(tài)，必須通過觀察、分析、思

42、考、判斷，才能了解它的功能、性能等特性。  注釋2：許多軟件的開發(fā)和運(yùn)行涉及軟件用戶的機(jī)構(gòu)設(shè)置，體制問題以及管理方式等，甚至涉及到人們的觀念和心理，軟件知識(shí)產(chǎn)權(quán)及法律等問題。 3.2 結(jié)構(gòu)化分析方法 結(jié)構(gòu)化方法的核心和基礎(chǔ)是結(jié)構(gòu)化程序設(shè)計(jì)理論。 1、需求分析 需求分析方法有：1）結(jié)構(gòu)化需求分析方法；2）面向?qū)ο蟮姆治龇椒ā?*：需求分析的任務(wù)就是導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型，解決“做什么”的問題。 *：需求分析一般分為需求獲取、需求分析、編寫需求規(guī)格說明書和需求評(píng)審四個(gè)步驟進(jìn)行。 2、結(jié)構(gòu)化分析方法 結(jié)構(gòu)化分析方法是結(jié)構(gòu)化程序設(shè)計(jì)理論在軟件需求分析階段的應(yīng)用。 結(jié)構(gòu)化分析方法的實(shí)

43、質(zhì)：著眼于數(shù)據(jù)流，自頂向下，逐層分解，建立系統(tǒng)的處理流程，以數(shù)據(jù)流圖和數(shù)據(jù)字典為主要工具，建立系統(tǒng)的邏輯模型。 結(jié)構(gòu)化分析的常用工具：1）數(shù)據(jù)流圖（DFD）；2）數(shù)據(jù)字典（DD）；3）判定樹；4）判定表。 數(shù)據(jù)流圖以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過程，它反映了系統(tǒng)必須完成的邏輯功能，是結(jié)構(gòu)化分析方法中用于表示系統(tǒng)邏輯模型的一種工具。 上圖是數(shù)據(jù)流圖的基本圖形元素： 加工（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。 數(shù)據(jù)流：沿箭頭方向傳送數(shù)據(jù)的通道，一般在旁邊標(biāo)注數(shù)據(jù)流名。 存儲(chǔ)文件（數(shù)據(jù)源）：表示處理過程中存放各種數(shù)據(jù)的文件。 源，潭：表示系統(tǒng)和環(huán)境的接口，屬系統(tǒng)之外的實(shí)體。 畫數(shù)據(jù)流圖的基

44、本步驟：自外向內(nèi)，自頂向下，逐層細(xì)化，完善求精。 下圖是一個(gè)數(shù)據(jù)流圖的示例： 數(shù)據(jù)字典：對(duì)所有與系統(tǒng)相關(guān)的數(shù)據(jù)元素的一個(gè)有組織的列表，以及精確的、嚴(yán)格的定義，使得用戶和系統(tǒng)分析員對(duì)于輸入、輸出、存儲(chǔ)成分和中間計(jì)算結(jié)果有共同的理解。 *：數(shù)據(jù)字典的作用是對(duì)數(shù)據(jù)流圖中出現(xiàn)的被命名的圖形元素的確切解釋。 *：數(shù)據(jù)字典是結(jié)構(gòu)化分析方法的核心。 3、軟件需求規(guī)格說明書（SRS） 軟件需求規(guī)格說明書是需求分析階段的最后成果，通過建立完整的信息描述、詳細(xì)的功能和行為描述、性能需求和設(shè)計(jì)約束的說明、合適的驗(yàn)收標(biāo)準(zhǔn)，給出對(duì)目標(biāo)軟件的各種需求。3.3 結(jié)構(gòu)化設(shè)計(jì)方法 1、軟件設(shè)計(jì)的基礎(chǔ) *：需求分析主要解決“做什

45、么”的問題，而軟件設(shè)計(jì)主要解決“怎么做”的問題。 從技術(shù)觀點(diǎn)來看，軟件設(shè)計(jì)包括軟件結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)設(shè)計(jì)、接口設(shè)計(jì)、過程設(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)之間以及軟件與人之間如何通信。 過程設(shè)計(jì)：把系統(tǒng)結(jié)構(gòu)部件轉(zhuǎn)換成軟件的過程性描述。 從工程角度來看，軟件設(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ì)的基本原理包括：抽象、模塊化、信息隱蔽和模塊獨(dú)立性。 1）抽象。抽象是一種思維工具，就是把事物本質(zhì)的共同特性提取出來而