【正文】 斷地維護(hù)，根據(jù)新進(jìn)出的需求進(jìn)行必要而且可能的擴(kuò)充和刪改。 （ 5） 軟件測試。編寫概要設(shè)計(jì)說明書、詳細(xì)設(shè)計(jì)說明書和測試計(jì)劃初稿，提交評(píng)審。編寫軟件規(guī)格說明書及初步的用戶手冊，提交評(píng)審。軟件生命周期的主要活動(dòng)階段是： （ 1） 可行性研究與計(jì)劃制定。軟件工程過程應(yīng)確定方法使用的順序、要求交付的文檔資料、為保證質(zhì)量和適應(yīng)變化所需要的管理、軟件開發(fā)各個(gè)階段完成的任務(wù)。 通常把用戶的要求轉(zhuǎn)變成軟件產(chǎn)品的過程也叫做軟件開發(fā)過程。 （ 3） C（ check） ——軟件確認(rèn)?；谶@個(gè)方面，軟件工程過程通常包含 4種基本活動(dòng)： （ 1） P（ plan） ——軟件規(guī)格說明。在考 慮軟件費(fèi)用時(shí)，不僅僅要降低開發(fā)成本，更要降低整個(gè)軟件生命周期的總成本。方法是完成軟件工程項(xiàng)目的技術(shù)手段；工具支持軟件的開發(fā)、管理、文檔生成；過程支持軟件開發(fā)的各個(gè)環(huán)節(jié)的控制、管理。 關(guān)于軟件工程的定義，國標(biāo)（ GB）中指出，軟件工程是應(yīng)用于計(jì)算機(jī)軟件的定義、開發(fā)和維護(hù)的一整套方法、工具文檔、實(shí)踐標(biāo)準(zhǔn)的工序。 （ 5） 軟件的成本不斷提高。 （ 2） 軟件開發(fā)成本和進(jìn)度無法控制。實(shí)際上，幾科所有的軟件都 不同程度地存在這些問題。系統(tǒng)軟件是計(jì)算機(jī)管理自身資源，提高計(jì)算機(jī)使用效率并為計(jì)算機(jī)用戶提供各種服務(wù)的軟件。 （ 5） 軟件復(fù)雜性高，成本昂貴 。一旦研制開發(fā)成功，可以大量拷貝同一內(nèi)容的副本。 國標(biāo)（ GB）中對(duì)計(jì)算機(jī)軟件的定義為：與計(jì)算機(jī)系統(tǒng)的操作有關(guān)的計(jì)算機(jī)程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數(shù)據(jù)。基中，程序是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的用程序設(shè)計(jì)語言描述的、適合計(jì)算機(jī)執(zhí)行的指令（語句）序列。 多態(tài)性機(jī)制不僅增加了面向?qū)ο筌浖到y(tǒng)的靈活性，進(jìn)一步減少了信息冗余，而且顯著地提高了軟件的可重用性和可擴(kuò)充性。繼承性的優(yōu)點(diǎn)是，相似的對(duì)象可以共享程序代碼和數(shù)據(jù)結(jié)構(gòu)，從而大大減少了程序中的冗余信息，提高軟件的可重用性，便于軟件個(gè)性維護(hù)。單繼承是指，一個(gè)類只允許有一個(gè)父類，即類等級(jí)為樹形結(jié)構(gòu)。這種層次結(jié) 構(gòu)系統(tǒng)的一個(gè)重要性質(zhì)是繼承性，一個(gè)類直接繼承其父類的描述（數(shù)據(jù)和操作）或特性，子類自動(dòng)地共享基類中定義的數(shù)據(jù)和方法。繼承是使用己有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。一個(gè)對(duì)象可以同時(shí)往多個(gè)對(duì)象傳遞信息，兩個(gè)對(duì)象也可以同時(shí)向某個(gè)對(duì)象傳遞消息。所傳送的消息實(shí)質(zhì)上是接受對(duì)象所具有的操作 /方法名稱，有時(shí)還包括相應(yīng)參數(shù)。消息是一個(gè)實(shí)例與另一個(gè)實(shí)例之間傳遞信息，它請(qǐng)示對(duì)象執(zhí)行某一處 理或回答某一要求的信息，它統(tǒng)一了數(shù)據(jù)流的控制流。 例如： Integer是一個(gè)整數(shù)類，它描述了所有整數(shù)的性質(zhì)。對(duì)象是面向?qū)ο蟮能浖?的基本模塊，它是由數(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ì)象的外部特性，即只需知道數(shù)據(jù)的取值范圍和可以對(duì)該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。指可以將具有相同屬性的操作的對(duì)象抽象成類。對(duì)的這一特性即是對(duì)象的封裝性。 操作描述了對(duì)象執(zhí)行的功能，若通過消息傳遞，還可以為其他對(duì)象使用?？傊瑢?duì)象是對(duì)問題域中某個(gè)實(shí)體的抽象，設(shè)立某個(gè)對(duì)象就反映軟件系統(tǒng)保存有關(guān)它的信息并具有與它進(jìn)行交互的能力。 易于開發(fā)大型軟件產(chǎn)品 可維護(hù)性好 （ 1）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件穩(wěn)定性比較好 （ 2）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件比較容易修改； （ 3）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件比較容易理解。 面向?qū)ο蟮脑O(shè)計(jì)方法與傳統(tǒng)的面向過程的方法有本質(zhì)不同，這種方法的基本原理是：使用現(xiàn)實(shí)世界的概念抽象地思考問題從而自然地解決問題。 2． 3面向?qū)ο蟮某绦蛟O(shè)計(jì) 一、關(guān)于面向?qū)ο蠓椒? 面向?qū)ο蠓椒ǖ谋举|(zhì)，就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實(shí)生活中常用的思維方法來認(rèn)識(shí)、理解和描述客觀事 物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域，也就是說，系統(tǒng)中的對(duì)象以及對(duì)象之間的關(guān)系能夠如實(shí)地反映問題域中固有事物及其關(guān)系。二是編程工作的效率，降低軟件開發(fā)成本。 選擇結(jié)構(gòu)：選擇結(jié)構(gòu)又稱為分支結(jié)構(gòu)，它包括簡單選擇和多分支選擇結(jié)構(gòu)，這種結(jié)構(gòu)可以根據(jù)設(shè)定的條件，判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列。模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個(gè)小目標(biāo)稱為一個(gè)模塊。 自頂向下：程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。 語句的結(jié)構(gòu) 程序應(yīng)該簡單易懂，語句構(gòu)造應(yīng)該簡單直接，不應(yīng)該為提高效率而把語句復(fù)雜化。一般應(yīng)注意如下幾點(diǎn)： （ 1） 數(shù)據(jù)說明的次序規(guī)范化鑒于程序理解、新聞?dòng)浾吆途S護(hù)的需要，使數(shù)據(jù)說明次序固定，可以使數(shù)據(jù)的發(fā)生容易查找，也有利于測試、排錯(cuò)和維護(hù)。 源程序文檔化 源程序文檔化應(yīng)考慮如下幾點(diǎn)： （ 1） 符號(hào)名的命名：符號(hào)名的命名應(yīng)具有一定的實(shí)際含義，以便于對(duì)程序功能的理解。 一般來講。 設(shè)一棵完全二叉共有 700個(gè)結(jié)點(diǎn)，則在該二叉樹中有 個(gè)葉子結(jié)點(diǎn)。反復(fù)做第（ 2）步，真到剩下的子序列為空為止。 簡單選擇排序法在最壞情況下需要比較 n(n1)/2/次。增量序列一般取 h=n/2k(k=1,2,…[log2n], 其中 n為待排序序列的長度。效率與冒泡法相同 在最壞情況下，簡單插入排序需要 n(n1)/2次比較。 上述兩個(gè)操作交替進(jìn)行，直到指針 i與 j 指向同一個(gè)位置（即 i=j）為止，此時(shí)將 P(i)的位置上。 步驟：首先，在表的第一個(gè)，中間一個(gè)與最后一個(gè)元素中選取中項(xiàng)，設(shè)為 P（ K），并將 P（ K）賦給 T，再將表中的第一個(gè)元素移到 P（ K）的位置上。 快速排序法 快速排序法也是種互換類的排序法，但由于它比冒泡排序法的速度快，因此稱之為快速排序法。若相鄰兩個(gè)元素中，后面的元素大于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。冒泡排序法與快速排序法都屬于交換類的排序方法。 這個(gè)過程一直進(jìn)行到查找成功或子表長度為 0（說明線性表中沒有這個(gè)元素）為止。 即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。 一、順序查找 順序查找又稱順序搜索。 （ 2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。在最壞情況下，需要的比較次數(shù)為 O（Ｎ１ .５）。 子序列的分割方法 如下： 將相隔某個(gè)增量 H 的元素構(gòu)成一個(gè)子序列。 二、 插入類排序法 簡單插入排序法 所謂插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。反復(fù)操作以下兩步： （ 4） 將 j逐漸減小，并逐次比較 P（ j）與 T，直到發(fā)現(xiàn)一個(gè) P(j)T 為止，將 P(j)移到 P(i)位置上。通過對(duì)線性表的一次分割，就以 T 為分界線，將線性表分成了前后兩個(gè)子表，且前面子表中的所有元素均不大于 T，而后面子表中的所有元素均不小于T。 重復(fù)上述過程，直到剩下的線性有變空為止，此時(shí)的線性表已經(jīng)變?yōu)橛行?。若相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們互換，稱之為消去了一個(gè)逆序?？梢宰C明，對(duì)于長度為 n的有序線性表，在最壞情況下，二分查找只需要比較 log2n次 ，而順序查找需要比較 n次。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。 順序查找的效率是很低的。 F， C， A， D， B， E， G， H， P 中序遍歷（ LDR） 所謂中序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子 樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。 若 2k+1≤n，則編號(hào)為 k 的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為 2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。 完全二叉樹還具有以下兩個(gè)性質(zhì)： 性質(zhì) 5：具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 [ log2n]+1。 完全二叉樹 所謂完全二叉樹是指這樣的二叉樹，除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)的最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。 性質(zhì) 4：具有 n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為 [ log2n]+1,其中 [ log2n]表示取的整數(shù)部分。 二叉樹的基本性質(zhì) 性質(zhì) 1：在二叉樹的第 K層上，最多有（ K≥1）個(gè)結(jié)點(diǎn)。二就樹具有以下兩個(gè)特點(diǎn)： 非空二叉樹只有一個(gè)根結(jié)點(diǎn)； 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。 用樹來表示算術(shù)表達(dá)式的原則如下： 表達(dá)式中的每一個(gè)運(yùn)算符在樹中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)。 樹的最大層次稱為樹的深度。 在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。 鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。 隊(duì)列運(yùn)算包括（ 1）入隊(duì)運(yùn)算：從隊(duì)尾插入一個(gè)元素；（ 2）退隊(duì)運(yùn)算：從隊(duì)頭刪除一個(gè)元素。 棧的基本運(yùn)算：（ 1）插入元素稱為入棧運(yùn)算；（ 2）刪除元素稱為退棧運(yùn)算；（ 3）讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量，此時(shí)指針無變化。 順序表的運(yùn)算：插入、刪除。 非空線性表的結(jié)構(gòu)特征： （ 1）且只有一個(gè)根結(jié)點(diǎn) a1，它無前件； （ 2）有且只有一個(gè)終端結(jié)點(diǎn) an，它無后件； （ 3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。 線性結(jié)構(gòu)條件： （ 1）有且只有一個(gè)根結(jié)點(diǎn)； （ 2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。 數(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ì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。 算法的基本要素：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)。 二級(jí)共公基礎(chǔ)知識(shí)教程 第一章數(shù)據(jù)結(jié)構(gòu)與算法 算法 算法：是指解題方案的準(zhǔn)確而完整的描述。特征包括： （ 1）可行性； （ 2）確定性，算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性； （ 3）有窮性，算法必須能在有限的時(shí)間內(nèi)做完，即能在執(zhí)行有限個(gè)步驟后終止，包 括合理的執(zhí)行時(shí)間的含義； （ 4）擁有足夠的情報(bào)。 算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。 算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。 在復(fù)雜線性表中，由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個(gè)記錄構(gòu)成的線性表又稱為文件。 ai 的存儲(chǔ)地址為： ADR(ai)=ADR(a1)+(i1)k,， ADR(a1)為第一個(gè)元素的地址， k 代表每個(gè)元素占的字節(jié)數(shù)。用 top表示棧頂 位置，用 bottom表示棧底。 隊(duì)列是 “先進(jìn)行出 ”（ FIFO）或 “后進(jìn)后出 ”（ LILO）的線性表。 在鏈?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)系是由指針域來確定的。 1． 6樹與二叉樹 一、樹的基本概念 在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱為樹的根。 葉子結(jié)點(diǎn)的度為 0。例職，取正（ +）等只有一個(gè)運(yùn)算對(duì)象，稱為單目運(yùn)算符；二個(gè)運(yùn)算對(duì)象稱為雙目運(yùn)算符，三目運(yùn)算符。 二、二叉樹及其基本性質(zhì) 什么是二叉樹 二叉樹是一種很有用的非線性結(jié)構(gòu)?？梢詻]有其中的一個(gè)，也可以全沒有。 性質(zhì) 3：在任意一棵二叉樹中度為 0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為 2的結(jié)點(diǎn)多一個(gè)。這就是說，在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹的第 K 層上有2K1個(gè)結(jié)點(diǎn)，且深度為 m的滿二叉樹有 2m1個(gè)結(jié)點(diǎn)。 由滿二叉樹與完全二叉樹的特點(diǎn)可以看出，滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。 若 2k≤n，則編號(hào)為 k 的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為 2k ；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）。 前序遍歷（ DLR） 所謂前序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。順序查找一般是指在線性表中查找指定的元素，其基本方法如下：從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若相等則表示找到（ 即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較但都不相等，則表示線性表中沒有要找的元素（即查找失敗）。 二、二分法查找 二分法查找只適用于存儲(chǔ)的有序表。 顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，并且，二分查找的效率要比順序查找高得多。 冒泡排序法 基本過