二級C語言考試基礎(chǔ)知識-第1章數(shù)據(jù)結(jié)構(gòu)與算法

1、考點 1算法的復雜度【考點精講】1算法的基本概念計算機算法為計算機解題的過程實際上是在實施某種算法。算法的基本特征：可行性、確定性、有窮性、擁有足夠的情報。基本運算和操作包括：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。算法的 3 種基本控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合。2算法復雜度算法復雜度包括時間復雜度和空間復雜度。名稱時間復雜度空間復雜度指執(zhí)行算法所需要的計算工作量指執(zhí)行這個算法所需要的內(nèi)存空間描述考點 2邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)【考點精講】1數(shù)據(jù)結(jié)構(gòu)的基本概念（1）數(shù)據(jù)結(jié)構(gòu)：

2、指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。（2）數(shù)據(jù)結(jié)構(gòu)研究的 3 個方面： 數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； 在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)； 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。2邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個數(shù)據(jù)元素的集合和定義在此集合中映了數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。一個數(shù)據(jù)結(jié)構(gòu)可以表示成：B=（D，R）其中 B 表示數(shù)據(jù)結(jié)構(gòu)。為了反映 D 中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。例如，如果把一年四季看作一個數(shù)據(jù)結(jié)構(gòu)，則可表示成1的若干關(guān)系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素

3、的集合，通常記為D；二是D上的關(guān)系，它反B =（D,R）D =春季，夏季，秋季，冬季R =（春季，夏季）,（夏季，秋季），（秋季，冬季）3存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。由于數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計算機存儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后件關(guān)系），在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接等存儲結(jié)構(gòu)。順序存儲方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰

4、的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，結(jié)點之間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。鏈式存儲結(jié)構(gòu)就是在每個結(jié)點中至少包含一個指針域，用指針來體現(xiàn)數(shù)據(jù)元素之間邏輯上的聯(lián)系。考點 3線性結(jié)構(gòu)和非線性結(jié)構(gòu)【考點精講】根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。（1）如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件： 有且只有一個根結(jié)點； 每一個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應是線性結(jié)構(gòu)。棧、隊列、串等都線性結(jié)構(gòu)。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。

5、數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。（2）線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點： 線性表中所有元素所占的存儲空間是連續(xù)的； 線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。元素 ai 的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k，ADR(a1)為第一個元素的地址，k 代表每個元素占的字節(jié)數(shù)。（3）順序表的運算：查找、插入、刪除。【考點精講】1棧的基本概念2考點 4棧棧（stack）是一種特殊的線性表，是限定只在一端進行插入與刪除的線性表。在棧中，一端是封閉的，既不允許進行插入元素，也不允許刪除元素；另一端是開口的，允許插入和刪除元素。通常稱插入、刪除的這一端為

6、棧頂，另一端為棧底。當表中沒有元素時稱為空棧。棧頂元素總是最后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的。例如，槍械的子彈匣就可以用來形象的表示棧結(jié)構(gòu)。子彈匣的一端是完全封閉的，最后被壓入彈匣的子彈總是最先被彈出，而最先被壓入的子彈最后才能被彈出。2棧的順序存儲及其運算棧的基本運算有三種：入棧、退棧與讀棧頂元素。入棧運算：在棧頂位置插入一個新元素。退棧運算：取出棧頂元素并賦給一個指定的變量。讀棧頂元素：將棧頂元素賦給一個指定的變量。考點 5隊列【考點精講】1隊列的基本概念隊列是只允許在一

7、端進行刪除，在另一端進行插入的順序表，通常將允許刪除的這一端稱為隊頭，允許插入的這一端稱為隊尾。當表中沒有元素時稱為空隊列。隊列的修改是依照先進先出的原則進行的，因此隊列也稱為先進先出的線性表，或者后進后出的線性表。例如：火車進遂道，最先進遂道的是火車頭，最后是火車尾，而火車出遂道的時候也是火車頭先出，最后出的是火車尾。若有隊列：Q =（q1，q2，qn）那么，q1 為隊頭元素（排頭元素），qn 為隊尾元素。隊列中的元素是按照 q1，q2，qn 的順序進入的，退出隊列也只能按照這個次序依次退出，即只有在 q1，q2，qn-1 都退隊之后，qn 才能退出隊列。因最先進入隊列的元素將最先出隊，所以

8、隊列具有先進先出的特性，體現(xiàn)“先來先服務”的原則。隊頭元素 q1 是最先被插入的元素，也是最先被刪除的元素。隊尾元素 qn 是最后被插入的元素，也是最后被刪除的元素。因此，與棧相反，隊列又稱為“先進先出”（First In First Out，簡稱 FIFO） 或“后進后出”（Last In Last Out，簡稱 LILO）的線性表。2隊列運算入隊運算是往隊列隊尾插入一個數(shù)據(jù)元素；退隊運算是從隊列的隊頭刪除一個數(shù)據(jù)元素。隊列的順序存儲結(jié)構(gòu)一般采用隊列循環(huán)的形式。循環(huán)隊列 s=0 表示隊列空；s=1 且 front=rear 表示隊列滿。計算循環(huán)隊列的元素個數(shù)：“尾指針減頭指針”，若為負數(shù)，再

9、加其容量即可。3考點 6鏈表【考點精講】在鏈式存儲方式中，要求每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件）。鏈式存儲方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。（1）線性鏈表線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表。在某些應用中，對線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針，用以指向其前件結(jié)點；另一個稱為右指針，用以指向其后件結(jié)點。這樣的表稱為雙向鏈表。在線性鏈表中，各數(shù)據(jù)元素結(jié)點的存儲空間可以是不連續(xù)的，且各數(shù)據(jù)元素的存儲順序與邏輯順序可以不一致。在線性鏈表中進行插入與刪除，不需要

10、移動鏈表中的元素。線性單鏈表中，HEAD 稱為頭指針，HEAD=NULL（或 0）稱為空表。如果是雙項鏈表的兩指針：左指針（Llink）指向前件結(jié)點，右指針（Rlink）指向后件結(jié)點。線性鏈表的基本運算：查找、插入、刪除。（2）帶鏈的棧棧也是線性表，也可以采用鏈式存儲結(jié)構(gòu)。帶鏈的?？梢杂脕硎占嬎銠C存儲空間中所有空閑的存儲結(jié)點，這種帶鏈的棧稱為可利用棧。考點 7二叉樹及其基本性質(zhì)【考點精講】1二叉樹及其基本概念二叉樹是一種很有用的非線性結(jié)構(gòu)，具有以下兩個特點：非空二叉樹只有一個根結(jié)點；每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹和右子樹。在二叉樹中，每一個結(jié)點的度最大為 2，即所有子樹（

11、左子樹或右子樹）也均為二叉樹。另外，二叉樹中的每個結(jié)點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結(jié)點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結(jié)點既沒有左子樹也沒有右子樹時，該結(jié)點即為葉子結(jié)點。例如，一個家族中的族譜關(guān)系如圖 1-1 所示：A 有后代 B，C；B 有后代 D，E；C 有后代 F；典型的二叉樹如圖 1-1 所示：4下面就圖 1-1 詳細講解二叉樹的一些基本概念。圖 1-1 族譜二叉樹2二叉樹基本性質(zhì)二叉樹具有以下幾個性質(zhì)：性質(zhì) 1：在二叉樹的第 k 層上，最多有 2k-1（k1）個結(jié)點；性質(zhì) 2：深度為 m 的二叉樹最多有 2m-1 個結(jié)點；性質(zhì) 3

12、：在任意一棵二叉樹中，度為 0 的結(jié)點（即葉子結(jié)點）總是比度為 2 的結(jié)點多一個。性質(zhì) 4：具有 n 個結(jié)點的二叉樹，其深度至少為log2n+1，其中l(wèi)og2n表示取 log2n 的整數(shù)部分。3滿二叉樹與完全二叉樹滿二叉樹是指這樣的一種二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點。在滿二叉樹中，每一層上的結(jié)點數(shù)都達到最大值，即在滿二叉樹的第 k 層上有 2k-1 個結(jié)點，且深度為 m 的滿二叉樹有 2m1個結(jié)點。完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。對于完全二叉樹來說，葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)：對于任何一

13、個結(jié)點，若其右分支下的子孫結(jié)點的最大層次為 p，則其左分支下的子孫結(jié)點的最大層次或為 p，或為 p+1。完全二叉樹具有以下兩個性質(zhì)：性質(zhì) 5：具有 n 個結(jié)點的完全二叉樹的深度為log2n+1。性質(zhì) 6：設(shè)完全二叉樹共有 n 個結(jié)點。如果從根結(jié)點開始，按層次（每一層從左到右）用自然數(shù) 1，2，n 給結(jié)點進行編號，則對于編號為 k（k=1，2，n）的結(jié)點有以下結(jié)論：若 k=1，則該結(jié)點為根結(jié)點，它沒有父結(jié)點；若 k1，則該結(jié)點的父結(jié)點編號為 INT（k/2）。若 2kn，則編號為 k 的結(jié)點的左子結(jié)點編號為 2k；否則該結(jié)點無左子結(jié)點（顯然也沒有右子結(jié)點）。若 2k+1n，則編號為 k 的結(jié)點的

14、右子結(jié)點編號為 2k+1；否則該結(jié)點無右子結(jié)點。考點 8二叉樹的遍歷【考點精講】5父結(jié)點（根）在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。例如，在圖 1-1 中，結(jié)點 A 是樹的根結(jié)點。子結(jié)點和葉子結(jié)點在樹結(jié)構(gòu)中，每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。例如，在圖 1-1 中，結(jié)點 D，E，F(xiàn) 均為葉子結(jié)點。度在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。例如，在圖 1-1 中，根結(jié)點 A 和結(jié)點 B 的度為 2，結(jié)點 C 的度為 1，葉子結(jié)點 D，E，F(xiàn) 的度為 0

15、。所以，該樹的度為 2。深度定義一棵樹的根結(jié)點所在的層次為 1，其他結(jié)點所在的層次等于它的父結(jié)點所在的層次加 1。樹的最大層次稱為樹的深度。例如，在圖 1-1 中，根結(jié)點 A 在第 1 層，結(jié)點 B，C 在第 2 層，結(jié)點 D，E，F(xiàn) 在第 3 層。該樹的深度為 3。子樹在樹中，以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵子樹。在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和后序遍歷。（1）前序遍歷：先訪問根結(jié)點、然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子

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

17、，B， F，C，A。考點 9順序查找【考點精講】查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示查找失敗。例如，在一維數(shù)組21，46，24，99，57，77，86中，查找數(shù)據(jù)元素 98，首先從第 1 個元素 21 開始進行比較，與要查找的數(shù)據(jù)不相等，接著與第 2 個元素 46 進行比較，以此類推，當進行到與第 4 個元素比較時，它們相等，所以查找成功。如果查找數(shù)據(jù)元素 100，則整個線性表掃描完畢，仍未找到與 100 相等的元素，表示線性表中

18、沒有要查找的元素。在下列兩種情況下也只能采用順序查找：（1）如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，只能用順序查找。（2）即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找?？键c 10二分法查找【考點精講】二分法查找，也稱拆半查找，是一種高效的查找方法。能使用二分法查找的線性表必須滿足兩個條件：用順序存儲結(jié)構(gòu)；線性表是有序表。在本書中，為了簡化問題，而更方便討論，“有序”是特指元素按非遞減排列，即從小到大排列，但允許相鄰元素相等。下一節(jié)排序中，有序的含義也是如此。對于長度為 n 的有序線性表，利用二分法查找元素 X 的過程如下。6步驟 1：將 X 與線性表的中間項比較：

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