數據結構與算法

1、數據結構與算法算法的復雜度算法的基本概念利用計算機算法為計算機解題的過程實際上是在實施某種算法。（1）算法的基本特征算法一般具有4 個基本特征：可行性、確定性、有窮性、擁有足夠的情報。（2）算法的基本運算和操作算法的基本運算和操作包括：算術運算、邏輯運算、關系運算、數據傳輸。（3）算法的3 種基本控制結構算法的3 種基本控制結構是：順序結構、選擇結構、循環(huán)結構。（4）算法基本設計方法算法基本設計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術、回溯法。（5）指令系統(tǒng)所謂指令系統(tǒng)指的是一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。算法復雜度算法復雜度包括時間復雜度和空間復雜度。時間復雜度執(zhí)行算法所需要的計

2、算工作量空間復雜度執(zhí)行這個算法所需要的內存空間1.2數據結構1.2.1邏輯結構和存儲結構1.數據結構的基本概念（1）數據結構指相互有關聯的數據元素的集合。二級公共基礎知識速學教程2（2）數據結構研究的3 個方面數據集合中各數據元素之間所固有的邏輯關系，即數據的邏輯結構；在對數據進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；對各種數據結構進行的運算。2.邏輯結構數據的邏輯結構是對數據元素之間的邏輯關系的描述，它可以用一個數據元素的集合和定義在此集合中的若干關系來表示。數據的邏輯結構有兩個要素：一是數據元素的集合，通常記為D；二是D 上的關系，它反映了數據元素之間的前后件關系，通常

3、記為R。一個數據結構可以表示成：B=(D,R)其中，B 表示數據結構。為了反映D 中各數據元素之間的前后件關系，一般用二元組來表示。例如，如果把一年四季看作一個數據結構，則可表示成：B =(D,R)D =春季,夏季,秋季,冬季R =(春季,夏季),(夏季,秋季),(秋季,冬季)3.存儲結構數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）。由于數據元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放在計算機存儲空間中的各數據元素之間的邏輯關系（即前后件關系），在數據的存儲結構中，不僅要存放各數據元素的信息，還需要存放各數據元素之間的前后件關系的

4、信息。一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接等存儲結構。順序存儲方式主要用于線性的數據結構，它把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元里，結點之間的關系由存儲單元的鄰接關系來體現。鏈式存儲結構就是在每個結點中至少包含一個指針域，用指針來體現數據元素之間邏輯上的聯系。二級公共基礎知識速學教程31.2.2線性結構和非線性結構根據數據結構中各數據元素之間前后件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。（1）如果一個非空的數據結構滿足下列兩個條件：有且只有一個根結點；每一個結點最多有一個前件，也最多有一個后件。則稱該數據結構為線性結

5、構。線性結構又稱線性表。在一個線性結構中插入或刪除任何一個結點后還應是線性結構。棧、隊列、串等都為線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。數組、廣義表、樹和圖等數據結構都是非線性結構。（2）線性表的順序存儲結構具有以下兩個基本特點：線性表中所有元素所占的存儲空間是連續(xù)的；線性表中各數據元素在存儲空間中是按邏輯順序依次存放的。元素ai 的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k，ADR(a1)為第一個元素的地址，k 代表每個元素占的字節(jié)數。（3）順序表的運算有查找、插入、刪除3 種。1.3棧1.棧的基本概念棧（stack）是一種特殊的線性表，是限定只在一端進行

6、插入與刪除的線性表。在棧中，一端是封閉的，既不允許進行插入元素，也不允許刪除元素；另一端是開口的，允許插入和刪除元素。通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時稱為空棧。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。棧是按照“先進后出”或“后進先出”的原則組織數據的。例如，槍械的子彈匣就可以用來形象的表示棧結構。子彈匣的一端是完全封閉的，最后被壓入彈匣的子彈總是最先被彈出，而最先被壓入的子彈最后才能被彈出。二級公共基礎知識速學教程42.棧的順序存儲及其運算棧的基本運算有3 種：入棧、退棧與讀棧頂元素。入棧

7、運算：在棧頂位置插入一個新元素；退棧運算：取出棧頂元素并賦給一個指定的變量；讀棧頂元素：將棧頂元素賦給一個指定的變量。1.4隊列1.隊列的基本概念隊列是只允許在一端進行刪除，在另一端進行插入的順序表，通常將允許刪除的這一端稱為隊頭，允許插入的這一端稱為隊尾。當表中沒有元素時稱為空隊列。隊列的修改是依照先進先出的原則進行的，因此隊列也稱為先進先出的線性表，或者后進后出的線性表。例如：火車進遂道，最先進遂道的是火車頭，最后是火車尾，而火車出遂道的時候也是火車頭先出，最后出的是火車尾。若有隊列：Q =(q 1 ,q 2 ,q n )那么，q 1為隊頭元素（排頭元素），q n為隊尾元素。隊列中的元素是

8、按照q 1 ，q 2 ，q n的順序進入的，退出隊列也只能按照這個次序依次退出，即只有在q 1 ，q 2 ，q n-1都退隊之后，q n才能退出隊列。因最先進入隊列的元素將最先出隊，所以隊列具有先進先出的特性，體現“先來先服務”的原則。隊頭元素q 1是最先被插入的元素，也是最先被刪除的元素。隊尾元素q n是最后被插入的元素，也是最后被刪除的元素。因此，與棧相反，隊列又稱為“先進先出”（First In First Out，簡稱FIFO）或“后進后出”（Last In Last Out，簡稱LILO）的線性表。2.隊列運算入隊運算是往隊列隊尾插入一個數據元素；退隊運算是從隊列的隊頭刪除一個數據元

9、素。隊列的順序存儲結構一般采用隊列循環(huán)的形式。循環(huán)隊列s=0 表示隊列空；二級公共基礎知識速學教程5s=1 且front=rear 表示隊列滿。計算循環(huán)隊列的元素個數：“尾指針減頭指針”，若為負數，再加其容量即可。1.5鏈表在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用于存放數據元素值，稱為數據域；另一部分用于存放指針，稱為指針域。其中指針用于指向該結點的前一個或后一個結點（即前件或后件）。鏈式存儲方式既可用于表示線性結構，也可用于表示非線性結構。（1）線性鏈表線性表的鏈式存儲結構稱為線性鏈表。在某些應用中，對線性鏈表中的每個結點設置兩個指針，一個稱為左指針，用以指向其前件結點；另一個稱

10、為右指針，用以指向其后件結點。這樣的表稱為雙向鏈表。在線性鏈表中，各數據元素結點的存儲空間可以是不連續(xù)的，且各數據元素的存儲順序與邏輯順序可以不一致。在線性鏈表中進行插入與刪除，不需要移動鏈表中的元素。線性單鏈表中，HEAD 稱為頭指針，HEAD=NULL（或0）稱為空表。如果是雙項鏈表的兩指針：左指針（Llink）指向前件結點，右指針（Rlink）指向后件結點。線性鏈表的基本運算：查找、插入、刪除。（2）帶鏈的棧棧也是線性表，也可以采用鏈式存儲結構。帶鏈的?？梢杂脕硎占嬎銠C存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為可利用棧。1.6二叉樹1.6.1二叉樹概念及其基本性質1.二叉樹及其基本

11、概念二叉樹是一種很有用的非線性結構，具有以下兩個特點：二級公共基礎知識速學教程非空二叉樹只有一個根結點；每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹。另外，二叉樹中的每個結點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結點既沒有左子樹也沒有右子樹時，該結點即為葉子結點。例如，一個家族中的族譜關系如圖1-1 所示：A 有后代B，C；B 有后代D，E；C 有后代F。典型的二叉樹如圖1-1 所示：詳細講解二叉樹的基本概念，見表1-2。圖

12、1-1 二叉樹圖表1-2二叉樹的基本概念父結點（根）在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。例如，在圖1-1 中，結點A 是樹的根結點。子結點和葉子結點在樹結構中，每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。例如，在圖1-1 中，結點D，E，F 均為葉子結點。度在樹結構中，一個結點所擁有的后件的個數稱為該結點的度，所有結點中最大的度稱為樹的度。例如，在圖1-1 中，根結點A 和結點B 的度為2，結點C 的度為1，葉子結點D，E，F 的度為0。所以，該樹的度為2。深度定義一棵樹的根結點所在的層次為1，其他結

13、點所在的層次等于它的父結點所在的層次加1。樹的最大層次稱為樹的深度。例如，在圖1-1 中，根結點A 在第1 層，結點B，C 在第2 層，結點D，E，F 在第3 層。該樹的深度為3。子樹在樹中，以某結點的一個子結點為根構成的樹稱為該結點的一棵子樹。6二級公共基礎知識速學教程72.二叉樹基本性質二叉樹具有以下幾個性質：性質1：在二叉樹的第k 層上，最多有2k-1（k1）個結點。性質2：深度為m 的二叉樹最多有2m-1 個結點。性質3：在任意一棵二叉樹中，度為0 的結點（即葉子結點）總是比度為2的結點多一個。性質4：具有n 個結點的二叉樹，其深度至少為log2n+1，其中l(wèi)og2n表示取log2n

14、的整數部分。3.滿二叉樹與完全二叉樹滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結點都有兩個子結點。在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k 層上有2k-1個結點，且深度為m 的滿二叉樹有2m-1 個結點。完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結點數均達到最大值；在最后一層上只缺少右邊的若干結點。對于完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現：對于任何一個結點，若其右分支下的子孫結點的最大層次為p，則其左分支下的子孫結點的最大層次或為p，或為p+1。完全二叉樹具有以下兩個性質：性質1：具有n 個結點的完全二叉樹的深度為log2n+1。

15、性質2：設完全二叉樹共有n 個結點。如果從根結點開始，按層次（每一層從左到右）用自然數1，2，n 給結點進行編號，則對于編號為k（k=1，2，n）的結點有以下結論：若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT（k/2）；若2kn，則編號為k 的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）；若2k+1n，則編號為k 的結點的右子結點編號為2k+1；否則該結點無右子結點。二級公共基礎知識速學教程81.6.2二叉樹的遍歷在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左后右的原則下，根據訪問根結點的次序，二叉樹的遍歷分為三類

16、：前序遍歷、中序遍歷和后序遍歷。（1）前序遍歷先訪問根結點，然后遍歷左子樹，最后遍歷右子樹；并且在遍歷左、右子樹時，仍需先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。例如，對圖1-1 中的二叉樹進行前序遍歷的結果（或稱為該二叉樹的前序序列）為：A，B，D，E，C，F。（2）中序遍歷先遍歷左子樹、然后訪問根結點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結點，最后遍歷右子樹。例如，對圖1-1中的二叉樹進行中序遍歷的結果（或稱為該二叉樹的中序序列）為：D，B，E，A，C，F。（3）后序遍歷先遍歷左子樹、然后遍歷右子樹，最后訪問根結點；并且，在遍歷左、右子樹時，仍然先遍歷

17、左子樹，然后遍歷右子樹，最后訪問根結點。例如，對圖1-1中的二叉樹進行后序遍歷的結果（或稱為該二叉樹的后序序列）為：D，E，B，F，C，A。1.7查找1.7.1順序查找查找是指在一個給定的數據結構中查找某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示查找失敗。例如，在一維數組21，46，24，99，57，77，86中，查找數據元素99，首二級公共基礎知識速學教程9先從第1 個元素21 開始進行比較，比較結果與要查找的數據不相等，接著與第2 個元素46 進行比較，以此類推，當進

18、行到與第4 個元素比較時，它們相等，所以查找成功。如果查找數據元素100，則整個線性表掃描完畢，仍未找到與100相等的元素，表示線性表中沒有要查找的元素。在下列兩種情況下也只能采用順序查找：如果線性表為無序表，則不管是順序存儲結構還是鏈式存儲結構，只能用順序查找；即使是有序線性表，如果采用鏈式存儲結構，也只能用順序查找。1.7.2二分法查找二分法查找，也稱拆半查找，是一種高效的查找方法。能使用二分法查找的線性表必須滿足用順序存儲結構和線性表是有序表兩個條件?！坝行颉笔翘刂冈匕捶沁f減排列，即從小到大排列，但允許相鄰元素相等。下一節(jié)排序中，有序的含義也是如此。對于長度為n 的有序線性表，利用二分

19、法查找元素X 的過程如下：步驟1：將X 與線性表的中間項比較；步驟2：如果X 的值與中間項的值相等，則查找成功，結束查找；步驟3：如果X 小于中間項的值，則在線性表的前半部分以二分法繼續(xù)查找；步驟4：如果X 大于中間項的值，則在線性表的后半部分以二分法繼續(xù)查找。例如，長度為8 的線性表關鍵碼序列為：6，13，27，30，38，46，47，70，被查元素為38，首先將與線性表的中間項比較，即與第4 個數據元素30 相比較，38 大于中間項30 的值，則在線性表38，46，47，70中繼續(xù)查找；接著與中間項比較，即與第2 個元素46 相比較，38 小于46，則在線性表38中繼續(xù)查找，最后一次比較相

20、等，查找成功。順序查找法每一次比較，只將查找范圍減少1，而二分法查找，每比較一次，可將查找范圍減少為原來的一半，效率大大提高。對于長度為n 的有序線性表，在最壞情況下，二分法查找只需比較log2n 次，二級公共基礎知識速學教程10而順序查找需要比較n 次。1.8排序1.交換類排序法（1）冒泡排序法首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往后移動，最后最大者到了線性表的最后。然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前

21、移動，最后最小者到了線性表的最前面。對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時已經排好序。在最壞的情況下，冒泡排序需要比較次數為n(n-1)/2。（2）快速排序法任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一次排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序。2.插入類排序法簡單插入排序法，最壞情況需要n(n-1)/2 次比較；希爾排序法，最壞情況需要O(n1.5)次比較。3.選擇類排序法簡單選擇排序法，最壞情況需要n(n-1)/2 次

22、比較；堆排序法，最壞情況需要O(nlog2n)次比較。相比以上幾種（除希爾排序法外），堆排序法的時間復雜度最小。二級公共基礎知識速學教程11第2章程序設計基礎2.1程序設計的方法與風格養(yǎng)成良好的程序設計風格，主要考慮下述因素：（1）源程序文檔化符號名的命名：符號名的命名應具有一定的實際含義，以便于對程序功能的理解；程序注釋：在源程序中添加正確的注釋可幫助人們理解程序。程序注釋可分為序言性注釋和功能性注釋。語句結構清晰第一、效率第二；視覺組織：通過在程序中添加一些空格、空行和縮進等，使人們在視覺上對程序的結構一目了然。（2）數據說明的方法為使程序中的數據說明易于理解和維護，可采用下列數據說明的風

23、格，見表2-1。表2-1數據說明風格數據說明風格詳細說明次序應規(guī)范化使數據說明次序固定，使數據的屬性容易查找，也有利于測試、排錯和維護變量安排有序化當多個變量出現在同一個說明語句中時，變量名應按字母順序排序，以便于查找使用注釋在定義一個復雜的數據結構時，應通過注解來說明該數據結構的特點（3）語句的結構程序語句的結構程序應該簡單易懂，語句構造應該簡單直接。（4）輸入和輸出輸入輸出比較簡單，這里就不作介紹。二級公共基礎知識速學教程122.2結構化程序設計1.結構化程序設計的原則結構化程序設計方法引入了工程思想和結構化思想，使大型軟件的開發(fā)和編程得到了極大的改善。結構化程序設計方法的主要原則為：自頂

24、向下、逐步求精、模塊化和限制使用goto 語句。自頂向上：先考慮整體，再考慮細節(jié)；先考慮全局目標，再考慮局部目標；逐步求精：對復雜問題應設計一些子目標作為過渡，逐步細化；模塊化：把程序要解決的總目標分解為分目標，再進一步分解為具體的小目標，把每個小目標稱為一個模塊。限制使用goto 語句：在程序開發(fā)過程中要限制使用goto 語句。2.結構化程序的基本結構結構化程序的基本結構有三種類型：順序結構、選擇結構和循環(huán)結構。順序結構：是最基本、最普通的結構形式，按照程序中的語句行的先后順序逐條執(zhí)行；選擇結構：又稱為分支結構，它包括簡單選擇和多分支選擇結構；循環(huán)結構：根據給定的條件，判斷是否要重復執(zhí)行某一

25、相同的或類似的程序段。循環(huán)結構對應兩類循環(huán)語句：先判斷后執(zhí)行的循環(huán)體稱為當型循環(huán)結構；先執(zhí)行循環(huán)體后判斷的稱為直到型循環(huán)結構。2.3面向對象方法面向對象方法涵蓋對象及對象屬性與方法、類、繼承、多態(tài)性幾個基本要素。1.對象通常把對象的操作也稱為方法或服務。屬性即對象所包含的信息，它在設計對象時確定，一般只能通過執(zhí)行對象的操作來改變。屬性值應該指的是純粹的數據值，而不能指對象。操作描述了對象執(zhí)行的功能，若通過信息的傳遞，還可以為其他對象使用。二級公共基礎知識速學教程13對象具有如下特征：標識惟一性、分類性、多態(tài)性、封裝性、模塊獨立性。2.類和實例類是具有共同屬性、共同方法的對象的集合。它描述了屬于

26、該對象類型的所有對象的性質，而一個對象則是其對應類的一個實例。類是關于對象性質的描述，它同對象一樣，包括一組數據屬性和在數據上的一組合法操作。3.消息消息是實例之間傳遞的信息，它請求對象執(zhí)行某一處理或回答某一要求的信息，它統(tǒng)一了數據流和控制流。一個消息由三部分組成：接收消息的對象的名稱、消息標識符（消息名）和零個或多個參數。4.繼承廣義地說，繼承是指能夠直接獲得已有的性質和特征，而不必重復定義它們。繼承分為單繼承與多重繼承。單繼承是指，一個類只允許有一個父類，即類等級為樹形結構。多重繼承是指，一個類允許有多個父類。5.多態(tài)性對象根據所接受的消息而做出動作，同樣的消息被不同的對象接受時可導致完全

27、不同的行動，該現象稱為多態(tài)性。二級公共基礎知識速學教程14第3章軟件工程基礎3.1軟件工程基本概念1.軟件定義與軟件特點軟件指的是計算機系統(tǒng)中與硬件相互依存的另一部分，包括程序、數據和相關文檔的完整集合。程序是軟件開發(fā)人員根據用戶需求開發(fā)的、用程序設計語言描述的、適合計算機執(zhí)行的指令序列。數據是使程序能正常操縱信息的數據結構。文檔是與程序的開發(fā)、維護和使用有關的圖文資料。可見，軟件由兩部分組成：􀁺機器可執(zhí)行的程序和數據；􀁺機器不可執(zhí)行的，與軟件開發(fā)、運行、維護、使用等有關的文檔。根據應用目標的不同，軟件可分應用軟件、系統(tǒng)軟件和支撐軟件（或工具軟件），見表3-

28、1。表3-1軟件的分類名稱描述應用軟件為解決特定領域的應用而開發(fā)的軟件系統(tǒng)軟件計算機管理自身資源，提高計算機使用效率并為計算機用戶提供各種服務的軟件支撐軟件（或工具軟件）支撐軟件是介于兩者之間，協助用戶開發(fā)軟件的工具性軟件2.軟件工程為了擺脫軟件危機，提出了軟件工程的概念。軟件工程學是研究軟件開發(fā)和維護的普遍原理與技術的一門工程學科。所謂軟件工程是指采用工程的概念、原理、技術和方法指導軟件的開發(fā)與維護。軟件工程學的主要研究對象包括軟件開發(fā)與維護的技術、方法、工具和管理等方面。二級公共基礎知識速學教程軟件工程包括3 個要素：方法、工具和過程，見表3-2。表3-2軟件工程三要素名稱描述方法方法是完

29、成軟件工程項目的技術手段工具工具支持軟件的開發(fā)、管理、文檔生成過程過程支持軟件開發(fā)的各個環(huán)節(jié)的控制、管理3.2軟件生命周期1.軟件生命周期概念軟件產品從提出、實現、使用維護到停止使用退役的過程稱為軟件生命周期。軟件生命周期分為3 個時期共8 個階段，􀁺軟件定義期：包括問題定義、可行性研究和需求分析3 個階段；􀁺軟件開發(fā)期：包括概要設計、詳細設計、實現和測試4 個階段；􀁺運行維護期：即運行維護階段。軟件生命周期各個階段的活動可以有重復，執(zhí)行時也可以有迭代，如圖3-1所示。圖3-1 軟件生命周期15二級公共基礎知識速學教程162.軟件生命周期各

30、階段的主要任務在圖3-1 中的軟件生命周期各階段的主要任務，見表3-3。表3-3軟件生命周期各階段的主要任務任務描述問題定義確定要求解決的問題是什么可行性研究與計劃制定決定該問題是否存在一個可行的解決辦法，指定完成開發(fā)任務的實施計劃需求分析對待開發(fā)軟件提出需求進行分析并給出詳細定義。編寫軟件規(guī)格說明書及初步的用戶手冊，提交評審軟件設計通常又分為概要設計和詳細設計兩個階段，給出軟件的結構、模塊的劃分、功能的分配以及處理流程。這階段提交評審的文檔有概要設計說明書、詳細設計說明書和測試計劃初稿軟件實現在軟件設計的基礎上編寫程序。這階段完成的文檔有用戶手冊、操作手冊等面向用戶的文檔，以及為下一步作準備

31、而編寫的單元測試計劃軟件測試在設計測試用例的基礎上，檢驗軟件的各個組成部分。編寫測試分析報告運行維護將已交付的軟件投入運行，同時不斷的維護，進行必要而且可行的擴充和刪改3.3軟件設計3.3.1軟件設計基本概念（1）按技術觀點分從技術觀點上看，軟件設計包括軟件結構設計、數據設計、接口設計、過程設計。結構設計定義軟件系統(tǒng)各主要部件之間的關系；數據設計將分析時創(chuàng)建的模型轉化為數據結構的定義；接口設計是描述軟件內部、軟件和協作系統(tǒng)之間以及軟件與人之間如何通信；過程設計則是把系統(tǒng)結構部件轉換為軟件的過程性描述。（2）按工程管理角度分從工程管理角度來看，軟件設計分兩步完成：概要設計和詳細設計。二級公共基礎

32、知識速學教程17概要設計將軟件需求轉化為軟件體系結構、確定系統(tǒng)級接口、全局數據結構或數據庫模式；詳細設計確立每個模塊的實現算法和局部數據結構，用適當方法表示算法和數據結構的細節(jié)。3.3.2軟件設計的基本原理1.軟件設計中應該遵循的基本原理和與軟件設計有關的概念（1）抽象軟件設計中考慮模塊化解決方案時，可以定出多個抽象級別。抽象的層次從概要設計到詳細設計逐步降低。（2）模塊化模塊是指把一個待開發(fā)的軟件分解成若干小的簡單的部分。模塊化是指解決一個復雜問題時自頂向下逐層把軟件系統(tǒng)劃分成若干模塊的過程。（3）信息隱蔽信息隱蔽是指在一個模塊內包含的信息（過程或數據），對于不需要這些信息的其他模塊來說是不

33、能訪問的。（4）模塊獨立性模塊獨立性是指每個模塊只完成系統(tǒng)要求的獨立的子功能，并且與其他模塊的聯系最少且接口簡單。模塊的獨立程度是評價設計好壞的重要度量標準。衡量軟件的模塊獨立性使用耦合性和內聚性兩個定性的度量標準。內聚性是信息隱蔽和局部化概念的自然擴展。一個模塊的內聚性越強則該模塊的模塊獨立性越強。一個模塊與其他模塊的耦合性越強則該模塊的模塊獨立性越弱。2.衡量軟件模塊獨立性使用耦合性和內聚性兩個定性的度量標準內聚性是度量一個模塊功能強度的一個相對指標。內聚是從功能角度來衡量模塊的聯系，它描述的是模塊內的功能聯系。內聚有如下種類，它們之間的內聚度由弱到強排列：偶然內聚、邏輯內聚、時間內聚、過

34、程內聚、通信內聚、順序內聚、功能內聚。耦合性是模塊之間互相連接的緊密程度的度量。耦合性取決于各個模塊之間二級公共基礎知識速學教程18接口的復雜度、調用方式以及哪些信息通過接口。耦合可以分為多種形勢，它們之間的耦合度由高到低排列：內容耦合、公共耦合、外部耦合、控制耦合、標記耦合、數據耦合、非直接耦合。在程序結構中，各模塊的內聚性越強，則耦合性越弱。一般較優(yōu)秀的軟件設計，應盡量做到高內聚，低耦合，即減弱模塊之間的耦合性和提高模塊內的內聚性，有利于提高模塊的獨立性。3.4結構化分析方法1.結構化分析方法的定義結構化分析方法就是使用數據流圖（DFD）、數據字典（DD）、結構化英語、判定表和判定樹的工具

35、，來建立一種新的、稱為結構化規(guī)格說明的目標文檔。結構化分析方法的實質是著眼于數據流、自頂向下、對系統(tǒng)的功能進行逐層分解、以數據流圖和數據字典為主要工具，建立系統(tǒng)的邏輯模型。2.結構化分析方法常用工具（1）數據流圖（DFD）數據流圖是系統(tǒng)邏輯模型的圖形表示，即使不是專業(yè)的計算機技術人員也容易理解它，因此它是分析員與用戶之間極好的通信工具。（2）數據字典（DD）數據字典是對數據流圖中所有元素的定義的集合，是結構化分析的核心。數據流圖和數據字典共同構成系統(tǒng)的邏輯模型，沒有數據字典數據流圖就不嚴格，若沒有數據流圖，數據字典也難于發(fā)揮作用。數據字典中有4 種類型的條目：數據流、數據項、數據存儲和加工。（

36、3）判定表有些加工的邏輯用語言形式不容易表達清楚，而用表的形式則一目了然。如果一個加工邏輯有多個條件、多個操作，并且在不同的條件組合下執(zhí)行不同的操作，那么可以使用判定表來描述。（4）判定樹判定樹和判定表沒有本質的區(qū)別，可以用判定表表示的加工邏輯都能用判定二級公共基礎知識速學教程19樹表示。3.軟件需求規(guī)格說明書軟件需求規(guī)格說明書是需求分析階段的最后成果，是軟件開發(fā)的重要文檔之一。它的特點是具有正確性、無歧義性、完整性、可驗證性、一致性、可理解性、可修改性和可追蹤性。3.5軟件測試3.5.1軟件測試的目的和準則1.軟件測試的目的Grenford.J.Myers 給出了軟件測試的目的：И

37、698;測試是為了發(fā)現程序中的錯誤而執(zhí)行程序的過程；􀁺好的測試用例（test case）能發(fā)現迄今為止尚未發(fā)現的錯誤；􀁺一次成功的測試是能發(fā)現至今為止尚未發(fā)現的錯誤。測試的目的是發(fā)現軟件中的錯誤，但是，暴露錯誤并不是軟件測試的最終目的，測試的根本目的是盡可能多地發(fā)現并排除軟件中隱藏的錯誤。2.軟件測試的準則根據上述軟件測試的目的，為了能設計出有效的測試方案，以及好的測試用例，軟件測試人員必須深入理解，并正確運用以下軟件測試的基本準則：􀁺所有測試都應追溯到用戶需求；􀁺在測試之前制定測試計劃，并嚴格執(zhí)行；􀁺充

38、分注意測試中的群集現象；􀁺避免由程序的編寫者測試自己的程序；􀁺不可能進行窮舉測試；􀁺妥善保存測試計劃、測試用例、出錯統(tǒng)計和最終分析報告，為維護提供方便。3.5.2軟件測試的方法和實施1.軟件測試方法軟件測試具有多種方法，依據軟件是否需要被執(zhí)行，可以分為靜態(tài)測試和動二級公共基礎知識速學教程20態(tài)測試方法。如果依照功能劃分，可以分為白盒測試和黑盒測試方法。（1）靜態(tài)測試和動態(tài)測試靜態(tài)測試包括代碼檢查、靜態(tài)結構分析、代碼質量度量等。其中代碼檢查分為代碼審查、代碼走查、桌面檢查、靜態(tài)分析等具體形式；動態(tài)測試。靜態(tài)測試不實際運行軟件，主要通過人工進行

39、分析。動態(tài)測試就是通常所說的上機測試，是通過運行軟件來檢驗軟件中的動態(tài)行為和運行結果的正確性。動態(tài)測試的關鍵是使用設計高效、合理的測試用例。測試用例就是為測試設計的數據，由測試輸入數據和預期的輸出結果兩部份組成。測試用例的設計方法一般分為兩類：黑盒測試方法和白盒測試方法。（2）黑盒測試和白盒測試白盒測試。白盒測試是把程序看成裝在一只透明的白盒子里，測試者完全了解程序的結構和處理過程。它根據程序的內部邏輯來設計測試用例，檢查程序中的邏輯通路是否都按預定的要求正確地工作；黑盒測試。黑盒測試是把程序看成一只黑盒子，測試者完全不了解，或不考慮程序的結構和處理過程。它根據規(guī)格說明書的功能來設計測試用例，

40、檢查程序的功能是否符合規(guī)格說明的要求。2.軟件測試的實施軟件測試過程分4 個步驟，即單元測試、集成測試、驗收測試和系統(tǒng)測試。單元測試是對軟件設計的最小單位模塊（程序單元）進行正確性檢驗測試。單元測試的技術可以采用靜態(tài)分析和動態(tài)測試。集成測試是測試和組裝軟件的過程，主要目的是發(fā)現與接口有關的錯誤，主要依據是概要設計說明書。集成測試所設計的內容包括：軟件單元的接口測試、全局數據結構測試、邊界條件和非法輸入的測試等。集成測試時將模塊組裝成程序，通常采用兩種方式：非增量方式組裝和增量方式組裝。確認測試的任務是驗證軟件的功能和性能，以及其他特性是否滿足了需求規(guī)格說明中確定的各種需求，包括軟件配置是否完全

41、、正確。確認測試的實施首先運用黑盒測試方法，對軟件進行有效性測試，即驗證被測軟件是否滿足需求規(guī)格二級公共基礎知識速學教程21說明確認的標準。系統(tǒng)測試是通過測試確認的軟件，作為整個基于計算機系統(tǒng)的一個元素，與計算機硬件、外設、支撐軟件、數據和人員等其他系統(tǒng)元素組合在一起，在實際運行（使用）環(huán)境下對計算機系統(tǒng)進行一系列的集成測試和確認測試。系統(tǒng)測試的具體實施一般包括：功能測試、性能測試、操作測試、配置測試、外部接口測試、安全性測試等。3.6程序的調試在對程序進行了成功的測試之后將進入程序調試（通常稱Debug，即排錯）。程序的調試任務是診斷和改正程序中的錯誤。調試主要在開發(fā)階段進行。程序調試活動由

42、兩部分組成，一是根據錯誤的跡象確定程序中錯誤的確切性質、原因和位置；二是對程序進行修改，排除這個錯誤。程序調試的基本步驟：錯誤定位。從錯誤的外部表現形式入手，研究有關部分的程序，確定程序中出錯位置，找出錯誤的內在原因；修改設計和代碼，以排除錯誤；進行回歸測試，防止引進新的錯誤。軟件調試可分為靜態(tài)調試和動態(tài)調試。靜態(tài)調試主要是指通過人的思維來分析源程序代碼和排錯，是主要的設計手段，而動態(tài)調試是輔助靜態(tài)調試的。主要的調試方法有：強行排錯法、回溯法和原因排除法3 種。二級公共基礎知識速學教程22第4章數據庫設計基礎4.1數據庫的基本概念數據是數據庫中存儲的基本對象，它是描述事物的符號記錄。數據庫是長

43、期儲存在計算機內、有組織的、可共享的大量數據的集合，它具有統(tǒng)一的結構形式并存放于統(tǒng)一的存儲介質內，是多種應用數據的集成，并可被各個應用程序所共享，所以數據庫技術的根本目標是解決數據共享問題。數據庫管理系統(tǒng)（DBMS，Database Management System）是數據庫的機構，它是一種系統(tǒng)軟件，負責數據庫中的數據組織、數據操作、數據維護、控制及保護和數據服務等。數據庫管理系統(tǒng)是數據系統(tǒng)的核心。為完成數據庫管理系統(tǒng)的功能，數據庫管理系統(tǒng)提供相應的數據語言：數據定義語言、數據操縱語言、數據控制語言。4.2數據庫系統(tǒng)的發(fā)展和基本特點1.數據庫系統(tǒng)的發(fā)展數據管理技術的發(fā)展經歷了3 個階段：人工

44、管理階段、文件系統(tǒng)階段和數據庫系統(tǒng)階段。關于數據管理三個階段中的軟硬件背景及處理特點，簡單概括可見表4-1。表4-1數據管理三個階段的比較人工管理階段文件管理階段數據庫系統(tǒng)管理階段應用目的科學計算科學計算、管理大規(guī)模管理硬件背景無直接存取設備磁盤、磁鼓大容量磁盤軟件背景無操作系統(tǒng)有文件系統(tǒng)有數據庫管理系統(tǒng)背景處理方式批處理聯機實時處理、批處理分布處理、聯機實時處理和批處理二級公共基礎知識速學教程23數據管理者人文件系統(tǒng)數據庫管理系統(tǒng)數據面向的對象某個應用程序某個應用程序現實世界數據共享程度無共享，冗余度大共享性差，冗余度大共享性大，冗余度小數據的獨立性不獨立，完全依賴于程序獨立性差具有高度的物

45、理獨立性和一定的邏輯獨立性數據的結構化無結構記錄內有結構，整體無結構整體結構化，用數據模型描述特點數據控制能力由應用程序控制應用程序控制由DBMS 提供數據安全性、完整性、并發(fā)控制和恢復2.數據庫系統(tǒng)的特點數據獨立性是數據與程序間的互不依賴性，即數據庫中的數據獨立于應用程序而不依賴于應用程序。數據的獨立性一般分為物理獨立性與邏輯獨立性兩種。物理獨立性：當數據的物理結構（包括存儲結構、存取方式等）改變時，如存儲設備的更換、物理存儲的更換、存取方式改變等，應用程序都不用改變。邏輯獨立性：數據的邏輯結構改變了，如修改數據模式、增加新的數據類型、改變數據間聯系等，用戶程序都可以不變。4.3數據庫系統(tǒng)的

46、內部體系結構1.數據統(tǒng)系統(tǒng)的3級模式概念模式，也稱邏輯模式，是對數據庫系統(tǒng)中全局數據邏輯結構的描述，是全體用戶（應用）公共數據視圖。一個數據庫只有一個概念模式；外模式，外模式也稱子模式，它是數據庫用戶能夠看見和使用的局部數據的邏輯結構和特征的描述，它是由概念模式推導而出來的，是數據庫用戶的數據二級公共基礎知識速學教程24視圖，是與某一應用有關的數據的邏輯表示。一個概念模式可以有若干個外模式；內模式，內模式又稱物理模式，它給出了數據庫物理存儲結構與物理存取方法。內模式處于最底層，它反映了數據在計算機物理結構中的實際存儲形式，概念模式處于中間層，它反映了設計者的數據全局邏輯要求，而外模式處于最外層

47、，它反映了用戶對數據的要求。2.數據庫系統(tǒng)的兩級映射兩級映射保證了數據庫系統(tǒng)中數據的獨立性。概念模式到內模式的映射。該映射給出了概念模式中數據的全局邏輯結構到數據的物理存儲結構間的對應關系；外模式到概念模式的映射。概念模式是一個全局模式而外模式是用戶的局部模式。一個概念模式中可以定義多個外模式，而每個外模式是概念模式的一個基本視圖。4.4數據模型的基本概念數據模型從抽象層次上描述了數據庫系統(tǒng)的靜態(tài)特征、動態(tài)行為和約束條件，因此數據模型通常由數據結構、數據操作及數據約束三部分組成。數據庫管理系統(tǒng)所支持的數據模型分為3 種：層次模型、網狀模型和關系模型。數據模型特點見表4-2。表4-2 各種數據模型的特點發(fā)展階段主要特點層次模型用樹形結構表示實體及其之間聯系的模型稱為層次模型，上級結點與下級結點之間為一對多的聯系網狀模型用網狀結構表示實體及其之間聯系的模型稱為網狀模型，網中的每一個結點代表一個實體類型，允許結點有多于一個的父結點，可以有一個以上的結點沒有父結點關系模型用二維表結構來表示實體以及實體之間聯系的模型稱為關系模型，在關系模型中把數據看成是二維表中的元素，一張二維表就是一個關系二級公共