全國計(jì)算機(jī)二級內(nèi)容學(xué)習(xí)

1、-.數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法一、基本概念：一、基本概念：數(shù)數(shù)據(jù)據(jù)(data)(data)：信息的載體，能夠被計(jì)算機(jī)：信息的載體，能夠被計(jì)算機(jī)識別、存儲和加工處理的物理符號。包括識別、存儲和加工處理的物理符號。包括文本類型的數(shù)據(jù)文本類型的數(shù)據(jù)( (如：字母、數(shù)字、漢字如：字母、數(shù)字、漢字) )和多媒體類型的數(shù)據(jù)和多媒體類型的數(shù)據(jù)( (如：如：聲音、聲音、動(dòng)畫、動(dòng)畫、圖圖像像) )。數(shù)數(shù)據(jù)元素?fù)?jù)元素(data element)(data element)：是數(shù)據(jù)的基本單：是數(shù)據(jù)的基本單位，位，有時(shí)也稱為元素、有時(shí)也稱為元素、結(jié)點(diǎn)、結(jié)點(diǎn)、頂點(diǎn)、頂點(diǎn)、記錄，記錄，可以有若干個(gè)數(shù)據(jù)項(xiàng)（字段、域、屬性

2、）可以有若干個(gè)數(shù)據(jù)項(xiàng)（字段、域、屬性）組成。組成。數(shù)數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)（data structuredata structure） ：指的是數(shù)據(jù)之指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。其包間的相互關(guān)系，即數(shù)據(jù)的組織形式。其包括三個(gè)部分：括三個(gè)部分：.-可修編-.-.1 1、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系、邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系2 2、存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算、存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器的表示。機(jī)存儲器的表示。3 3、數(shù)據(jù)的運(yùn)算（算法）、數(shù)據(jù)的運(yùn)算（算法） ：即對數(shù)據(jù)施加的：即對數(shù)據(jù)施加的操作操作數(shù)數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：據(jù)的邏輯結(jié)構(gòu)有兩大類：1 1、線性結(jié)構(gòu)

3、：、線性結(jié)構(gòu)：特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)特征是：若結(jié)構(gòu)是非空集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最并且所有結(jié)點(diǎn)最多只有一個(gè)直接前趨和一個(gè)直接后繼。多只有一個(gè)直接前趨和一個(gè)直接后繼。例：一維數(shù)組、鏈表、棧、隊(duì)列、串例：一維數(shù)組、鏈表、棧、隊(duì)列、串2 2、非線性結(jié)構(gòu)：、非線性結(jié)構(gòu)：特征是：特征是：一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。接后繼。.-可修編-.-.例：多維數(shù)組、廣義表、樹、圖例：多維數(shù)組、廣義表、樹、圖數(shù)數(shù)據(jù)的存儲結(jié)構(gòu)有以下基本存儲方法：據(jù)的存儲結(jié)構(gòu)有以下基本存儲方法：1 1、順序存儲方法：、順序存儲方

4、法：該方法是將邏輯上相鄰的結(jié)點(diǎn)存儲在物理該方法是將邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置上相鄰的存儲單元里，位置上相鄰的存儲單元里，結(jié)點(diǎn)間的邏輯關(guān)結(jié)點(diǎn)間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，系由存儲單元的鄰接關(guān)系來體現(xiàn)，一般通過一般通過數(shù)組來實(shí)現(xiàn)的。數(shù)組來實(shí)現(xiàn)的。2 2、存儲方法：、存儲方法：該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。通過指針類型來實(shí)現(xiàn)的。指針字段表示的。通過指針類型來實(shí)現(xiàn)的。3 3、索引存儲方法：、索引存儲方法：該方法通常是在存儲結(jié)點(diǎn)信息的同時(shí)，該方法通常是在存儲

5、結(jié)點(diǎn)信息的同時(shí)，還建還建立附加的索引表，立附加的索引表，索引表中的每一項(xiàng)稱為索索引表中的每一項(xiàng)稱為索.-可修編-.-.引項(xiàng)，引項(xiàng)， 索引項(xiàng)的一般形式是：索引項(xiàng)的一般形式是：關(guān)鍵字，關(guān)鍵字， 地址。地址。4 4、散列存儲方法：、散列存儲方法：該方法的基本思想是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直該方法的基本思想是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲地址，接計(jì)算出該結(jié)點(diǎn)的存儲地址，通過散列函數(shù)通過散列函數(shù)實(shí)現(xiàn)。例：除余法散列函數(shù)、相乘取整法散實(shí)現(xiàn)。例：除余法散列函數(shù)、相乘取整法散列函數(shù)列函數(shù)算算法的基本特征：法的基本特征：1 1、可行性、可行性(effectiveness)(effectiveness)：針對實(shí)際

6、問題而：針對實(shí)際問題而設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。設(shè)計(jì)的算法，執(zhí)行后能夠得到滿意的結(jié)果。2 2、確定性、確定性(definiteness)(definiteness)：算法中的每一個(gè)步：算法中的每一個(gè)步驟都必須有明確的定義，不允許出現(xiàn)歧義驟都必須有明確的定義，不允許出現(xiàn)歧義性。性。3 3、有窮性有窮性(finiteness)(finiteness)：算法必須在有限時(shí)間算法必須在有限時(shí)間做完，即必須在執(zhí)行有限個(gè)步驟之后終止。做完，即必須在執(zhí)行有限個(gè)步驟之后終止。.-可修編-.-.時(shí)時(shí)間復(fù)雜度：該算法執(zhí)行的時(shí)間耗費(fèi)，它間復(fù)雜度：該算法執(zhí)行的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模是該算法所求解

7、問題規(guī)模 n n 的函數(shù)。的函數(shù)?？湛臻g復(fù)雜度：間復(fù)雜度：該算法執(zhí)行時(shí)所耗費(fèi)的存儲該算法執(zhí)行時(shí)所耗費(fèi)的存儲空間，它也是問題規(guī)?？臻g，它也是問題規(guī)模 n n 的函數(shù)。的函數(shù)。二、線性表：二、線性表：線線性表性表(linear list)(linear list)： 是由是由 n(n=0)n(n=0)個(gè)數(shù)據(jù)元個(gè)數(shù)據(jù)元素素( (結(jié)點(diǎn)結(jié)點(diǎn))a )a1 1,a ,a2 2,a ,a3 3, , ,a ,an n組成的有限序組成的有限序列。對于非空的線性表，有且僅有一個(gè)開列。對于非空的線性表，有且僅有一個(gè)開始結(jié)點(diǎn)始結(jié)點(diǎn) a a1 1，它沒有直接前趨；有且僅有一，它沒有直接前趨；有且僅有一個(gè)終端結(jié)點(diǎn)個(gè)終端結(jié)

8、點(diǎn) a an n，它沒有直接后繼；其余的，它沒有直接后繼；其余的結(jié)點(diǎn)有且僅有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)。直接后繼結(jié)點(diǎn)。線線性表的存儲結(jié)構(gòu)：性表的存儲結(jié)構(gòu)：.-可修編-.-.1 1、順序存儲、順序存儲(sequential list)(sequential list)：將線性表的結(jié)：將線性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲單元里，存儲單元里，用這種方法存儲的線性表稱為用這種方法存儲的線性表稱為順序表。順序表。2 2、鏈?zhǔn)酱鎯?、鏈?zhǔn)酱鎯?linked(linked list)list)：邏輯上相鄰的結(jié)：邏輯上

9、相鄰的結(jié)點(diǎn)，點(diǎn)， 物理上也相鄰，物理上也相鄰， 存儲單元可以是連續(xù)的，存儲單元可以是連續(xù)的，也可以是不連續(xù)的，也可以是不連續(xù)的，在存儲每個(gè)結(jié)點(diǎn)值的同在存儲每個(gè)結(jié)點(diǎn)值的同時(shí)，還存儲指向其后繼結(jié)點(diǎn)的地址，用這種時(shí)，還存儲指向其后繼結(jié)點(diǎn)的地址，用這種方法存儲的線性表稱為鏈表。方法存儲的線性表稱為鏈表。常常見的運(yùn)算有：見的運(yùn)算有：表的初始化、求表的長度、取表中的第表的初始化、求表的長度、取表中的第 i i 個(gè)個(gè)結(jié)點(diǎn)、結(jié)點(diǎn)、 查找結(jié)點(diǎn)、查找結(jié)點(diǎn)、 插入新的結(jié)點(diǎn)、插入新的結(jié)點(diǎn)、刪除結(jié)點(diǎn)。刪除結(jié)點(diǎn)。順順序表和鏈表的比較：序表和鏈表的比較：1 1、基于空間的考慮：、基于空間的考慮：.-可修編-.-.a a、順

10、序表的存儲空間是靜態(tài)分配的，而鏈、順序表的存儲空間是靜態(tài)分配的，而鏈表的存儲空間是動(dòng)態(tài)分配的。表的存儲空間是動(dòng)態(tài)分配的。b b、順序表占的存儲空間必須是連續(xù)的，而、順序表占的存儲空間必須是連續(xù)的，而鏈表占的存儲空間可以是連續(xù)的，鏈表占的存儲空間可以是連續(xù)的，也可是不也可是不連續(xù)的連續(xù)的c c、順序表存儲密度為、順序表存儲密度為 1 1，而鏈表中的每個(gè)，而鏈表中的每個(gè)結(jié)點(diǎn)，除了數(shù)據(jù)域外，還要額外的設(shè)置指針結(jié)點(diǎn)，除了數(shù)據(jù)域外，還要額外的設(shè)置指針域，存儲密度小于域，存儲密度小于 1 12 2、基于時(shí)間的考慮：、基于時(shí)間的考慮：a a、 在鏈表中的任何位置上進(jìn)行插入和刪除，在鏈表中的任何位置上進(jìn)行插入

11、和刪除，只需要修改指針，只需要修改指針，而順序表中平均將要移動(dòng)而順序表中平均將要移動(dòng)近一半的結(jié)點(diǎn)。近一半的結(jié)點(diǎn)。b b、順序表是隨機(jī)存取結(jié)構(gòu)，它的存取時(shí)間、順序表是隨機(jī)存取結(jié)構(gòu)，它的存取時(shí)間為為 o(1)o(1)，而鏈表需從頭結(jié)點(diǎn)順著鏈掃描鏈，而鏈表需從頭結(jié)點(diǎn)順著鏈掃描鏈表。表。.-可修編-.-.總之，當(dāng)線性表的長度變化不大，易于事先總之，當(dāng)線性表的長度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲空間，宜采用確定其大小時(shí)，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)；順序表作為存儲結(jié)構(gòu)；當(dāng)線性表的長度變化當(dāng)線性表的長度變化較大，難以估計(jì)其存儲規(guī)模時(shí)，以采用鏈表較大，難以估計(jì)其存儲規(guī)模時(shí)，以采用鏈

12、表作為存儲結(jié)構(gòu)為好。作為存儲結(jié)構(gòu)為好。若線性表的操作主要是若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲結(jié)構(gòu)為宜；順序表做存儲結(jié)構(gòu)為宜；對于頻繁進(jìn)行插入對于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲結(jié)構(gòu)。和刪除的線性表，宜采用鏈表做存儲結(jié)構(gòu)。例：關(guān)于線性表的描述中，錯(cuò)誤的是（例：關(guān)于線性表的描述中，錯(cuò)誤的是（）a a、線性表是線性結(jié)構(gòu)、線性表是線性結(jié)構(gòu)b b、線性表的順、線性表的順序存儲結(jié)構(gòu)，序存儲結(jié)構(gòu)，必須占用一片連續(xù)的存儲單元必須占用一片連續(xù)的存儲單元c c、線性表是單鏈表線性表是單鏈表d d、線性表的鏈?zhǔn)骄€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

13、，不必占用一片連續(xù)的存儲單元存儲結(jié)構(gòu)，不必占用一片連續(xù)的存儲單元.-可修編-.-.用數(shù)組表示線性表的優(yōu)點(diǎn)是（用數(shù)組表示線性表的優(yōu)點(diǎn)是（）a a、便于插入和刪除操作、便于插入和刪除操作b b、便、便于隨機(jī)存取于隨機(jī)存取c c、可以動(dòng)態(tài)地分配存儲空間、可以動(dòng)態(tài)地分配存儲空間d d、不、不需要占用一片連續(xù)的存儲空間需要占用一片連續(xù)的存儲空間三、棧：三、棧：棧棧(stack)(stack)：是限制僅在表的一端進(jìn)行插入：是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂?shù)倪@一端為棧頂 (top)(top)，另一端稱為棧底，另一端稱為棧底(bo

14、ttom)(bottom)。當(dāng)表中沒有元素時(shí)稱為空棧。當(dāng)表中沒有元素時(shí)稱為空棧。是一種后進(jìn)先出的線性表，又稱為是一種后進(jìn)先出的線性表，又稱為lifolifo表。表。棧棧的基本運(yùn)算有：的基本運(yùn)算有：棧的初始化、判棧空、判棧滿、進(jìn)棧、出棧的初始化、判?？?、判棧滿、進(jìn)棧、出.-可修編-.-.棧等棧等棧棧的存儲：的存儲：順序存儲、鏈?zhǔn)酱鎯樞虼鎯?、鏈?zhǔn)酱鎯豪喝暨M(jìn)棧的輸入序列是若進(jìn)棧的輸入序列是 a a、b b、c c、d d、e e，并且在它們進(jìn)棧的過程中可以進(jìn)行出棧操并且在它們進(jìn)棧的過程中可以進(jìn)行出棧操作，則不可能出現(xiàn)的出棧序列是（作，則不可能出現(xiàn)的出棧序列是（）a a、edcbaedcbab

15、 b、decbadecbac c、dceabdceabd d、abcdeabcde四、隊(duì)列：四、隊(duì)列：隊(duì)隊(duì)列列(queue)(queue)：也是一種運(yùn)算受限的線性：也是一種運(yùn)算受限的線性表，它只允許在表的一端進(jìn)行插入，而在表，它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。另一端進(jìn)行刪除。允許刪除的一段稱為隊(duì)允許刪除的一段稱為隊(duì)頭頭(front)(front) ，允允許許插插入入的的一一段段稱稱為為隊(duì)隊(duì)尾尾.-可修編-.-.(rear)(rear)。 （類似于生活中的購物排隊(duì)）（類似于生活中的購物排隊(duì)）。是。是一種先進(jìn)先出的線性表，又稱為一種先進(jìn)先出的線性表，又稱為 fifofifo 表。表。

16、隊(duì)隊(duì)列的基本運(yùn)算：列的基本運(yùn)算：隊(duì)列的初始化、判隊(duì)空、判隊(duì)滿、入隊(duì)、隊(duì)列的初始化、判隊(duì)空、判隊(duì)滿、入隊(duì)、出隊(duì)出隊(duì)隊(duì)隊(duì)列的存儲實(shí)現(xiàn)：列的存儲實(shí)現(xiàn)：順序存儲、鏈?zhǔn)酱鎯樞虼鎯Α㈡準(zhǔn)酱鎯阂粋€(gè)隊(duì)列的入隊(duì)序列是例：一個(gè)隊(duì)列的入隊(duì)序列是 1 1，2 2，3 3，4 4，則隊(duì)列的輸出序列是則隊(duì)列的輸出序列是 （）a a、4 4，3 3，2 2，1 1b b、1 1，2 2，3 3，4 4c c、1 1，4 4，3 3，2 2d d、3 3，2 2，4 4，1 1五、串：五、串：串串(string)(string)： 是零個(gè)或多個(gè)字符組成的有限是零個(gè)或多個(gè)字符組成的有限.-可修編-.-.序列。序列。串中所

17、包含的字符個(gè)數(shù)稱為該串的長度。串中所包含的字符個(gè)數(shù)稱為該串的長度。串中任意個(gè)連續(xù)字符組成的子序列稱為串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，該串的子串，包含子串的串相應(yīng)地稱為主串包含子串的串相應(yīng)地稱為主串注：空串是任意串的子串，任意串是其自注：空串是任意串的子串，任意串是其自身的子串身的子串串串有串常量、串變量之分：有串常量、串變量之分：1 1、串常量在程序中只能被引用但不能改、串常量在程序中只能被引用但不能改變其值，即只能讀不能寫。變其值，即只能讀不能寫。2 2、串變量其值是可以改變的。、串變量其值是可以改變的。串串的基本運(yùn)算：的基本運(yùn)算：求串長、串復(fù)制、串聯(lián)接、串比較、字符求串長、串

18、復(fù)制、串聯(lián)接、串比較、字符定位、定位、六、樹（非線性結(jié)構(gòu)）六、樹（非線性結(jié)構(gòu)）：.-可修編-.-.樹樹(tree)(tree)：是：是 n(n=0)n(n=0)個(gè)結(jié)點(diǎn)的有限集個(gè)結(jié)點(diǎn)的有限集 t t，t(n=0)t(n=0)為空時(shí)稱為空樹，否則它滿足如下為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：兩個(gè)條件：1 1、有且僅有一個(gè)特定的稱為根有且僅有一個(gè)特定的稱為根(root)(root)的結(jié)的結(jié)點(diǎn)點(diǎn)2 2、其余的結(jié)點(diǎn)可分為、其余的結(jié)點(diǎn)可分為 m(m=0)m(m=0)個(gè)互不相個(gè)互不相交的子集交的子集 t1t1，t2t2，. .，tmtm，其中每，其中每個(gè)子集本身又是一棵樹，并稱其為根的個(gè)子集本身又是一棵

19、樹，并稱其為根的子樹子樹(subtree)(subtree)。在在樹的樹形圖表示中，樹的樹形圖表示中，結(jié)點(diǎn)通常是用圓圈結(jié)點(diǎn)通常是用圓圈表示的，結(jié)點(diǎn)的名字一般是寫在圓圈旁表示的，結(jié)點(diǎn)的名字一般是寫在圓圈旁邊，有時(shí)亦可寫在圓圈。邊，有時(shí)亦可寫在圓圈。度度(degree)(degree)：一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為：一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度。該結(jié)點(diǎn)的度。一棵樹的度是指該樹中結(jié)點(diǎn)一棵樹的度是指該樹中結(jié)點(diǎn)的最大度數(shù)。的最大度數(shù)。.-可修編-.-.葉葉子子(leaf)(leaf)： 度為零的結(jié)點(diǎn)稱為葉子或終端度為零的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)結(jié)點(diǎn)分分支結(jié)點(diǎn)支結(jié)點(diǎn)(node)(node)：度不為零的結(jié)點(diǎn)

20、稱為分：度不為零的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。支結(jié)點(diǎn)。樹樹中某個(gè)結(jié)點(diǎn)的子樹之根稱為該結(jié)點(diǎn)的中某個(gè)結(jié)點(diǎn)的子樹之根稱為該結(jié)點(diǎn)的孩子孩子(child)(child)結(jié)點(diǎn)或子結(jié)點(diǎn)，相應(yīng)的該結(jié)點(diǎn)結(jié)點(diǎn)或子結(jié)點(diǎn)，相應(yīng)的該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親稱為孩子結(jié)點(diǎn)的雙親(parents)(parents)結(jié)點(diǎn)或父結(jié)結(jié)點(diǎn)或父結(jié)點(diǎn)。點(diǎn)。同同一個(gè)雙親的孩子稱為兄弟結(jié)點(diǎn)一個(gè)雙親的孩子稱為兄弟結(jié)點(diǎn)(sibling)(sibling)結(jié)結(jié)點(diǎn)的層數(shù)點(diǎn)的層數(shù) (level)(level)是從根起算是從根起算 , ,設(shè)根的層設(shè)根的層數(shù)為數(shù)為 1, 1,其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加的層數(shù)加 1. 1.樹樹 中中

21、 結(jié)結(jié) 點(diǎn)點(diǎn) 的的 最最 大大 層層 數(shù)數(shù) 稱稱 為為 樹樹 的的 高高 度度(height)(height)或深度或深度(depth).(depth).森森林林(forest)(forest)： 是是 m(m=0)m(m=0)棵互不相交的樹棵互不相交的樹.-可修編-.-.的集合。刪去一棵樹的根，就得到一個(gè)森的集合。刪去一棵樹的根，就得到一個(gè)森林，反之，加上一個(gè)結(jié)點(diǎn)作樹根，森林就林，反之，加上一個(gè)結(jié)點(diǎn)作樹根，森林就變?yōu)橐豢脴?。變?yōu)橐豢脴?。二二叉樹叉?binary(binary tree)tree)：是：是 n(n=0)n(n=0)個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的有限集，有限集，它或者是空集它或者是空集(n=

22、0)(n=0)，或者由一個(gè)或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、根結(jié)點(diǎn)及兩棵互不相交的、分別稱作這個(gè)分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。根的左子樹和右子樹的二叉樹組成。二叉樹中，每個(gè)結(jié)點(diǎn)最多只能有兩棵子二叉樹中，每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹，并且有左右之分。樹，并且有左右之分。二二叉樹的五種基本形態(tài)：叉樹的五種基本形態(tài)：例：具有例：具有 3 3 個(gè)結(jié)點(diǎn)的二叉樹有幾種形態(tài)。個(gè)結(jié)點(diǎn)的二叉樹有幾種形態(tài)。滿滿二叉樹二叉樹(full(full binarybinary tree)tree)：一棵深度為：一棵深度為 k k且有且有 2 2 -1-1 個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹.

23、-可修編-.k k-.完完全二叉樹全二叉樹(plete binary tree)(plete binary tree)： 若一棵二叉若一棵二叉樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)樹至多只有最下面的兩層上結(jié)點(diǎn)的度數(shù)可以小于可以小于 2 2，并且最下一層上的結(jié)點(diǎn)都集，并且最下一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，中在該層最左邊的若干位置上，則此二叉則此二叉樹稱為完全二叉樹。樹稱為完全二叉樹。二叉樹的性質(zhì)：二叉樹的性質(zhì)：性質(zhì)性質(zhì) 1 1：二叉樹第：二叉樹第 i i 層上的結(jié)點(diǎn)數(shù)目最多為層上的結(jié)點(diǎn)數(shù)目最多為2 2 (i=1)(i=1)性質(zhì)性質(zhì) 2 2：深度為：深度為k k 的二叉樹至多有的二叉樹至

24、多有 2 2 -1-1 個(gè)結(jié)個(gè)結(jié)點(diǎn)點(diǎn)(k=1)(k=1)性質(zhì)性質(zhì) 3 3：在任意一棵二叉樹中，若終端結(jié)點(diǎn)：在任意一棵二叉樹中，若終端結(jié)點(diǎn)的個(gè)數(shù)為的個(gè)數(shù)為n n0 0， 度為度為2 2的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為n n2 2， 則則n n0 0=n=n2 2+1+1性質(zhì)性質(zhì) 4 4：具有：具有 n n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度個(gè)結(jié)點(diǎn)的完全二叉樹的深度為為lgn+1(lgn+1(取下整取下整) ) 或或 lg(n+1)(lg(n+1)(取上整取上整) )。.-可修編-.i-1i-1k k-.例：一棵二叉樹的結(jié)點(diǎn)數(shù)為例：一棵二叉樹的結(jié)點(diǎn)數(shù)為 1818 個(gè)，求它的個(gè)，求它的最小高度最小高度已知度為已知度為 2

25、 2 的結(jié)點(diǎn)數(shù)為的結(jié)點(diǎn)數(shù)為 1515 個(gè)，求葉子結(jié)個(gè)，求葉子結(jié)點(diǎn)數(shù)點(diǎn)數(shù)二叉樹的遍歷：二叉樹的遍歷：遍遍歷歷(traversal)(traversal)：是指沿著某條搜索路線，：是指沿著某條搜索路線，依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。次訪問。前序遍歷：前序遍歷： （又稱為先序遍歷、先根遍歷）（又稱為先序遍歷、先根遍歷）若二叉樹為空，則執(zhí)行空操作。否則：若二叉樹為空，則執(zhí)行空操作。否則：1 1、訪問根結(jié)點(diǎn)；、訪問根結(jié)點(diǎn)；2 2、前序遍歷左子樹；、前序遍歷左子樹；3 3、前序遍歷右子樹。、前序遍歷右子樹。.-可修編-.-.中序遍歷：中序遍歷： （又稱為中根遍

26、歷）（又稱為中根遍歷）若二叉樹為空，則執(zhí)行空操作。否則：若二叉樹為空，則執(zhí)行空操作。否則：1 1、中序遍歷左子樹；、中序遍歷左子樹；2 2、訪問根結(jié)點(diǎn)；、訪問根結(jié)點(diǎn)；3 3、中序遍歷右子樹。、中序遍歷右子樹。后序遍歷：后序遍歷： （又稱為后根遍歷）（又稱為后根遍歷）若二叉樹為空，則執(zhí)行空操作。否則：若二叉樹為空，則執(zhí)行空操作。否則：1 1、后序遍歷左子樹；、后序遍歷左子樹；2 2、后序遍歷右子樹；、后序遍歷右子樹；3 3、訪問根結(jié)點(diǎn)。、訪問根結(jié)點(diǎn)。例：已知一棵二叉樹的中序遍歷序列是：例：已知一棵二叉樹的中序遍歷序列是：fdgbachefdgbache，其后序遍歷序列是：，其后序遍歷序列是：fg

27、dbhecafgdbheca求其前序遍歷序列。求其前序遍歷序列。一棵二叉樹的前序遍歷序列為一棵二叉樹的前序遍歷序列為 abdgcfkabdgcfk，.-可修編-.-.中序遍歷序列為中序遍歷序列為 dgbafckdgbafck， 則結(jié)點(diǎn)的后序遍則結(jié)點(diǎn)的后序遍歷序列是（歷序列是（）a a、 acfkdbgacfkdbgb b、 gdbfkcagdbfkcac c、kcfagdbkcfagdbd d、abcdfkgabcdfkg七、排序七、排序(sort)(sort)：所所謂排序，就是指整理文件中的記錄，使謂排序，就是指整理文件中的記錄，使之按關(guān)鍵字遞增之按關(guān)鍵字遞增 （或遞減）（或遞減） 次序排列

28、起來。次序排列起來。冒冒泡排序泡排序(bubble sorting)(bubble sorting)：通過對待排序序列從后向前或從前向后通過對待排序序列從后向前或從前向后( (從下標(biāo)較大的元素開始從下標(biāo)較大的元素開始) )，依次比較相鄰元，依次比較相鄰元素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼素的排序碼，若發(fā)現(xiàn)逆序則交換，使排序碼較大的元素逐漸從前部移向后部或較小的較大的元素逐漸從前部移向后部或較小的元素逐漸從后部移向前部元素逐漸從后部移向前部（從下標(biāo)較大的單（從下標(biāo)較大的單元移向下標(biāo)較小的單元）元移向下標(biāo)較小的單元） 。.-可修編-.-.直直接選擇排序接選擇排序(selection sorti

29、ng)(selection sorting)：掃描整個(gè)線性表，從中選出最小的元素，掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面；將它交換到表的最前面；然后對剩下的子表然后對剩下的子表采用同樣的方法，直到子表空為止。采用同樣的方法，直到子表空為止。直直接插入排序接插入排序(insertion sorting)(insertion sorting)：每次將一個(gè)待排序的記錄，每次將一個(gè)待排序的記錄，按其關(guān)鍵字大按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。當(dāng)位置，直到全部記錄插入完成為止。快快速排序速排序(quick

30、 sorting)(quick sorting)：任取待排序序列任取待排序序列中的某個(gè)元素作為基準(zhǔn)中的某個(gè)元素作為基準(zhǔn) ( (一般取第一個(gè)元一般取第一個(gè)元素素) )， 通過一趟排序，通過一趟排序，將待排元素分為左右將待排元素分為左右兩個(gè)子序列，左子序列元素的排序碼均小兩個(gè)子序列，左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分排序碼則大于基準(zhǔn)元素的排序碼，然后分別對兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)別對兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè).-可修編-.-.序列有序。序列有序。各種部排序方法的比較各種部排序方法的比較排

31、排序序方方法法直直接接插插入入直直接接選選擇擇o(no(n ) )2 2時(shí)間復(fù)雜度時(shí)間復(fù)雜度最好時(shí)最好時(shí)間間平均時(shí)平均時(shí)間間最壞時(shí)最壞時(shí)間間空間復(fù)空間復(fù)雜度雜度o(n)o(n)o(no(n ) )2 2o(no(n ) )2 2o(1)o(1)o(no(n ) )2 2o(no(n ) )2 2o(1)o(1).-可修編-.-.冒冒泡泡快快速速o(n)o(n)o(no(n ) )2 2o(no(n ) )2 2o(1)o(1)o(nlgn)o(nlgn)o(nlgn)o(nlgn)o(no(n ) )2 2o(lgn)o(lgn)o(1)o(1)堆堆o(nlgn)o(nlgn)o(nlgn)o

32、(nlgn)o(nlgn)o(nlgn)例：例：對一個(gè)具有對一個(gè)具有 n n 個(gè)元素的序列進(jìn)行冒泡排個(gè)元素的序列進(jìn)行冒泡排序，在最壞情況下，要進(jìn)行交換的次數(shù)是序，在最壞情況下，要進(jìn)行交換的次數(shù)是（）a a、 n(n+1)/2n(n+1)/2b b、 n(n-1)/2n(n-1)/2c c、 n*n/2n*n/2d d、n(n+1)/2-1n(n+1)/2-1對對 n n 個(gè)元素進(jìn)行冒泡排序過程中，個(gè)元素進(jìn)行冒泡排序過程中，最好情最好情況下的時(shí)間復(fù)雜性為（況下的時(shí)間復(fù)雜性為（）a a、 o(1)o(1)b b、 o(logo(log2 2n)n)c c、 o(no(n ) )d d、o(n)o(

33、n).-可修編-.2 2-.對對 n n 個(gè)元素進(jìn)行快速排序的過程中，個(gè)元素進(jìn)行快速排序的過程中，平均平均情況下的時(shí)間復(fù)雜性為（情況下的時(shí)間復(fù)雜性為（）a a、 o(1)o(1)b b、 o(lgn)o(lgn)c c、 o(no(n ) )d d、o(nlgn)o(nlgn)2 2八、查找八、查找(searching)(searching)：所所謂查找是指給定一個(gè)值謂查找是指給定一個(gè)值 k k，在含有，在含有 n n 個(gè)個(gè)結(jié)點(diǎn)的表中找出關(guān)鍵字等于給定值結(jié)點(diǎn)的表中找出關(guān)鍵字等于給定值 k k的結(jié)的結(jié)點(diǎn)。若找到，則查找成功，返回該結(jié)點(diǎn)的點(diǎn)。若找到，則查找成功，返回該結(jié)點(diǎn)的信息或該結(jié)點(diǎn)在表中的位置

34、；信息或該結(jié)點(diǎn)在表中的位置；否則查找失否則查找失敗，返回相關(guān)的提示信息。敗，返回相關(guān)的提示信息。順順序查找序查找 (sequential(sequential search)search)的基本思想的基本思想是：從表的一端開始，順序掃描線性表，是：從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值 k k相相比較，比較，若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與若當(dāng)前掃描到的結(jié)點(diǎn)關(guān)鍵字與 k k 相相.-可修編-.-.等，則查找成功；若掃描結(jié)束后，仍未找等，則查找成功；若掃描結(jié)束后，仍未找到關(guān)鍵字等于到關(guān)鍵字等于 k k 的結(jié)點(diǎn)，則查找失敗。順的結(jié)點(diǎn)，則查找失敗。

35、順序查找即適用順序存儲結(jié)構(gòu)，序查找即適用順序存儲結(jié)構(gòu)，又適用鏈?zhǔn)接诌m用鏈?zhǔn)酱鎯Y(jié)構(gòu)。存儲結(jié)構(gòu)。查找成功的平均查找長度為：查找成功的平均查找長度為：(n(n 為結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)目目) )(1+2+3+4+(1+2+3+4+ +n) / n = (n+1)/2+n) / n = (n+1)/2二二分查找分查找(binary search)(binary search)又稱折半查找，又稱折半查找， 它它是一種效率較高的查找方法，是一種效率較高的查找方法，二分查找要二分查找要求線性表是有序表，求線性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字即表中結(jié)點(diǎn)按關(guān)鍵字有序，并且要用向量作為表的存儲結(jié)構(gòu)。有序，并且要用向量作為

36、表的存儲結(jié)構(gòu)。另外，二分查找只適用順序存儲結(jié)構(gòu)，在另外，二分查找只適用順序存儲結(jié)構(gòu)，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上無法實(shí)現(xiàn)二分查找。鏈?zhǔn)酱鎯Y(jié)構(gòu)上無法實(shí)現(xiàn)二分查找。查找成功時(shí)的平均查找長度：查找成功時(shí)的平均查找長度：(n(n 為結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù).-可修編-.-.目目) )n 1lg(n 1)1n當(dāng)當(dāng) n n 很大時(shí)，很大時(shí)， 可用近似公式：可用近似公式：lg(n+1)-1lg(n+1)-1表示表示軟件工程基礎(chǔ)軟件工程基礎(chǔ)一、基本概念：一、基本概念：軟軟件件(software)(software)：軟件是一種產(chǎn)品：軟件是一種產(chǎn)品 ( (邏輯產(chǎn)邏輯產(chǎn)品品) )， 指的是計(jì)算機(jī)中程序及其說明程序的指的是計(jì)算機(jī)中程序

37、及其說明程序的各種文檔。各種文檔。 “程序”是計(jì)算任務(wù)的處理對“程序”是計(jì)算任務(wù)的處理對象和處理規(guī)則的描述；象和處理規(guī)則的描述； “文檔”是有關(guān)計(jì)“文檔”是有關(guān)計(jì)算機(jī)程序功能、設(shè)計(jì)、編制、使用的文字算機(jī)程序功能、設(shè)計(jì)、編制、使用的文字.-可修編-.-.或圖形資料。或圖形資料。軟軟件危機(jī)的表現(xiàn)：件危機(jī)的表現(xiàn)：1 1、軟件需求的增長得不到滿足、軟件需求的增長得不到滿足2 2、軟件開發(fā)成本和進(jìn)度無法控制、軟件開發(fā)成本和進(jìn)度無法控制3 3、軟件質(zhì)量難以保證、軟件質(zhì)量難以保證4 4、軟件不可維護(hù)或維護(hù)程度非常低、軟件不可維護(hù)或維護(hù)程度非常低5 5、軟件成本不斷提高、軟件成本不斷提高6 6、軟件開發(fā)生產(chǎn)效

38、率的提高趕不上硬件、軟件開發(fā)生產(chǎn)效率的提高趕不上硬件的發(fā)展和應(yīng)用需求的增長的發(fā)展和應(yīng)用需求的增長軟軟件工程件工程(software engineering)(software engineering)： 用工程化用工程化的方法、科學(xué)知識和技術(shù)原理來定義、開的方法、科學(xué)知識和技術(shù)原理來定義、開發(fā)、維護(hù)軟件的一門學(xué)科。發(fā)、維護(hù)軟件的一門學(xué)科。軟軟件工程的目標(biāo)：件工程的目標(biāo)：付出較低的開發(fā)成本；付出較低的開發(fā)成本；達(dá)到要求的軟件功達(dá)到要求的軟件功.-可修編-.-.能；取得較好的軟件性能；開發(fā)的軟件易能；取得較好的軟件性能；開發(fā)的軟件易于移植；需要較低的維護(hù)費(fèi)用；能按時(shí)完于移植；需要較低的維護(hù)費(fèi)用；能

39、按時(shí)完成開發(fā)任務(wù)，及時(shí)交付使用；開發(fā)的軟件成開發(fā)任務(wù)，及時(shí)交付使用；開發(fā)的軟件可靠性高?？煽啃愿摺＼涇浖こ萄芯康闹饕菔擒浖_發(fā)技術(shù)件工程研究的主要容是軟件開發(fā)技術(shù)和軟件開發(fā)管理兩個(gè)方面。和軟件開發(fā)管理兩個(gè)方面。軟軟件生存周期：件生存周期：是指一個(gè)軟件從提出開發(fā)是指一個(gè)軟件從提出開發(fā)要求開始直到該軟件報(bào)廢要求開始直到該軟件報(bào)廢( (停止運(yùn)行停止運(yùn)行) )為止為止的整個(gè)時(shí)期。的整個(gè)時(shí)期。軟軟件生存周期模型：件生存周期模型：是描述軟件開發(fā)過程是描述軟件開發(fā)過程中各種活動(dòng)如何執(zhí)行的模型。中各種活動(dòng)如何執(zhí)行的模型。常常用的模型有：瀑布模型、增量模型、螺用的模型有：瀑布模型、增量模型、螺旋模型、噴泉模

40、型、變換模型和基于知識旋模型、噴泉模型、變換模型和基于知識的模型的模型瀑布模型是將軟件生存周期各個(gè)活動(dòng)規(guī)定瀑布模型是將軟件生存周期各個(gè)活動(dòng)規(guī)定.-可修編-.-.為依線性順序連接的若干階段的模型。為依線性順序連接的若干階段的模型。主要主要包括問題定義及可行性分析、項(xiàng)目開發(fā)計(jì)包括問題定義及可行性分析、項(xiàng)目開發(fā)計(jì)劃、劃、需求分析、需求分析、概要設(shè)計(jì)、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、詳細(xì)設(shè)計(jì)、編碼、編碼、測試和維護(hù)幾個(gè)階段。測試和維護(hù)幾個(gè)階段。例：下列描述中正確的是（例：下列描述中正確的是（）a a、程序就是軟件、程序就是軟件不受計(jì)算機(jī)系統(tǒng)的限制不受計(jì)算機(jī)系統(tǒng)的限制c c、軟件既是邏輯實(shí)體，又是物理實(shí)體、軟件既是

41、邏輯實(shí)體，又是物理實(shí)體d d、軟件是程序、數(shù)據(jù)與相關(guān)文、軟件是程序、數(shù)據(jù)與相關(guān)文b b、 軟件開發(fā)軟件開發(fā)檔的集合檔的集合二、軟件可行性研究與項(xiàng)目開發(fā)計(jì)劃：二、軟件可行性研究與項(xiàng)目開發(fā)計(jì)劃：軟軟件可行性研究的目的是用最小的代價(jià)件可行性研究的目的是用最小的代價(jià)在盡可能短的時(shí)間確定該軟件項(xiàng)目是否在盡可能短的時(shí)間確定該軟件項(xiàng)目是否能夠開發(fā)，是否值得去開發(fā)。能夠開發(fā)，是否值得去開發(fā)。.-可修編-.-.可可行性研究的任務(wù)：行性研究的任務(wù)：a a、技術(shù)可行性、技術(shù)可行性b b、經(jīng)濟(jì)可行性、經(jīng)濟(jì)可行性c c、社會可行性（法律可行性）、社會可行性（法律可行性）可可行性研究的具體步驟：行性研究的具體步驟：1 1

42、、確定項(xiàng)目規(guī)模和目標(biāo)、確定項(xiàng)目規(guī)模和目標(biāo)2 2、研究正在運(yùn)行的系統(tǒng)、研究正在運(yùn)行的系統(tǒng)3 3、建立新系統(tǒng)的高層邏輯模型、建立新系統(tǒng)的高層邏輯模型4 4、導(dǎo)出和評價(jià)各種方案、導(dǎo)出和評價(jià)各種方案5 5、推薦可行的方案、推薦可行的方案6 6、編寫可行性研究報(bào)告、編寫可行性研究報(bào)告三、軟件需求分析：三、軟件需求分析：需需求分析是指開發(fā)人員要準(zhǔn)確理解用戶求分析是指開發(fā)人員要準(zhǔn)確理解用戶的要求，進(jìn)行細(xì)致的調(diào)查分析，將用戶非的要求，進(jìn)行細(xì)致的調(diào)查分析，將用戶非.-可修編-.-.形式的需求述轉(zhuǎn)化為完整的需求定義，形式的需求述轉(zhuǎn)化為完整的需求定義，再再由需求定義轉(zhuǎn)換到相應(yīng)的形式功能規(guī)約由需求定義轉(zhuǎn)換到相應(yīng)的形式

43、功能規(guī)約（需求規(guī)格說明）的過程。（需求規(guī)格說明）的過程。需需求分析的基本任務(wù)：求分析的基本任務(wù)：1 1、問題識別、問題識別a a、功能需求、功能需求b b、性能需求、性能需求c c、環(huán)境需求、環(huán)境需求d d、用戶界面需求、用戶界面需求2 2、分析與綜合，導(dǎo)出軟件的邏輯模型、分析與綜合，導(dǎo)出軟件的邏輯模型3 3、編寫文檔、編寫文檔( (需求規(guī)格說明書需求規(guī)格說明書) )需需求分析的方法：求分析的方法：1 1、結(jié)構(gòu)化分析、結(jié)構(gòu)化分析(structured analysis)(structured analysis)：是面向：是面向數(shù)據(jù)流進(jìn)行需求分析的方法。數(shù)據(jù)流進(jìn)行需求分析的方法。sasa 方法利

44、用圖形等半形式化的描述方式方法利用圖形等半形式化的描述方式.-可修編-.-.表達(dá)需求，主要描述工具：表達(dá)需求，主要描述工具：a a、數(shù)據(jù)流圖、數(shù)據(jù)流圖(dfd)(dfd)：是：是 sasa 方法中用于表示方法中用于表示系統(tǒng)邏輯模型的一種工具，系統(tǒng)邏輯模型的一種工具，以圖形的方式描以圖形的方式描繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過程。繪數(shù)據(jù)在系統(tǒng)中流動(dòng)和處理的過程。b b、數(shù)據(jù)字典、數(shù)據(jù)字典(dd)(dd)：用以定義數(shù)據(jù)流圖中的：用以定義數(shù)據(jù)流圖中的各個(gè)成分的具體含義，為系統(tǒng)的分析、設(shè)計(jì)各個(gè)成分的具體含義，為系統(tǒng)的分析、設(shè)計(jì)及維護(hù)提供了有關(guān)元素的一致的定義和詳及維護(hù)提供了有關(guān)元素的一致的定義和詳細(xì)的描述

45、。細(xì)的描述。c c、描述加工邏輯的結(jié)構(gòu)化語言、判定表、描述加工邏輯的結(jié)構(gòu)化語言、判定表、判定樹判定樹2 2、idefidef 方法方法( (是是 icam definitionicam definition 的縮寫的縮寫) )：是一種用于進(jìn)行復(fù)雜系統(tǒng)分析和設(shè)計(jì)的是一種用于進(jìn)行復(fù)雜系統(tǒng)分析和設(shè)計(jì)的方法，方法，是在結(jié)構(gòu)化分析和設(shè)計(jì)技術(shù)的基礎(chǔ)上是在結(jié)構(gòu)化分析和設(shè)計(jì)技術(shù)的基礎(chǔ)上提出來的。提出來的。3 3、面向?qū)ο蠓治龇椒?、面向?qū)ο蠓治龇椒?oop)(oop)：.-可修編-.-.將客觀世界的事物抽象為對象，將客觀世界的事物抽象為對象，通過屬性通過屬性和方法描述對象的狀態(tài)和行為，具有繼承、和方法描述對象的

46、狀態(tài)和行為，具有繼承、封裝和多態(tài)性等特征。封裝和多態(tài)性等特征。例：軟件開發(fā)的結(jié)構(gòu)化分析方法中，常用的例：軟件開發(fā)的結(jié)構(gòu)化分析方法中，常用的描述軟件功能需求的工具是（描述軟件功能需求的工具是（）a a、業(yè)務(wù)流程圖、處理說明、業(yè)務(wù)流程圖、處理說明b b、軟件流程圖、模塊說明軟件流程圖、模塊說明c c、數(shù)據(jù)流程圖、數(shù)據(jù)字典、數(shù)據(jù)流程圖、數(shù)據(jù)字典d d、系統(tǒng)流程圖、程序編碼系統(tǒng)流程圖、程序編碼四、軟件概要設(shè)計(jì)：四、軟件概要設(shè)計(jì)：將軟件需求轉(zhuǎn)換為軟件表示的過程。將軟件需求轉(zhuǎn)換為軟件表示的過程。軟軟件概要設(shè)計(jì)的基本任務(wù)：件概要設(shè)計(jì)的基本任務(wù)：1 1、設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)、設(shè)計(jì)軟件系統(tǒng)結(jié)構(gòu)2 2、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)

47、庫設(shè)計(jì)（概要設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)及數(shù)據(jù)庫設(shè)計(jì)（概要設(shè)計(jì)、.-可修編-.-.邏輯設(shè)計(jì)、物理設(shè)計(jì)）邏輯設(shè)計(jì)、物理設(shè)計(jì)） ：3 3、編寫概要設(shè)計(jì)文檔：、編寫概要設(shè)計(jì)文檔：4 4、評審：、評審：軟軟件設(shè)計(jì)的方法：件設(shè)計(jì)的方法：模塊化：模塊在程序中是數(shù)據(jù)說明、可執(zhí)模塊化：模塊在程序中是數(shù)據(jù)說明、可執(zhí)行語句等程序?qū)ο蟮募?，行語句等程序?qū)ο蟮募希蛘呤菃为?dú)命名或者是單獨(dú)命名和編址的元素，和編址的元素， 如高級語言中的過程、如高級語言中的過程、 函數(shù)、函數(shù)、子程序等。子程序等。模模塊獨(dú)立性指每個(gè)模塊只完成系統(tǒng)要求塊獨(dú)立性指每個(gè)模塊只完成系統(tǒng)要求的獨(dú)立的子功能，的獨(dú)立的子功能，并且與其他模塊的聯(lián)系并且與其他模塊的

48、聯(lián)系最少且接口簡單。其度量標(biāo)準(zhǔn)是：耦合性最少且接口簡單。其度量標(biāo)準(zhǔn)是：耦合性和聚性和聚性耦耦合性也稱塊間聯(lián)系，合性也稱塊間聯(lián)系，指軟件系統(tǒng)結(jié)構(gòu)中指軟件系統(tǒng)結(jié)構(gòu)中各模塊間相互聯(lián)系緊密程度的一種度量。各模塊間相互聯(lián)系緊密程度的一種度量。模塊之間聯(lián)系越緊密，其耦合性就越強(qiáng)，模塊之間聯(lián)系越緊密，其耦合性就越強(qiáng)，.-可修編-.-.模塊的獨(dú)立性則越差。模塊的獨(dú)立性則越差。聚聚性也稱塊聯(lián)系，指模塊功能強(qiáng)度的度性也稱塊聯(lián)系，指模塊功能強(qiáng)度的度量，量， 即一個(gè)模塊部各個(gè)元素即一個(gè)模塊部各個(gè)元素( (語句之間、語句之間、 程程序段之間序段之間) )彼此結(jié)合的緊密程度的度量。彼此結(jié)合的緊密程度的度量。將將軟件系統(tǒng)劃

49、分模塊時(shí)，軟件系統(tǒng)劃分模塊時(shí)，盡量做到高聚低盡量做到高聚低耦合。耦合。例：為了使模塊盡可能獨(dú)立，要求（例：為了使模塊盡可能獨(dú)立，要求（）a a、模塊的聚程序要盡量高，模塊的聚程序要盡量高，且各模塊間的且各模塊間的耦合程序要盡量強(qiáng)耦合程序要盡量強(qiáng)b b、模塊的聚程序要盡量高，模塊的聚程序要盡量高，且各模塊間的且各模塊間的耦合程序要盡量弱耦合程序要盡量弱c c、模塊的聚程序要盡量低，模塊的聚程序要盡量低，且各模塊間的且各模塊間的耦合程序要盡量弱耦合程序要盡量弱d d、 模塊的聚程序要盡量低，模塊的聚程序要盡量低，且各模塊間的且各模塊間的.-可修編-.-.耦合程序要盡量強(qiáng)耦合程序要盡量強(qiáng)五、軟件詳細(xì)

50、設(shè)計(jì)：五、軟件詳細(xì)設(shè)計(jì)：主要確定每個(gè)模塊具體執(zhí)行過程主要確定每個(gè)模塊具體執(zhí)行過程軟軟件詳細(xì)設(shè)計(jì)的基本任務(wù)：件詳細(xì)設(shè)計(jì)的基本任務(wù)：1 1、為每個(gè)模塊進(jìn)行詳細(xì)的算法設(shè)計(jì)：、為每個(gè)模塊進(jìn)行詳細(xì)的算法設(shè)計(jì)：2 2、為模塊的數(shù)據(jù)結(jié)構(gòu)進(jìn)行設(shè)計(jì)：、為模塊的數(shù)據(jù)結(jié)構(gòu)進(jìn)行設(shè)計(jì)：3 3、對數(shù)據(jù)庫進(jìn)行物理設(shè)計(jì)：、對數(shù)據(jù)庫進(jìn)行物理設(shè)計(jì)：4 4、輸入、輸出格式設(shè)計(jì)、輸入、輸出格式設(shè)計(jì)5 5、編寫詳細(xì)設(shè)計(jì)說明書：、編寫詳細(xì)設(shè)計(jì)說明書：6 6、評審：、評審：詳詳細(xì)設(shè)計(jì)常用三種工具：細(xì)設(shè)計(jì)常用三種工具：圖形圖形( (流程圖、盒圖、問題分析圖流程圖、盒圖、問題分析圖 pad)pad)、表格表格( (判定表判定表) )、語言語言

51、( (過程設(shè)計(jì)語言，又稱為偽碼過程設(shè)計(jì)語言，又稱為偽碼) ).-可修編-.-.六、軟件編碼：六、軟件編碼：主要是將詳細(xì)設(shè)計(jì)得到的處理過程描述主要是將詳細(xì)設(shè)計(jì)得到的處理過程描述轉(zhuǎn)換為基于某種計(jì)算機(jī)語言的程序轉(zhuǎn)換為基于某種計(jì)算機(jī)語言的程序常用的計(jì)算機(jī)語言：常用的計(jì)算機(jī)語言：pascalpascal 、c c、c+c+、javajava 等等七、軟件測試：七、軟件測試：軟件測試代表了需求分析、設(shè)計(jì)、編碼的軟件測試代表了需求分析、設(shè)計(jì)、編碼的最終復(fù)審。最終復(fù)審。軟件測試貫穿于軟件開發(fā)的全過軟件測試貫穿于軟件開發(fā)的全過程。程。軟軟件測試的目的：件測試的目的：1 1、軟件測試是為了盡可能多地發(fā)現(xiàn)程序、軟件

52、測試是為了盡可能多地發(fā)現(xiàn)程序中的錯(cuò)誤而執(zhí)行程序的過程。中的錯(cuò)誤而執(zhí)行程序的過程。2 2、一個(gè)好的測試用例能夠發(fā)現(xiàn)至今尚未、一個(gè)好的測試用例能夠發(fā)現(xiàn)至今尚未.-可修編-.-.發(fā)現(xiàn)的錯(cuò)誤。發(fā)現(xiàn)的錯(cuò)誤。3 3、一個(gè)成功的測試是發(fā)現(xiàn)了至今尚未發(fā)、一個(gè)成功的測試是發(fā)現(xiàn)了至今尚未發(fā)現(xiàn)的錯(cuò)誤的測試。現(xiàn)的錯(cuò)誤的測試。軟軟件測試的原則：件測試的原則：1 1、測試用例應(yīng)由輸入數(shù)據(jù)和預(yù)期的輸出、測試用例應(yīng)由輸入數(shù)據(jù)和預(yù)期的輸出數(shù)據(jù)兩部分組成。數(shù)據(jù)兩部分組成。2 2、測試用例不僅選用合理的輸入數(shù)據(jù)，、測試用例不僅選用合理的輸入數(shù)據(jù)，還要選擇不合理的輸入數(shù)據(jù)還要選擇不合理的輸入數(shù)據(jù)3 3、除了檢查程序是否做了它應(yīng)該做的

53、事、除了檢查程序是否做了它應(yīng)該做的事4 4、應(yīng)制定測試計(jì)劃并嚴(yán)格執(zhí)行，排除隨、應(yīng)制定測試計(jì)劃并嚴(yán)格執(zhí)行，排除隨意性意性5 5、長期保留測試用例、長期保留測試用例6 6、對發(fā)現(xiàn)錯(cuò)誤較多的程序段，應(yīng)進(jìn)行更、對發(fā)現(xiàn)錯(cuò)誤較多的程序段，應(yīng)進(jìn)行更深入的測試深入的測試7 7、程序員避免測試自己的程序、程序員避免測試自己的程序.-可修編-.-.軟軟件測試方法：件測試方法：1 1、靜態(tài)測試：、靜態(tài)測試：是指被測試程序不在機(jī)器上運(yùn)行，而是是指被測試程序不在機(jī)器上運(yùn)行，而是采用人工檢測和計(jì)算機(jī)輔助靜態(tài)分析的手采用人工檢測和計(jì)算機(jī)輔助靜態(tài)分析的手段對程序進(jìn)行檢測。段對程序進(jìn)行檢測。2 2、動(dòng)態(tài)測試：是指通過運(yùn)行程序發(fā)

54、現(xiàn)錯(cuò)、動(dòng)態(tài)測試：是指通過運(yùn)行程序發(fā)現(xiàn)錯(cuò)誤誤a a、黑盒測試法、黑盒測試法( (功能測試功能測試) )：主要對軟件的接口進(jìn)行測試，主要對軟件的接口進(jìn)行測試，依據(jù)需求規(guī)依據(jù)需求規(guī)格說明書，檢查程序是否滿足功能要求。常格說明書，檢查程序是否滿足功能要求。常用的技術(shù)是等價(jià)類劃分法、邊界值分析法、用的技術(shù)是等價(jià)類劃分法、邊界值分析法、錯(cuò)誤推測法、因果圖法、綜合策略法錯(cuò)誤推測法、因果圖法、綜合策略法b b、白盒測試法、白盒測試法( (結(jié)構(gòu)測試結(jié)構(gòu)測試) )：主要測試程序的部結(jié)構(gòu)和處理過程。主要測試程序的部結(jié)構(gòu)和處理過程。常用常用的技術(shù)是語句覆蓋、條件覆蓋、路徑覆蓋、的技術(shù)是語句覆蓋、條件覆蓋、路徑覆蓋、.

55、-可修編-.-.判定覆蓋等判定覆蓋等軟軟件測試的實(shí)施：件測試的實(shí)施：1 1、單元測試：、單元測試：單元測試是對軟件設(shè)計(jì)的最小單位單元測試是對軟件設(shè)計(jì)的最小單位模塊模塊( (程序單元程序單元) )進(jìn)行正確性檢驗(yàn)測試，主要進(jìn)行正確性檢驗(yàn)測試，主要針對模塊的以下五個(gè)基本特征進(jìn)行測試：針對模塊的以下五個(gè)基本特征進(jìn)行測試：a a、模塊接口、模塊接口b b、局部數(shù)據(jù)結(jié)構(gòu)：、局部數(shù)據(jù)結(jié)構(gòu)：c c、重要的執(zhí)行路徑：、重要的執(zhí)行路徑：d d、錯(cuò)誤處理測試：、錯(cuò)誤處理測試：e e、邊界條件：、邊界條件：2 2、集成測試：、集成測試：集成測試是指在單元測試的基礎(chǔ)上，集成測試是指在單元測試的基礎(chǔ)上，將所將所有模塊按照

56、設(shè)計(jì)要求組裝成一個(gè)完整的系有模塊按照設(shè)計(jì)要求組裝成一個(gè)完整的系統(tǒng)進(jìn)行的測試，故也稱組裝測試或聯(lián)合測統(tǒng)進(jìn)行的測試，故也稱組裝測試或聯(lián)合測.-可修編-.-.試。試。主要方法有兩種：主要方法有兩種：非漸增式測試：非漸增式測試：首先對每個(gè)模塊分別進(jìn)行首先對每個(gè)模塊分別進(jìn)行單元測試，單元測試，然后再把所有的模塊按設(shè)計(jì)要求然后再把所有的模塊按設(shè)計(jì)要求組裝在一起進(jìn)行測試。組裝在一起進(jìn)行測試。漸增式測試：漸增式測試：逐個(gè)把未經(jīng)過測試的模塊組逐個(gè)把未經(jīng)過測試的模塊組裝到已經(jīng)過測試的模塊上去，進(jìn)行集成測裝到已經(jīng)過測試的模塊上去，進(jìn)行集成測試，每加入一個(gè)新模塊進(jìn)行一次集成測試，試，每加入一個(gè)新模塊進(jìn)行一次集成測試，

57、重復(fù)此過程直至程序組裝完畢。重復(fù)此過程直至程序組裝完畢。3 3、確認(rèn)測試：、確認(rèn)測試：確認(rèn)測試又稱有效性測試，確認(rèn)測試又稱有效性測試，它的任務(wù)是檢它的任務(wù)是檢查軟件的功能與性能是否與需求規(guī)格說明查軟件的功能與性能是否與需求規(guī)格說明書中確定的指標(biāo)相符合，書中確定的指標(biāo)相符合，因而需求規(guī)格說明因而需求規(guī)格說明是確認(rèn)測試的基礎(chǔ)。是確認(rèn)測試的基礎(chǔ)。4 4、系統(tǒng)測試：、系統(tǒng)測試：.-可修編-.-.系統(tǒng)測試是通過測試確認(rèn)的軟件作為整系統(tǒng)測試是通過測試確認(rèn)的軟件作為整個(gè)計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、個(gè)計(jì)算機(jī)系統(tǒng)的一個(gè)元素，與計(jì)算機(jī)硬件、外設(shè)、支撐軟件、數(shù)據(jù)和人員等其他系統(tǒng)元外設(shè)、支撐軟件、數(shù)據(jù)和人員等

58、其他系統(tǒng)元素組合在一起，素組合在一起，在實(shí)際運(yùn)行環(huán)境下對計(jì)算機(jī)在實(shí)際運(yùn)行環(huán)境下對計(jì)算機(jī)系統(tǒng)進(jìn)行一系列的集成測試和確認(rèn)測試。系統(tǒng)進(jìn)行一系列的集成測試和確認(rèn)測試。程程序調(diào)試：序調(diào)試：調(diào)試是在進(jìn)行了成功的測試之后才開始調(diào)試是在進(jìn)行了成功的測試之后才開始的工作，目的是確定錯(cuò)誤的原因和位置，的工作，目的是確定錯(cuò)誤的原因和位置，并改正錯(cuò)誤，又稱為糾錯(cuò)。并改正錯(cuò)誤，又稱為糾錯(cuò)。例：軟件測試的目的是（例：軟件測試的目的是（）a a、證證明明軟軟件件的的正正確確性性b b、找出軟件系統(tǒng)中存在的所有錯(cuò)誤、找出軟件系統(tǒng)中存在的所有錯(cuò)誤c c、盡可能多地發(fā)現(xiàn)軟件系統(tǒng)中的錯(cuò)誤、盡可能多地發(fā)現(xiàn)軟件系統(tǒng)中的錯(cuò)誤d d、證明

59、軟件系統(tǒng)中存在錯(cuò)誤、證明軟件系統(tǒng)中存在錯(cuò)誤.-可修編-.-.在軟件測試方法中，在軟件測試方法中，黑箱測試法和白箱測黑箱測試法和白箱測試法是常用的方法，其中黑箱測試法是常用的方法，其中黑箱測試法主要是試法主要是用于測試（用于測試（）a a、結(jié)構(gòu)合理性、結(jié)構(gòu)合理性輯輯b b 、 軟軟 件件 外外 部部 功功 能能d d、 程序部邏程序部邏c c、程序正確性、程序正確性八、軟件維護(hù)：八、軟件維護(hù)：軟件投入使用后進(jìn)行的階段，軟件投入使用后進(jìn)行的階段，是軟件生是軟件生存周期中時(shí)間最長的一個(gè)階段，存周期中時(shí)間最長的一個(gè)階段，所花費(fèi)的精所花費(fèi)的精力和費(fèi)用也是最多的一個(gè)階段。主要是因力和費(fèi)用也是最多的一個(gè)階段

60、。主要是因?yàn)椋弘[含的錯(cuò)誤要修改；新增的功能要加入為：隱含的錯(cuò)誤要修改；新增的功能要加入進(jìn)去；環(huán)境的變化對程序進(jìn)行變動(dòng)等。進(jìn)去；環(huán)境的變化對程序進(jìn)行變動(dòng)等。軟軟件維護(hù)的容有四類：件維護(hù)的容有四類：.-可修編-.-.1 1、校正性維護(hù)：、校正性維護(hù)：為了識別和糾正錯(cuò)誤，為了識別和糾正錯(cuò)誤，修改軟件性能上的修改軟件性能上的缺陷，其占整個(gè)維護(hù)工作的缺陷，其占整個(gè)維護(hù)工作的 21%21%2 2、適應(yīng)性維護(hù)：、適應(yīng)性維護(hù)：為了使應(yīng)用軟件適應(yīng)環(huán)境為了使應(yīng)用軟件適應(yīng)環(huán)境 ( (硬件、系統(tǒng)軟硬件、系統(tǒng)軟件、數(shù)據(jù)件、數(shù)據(jù)) )的變化而修改軟件的過程稱為適的變化而修改軟件的過程稱為適應(yīng)性維護(hù)，其占整個(gè)維護(hù)工作的應(yīng)性