13 數(shù)據(jù)結構與算法.doc

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