03-算法與數(shù)據(jù)結構ppt課件

1、z設計程序首先要了解需求研討要處理的問題，提設計程序首先要了解需求研討要處理的問題，提出適當?shù)挠嬎隳Ｐ筒⒘谐鎏幚韱栴}的方法和步驟出適當?shù)挠嬎隳Ｐ筒⒘谐鎏幚韱栴}的方法和步驟, ,模型一旦建立起來，就要選擇適宜的算法，并將模型一旦建立起來，就要選擇適宜的算法，并將解題步驟表述出來解題步驟表述出來z本章著重討論處理問題的中心本章著重討論處理問題的中心 - - 算法以及算法算法以及算法的處置對象的處置對象 - - 數(shù)據(jù)的構造數(shù)據(jù)的構造z解題過程的準確、完好的描畫稱作解該問題的算法解題過程的準確、完好的描畫稱作解該問題的算法z程序就是用計算機言語表述的算法，流程圖就是圖程序就是用計算機言語表述的算法，流

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

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

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

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

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

7、，終止循環(huán)過程的然后用循環(huán)處置實現(xiàn)迭代過程，終止循環(huán)過程的條件是前后兩次得到的近似值之差的絕對值小于條件是前后兩次得到的近似值之差的絕對值小于或等于預先給定的誤差或等于預先給定的誤差z并以為最后一次迭代得到的近似值為問題的解。并以為最后一次迭代得到的近似值為問題的解。z假設一個過程直接或間接地調用它本身，那么稱假設一個過程直接或間接地調用它本身，那么稱該過程是遞歸的該過程是遞歸的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遞歸過程必需有一個遞歸終止條件，當n=0時定義為1，是階乘遞歸定義的遞歸出口遞歸那么是從函數(shù)本身出發(fā)，逐次上溯調用其本身求解過程，直到遞歸的出口，然后再從里向外倒推回來，得到最終的值z所謂遞推法，它的數(shù)學公式也是遞歸的。只是在所謂遞推法，它的數(shù)學公式也是遞歸的。只是在實現(xiàn)計算時與遞歸相反。從給定邊境出發(fā)逐漸迭實現(xiàn)計算時與遞歸相反。從給定邊境出發(fā)逐漸迭代到達指定計算參數(shù)。代到達指定計算參數(shù)。z例：求階乘例：求階乘zf(n)f(n)n! n! n n(n-1)! (n-1)

9、! n nf(n-1)f(n-1)z要計算要計算10!10!，可以從遞推初始條件，可以從遞推初始條件f(0)=1f(0)=1出發(fā)，運出發(fā)，運用遞推公式用遞推公式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í)行效率最有效的方法，科技計算中最常見科技計算中最常見z解一個夏雜的問題時，盡能夠地把這個問題分解為解一個夏雜的問題時，盡能夠地把這個問題分解為較小部分，找出各個的解，然后再把各部分的解組較小部分，找出各個的

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

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

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

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

14、間插入一個新的元素；在兩個確定的元素之間插入一個新的元素；z(2)(2)刪除線性表中某個元素；刪除線性表中某個元素；z(3)(3)按某種要求查找線性表中的一個元素，需求按某種要求查找線性表中的一個元素，需求時，還可找到元素進展值的更新時，還可找到元素進展值的更新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在順序表中插入或刪除在順序表中插入或刪除元素時，每進展一次插元素時，每進展一次插入或刪除，都要挪動近入或刪除，都要挪動近乎一半的元素。乎一半的元素。對于長度可變的線性表，對于長度可變的線性表，必需按能夠到達的最大必需按能夠到達的最大長度分配空間長度分配空間inf

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

17、構造，也可以用鏈式存儲構造造，也可以用鏈式存儲構造(2(2棧的運算棧的運算設置一個空棧設置一個空棧斷定棧能否為空斷定棧能否為空進棧、退棧進棧、退棧讀取棧頂元素等讀取棧頂元素等1 進 棧 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注 釋 ： 當 棧 空 時 返 回 函 數(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隊列的構造特點隊列的構造特點隊列隊列(Queue)(Queue)是限定一切的插入只能在表的一端進是限定一切的

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

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

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

22、，結點中指針域的個數(shù)應由樹的度來決議結點中指針域的個數(shù)應由樹的度來決議z但在實踐運用中，這種存儲構造并不方便，普通將但在實踐運用中，這種存儲構造并不方便，普通將樹轉化為二叉樹表示，進展處置樹轉化為二叉樹表示，進展處置Edatapoint1point2point3ABCDFGHIJroot(a)(b)LCDATARCroot(a)(b)ABCDEGFHIABCDDATAEFGHI2400LC780003560RC090001root123456789123456789(c)可使器具有可使器具有2 2個指針域的鏈表，個指針域的鏈表，LCLC為左指針域，指向為左指針域，指向結點的左子樹，結點的左子樹

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

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

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

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

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

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

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

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

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

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

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

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

35、關鍵其相應的關鍵字為字為K1K1，K2K2，KnKn, ,需確定一種陳列需確定一種陳列P(1),P(2)P(n)P(1),P(2)P(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使上述文件成為一個按其關鍵字線性有序的文件使上述文件成為一個按其關鍵字線性有序的文件RP(1)RP(1)，RP(2) RP(2) ，RP(n)RP(n)，這種運算就稱為排序，這種運算就稱為排序z內排序內排序 指當文件的數(shù)據(jù)量不太大時，全部信息放

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

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