全國(guó)計(jì)算機(jī)等級(jí)考試《數(shù)據(jù)結(jié)構(gòu)》講解

全國(guó)計(jì)算機(jī)等級(jí)考試《數(shù)據(jù)結(jié)構(gòu)》講解全國(guó)計(jì)算機(jī)等級(jí)考試《數(shù)據(jù)結(jié)構(gòu)》講解全國(guó)計(jì)算機(jī)等級(jí)考試《數(shù)據(jù)結(jié)構(gòu)》講解資料僅供參考文件編號(hào)：2022年4月全國(guó)計(jì)算機(jī)等級(jí)考試《數(shù)據(jù)結(jié)構(gòu)》講解版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：心之所向，所向披靡第一章數(shù)據(jù)結(jié)構(gòu)與算法§1概述一、基本概念數(shù)據(jù)是對(duì)客觀事物所進(jìn)行的描述，這種描述是采用了計(jì)算機(jī)系統(tǒng)能夠識(shí)別、存儲(chǔ)和處理的形式來(lái)進(jìn)行的。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。（在不同的場(chǎng)合又稱(chēng)結(jié)點(diǎn)、記錄等）數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。在數(shù)據(jù)結(jié)構(gòu)學(xué)科中研究的對(duì)象是數(shù)據(jù)元素，而不討論數(shù)據(jù)項(xiàng)間的構(gòu)成和關(guān)系。數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，即數(shù)據(jù)集合的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。抽象化地描述數(shù)據(jù)元素之間的相互關(guān)系稱(chēng)為數(shù)據(jù)的邏輯結(jié)構(gòu)，它包含兩方面的要素：一是數(shù)據(jù)元素的集合D，二是在D上的一組運(yùn)算和相應(yīng)的運(yùn)算規(guī)則或簡(jiǎn)稱(chēng)為關(guān)系R。數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu)（也稱(chēng)為存儲(chǔ)結(jié)構(gòu)），一般來(lái)說(shuō)，一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和哈希存儲(chǔ)等形式。數(shù)據(jù)結(jié)構(gòu)學(xué)科主要研究如下三個(gè)方面的內(nèi)容：①數(shù)據(jù)的邏輯結(jié)構(gòu)；②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；③對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，即算法的設(shè)計(jì)。二、算法算法是對(duì)特定問(wèn)題求解步驟的描述，它是指令的有限序列。算法的基本特征：①有窮性；②確定性；③可行性；④0個(gè)或多個(gè)輸入；⑤1個(gè)或多個(gè)輸出。算法的基本要素：①對(duì)數(shù)據(jù)的運(yùn)算和操作：基本運(yùn)算和操作包括算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算和數(shù)據(jù)傳輸；②算法的控制結(jié)構(gòu)：基本的控制結(jié)構(gòu)包括：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。算法設(shè)計(jì)的基本方法：①列舉法；②歸納法；③遞推；④遞歸；⑤半遞推技術(shù)；⑥回溯法。算法復(fù)雜度（性）主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。所謂時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。一般選取一個(gè)標(biāo)準(zhǔn)操作，找出隨著問(wèn)題規(guī)模n的變化，算法所執(zhí)行標(biāo)準(zhǔn)操作的運(yùn)算次數(shù)與其之間的函數(shù)關(guān)系f(n)，以f(n)的數(shù)量級(jí)O(n)來(lái)表示時(shí)間復(fù)雜度T(n)。常見(jiàn)的時(shí)間復(fù)雜度有：線性級(jí)O(n)，平方級(jí)O(n2)，對(duì)數(shù)級(jí)O(log2n)和指數(shù)級(jí)O(2n)等。分析某算法的時(shí)間復(fù)雜度時(shí)，有時(shí)還從最好情況、最壞情況、平均情況等方面進(jìn)行全面比較。所謂空間復(fù)雜度是指執(zhí)行算法所需要的存儲(chǔ)空間的大小。一般也是問(wèn)題規(guī)模的一個(gè)函數(shù)，取其數(shù)量級(jí)表示為O(n)。通常分析算法所需輔助空間的最大情況?！?線性表一、線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)滿足：①有且僅有一個(gè)根結(jié)點(diǎn)；②每一個(gè)結(jié)點(diǎn)最多有一個(gè)直接前趨結(jié)點(diǎn)，也最多有一個(gè)直接后繼結(jié)點(diǎn)；③在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后，還是線性結(jié)構(gòu)。線性結(jié)構(gòu)元素之間是一對(duì)一的聯(lián)系。典型的線性結(jié)構(gòu)有線性表、棧、隊(duì)列、字符串等。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱(chēng)之為非線性結(jié)構(gòu)。典型的非線結(jié)構(gòu)有樹(shù)（一對(duì)多的聯(lián)系）、圖（多對(duì)多的聯(lián)系）等。二、線性表線性表是由n（n>=0）個(gè)數(shù)據(jù)元素組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)（首元素）外，有且只有一個(gè)前趨，除了最后一個(gè)（尾元素）外，有且僅有一個(gè)后繼。即線性表或是一個(gè)空表，或可表示為：（a1,a2,……,ai,……,an）其中ai是性質(zhì)相同的數(shù)據(jù)元素，也稱(chēng)為線性表中的一個(gè)結(jié)點(diǎn)。線性表的長(zhǎng)度，即表中的元素個(gè)數(shù)n，當(dāng)n=0時(shí)稱(chēng)為空表。三、線性表的順序存儲(chǔ)結(jié)構(gòu)（順序表）線性表的順序存儲(chǔ)結(jié)構(gòu)的基本特點(diǎn)：①線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的（一般用數(shù)組實(shí)現(xiàn)）；②線性表中每個(gè)元素在存儲(chǔ)空間中是按邏輯順序存放的，即用物理上的相鄰關(guān)系來(lái)體現(xiàn)邏輯上的相鄰關(guān)系。線性表的隨機(jī)存取地址計(jì)算公式為： ADD(ai)=ADD(a1)+(i-1)*k這里ADD(ai)是第i元素的地址，k是每個(gè)元素占用空間字節(jié)數(shù)。線性表上的主要運(yùn)算：①線性表的插入；②線性表的刪除；③線性表的查找；④線性表的排序；⑤線性表的分解；⑥線性表的合并；⑦線性表的復(fù)制；⑧線性表的逆轉(zhuǎn)。四、線性表的插入運(yùn)算在長(zhǎng)度為n的線性表(a1,a2,…,ai,…,an)的第i元素ai之前插入一個(gè)新元素x后得到的長(zhǎng)度為n+1的線性表為(a1,a2,…,x,ai,…,an)。實(shí)現(xiàn)方法：要在第i（1<=i<.n）元素之前插入一個(gè)新元素x，首先要從最后一個(gè)（即第n個(gè)）元素開(kāi)始，直到第i元素之間的n-i+1個(gè)元素依次向后移動(dòng)一個(gè)位置，移動(dòng)結(jié)束后，在第i位置寫(xiě)入新元素x。插入結(jié)束后，表長(zhǎng)度就增加了1。插入操作算法的時(shí)間復(fù)雜度分析：如果插入的位置在第n個(gè)元素之前，則只需將第n元素后移，這是最好情況；如果插入的位置在第1個(gè)元素之前，則n個(gè)元素都要后移，這是最壞情況；在等概情況下（即在任何位置插入的機(jī)率相同）平均移動(dòng)元素個(gè)數(shù)為n/2。五、線性表的刪除運(yùn)算在長(zhǎng)度為n的線性表(a1,a2,…,ai,…,an)中刪除第i元素ai后，變?yōu)殚L(zhǎng)度為n-1的線性表(a1,a2,…,ai-1,ai+1…,an)。實(shí)現(xiàn)方法：要?jiǎng)h除第i（1<=i<.n）元素，首先要從第i+1元素開(kāi)始，直到最后一個(gè)（即第n個(gè)）元素之間的n-i個(gè)元素依次向前移動(dòng)一個(gè)位置。刪除結(jié)束后，表長(zhǎng)度減1。刪除操作算法的時(shí)間復(fù)雜度分析：與插入操作類(lèi)似，平均情況下需要移動(dòng)表中一半的元素。兩種操作的算法時(shí)間復(fù)雜度都可記作O(n)。六、線性表順序存儲(chǔ)結(jié)構(gòu)的適用場(chǎng)合線性表的順序存儲(chǔ)結(jié)構(gòu)對(duì)于小線性表或者表中元素不常變動(dòng)的線性表來(lái)說(shuō)是合適的，因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)比較簡(jiǎn)單且易于隨機(jī)讀??；但這種順序存儲(chǔ)方式對(duì)于元素需要變動(dòng)的大線性表就不太適合了，因?yàn)椴迦牒蛣h除操作的效率比較低。§3棧和隊(duì)列棧和隊(duì)列都是運(yùn)算受限的線性表，各自又有自身的特點(diǎn)。一、棧的概念棧（也稱(chēng)堆棧）是限定只能在表的一端進(jìn)行插入和刪除的線性表。它按照“后進(jìn)先出”（LIFO）的原則組織數(shù)據(jù)。表中允許插入和刪除的一端叫做棧頂，表中的固定端叫做棧底。二、棧的順序存儲(chǔ)方式（順序棧）一般用一維數(shù)組S[m]作為棧的存儲(chǔ)空間，其中m為棧的最大容量。設(shè)置棧頂指針top指向下次進(jìn)棧的位置。判空條件為：top==0；判滿條件為：top==m。三、棧的基本運(yùn)算1、入棧：先判滿，若棧滿不能入棧，發(fā)生“上溢”錯(cuò)誤；不滿時(shí)將新元素插入到棧頂位置后，修改棧頂指針top++。2、出棧：先判空，若?？詹荒艹鰲?，發(fā)生“下溢”錯(cuò)誤；非空時(shí)修改棧頂指針top--，將棧頂元素賦給一個(gè)指定的變量。3、讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量，棧頂指針不變。當(dāng)棧為空時(shí)，讀棧頂元素操作失敗。四、隊(duì)列的概念隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。它按照“先進(jìn)先出”（FIFO）的原則組織數(shù)據(jù)。表中允許插入的一端叫做隊(duì)尾，允許刪除的一端叫做隊(duì)頭。五、隊(duì)列的順序存儲(chǔ)方式（順序隊(duì)列）一般用一維數(shù)組Q[m]作為隊(duì)列的存儲(chǔ)空間，其中m為隊(duì)列的最大容量。設(shè)置隊(duì)尾指針rear指向隊(duì)尾元素的位置，設(shè)置隊(duì)頭指針front指向隊(duì)頭元素的前一位置。為了克服“假溢出”現(xiàn)象采用循環(huán)隊(duì)列，即把一維數(shù)組Q[m]想象成首尾相接的循環(huán)數(shù)組，設(shè)想Q[0]接在Q[m-1]之后。判空條件為：rear==front；判滿條件為：(rear+1)modm==front。六、隊(duì)列的基本運(yùn)算1、入隊(duì)：先判滿，若隊(duì)列滿則不能入隊(duì)，發(fā)生“上溢”錯(cuò)誤；隊(duì)列不滿時(shí)，修改rear為(rear+1)modm，然后把新元素插入到rear位置；2、出隊(duì)：先判空，若隊(duì)列空則不能出隊(duì)，發(fā)生“下溢”錯(cuò)誤；隊(duì)列非空時(shí)，修改front為(front+1)modm，然后把隊(duì)頭元素讀入到指定的變量中；3、求隊(duì)列長(zhǎng)度：即求隊(duì)列中元素的個(gè)數(shù)，(rear-front+m)modm?！?線性鏈表線性表的順序存儲(chǔ)方式有結(jié)構(gòu)簡(jiǎn)單、可以隨機(jī)存取等優(yōu)點(diǎn)，但也存在兩大缺點(diǎn)：①插入或刪除操作時(shí)，需要移動(dòng)大量元素，效率低；②對(duì)于長(zhǎng)度可變的線性表，要預(yù)先分配（靜態(tài)分配）足夠的空間，這是很困難的。分配太大可能使部分空間長(zhǎng)期閑置不用，分配太小會(huì)造成表的容量難以擴(kuò)充。為了克服以上缺點(diǎn)，可以采用鏈?zhǔn)酱鎯?chǔ)方式，實(shí)現(xiàn)動(dòng)態(tài)分配。線性表的鏈?zhǔn)酱鎯?chǔ)稱(chēng)為線性鏈表。線性鏈表中各個(gè)元素（結(jié)點(diǎn)）的存儲(chǔ)空間可以連續(xù)也可以不連續(xù)，根據(jù)表的使用情況可以隨時(shí)申請(qǐng)和撤消元素占用空間。一、結(jié)點(diǎn)結(jié)構(gòu)datanext表中的每個(gè)元素除了存儲(chǔ)自身信息外，增設(shè)一個(gè)指示后繼元素地址的指針。在用C語(yǔ)言實(shí)現(xiàn)時(shí)可以定義為結(jié)構(gòu)體類(lèi)型。由于每個(gè)結(jié)點(diǎn)都記下了后繼結(jié)點(diǎn)的地址（最后一個(gè)結(jié)點(diǎn)的指針為空指針），整個(gè)表就構(gòu)成了一個(gè)鏈。為了找到這個(gè)鏈表，應(yīng)設(shè)一個(gè)頭指針（head）指向表頭結(jié)點(diǎn)。要對(duì)鏈表進(jìn)行操作，一般總要從頭指針出發(fā)，所以鏈?zhǔn)浇Y(jié)構(gòu)是順序存取結(jié)構(gòu)。二、單鏈表表中每個(gè)結(jié)點(diǎn)只用一個(gè)指針，指向后繼結(jié)點(diǎn)。又分為不帶頭結(jié)點(diǎn)的單鏈表和帶頭結(jié)點(diǎn)的單鏈表（增設(shè)表頭結(jié)點(diǎn)，該結(jié)點(diǎn)不含數(shù)據(jù)域，只有一個(gè)指向第一個(gè)表結(jié)點(diǎn)的指針。使得以空表和非空表的操作實(shí)現(xiàn)了統(tǒng)一）。三、循環(huán)鏈表鏈表中尾結(jié)點(diǎn)的指針不為空，而是指向表頭結(jié)點(diǎn)，這樣從表中任何一個(gè)結(jié)點(diǎn)出發(fā)都可以訪問(wèn)到表中其它所有的結(jié)點(diǎn)。四、雙向循環(huán)鏈表鏈表中每個(gè)結(jié)點(diǎn)設(shè)兩個(gè)指針域（可稱(chēng)為左指針llink和右指針rlink），分別指向前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)，表頭結(jié)點(diǎn)的左指針指向尾結(jié)點(diǎn)，表尾結(jié)點(diǎn)的右指針指向頭結(jié)點(diǎn)。llinkdatarlink五、鏈?zhǔn)綏５逆準(zhǔn)浇Y(jié)構(gòu)和單鏈表存儲(chǔ)結(jié)構(gòu)基本相同，單鏈表的頭指針含義為棧的棧頂指針。插入和刪除結(jié)點(diǎn)只能通過(guò)棧頂指針在棧頂端進(jìn)行。六、鏈?zhǔn)疥?duì)列隊(duì)列的鏈?zhǔn)浇Y(jié)構(gòu)也和單鏈表的存儲(chǔ)結(jié)構(gòu)基本相同，不過(guò)鏈?zhǔn)疥?duì)列有兩個(gè)指針，一個(gè)隊(duì)頭指針，一個(gè)隊(duì)尾指針。七、線性鏈表主要基本運(yùn)算①查找結(jié)點(diǎn)：線性鏈表的查找過(guò)程是從頭指針（或鏈?zhǔn)綏５臈ｍ斨羔?、或鏈?zhǔn)疥?duì)列的隊(duì)頭指針）指向的結(jié)點(diǎn)開(kāi)始，沿指針進(jìn)行掃描，直到找到下一結(jié)點(diǎn)的數(shù)據(jù)域?yàn)椴檎抑祒或已無(wú)后繼結(jié)點(diǎn)為止。②插入結(jié)點(diǎn)：先向系統(tǒng)申請(qǐng)一個(gè)新結(jié)點(diǎn)（由指針p指向），并賦值；然后利用查找算法找到待插入位置的前一結(jié)點(diǎn)的指針q；修改兩個(gè)指針即可：先將p指向q的后繼結(jié)點(diǎn)，再將p掛接在q的后面。（與順序存儲(chǔ)結(jié)構(gòu)的插入操作的最大區(qū)別：一是可隨時(shí)申請(qǐng)新結(jié)點(diǎn)空間，無(wú)需判滿；二是只修改兩個(gè)指針，無(wú)需移動(dòng)結(jié)點(diǎn)）。③刪除結(jié)點(diǎn)：先判空，對(duì)非空表利用查找算法找到待刪除位置的前一結(jié)點(diǎn)的指針q，用另一指針p暫時(shí)保存q的后繼結(jié)點(diǎn)（即待刪除結(jié)點(diǎn)），然后把p結(jié)點(diǎn)的后繼鏈直接掛接在q的后面。最后釋放p結(jié)點(diǎn)所分配的內(nèi)存空間。（與順序存儲(chǔ)結(jié)構(gòu)的刪除操作的最大區(qū)別是，只修改一個(gè)指針，無(wú)需移動(dòng)結(jié)點(diǎn)）?！?樹(shù)與二叉樹(shù)樹(shù)型結(jié)構(gòu)是非線性結(jié)構(gòu)，是一種以分支關(guān)系定義的層次結(jié)構(gòu)，體現(xiàn)數(shù)據(jù)元素之間的“一對(duì)多”的聯(lián)系。一、樹(shù)的基本概念1、基本術(shù)語(yǔ)：根結(jié)點(diǎn)，父結(jié)點(diǎn)，子結(jié)點(diǎn)，葉子結(jié)點(diǎn)，結(jié)點(diǎn)的度，樹(shù)的度，樹(shù)的深度，子樹(shù)，空樹(shù)，有序樹(shù)，無(wú)序樹(shù)，森林，樹(shù)的表示法。2、樹(shù)的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)。3、樹(shù)的應(yīng)用：表示算術(shù)表達(dá)式，二叉排序樹(shù)，哈夫曼樹(shù)等。二、二叉樹(shù)及其特點(diǎn)1、二叉樹(shù)的遞歸定義：二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，這個(gè)集合或是空，或者是由一個(gè)根結(jié)點(diǎn)和兩棵分別稱(chēng)為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)組成。2、二叉樹(shù)的特點(diǎn)：非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)（度只能是0、1、2）且嚴(yán)格區(qū)分是左子樹(shù)還是右子樹(shù)（即二叉樹(shù)是有序樹(shù)）。3、二叉樹(shù)的五種基本形態(tài)①空二叉樹(shù)②只有一個(gè)根結(jié)點(diǎn)③右子樹(shù)為空④左子樹(shù)為空⑤左、右子樹(shù)均非空。三、二叉樹(shù)的基本性質(zhì)1、在二叉樹(shù)的第i層上，最多有2i-1（i>=1）個(gè)結(jié)點(diǎn)。2、深度為k的二叉樹(shù)中結(jié)點(diǎn)總數(shù)最多為2k-1（k>=1）。3、對(duì)任意的一棵二叉樹(shù)，度為0的結(jié)點(diǎn)（即葉結(jié)點(diǎn)）數(shù)n0總比度為2的結(jié)點(diǎn)數(shù)n2多1個(gè)，即n0=n2+1。滿二叉樹(shù)：深度為k的二叉樹(shù)共有2k-1個(gè)結(jié)點(diǎn)（即性質(zhì)2中允許的最大值）。完全二叉樹(shù)：深度為k的完全二叉樹(shù)，其前k-1層是一棵滿二叉樹(shù)，最后一層（第k層）上結(jié)點(diǎn)都盡量排在靠左的位置上。滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。4、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1。（這里的[]表示取整）5、對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果從根結(jié)點(diǎn)開(kāi)始，按層序（每層從左到右）用自然數(shù)進(jìn)行編號(hào)，則對(duì)編號(hào)為k的結(jié)點(diǎn)（1<=k<=n）有以下結(jié)論：①若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為[k/2]；若k=1，則它是根結(jié)點(diǎn)，無(wú)父結(jié)點(diǎn)。②若2k<=n，則該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)編號(hào)為2k；若2k>n，則它無(wú)左孩子結(jié)點(diǎn)。③若2k+1<=n，則該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)編號(hào)為2k+1；若2k+1>n，則它無(wú)右孩子結(jié)點(diǎn)。四、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1、順序存儲(chǔ)：選用一個(gè)數(shù)組T[n]，根據(jù)性質(zhì)5的編號(hào)關(guān)系，各結(jié)點(diǎn)按編號(hào)放在相應(yīng)位置上。適用于滿二叉樹(shù)和完全二叉樹(shù)，對(duì)于一般二叉樹(shù)，會(huì)造成空間浪費(fèi)。lchilddatarchild2、鏈?zhǔn)酱鎯?chǔ)：①二叉鏈表：結(jié)點(diǎn)結(jié)構(gòu)包括三個(gè)域，數(shù)據(jù)域data，左孩指針lchild，右孩指針rchild。②三叉鏈表：有時(shí)為了求父結(jié)點(diǎn)的方便，在二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)中再增設(shè)一個(gè)指向父結(jié)點(diǎn)的指針parent。五、二叉樹(shù)的遍歷1、前序遍歷（DLR）：先訪問(wèn)根結(jié)點(diǎn)，再前序遍歷左子樹(shù)，最后前序遍歷右子樹(shù)。2、中序遍歷（LDR）：先中序遍歷左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)。3、后序遍歷（LRD）：先后序遍歷左子樹(shù)，再后序遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。§６查找查找是根據(jù)給定的關(guān)鍵字值，在表中確定一個(gè)其關(guān)鍵字等于給定值的記錄的過(guò)程。若表中存在這樣的一個(gè)記錄，則稱(chēng)為查找成功，輸出記錄的有關(guān)信息或在表中的位置；若表中不存在相應(yīng)的記錄，則稱(chēng)查找不成功，可以輸出一個(gè)空記錄或空指針。常用的查找方法有順序查找、折半查找、索引順序查找、樹(shù)表查找和哈希查找。這里只介紹前兩種方法。一、順序查找1、查找方法：從表頭到表尾逐個(gè)進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字值與給定值相等，則查找成功，否則繼續(xù)比較表中下一個(gè)記錄，直到整個(gè)表都遍歷完。2、適用場(chǎng)合：對(duì)表的結(jié)構(gòu)無(wú)要求，順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的查找表都可以。3、算法分析：平均查找長(zhǎng)度（ASL）為n/2，時(shí)間復(fù)雜度為O(n)。二、折半查找（二分查找）1、查找方法：每次把待查值和查找表中間位置的記錄的關(guān)鍵字進(jìn)行比較，若相等則查找成功；不相等時(shí)根據(jù)大于或小于關(guān)系確定在后半?yún)^(qū)間或在前半?yún)^(qū)間繼續(xù)折半查找。2、適用場(chǎng)合：順序存儲(chǔ)的有序表。3、算法分析：平均查找長(zhǎng)度為log2(n+1)-1，時(shí)間復(fù)雜度為O(log2n)。三、兩種查找方法的比較順序查找算法簡(jiǎn)單，對(duì)表的結(jié)構(gòu)無(wú)要求，但時(shí)間性能不太好；折半查找以減半的方式縮小搜索范圍，查找速度快，但前提是順序存儲(chǔ)的查找表并且已按關(guān)鍵字排好序。§７排序排序的功能是將一個(gè)記錄的無(wú)序序列重新排列成一個(gè)按關(guān)鍵字有序的序列。排序的目的之一是方便查找。排序的依據(jù)是記錄中能唯一識(shí)別該記錄的數(shù)據(jù)項(xiàng)，稱(chēng)為關(guān)鍵字?？梢园搓P(guān)鍵字的值從小到大排序，稱(chēng)為升序排序，反之稱(chēng)為降序排序。在記錄序列中，排序前存在相同關(guān)鍵字的記錄，經(jīng)過(guò)某種排序方法排序后，這些記錄的相對(duì)次序保持不變，則稱(chēng)這種排序方法是穩(wěn)定的，反之稱(chēng)這種排序方法是不穩(wěn)定的。在內(nèi)存中就能完成對(duì)記錄序列的排序過(guò)程的排序稱(chēng)為內(nèi)部排序，若記錄文件很大，還需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程稱(chēng)為外部排序。排序方法分為插入排序法、交換排序法、選擇排序法、歸并排序法、基數(shù)排序法等大類(lèi)。一般的性能評(píng)價(jià)標(biāo)準(zhǔn)有兩條：一是執(zhí)行排序算法所需的時(shí)間，二是執(zhí)行排序算法所需的附加空間。時(shí)間性能一般以具體排序算法執(zhí)行過(guò)程中的關(guān)鍵字之間的比較次數(shù)和記錄位置的移動(dòng)次數(shù)來(lái)反映。這里只介紹前三類(lèi)六種排序方法。一、插入排序1、直接插入排序基本思想是：將待排序表看做是左、右兩部分，其中左邊是有序區(qū)，右邊是無(wú)序區(qū)，整個(gè)排序過(guò)程就是將右邊無(wú)序區(qū)中的元素逐個(gè)插入到左邊的有序區(qū)中，以構(gòu)成新的有序區(qū)。2、希爾排序基本思想是：將待排序列分為若干組，在每組內(nèi)進(jìn)行直接插入排序，以使整個(gè)序列基本有序，然后現(xiàn)對(duì)整個(gè)序列進(jìn)行直接插入排序。關(guān)鍵在于如何分組，常用辦法是第一輪取步長(zhǎng)為初始長(zhǎng)度n的一半，即間隔為[n/2]的元素為一組，以后每輪的步長(zhǎng)為上次的一半（縮小增量法）。二、交換排序1、冒泡排序（簡(jiǎn)單交換排序）基本思想是：從表的一端開(kāi)始，逐個(gè)比較相鄰的兩個(gè)元素的關(guān)鍵字值，發(fā)現(xiàn)倒序就交換。一輪比較的結(jié)果是關(guān)鍵字值最大的元素排到表尾，關(guān)鍵字值小的元素前移，就像在水面上的重物下沉、輕物上浮一樣，故稱(chēng)之“冒泡”排序。2、快速排序基本思想是：選定一個(gè)元素作為中間元素，然