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

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