03-算法與數(shù)據(jù)結(jié)構(gòu)ppt課件

1、z設(shè)計(jì)程序首先要了解需求研討要處理的問題，提設(shè)計(jì)程序首先要了解需求研討要處理的問題，提出適當(dāng)?shù)挠?jì)算模型并列出處理問題的方法和步驟出適當(dāng)?shù)挠?jì)算模型并列出處理問題的方法和步驟, ,模型一旦建立起來，就要選擇適宜的算法，并將模型一旦建立起來，就要選擇適宜的算法，并將解題步驟表述出來解題步驟表述出來z本章著重討論處理問題的中心本章著重討論處理問題的中心 - - 算法以及算法算法以及算法的處置對象的處置對象 - - 數(shù)據(jù)的構(gòu)造數(shù)據(jù)的構(gòu)造z解題過程的準(zhǔn)確、完好的描畫稱作解該問題的算法解題過程的準(zhǔn)確、完好的描畫稱作解該問題的算法z程序就是用計(jì)算機(jī)言語表述的算法，流程圖就是圖程序就是用計(jì)算機(jī)言語表述的算法，流

2、程圖就是圖形化了的算法形化了的算法z程序算法數(shù)據(jù)構(gòu)造程序算法數(shù)據(jù)構(gòu)造z3.1.1 3.1.1 算法的兩要素算法的兩要素z算法由操作與控制構(gòu)造兩要素組成算法由操作與控制構(gòu)造兩要素組成z1.1.操作操作(1) 邏輯運(yùn)算： “與、“或、“非；(2) 算術(shù)運(yùn)算： 加、減、乘、除；(3) 數(shù)據(jù)比較： 大于、小于、等于、不等于；(4) 數(shù)據(jù)傳送： 輸入、輸出、賦值。z算法的控制構(gòu)造，決議了各操作的執(zhí)行次序。用算法的控制構(gòu)造，決議了各操作的執(zhí)行次序。用流程圖流程圖 可以籠統(tǒng)地表示出算法的控制構(gòu)造可以籠統(tǒng)地表示出算法的控制構(gòu)造z任何復(fù)雜的算法都可以用順序、選擇、循環(huán)三種任何復(fù)雜的算法都可以用順序、選擇、循環(huán)三

3、種控制構(gòu)造組合而成控制構(gòu)造組合而成S1S2BS1S2BS(a)(b)(c)S3FTBFT(d)S1. 1. 算法是由一套計(jì)算規(guī)那么組成的一個(gè)過程算法是由一套計(jì)算規(guī)那么組成的一個(gè)過程2. 2. 組成算法的規(guī)那么是確定的、可執(zhí)行的組成算法的規(guī)那么是確定的、可執(zhí)行的3. 3. 每種算法必需有確定的結(jié)果，產(chǎn)生一個(gè)或多個(gè)輸出每種算法必需有確定的結(jié)果，產(chǎn)生一個(gè)或多個(gè)輸出4. 4. 每個(gè)算法必需有每個(gè)算法必需有0 0個(gè)自動(dòng)生成初始數(shù)或多個(gè)輸個(gè)自動(dòng)生成初始數(shù)或多個(gè)輸入入5. 5. 解答必需在有限步內(nèi)得到解答必需在有限步內(nèi)得到, ,不能出現(xiàn)不能出現(xiàn)“死循環(huán)死循環(huán)我們可以得出如下的結(jié)論：算法是一個(gè)過程，這個(gè)過程我

4、們可以得出如下的結(jié)論：算法是一個(gè)過程，這個(gè)過程由一套明確的規(guī)那么組成，這些規(guī)那么指定了一個(gè)操由一套明確的規(guī)那么組成，這些規(guī)那么指定了一個(gè)操作的順序，以便用有限的步驟提供特定類型問題的解作的順序，以便用有限的步驟提供特定類型問題的解答答 算法設(shè)計(jì)普通是由粗到細(xì)的過程，普通可以運(yùn)用下面算法設(shè)計(jì)普通是由粗到細(xì)的過程，普通可以運(yùn)用下面幾種類型的工具描畫算法幾種類型的工具描畫算法: :1.1.自然言語自然言語自然言語描畫算法通俗易懂，但它有著難以抑制的缺陷：自然言語描畫算法通俗易懂，但它有著難以抑制的缺陷：(1) (1) 易產(chǎn)生歧義性易產(chǎn)生歧義性 (2) (2) 語句繁瑣冗長，很難清楚地表達(dá)算法的邏輯流

5、程語句繁瑣冗長，很難清楚地表達(dá)算法的邏輯流程(3) (3) 當(dāng)今的計(jì)算機(jī)尚不能處置用自然言語表示的算法當(dāng)今的計(jì)算機(jī)尚不能處置用自然言語表示的算法2.2.公用工具公用工具常用的有流程圖、常用的有流程圖、PADPAD圖和圖和N-SN-S圖、偽代碼等圖、偽代碼等3.3.算法描畫言語算法描畫言語為了便于轉(zhuǎn)換成某種編程言語，普通采用準(zhǔn)程序設(shè)計(jì)言為了便于轉(zhuǎn)換成某種編程言語，普通采用準(zhǔn)程序設(shè)計(jì)言語作算法描畫言語。在本書中為類語作算法描畫言語。在本書中為類VBVB言語言語繼續(xù)繼續(xù) 開始結(jié)束(a) 起止框、連接框(b) 輸入輸出框AA輸入a,bN10(c) 判斷框truefalse(d) 處理框i+1i(e)

6、注釋框(f) 流向線N為正整數(shù)前往1.枚舉法窮舉法根本思想是：先根據(jù)標(biāo)題的部分條件確定答案的大致范圍在此范圍內(nèi)對一切能夠的情況逐一驗(yàn)證，直到全部情況驗(yàn)證完假設(shè)某個(gè)情況使驗(yàn)證符合標(biāo)題的條件，那么為此題的一個(gè)答案；假設(shè)全部情況驗(yàn)證完后均不符合標(biāo)題的條件，那么問題無解z使一個(gè)復(fù)雜問題的求解過程轉(zhuǎn)化為相對簡單的迭使一個(gè)復(fù)雜問題的求解過程轉(zhuǎn)化為相對簡單的迭代算式的反復(fù)執(zhí)行過程代算式的反復(fù)執(zhí)行過程z運(yùn)用迭代法構(gòu)造算法的根本方法是：運(yùn)用迭代法構(gòu)造算法的根本方法是：z首先確定一個(gè)適宜的迭代公式，選取一個(gè)初始近首先確定一個(gè)適宜的迭代公式，選取一個(gè)初始近似值以及解的誤差似值以及解的誤差z然后用循環(huán)處置實(shí)現(xiàn)迭代過程

7、，終止循環(huán)過程的然后用循環(huán)處置實(shí)現(xiàn)迭代過程，終止循環(huán)過程的條件是前后兩次得到的近似值之差的絕對值小于條件是前后兩次得到的近似值之差的絕對值小于或等于預(yù)先給定的誤差或等于預(yù)先給定的誤差z并以為最后一次迭代得到的近似值為問題的解。并以為最后一次迭代得到的近似值為問題的解。z假設(shè)一個(gè)過程直接或間接地調(diào)用它本身，那么稱假設(shè)一個(gè)過程直接或間接地調(diào)用它本身，那么稱該過程是遞歸的該過程是遞歸的z例：求階乘。例：求階乘。zFunc fac(n As Integer)Func fac(n As Integer)z If n=1 then If n=1 then z fac=1 fac=1z Else Elsez

8、 fac=n fac=n* *fac(n-1)fac(n-1)z Endif Endif 1 n=0n! n(n-1)! n0遞歸過程必需有一個(gè)遞歸終止條件，當(dāng)n=0時(shí)定義為1，是階乘遞歸定義的遞歸出口遞歸那么是從函數(shù)本身出發(fā)，逐次上溯調(diào)用其本身求解過程，直到遞歸的出口，然后再從里向外倒推回來，得到最終的值z所謂遞推法，它的數(shù)學(xué)公式也是遞歸的。只是在所謂遞推法，它的數(shù)學(xué)公式也是遞歸的。只是在實(shí)現(xiàn)計(jì)算時(shí)與遞歸相反。從給定邊境出發(fā)逐漸迭實(shí)現(xiàn)計(jì)算時(shí)與遞歸相反。從給定邊境出發(fā)逐漸迭代到達(dá)指定計(jì)算參數(shù)。代到達(dá)指定計(jì)算參數(shù)。z例：求階乘例：求階乘zf(n)f(n)n! n! n n(n-1)! (n-1)

9、! n nf(n-1)f(n-1)z要計(jì)算要計(jì)算10!10!，可以從遞推初始條件，可以從遞推初始條件f(0)=1f(0)=1出發(fā)，運(yùn)出發(fā)，運(yùn)用遞推公式用遞推公式f(n)=nf(n)=nf(n-1)f(n-1)逐漸求出逐漸求出f(1)f(1)、f(2)f(2)、f(9)f(9)、最后求出、最后求出f(10)f(10)的值的值z遞推操作是提高遞歸函數(shù)執(zhí)行效率最有效的方法，遞推操作是提高遞歸函數(shù)執(zhí)行效率最有效的方法，科技計(jì)算中最常見科技計(jì)算中最常見z解一個(gè)夏雜的問題時(shí)，盡能夠地把這個(gè)問題分解為解一個(gè)夏雜的問題時(shí)，盡能夠地把這個(gè)問題分解為較小部分，找出各個(gè)的解，然后再把各部分的解組較小部分，找出各個(gè)的

10、解，然后再把各部分的解組合成整個(gè)問題的解，這就是所謂的分治法合成整個(gè)問題的解，這就是所謂的分治法z6.6.回溯法回溯法z在那些涉及到尋覓一組解的問題或者滿足某些約束在那些涉及到尋覓一組解的問題或者滿足某些約束條件的最優(yōu)解的問題中，有許多可以用回溯法來求條件的最優(yōu)解的問題中，有許多可以用回溯法來求解解2數(shù)據(jù)構(gòu)造運(yùn)用例如例3.4識別“體字的過程丿乙亻刂借何體 休體休判斷偏旁部首四角號碼匹配局部匹配按分支和層次組織的數(shù)據(jù)，稱為：“樹形構(gòu)造z例3.5計(jì)算機(jī)換房系統(tǒng)中的“多角互換問題甲甲乙乙丙丁數(shù)據(jù)構(gòu)造叫它們?yōu)椤把h(huán)鏈表例例3.6 3.6 飯店效力系統(tǒng)中的客房預(yù)訂問題飯店效力系統(tǒng)中的客房預(yù)訂問題劉佳4.

11、14雙間張大明5.1單間王仁3.24雙間黃超8.12三間頭尾這種構(gòu)造稱為“隊(duì)列，是一種元素間先后次序很強(qiáng)的數(shù)據(jù)構(gòu)造例3.7 管理信息系統(tǒng)中的查訊問題各種計(jì)算機(jī)管理信息系統(tǒng)中，通常相關(guān)的信息(記錄)組成一個(gè)文件,文件是一類很重要的數(shù)據(jù)構(gòu)造文件中的記錄可按順序方式組織黃鵬8211編譯原理劉東8201算法分析李季為8211編譯原理李賓8202算法分析王華8202圖形學(xué)杜可翔8201編譯原理何平8201編譯原理陳紅英8211算法分析姓名班級選修課鏈鏈頭(b)(a)黃鵬8211編譯原理劉東8201算法分析李季為8211編譯原理李賓8202算法分析王華8202圖形學(xué)杜可翔8201編譯原理何平8201編譯原

12、理陳紅英8211算法分析姓名班級選修課鏈鏈頭(b)(a)順序文件導(dǎo)出的鏈表為提高檢索效率，可將一切選修“算法分析課的同窗記錄串接到一同，這種串接稱為“加鏈z線性表的邏輯構(gòu)造是線性表的邏輯構(gòu)造是n n個(gè)數(shù)據(jù)元素的有限序列個(gè)數(shù)據(jù)元素的有限序列: :z(a1, a2 ,a3,an) (a1, a2 ,a3,an) zn n為線性表的長度為線性表的長度(n0)(n0)，n=0n=0的表稱為空表的表稱為空表z數(shù)據(jù)元素呈線性關(guān)系數(shù)據(jù)元素呈線性關(guān)系. .必存在獨(dú)一的稱為必存在獨(dú)一的稱為“第一個(gè)第一個(gè)的數(shù)據(jù)元素的數(shù)據(jù)元素; ;必存在獨(dú)一的稱為必存在獨(dú)一的稱為“最后一個(gè)的數(shù)據(jù)最后一個(gè)的數(shù)據(jù)元素；元素；z除第一個(gè)

13、元素外，每個(gè)元素都有且只需一個(gè)前驅(qū)元除第一個(gè)元素外，每個(gè)元素都有且只需一個(gè)前驅(qū)元素；素； 除最后一個(gè)元素外，每個(gè)元素都有且只需一個(gè)除最后一個(gè)元素外，每個(gè)元素都有且只需一個(gè)后繼元素。后繼元素。z一切數(shù)據(jù)元素一切數(shù)據(jù)元素aiai在同一個(gè)線性表中必需是一樣的數(shù)在同一個(gè)線性表中必需是一樣的數(shù)據(jù)類型據(jù)類型z線性表按其存儲構(gòu)造可分為順序表和鏈表。用順線性表按其存儲構(gòu)造可分為順序表和鏈表。用順序存儲構(gòu)造存儲的線性表稱為順序表；用鏈?zhǔn)酱嫘虼鎯?gòu)造存儲的線性表稱為順序表；用鏈?zhǔn)酱鎯?gòu)造存儲的線性表稱為鏈表儲構(gòu)造存儲的線性表稱為鏈表z線性表的根本運(yùn)算主要有：線性表的根本運(yùn)算主要有：z(1)(1)在兩個(gè)確定的元素之

14、間插入一個(gè)新的元素；在兩個(gè)確定的元素之間插入一個(gè)新的元素；z(2)(2)刪除線性表中某個(gè)元素；刪除線性表中某個(gè)元素；z(3)(3)按某種要求查找線性表中的一個(gè)元素，需求按某種要求查找線性表中的一個(gè)元素，需求時(shí)，還可找到元素進(jìn)展值的更新時(shí)，還可找到元素進(jìn)展值的更新PROC INSERT (VAR A,VAR n,i,x)If(in+1) Then ERROR(“位置不存在！) Else For j=n Down To i A(j+1)=A(j) Next j Endif A(i)=x n=n+1 EndPROC DELETE (VAR A,VAR n,I)PROC DELETE (VAR A,V

15、AR n,I)If (in) ThenIf (in) Then ERROR ( ERROR (位置不存在！位置不存在！) ) ELSE ELSE FOR j=i TO n-1 FOR j=i TO n-1 A(j)=A(j+1) A(j)=A(j+1) Next j Next j n=n-1 n=n-1 EndifEndifEndEnd在順序表中插入或刪除在順序表中插入或刪除元素時(shí)，每進(jìn)展一次插元素時(shí)，每進(jìn)展一次插入或刪除，都要挪動(dòng)近入或刪除，都要挪動(dòng)近乎一半的元素。乎一半的元素。對于長度可變的線性表，對于長度可變的線性表，必需按能夠到達(dá)的最大必需按能夠到達(dá)的最大長度分配空間長度分配空間inf

16、onext信息域指針域abHeadabHeadx acHeadb 結(jié)點(diǎn)1結(jié)點(diǎn)2結(jié)點(diǎn)nz棧棧(STACK)(STACK)也是一種特殊的線性也是一種特殊的線性表，是一種表，是一種“后進(jìn)先出的構(gòu)造，后進(jìn)先出的構(gòu)造，它的運(yùn)算規(guī)那么遭到一些約束和它的運(yùn)算規(guī)那么遭到一些約束和限定，故又稱限定性數(shù)據(jù)構(gòu)造限定，故又稱限定性數(shù)據(jù)構(gòu)造z(1(1棧的構(gòu)造特點(diǎn)棧的構(gòu)造特點(diǎn)z棧是限定僅在表尾進(jìn)展插入和刪棧是限定僅在表尾進(jìn)展插入和刪除運(yùn)算的線性表，表尾稱為棧頂除運(yùn)算的線性表，表尾稱為棧頂(top)(top)，表頭稱為棧底，表頭稱為棧底(bottom)(bottom)z棧的物理存儲可以用順序存儲構(gòu)棧的物理存儲可以用順序存儲

17、構(gòu)造，也可以用鏈?zhǔn)酱鎯?gòu)造造，也可以用鏈?zhǔn)酱鎯?gòu)造(2(2棧的運(yùn)算棧的運(yùn)算設(shè)置一個(gè)空棧設(shè)置一個(gè)空棧斷定棧能否為空斷定棧能否為空進(jìn)棧、退棧進(jìn)棧、退棧讀取棧頂元素等讀取棧頂元素等1 進(jìn) 棧 PROCEDURE PUSHSTACK (VAR STACK， m， VAR top， x) 注 釋 ： 在 棧 STACK(1:m)的 棧 頂 top之 上 插 入 元 素 x BEGIN IF top=m THEN ERROR (“棧 滿 ！ ”) ELSE top=top+1 注 釋 ： 棧 頂 上 移 STACK(top)=x 注 釋 ： 將 x放 入 棧 頂 ENDIF END2 退 棧 FUNCTI

18、ON POPSTACK (VAR STACK， VAR top， VAR y)： VAR注 釋 ： 當(dāng) 棧 空 時(shí) 返 回 函 數(shù) 值 FALSE，反 之 退 出 棧 頂 元 素 賦 給 變 量 y并 返 回 函 數(shù) 值 TRUE BEGIN IF top=0 THEN RETURN (FALSE) ELSE y=STACK(top) 注 釋 ： 將 棧 頂 元 素 賦 給 變 量 y top=top-1 注 釋 ： 棧 頂 下 移 RETURN (TRUE) ENDIF END(1(1隊(duì)列的構(gòu)造特點(diǎn)隊(duì)列的構(gòu)造特點(diǎn)隊(duì)列隊(duì)列(Queue)(Queue)是限定一切的插入只能在表的一端進(jìn)是限定一切的

19、插入只能在表的一端進(jìn)展，而一切的刪除都在表的另一端進(jìn)展的線性表展，而一切的刪除都在表的另一端進(jìn)展的線性表表中允許插入的一端稱為隊(duì)尾表中允許插入的一端稱為隊(duì)尾(Rear)(Rear)，允許刪除的，允許刪除的一端稱為隊(duì)頭一端稱為隊(duì)頭(Front)(Front)隊(duì)列的操作是按先進(jìn)先出的原那么進(jìn)展的隊(duì)列的操作是按先進(jìn)先出的原那么進(jìn)展的隊(duì)列的物理存儲可以用順序存儲構(gòu)造，也可以用鏈隊(duì)列的物理存儲可以用順序存儲構(gòu)造，也可以用鏈?zhǔn)酱鎯?gòu)造。式存儲構(gòu)造。a1 a2 a3 an入隊(duì)列出隊(duì)列頭尾z假設(shè)隊(duì)列的容量無法預(yù)先估計(jì)時(shí)，可以采用鏈表存儲構(gòu)造AABBBCBCDCDECD初態(tài)插入A插入B刪除A插入C插入D刪除B插

20、入EFRFRFRFRFRRFRFFR循環(huán)隊(duì)列的插入、刪除循環(huán)隊(duì)列的插入、刪除隊(duì)尾隊(duì)頭FrontRearz串(String)可以看作一維字符數(shù)組，但其長度不恒定，可以作刪除、插入操作z許多高級言語把串作為一種單獨(dú)的類型，其元素不可作四那么運(yùn)算z進(jìn)展銜接、刪除、插入操作，用子串有時(shí)很方便z子串(Substring)是串的一部分，具有串的一切特征AAFEDCBJHIGz0 0棵或多棵不相交的樹的集合稱為樹林棵或多棵不相交的樹的集合稱為樹林z二叉樹是另一種重要的樹形構(gòu)造，其構(gòu)造定義為：二叉樹是另一種重要的樹形構(gòu)造，其構(gòu)造定義為：二叉樹二叉樹(Binary Tree)(Binary Tree)是是n(n

21、0)n(n0)個(gè)結(jié)點(diǎn)的有限集，個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛渌驗(yàn)榭諛?n=0)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為根的左子樹和右子樹的、互不相交的二叉樹組成根的左子樹和右子樹的、互不相交的二叉樹組成z二叉樹的邏輯構(gòu)造：二叉樹的邏輯構(gòu)造：z二叉樹的結(jié)點(diǎn)的子樹要區(qū)分二叉樹的結(jié)點(diǎn)的子樹要區(qū)分z左子樹和右子樹，即使左子樹和右子樹，即使z在結(jié)點(diǎn)只需一棵子在結(jié)點(diǎn)只需一棵子z樹的情況下也要明確指出該樹的情況下也要明確指出該z子樹是左子樹還是右子樹子樹是左子樹還是右子樹AGDCBIHEFz樹的存儲構(gòu)造可以采器具有多個(gè)指針域的多重鏈表，樹的存儲構(gòu)造可以采器具有多個(gè)指針域的多重鏈表

22、，結(jié)點(diǎn)中指針域的個(gè)數(shù)應(yīng)由樹的度來決議結(jié)點(diǎn)中指針域的個(gè)數(shù)應(yīng)由樹的度來決議z但在實(shí)踐運(yùn)用中，這種存儲構(gòu)造并不方便，普通將但在實(shí)踐運(yùn)用中，這種存儲構(gòu)造并不方便，普通將樹轉(zhuǎn)化為二叉樹表示，進(jìn)展處置樹轉(zhuǎn)化為二叉樹表示，進(jìn)展處置Edatapoint1point2point3ABCDFGHIJroot(a)(b)LCDATARCroot(a)(b)ABCDEGFHIABCDDATAEFGHI2400LC780003560RC090001root123456789123456789(c)可使器具有可使器具有2 2個(gè)指針域的鏈表，個(gè)指針域的鏈表，LCLC為左指針域，指向?yàn)樽笾羔樣?，指向結(jié)點(diǎn)的左子樹，結(jié)點(diǎn)的左子樹

23、，RCRC為右指針域，指向結(jié)點(diǎn)的右子樹。為右指針域，指向結(jié)點(diǎn)的右子樹。亦可用數(shù)組的下標(biāo)來模擬指針，即開辟三個(gè)一維數(shù)亦可用數(shù)組的下標(biāo)來模擬指針，即開辟三個(gè)一維數(shù)組組DATADATA，LCLC和和RCRC分別存放結(jié)點(diǎn)的元素及其左、右指分別存放結(jié)點(diǎn)的元素及其左、右指針針z每一棵都能獨(dú)一地轉(zhuǎn)換到它所對應(yīng)的二叉樹z轉(zhuǎn)換方法：凡是兄弟就用線銜接起來，對每個(gè)非終端結(jié)點(diǎn)，除其最左孩子外，刪去該結(jié)點(diǎn)與其他孩子結(jié)點(diǎn)的連線，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)450AGDCBIHEFJAAFEDCBJHIGz 樹的遍歷樹的遍歷z 根據(jù)樹的遞歸定義，有兩種遍歷樹的方法：根據(jù)樹的遞歸定義，有兩種遍歷樹的方法：z (1)(1)先

24、根先根( (次序次序) )遍歷：假設(shè)樹中只需一個(gè)根結(jié)點(diǎn)，遍歷：假設(shè)樹中只需一個(gè)根結(jié)點(diǎn)，那么訪問樹的根結(jié)點(diǎn)；那么訪問樹的根結(jié)點(diǎn)； 否那么，首先訪問樹的否那么，首先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷每棵子樹。根結(jié)點(diǎn)，然后依次先根遍歷每棵子樹。z (2)(2)后根后根( (次序次序) )遍歷：假設(shè)樹中只需一個(gè)根結(jié)點(diǎn)，遍歷：假設(shè)樹中只需一個(gè)根結(jié)點(diǎn)，那么訪問樹的根結(jié)點(diǎn)；那么訪問樹的根結(jié)點(diǎn)； 否那么，首先依次后根否那么，首先依次后根遍歷每一棵子樹，然后訪問樹的根結(jié)點(diǎn)。遍歷每一棵子樹，然后訪問樹的根結(jié)點(diǎn)。(3)(3)后序遍歷二叉樹的算法為：后序遍歷二叉樹的算法為： 假設(shè)二叉樹不空，那么：假設(shè)二叉樹不空，那么：

25、 a) a) 后序遍歷左子樹；后序遍歷左子樹； b) b) 后序遍歷右子樹；后序遍歷右子樹； c) c) 訪問根結(jié)點(diǎn)。訪問根結(jié)點(diǎn)。前圖用后序遍歷為：前圖用后序遍歷為：FEGJIHDCBAFEGJIHDCBA(1)前序遍歷二叉樹算法為： 假設(shè)二叉樹不空，那么： a) 訪問根結(jié)點(diǎn)； b) 前序遍歷左子樹； c) 前序遍歷右子樹。前圖用前序遍歷為ABEFCGDHIJ(2)(2)中序遍歷二叉樹的算法為：中序遍歷二叉樹的算法為： 假設(shè)二叉樹不空，那么作：假設(shè)二叉樹不空，那么作： a) a) 中序遍歷左子樹；中序遍歷左子樹； b) b) 訪問根結(jié)點(diǎn)；訪問根結(jié)點(diǎn)； c) c) 中序遍歷右子樹。中序遍歷右子樹

26、。前圖用中序遍歷為：前圖用中序遍歷為：EFBGCHIJDAEFBGCHIJDAz常用常用G=(V,E)G=(V,E)代表一個(gè)圖，代表一個(gè)圖，V V是結(jié)點(diǎn)的有窮集合是結(jié)點(diǎn)的有窮集合( (非空非空) )，E E是邊的有窮集合是邊的有窮集合(E(E可為空集可為空集) )。假設(shè)一條邊的結(jié)點(diǎn)對無。假設(shè)一條邊的結(jié)點(diǎn)對無序，那么稱無向圖。序，那么稱無向圖。(V1,V2)(V1,V2)和和(V2,V1)(V2,V1)一樣一樣z有向圖由頂點(diǎn)的非空有限集和邊的有限有向圖由頂點(diǎn)的非空有限集和邊的有限z集組成。集組成。(V1,V2)(V1,V2)和和(V2,V1)(V2,V1)表示不同邊表示不同邊zn n個(gè)頂點(diǎn)的無向

27、圖邊的最大數(shù)目是個(gè)頂點(diǎn)的無向圖邊的最大數(shù)目是n(n-1)/2n(n-1)/2。zn n個(gè)頂點(diǎn)的有向圖邊的最大數(shù)目為個(gè)頂點(diǎn)的有向圖邊的最大數(shù)目為n2n2雙環(huán)且自環(huán)。雙環(huán)且自環(huán)。z假設(shè)假設(shè)(V1, V2)E(V1, V2)E，那么稱，那么稱V1V1和和V2V2是相鄰結(jié)點(diǎn)。邊是相鄰結(jié)點(diǎn)。邊(V1, (V1, V2)V2)是是V1V1和和V2V2相關(guān)聯(lián)的邊。一個(gè)結(jié)點(diǎn)的度是與該結(jié)點(diǎn)相相關(guān)聯(lián)的邊。一個(gè)結(jié)點(diǎn)的度是與該結(jié)點(diǎn)相關(guān)聯(lián)的邊的數(shù)目。對于有向圖，那么把以結(jié)點(diǎn)關(guān)聯(lián)的邊的數(shù)目。對于有向圖，那么把以結(jié)點(diǎn)ViVi為終點(diǎn)為終點(diǎn)的邊的數(shù)目稱結(jié)點(diǎn)的邊的數(shù)目稱結(jié)點(diǎn)ViVi的入度；的入度； 把以把以ViVi為始點(diǎn)的邊的數(shù)

28、為始點(diǎn)的邊的數(shù)目稱為目稱為ViVi的出度。出度為的出度。出度為0 0的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)。的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)。V1V2V3V4z假設(shè)G是一個(gè)具有n個(gè)結(jié)點(diǎn)的圖，那么G的相鄰矩陣是:z (2)圖的鄰接表表示法z用鄰接表法表示有向圖，根據(jù)需求可以保管每個(gè)結(jié)點(diǎn)的出邊表，也可以保管每個(gè)結(jié)點(diǎn)的入邊表Ai,j =1，若(Vi，Vj)是圖 G 的邊0，若(Vi，Vj)不是圖 G 的邊V1V2V3V412342111332244結(jié)點(diǎn)表邊表V1V2V3V4根本思想是：從圖中某個(gè)根本思想是：從圖中某個(gè)V V出發(fā)，訪問此結(jié)點(diǎn)，再依出發(fā)，訪問此結(jié)點(diǎn)，再依次訪問一切與次訪問一切與V V有途徑的結(jié)點(diǎn)。完成后再另選圖中有途徑的

29、結(jié)點(diǎn)。完成后再另選圖中一個(gè)未被訪問的結(jié)點(diǎn)作始點(diǎn)，反復(fù)上述過程，直一個(gè)未被訪問的結(jié)點(diǎn)作始點(diǎn)，反復(fù)上述過程，直至圖中一切結(jié)點(diǎn)都被訪問到為止。至圖中一切結(jié)點(diǎn)都被訪問到為止。(2)(2)廣度優(yōu)先遍歷廣度優(yōu)先遍歷根本思想是：從某個(gè)結(jié)點(diǎn)根本思想是：從某個(gè)結(jié)點(diǎn)V V出發(fā)，訪問此結(jié)點(diǎn)，再依出發(fā)，訪問此結(jié)點(diǎn)，再依次訪問次訪問V V鄰接的未訪問結(jié)點(diǎn)。再從這些結(jié)點(diǎn)出發(fā)進(jìn)鄰接的未訪問結(jié)點(diǎn)。再從這些結(jié)點(diǎn)出發(fā)進(jìn)展廣度優(yōu)先遍歷，直至圖中一切被訪問過的結(jié)點(diǎn)展廣度優(yōu)先遍歷，直至圖中一切被訪問過的結(jié)點(diǎn)的相鄰結(jié)點(diǎn)都被訪問到。完成后另選圖中一個(gè)未的相鄰結(jié)點(diǎn)都被訪問到。完成后另選圖中一個(gè)未曾訪問的結(jié)點(diǎn)作始點(diǎn)，反復(fù)上述過程，直至圖中曾訪

30、問的結(jié)點(diǎn)作始點(diǎn)，反復(fù)上述過程，直至圖中一切結(jié)點(diǎn)都被訪問到為止一切結(jié)點(diǎn)都被訪問到為止3.3.1 3.3.1 根本概念根本概念關(guān)鍵字關(guān)鍵字 是數(shù)據(jù)元素中可以獨(dú)一標(biāo)識一個(gè)數(shù)據(jù)元素的是數(shù)據(jù)元素中可以獨(dú)一標(biāo)識一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)，比如學(xué)號、身份證號等，數(shù)據(jù)項(xiàng)，比如學(xué)號、身份證號等，查找查找 是根據(jù)給定的關(guān)鍵值，在一組數(shù)據(jù)中確定一個(gè)是根據(jù)給定的關(guān)鍵值，在一組數(shù)據(jù)中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素的過程其關(guān)鍵字等于給定值的數(shù)據(jù)元素的過程確切定義：給定一個(gè)值確切定義：給定一個(gè)值K K，在含有，在含有n n個(gè)記錄的文件中進(jìn)個(gè)記錄的文件中進(jìn)展搜索，尋覓一個(gè)其關(guān)鍵字等于給定的展搜索，尋覓一個(gè)其關(guān)鍵字等于給定的K

31、 K值的記錄，值的記錄，如找到，那么輸出記錄或記錄在文件中的相對位置如找到，那么輸出記錄或記錄在文件中的相對位置稱查找勝利；否那么輸出查找不勝利的信息稱查找稱查找勝利；否那么輸出查找不勝利的信息稱查找失敗。失敗。z順序查找的方法是：用待查關(guān)鍵字值與線性表中各結(jié)點(diǎn)順序查找的方法是：用待查關(guān)鍵字值與線性表中各結(jié)點(diǎn)的關(guān)鍵字值逐個(gè)比較，直到找出相等的關(guān)鍵字值的關(guān)鍵字值逐個(gè)比較，直到找出相等的關(guān)鍵字值; ;或找遍或找遍一切結(jié)點(diǎn)都找不到一切結(jié)點(diǎn)都找不到, ,即查找失敗即查找失敗z順序查找的優(yōu)點(diǎn)是對線性表結(jié)點(diǎn)的邏輯次序無要求順序查找的優(yōu)點(diǎn)是對線性表結(jié)點(diǎn)的邏輯次序無要求, ,對對線性表的存儲構(gòu)造無要求線性表的

32、存儲構(gòu)造無要求, ,缺陷是平均檢索長度長缺陷是平均檢索長度長, ,為為n/2n/2z2.2.二分法查找二分法查找z要求線性表結(jié)點(diǎn)按關(guān)鍵字碼值排好，且以順序方式存儲要求線性表結(jié)點(diǎn)按關(guān)鍵字碼值排好，且以順序方式存儲z用要查找的碼值用要查找的碼值X X與中間位置結(jié)點(diǎn)的關(guān)鍵碼值與中間位置結(jié)點(diǎn)的關(guān)鍵碼值W W相比較：相比較：z (1)X=W (1)X=W，此時(shí)曾經(jīng)查找勝利，查找終了。，此時(shí)曾經(jīng)查找勝利，查找終了。z (2)XW, (2)XW,闡明闡明X X在表的后半部分在表的后半部分, ,取后半部分進(jìn)展查找取后半部分進(jìn)展查找z (3)XW, (3)XW,闡明闡明X X在表的前半部分，取前半部分進(jìn)展查找在

33、表的前半部分，取前半部分進(jìn)展查找z二分法查找的優(yōu)點(diǎn)是平均檢索長度小，為二分法查找的優(yōu)點(diǎn)是平均檢索長度小，為log2nlog2nz要求文件中記錄關(guān)鍵字要求文件中記錄關(guān)鍵字“分塊有序分塊有序, ,即前一塊中最大關(guān)即前一塊中最大關(guān)鍵字小于后一塊中最小關(guān)鍵字鍵字小于后一塊中最小關(guān)鍵字, ,而塊內(nèi)的關(guān)鍵字不一定有而塊內(nèi)的關(guān)鍵字不一定有序序z分塊查找的根本思想分塊查找的根本思想 ：先抽取各塊中的最大關(guān)鍵字構(gòu)：先抽取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表，由于文件中的記錄按關(guān)鍵字分塊有序，成一個(gè)索引表，由于文件中的記錄按關(guān)鍵字分塊有序，那么索引表呈遞增有序形狀。查找分兩步進(jìn)展那么索引表呈遞增有序形狀。查找分兩步進(jìn)

34、展: :第一步先第一步先對索引表進(jìn)展二分查找或順序查找，以確定待查記錄在對索引表進(jìn)展二分查找或順序查找，以確定待查記錄在哪一塊，第二步在已限定的那一塊中進(jìn)展順序查找哪一塊，第二步在已限定的那一塊中進(jìn)展順序查找z用分塊查找的文件不一定分成大小相等的假設(shè)干塊，塊用分塊查找的文件不一定分成大小相等的假設(shè)干塊，塊大小及其分法可根據(jù)文件的特征來定。分塊查找不僅適大小及其分法可根據(jù)文件的特征來定。分塊查找不僅適用于順序方式存儲的順序表，也適用于線性鏈表方式存用于順序方式存儲的順序表，也適用于線性鏈表方式存儲的文件儲的文件z設(shè)含有設(shè)含有n n個(gè)記錄的文件個(gè)記錄的文件R1R1，R2R2，RnRn, ,其相應(yīng)的

35、關(guān)鍵其相應(yīng)的關(guān)鍵字為字為K1K1，K2K2，KnKn, ,需確定一種陳列需確定一種陳列P(1),P(2)P(n)P(1),P(2)P(n)使其相應(yīng)的關(guān)鍵字滿足遞增使其相應(yīng)的關(guān)鍵字滿足遞增( (或遞減或遞減) )關(guān)系：關(guān)系：z KP(1)KP(2)KP(n) KP(1)KP(2)KP(n) 或或KP(1)KP(2)KP(n)KP(1)KP(2)KP(n)z使上述文件成為一個(gè)按其關(guān)鍵字線性有序的文件使上述文件成為一個(gè)按其關(guān)鍵字線性有序的文件RP(1)RP(1)，RP(2) RP(2) ，RP(n)RP(n)，這種運(yùn)算就稱為排序，這種運(yùn)算就稱為排序z內(nèi)排序內(nèi)排序 指當(dāng)文件的數(shù)據(jù)量不太大時(shí)，全部信息放

36、在內(nèi)指當(dāng)文件的數(shù)據(jù)量不太大時(shí)，全部信息放在內(nèi)存中處置的排序方法。當(dāng)文件的數(shù)據(jù)量較大時(shí)，排序過存中處置的排序方法。當(dāng)文件的數(shù)據(jù)量較大時(shí)，排序過程中需求在內(nèi)、外存之間不斷地進(jìn)展數(shù)據(jù)交換才干到達(dá)程中需求在內(nèi)、外存之間不斷地進(jìn)展數(shù)據(jù)交換才干到達(dá)排序的目的，這種排序稱為外排序排序的目的，這種排序稱為外排序z根本思想是：每步將一個(gè)待排序的記錄，按關(guān)鍵碼值的根本思想是：每步將一個(gè)待排序的記錄，按關(guān)鍵碼值的大小插入到前面已排序的適當(dāng)位置上，直到全部插完止大小插入到前面已排序的適當(dāng)位置上，直到全部插完止z1. 1. 直接插入排序：在排好的序列中用順序法查找插入直接插入排序：在排好的序列中用順序法查找插入位置，找

37、到后將其后記錄后移一個(gè)位置，插入新記錄。位置，找到后將其后記錄后移一個(gè)位置，插入新記錄。排序排序n n個(gè)記錄的文件，關(guān)鍵碼比較次數(shù)為個(gè)記錄的文件，關(guān)鍵碼比較次數(shù)為n2n2量級，記錄量級，記錄挪動(dòng)個(gè)數(shù)也為挪動(dòng)個(gè)數(shù)也為n2n2量級量級z2. 2. 二分法插入排序：在已排好序的序列中運(yùn)用二分法二分法插入排序：在已排好序的序列中運(yùn)用二分法查找插入位置，找到后挪動(dòng)其后記錄插入新記錄。關(guān)鍵查找插入位置，找到后挪動(dòng)其后記錄插入新記錄。關(guān)鍵字比較次數(shù)降為字比較次數(shù)降為nlog2nnlog2n量級，記錄挪動(dòng)個(gè)數(shù)仍為量級，記錄挪動(dòng)個(gè)數(shù)仍為n2n2量級量級z根本思想是：每次從待排序的記錄中選出關(guān)鍵字最小根本思想是：每次從待排序的記錄中