算法和數(shù)據(jù)結(jié)構(gòu)

第三章算法與數(shù)據(jù)結(jié)構(gòu)設(shè)計程序首先要了解需要研究要解決的問題，提出適當(dāng)?shù)挠嬎隳Ｐ筒⒘谐鼋鉀Q問題的方法和步驟,模型一旦建立起來，就要選擇合適的算法，并將解題步驟表述出來本章著重討論解決問題的核心--算法以及算法的處理對象--數(shù)據(jù)的結(jié)構(gòu)算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第1頁。3．1算法解題過程的準(zhǔn)確、完整的描述稱作解該問題的算法程序就是用計算機語言表述的算法，流程圖就是圖形化了的算法程序＝算法＋數(shù)據(jù)結(jié)構(gòu)3.1.1算法的兩要素算法由操作與控制結(jié)構(gòu)兩要素組成1.操作(1)邏輯運算：“與”、“或”、“非”；(2)算術(shù)運算：加、減、乘、除；(3)數(shù)據(jù)比較：大于、小于、等于、不等于；(4)數(shù)據(jù)傳送：輸入、輸出、賦值。算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第2頁。2.控制結(jié)構(gòu)算法的控制結(jié)構(gòu)，決定了各操作的執(zhí)行次序。用流程圖可以形象地表示出算法的控制結(jié)構(gòu)任何復(fù)雜的算法都可以用順序、選擇、循環(huán)三種控制結(jié)構(gòu)組合而成算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第3頁。3.1.2算法的特征1.算法是由一套計算規(guī)則組成的一個過程2.組成算法的規(guī)則是確定的、可執(zhí)行的3.每種算法必須有確定的結(jié)果，產(chǎn)生一個或多個輸出4.每個算法必須有0個（自動生成初始數(shù)）或多個輸入5.解答必須在有限步內(nèi)得到,不能出現(xiàn)“死循環(huán)”我們可以得出如下的結(jié)論：算法是一個過程，這個過程由一套明確的規(guī)則組成，這些規(guī)則指定了一個操作的順序，以便用有限的步驟提供特定類型問題的解答算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第4頁。3.1.3算法的表示算法設(shè)計一般是由粗到細(xì)的過程，一般可以使用下面幾種類型的工具描述算法:1.自然語言自然語言描述算法通俗易懂，但它有著難以克服的缺陷：(1)易產(chǎn)生歧義性(2)語句繁瑣冗長，很難清楚地表達(dá)算法的邏輯流程(3)當(dāng)今的計算機尚不能處理用自然語言表示的算法2.專用工具常用的有流程圖、PAD圖和N-S圖、偽代碼等3.算法描述語言為了便于轉(zhuǎn)換成某種編程語言，一般采用準(zhǔn)程序設(shè)計語言作算法描述語言。在本書中為類VB語言繼續(xù)算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第5頁。流程圖

是采用不同的幾何圖形來描述算法的邏輯結(jié)構(gòu)，每個幾何圖形表示不同性質(zhì)的操作常用流程圖符號：返回算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第6頁。1.枚舉法（窮舉法）基本思想是：先依據(jù)題目的部分條件確定答案的大致范圍在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完若某個情況使驗證符合題目的條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解3.1.4常用算法算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第7頁。2.迭代法使一個復(fù)雜問題的求解過程轉(zhuǎn)化為相對簡單的迭代算式的重復(fù)執(zhí)行過程使用迭代法構(gòu)造算法的基本方法是：首先確定一個合適的迭代公式，選取一個初始近似值以及解的誤差然后用循環(huán)處理實現(xiàn)迭代過程，終止循環(huán)過程的條件是前后兩次得到的近似值之差的絕對值小于或等于預(yù)先給定的誤差并認(rèn)為最后一次迭代得到的近似值為問題的解。算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第8頁。3.遞歸法如果一個過程直接或間接地調(diào)用它自身，則稱該過程是遞歸的例：求階乘。Funcfac(nAsInteger)Ifn=1thenfac=1Elsefac=n*fac(n-1)Endif遞歸過程必須有一個遞歸終止條件，當(dāng)n=0時定義為1，是階乘遞歸定義的遞歸出口遞歸則是從函數(shù)本身出發(fā)，逐次上溯調(diào)用其本身求解過程，直到遞歸的出口，然后再從里向外倒推回來，得到最終的值算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第9頁。4.遞推法所謂遞推法，它的數(shù)學(xué)公式也是遞歸的。只是在實現(xiàn)計算時與遞歸相反。從給定邊界出發(fā)逐步迭代到達(dá)指定計算參數(shù)。例：求階乘f(n)＝n!＝n×(n-1)!＝n×f(n-1)要計算10!，可以從遞推初始條件f(0)=1出發(fā)，應(yīng)用遞推公式f(n)=n×f(n-1)逐步求出f(1)、f(2)…、f(9)、最后求出f(10)的值遞推操作是提高遞歸函數(shù)執(zhí)行效率最有效的方法，科技計算中最常見算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第10頁。5.分治法解一個夏雜的問題時，盡可能地把這個問題分解為較小部分，找出各個的解，然后再把各部分的解組合成整個問題的解，這就是所謂的分治法6.回溯法在那些涉及到尋找一組解的問題或者滿足某些約束條件的最優(yōu)解的問題中，有許多可以用回溯法來求解算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第11頁?；厮莘ǖ乃惴ㄊ牵篜rocBacktracking(succ:Boolean)確定起始狀態(tài)值走第一步確定下一步還有幾種可能選一可能走下一步，記住可能和本步特征做完新一步應(yīng)做的事While目標(biāo)未達(dá)到do

確定下一步有幾種可能

While沒有可能and還有上一步do

回退上一步查有無下一可能

Enddo

If上一步?jīng)]有了Thenreturn(SUCC=FALSE)

EndIf選一可能走一步，記住可能和本步特征做完新一步應(yīng)做的事Enddoreturn(SUCC=TRUE)EndBacktracking算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第12頁。3.2數(shù)據(jù)結(jié)構(gòu)

3.2.1數(shù)據(jù)結(jié)構(gòu)概述。1．?dāng)?shù)據(jù)結(jié)構(gòu)的研究內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運算

數(shù)據(jù)的邏輯結(jié)構(gòu)：Data-Structure＝(D,R)其中：D是數(shù)據(jù)元素的集合，R是D上關(guān)系的集合一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)。線性數(shù)據(jù)結(jié)構(gòu)有線性表、棧、隊列、串、數(shù)組和文件；非線性數(shù)據(jù)結(jié)構(gòu)有樹和圖程序中的數(shù)據(jù)運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，但運算的具體實現(xiàn)要在存儲結(jié)構(gòu)上進(jìn)行。每種邏輯結(jié)構(gòu)都有一個運算集合。常用的運算有檢索、插入、刪除、更新、排序等算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第13頁。2．?dāng)?shù)據(jù)結(jié)構(gòu)應(yīng)用示例例3.4識別“體”字的過程按分支和層次組織的數(shù)據(jù)，稱為：“樹形結(jié)構(gòu)”算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第14頁。例3.5計算機換房系統(tǒng)中的“多角互換問題”數(shù)據(jù)結(jié)構(gòu)叫它們?yōu)椤把h(huán)鏈表”例3.6飯店服務(wù)系統(tǒng)中的客房預(yù)訂問題這種結(jié)構(gòu)稱為“隊列”，是一種元素間先后次序很強的數(shù)據(jù)結(jié)構(gòu)算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第15頁。例3.7管理信息系統(tǒng)中的查詢問題 各種計算機管理信息系統(tǒng)中，通常相關(guān)的信息(記錄)組成一個文件,文件是一類很重要的數(shù)據(jù)結(jié)構(gòu)文件中的記錄可按順序方式組織順序文件導(dǎo)出的鏈表為提高檢索效率，可將所有選修“算法分析”課的同學(xué)記錄串接到一起，這種串接稱為“加鏈”算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第16頁。3.2.2線性表線性表的邏輯結(jié)構(gòu)是n個數(shù)據(jù)元素的有限序列: (a1,a2,a3,…an)

n為線性表的長度(n≥0)，n=0的表稱為空表數(shù)據(jù)元素呈線性關(guān)系.必存在唯一的稱為“第一個”的數(shù)據(jù)元素;必存在唯一的稱為“最后一個”的數(shù)據(jù)元素；除第一個元素外，每個元素都有且只有一個前驅(qū)元素；除最后一個元素外，每個元素都有且只有一個后繼元素。所有數(shù)據(jù)元素ai在同一個線性表中必須是相同的數(shù)據(jù)類型算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第17頁。線性表按其存儲結(jié)構(gòu)可分為順序表和鏈表。用順序存儲結(jié)構(gòu)存儲的線性表稱為順序表；用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的線性表稱為鏈表線性表的基本運算主要有：(1)在兩個確定的元素之間插入一個新的元素；(2)刪除線性表中某個元素；(3)按某種要求查找線性表中的一個元素，需要時，還可找到元素進(jìn)行值的更新算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第18頁。1.順序表和一維數(shù)組將線性表中的數(shù)據(jù)元素依次存放在某個存儲區(qū)域中,所形成的表稱為順序表。一維數(shù)組就是用順序方式存儲的線性表，其下標(biāo)可看成元素的相對地址運算：(1)插入，在線性表(a1,a2…，ai，ai+1…，an)的第i個位置插入元素x，算法如下：PROCINSERT(VARA,VARn,i,x)If(i<1)Or(i>n+1)ThenERROR(“位置不存在！”)

ElseForj=nDownToiA(j+1)=A(j)

NextjEndifA(i)=x

n=n+1End算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第19頁。(2)刪除：在表長為n的線性表(a1,a2,…ai-1,ai,ai+1…an)中刪除第i個數(shù)據(jù)元素，通常還需將第i+1個至第n個元素向前推動一個位置，即(a1,a2,…，ai-1,ai+1，…，an)，其算法描述如下:PROCDELETE(VARA,VARn,I)If(i<1)Or(i>n)Then

ERROR('位置不存在！') ELSEFORj=iTOn-1A(j)=A(j+1)Nextjn=n-1EndifEnd在順序表中插入或刪除元素時，每進(jìn)行一次插入或刪除，都要移動近乎一半的元素。對于長度可變的線性表，必須按可能達(dá)到的最大長度分配空間順序表的不足：算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第20頁。2．鏈表(1）單鏈表(線性鏈表):鏈?zhǔn)酱鎯Φ木€性表結(jié)點除信息域外還含有一個指針域，用來指出其后繼結(jié)點的位置最后一個結(jié)點沒有后繼結(jié)點，指針?biāo)闹羔樣驗榭?記為NIL或∧)。另外還需要設(shè)置一個指針head，指向單鏈表的第一個結(jié)點算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第21頁。鏈表的一個重要特點是插入、刪除運算靈活方便，不需移動結(jié)點，只要改變結(jié)點中指針域的值即可插入刪除算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第22頁。(2）循環(huán)鏈表：循環(huán)鏈表和單鏈表的差別僅在于鏈表中最后一個結(jié)點的指針域不為“NIL”，而是指向頭一個結(jié)點，成為一個由鏈指針鏈結(jié)的環(huán)(3）雙向鏈表：設(shè)有一個指向后繼結(jié)點的指針和一個指向前驅(qū)結(jié)點的指針?biāo)惴ê蛿?shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第23頁。3．棧棧(STACK)也是一種特殊的線性表，是一種“后進(jìn)先出”的結(jié)構(gòu)，它的運算規(guī)則受到一些約束和限定，故又稱限定性數(shù)據(jù)結(jié)構(gòu)(1）棧的結(jié)構(gòu)特點棧是限定僅在表尾進(jìn)行插入和刪除運算的線性表，表尾稱為棧頂(top)，表頭稱為棧底(bottom)棧的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)(2）棧的運算設(shè)置一個空棧判定棧是否為空進(jìn)棧、退棧讀取棧頂元素等算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第24頁。4．隊列(1）隊列的結(jié)構(gòu)特點隊列(Queue)是限定所有的插入只能在表的一端進(jìn)行，而所有的刪除都在表的另一端進(jìn)行的線性表表中允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊頭(Front)隊列的操作是按先進(jìn)先出的原則進(jìn)行的隊列的物理存儲可以用順序存儲結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)。算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第25頁。(2）隊列的運算：設(shè)置一個空隊列；判定隊列是否是空隊列；入隊列；出隊列；讀取隊頭元素等如果隊列的容量無法預(yù)先估計時，可以采用鏈表存儲結(jié)構(gòu)循環(huán)隊列的插入、刪除算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第26頁。3.2.3串串(String)可以看作一維字符數(shù)組，但其長度不恒定，可以作刪除、插入操作許多高級語言把串作為一種單獨的類型，其元素不可作四則運算進(jìn)行連接、刪除、插入操作，用子串有時很方便子串(Substring)是串的一部分，具有串的一切特征算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第27頁。3.2.4樹和二叉樹

1.樹和二叉樹的定義和術(shù)語樹的邏輯結(jié)構(gòu)樹的形式化定義：樹(Tree)是由一個或多個結(jié)點組成的有限集合T，其中有一個特定的稱為根的結(jié)點；其余結(jié)點可分為m(m≥0)個互不相交的有限集T1,T2,T3,…,Tm，每一個集合本身又是一棵樹，且稱為根的子樹用表來表示樹：(A(B(E,F),C(G),D(H,I,J)))結(jié)點子樹個數(shù)為結(jié)點的度,結(jié)點度的最大值為該樹的度結(jié)點B的度為2，樹的度為3算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第28頁。0棵或多棵不相交的樹的集合稱為樹林二叉樹是另一種重要的樹形結(jié)構(gòu)，其結(jié)構(gòu)定義為：二叉樹(BinaryTree)是n(n≥0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為根的左子樹和右子樹的、互不相交的二叉樹組成二叉樹的邏輯結(jié)構(gòu)：二叉樹的結(jié)點的子樹要區(qū)分左子樹和右子樹，即使在結(jié)點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第29頁。2.樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)可以采用具有多個指針域的多重鏈表，結(jié)點中指針域的個數(shù)應(yīng)由樹的度來決定但在實際應(yīng)用中，這種存儲結(jié)構(gòu)并不方便，一般將樹轉(zhuǎn)化為二叉樹表示，進(jìn)行處理算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第30頁。3.二叉樹的存儲結(jié)構(gòu)可使用具有2個指針域的鏈表，LC為左指針域，指向結(jié)點的左子樹，RC為右指針域，指向結(jié)點的右子樹。亦可用數(shù)組的下標(biāo)來模擬指針，即開辟三個一維數(shù)組DATA，LC和RC分別存放結(jié)點的元素及其左、右指針?biāo)惴ê蛿?shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第31頁。4.樹的二叉樹表示每一棵都能唯一地轉(zhuǎn)換到它所對應(yīng)的二叉樹轉(zhuǎn)換方法：凡是兄弟就用線連接起來，對每個非終端結(jié)點，除其最左孩子外，刪去該結(jié)點與其他孩子結(jié)點的連線，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)450算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第32頁。5.樹和二叉樹的遍歷(周游)樹的遍歷根據(jù)樹的遞歸定義，有兩種遍歷樹的方法：(1)先根(次序)遍歷：若樹中只有一個根結(jié)點，則訪問樹的根結(jié)點；否則，首先訪問樹的根結(jié)點，然后依次先根遍歷每棵子樹。(2)后根(次序)遍歷：若樹中只有一個根結(jié)點，則訪問樹的根結(jié)點；否則，首先依次后根遍歷每一棵子樹，然后訪問樹的根結(jié)點。算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第33頁。二叉樹的遍歷(3)后序遍歷二叉樹的算法為：若二叉樹不空，則：

a)后序遍歷左子樹；

b)后序遍歷右子樹；

c)訪問根結(jié)點。前圖用后序遍歷為：FEGJIHDCBA(1)前序遍歷二叉樹算法為：若二叉樹不空，則：

a)訪問根結(jié)點；

b)前序遍歷左子樹；

c)前序遍歷右子樹。前圖用前序遍歷為ABEFCGDHIJ(2)中序遍歷二叉樹的算法為：

若二叉樹不空，則作：

a)中序遍歷左子樹；

b)訪問根結(jié)點；

c)中序遍歷右子樹。前圖用中序遍歷為：EFBGCHIJDA算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第34頁。3.2.5圖

1.圖的概念和術(shù)語常用G=(V,E)代表一個圖，V是結(jié)點的有窮集合(非空)，E是邊的有窮集合(E可為空集)。若一條邊的結(jié)點對無序，則稱無向圖。(V1,V2)和(V2,V1)相同有向圖由頂點的非空有限集和邊的有限集組成。(V1,V2)和(V2,V1)表示不同邊n個頂點的無向圖邊的最大數(shù)目是n(n-1)/2。n個頂點的有向圖邊的最大數(shù)目為n2（雙環(huán)且自環(huán)）。若(V1,V2)∈E，則稱V1和V2是相鄰結(jié)點。邊(V1,V2)是V1和V2相關(guān)聯(lián)的邊。一個結(jié)點的度是與該結(jié)點相關(guān)聯(lián)的邊的數(shù)目。對于有向圖，則把以結(jié)點Vi為終點的邊的數(shù)目稱結(jié)點Vi的入度；把以Vi為始點的邊的數(shù)目稱為Vi的出度。出度為0的結(jié)點稱為終端結(jié)點。算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第35頁。2.圖的存儲

(1)圖的相鄰矩陣表示法若G是一個具有n個結(jié)點的圖，則G的相鄰矩陣是:(2)圖的鄰接表表示法用鄰接表法表示有向圖，根據(jù)需要可以保存每個結(jié)點的出邊表，也可以保存每個結(jié)點的入邊表算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第36頁。3.圖的遍歷

(1)深度優(yōu)先遍歷基本思想是：從圖中某個V出發(fā)，訪問此結(jié)點，再依次訪問所有與V有路徑的結(jié)點。完成后再另選圖中一個未被訪問的結(jié)點作始點，重復(fù)上述過程，直至圖中所有結(jié)點都被訪問到為止。(2)廣度優(yōu)先遍歷基本思想是：從某個結(jié)點V出發(fā)，訪問此結(jié)點，再依次訪問V鄰接的未訪問結(jié)點。再從這些結(jié)點出發(fā)進(jìn)行廣度優(yōu)先遍歷，直至圖中所有被訪問過的結(jié)點的相鄰結(jié)點都被訪問到。完成后另選圖中一個未曾訪問的結(jié)點作始點，重復(fù)上述過程，直至圖中所有結(jié)點都被訪問到為止算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第37頁。3.3查找3.3.1基本概念關(guān)鍵字是數(shù)據(jù)元素中可以唯一標(biāo)識一個數(shù)據(jù)元素的數(shù)據(jù)項，比如學(xué)號、身份證號等，查找是根據(jù)給定的關(guān)鍵值，在一組數(shù)據(jù)中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素的過程確切定義：給定一個值K，在含有n個記錄的文件中進(jìn)行搜索，尋找一個其關(guān)鍵字等于給定的K值的記錄，如找到，則輸出記錄或記錄在文件中的相對位置稱查找成功；否則輸出查找不成功的信息稱查找失敗。算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第38頁。

3.3.2查找算法

1.順序查找順序查找的方法是：用待查關(guān)鍵字值與線性表中各結(jié)點的關(guān)鍵字值逐個比較，直到找出相等的關(guān)鍵字值;或找遍所有結(jié)點都找不到,即查找失敗順序查找的優(yōu)點是對線性表結(jié)點的邏輯次序無要求,對線性表的存儲結(jié)構(gòu)無要求,缺點是平均檢索長度長,為n/22.二分法查找要求線性表結(jié)點按關(guān)鍵字碼值排好，且以順序方式存儲用要查找的碼值X與中間位置結(jié)點的關(guān)鍵碼值W相比較：(1)X=W，此時已經(jīng)查找成功，查找結(jié)束。(2)X>W,表明X在表的后半部分,取后半部分進(jìn)行查找(3)X<W,表明X在表的前半部分，取前半部分進(jìn)行查找二分法查找的優(yōu)點是平均檢索長度小，為log2n算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第39頁。3.分塊查找要求文件中記錄關(guān)鍵字“分塊有序”,即前一塊中最大關(guān)鍵字小于后一塊中最小關(guān)鍵字,而塊內(nèi)的關(guān)鍵字不一定有序分塊查找的基本思想：先抽取各塊中的最大關(guān)鍵字構(gòu)成一個索引表，由于文件中的記錄按關(guān)鍵字分塊有序，則索引表呈遞增有序狀態(tài)。查找分兩步進(jìn)行:第一步先對索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊，第二步在已限定的那一塊中進(jìn)行順序查找用分塊查找的文件不一定分成大小相等的若干塊，塊大小及其分法可根據(jù)文件的特征來定。分塊查找不僅適用于順序方式存儲的順序表，也適用于線性鏈表方式存儲的文件算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第40頁。3.4排序

3.4.1基本概念設(shè)含有n個記錄的文件｛R1，R2，…Rn｝,其相應(yīng)的關(guān)鍵字為｛K1，K2，…Kn｝,需確定一種排列P(1),P(2)…P(n)使其相應(yīng)的關(guān)鍵字滿足遞增(或遞減)關(guān)系：

KP(1)≤KP(2)≤…KP(n)

或KP(1)≥KP(2)≥…KP(n)使上述文件成為一個按其關(guān)鍵字線性有序的文件｛RP(1)，RP(2)，…RP(n)｝，這種運算就稱為排序內(nèi)排序指當(dāng)文件的數(shù)據(jù)量不太大時，全部信息放在內(nèi)存中處理的排序方法。當(dāng)文件的數(shù)據(jù)量較大時，排序過程中需要在內(nèi)、外存之間不斷地進(jìn)行數(shù)據(jù)交換才能達(dá)到排序的目的，這種排序稱為外排序算法和數(shù)據(jù)結(jié)構(gòu)全文共46頁，當(dāng)前為第41頁。3.4.2插入排序基本思想是：每步將一個待排序的記錄，按關(guān)鍵碼值的大小插入到前面已排序的適當(dāng)位置上，直到全部插完止1.直接插入排序：在排