13 數(shù)據(jù)結(jié)構(gòu)與算法.doc

武漢三維教育C語言考試研究中心網(wǎng)址：第一章數(shù)據(jù)結(jié)構(gòu)與算法第1頁共5頁第一章數(shù)據(jù)結(jié)構(gòu)與算法考點一：算法算法：是指解題方案的準確而完整的描述。算法的基本特征：(1)可行性：程序必須得到滿意的結(jié)果，所以要考慮算法的可行性；(2)確定性：算法中每一步都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；(3)有窮性：算法必須能在有限的時間內(nèi)做完，即能在執(zhí)行有限個步驟后終止；(4)擁有足夠的情報。算法的基本要素：(1)算法的控制結(jié)構(gòu)。(2)對數(shù)據(jù)對象的運算和操作；基本運算和操作包括：算術(shù)運算、邏輯運算、關(guān)系運算、數(shù)據(jù)傳輸。算法的3種基本控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。算法復(fù)雜度：(1)時間復(fù)雜度：指執(zhí)行算法所需要的計算工作量；(2)空間復(fù)雜度：指執(zhí)行這個算法所需要的內(nèi)存空間；指令系統(tǒng)：一個計算機系統(tǒng)能執(zhí)行的所有指令的集合；考點二：邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)的基本概念(1)數(shù)據(jù)結(jié)構(gòu)：指相互有關(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ù)元素的集合和定義在此集合中的若干關(guān)系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了數(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)，則可表示成B=（D,R）D=春季，夏季，秋季，冬季R=（春季，夏季）,（夏季，秋季），（秋季，冬季）3.存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示。一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接等存儲結(jié)構(gòu)。有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈式存儲結(jié)構(gòu)?？键c三：線性結(jié)構(gòu)與非線性結(jié)構(gòu)武漢三維教育C語言考試研究中心網(wǎng)址：第一章數(shù)據(jù)結(jié)構(gòu)與算法第2頁共5頁根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。(1)線性結(jié)構(gòu)必須滿足的兩個兩個條件：有且只有一個根結(jié)點；每一個結(jié)點最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)是線性結(jié)構(gòu)。(2)棧、隊列、串等都線性結(jié)構(gòu)。非線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。(3)線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：線性表中所有元素所占的存儲空間是連續(xù)的；線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。元素ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。線性表是由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。(4)順序表的運算：查找、插入、刪除?？键c四：棧和隊列棧：形象的比喻小學(xué)課本上講烏鴉喝水用的杯子。限定在一端進行插入與刪除的線性表，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧按照“先進后出”（FILO）或“后進先出”（LIFO）組織數(shù)據(jù)，棧具有記憶作用。用top表示棧頂位置，用bottom表示棧底。棧的基本運算：(1)插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。棧是支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)。隊列：形象比喻在食堂里打飯時排的長隊，先來先服務(wù)指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。Rear指針指向隊尾，front指針指向隊頭。當(dāng)表中沒有元素時稱為空隊列。隊列是“先進先出”（FIFO）或“后進后出”（LILO）的線性表。隊列運算包括：(1)入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。循環(huán)隊列：隊列的頭指針指向隊列的尾指針，循環(huán)隊列是隊列的順序存儲結(jié)構(gòu)?？键c五：鏈表在鏈式存儲方式中，要求每個結(jié)點由兩部分組成：(1)用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域，(2)用于存放指針，稱為指針域。其中指針用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件）。鏈式存儲方式既可用于表示線性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。1)線性鏈表線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表。武漢三維教育C語言考試研究中心網(wǎng)址：第一章數(shù)據(jù)結(jié)構(gòu)與算法第3頁共5頁在某些應(yīng)用中，對線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針，用以指向其前件結(jié)點；另一個稱為右指針，用以指向其后件結(jié)點。這樣的表稱為雙向鏈表。在線性鏈表中，各數(shù)據(jù)元素結(jié)點的存儲空間可以是不連續(xù)的，且各數(shù)據(jù)元素的存儲順序與邏輯順序可以不一致。在線性鏈表中進行插入與刪除，不需要移動鏈表中的元素。線性單鏈表中，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表。如果是雙向鏈表的兩指針：左指針（Llink）指向前件結(jié)點，右指針（Rlink）指向后件結(jié)點。線性鏈表的基本運算：查找、插入、刪除。2)帶鏈的棧棧也是線性表，也可以采用鏈式存儲結(jié)構(gòu)。帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結(jié)點，這種帶鏈的棧稱為可利用棧。考點六：二叉樹及其基本性質(zhì)1）二叉樹及其基本概念樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。具有以下兩個特點：非空二叉樹只有一個根結(jié)點；每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹和右子樹。度：結(jié)點的左右子樹的個數(shù)，每一個結(jié)點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，在二叉樹中，一個結(jié)點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。樹的度即為二叉樹中最大的度的數(shù)。葉子結(jié)點：既沒有左子樹也沒有右子樹的結(jié)點。例如，一個家族中的族譜關(guān)系如圖1-1所示：A有后代B，C；B有后代D，E；C有后代F；典型的二叉樹如圖1-1所示：父結(jié)點（根）在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個稱為樹的根結(jié)點。例如上圖，結(jié)點A是樹的根結(jié)點。子結(jié)點和葉子結(jié)點在樹的結(jié)構(gòu)中，每一個節(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。例如上圖，結(jié)點D、E、F都為葉子結(jié)點。度在樹結(jié)構(gòu)中，一個結(jié)點擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。例如上圖，根結(jié)點A和結(jié)點B的度為2，結(jié)點C的度為1，葉子結(jié)點D、E、F的度為0。所以，樹的度為2。深度定義一棵樹的根結(jié)點所在的層次為1，其他結(jié)點所在的層次等于它的父結(jié)點所在的層次加1。樹的最大層次稱為樹的深度。例如上圖，根結(jié)點A在第1層，結(jié)點B、C在第2層，結(jié)點D、E、F在第3層。該樹的深度為3。子樹在樹中，以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹稱為該結(jié)點的一棵子樹。ABCDEF武漢三維教育C語言考試研究中心網(wǎng)址：第一章數(shù)據(jù)結(jié)構(gòu)與算法第4頁共5頁1)二叉樹基本性質(zhì)二叉樹具有以下幾個性質(zhì)：性質(zhì)1：在二叉樹的第k層上，最多有2k-1（k1）個結(jié)點；性質(zhì)2：深度為m的二叉樹最多有2m-1個結(jié)點；性質(zhì)3：在任意一棵二叉樹中，度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個。性質(zhì)4：具有n個結(jié)點的二叉樹，其深度至少為log2n+1，其中l(wèi)og2n表示取log2n的整數(shù)部分。1）滿二叉樹與完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結(jié)點都有兩個子結(jié)點完全二叉樹：除最后一層外，每一層上的結(jié)點數(shù)均達到最大值；在最后一層上只缺少右邊的若干結(jié)點。2）二叉樹的遍歷二叉樹的遍歷：(1)前序遍歷（DLR），首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。例如，對圖1-1中的二叉樹進行前序遍歷的結(jié)果（或稱為該二叉樹的前序序列）為：A，B，D，E，C，F(xiàn)。(2)中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。例如，對圖1-1中的二叉樹進行中序遍歷的結(jié)果（或稱為該二叉樹的中序序列）為：D，B，E，A，C，F(xiàn)。(3)后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。例如，對圖1-1中的二叉樹進行后序遍歷的結(jié)果（或稱為該二叉樹的后序序列）為：D，E，B，F(xiàn)，C，A?？键c七：順序查找查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示查找失敗。例如，在一維數(shù)組21，46，24，99，57，77，86中，查找數(shù)據(jù)元素98，首先從第1個元素21開始進行比較，與要查找的數(shù)據(jù)不相等，接著與第2個元素46進行比較，以此類推，當(dāng)進行到與第4個元素比較時，它們相等，所以查找成功。如果查找數(shù)據(jù)元素100，則整個線性表掃描完畢，仍未找到與100相等的元素，表示線性表中沒有要查找的元素。在下列兩種情況下也只能采用順序查找：(1)如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，只能用順序查找。(2)即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找。(有序表，存儲的數(shù)據(jù)從小到大有規(guī)律存放)考點八：二分法查找二分法查找，也稱拆半查找，是一種高效的查找方法。能使用二分法查找的線性表必須滿足兩個條件：用順序存儲結(jié)構(gòu)；線性表是有序表。二分法查找只適用于順序存儲的有序表。例如，長度為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ù)查找，最后一次比較相等，查找成功。順序查找法每一次比較，只將查找范圍減少1，而二分法查找，每比較一次，可將查找范圍減少為原來的一半，效率大大提高。武漢三維教育C語言考試研究中心網(wǎng)址：第一章數(shù)據(jù)結(jié)構(gòu)與算法第5頁共5頁對于長度為n的有序線性表，在最壞情況下，二分法查找只需比較log2n次，而順序查找需要比較n次?？键c九：排序技術(shù)(1)交換類排序法冒泡排序法首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往后移動，最后最大者到了線性表的最后。然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最后最小者到了線性表的最前面。對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時已經(jīng)排好序。在最壞的情況下，冒泡排序需要比較次數(shù)為n(n-1)/2。快速排序法任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分