C語(yǔ)言課件-數(shù)據(jù)結(jié)構(gòu)與算法

第1章數(shù)據(jù)結(jié)構(gòu)與算法1.1算法1.2數(shù)據(jù)結(jié)構(gòu)的根本概念1.3線性表及其順序存儲(chǔ)結(jié)構(gòu)1.4棧和隊(duì)列1.5線性鏈表1.6樹(shù)和二叉樹(shù)1.7查找技術(shù)1.8排序技術(shù)算法的根本概念算法的復(fù)雜度分析1.1算法算法的根本概念通俗的定義：算法是指解題方案的準(zhǔn)確而完整的描述。算法的根本特征1.可行性2.確定性3.有窮性4.擁有足夠的情報(bào)算法的嚴(yán)格定義： 算法是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)那么，并且每一個(gè)規(guī)那么都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法的根本要素(1)算法中對(duì)數(shù)據(jù)的運(yùn)算和操作①算術(shù)運(yùn)算②邏輯運(yùn)算③關(guān)系運(yùn)算④數(shù)據(jù)傳輸(2)算法的控制結(jié)構(gòu)傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語(yǔ)言等。算法設(shè)計(jì)根本方法1.列舉法 根據(jù)提出的問(wèn)題，列舉所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的?因此，列舉法常用于解決“是否存在”或“有多少種可能”等類(lèi)型的問(wèn)題，例如求解不定方程的問(wèn)題。例：設(shè)每只母雞值3元，每只公雞值2元，兩只小雞值1元?，F(xiàn)要用100元錢(qián)買(mǎi)100只雞，設(shè)計(jì)買(mǎi)雞方案。假設(shè)買(mǎi)母雞I只，公雞J只，小雞K只。2.歸納法通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。3.遞推從的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。4.遞歸將一個(gè)復(fù)雜的問(wèn)題歸結(jié)為假設(shè)干個(gè)較簡(jiǎn)單的問(wèn)題，然后將這些較簡(jiǎn)單的每一個(gè)問(wèn)題再歸結(jié)為更簡(jiǎn)單的問(wèn)題，這個(gè)過(guò)程可以一直做下去，直到最簡(jiǎn)單的問(wèn)題為止。5.減半遞推技術(shù)所謂“減半”，是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變。所謂“遞推”，是指重復(fù)“減半”的過(guò)程。例：二分法求方程實(shí)根6.回溯法通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，然后沿著這個(gè)線索逐步試探，對(duì)于每一步的試探，假設(shè)試探成功，就得到問(wèn)題的解，假設(shè)試探失敗，就逐步回退，換別的路線再進(jìn)行試探。例：迷宮問(wèn)題算法的復(fù)雜度分析算法的時(shí)間復(fù)雜度算法的空間復(fù)雜度執(zhí)行算法所需要的內(nèi)存空間。1.2數(shù)據(jù)結(jié)構(gòu)的根本概念什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的圖形表示線性數(shù)據(jù)結(jié)構(gòu)與非線性數(shù)據(jù)結(jié)構(gòu)目的：提高數(shù)據(jù)處理的效率提高數(shù)據(jù)處理的速度盡量節(jié)省計(jì)算機(jī)存儲(chǔ)空間數(shù)據(jù)結(jié)構(gòu)三個(gè)方面的問(wèn)題：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素集合?，F(xiàn)實(shí)世界中客觀存在的一切個(gè)體都可以是數(shù)據(jù)元素。描述一年四季的季節(jié)名春，夏，秋，冬可以作為季節(jié)的數(shù)據(jù)元素；表示數(shù)值的各個(gè)數(shù)18，11，35，23，16，…可以作為數(shù)值的數(shù)據(jù)元素；前后件關(guān)系前后件關(guān)系(也稱(chēng)為直接前驅(qū)和直接后繼)是數(shù)據(jù)元素之間的自然存在的一個(gè)根本關(guān)系，但前后件關(guān)系所表示的實(shí)際意義是隨具體對(duì)象的不同而不同。一般來(lái)說(shuō)，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來(lái)描述。數(shù)據(jù)的邏輯結(jié)構(gòu)一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含兩方面的信息〔1〕表示數(shù)據(jù)元素的信息；〔2〕表示各數(shù)據(jù)元素之間的前后件關(guān)系〔即邏輯關(guān)系〕數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：數(shù)據(jù)元素的集合D；反映D中各數(shù)據(jù)元素之間的前后件關(guān)系R。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)可以表示成B＝〔D，R〕其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來(lái)表示。設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，那么二元組〔a，b〕表示a是b的前件，b是a的后件。數(shù)據(jù)的邏輯結(jié)構(gòu)例如B＝〔D，R〕D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}家庭成員數(shù)據(jù)結(jié)構(gòu)B＝〔D，R〕D＝{父親，兒子，女兒}R＝{(父親，兒子〕，(父親，女兒〕}數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)〔數(shù)據(jù)的物理結(jié)構(gòu)〕數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。各數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相同。常用的存儲(chǔ)結(jié)構(gòu)有：順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示〔數(shù)據(jù)結(jié)點(diǎn)，結(jié)點(diǎn)〕用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。如:一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示

家庭成員間輩份關(guān)系數(shù)據(jù)結(jié)的圖形表示用圖形表示數(shù)據(jù)結(jié)構(gòu)B＝〔D，R〕D＝{di|1≤i≤7}＝{d1，d2，d3，d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算根本運(yùn)算：插入和刪除其他運(yùn)算：查找、分類(lèi)、合并、分解、復(fù)制和修改等。數(shù)據(jù)結(jié)構(gòu)的處理過(guò)程中，不僅結(jié)點(diǎn)的個(gè)數(shù)在動(dòng)態(tài)地變化，而且各數(shù)據(jù)元素之間的關(guān)系也有可能在動(dòng)態(tài)地變化。線性數(shù)據(jù)結(jié)構(gòu)與非線性數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)：〔1〕有且只有一個(gè)根結(jié)點(diǎn)；〔2〕每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。線性結(jié)構(gòu)又稱(chēng)線性表。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，那么稱(chēng)之為非線性結(jié)構(gòu)不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)特例

提示:在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)空數(shù)據(jù)結(jié)構(gòu)

1.3線性表及其順序存儲(chǔ)結(jié)構(gòu)什么是線性表線性表的順序存儲(chǔ)結(jié)構(gòu)線性表在順序存儲(chǔ)下的插入運(yùn)算線性表在順序存儲(chǔ)下的刪除運(yùn)算什么是線性表n維向量(x1，x2，…，xn)是一個(gè)長(zhǎng)度為n的線性表英文小寫(xiě)字母表(a，b，c，…，z)是一個(gè)長(zhǎng)度為26的線性表一年中的四個(gè)季節(jié)(春，夏，秋，冬)是一個(gè)長(zhǎng)度為4的線性表矩陣是一個(gè)比較復(fù)雜的線性表學(xué)生情況登記表是一個(gè)復(fù)雜的線性表什么是線性表(定義〕線性表是由n(n≥0)個(gè)數(shù)據(jù)元素a1，a2，…，an組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后件。即線性表或是一個(gè)空表，或可以表示為(a1，a2，…，ai，…，an)其中ai(i＝1，2，…，n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱(chēng)其為線性表中的一個(gè)結(jié)點(diǎn)。非空線性表結(jié)構(gòu)特征(1)有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件；(2)有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件；(3)除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其它所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱(chēng)為線性表的長(zhǎng)度。當(dāng)n＝0時(shí)，稱(chēng)為空表。線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)根本特點(diǎn)：(1)線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。線性表中第i個(gè)元素ai在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為ADR(ai)＝ADR(a1)＋(i－1)k長(zhǎng)度為n的線性表(a1，a2，…，ai，…，an)

順序存儲(chǔ)結(jié)構(gòu)整型一維數(shù)組存放長(zhǎng)度為8的線性表

(29,18,56,63,35,24,31,47)順序存儲(chǔ)結(jié)構(gòu)下線性表的運(yùn)算：插入刪除查找排序分解合并復(fù)制逆轉(zhuǎn)原那么：運(yùn)算后仍保持線性表的特性線性表在順序存儲(chǔ)下的插入運(yùn)算線性表在順序存儲(chǔ)下的刪除運(yùn)算1.4棧和隊(duì)列棧及其根本運(yùn)算隊(duì)列及其根本運(yùn)算棧及其根本運(yùn)算什么是棧棧的順序存儲(chǔ)及其運(yùn)算棧(stack)是限定在一端進(jìn)行插入與刪除的線性表。允許插入與刪除的一端稱(chēng)為棧頂，不允許插入與刪除的另一端稱(chēng)為棧底。棧是按照“先進(jìn)后出”(FILO—FirstInLastOut)或“后進(jìn)先出”(LIFO—LastInFirstOut)的原那么組織數(shù)據(jù)的，因此，棧也被稱(chēng)為“先進(jìn)后出”表或“后進(jìn)先出”表。棧具有記憶作用。用指針top來(lái)指示棧頂?shù)奈恢茫弥羔榖ottom指向棧底。往棧中插入一個(gè)元素稱(chēng)為入棧運(yùn)算，從棧中刪除一個(gè)元素(即刪除棧頂元素)稱(chēng)為退棧運(yùn)算。如：主程序與子程序之間的調(diào)用關(guān)系什么是棧棧的順序存儲(chǔ)及其運(yùn)算top＝0表示?？?；top＝m表示棧滿(mǎn)(1)入棧運(yùn)算〔上溢〕(2)退棧運(yùn)算〔下溢〕(3)讀棧頂元素〔不刪除棧頂元素〕棧的順序存儲(chǔ)及其運(yùn)算隊(duì)列及其根本運(yùn)算什么是隊(duì)列循環(huán)隊(duì)列隊(duì)列(equeue)是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。允許插入的一端稱(chēng)為隊(duì)尾，用尾指針(rear)指向隊(duì)尾元素。允許刪除的一端稱(chēng)為排頭(也稱(chēng)隊(duì)頭)，用排頭指針(front)指向排頭元素的前一個(gè)位置。隊(duì)列又稱(chēng)為“先進(jìn)先出”(FIFO—FirstInFirstOut)或“后進(jìn)后出”(LILO—LastInLastOut)的線性表，表達(dá)了“先來(lái)先效勞”的原那么。往隊(duì)列的隊(duì)尾插入一個(gè)元素稱(chēng)為入隊(duì)運(yùn)算，從隊(duì)列的排頭刪除一個(gè)元素稱(chēng)為退隊(duì)運(yùn)算。什么是隊(duì)列隊(duì)列根本運(yùn)算循環(huán)隊(duì)列及其運(yùn)算循環(huán)隊(duì)列及其運(yùn)算循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front=m入隊(duì)運(yùn)算：隊(duì)尾指針進(jìn)1，當(dāng)隊(duì)尾指針rear=m+1時(shí)，那么置rear=1。退隊(duì)運(yùn)算：排頭指針進(jìn)1，當(dāng)排頭指針front=m+1時(shí)，那么置front=1隊(duì)列空的條件為s＝0〔下溢〕隊(duì)列滿(mǎn)的條件為(s＝1)且front＝rear〔上溢〕1.5線性鏈表什么是線性表線性鏈表的根本運(yùn)算循環(huán)鏈表順序存儲(chǔ)線性表的缺點(diǎn)：插入上溢共享1.線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線性鏈表。線性鏈表的根本概念頭結(jié)點(diǎn)：指向線性表中第一個(gè)結(jié)點(diǎn)的指針HEAD稱(chēng)為頭指針，當(dāng)HEAD=NULL(或0〕時(shí)稱(chēng)為空表。線性單鏈表只能順指針向鏈尾方向進(jìn)行掃描。雙向鏈表帶鏈的棧帶鏈的隊(duì)列線性鏈表的插入在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中插入一個(gè)新元素。線性鏈表的根本運(yùn)算(1)從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p。并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲，即V(p)＝b。(2)在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)q。(3)將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后：①使結(jié)點(diǎn)p指向包含元素x的結(jié)點(diǎn)，即NEXT(p)＝NEXT(q)②使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p，即NEXT(q)＝p線性鏈表的刪除鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。(1)尋找包含元素x的前一個(gè)結(jié)點(diǎn)q。那么包含元素x的結(jié)點(diǎn)序號(hào)p＝NEXT(q)。(2)將結(jié)點(diǎn)q后的結(jié)點(diǎn)p刪除，即NEXT(q)＝NEXT(p)。(3)將包含元素x的結(jié)點(diǎn)p送回可利用棧。(1)在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)。(2)空表與非空表的運(yùn)算統(tǒng)一。循環(huán)鏈表循環(huán)鏈表的優(yōu)勢(shì)：通過(guò)任何一個(gè)結(jié)點(diǎn)都可以訪問(wèn)到其他任意結(jié)點(diǎn)增加了表頭結(jié)點(diǎn)，使得空表與非空表的運(yùn)算統(tǒng)一。樹(shù)與二叉樹(shù)樹(shù)的根本概念二叉樹(shù)及其根本性質(zhì)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的遍歷樹(shù)是由n(n0)個(gè)結(jié)點(diǎn)組成的有限集合。如果n=0，稱(chēng)為空樹(shù)；如果n>0，那么:有一個(gè)特定的稱(chēng)之為根的結(jié)點(diǎn)，它只有后繼，但沒(méi)有前驅(qū)；除根以外的其它結(jié)點(diǎn)劃分為m(m0)個(gè)互不相交的有限集合T0,T1,…,Tm-1，每個(gè)集合本身又是一棵樹(shù)，并且稱(chēng)之為根的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)后繼。什么是樹(shù)？1〕度〔次數(shù)、級(jí)〕〔1〕結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)〔2〕樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值2〕描述上下及左右的關(guān)系孩子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹(shù)的根雙親結(jié)點(diǎn)：結(jié)點(diǎn)的直接前驅(qū)〔前件〕兄弟結(jié)點(diǎn)：同一個(gè)雙親的孩子之間互稱(chēng)兄弟祖先：結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)子孫：結(jié)點(diǎn)的后代3〕層次〔1〕結(jié)點(diǎn)的層次〔2〕樹(shù)的深度〔高度〕樹(shù)的根本術(shù)語(yǔ)結(jié)點(diǎn)(node)結(jié)點(diǎn)的度(degree)分支(branch)結(jié)點(diǎn)葉(leaf)結(jié)點(diǎn)孩子(child)結(jié)點(diǎn)雙親(parent)結(jié)點(diǎn)兄弟(sibling)結(jié)點(diǎn)祖先(ancestor)結(jié)點(diǎn)子孫(descendant)結(jié)點(diǎn)結(jié)點(diǎn)所處層次(level)樹(shù)的深度(depth)樹(shù)的度(degree)(1)表達(dá)式中的每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱(chēng)為運(yùn)算符結(jié)點(diǎn)。(2)運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù)〔在樹(shù)中的順序?yàn)閺淖蟮接摇场?3)運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。表達(dá)式樹(shù)a*(b＋c/d)＋e*h－g*f(s，t，x＋y)a*(b＋c/d)＋e*h－g*f(s，t，x＋y)注：樹(shù)在計(jì)算機(jī)中通常用多重鏈表表示。

(1)非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；(2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。什么是二叉樹(shù)性質(zhì)1在二叉樹(shù)的第k層上，最多有2k－1(k≥1)個(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其中[log2n]表示取log2n的整數(shù)局部。二叉樹(shù)的根本性質(zhì)滿(mǎn)二叉樹(shù)完全二叉樹(shù)假設(shè)設(shè)二叉樹(shù)的深度為h，那么共有h層。除第h層外，其它各層(0h-1)的結(jié)點(diǎn)數(shù)都到達(dá)最大個(gè)數(shù)，第h層從右向左連續(xù)缺假設(shè)干結(jié)點(diǎn)，這就是完全二叉樹(shù)。性質(zhì)5具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]＋1。性質(zhì)6設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始，按層序〔每一層從左到右〕用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，那么對(duì)于編號(hào)為k(k＝1，2，…，n)的結(jié)點(diǎn)有以下結(jié)論：(1)假設(shè)k＝1，那么該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；假設(shè)k＞1，那么該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。(2)假設(shè)2k≤n，那么編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否那么該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)〔顯然也沒(méi)有右子結(jié)點(diǎn)〕。(3)假設(shè)2k＋1≤n，那么編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k＋1；否那么該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。二叉鏈表

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)〔鏈表存儲(chǔ)和順序存儲(chǔ)〕1.前序遍歷(DLR)假設(shè)二叉樹(shù)為空，那么結(jié)束返回。否那么：(1)訪問(wèn)根結(jié)點(diǎn)；(2)前序遍歷左子樹(shù)；(3)前序遍歷右子樹(shù)。2.中序遍歷(LDR)假設(shè)二叉樹(shù)為空，那么結(jié)束返回。否那么：(1)中序遍歷左子樹(shù)；(2)訪問(wèn)根結(jié)點(diǎn)；(3)中序遍歷左子樹(shù)。3.后序遍歷(LRD)假設(shè)二叉樹(shù)為空，那么結(jié)束返回。否那么：(1)后序遍歷左子樹(shù)；(2)后序遍歷左子樹(shù)；(3)訪問(wèn)根結(jié)點(diǎn)。二叉樹(shù)的遍歷二叉樹(shù)的遍歷例題〔1〕二叉樹(shù)后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是A〕acbedB〕decabC〕deabcD〕cedba

〔2〕一棵二叉樹(shù)前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，那么該二叉樹(shù)的后序遍歷為A〕GEDHFBCAB〕DGEBHFCAC〕ABCDEFGHD〕ACBFEDHG1.7查找技術(shù)順序查找二分法查找(1)如果線性表為無(wú)序表〔即表中元素的排列是無(wú)序的〕，那么不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。(2)即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。(3)最壞情況時(shí)間復(fù)雜度為n。順序查找設(shè)有序線性表的長(zhǎng)度為n，被查元素為x。將x與線性表的中間項(xiàng)進(jìn)行比較：假設(shè)中間項(xiàng)的值等于x，那么說(shuō)明查到，查找結(jié)束；假設(shè)x小于中間項(xiàng)的值，那么在線性表的前半局部〔即中間項(xiàng)以前的局部〕以相同的方法進(jìn)行查找；假設(shè)x大于中間項(xiàng)的值，那么在線性表的后半局部〔即中間項(xiàng)以后的局部〕以相同的方法進(jìn)行查找。這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0(說(shuō)明線性表中沒(méi)有這個(gè)元素)為止。在最壞情況下，對(duì)分查找只需比較log2n次，而順序查找需比較n次。二分法查找1.8排序技術(shù)交換類(lèi)排序插入類(lèi)排序選擇類(lèi)排序首先，從表頭開(kāi)始往后掃描線性表，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。假設(shè)相鄰兩個(gè)元素中，前面的元素大于后面的元素，那么將它們互換，稱(chēng)之為消去了一個(gè)逆序。顯然，在掃描過(guò)程中，不斷地將兩相鄰元素中的大者往后移動(dòng)，最后就將線性表中的最大者換到了表的最后。然后從后到前掃描剩下的線性表，同樣，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。假設(shè)相鄰兩個(gè)元素中，后面的元素小于前面的元素，那么將它們互換，這樣就又消去了一個(gè)逆序。顯然，在掃描過(guò)程中，不斷地將兩相鄰元素中的小者往前移動(dòng)，最后就將剩下線性表中的最小者換到了表的最前。對(duì)剩下的線性表重復(fù)上述過(guò)程，直到剩下的線性表變空為止，此時(shí)的線性表已經(jīng)變?yōu)橛行颉Ｗ顗那闆r下的時(shí)間復(fù)雜度為n(n-1)/2.冒泡排序快速排序首先，在表的第一個(gè)、中間一個(gè)與最后一個(gè)元素中選取中項(xiàng)，設(shè)為P(k)，并將P(k)賦給T，再將表中的第一個(gè)元素移到P(k)的位置上。然后設(shè)置兩個(gè)指針i和j分別指向表的起始與最后的位置。反復(fù)作以下兩步：(1)將j逐漸減小，并逐次比較P(j)與T，直到發(fā)現(xiàn)一個(gè)P(j)＜T為止，將P(j)移到P(i)的位置上。(2)將i逐漸增大，并逐次比較P(i)與T，直到發(fā)現(xiàn)一個(gè)P(i)＞T為止，將P(i)移到P(j)的位置上。上述兩個(gè)操作交替進(jìn)行，直到指針i與j指向同一個(gè)位置〔即i＝j(luò)〕為止，此時(shí)將T移到P(i)的位置上。簡(jiǎn)單插入排序51731694286

↑j＝215731694286

↑j＝315731694286

↑j＝413571694286

↑j＝511357694286

↑j＝6

11356794286

↑j＝711356794286

↑j＝81