全國計算機(jī)等級考試二級公共基礎(chǔ)知識考綱.doc

《全國計算機(jī)等級考試二級公共基礎(chǔ)知識考綱.doc》由會員分享，可在線閱讀，更多相關(guān)《全國計算機(jī)等級考試二級公共基礎(chǔ)知識考綱.doc（40頁珍藏版）》請在裝配圖網(wǎng)上搜索。

。 目錄 二級公共基礎(chǔ)知識考綱 ………………………………………………………………1 第一章 數(shù)據(jù)結(jié)構(gòu)與算法…………………………………………………………2 第二章 程序設(shè)計基礎(chǔ)……………………………………………………………19 第三章 軟件工程基礎(chǔ)……………………………………………………………23 第四章 數(shù)據(jù)庫設(shè)計基礎(chǔ)…………………………………………………………32 全國計算機(jī)等級考試二級公共基礎(chǔ)知識考綱 考試內(nèi)容 一、 基本數(shù)據(jù)結(jié)構(gòu)與算法 1. 算法的基本概念；算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。 2. 數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。 3. 線性表的定義；線性表的順序存儲結(jié)構(gòu)及其插入與刪除運(yùn)算。 4. 棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運(yùn)算。 5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算。 6. 樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。 7. 順序查找與二分法查找算法；基本排序算法（交換類排序，選擇類排序，插入類排序）。 二、 程序設(shè)計基礎(chǔ) 1. 程序設(shè)計方法與風(fēng)格。 2. 結(jié)構(gòu)化程序設(shè)計。 3. 面向?qū)ο蟮某绦蛟O(shè)計方法，對象，方法，屬性及繼承與多態(tài)性。 三、 軟件工程基礎(chǔ) 1. 軟件工程基本概念，軟件生命周戎概念，軟件工具與軟件開發(fā)環(huán)境。 2. 結(jié)構(gòu)化分析方法，數(shù)據(jù)流圖，數(shù)據(jù)字典，軟件需求規(guī)格說明書。 3. 結(jié)構(gòu)化設(shè)計方法，總體設(shè)計與詳細(xì)設(shè)計。 4. 軟件測試的方法，白盒測試與黑盒測試，測試用例設(shè)計，軟件測試的實(shí)施，單元測試、集成測試和系統(tǒng)測試。 5. 程序的調(diào)試，靜態(tài)調(diào)試與動態(tài)調(diào)試。 四、 數(shù)據(jù)庫設(shè)計基礎(chǔ) 1. 數(shù)據(jù)庫的基本概念：數(shù)據(jù)庫，數(shù)據(jù)庫管理系統(tǒng)，數(shù)據(jù)庫系統(tǒng)。 2. 數(shù)據(jù)模型，實(shí)體聯(lián)系模型及E-R圖，從E-R圖導(dǎo)出關(guān)系數(shù)據(jù)模型。 3. 關(guān)系代數(shù)運(yùn)算，包括集合運(yùn)算及選擇、投影、連接運(yùn)算，數(shù)據(jù)庫規(guī)范化理論。 4. 數(shù)據(jù)庫設(shè)計方法和步驟：需求分析、概念設(shè)計、邏輯設(shè)計和物理設(shè)計的相關(guān)策略。 考試方式 公共基礎(chǔ)的考試方式為筆試，與C語言（VisualBASIC、Visual FoxPro、Java、Access、Visual C++）的筆試部分合為一張試卷。公共基礎(chǔ)部分占全卷的30分。公共基礎(chǔ)知識有10道選擇題和5道填空題。 第一章 數(shù)據(jù)結(jié)構(gòu)與算法 一、內(nèi)容要點(diǎn) （一）算法 1．算法的基本概念 算法是指解題方案的準(zhǔn)確而完整的描述。即是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，沒有二義性，同時該規(guī)則將在有限次運(yùn)算后可終止。 1）算法的基本特征 （1）可行性 由于算法的設(shè)計是為了在某一個特定的計算工具上解決某一個實(shí)際的問題而設(shè)計的，因此，它總是受到計算工具的限制，使執(zhí)行產(chǎn)生偏差。 如：計算機(jī)的數(shù)值有效位是有限的，當(dāng)大數(shù)和小數(shù)進(jìn)行運(yùn)算時，往往會因為有效位數(shù)的影響而使小數(shù)丟失，因此，在算法設(shè)計時，應(yīng)該考慮到這一點(diǎn)。 （2）確定性 算法的設(shè)計必須是每一個步驟都有明確的定義，不允許有模糊的解釋，也不能有多義性。 例如，一個實(shí)際的問題，小寶和萍萍共有12個蘋果，小寶比萍萍多4個，請問小寶和萍萍各有幾個蘋果？這個問題，我們可以立一個方程 來求解，要求x和y的值，公式是正確的，但如何讓計算能夠進(jìn)行計算，我們的算法不能把公式直接輸進(jìn)去，而應(yīng)該設(shè)計出解題的步驟和過程。 即設(shè)計的算法是計算工具所能夠正常解決問題的過程。 （3）有窮性 算法的有窮性，即在一定的時間是能夠完成的，即算法應(yīng)該在計算有限個步驟后能夠正常結(jié)束。 例如，在數(shù)學(xué)中的無窮級數(shù)，在計算機(jī)中只能求有限項，即計算的過程是有窮的。 （4）擁有足夠的情報 算法的執(zhí)行與輸入的數(shù)據(jù)和提供的初始條件相關(guān)，不同的輸入或初始條件會有不同的輸出結(jié)果，提供準(zhǔn)確的初始條件和數(shù)據(jù)，才能使算法正確執(zhí)行。 2）算法的基本要素 一是數(shù)據(jù)對象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。 （1）算法中對數(shù)據(jù)的運(yùn)算和操作 算法實(shí)際上是按解題要求從環(huán)境能進(jìn)行的所有操作中選擇合適的操作所組成的一組指令序列。即算法是計算機(jī)所能夠處理的操作所組成的指令序列。 （2）算法的控制結(jié)構(gòu) 算法的功能不僅取決于所選用的操作，而且還與各操作之間的順序有關(guān)。 在算法中，操作的執(zhí)行順序又稱算法的控制結(jié)構(gòu)，一般的算法控制結(jié)構(gòu)有三種：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。 在算法描述是，有相關(guān)的工具對這三種結(jié)構(gòu)進(jìn)行描述，常用的描述工具有：流程圖、N-S結(jié)構(gòu)圖和算法描述語言等。 3）算法設(shè)計的基本方法 為用計算機(jī)解決實(shí)際問題而設(shè)計的算法，即是計算機(jī)算法。 通常的算法設(shè)計有如下幾種： （1）列舉法 列舉法的基本思想是，根據(jù)提出的問題，列舉出所有可能的情況，并用問題中給定的條件檢驗?zāi)男┦菨M足條件的，哪些是不滿足條件的。列舉法通常用于解決“是否存在”或“有哪些可能”等問題。 例如，我國古代的趣味數(shù)學(xué)題：“百錢買百雞”、“雞兔同籠”等，均可采用列舉法進(jìn)行解決。 使用列舉法時，要對問題進(jìn)行詳細(xì)的分析，將與問題有關(guān)的知識條理化、完備化、系統(tǒng)化，從中找出規(guī)律。 （2）歸納法 歸納法的基本思想是，通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)系。歸納是一種抽象，即從特殊現(xiàn)象中找出一般規(guī)律。但由于在歸納法中不可能對所有的情況進(jìn)行列舉，因此，該方法得到的結(jié)論只是一種猜測，還需要進(jìn)行證明。 （3）遞推 遞推，即是從已知的初始條件出發(fā)，逐次推出所要求的各個中間環(huán)節(jié)和最后結(jié)果。其中初始條件或問題本身已經(jīng)給定，或是通過對問題的分析與化簡而確定。 遞推的本質(zhì)也是一種歸納，遞推關(guān)系式通常是歸納的結(jié)果。 例如，裴波那契數(shù)列，是采用遞推的方法解決問題的。 （4）遞歸 在解決一些復(fù)雜問題時，為了降低問題的復(fù)雜程序，通常是將問題逐層分解，最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程，并沒有對問題進(jìn)行求解，而只是當(dāng)解決了最后的問題那些最簡單的問題后，再沿著原來分解的逆過程逐步進(jìn)行綜合，這就是遞歸的方法。 遞歸分為直接遞歸和間接遞歸兩種方法。如果一個算法直接調(diào)用自己，稱為直接遞歸調(diào)用；如果一個算法A調(diào)用另一個算法B，而算法B又調(diào)用算法A，則此種遞歸稱為間接遞歸調(diào)用。 （5）減半遞推技術(shù) 減半遞推即將問題的規(guī)模減半，然后，重復(fù)相同的遞推操作。 例如，一元二次方程的求解。 （6）回溯法 有些實(shí)際的問題很難歸納出一組簡單的遞推公式或直觀的求解步驟，也不能使用無限的列舉。對于這類問題，只能采用試探的方法，通過對問題的分析，找出解決問題的線索，然后沿著這個線索進(jìn)行試探，如果試探成功，就得到問題的解，如果不成功，再逐步回退，換別的路線進(jìn)行試探。這種方法，即稱為回溯法。 如人工智能中的機(jī)器人下棋。 2．算法復(fù)雜度 算法的復(fù)雜度包括時間復(fù)雜度和空間復(fù)雜度。 1）時間復(fù)雜度 即實(shí)現(xiàn)該算法需要的計算工作量。算法的工作量用算法所執(zhí)行的基本運(yùn)算次數(shù)來計算。 同一個問題規(guī)模下，如果算法執(zhí)行所需要的基本次數(shù)取決于某一特定輸入時，可以用以下兩種方法來分析算法的工作量： 算法工作量=f(n) （1）平均性態(tài) 用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來度量算法的工作量。 設(shè)x是某個可能輸入中的某個特定輸入，p(x)是x出現(xiàn)的概率，t(x)是算法在輸入為x時所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為： Dn表示當(dāng)規(guī)模為n時，算法執(zhí)行時所有可能輸入的集合。 （2）最壞情況復(fù)雜度 指在規(guī)模為n時，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為： 例如，在具有n個元素的數(shù)列中搜索一個數(shù)x。 平均性態(tài)： 即該數(shù)在數(shù)列中任何位置出現(xiàn)的數(shù)列是相同的，也有可能不存在，存在的概率為q。 如果有一半的機(jī)會存在，則概率q為1/2，平均性態(tài)： 如果查找的元素一定在數(shù)列中，則每個數(shù)存在的概率即為1，則平均性態(tài)為： 最壞情況分析：即要查找的元素X在數(shù)列的最后或不在數(shù)列中，顯然，它的最壞情況復(fù)雜度為： 2）算法的空間復(fù)雜度 指要執(zhí)行該算法所需要的內(nèi)存空間。算法所占用的內(nèi)存空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間，如執(zhí)行過程中工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間等。 （二）數(shù)據(jù)結(jié)構(gòu)的基本概念 1．概念 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。它包括以下兩個方面： l 表示數(shù)據(jù)元素的信息 l 表示各數(shù)據(jù)之間的前后件關(guān)系 1）數(shù)據(jù)的邏輯結(jié)構(gòu) 是指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素： l 數(shù)據(jù)元素的集合，記作D l 數(shù)據(jù)之間的前后件關(guān)系，記作R 則數(shù)據(jù)結(jié)構(gòu)B=（D，R） 2）數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)，或數(shù)據(jù)的物理結(jié)構(gòu)。 即數(shù)據(jù)存儲時，不僅要存放數(shù)據(jù)元素的信息，而且要存儲數(shù)據(jù)元素之間的前后件關(guān)系的信息。 通常的數(shù)據(jù)存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。 2．?dāng)?shù)據(jù)結(jié)構(gòu)的圖形表示 數(shù)據(jù)結(jié)構(gòu)的圖形表示有兩個元素： l 中間標(biāo)有元素值的方框表示數(shù)據(jù)元素，稱為數(shù)據(jù)結(jié)點(diǎn) l 用有向線段表示數(shù)據(jù)元素之間的前后件關(guān)系，即有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn) 注意：在結(jié)構(gòu)圖中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)，也稱葉子結(jié)點(diǎn)。 3．線性結(jié)構(gòu)與非線性結(jié)構(gòu) 如果一個數(shù)據(jù)元素都沒有，該數(shù)據(jù)結(jié)構(gòu)稱為空數(shù)據(jù)結(jié)構(gòu)；在空數(shù)據(jù)結(jié)構(gòu)中插入一個新的元素后數(shù)據(jù)結(jié)構(gòu)變?yōu)榉强諗?shù)據(jù)結(jié)構(gòu)；將數(shù)據(jù)結(jié)構(gòu)中的所有元素均刪除，則該數(shù)據(jù)結(jié)構(gòu)變成空數(shù)據(jù)結(jié)構(gòu)。 如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足如下條件，則該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)： l 有且只有一個根結(jié)點(diǎn) l 每一個結(jié)點(diǎn)最多只有一個前件，也最多只有一個后件 線性結(jié)構(gòu)又稱線性表。 注意：在線性結(jié)構(gòu)表中插入或刪除元素，該線性表仍然應(yīng)滿足線性結(jié)構(gòu)。 如果一個數(shù)據(jù)結(jié)構(gòu)不滿足線性結(jié)構(gòu)，則稱為非線性結(jié)構(gòu)。 （三）線性表及其順序存儲結(jié)構(gòu) 1．基本概念 線性表是最常用的數(shù)據(jù)結(jié)構(gòu)，它由一組數(shù)據(jù)元素組成。 注意：這里的數(shù)據(jù)元素是一個廣義的數(shù)據(jù)元素，并不僅僅是指一個數(shù)據(jù)。如，矩陣、學(xué)生記錄表等。 非空線性表的結(jié)構(gòu)特征： l 有且只有一個根結(jié)點(diǎn)，它無前件 l 有且只有一個終端結(jié)點(diǎn)，它無后件 l 除根結(jié)點(diǎn)和終端結(jié)點(diǎn)之外，所有的結(jié)點(diǎn)有且只有一個前件和一個后件。線性表中結(jié)點(diǎn)的個數(shù)稱為結(jié)點(diǎn)的長度n。當(dāng)n=0時，稱為空表。 2．順序存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu)的特點(diǎn)： l 線性表中所有的元素所占的存儲空間是連續(xù)的 l 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 通常，順序存儲結(jié)構(gòu)中，線性表中每一個數(shù)據(jù)元素在計算機(jī)存儲空間中的存儲地址由該元素在線性表中的位置序號唯一確定。 線性表的順序存儲結(jié)構(gòu)下的基本運(yùn)算： l 在指定位置插入一個元素 l 刪除線性表中的指定元素 l 查找某個或某些特定的元素 l 線性表的排序 l 按要求將一個線性表拆分為多個線性表 l 將多個線性表合并為一個線性表 l 復(fù)制線性表 l 逆轉(zhuǎn)一個線性表 3．線性表的基本操作 1）順序表的插入運(yùn)算 在順序存儲結(jié)構(gòu)的線性表中插入一個元素。 注意：找到插入位置后，將插入位置開始的所有元素從最后一個元素開始順序后移。另外，在定義線性表時，一定要定義足夠的空間，否則，將不允許插入元素。 2）順序表的刪除運(yùn)算 在順序在存儲結(jié)構(gòu)的線性表中刪除一個元素。 注意：找到刪除的數(shù)據(jù)元素后，從該元素位置開始，將后面的元素一一向前移動，在移動完成后，線性表的長度減1 （四）棧和隊列 1．棧及其基本運(yùn)算 1）棧 棧是一種特殊的線性表，它是限定在一端進(jìn)行插入和刪除的線性表。它的插入和刪除只能在表的一端進(jìn)行，而另一端是封閉的，不允許進(jìn)行插入和刪除操作。 在棧中，允許插入和刪除操作一端稱為棧頂，不允許插入和刪除操作的一端則稱為棧底。棧頂?shù)脑乜偸亲詈蟊徊迦氲脑兀彩亲钕缺粍h除的元素。它遵循的原則是：先進(jìn)后出或后進(jìn)先出。 堆棧指針總是指向棧頂元素的。 2）棧的順序存儲及其運(yùn)算 在棧的順序存儲空間S（1：m）中，S（bottom）通常為棧底元素，S（top）為棧頂元素。Top=0表示棧空；top=m表示棧滿。 1）入棧運(yùn)算 即在棧的頂部插入一個新元素。操作方式是：將棧頂指針加1，再將元素插入至指針?biāo)傅奈恢谩? 2）退棧運(yùn)算 退棧運(yùn)算即將棧頂元素取出并賦給一個指定的變量。操作方式是：先將棧頂元素賦給指定的變量，再將棧頂指針減1。 3）讀棧頂元素 將棧頂元素賦給某一指定變量，但棧頂指針不變。 2．隊列及其基本運(yùn)算 1）隊列 隊列即是允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊尾，通常用一個尾指針指向隊尾；允許刪除的一端稱為隊首，通常用一個隊首指針指向排隊元素的前一個位置。 隊列遵循的規(guī)則是：先進(jìn)先出或后進(jìn)后出 2）循環(huán)隊列及其運(yùn)算 隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式。 循環(huán)隊列，即是次隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。 在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從排頭指針front指向的后一個位置到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。 循環(huán)隊列的初始狀態(tài)為空，即rear=front=m。這里m即為隊列的存儲空間。 循環(huán)隊列的基本運(yùn)算：入隊運(yùn)算和退隊運(yùn)算。 入隊運(yùn)算：每進(jìn)行一次入隊運(yùn)算，隊尾指針加1。當(dāng)隊尾指針rear=m+1時，即表示隊列空間的尾部已經(jīng)放置了元素，則下一個元素應(yīng)該旋轉(zhuǎn)到隊列空間的首部，即rear=1 退隊運(yùn)算：每退隊一個元素，排頭指針加1。當(dāng)排頭指針front=m+1時，即排頭指針指向隊列空間的尾部，退隊后，排頭指針指向隊列空間的開始，即front=1。 在隊列操作時，循環(huán)隊列滿時，front=rear，隊列空時，也有rear=front，即在隊列空或滿時，排頭指針和隊尾指針均指向同一個位置。要判斷隊列空或滿時，還應(yīng)增加一個標(biāo)志，s值的定義： 判斷隊列空與隊列滿的條件下： 隊列空的條件：s=0 隊列滿的條件：s=1、front=rear （1）入隊運(yùn)算 即在隊尾加入一個新元素。這個運(yùn)算有兩個基本操作：首先，將隊尾指針加1，即rear=rear+1，當(dāng)rear=m+1時，置rear=1，然后，將新元素插入到隊尾指針指向的位置。 當(dāng)循環(huán)隊列非空（s=1），且front=rear時，隊列滿，不能進(jìn)行入隊操作。此情況稱“上溢”。 （2）退隊操作 即將隊首的元素賦給一個指定的變量。該運(yùn)算也有兩個基本操作：首先，將排頭指針加1，即front=front+1，當(dāng)front=m+1時，置front=1，然后，將排頭指針指向的元素賦給指定的變量。 當(dāng)循環(huán)隊列為空（s=0）時，不能進(jìn)行退隊運(yùn)算。此種情況稱為“下溢”。 （五）線性鏈表 1．基本概念 前面的線性表均是采用順序存儲結(jié)構(gòu)及在順序存儲結(jié)構(gòu)下的運(yùn)算。 1）順序存儲的優(yōu)點(diǎn)： l 結(jié)構(gòu)簡單 l 運(yùn)算方便 2）順序存儲結(jié)構(gòu)的缺點(diǎn)： l 要在順序存儲的線性表中插入一個新元素或刪除一個元素時，為了保證插入或刪除后的線性表仍然為順序存儲。在插入或刪除元素時，需要移動大量的數(shù)據(jù)元素，因此運(yùn)算效率較低。 l 如果一個線性表分配順序存儲空間后，如果出現(xiàn)線性表的存儲空間已滿，但還需要插入元素時，會發(fā)生“上溢”錯誤。 l 在實(shí)際應(yīng)用時，可能有多個線性表同時使用存儲空間，這樣給存儲空間的分配帶來問題，有可能使有的隊列空間不夠或過多造成浪費(fèi)。 基于上述情況，對于大的線性表或元素變動頻繁的大線性表不宜采用順序存儲結(jié)構(gòu)，而應(yīng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 3）鏈?zhǔn)酱鎯Y(jié)構(gòu) 假設(shè)每一個數(shù)據(jù)結(jié)點(diǎn)對應(yīng)一個存儲單元，該存儲單元稱為存儲結(jié)點(diǎn)，簡稱結(jié)點(diǎn)。 在鏈?zhǔn)酱鎯Ψ绞街?，要求每一個結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素，你為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。該指針用于指向該結(jié)點(diǎn)的前一個或后一個結(jié)點(diǎn)。 在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。 鏈?zhǔn)酱鎯Y(jié)構(gòu)既可以用于線性結(jié)構(gòu)，也可用于非線性結(jié)構(gòu)。 4）線性鏈表 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。 將存儲空間劃分成若干的小塊，每塊占用若干個字節(jié)，這些小塊稱為存儲結(jié)點(diǎn)。 將存儲結(jié)點(diǎn)分為兩個部分，一部分用于存儲數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲元素之間的前后件關(guān)系，即存放下一個元素在存儲序號（即存儲地址），即指向后件結(jié)點(diǎn)，稱為指針域。 在線性鏈表中用一個專門的指針HEAD指向線性鏈表中第一個數(shù)據(jù)元素的結(jié)點(diǎn)（即存放第一個元素的地址）。線性表中最后一個元素沒有后件，因此，線性鏈表中的最后一個結(jié)點(diǎn)的指針域為空（用Null或0表示），表示鏈終結(jié)。 在線性鏈表中，各元素的存儲序號是不連續(xù)的，元素間的前后件關(guān)系與位置關(guān)系也是不一致的。在線性鏈表中，前后件的關(guān)系依靠各結(jié)點(diǎn)的指針來指示，指向表的第一個元素的指針HEAD稱為頭指針，當(dāng)HEAD=NULL時，表示該鏈表為空。 對于線性鏈表，可以從頭指針開始，沿著各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。 這種線性鏈表稱為線性單鏈表，即可以從表頭開始向后掃描鏈表中的所有結(jié)點(diǎn)，而不能從中間或表尾結(jié)點(diǎn)向前掃描位于該結(jié)點(diǎn)之前的元素。 這種鏈表結(jié)構(gòu)的缺點(diǎn)是不能任意地對鏈表中的元素按下同的方向進(jìn)行掃描。在某些應(yīng)用時，如果對鏈表中的元素設(shè)置兩個指針域，一個為指向前件的指針域，稱為左指針（LLink），一個為指向后件的指針域，稱為右指針（RLink）。則這種鏈表是雙向鏈表。 5）帶鏈的棧 帶鏈的棧即是用來收集計算機(jī)存儲空間中的所有空閑的存儲結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。 當(dāng)需要存儲結(jié)點(diǎn)時，即從可利用的棧的頂部取出棧頂結(jié)點(diǎn)；當(dāng)系統(tǒng)要釋放一個存儲結(jié)點(diǎn)時，將該結(jié)點(diǎn)空間放回到可利用棧的棧頂。 即在計算機(jī)中所有空閑的空間，均可以以結(jié)點(diǎn)的方式鏈接到可利用棧中，隨著其他線性鏈表中結(jié)點(diǎn)的插入與刪除，可利用棧處于動態(tài)變化之中，即可利用棧經(jīng)常要進(jìn)行退棧和入棧操作。 6）帶鏈的隊列 隊列也是線性表，也可利用鏈?zhǔn)酱鎯Y(jié)構(gòu)來進(jìn)行保存。 2．線性鏈表的基本運(yùn)算 線性鏈表包括的基本運(yùn)算： l 在鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個新元素 l 在鏈表中刪除包含指定元素的結(jié)點(diǎn) l 將兩個線性鏈表按要求合并成一個線性鏈表 l 將一個線性鏈表按要求進(jìn)行分解 l 逆轉(zhuǎn)線性鏈表 l 復(fù)制線性鏈表 l 線性鏈表的排序 l 線性鏈表的查找 1）線性鏈表中查找指定的元素 在線性鏈表中查找元素X：從頭指針指向的結(jié)點(diǎn)開始往后沿指針進(jìn)行掃描，直到后面已沒有結(jié)點(diǎn)或下一個結(jié)點(diǎn)的數(shù)據(jù)域為X為止。 元素的查找，經(jīng)常是為了進(jìn)行插入或刪除操作而進(jìn)行的，因此，在查找時，往往是需要記錄下該結(jié)點(diǎn)的前一個結(jié)點(diǎn)。 2）線性鏈表的插入 線性鏈表的插入即在鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表中插入一個新元素。 在線性鏈表中包含元素x的結(jié)點(diǎn)之前插入新元素b，插入過程： （1）從可利用棧中取得一個結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號為p，即取得的結(jié)點(diǎn)的存儲序號存放在變量p中。并置結(jié)點(diǎn)p的數(shù)據(jù)域為插入的元素值b。 （2）在線性鏈表中尋找包含元素x的前一個結(jié)點(diǎn)，該結(jié)點(diǎn)的存儲序號為q。 （3）將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后。具體的操作：首先，使結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后（即結(jié)點(diǎn)q的后件結(jié)點(diǎn)），然后，使結(jié)點(diǎn)q的指針域 內(nèi)容改為指向結(jié)點(diǎn)p。 線性鏈表的插入操作，新結(jié)點(diǎn)是為來自于可利用棧，因此不會造成線性表的溢出。同樣，由于可利用?？杀欢鄠€線性表利用，因此，不會造成存儲空間的浪費(fèi)，大家動態(tài)地共同使用存儲空間。 3）線性鏈表的刪除 線性鏈表的刪除，即是在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性表中刪除指定元素的結(jié)點(diǎn)。 操作方式： （1）在線性表中找到包含指定元素x的前一個結(jié)點(diǎn)p （2）將該結(jié)點(diǎn)p后的包含元素x的結(jié)點(diǎn)從線性鏈表中刪除，然后將被刪除結(jié)點(diǎn)的后一個結(jié)點(diǎn)q的地址提供給結(jié)點(diǎn)p的指針域，即將結(jié)點(diǎn)p指向結(jié)點(diǎn)q。 （3）將刪除的結(jié)點(diǎn)送回可利用棧。 從以上的刪除操作可見，刪除一個指定的元素，不需要移動其他的元素即可實(shí)現(xiàn)，這是順序存儲的線性表所不能實(shí)現(xiàn)的。同時，此操作還可更有效地利用計算機(jī)的存儲空間。 3．循環(huán)鏈表及其基本操作 在線性鏈表中，雖然對數(shù)據(jù)元素的插入和刪除操作比較簡單，但由于它對第一個結(jié)點(diǎn)和空表需要單獨(dú)處理，使得空表與非空表的處理不一致。 循環(huán)鏈表，即是采用另一種鏈接方式，它的特點(diǎn)如下： （1）在循環(huán)鏈表中增加一個表頭結(jié)點(diǎn)，其數(shù)據(jù)域為任意或根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。 （2）循環(huán)鏈表中最后一個結(jié)點(diǎn)的指針域不是空的，而是指向表頭結(jié)點(diǎn)。在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成一個環(huán)狀鏈。 在循環(huán)鏈表中，只要指出表中任何一個結(jié)點(diǎn)的位置，均可以從它開始掃描到所有的結(jié)點(diǎn)，而線性鏈表做不到，線性鏈表是一種單向的鏈表，只能按照指針的方向進(jìn)行掃描。 循環(huán)鏈表中設(shè)置了一個表頭結(jié)點(diǎn)，因此，在任何時候都至少有一個結(jié)點(diǎn)，因此空表與非空表的運(yùn)算相統(tǒng)一。 （六）樹與二叉樹 1．樹的基本概念 樹是一種簡單的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次結(jié)構(gòu)。在樹的圖形表示中，用直線連接兩端的結(jié)點(diǎn)，上端點(diǎn)為前件，下端點(diǎn)為后件。 在樹結(jié)構(gòu)中，每一個結(jié)點(diǎn)只有一個前件，稱為父結(jié)點(diǎn)。如A即為結(jié)點(diǎn)B、C、D的父結(jié)點(diǎn)。 沒有父結(jié)點(diǎn)的結(jié)點(diǎn)只有一個，稱為根結(jié)點(diǎn)。如上圖所示，結(jié)點(diǎn)A即為根結(jié)點(diǎn)。 每一個結(jié)點(diǎn)可以有多個后件，它們均稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。如結(jié)點(diǎn)G、H、I是結(jié)點(diǎn)D的子結(jié)點(diǎn)。 沒有后件的結(jié)點(diǎn)，稱為葉子結(jié)點(diǎn)。上圖中，葉子結(jié)點(diǎn)有：J、M、N、L、C、G、H、I。 在樹結(jié)構(gòu)中，一個結(jié)點(diǎn)所擁有的后件結(jié)點(diǎn)個數(shù)稱為該結(jié)點(diǎn)的度。例如，結(jié)點(diǎn)D的度為3，結(jié)點(diǎn)E的度為1等，按此原則，所有葉子結(jié)點(diǎn)的度均為0。 在樹中，所有結(jié)點(diǎn)中最大的度稱為該樹的度。上圖所示的樹中，所有結(jié)點(diǎn)中最大的度是3，所以該樹的度為3。 樹分層，根結(jié)點(diǎn)為第一層，往下依次類推。同一層結(jié)點(diǎn)的所有子結(jié)點(diǎn)均在下一層。如上圖：A結(jié)點(diǎn)在第1層，B、C、D結(jié)點(diǎn)在第2層；E、F、G、H、I在第3層；J、K、L在第4層；M、N在第5層。 樹的最大層次稱為樹的深度。上圖樹的深度為5。 在樹中，某結(jié)點(diǎn)的一個子結(jié)點(diǎn)為根構(gòu)成的樹稱作該結(jié)點(diǎn)的子樹。葉子結(jié)點(diǎn)沒有子樹。 在計算機(jī)中，可以用樹來表示算術(shù)表達(dá)式。原則如下： （1）表達(dá)式中每一個運(yùn)算符在樹中對應(yīng)一個結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn) （2）運(yùn)算符的每一個運(yùn)算對象在樹中為該運(yùn)算符結(jié)點(diǎn)的子樹（在樹中的順序為從左到右） （3）運(yùn)算對象中的單變量均為葉子結(jié)點(diǎn) 樹在計算機(jī)中用多重鏈表表示。多重鏈表中的每個結(jié)點(diǎn)描述了樹中對應(yīng)結(jié)點(diǎn)的信息，而每個結(jié)點(diǎn)中的鏈域（即指針域）個數(shù)將隨著樹中該結(jié)點(diǎn)的度而定義。 如果在樹中，每一個結(jié)點(diǎn)的子結(jié)點(diǎn)的個數(shù)不相同，因此在多重鏈中各結(jié)點(diǎn)的鏈域個數(shù)也不相同，會導(dǎo)致算法太復(fù)雜。因此，在樹中，常采用定長結(jié)點(diǎn)來表示樹中的每一個結(jié)點(diǎn)，即取樹的度作為每個結(jié)點(diǎn)的鏈域的個數(shù)。這樣，管理相對簡化了，但會造成空間的浪費(fèi)，因為有許多的結(jié)點(diǎn)存在空鏈域。 2．二叉樹及其基本性質(zhì) 1）二叉樹的定義 二叉樹的特點(diǎn)： l 非空二叉樹只有一個根結(jié)點(diǎn) l 每一個結(jié)點(diǎn)最多只有兩個子結(jié)點(diǎn)，且結(jié)點(diǎn)分左右。則一個結(jié)點(diǎn)最多可以有兩棵子樹，分別稱為左子樹和右子樹 在二叉樹中，每一個結(jié)點(diǎn)的度最大為2，即二叉樹的度為2。在二叉樹中，任何的子樹也均為二叉樹。 在二叉樹中，每一個結(jié)點(diǎn)的子樹被分為左子樹和右子樹。在二叉樹中，允許某一個結(jié)點(diǎn)只有左子樹或只有右子樹。如果一個結(jié)點(diǎn)既沒有左子樹，也沒有右子樹，則該結(jié)點(diǎn)為葉子結(jié)點(diǎn)。 2）二叉樹的性質(zhì) 性質(zhì)1：在二叉樹的第k層上，最多有2k-1（k≥1）個結(jié)點(diǎn)。 性質(zhì)2：深度為m的二叉樹最多有2m-1個結(jié)點(diǎn)。 性質(zhì)3：在任意一棵二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個。 性質(zhì)4：具有n個結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示log2n的整數(shù)部分。 3）滿二叉樹與完全二叉樹 （1）滿二叉樹 滿二叉樹的特點(diǎn)： 除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)。即在滿二叉樹中，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值，即在滿二叉樹上的第k層上有2k-1個結(jié)點(diǎn)。如下即為一棵滿二叉樹。 （2）完全二叉樹 特點(diǎn)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干個結(jié)點(diǎn)。 即如果從根結(jié)點(diǎn)開始，對二叉樹的結(jié)點(diǎn)自上而下、自左而右用自然數(shù)進(jìn)行連續(xù)編號，則深度為m、且有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為m的滿二叉樹中編號從1到n的結(jié)點(diǎn)一一對應(yīng)，則是完全二叉樹。 對于完全二叉樹，葉子結(jié)點(diǎn)只能在層次最大的兩層中出現(xiàn)；對于任何一個結(jié)點(diǎn)，若其右分支下的子樹結(jié)點(diǎn)的最大層次為p，則其分支下的子孫結(jié)點(diǎn)的最大層次為p或p+1。 完全二叉樹具有的性質(zhì)： 性質(zhì)5：具有n個結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1 性質(zhì)6：設(shè)完全二叉樹共有n個結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層次（每一層從左到右）用自然數(shù)1、2……、n給結(jié)點(diǎn)編號，對于編號為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)編號為INT(k/2)。 ② 若2k≤n，則編號為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號為2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（當(dāng)然也沒有右子結(jié)點(diǎn)） ③ 若2k+1≤n，則編號為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。 3．二叉樹的存儲結(jié)構(gòu) 二叉樹的存儲常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 存儲二叉樹中各元素的存儲結(jié)點(diǎn)由兩個部分組成：數(shù)據(jù)域和指針域。在二叉樹中，由于每個結(jié)點(diǎn)可有兩個子結(jié)點(diǎn)，則它的指針域有兩個：一個用于存儲該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲地址，即稱為左指針域；一個用于存儲指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲地址，稱為右指針域。 存儲結(jié)構(gòu)如下： Lchild Value Rchild i L(i) V(i) R(i) 即二叉樹的存儲結(jié)構(gòu)中每一個存儲結(jié)點(diǎn)都有兩個指針域，因此，二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉樹的鏈表。在二叉樹在存儲中，用一個頭指針指向二叉樹的根結(jié)點(diǎn)的存儲地址。 如圖所示的二叉樹： 如果我們將該二叉樹的所有結(jié)點(diǎn)順序編號，順序存放在存儲空間里，則它們在內(nèi)存空間中的存放方式是： i L(i) V(i) R(i) BTà 1 2 A 3 2 4 B 5 3 6 C 7 4 8 D 9 5 10 E 11 6 12 F 13 7 14 G 15 8 16 H 17 9 18 I 0 10 0 J 0 11 0 K 0 12 0 L 0 13 0 M 0 14 0 N 0 15 0 O 0 16 0 P 0 17 0 Q 0 18 0 R 0 當(dāng)然，對于滿二叉樹或完全二叉樹而言，也可采用順序存儲的方式，但順序存儲的方式不適合其他的二叉樹。 4．二叉樹的遍歷 二叉樹的遍歷即是不重復(fù)地訪問二叉樹的所有結(jié)點(diǎn)。 在遍歷二叉樹時，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，二叉樹的遍歷又可分為三種：前序遍歷、中序遍歷和后序遍歷。 1）前序遍歷 前序遍歷即先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。在遍歷左子樹和遍歷右子樹時，依然是先遍歷根結(jié)點(diǎn)，然后是左子樹，再是右子樹。 操作的具體方式： l 若二叉樹為空，則結(jié)束返回。 l 否則：訪問根結(jié)點(diǎn)?前序遍歷左子樹?前序遍歷右子樹 如上圖所示的完全二叉樹，它的前序遍歷結(jié)果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O 2）中序遍歷 中序遍歷，即先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后是遍歷右子樹。 具體的操作方式： l 若二叉樹為空，則結(jié)束返回。 l 否則：中序遍歷左子樹?訪問根結(jié)點(diǎn) ?中序遍歷右子樹 這里強(qiáng)調(diào)，在遍歷左子樹和右子樹時，仍然要采用中序遍歷的方法。 如上圖所示的完全二叉樹，它的中序遍歷結(jié)果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O 3）后序遍歷 后序遍歷，即選遍歷左子樹，然后是遍歷右子樹，最后訪問根結(jié)點(diǎn)。 具體的操作方式： l 若二叉樹為空，則結(jié)束返回。 l 否則：前序遍歷左子樹?前序遍歷右子樹?訪問根結(jié)點(diǎn) 如上圖所示的完全二叉樹，它的后序遍歷結(jié)果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A （七）查找技術(shù) 查找即是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。 1．順序查找 順序查找又稱順序搜索。一般是在線性表中查找指定的元素。 基本操作方法是： 從線性表的第一個元素開始，與被查元素進(jìn)行比較，相等則查找成功，否則繼續(xù)向后查找。如果所有的元素均查找完畢后都不相等，則該元素在指定的線性表中不存在。 順序查找的最好情況：要查找的元素在線性表的第一個元素，則查找效率最高；如果要查找的元素在線性表的最后或根本不存在，則查找需要搜索所有的線性表元素，這種情況是最差情況。 對于線性表而言，順序查找效率很低。但對于以下的線性表，也只能采用順序查找的方法： l 線性表為無序表，即表中的元素沒有排列不是按大小順序進(jìn)行排列的，這類線性表不管它的存儲方式是順序存儲還是鏈?zhǔn)酱鎯?，都只能按順序查找方式進(jìn)行查找 l 即使是有序線性表，如果采用鏈?zhǔn)酱鎯?，也只能采用順序查找方? 例如，現(xiàn)有線性表：7、2、1、5、9、4，要在序列中查找元素6，查找的過程是： l 整個線性表的長度為5 l 查找計次n=1，將元素6與序列的第一個7元素進(jìn)行比較，不等，繼續(xù)查找 l n=2，將6與第二個元素2進(jìn)行比較，不等，繼續(xù) l n=3，將6與第三個元素1進(jìn)行比較，不等，繼續(xù) l n=4，將6與第四個元素5進(jìn)行比較，不等，繼續(xù) l n=5，將6與第五個元素9進(jìn)行比較，不等，繼續(xù) l n=6，將6與第六個元素4進(jìn)行比較，不等，繼續(xù) l n=7，超出線性表的長度，查找結(jié)束，則該表中不存在要查找的元素。 2．二分查找 二分查找只適用于順序存儲的有序表。此處所述的有序表是指線性中的元素按值非遞減排列（即由小到大，但允許相鄰元素值相等）。 二分查找的方法如下： 將要查找的元素與有序序列的中間元素進(jìn)行比較： l 如果該元素比中間元素大，則繼續(xù)在線性表的后半部分（中間項以后的部分）進(jìn)行查找 l 如果要查找的元素的值比中間元素的值小，則繼續(xù)在線性表的前半部分（中間項以前的部分）進(jìn)行查找 這個查找過程一直按相同的順序進(jìn)行下去，一直到查找成功或子表長度為0（說明線性表中沒有要查找的元素） 有序線性表的二分法查找，條件是必須這個有序線性表的存儲方式是順序存儲的。它的查找效率比順序查找要高得多，它的最壞情況的查找次數(shù)是log2n次，而順序查找的最壞情況的查找次數(shù)是n次。 當(dāng)然，二分查找的方法也支持順序存儲的遞減序列的線性表。 有非遞減有序線性表：1、2、4、5、7、9，要查找元素6。查找的方法是： l 序列長度為n=6，中間元素的序號m=[(n+1)/2]=3 l 查找計次k=1，將元素6與中間元素即元素4進(jìn)行比較，不等，6>4 l 查找計次k=2，查找繼續(xù)在后半部分進(jìn)行，后半部分子表的長度為3，計算中間元素的序號：m=3+[(3+1)/2]=5，將元素與后半部分的中間項進(jìn)行比較，即第5個元素中的7進(jìn)行比較，不等，6<7 l 查找計次k=3，繼續(xù)查找在后半部分序列的前半部分子序列中查找，子表長度為1，則中間項序號即為m=3+[(1+1)/2]=4，即與第4個元素5進(jìn)行比較，不相等，繼續(xù)查找的子表長度為0，則查找結(jié)束 （八）排序技術(shù) 排序即是將一個無序的序列整理成按值非遞減順序排列的有序序列。在這里，我們討論的是順序存儲的線性表的排序操作。 1．交換類排序法 交換類排序法，即是借助于數(shù)據(jù)元素之間的互相交換進(jìn)行排序的方法。 1）冒泡排序法 冒泡排序法即是利用相鄰數(shù)據(jù)元素之間的交換逐步將線性表變成有序序列的操作方法。 操作過程如下： l 從表頭開始掃描線性表，在掃描過程中逐次比較相鄰兩個元素的大小，若相鄰兩個元素中前一個元素的值比后一個元素的值大，將兩個元素位置進(jìn)行交換，當(dāng)掃描完成一遍時，則序列中最大的元素被放置到序列的最后。 l 再繼續(xù)對序列從頭進(jìn)行掃描，這一次掃描的長度是序列長度減1，因為最大的元素已經(jīng)就位了，采用與前相同的方法，兩兩之間進(jìn)行比較，將次大數(shù)移到子序列的末尾。 l 按相同的方法繼續(xù)掃描，每次掃描的子序列的長度均比上一次減1，直至子序列的長度為1時，排序結(jié)束。 例如，有序列5、2、9、4、1、7、6，將該序列從小到大進(jìn)行排列。 采用冒泡排序法，具體操作步驟如下： 序列長度n=7 原序列 5 2 9 4 1 7 6 第一遍（從前往后） 5?? 2 9 4 1 7 6 2 5 9?? 4 1 7 6 2 5 4 9?? 1 7 6 2 3 4 1 9?? 7 6 2 5 4 1 7 9?? 6 第一遍結(jié)束后 2 5 4 1 7 6 9 第二遍（從前往后） 2 5?? 4 1 7 6 9 2 4 5?? 1 7 6 9 2 4 1 5 7?? 6 9 2 4 1 5 6 7 9 第二遍結(jié)束后 2 4 1 5 6 7 9 第三遍（從前往后） 2 4?? 1 5 6 7 9 2 1 4 5 6 7 9 第三遍結(jié)束 2 1 4 5 6 7 9 第四遍（從前往后） 2?? 1 4 5 6 7 9 1 2 4 5 6 7 9 第四遍結(jié)束 1 2 4 5 6 7 9 最后結(jié)果 1 2 4 5 6 7 9 掃描的次數(shù)，最多需要掃描n-1次，如果序列已經(jīng)就位，則掃描結(jié)束。測試是否已經(jīng)就位，可設(shè)置一個標(biāo)志，如果該次掃描沒有數(shù)據(jù)交換，則說明數(shù)據(jù)排序結(jié)束。 2）快速排序法 冒泡排序方法每次交換只能改變相鄰兩個元素之間的逆序，速度相對較慢。如果將兩個不相鄰的元素之間進(jìn)行交換，可以消除多個逆序。 快速排序的方法是： 從線性表中選取一個元素，設(shè)為T，將線性表后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果將線性表分成兩個部分（稱為兩個子表），T插入到其分界線的位置處，這個過程稱為線性表的分割。對過對線性表的一次分割，就以T為分界線，將線性表分成前后兩個子表，且前面子表中的所有元素均不大于T，而后面的所有元素均不小于T。 再將前后兩個子表再進(jìn)行相同的快速排序，將子表再進(jìn)行分割，直到所有的子表均為空，則完成快速排序操作。 在快速排序過程中，隨著對各子表不斷的進(jìn)行分割，劃分出的子表會越來越多，但一次又只能對一個子表進(jìn)行分割處理，需要將暫時不用的子表記憶起來，這里可用棧來實(shí)現(xiàn)。 對某個子表進(jìn)行分割后，可以將分割出的后一個子表的第一個元素與最后一個元素的位置壓入棧中，而繼續(xù)對前一個子表進(jìn)行再分割；當(dāng)分割出的子表為空時，可以從棧中退出一個子表進(jìn)行分割。 這個過程直到棧為空為止，說明所有子表為空，沒有子表再需分割，排序就完成。 2．插入類排序法 1）簡單插入排序 插入排序，是指將無序序列中的各元素依次插入到已經(jīng)有序的線性表中。 插入排序操作的思路：在線性表中，只包含第1個元素的子表，作為該有序表。從線性表的第2個元素開始直到最后一個元素，逐次將其中的每一個元素插入到前面的有序的子表中。 該方法與冒泡排序方法的效率相同，最壞的情況下需要n(n-1)/2次比較。 例如，有序列5、2、9、4、1、7、6，將該序列從小到大進(jìn)行排列。 采用簡單插入排序法，具體操作步驟如下： 序列長度n=7 5 2 9 4 1 7 6 -j=2 2 5 9 4 1 7 6 -j=3 2 5 9 4 1 7 6 -j=4 2 4 5 9 1 7 6 -j=5 1 2 4 5 9 7 6 -j=6 1 2 4 5 7 9 6 -j=7 插入排序后的結(jié)果 1 2 4 5 6 7 9 2）希爾排序法 希爾排序法的基本思想： 將整個無序序列分割成若干小的子序列分別進(jìn)行插入排序。 子序列的分割方法：將相隔某個增量h的元素構(gòu)成一個子序列，在排序的過程中，逐次減小這個增量，最后當(dāng)h減小到1時，再進(jìn)行一次插入排序操作，即完成排序。 增量序列一般取ht=n/2k(k=1,2,…,[log2n])，其中n為待排序序列的長度。 3．選擇類排序法 1）簡單選擇排序法 基本思路：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面，然后對后面的子表采用相同的方法，直到子表為空為止。 對于長度為n的序列，需要掃描n-1次，每一次掃描均找出剩余的子表中最小的元素，然后將該最小元素與子表的第一個元素進(jìn)行交換。 例如，有序列5、2、9、4、1、7、6，將該序列從小到大進(jìn)行排列。 采用簡單選擇排序法，具體操作步驟如下： 原序列 5 2 9 4 1 7 6 第一遍掃描 1 2 9 4 5 7 6 第二遍掃描 1 2 9 4 5 7 6 第三遍掃描 1 2 4 9 5 7 6 第四遍掃描 1 2 4 5 9 7 6 第五遍掃描 1 2 4 5 6 7 9 第六遍掃描 1 2 4 5 6 7 9 排序結(jié)果 1 2 4 5 6 7 9 2）堆排序法 堆排序法屬于選擇類排序方法。 堆的定義：具有n個元素的序列（h1,h2,…,hn），當(dāng)且僅當(dāng)滿足 （I=1,2,…,n/2）時稱之為堆。 本節(jié)只討論滿足前者條件的堆。 由堆的定義看，堆頂元素（即第一個元素）必為最大項。 可以用一維數(shù)組或完全二叉樹來表示堆的結(jié)構(gòu)。 用完全二叉樹表示堆時，樹中所有非葉子結(jié)點(diǎn)值均不小于其左右子樹的根結(jié)點(diǎn)的值，因此堆頂（完全二叉樹的根結(jié)點(diǎn)）元素必須為序列的n個元素中的最大項。 例如，有序列5、2、9、4、1、7、6，將該序列從小到大進(jìn)行排列。 利用堆排序法將該序列進(jìn)行排序。 操作方式即：先將無序堆的根結(jié)點(diǎn)5與左右子樹的根結(jié)點(diǎn)2、9進(jìn)行比較，5<9，將5與9進(jìn)行交換；整后，對左右子樹進(jìn)行堆調(diào)整，左子樹的根結(jié)點(diǎn)2小于其左葉子結(jié)點(diǎn)5，調(diào)整；右子樹的根結(jié)點(diǎn)5小于其左右子結(jié)點(diǎn)7和6，根據(jù)堆的要求，將5與7進(jìn)行調(diào)整。 根據(jù)堆的定義，可以得到堆排序的方法： （1）首先將一個無序序列建成堆 （2）然后將堆頂元素（序列中的最大項）與堆中最后一個元素交換（最大項應(yīng)該在序列的最后）。 三、本章應(yīng)考點(diǎn)撥 本章內(nèi)容在筆試中會出現(xiàn)5-6個題目，是公共基礎(chǔ)知識部分出題量比較多的一章，所占分值也比較大，約10分。 第二章 程序設(shè)計基礎(chǔ) 一、內(nèi)容要點(diǎn) （一）程序設(shè)計方法與風(fēng)格 程序設(shè)計方法：主要經(jīng)過了面向過程的結(jié)構(gòu)化程序設(shè)計和面向?qū)ο蟮某绦蛟O(shè)計方法。 程序設(shè)計風(fēng)格，是指編寫程序時所表現(xiàn)出來的特點(diǎn)、習(xí)慣和邏輯思路。通常，要求程序設(shè)計的風(fēng)格應(yīng)強(qiáng)調(diào)簡單和清晰，必須是可以讀的，可以理解的。 要形成良好的程序設(shè)計的風(fēng)格，應(yīng)考慮如下因素： 1．源程序文檔化 （1）符號名的命名：符號名的命名要具有一定的實(shí)際含義，便于對程序的理解，即通常說的見名思義； （2）程序注釋：正確的程序注釋能夠幫助他人理解程序。注釋一般包括序言性注釋和功能性注釋； （3）視覺組織：為了使程序一目了然，可以對程序的格式進(jìn)行設(shè)置，適當(dāng)?shù)赝ㄟ^空格、空行、縮進(jìn)等使程序?qū)哟吻逦? 2．?dāng)?shù)據(jù)說明方法 （1）數(shù)據(jù)說明的次序規(guī)范化； （2）說明語句中變量安排有序化； （3）使用注釋來說明復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。 3．語句的結(jié)構(gòu) （1）在一行內(nèi)只寫一條語句； （2）程序的編寫應(yīng)該優(yōu)先考慮清晰性； （3）除非對效率有特殊的要求，否則，應(yīng)做到清晰第一，效率第二； （4）首先保證程序的正確，然后再要求速度； （5）避免使用臨時變量使程序的可讀性下降； （7）盡量使用庫函數(shù)，即盡量使用系統(tǒng)提供的資源； （8）避免采用復(fù)雜的條件語句； （9）盡量減少使用“否定”條件的條件語句； （10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化； （11）要模塊化，使模塊功能盡可能單一化； （12）利用信息隱蔽，確保每一個模塊的獨(dú)立性； （13）從數(shù)據(jù)出發(fā)去構(gòu)造程序； （14）不要修補(bǔ)不好的程序，要重新編寫。 4．輸入和輸出 （1）對所有的輸入輸出數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性； （2）檢查輸入項的各種重要組合的合理性； （3）輸入格式要簡單，以使得輸入的步驟和操作盡可能簡單； （4）輸入數(shù)據(jù)時，應(yīng)允許自由格式； （5）應(yīng)允許缺省值； （6）輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標(biāo)志； （7）以交互式輸入輸出方式進(jìn)行輸入時，要在屏幕上使用提示符明確輸入的請求，同時在數(shù)據(jù)輸入過程中和輸入結(jié)束時，應(yīng)在屏幕上給出狀態(tài)信息； （8）當(dāng)程序設(shè)計語言對輸入格式有嚴(yán)格要求時，應(yīng)保持輸入格式與輸入語句的一致性；給所有的輸出加注釋，并設(shè)計輸出報表格式。 （二）結(jié)構(gòu)化程序設(shè)計 1．結(jié)構(gòu)化程序設(shè)計的原則 結(jié)構(gòu)化程序設(shè)計方法的主要原則：自頂而下、逐步求精，模塊化，限制使用goto語句。 1）自頂而下 程序設(shè)計時，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局，后考慮局部目標(biāo)。即先從最上層總目標(biāo)開始設(shè)計，逐步使問題具體化。 2）逐步求精 對復(fù)雜問題，應(yīng)設(shè)計一些子目標(biāo)作為過渡，逐步細(xì)化。 3）模塊化 一個復(fù)雜問題，都是由若干個稍簡單的問題構(gòu)成的。模塊化即是將復(fù)雜問題進(jìn)行分解，即將解決問題的總目標(biāo)分解成若干個分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每一個小目標(biāo)稱作一個模塊。 4）限制使用goto語句 goto語句可以提高效率，但對程序的可讀性、維護(hù)性都造成影響，因此應(yīng)盡量不用goto語句。 2．結(jié)構(gòu)化程序設(shè)計的基本結(jié)構(gòu)與特點(diǎn) 結(jié)構(gòu)化程序設(shè)計是程序設(shè)計的先進(jìn)方法和工具，采用結(jié)構(gòu)化程序設(shè)計可以使程序結(jié)構(gòu)良好、易讀、易理解、易維護(hù)。 1）順序結(jié)構(gòu) 順序結(jié)構(gòu)即是順序執(zhí)行的結(jié)構(gòu)，是按照程序語句行的自然順序，一條一條語句地執(zhí)行程序。 2）選擇結(jié)構(gòu) 選擇結(jié)構(gòu)又稱分支結(jié)構(gòu)，它包括簡單選擇和多分支選擇結(jié)構(gòu)。程序的執(zhí)行是根據(jù)給定的條件，選擇相應(yīng)的分支來執(zhí)行。 3）重復(fù)結(jié)構(gòu) 重復(fù)結(jié)構(gòu)又稱循環(huán)結(jié)構(gòu)，根據(jù)給定的條件，決定是否重復(fù)執(zhí)行某一相同的或類似的程序段。利用重復(fù)結(jié)構(gòu)可以大量簡化程序行。 3．結(jié)構(gòu)化程序設(shè)計原則和方法的應(yīng)用 1．使用程序設(shè)計語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯； 2．選用的控制結(jié)構(gòu)只允許有一個入口和一個出口； 3．程序語句組成容易識別的塊，每塊只有一個入口和一個出口； 4．復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn)； 5．語言中所有沒有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來模擬； 6．嚴(yán)格控制goto語句的使用： （1）用一個非結(jié)構(gòu)化的程序設(shè)計語言去實(shí)現(xiàn)一個結(jié)構(gòu)化的構(gòu)造； （2）若不使用goto語句會使功能模糊； （3）在某種可以改善而不是損害程序可讀性的情況下。 （三）面向?qū)ο蟮某绦蛟O(shè)計 1．關(guān)于面向?qū)ο蠓椒? 面向?qū)ο蠓椒ǖ谋举|(zhì)，是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實(shí)生活中常用的思維方法來認(rèn)識、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠反映問題域，即系統(tǒng)中的對象以及對象之間的關(guān)系能夠如實(shí)地反映問題域中固有事物及其關(guān)系。 面向?qū)ο蟮膬?yōu)點(diǎn)： 1）與人類習(xí)慣的思維方法一致 傳統(tǒng)的程序設(shè)計方法是以算法作為核心，將程序與過程相互獨(dú)立。 面向?qū)ο蠓椒ê图夹g(shù)是以對象為核心，對象是由數(shù)據(jù)和容許的操作組成的封裝體，與客觀實(shí)體有直接的對應(yīng)關(guān)系。對象之間通過傳遞消息互相聯(lián)系，以實(shí)現(xiàn)模擬世界中不同事物之間的聯(lián)系。 2）穩(wěn)定性好 面向?qū)ο蠓椒ɑ跇?gòu)造問題領(lǐng)域的對象模型，以對象為中心構(gòu)造軟件系統(tǒng)。它的基本方法是用對象模擬問題領(lǐng)域中的實(shí)體，以對象間的聯(lián)系刻畫實(shí)體間的聯(lián)系。 3）可重用性好 軟件的重用性是指在不同的軟件開發(fā)過程中重復(fù)使用相同或相似的軟件元素的過程。 4）易于開發(fā)大型軟件產(chǎn)品 在使用面向?qū)ο筮M(jìn)行軟件開發(fā)時，可以把大型產(chǎn)品看作是一系列本質(zhì)上相互獨(dú)立的小產(chǎn)品來處理，降低了技術(shù)難度，也使軟件開發(fā)的管理變得容易。 5）可維護(hù)性好 （1）利用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件穩(wěn)定性比較好 （2）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件比較容易修改 （3）用面向?qū)ο蟮姆椒ㄩ_發(fā)的軟件比較容易理解 （4）易于測試和調(diào)試 2．面向?qū)ο蠓椒ǖ幕靖拍? 1）對象 在面向?qū)ο蟪绦蛟O(shè)計方法中，對象是系統(tǒng)中用來描述客觀事物的一個實(shí)體，是構(gòu)成系統(tǒng)的一個基本單位，它由一組表示其靜態(tài)特征的屬性和它執(zhí)行的一組操作組成。 對象的基本特點(diǎn)： （1）標(biāo)識的唯一性 對象是可區(qū)分的，并且由對象的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分。 （2）分類性 指可以將具有相同屬性和操作的對象抽象成類。 （3）多態(tài)性 指同一個操作可以是不同對象的行為。 （4）封裝性 從外面看只能看到對象的外部特征，即只需知道數(shù)據(jù)的取值范圍和可以對該數(shù)據(jù)施加的操作，根本無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法。 （5）模塊獨(dú)立性好 對象是面向?qū)ο蟮能浖幕灸K，它是由數(shù)據(jù)及可以對這些數(shù)據(jù)施加的操作所組成的統(tǒng)一體，而且對象是以數(shù)據(jù)為中心的，操作圍繞對其數(shù)據(jù)所需做的處理來設(shè)置，沒有無關(guān)的操作。從模塊的獨(dú)立性考慮，對象內(nèi)容各種元素彼此相結(jié)合得很緊密，內(nèi)聚性強(qiáng)。 2）類和實(shí)例 將屬性、操作相似的對象歸為類。具有共同的屬性、共同的方法的對象的集合，即是類。 類是對象的抽象，它描述了屬于該對象的所有對象性質(zhì)，而一個對象則是其對應(yīng)類的一個實(shí)例。 3）消息 消息是一個實(shí)例與另一個實(shí)例之間傳遞的信息，它請求對象執(zhí)行某一處理或回答某一個要求的信息，它統(tǒng)一了數(shù)據(jù)流和控制流。 消息只包含傳遞者的要求，它告訴接受者需要做哪些處理，并不指示接受者怎樣去完成這些處理。 4）繼承 繼承是使用已有的類定義作為基礎(chǔ)建立新類的定義技術(shù)。已有的類可當(dāng)作基類來引用，則新類相應(yīng)地可作為派生類來引用。 繼承即是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。 5）多態(tài)性 對象根據(jù)所接受的消息而做出動作，同樣的消息被不同的對象接受時可導(dǎo)致完全不同的行動，該現(xiàn)象稱為多態(tài)性。 在面向?qū)ο蠹夹g(shù)中，多態(tài)性是指子類對象可以像父類對象那樣使用，同樣的消息可以發(fā)送給父類對象也可以發(fā)送給子類對象。 多態(tài)性機(jī)制增加了面向?qū)ο筌浖到y(tǒng)的靈活性，減少了信息冗余，而且顯著提高了軟件的可重用性可擴(kuò)充性。 三、本章應(yīng)考點(diǎn)撥 本章在考試中會出現(xiàn)約1個題目，所占分值大約占2分，是出題量較小的一章。本章內(nèi)容比較少，也很簡單，掌握住基本的概念就可以輕松應(yīng)對考試了，所以在這部分丟分，比較可惜。 第三章 軟件工程基礎(chǔ) 一、學(xué)習(xí)目標(biāo)與要求 1．了解軟件工程的基本概念； 2．了解軟件工程過程與軟件的生命周期，以及軟件工程的目標(biāo)和原則； 3．了解利用結(jié)構(gòu)化分析法進(jìn)行軟件工程中的需求分析的方法，并了解需求分析的方法和需要完成的任務(wù)； 4．了解數(shù)據(jù)流圖的使用方法； 5．了解如何利用結(jié)構(gòu)化設(shè)計方法進(jìn)行軟件設(shè)計，并了解軟件設(shè)計的一些常用用工具； 6．了解軟件測試的目的和方法，以及軟件測試的準(zhǔn)則，了解常用的軟件測試方法的區(qū)別和各自的功能與特點(diǎn)； 7．了解程序調(diào)試的方法和原則。 二、內(nèi)容要點(diǎn) （一）軟件工程基本概念 1．軟件定義與軟件特點(diǎn) 1）軟件的定義 與計算機(jī)系統(tǒng)的操作有關(guān)的計算機(jī)程序、規(guī)程、規(guī)則，以及可能有的文件、文檔及數(shù)據(jù)。 2）軟件的特點(diǎn) （1）軟件是一種邏輯實(shí)體，而不是物理實(shí)體，具有抽象性； （2）軟件的生產(chǎn)與硬件不同，