算法結(jié)構(gòu)與算法基礎(chǔ)

數(shù)據(jù)結(jié)構(gòu)與算法根底主要內(nèi)容1算法根底知識(shí)2數(shù)據(jù)結(jié)構(gòu)的根本概念3現(xiàn)性表及其屬虛存儲(chǔ)結(jié)構(gòu)4棧和隊(duì)列5二叉樹(shù)6查找和排序1.1、算法的根本概念〔一〕、算法的定義算法是一個(gè)有限條指令的集合，即一個(gè)算法是一個(gè)有窮規(guī)那么的有序集合，這些規(guī)那么確定了解決某一問(wèn)題的一個(gè)運(yùn)算序列，對(duì)任一個(gè)輸入，通過(guò)有限步計(jì)算，產(chǎn)生一個(gè)輸出。程序就是用計(jì)算機(jī)語(yǔ)言表述的算法，流程圖就是圖形化了的算法。程序＝算法+數(shù)據(jù)結(jié)構(gòu)〔二〕、算法的兩要素1、操作最根本的功能操作包括：〔1〕邏輯運(yùn)算：與、或、非；〔2〕算術(shù)運(yùn)算：加、減、乘、除；〔3〕數(shù)據(jù)比較：大于、小于、等于、不等于；〔4〕數(shù)據(jù)傳送：輸入、輸出、賦值。2、算法的控制結(jié)構(gòu)算法的控制結(jié)構(gòu)〔各操作之間的執(zhí)行順序〕給出了算法的框架，決定了各操作的執(zhí)行次序。流程圖可以形象地表示出算法的控制結(jié)構(gòu)。一個(gè)算法一般可以用順序、選擇、循環(huán)三種根本機(jī)構(gòu)組合而成〔三〕、算法的特征1、可行性:指解決問(wèn)題的方法切實(shí)可行。2、確定性：算法每一步都有明確的定義，不會(huì)產(chǎn)生二義性。3、有窮性：解答必須在有限步內(nèi)得到。。4、輸入：每個(gè)算法過(guò)程必須有0個(gè)或多個(gè)輸入。5、輸出：每種算法必須有確定的結(jié)果，產(chǎn)生一個(gè)或多個(gè)輸出〔四〕、算法的表示1、自然語(yǔ)言2、專用工具常用的有流程圖、PAD圖和N-S圖等。

返回計(jì)算機(jī)算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無(wú)不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。運(yùn)算是由計(jì)算機(jī)來(lái)完成，這就要設(shè)計(jì)相應(yīng)的插入、刪除和修改的算法。也就是說(shuō)，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。直觀定義：數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。1.2數(shù)據(jù)結(jié)構(gòu)的根本概念地位：“數(shù)據(jù)結(jié)構(gòu)〞在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)根底課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)〔特別是非數(shù)值性程序設(shè)計(jì)〕的根底，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序的重要根底。

數(shù)據(jù)結(jié)構(gòu)概念一般包括三個(gè)方面的內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式以及在這些數(shù)據(jù)上定義的運(yùn)算的集合。一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)該包含下面兩方面的信息：

1、表示信息元素的信息；

2、表示各數(shù)據(jù)元素之間的前后件關(guān)系；1.2數(shù)據(jù)結(jié)構(gòu)的根本概念〔1〕數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述，它只抽象地反映數(shù)據(jù)元素間的邏輯關(guān)系，而不管其在計(jì)算機(jī)中的存儲(chǔ)方式。數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。〔2〕數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器里的實(shí)現(xiàn)。按其結(jié)點(diǎn)各域的性質(zhì)可分成兩大類：一類是存放自身值的域—信息域。另一類是存放該結(jié)點(diǎn)與其它結(jié)點(diǎn)的關(guān)系的域—指針域?！?〕數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，運(yùn)算的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。常用的運(yùn)算有：檢索、插入、刪除、更新、排序等。infolink

數(shù)據(jù)存儲(chǔ)方式1、順序存儲(chǔ)結(jié)構(gòu)主要用于線性的數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)表達(dá)。例如，線性表〔k1，k2，k3，k4，k5〕，假定每個(gè)結(jié)點(diǎn)占一個(gè)存儲(chǔ)單元，結(jié)點(diǎn)k存放在200號(hào)單元中，那么順序存儲(chǔ)實(shí)現(xiàn)如右圖所示。k1k2k3k5k4200201202203204順序結(jié)構(gòu)的主要特點(diǎn)是：〔1〕結(jié)點(diǎn)中只有自身信息域，沒(méi)有連接信息域。因此，存儲(chǔ)密度大，存儲(chǔ)空間利用率高?！?〕可以通過(guò)計(jì)算直接確定數(shù)據(jù)結(jié)構(gòu)中第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址L，計(jì)算公式為：Li＝L0＋〔i-1〕×m其中，L0為第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址，m為每個(gè)結(jié)點(diǎn)占用的存儲(chǔ)單元個(gè)數(shù)。〔3〕插入、刪除運(yùn)算會(huì)引起大量結(jié)點(diǎn)的移動(dòng)。2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是在每個(gè)結(jié)點(diǎn)中至少包括一個(gè)指針域，用指針來(lái)表達(dá)數(shù)據(jù)元素之間邏輯上的聯(lián)系?？梢园堰壿嬌舷噜彽膬蓚€(gè)元素存放在物理上不相鄰的存儲(chǔ)單元中。例如，線性表〔k1，k2，k3，k4，k5〕可以用鏈?zhǔn)酱鎯?chǔ)，如下頁(yè)圖所示。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要特點(diǎn)：〔1〕結(jié)點(diǎn)中除自身信息外，還有表示連接信息的指針域，因此比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小，存儲(chǔ)空間利用率低?！?〕邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接，可用于線性表、樹(shù)、圖等多種邏輯結(jié)構(gòu)的存儲(chǔ)表示。〔3〕插入、刪除操作靈活方便，不必移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中的指針值即可。1.2常用數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)與運(yùn)算一、線性表〔一〕、線性表的根本概念1、線性表的定義線性表是最簡(jiǎn)單、最常用、最根本的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列：〔a1，a2，...，an〕表中元素的個(gè)數(shù)n定義為線性表的長(zhǎng)度〔n>=0〕，n=0的表稱為空表。2、線性表的結(jié)構(gòu)特征〔1〕數(shù)據(jù)元素呈線性關(guān)系；〔2〕必存在唯一的一個(gè)被稱為“第一個(gè)〞的數(shù)據(jù)元素；〔3〕必存在唯一的一個(gè)被稱為“最后一個(gè)〞的數(shù)據(jù)元素；〔4〕除第一個(gè)元素外，每個(gè)元素都有且只有一個(gè)前驅(qū)元素；〔5〕除最后一個(gè)元素外，每個(gè)元素都有且只有一個(gè)后繼元素；〔6〕所有數(shù)據(jù)元素ai，在同一個(gè)線性表中必須是相同的數(shù)據(jù)類型。3、線性表的種類按其存儲(chǔ)結(jié)構(gòu)可分為：〔1〕順序表用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱為順序表。〔2〕鏈表用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表稱為鏈表。4、線性表的根本運(yùn)算〔1〕在兩個(gè)確定的元素之間插入一個(gè)新的元素；〔2〕刪除線性表中某個(gè)元素；〔3〕按某種要求查找線性表中的一個(gè)元素，需要時(shí)，還可找到元素進(jìn)行值的更新。〔二〕、順序表和一維數(shù)組1、順序表的定義用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表的數(shù)據(jù)元素，這種順序分配存儲(chǔ)方式的表，稱為順序表。2、順序表的結(jié)構(gòu)特點(diǎn)〔1〕將表的數(shù)據(jù)元素按其邏輯順序依次存放到一組地址連續(xù)的存儲(chǔ)單元中；〔2〕邏輯上相鄰元素的存儲(chǔ)地址也是相鄰的，線性表的邏輯關(guān)系隱含在存儲(chǔ)單元的鄰接關(guān)系中?！?〕數(shù)據(jù)元素的數(shù)據(jù)類型相同；〔4〕每一個(gè)元素占用同樣大小的存儲(chǔ)單元。3、順序表與一維數(shù)組的關(guān)系高級(jí)語(yǔ)言里的一維數(shù)組是用順序方式存儲(chǔ)的線性表，因此，一維數(shù)組也稱為順序表。一維數(shù)組的各元素下標(biāo)與線性表中的元素序號(hào)一一對(duì)應(yīng)。例如：用一維數(shù)組A(1……n)存儲(chǔ)線性表〔a1，a2，a3，...，an〕時(shí)，A〔k〕的值就是表中第k個(gè)數(shù)據(jù)元素ak。即數(shù)組的下標(biāo)可看成是線性表中數(shù)據(jù)元素的相對(duì)地址。4、順序表的插入與刪除運(yùn)算〔1〕插入運(yùn)算在線性表〔a1，a2,…，ai,ai+1，…，an〕的第i個(gè)位置前插入元素x，使之成為〔a1，a2,…，x，ai,ai+1，…，an〕。假設(shè)順序表中結(jié)點(diǎn)個(gè)數(shù)為n，在往每個(gè)位置插入的概率相等的情況下，插入一個(gè)結(jié)點(diǎn)的平均移動(dòng)結(jié)點(diǎn)個(gè)數(shù)為n/2。a1a2aiai+1an?????????單元編號(hào)存儲(chǔ)空間12ii+1nn+1??????a1a2aiai+1an??????單元編號(hào)存儲(chǔ)空間12ii+1nn+1????????????a1a2aiai+1an??????單元編號(hào)存儲(chǔ)空間12ii+1nn+1??????a1a2aiai+1anx??????單元編號(hào)存儲(chǔ)空間12ii+1nn+1??????〔2〕刪除在線性表〔a1，a2，…，ai-1，ai，ai+1，…，an〕中刪除第i個(gè)數(shù)據(jù)元素，使之成為〔a1，a2，…，ai-1，ai+1，…，an〕。在等概率的情況下，刪除順序表中一個(gè)元素平均需要移動(dòng)的結(jié)點(diǎn)個(gè)數(shù)為〔n-1〕/2。a1a2aiai+1an??????單元編號(hào)存儲(chǔ)空間12ii+1n????????????a1a2an??????單元編號(hào)存儲(chǔ)空間12ii+1n??????ai+1???〔三〕、鏈表〔1〕單鏈表〔線性鏈表〕單鏈表就是鏈?zhǔn)酱鎯?chǔ)的線性表，其結(jié)點(diǎn)除信息域外還含有一個(gè)指針域，用來(lái)指出其后繼結(jié)點(diǎn)的位置。鏈表的插入、刪除運(yùn)算靈活方便，不需移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中指針域的值即可。info〔信息域〕link〔指針域〕〔2〕循環(huán)鏈表循環(huán)鏈表和單鏈表的差異在于鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不為“NULL〞，而指向第一個(gè)結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈結(jié)的環(huán)。結(jié)點(diǎn)1結(jié)點(diǎn)2結(jié)點(diǎn)n〔3〕雙向鏈表除設(shè)有指向后繼結(jié)點(diǎn)的指針，還設(shè)一個(gè)指向前驅(qū)結(jié)點(diǎn)的指針，稱這種含有兩個(gè)指針域的結(jié)點(diǎn)構(gòu)成的鏈表為雙向鏈表。(四)、?！瞫tack〕1、棧的定義棧〔stack〕是一種特殊的線性表，其元素均按“后進(jìn)先出〞的原那么進(jìn)行操作。因其運(yùn)算規(guī)那么受到一定約束和限定，故又稱限定性數(shù)據(jù)結(jié)構(gòu)。2、棧的結(jié)構(gòu)ana3a2a1棧頂Top棧底Bottom出棧Pop入棧Push表頭表尾3、棧的特點(diǎn)〔1〕棧是按“先進(jìn)后出〞〔LIFO〕的原那么進(jìn)行操作；〔2〕表尾稱為棧頂〔Top〕，表頭稱為棧底〔Bottom〕；〔3〕表中無(wú)元素時(shí)稱為空棧?！?〕棧的插入和刪除運(yùn)算被限定僅在表尾進(jìn)行?！?〕棧的物理存儲(chǔ)可以用順序存儲(chǔ)結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。4、棧的運(yùn)算進(jìn)棧操作退棧操作設(shè)置一個(gè)空棧判定某個(gè)棧是否為空棧讀取棧頂元素等?！参濉场㈥?duì)列〔Queue〕1、隊(duì)列的定義隊(duì)列是一種特殊的線性表，其元素均按“先進(jìn)先出〞的原那么進(jìn)行操作。因其運(yùn)算規(guī)那么受到一定約束和限定，也是限定性數(shù)據(jù)結(jié)構(gòu)。2、隊(duì)列的結(jié)構(gòu)a1a2a3??????an

出隊(duì)列〔刪除〕入隊(duì)列〔插入〕隊(duì)頭〔Front〕隊(duì)尾〔Rear〕3、隊(duì)列的特點(diǎn)〔1〕隊(duì)列是按“先進(jìn)先出〞〔FIFO〕的原那么進(jìn)行操作；〔2〕限定所有的插入只能在表的一端進(jìn)行，這一端稱為隊(duì)尾〔Rear〕?！?〕限定所有的刪除都在表的另一端進(jìn)行的線性表，這一端稱為隊(duì)頭〔Front〕?！?〕表中無(wú)元素時(shí)稱為空隊(duì)列?！?〕隊(duì)列的物理存儲(chǔ)可以用順序存儲(chǔ)結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。4、隊(duì)列的運(yùn)算插入一個(gè)新的隊(duì)尾元素〔入隊(duì)列〕刪除隊(duì)頭元素〔出隊(duì)列〕設(shè)置一個(gè)空隊(duì)列判定某個(gè)隊(duì)列是否是空隊(duì)列讀取隊(duì)頭元素等隊(duì)列的插入與刪除AABBBCBCDCDFR初態(tài)FR插入AFR插入BFR刪除AFR插入CFR插入DFR刪除B隊(duì)尾隊(duì)頭假溢出ABCfrontrearfrontrear(a)

A?B?C入隊(duì)

(b)

A?B出隊(duì),D?E入隊(duì)

(c)隊(duì)列假溢出隊(duì)列假溢出示意圖CDEfrontrear隨著元素不斷入隊(duì)列、出隊(duì)列，rear和front指針會(huì)不斷向后移動(dòng)〔如圖(b)所示〕，最終會(huì)指向數(shù)組的最大下標(biāo)位置〔如圖(c)所示〕。由于rear和front指針只能單方向移動(dòng)，這時(shí)元素?zé)o法入隊(duì)列，但是隊(duì)列中仍有大量空閑位置。這種情況稱為假溢出。三樹(shù)的定義及根本操作定義：樹(shù)〔tree〕是n個(gè)結(jié)點(diǎn)的有限集合T，且滿足以下條件：當(dāng)n=0時(shí)，集合為空，稱空樹(shù)。在任意非空樹(shù)中：〔1〕有且僅有一個(gè)特定的稱為根〔root〕的結(jié)點(diǎn)?！瞡=1〕〔2〕n>1，除根結(jié)點(diǎn)以外的其余結(jié)點(diǎn)可分為m(m>0)個(gè)互為相交的有限集合T1，T2……Tm，其中的每個(gè)集合本身又是一棵樹(shù)，并稱其為根的子樹(shù)〔subtree〕★這是一個(gè)遞歸定義，反映了樹(shù)的固有特性。即一棵樹(shù)由根及假設(shè)干棵子樹(shù)構(gòu)成，而子樹(shù)又由更小的子樹(shù)構(gòu)成?！飿?shù)結(jié)構(gòu)中結(jié)點(diǎn)之間有分支關(guān)系，層次關(guān)系，樹(shù)中無(wú)環(huán)路樹(shù)的一般表示：

樹(shù)的術(shù)語(yǔ)樹(shù)的結(jié)點(diǎn)：包括一個(gè)數(shù)據(jù)元素及假設(shè)干指向其子樹(shù)的分支。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù)稱為結(jié)點(diǎn)的度〔degree〕樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值為該樹(shù)的度。葉子〔leaf〕：度為0的結(jié)點(diǎn)稱葉子或終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。孩子，雙親和兄弟節(jié)點(diǎn)：節(jié)點(diǎn)的子樹(shù)的根稱為該節(jié)點(diǎn)的孩子結(jié)點(diǎn)〔child〕。而該節(jié)點(diǎn)稱做孩子節(jié)點(diǎn)的雙親結(jié)點(diǎn)〔父結(jié)點(diǎn)〕〔parent〕。具有同一雙親節(jié)點(diǎn)的孩子結(jié)點(diǎn)之間互稱為兄弟〔sibling〕。結(jié)點(diǎn)的層次〔level〕：結(jié)點(diǎn)的層次從根開(kāi)始算起，根的層次值為1，其余結(jié)點(diǎn)的層次值為雙親結(jié)點(diǎn)層次值加1。樹(shù)的深度〔depth〕：樹(shù)中結(jié)點(diǎn)的最大層次值稱為樹(shù)的深度或高度。有序樹(shù)與無(wú)序樹(shù)：如果將樹(shù)中結(jié)點(diǎn)的各個(gè)子樹(shù)看成從左到右是有序的〔即不能互換〕，那么稱該樹(shù)為有序樹(shù)，否那么稱為無(wú)序樹(shù)。森林〔forest〕：森林是m(m≥0)棵互不相交的樹(shù)的集合，刪去一棵樹(shù)的根，就得到一個(gè)森林。樹(shù)的邏輯結(jié)構(gòu)特征可用樹(shù)中結(jié)點(diǎn)的父子關(guān)系描述：樹(shù)中任一結(jié)點(diǎn)可以有零個(gè)或多個(gè)孩子結(jié)點(diǎn)，但只能有一個(gè)雙親結(jié)點(diǎn)〔根結(jié)點(diǎn)除外〕，樹(shù)中只有根結(jié)點(diǎn)無(wú)前驅(qū)結(jié)點(diǎn)，所有葉子結(jié)點(diǎn)都無(wú)后繼結(jié)點(diǎn)。顯然，父子關(guān)系是非線性的，所以樹(shù)結(jié)構(gòu)是非線性結(jié)構(gòu)。2、二叉樹(shù)定義二叉樹(shù)〔BinaryTree〕是n〔n>=0〕個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0〕，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為根的左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)組成。ABCDEFGHIAABAC注意：〔1〕二叉樹(shù)不是樹(shù)的特殊情況，是兩個(gè)概念；〔2〕樹(shù)和二叉樹(shù)之間最主要的差異是：二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)要區(qū)分左子樹(shù)和右子樹(shù)。二叉樹(shù)與樹(shù)的區(qū)別與聯(lián)系：

都有且僅有一個(gè)根，根無(wú)前驅(qū)，葉子無(wú)后繼。二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度小于等于2，二叉樹(shù)的子樹(shù)有左右之分。二叉樹(shù)的五種根本形態(tài)：空樹(shù)只有根右子樹(shù)為空左右子樹(shù)非空左子樹(shù)為空

二叉樹(shù)的性質(zhì)

性質(zhì)1：二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)目至多為ik-1(i≥1)性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)性質(zhì)3：在任何一棵二叉樹(shù)中，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，那么n0=n2+1性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1(二)、樹(shù)的存儲(chǔ)結(jié)構(gòu)

樹(shù)的存儲(chǔ)結(jié)構(gòu)可以采用具有多個(gè)指針域的多重鏈表，結(jié)點(diǎn)中指針域的個(gè)數(shù)由樹(shù)的度來(lái)決定。(三)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)通常使用具有兩個(gè)指針域的二叉鏈表作二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。

(四)、樹(shù)的二叉樹(shù)表示1、樹(shù)與二叉樹(shù)之間的對(duì)應(yīng)關(guān)系每一棵樹(shù)都能唯一地轉(zhuǎn)換到它所對(duì)應(yīng)的二叉樹(shù)。2、樹(shù)轉(zhuǎn)換成對(duì)應(yīng)二叉樹(shù)的方法但凡兄弟就用線連接起來(lái)，對(duì)每個(gè)非終端結(jié)點(diǎn)，除其最左孩子外，刪去該結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)的連線，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)45。，即得相應(yīng)的二叉樹(shù)。在樹(shù)所對(duì)應(yīng)的二叉樹(shù)中，一個(gè)結(jié)點(diǎn)的左孩子是它原來(lái)在樹(shù)里的第一個(gè)孩子，右孩子是它在原來(lái)樹(shù)里的下一個(gè)兄弟。ABCDEFGHIJABCDEFGHIJABCEFGDHIJ順時(shí)針旋轉(zhuǎn)45。長(zhǎng)兄左鏈父弟弟右鏈兄兄弟依次手拉手五、樹(shù)和二叉樹(shù)的遍歷〔周游〕遍歷：是按一定的次序，系統(tǒng)地訪問(wèn)該結(jié)構(gòu)中的所有結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)恰被訪問(wèn)一次。一棵非空二叉樹(shù)由樹(shù)根、左子樹(shù)和右子樹(shù)組成，依次遍歷這三局部，就可以遍歷整個(gè)二叉樹(shù)。有多種遍歷樹(shù)的方法，限定必須先左子樹(shù)，后右子樹(shù)，便有三種遍歷樹(shù)的方案： 1、前序遍歷二叉樹(shù) 2、中序遍歷二叉樹(shù) 3、后序遍歷二叉樹(shù)

2、二叉樹(shù)的遍歷〔1〕前序遍歷二叉樹(shù)算法(NLR)①訪問(wèn)根結(jié)點(diǎn)；②前序遍歷左子樹(shù)；③前序遍歷右子樹(shù)?！哺底蟆涤摇硨?duì)于上圖使用前序遍歷，那么處理順序?yàn)椋篈BEFCGDHIJ。ABCEFGDHIJ①②③④⑤⑥⑦⑧⑨〔2〕中序遍歷二叉樹(shù)的算法(LNR)假設(shè)二叉樹(shù)不空，那么依次進(jìn)行以下操作：①中序遍歷左子樹(shù)；②訪問(wèn)根結(jié)點(diǎn)；③中序遍歷右子樹(shù)?！沧蟆蹈涤摇矨BCEFGDHIJ①②③④⑤⑥⑦⑧⑨對(duì)于上圖，使用中序遍歷，那么處理順序?yàn)椋篍FBGCHIJDA?！?〕后序遍歷二叉樹(shù)的算法〔LRN〕假設(shè)二叉樹(shù)不空，那么依次進(jìn)行以下操作：①后序遍歷左子樹(shù)；②后序遍歷右子樹(shù)；③訪問(wèn)非根結(jié)點(diǎn)。〔左——〉右——〉根〕ABCEFGDHIJ①②③④⑤⑥⑦⑧⑨對(duì)于上圖，使用后序遍歷，那么處理順序?yàn)椋篎EGJIHDCBA。3、根據(jù)遍歷結(jié)果畫(huà)出二叉樹(shù)〔1〕由于前序遍歷法〔最首〕和后序遍歷法〔最尾〕能夠明確根的位置，所以此類題題干中必須給出兩者之一的遍歷結(jié)果；〔2〕此類題題干中必須給出中序遍歷結(jié)果；例題：后序遍歷結(jié)果為：FEGJIHDCBA中序遍歷結(jié)果為：EFBGCHIJDA1)FEGJIHDCBA和EFBGCHIJDA左根右〔為空〕2)FEGJIHDCB和EFBGCHIJD左根右3)FEGJIHDC和GCHIJD左根右4)FEGJIHD和HIJD左根右〔為空〕5)FEGJIH和HIJ左〔為空〕根右6)FEGJI和IJ左〔為空〕根右7)FE和EF左〔為空〕根右ABCEFGDHIJ返回1.3查找0一、根本概念1、關(guān)鍵字：是數(shù)據(jù)元素中可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。2、查找：根據(jù)給定的關(guān)鍵值，在一組數(shù)據(jù)中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素的過(guò)程。查找確實(shí)切定義為：給定一個(gè)值K，在含有用個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)其關(guān)鍵字等于給定的K值的記錄，如找到，那么輸出記錄或記錄在文件中的相對(duì)位置，稱查找成功；否那么輸出查找不成功的信息，稱查找失敗。二、查找算法1、順序查找〔1〕查找方法：用待查關(guān)鍵字值與線性表中各結(jié)點(diǎn)的關(guān)鍵字值逐個(gè)比較，直到找出相等的關(guān)鍵字值；或者找遍所有結(jié)點(diǎn)都找不到符合要求的項(xiàng)，即查找失敗?！?〕優(yōu)點(diǎn)：是對(duì)線性表的結(jié)點(diǎn)邏輯次序無(wú)要求，對(duì)線性表的存儲(chǔ)結(jié)構(gòu)無(wú)要求〔順序存儲(chǔ)、鏈接存儲(chǔ)皆可〕?！?〕缺點(diǎn)：是平均檢索長(zhǎng)度長(zhǎng)，為n／2。2、二分法查找如果線性表結(jié)點(diǎn)是按關(guān)鍵字值升序排好序的，且線性表以順序方式存儲(chǔ)，可以采用二分查找。〔1〕查找方法用要查找的關(guān)鍵碼值K與線性表中間位置結(jié)點(diǎn)的關(guān)鍵碼值W比較，有三種可能：①X=W，此時(shí)已經(jīng)查找成功，查找結(jié)束。②X＞W(wǎng)，說(shuō)明X只能在表的后半局部，所以取表的后半局部進(jìn)行查找。③X＜W，說(shuō)明X只能在表的前半局部，取表的前半局部進(jìn)行查找?！?〕優(yōu)點(diǎn)：①平均檢索長(zhǎng)度小，為log2n。②每經(jīng)過(guò)一個(gè)關(guān)鍵碼值比較，那么查找范圍縮小一半，經(jīng)過(guò)log2n次比較就可完成查找過(guò)程。〔3〕缺點(diǎn)：①要求文件必須按關(guān)鍵字有序；②只適用于順序方式存儲(chǔ)的順序表。③在n很小時(shí)〔如n＜30〕，二分法查找也不比順序查找優(yōu)越。3、分塊查找又稱索引順序查找，性能介于順序查找和二分查找之間?！?〕規(guī)那么：要求文件中記錄關(guān)鍵字“分塊有序〞?！胺謮K有序〞指的是文件可按關(guān)鍵字分成假設(shè)干塊，且前一塊中最大關(guān)鍵字小于后一塊中最小關(guān)鍵字，而各塊內(nèi)部的關(guān)鍵字不一定有序?！?〕根本思想①先抽取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表；②分兩步進(jìn)行查找，第一步先對(duì)索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊。第二步在己限定的那一塊中進(jìn)行順序查找。小于17082119313322254237405261737855948879851234567891011121314151617181920R〔1：20〕213352789412345DB〔1：5〕前一塊最大關(guān)鍵字后一塊最小關(guān)鍵字注意：分塊查找的文件不一定分成大小相等的假設(shè)干塊，塊大小及其分法可根據(jù)文件的特征來(lái)定。分塊查找不僅適用于順序方式存儲(chǔ)的順序表，也適用于線性鏈表方式存儲(chǔ)的文件。返回冒泡法排序〔從小到大〕。

以6個(gè)數(shù)：3、7、5、6、8、0為例。第一趟排序情況如下：375680第一次3和7比較，不交換375680第二次7和5比較，交換357680第三次7和6比較，交換356780第四次7和8比較，不交換356780第五次8和0比較，交換356708在第一趟排序中，6個(gè)數(shù)比較了5次，把6個(gè)數(shù)中的最大數(shù)8排在最后。冒泡法排序〔續(xù)〕第二趟排序情況如下： 356708第一次3和5比較，不交換356708第二次5和6比較，不交換356708第三次6和7比較，不交換356708第四次7和0比較，交換356078在第二趟排序中，最大數(shù)8不用參加比較，其余的5個(gè)數(shù)比較了4次，把其中的最大數(shù)7排在最后，排出78。以此類推：第三趟比較3次，排出678第四趟比較2次，排出5678第五趟比較1次，排出35678最后還剩下1個(gè)數(shù)0，不需再比較，得到排序結(jié)果：035678圖9.3冒泡排序例如483562551435772240984835625562146235772277401趟2趟3趟4趟5趟6趟算法分析最壞情況下，待排序記錄按關(guān)鍵字的逆序進(jìn)行排列，此時(shí)，每一趟冒泡排序需進(jìn)行i次比較，3i次移動(dòng)。經(jīng)過(guò)n-1趟冒泡排序后，總的比較次數(shù)為總的移動(dòng)次數(shù)為3n(n-1)/2次快速排序快速排序的根本思想是：從待排序記錄序列中選取一個(gè)記錄〔通常選取第一個(gè)記錄〕，其關(guān)鍵字設(shè)為K1，然后將其余關(guān)鍵字小于K1的記錄移到前面，而將關(guān)鍵字大于K1的記錄移到后面，結(jié)果將待排序記錄序列分成兩個(gè)子表，最后將關(guān)鍵字為K1的記錄插到其分界線的位置處。我們將這個(gè)過(guò)程稱作一趟快速排序。通過(guò)一次劃分后，就以關(guān)鍵字為K1的記錄為分界線，將待排序序列分成了兩個(gè)子表，且前面子表中所有記錄的關(guān)鍵字均不大于K1，而后面子表中的所有記錄的關(guān)鍵字均不小于K1。對(duì)分割后的子表繼續(xù)按上述原那么進(jìn)行分割，直到所有子表的表長(zhǎng)不超過(guò)1為止，此時(shí)待排序記錄序列就變成了一個(gè)有序表。3849659776132749初始關(guān)鍵字49Tij27651397492738134976976549{{}}1趟ijij2713382776499765762趟4913273849657697{}}}}{{{4913273849657697}{3趟有序序列4913273849657697圖9.4快速排序圖示簡(jiǎn)單插入排序簡(jiǎn)單插入排序算法的思路是:初始可認(rèn)為文件中的第1個(gè)記錄己排好序，然后將第2個(gè)到第n個(gè)記錄依次插入已排序的記錄組成的文件中。在對(duì)第i個(gè)記錄Ri進(jìn)行插入時(shí)，R1，R2，…，Ri-1已排序，將記錄Ri的關(guān)鍵字keyi與已經(jīng)排好序的關(guān)鍵字從右向左依次比較，找到Ri應(yīng)插入的位置，將該位置以后直到Ri-1各記錄順序后移，空出該位置讓Ri插入。簡(jiǎn)單插入排序的例子。1)

{48}

62

35

77

55

14

35

98

2)

{48

62}

35

77

55

14

35

98

3)

{35

48

62}

77

55

14

35

98

4)

{35

48

62

77}

55

14

35

98

5)

{35

48

55

62

77}

14

35

98

6)

{14

35

48

55

62

77}

35

98

7)

{14

35

35

48

55

62

77}

98

8)

{14

35

35

48

55

62

77

98

}

希爾排序希爾排序〔Shell’sMethod〕又稱“縮小增量排序〞〔DiminishingIncrementSort〕，是由在1959年提出來(lái)的。希爾排序的根本思想是：先將待排序記錄序列分割成假設(shè)干個(gè)“較稀疏的〞子序列，分別進(jìn)行簡(jiǎn)單插入排序。經(jīng)過(guò)上述粗略調(diào)整，整個(gè)序列中的記錄已經(jīng)根本有序，最后再對(duì)全部記錄進(jìn)行一次直接插入排序。具體實(shí)現(xiàn):首先選定兩個(gè)記錄間的距離d1，在整個(gè)待排序記錄序列中將所有間隔為d1的記錄分成一組，進(jìn)行組內(nèi)簡(jiǎn)單插入排序，然后再取兩個(gè)記錄間的距離d2<d1，在整個(gè)待排序記錄序列中，將所有間隔為d2的記錄分成一組，進(jìn)行組內(nèi)直接插入排序直至選定兩個(gè)記錄間的距離dt=1為止，此時(shí)只有一個(gè)子序列，即整個(gè)待排序記錄序列。希爾排序過(guò)