數(shù)據(jù)結(jié)構(gòu)與算法 課件 第7、8章 內(nèi)部排序、查找

全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第七章內(nèi)部排序?qū)W習(xí)目標(biāo)理解排序的基本概念。掌握各種排序方法及其特點(diǎn)。掌握各種排序算法的實(shí)現(xiàn)過程，能夠?qū)ζ溥M(jìn)行復(fù)雜度分析。能夠?qū)Ω鞣N排序方法進(jìn)行比較，理解各排序方法的使用條件。本章主要內(nèi)容排序的基本概念12交換排序3插入排序選擇排序4歸并排序56排序算法的比較7分配排序第一節(jié)

排序的基本概念定義7.1給定一組記錄r1,r2,…,rn，其關(guān)鍵字分別為 k1,k2,…,kn

將這些記錄排成順序?yàn)閞s1,rs2,…,rsn的一個(gè)序列S，滿足條件 ks1≤ks2≤…≤ksn

或是ks1≥ks2≥…≥ksn

此過程稱為排序若關(guān)鍵字值依從小到大的順序排列，則稱為升序若依從大到小的順序排列，則稱為降序內(nèi)部排序?qū)Σ煌愋偷年P(guān)鍵字而言，“大”、“小”的含義可能不一樣對(duì)于數(shù)值型的關(guān)鍵字，可按一般意義的“大”、“小”來(lái)理解對(duì)于字符型的關(guān)鍵字，往往按其對(duì)應(yīng)的ASCII碼來(lái)定義大小次序把能唯一標(biāo)識(shí)記錄的關(guān)鍵字稱為主關(guān)鍵字，其余的稱為次關(guān)鍵字主關(guān)鍵字值不允許有重復(fù)計(jì)算機(jī)中存放待排序數(shù)據(jù)的存儲(chǔ)介質(zhì)可以分為內(nèi)存和外存當(dāng)待排序的數(shù)據(jù)量不大，全部數(shù)據(jù)都可以放入內(nèi)存，排序操作也完全在內(nèi)存中進(jìn)行時(shí)，相應(yīng)的排序稱為內(nèi)部排序或內(nèi)排序內(nèi)排序因?yàn)椴簧婕皟?nèi)外存數(shù)據(jù)交換的問題所以一般來(lái)講，排序速度較快當(dāng)待排序的數(shù)據(jù)量大，全部數(shù)據(jù)不能同時(shí)放在內(nèi)存中，需要借助外存完成排序過程時(shí)，相應(yīng)的排序稱為外部排序或外排序外排序中，排序的具體操作在內(nèi)存完成，且僅能對(duì)部分?jǐn)?shù)據(jù)進(jìn)行排序過程中需要多次分批在內(nèi)存、外存之間進(jìn)行數(shù)據(jù)交換，從而完成全部數(shù)據(jù)的排序任務(wù)減少數(shù)據(jù)內(nèi)外存交換次數(shù)定義7.2具有相等關(guān)鍵字的兩個(gè)記錄R1和R2，在排序之前，R1位于R2之前，在排序之后，R1仍然位于R2之前，即排序并沒有改變具有相等關(guān)鍵字的兩個(gè)記錄的相對(duì)次序，這樣的排序方法稱為穩(wěn)定的（stable）如果排序方法不能保證具有相等關(guān)鍵字值的兩個(gè)記錄的相對(duì)次序在排序前后不被改變，則稱排序方法是不穩(wěn)定的當(dāng)兩個(gè)記錄中關(guān)鍵字的大小次序與記錄相對(duì)次序不一致時(shí)，稱兩個(gè)記錄是逆序的（inversion）實(shí)際上，排序就是不斷地調(diào)整逆序數(shù)據(jù)對(duì)的過程類型定義#definemaxSize30 //最大記錄數(shù)typedefintELEMType; //元素類型typedefstruct{

ELEMTypedata[maxSize]; //數(shù)組 intcurrentNum; //元素個(gè)數(shù)}myRcd;第二節(jié)插入排序——直接插入排序參與排序的n個(gè)數(shù)據(jù)均保存在數(shù)組A中A的前面（S部分）是已有序的子序列，后面是待排序的部分（U部分）初始時(shí)S部分中僅含有一個(gè)元素e，U部分中含有除e外的其他n-1個(gè)元素每進(jìn)行一趟排序，S部分增加一個(gè)元素，相應(yīng)地U部分減少一個(gè)元素n-1趟排序后，S部分中包含全部的n個(gè)元素，而U部分變?yōu)榭?。排序結(jié)束直接插入排序i=1:4268351702579596365i=2:4268351702579596365i=3:3542681702579596365i=4:1354268702579596365i=5:1354268702579596365i=6:1253542687079596365i=7:1253542687079596365i=8:1253542596870796365i=9:1253542596368707965結(jié)果:1253542596365687079算法實(shí)現(xiàn)之一算法實(shí)現(xiàn)之二效率直接插入排序除原來(lái)的數(shù)據(jù)所占用的數(shù)組空間外，還需要一個(gè)臨時(shí)工作單元，所以它的空間復(fù)雜度為O(1)最優(yōu)時(shí)，總的交換次數(shù)為0，總的比較次數(shù)為n-1最差時(shí)，總的交換次數(shù)為n(n-1)/2，總的比較次數(shù)為n(n-1)/2平均時(shí)，為最差情況的一半左右希爾排序希爾排序（shell’smethod）又稱縮小增量排序（diminishingincrementsort），它是插入排序的一種改進(jìn)利用的是數(shù)據(jù)基本有序時(shí)，或是數(shù)據(jù)個(gè)數(shù)較少時(shí)，直接插入排序的高效性需要解決兩個(gè)問題如何劃分段如何合并段劃分段及合并段劃分?jǐn)?shù)據(jù)段時(shí)是按照一定的間隔數(shù)進(jìn)行的，將相距等間隔數(shù)的元素放在同一個(gè)數(shù)據(jù)段內(nèi)間隔數(shù)為3時(shí)所有下標(biāo)等于3i(i≥0)的元素都分在第一個(gè)數(shù)據(jù)段中所有下標(biāo)等于3i+1(i≥0)的元素分在第二個(gè)數(shù)據(jù)段中所有下標(biāo)等于3i+2(i≥0)的元素分在第三個(gè)數(shù)據(jù)段中一般地，間隔數(shù)為k時(shí)，全部數(shù)據(jù)會(huì)分成k個(gè)數(shù)據(jù)段合并的過程易如反掌希爾排序的過程首次劃分?jǐn)?shù)據(jù)段每一個(gè)數(shù)據(jù)段看成是一個(gè)組，在組內(nèi)進(jìn)行直接插入排序依同樣的機(jī)制，將全部數(shù)據(jù)劃分為更長(zhǎng)的數(shù)據(jù)段，數(shù)據(jù)段內(nèi)的數(shù)據(jù)個(gè)數(shù)增多，段數(shù)減少每組內(nèi)依次進(jìn)行直接插入排序最后一趟排序的k值為1，也就是全部元素都在同一個(gè)組內(nèi)，對(duì)所有元素進(jìn)行直接插入排序增量序列di的取法取d0=m，di+1=

di/2

取d0=m，di+1=

(di+1)/2

取d0=m，di+1=

(di-1)/3

取d0=m，di+1=

(di-1)/2

希爾排序42,68,35,1,70,25,79,59,63,65,26,80,17,36增量為5黑色字是原始數(shù)據(jù)，紅色字是組內(nèi)排序后的數(shù)據(jù)結(jié)果：25,68,17,1,65,26,79,35,36,70,42,80,59,63d=54225

2526

2642

第一組

6868

7979

8080

第二組

3517

5935

1759

第三組

11

6336

3663第四組

7065

6570

第五組25,68,17,1,65,26,79,35,36,70,42,80,59,63增量為3結(jié)果：1,35,17,25,42,26,59,63,36,70,65,80,79,68d=3251

125

7959

7070

5979

第一組

6835

6542

3563

4265

6368第二組

1717

2626

3636

8080

第三組最后一趟使用增量1，數(shù)據(jù)均在同一組內(nèi)。這是第三趟排序結(jié)果：1,17,25,26,35,36,42,59,63,65,68,70,79,80用希爾排序方法對(duì)一個(gè)數(shù)據(jù)序列進(jìn)行排序時(shí)，若第1趟排序結(jié)果為 9,1,4,13,7,8,20,23,15則該趟排序采用的增量（間隔）可能是A．2 B．3 C．4 D．5答案：B排序中用到的增量序列的取法實(shí)際上很有講究如果增量序列取2的冪次，雖然計(jì)算增量時(shí)簡(jiǎn)單，但在前一趟掃描中互相比較過的兩個(gè)關(guān)鍵字，在后一趟掃描中還會(huì)遇到，從而又比較一次，顯然這些比較操作是多余的一般地，增量之間最好不是倍數(shù)關(guān)系希爾排序算法修改直接插入排序算法之一修改直接插入排序算法之二第三節(jié)交換排序——起泡排序參與排序的n個(gè)數(shù)據(jù)均保存在數(shù)組A中，起泡排序算法的一般策略是：掃描整個(gè)數(shù)組，依次比較相鄰的兩個(gè)元素，如果它們是逆序的，就交換它們，然后再去查看后面的相鄰元素。持續(xù)地進(jìn)行這個(gè)過程，直到所有元素都有序時(shí)為止每趟選最大值42,68,35,1,70,25,79,59,63,65i=1:4235168257059636579i=2:3514225685963657079i=3:1352542596365687079i=4:1253542596365687079i=5:1253542596365687079i=6:1253542596365687079i=7:1253542596365687079i=8:1253542596365687079i=9:1253542596365687079起泡排序算法選取并調(diào)整本趟最大值的起泡排序的算法每趟選最小值42,68,35,1,70,25,79,59,63,65i=1:1426835257059796365i=2:1254268355970637965i=3:1253542685963706579i=4:1253542596863657079i=5:1253542596368657079i=6:1253542596365687079i=7:1253542596365687079i=8:1253542596365687079i=9:1253542596365687079起泡排序算法選取并調(diào)整本趟最小值的起泡排序的算法若用起泡排序方法對(duì)序列10,14,26,29,41,52進(jìn)行降序排序，則需進(jìn)行比較操作的次數(shù)是（

）A．3 B．10 C．15 D．25答案：C。修改算法方法一：使用一個(gè)變量來(lái)記錄一趟掃描中是否有數(shù)據(jù)交換。當(dāng)發(fā)現(xiàn)沒有數(shù)據(jù)交換時(shí)，起泡排序可以立即結(jié)束方法二：設(shè)置一個(gè)變量flag，用它來(lái)標(biāo)識(shí)一趟排序過程中是否有記錄交換在每趟排序之前，flag的值為0，每次交換記錄后，flag的值修改為1每趟排序之后，判別flag的值，若為1，則繼續(xù)下一趟排序；若為0則表明該趟沒有交換任何記錄，意味著再?zèng)]有逆序的記錄存在，排序結(jié)束42,68,35,1,70,25,79,59,63,65 right=9

i=1:4235168257059636579 right=8i=2:3514225685963657079 right=7i=3:1352542596365687079 right=6i=4:1253542596365687079 right=1i=5:1253542596365687079

改進(jìn)后的起泡排序算法效率起泡排序算法中，數(shù)據(jù)比較的次數(shù)是確定的第一趟要比較n-1次，第二趟要比較n-2次，第i趟要比較n-i次，總的比較次數(shù)為次。起泡排序最優(yōu)、最差及平均情況下的比較次數(shù)是相同的，均為O(n2)最差情況下，交換次數(shù)亦為O(n2)次最優(yōu)情況下，不發(fā)生交換平均情況下，記錄交換的次數(shù)約為最差情況下交換次數(shù)的一半改進(jìn)后起泡排序，其最優(yōu)時(shí)間復(fù)雜度為O(n)快速排序快速排序算法是將一個(gè)含多數(shù)據(jù)的大數(shù)據(jù)段的排序問題，分解為兩個(gè)或一個(gè)含更少數(shù)據(jù)的小數(shù)據(jù)段的排序問題，小的數(shù)據(jù)段又繼續(xù)分解為更小的數(shù)據(jù)段，分解過程依此類推，這樣的分解過程稱為劃分每次劃分，都會(huì)得到比原來(lái)的數(shù)據(jù)段更小的數(shù)據(jù)段經(jīng)過多次劃分后，總會(huì)得到只含一個(gè)數(shù)據(jù)的數(shù)據(jù)段，而這樣的數(shù)據(jù)段自然有序再將這些有序的小數(shù)據(jù)段組合起來(lái)成為有序的大數(shù)據(jù)段，從而得到初始數(shù)據(jù)的排序結(jié)果快速排序中，需要解決兩個(gè)主要問題如何將一個(gè)大數(shù)據(jù)段劃分為小數(shù)據(jù)段有序的小數(shù)據(jù)段如何組合為大的數(shù)據(jù)段，并保證大數(shù)據(jù)段仍是有序的從初始數(shù)據(jù)中選擇一個(gè)元素，用它作為基準(zhǔn)元素，稱為樞軸（pivot）將初始數(shù)據(jù)中所有小于樞軸的數(shù)據(jù)分在一個(gè)組內(nèi)，設(shè)為組1將所有大于樞軸的數(shù)據(jù)分在另一個(gè)組內(nèi)，設(shè)為組2這就是快速排序劃分?jǐn)?shù)據(jù)段的機(jī)制組1中的所有數(shù)據(jù)全部都小于組2中的所有數(shù)據(jù)，這個(gè)性質(zhì)稱為整體有序初始：4268351702579596365選擇第一個(gè)元素做樞軸并將樞軸放到最后的位置pivot:426568351702579596342

↑

↑leftright尋找數(shù)據(jù)對(duì)6568351702579596342

↑

↑leftright進(jìn)行交換

得到2568351706579596342

↑

↑leftright尋找數(shù)據(jù)對(duì)2568351706579596342

↑

↑leftright交換2513568706579596342

↑

↑leftright放回樞軸2513542706579596368

↑

↑rightleft得到的結(jié)果具有如下的性質(zhì)樞軸42在最終的位置上樞軸前面的元素均小于樞軸樞軸后面的元素均大于樞軸算法劃分算法快速排序算法另一種劃分方法4268351702579596365pivot=42()68351702579596365

↑

↑leftright找到小于42的元素()68351702579596365（從右向左）

↑

↑leftright填空并產(chǎn)生新的空256835170()79596365

↑

↑leftright找到大于42的元素256835170()79596365（從左向向）

↑

↑leftright填空并產(chǎn)生新的空25()351706879596365

↑

↑leftright找到小于42的元素25()351706879596365（從右向左）

↑

↑leftright填空并產(chǎn)生新的空25135()706879596365

↑

↑leftright找到大于42的元素25135()706879596365（從左向右）

↑

↑rightleft因?yàn)閘eft與right已經(jīng)交錯(cuò)，所以這次使用樞軸來(lái)填空使用樞軸填空2513542706879596365

↑

↑rightleft另一種劃分算法效率如果每次都能把數(shù)組劃分成元素個(gè)數(shù)大致相等的兩個(gè)子段，則快速排序能達(dá)到最優(yōu)情況?？偟臅r(shí)間代價(jià)為O(nlogn)與之相對(duì)的是每次劃分不平衡，一個(gè)子段極大（含n-1個(gè)元素），另一個(gè)子段極?。ê?個(gè)元素）。這樣的情況是快速排序的最差情況。總的時(shí)間代價(jià)為O(n2)平均情況介于最優(yōu)與最差之間，在理想狀態(tài)下，時(shí)間代價(jià)為O(nlogn)導(dǎo)致快速排序效率不高的主要原因是劃分時(shí)選擇的樞軸不好在最左位置元素、中間位置元素及最右位置元素中選擇中間值作為樞軸，劃分后，兩個(gè)部分都不會(huì)為空，每個(gè)部分中最少含有一個(gè)元素。樞軸的這種選擇方法稱為三元取中方法排序當(dāng)n值很小時(shí)，它的優(yōu)越性并不突出使用直接插入排序來(lái)替代快速排序快速排序需要一個(gè)棧作為輔助空間，故最壞情況下空間復(fù)雜度為O(n)第四節(jié)選擇排序選擇排序（selectionsort）算法重復(fù)地選擇特定值放到其最終位置，從而完成一組值的排序。即對(duì)于數(shù)組中的每個(gè)位置，算法選出應(yīng)該處在那個(gè)位置的值，并將它一次性地放置到位簡(jiǎn)單選擇排序堆排序簡(jiǎn)單選擇排序第一趟掃描時(shí)從全部n個(gè)元素中找到最小值放到數(shù)組的第一個(gè)位置第二趟掃描時(shí)從剩余的n-1個(gè)元素中找到最小值放到數(shù)組的第二個(gè)位置一般地，第k趟掃描時(shí)從n-k+1個(gè)元素中找到最小值放到數(shù)組的第k個(gè)位置。直到只剩余一個(gè)元素時(shí)，不需要再做任何處理，排序過程結(jié)束簡(jiǎn)單選擇排序示例初始：42683526702579596365i=1:25683526704279596365i=2:25263568704279596365i=3:25263568704279596365i=4:25263542706879596365i=5:25263542596879706365i=6:25263542596379706865i=7:25263542596365706879i=8:25263542596365687079i=9:25263542596365687079堆排序

最小堆和最大堆例7-11設(shè)有數(shù)據(jù)序列：44,97,76,29,13,7,50,9,20，將它們建成最大堆，畫出最后得到的堆的結(jié)果。例7-12初始最大堆，輸出堆頂97，給出調(diào)整后的新堆堆排序堆排序示例46,20,17,40,52，使用堆排序?qū)ζ溥M(jìn)行降序排序示例下列關(guān)鍵字序列能構(gòu)成一個(gè)堆的是A．90,31,53,23,16,48B．90,48,31,53,16,23C．16,53,23,90,31,48D．16,31,23,90,53,48答案：A和D已知小根堆為8,15,10,21,34,16,12，刪除關(guān)鍵字8并放置到數(shù)組的最后位置，之后進(jìn)行整堆，在此過程中，關(guān)鍵字之間的比較次數(shù)是A．1 B．2 C．3 D．4答案：C第五節(jié)歸并排序所謂歸并（merge）是指將若干個(gè)有序序列合并為一個(gè)有序序列的操作，也稱為合并若參與合并的序列的個(gè)數(shù)為2，則稱為二路歸并借助于歸并操作完成的排序就是歸并排序（mergingsort）歸并排序采用的是二路歸并操作兩個(gè)有序序列的合并操作數(shù)據(jù)元素分別是a1,a2,…,am和b1,b2,…,bn使用兩個(gè)變量i和j分別指示兩個(gè)序列當(dāng)前元素的下標(biāo)，初始時(shí)均指向各自的第一個(gè)元素，即i=0，j=m使用數(shù)組B保存合并后的數(shù)據(jù)，使用變量k表示對(duì)應(yīng)的下標(biāo)，初始時(shí)為0歸并的過程比較A[i]和A[j]，若A[i]<A[j]，則B[k]=A[i]，然后i和k均加1。否則，B[k]=A[j]，然后j和k均加1。持續(xù)這個(gè)過程，直到i=m或j=m+n時(shí)數(shù)組A中依次保存了兩個(gè)有序序列：13,22,41,53和1,5,30,46，將它們歸并為一個(gè)有序序列，結(jié)果保存到數(shù)組B中此時(shí)第二個(gè)序列已空，將第一個(gè)序列的剩余元素全部復(fù)制到B中兩個(gè)有序段相鄰保存在myarr中，第一個(gè)有序段保存在下標(biāo)從l到m的地方，第二個(gè)有序段保存在下標(biāo)從m+1到n的地方。歸并后的有序段保存在tmplist中，下標(biāo)從k開始?xì)w并操作歸并排序非遞歸實(shí)現(xiàn)的歸并排序設(shè)待排序序列中含有n個(gè)記錄，初始時(shí)將它們看成是n個(gè)長(zhǎng)度為1有序段然后兩兩歸并。得到的有序子序列的個(gè)數(shù)是

n/2

再把得到的這些有序子序列兩兩歸并，得到

n/2

/2

個(gè)有序子序列。如果n不是4的倍數(shù)，則最后一個(gè)子序列的長(zhǎng)度小于4繼續(xù)這個(gè)過程，直到得到一個(gè)長(zhǎng)度為n的有序序列時(shí)為止非遞歸歸并排序示例42,68,35,1,70,25,79,59,63,65，使用非遞歸方式，進(jìn)行二路歸并排序共進(jìn)行4趟二路歸并的遞歸過程35,70,79,25,59,63,65，使用遞歸法，進(jìn)行二路歸并排序遞歸算法第六節(jié)分配排序盒子排序 23,98,10,19,28,3,53,29,20,94可以使用一個(gè)有100個(gè)元素的整數(shù)數(shù)組A來(lái)完成排序，初始時(shí)數(shù)組元素均為0從左至右掃描待排序數(shù)據(jù)，若數(shù)據(jù)為k，則令A(yù)[k]=1掃描完畢，使用for循環(huán)語(yǔ)句處理A中的每個(gè)元素，若元素值為1，則輸出其下標(biāo)值得到原初始數(shù)據(jù)的排序結(jié)果基數(shù)排序基數(shù)排序是一種分配排序，排序過程就是反復(fù)進(jìn)行“分配”和“收集”的過程在基數(shù)排序中，關(guān)鍵字被拆分為若干個(gè)子關(guān)鍵字，排序過程中需要分別對(duì)每個(gè)子關(guān)鍵字進(jìn)行分配和收集操作示例設(shè)有如下關(guān)鍵字序列 27,91,1,97,17,23,84,28,72,4,67,25給出基數(shù)排序過程一趟分配的結(jié)果第一趟收集的結(jié)果是：91,1,72,23,84,4,25,27,97,17,67,28二趟分配的結(jié)果第二趟收集的結(jié)果是：1,4,17,23,25,27,28,67,72,84,91,97算法實(shí)現(xiàn)以例7-20中第一趟排序?yàn)槔谝惶伺判蚴轻槍?duì)數(shù)據(jù)的個(gè)位進(jìn)行的，統(tǒng)計(jì)每個(gè)數(shù)的個(gè)位數(shù)，并記錄到count中，獲取個(gè)位數(shù)的方法是：myarr->data[j]%10

0123456789count0211210410對(duì)count數(shù)組進(jìn)行進(jìn)一步的處理，從下標(biāo)1開始，將前一個(gè)元素中的值加到本元素，即count[j]=count[j-1]+count[j]，可以得到各個(gè)盒子在mybrr中的下標(biāo)范圍

0123456789count0234677111212第j（j≥1）個(gè)盒子在mybrr中的下標(biāo)從count[j-1]到count[j]-1之間，比如，個(gè)位數(shù)為1的兩個(gè)數(shù)據(jù)（91和1），將保存在mybrr[0]到mybrr[1]中。第0個(gè)盒子在mybrr中的下標(biāo)從0開始程序示例對(duì)給定的關(guān)鍵字序列 110,119,007,911,114,120,122進(jìn)行基數(shù)排序，則第2趟分配收集后得到的關(guān)鍵字序列是A．007110119114911120122B．007110119114911122120C．007110911114119120122D．110120911122114007119答案：C第七節(jié)有關(guān)內(nèi)部排序算法的比較排序方法最優(yōu)時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度最差時(shí)間復(fù)雜度穩(wěn)定性直接插入排序O(n)O(n2)O(n2)穩(wěn)定起泡排序O(n2)O(n2)O(n2)穩(wěn)定簡(jiǎn)單選擇排序O(n2)O(n2)O(n2)不穩(wěn)定希爾排序O(n3/2)

不穩(wěn)定快速排序O(nlogn)O(nlogn)O(n2)不穩(wěn)定歸并排序O(nlogn)O(nlogn)O(nlogn)穩(wěn)定堆排序O(nlogn)O(nlogn)O(nlogn)不穩(wěn)定基數(shù)排序O(dn)O(dn)O(dn)穩(wěn)定ThankYou!全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第八章查找學(xué)習(xí)目標(biāo)理解查找的基本概念掌握順序查找、折半查找、索引順序查找方法的基本思想及實(shí)現(xiàn)過程，理解各種查找方法的適用條件理解二叉查找樹的概念，掌握二叉查找樹操作的定義及實(shí)現(xiàn)理解AVL樹的基本概念，掌握AVL樹基本操作的定義及實(shí)現(xiàn)理解B樹的概念，掌握插入及查找操作的定義及實(shí)現(xiàn)過程理解哈希方法中的基本概念，掌握哈希方法能夠?qū)Ω鞑檎曳椒ㄟM(jìn)行比較分析本章主要內(nèi)容查找的基本概念12樹形結(jié)構(gòu)的查找3順序表的查找哈希表及其查找4第一節(jié)查找的基本概念定義8.1設(shè)有一個(gè)集合T，其中有n個(gè)數(shù)據(jù)項(xiàng)，集合T及其中數(shù)據(jù)項(xiàng)的形式如下 T={(k0,I0),(k1,I1),…,(kn-1,In-1)} k0,k1,…,kn-1是互不相同的關(guān)鍵字值

Ij（0≤j≤n-1）是與關(guān)鍵字值kj相關(guān)的信息給定一個(gè)特定的關(guān)鍵字值K，查找問題是在T中確定數(shù)據(jù)項(xiàng)(kj,Ij)，使得kj=K查找表中的數(shù)據(jù)項(xiàng)也稱為記錄每個(gè)記錄至少包含一個(gè)關(guān)鍵字記錄中關(guān)鍵字的類型可以是能夠進(jìn)行比較操作的任意類型第二節(jié)順序表的查找順序查找方法初始時(shí)，將給定的關(guān)鍵字值K與表中第一個(gè)記錄的關(guān)鍵字值相比較，若兩個(gè)值相等則找到目標(biāo)，查找成功；否則將K與表中下一個(gè)記錄的關(guān)鍵字值繼續(xù)比較并判斷是否相等，依此類推。如果直到最后一個(gè)記錄的關(guān)鍵字值與K都不相等，則表明所存儲(chǔ)的數(shù)據(jù)中沒有要查找的目標(biāo)，查找不成功順序表結(jié)構(gòu)順序表保存在一個(gè)數(shù)組中typedefintELEMType;typedefstruct{

ELEMTypeelement[maxSize]; intn; //實(shí)際的元素個(gè)數(shù)}searchList;typedefintposition;順序查找的算法查找的平均查找長(zhǎng)度為(n+1)/2不成功查找的查找次數(shù)為n折半查找方法當(dāng)數(shù)據(jù)按關(guān)鍵字有序存儲(chǔ)時(shí)，可以改進(jìn)順序查找方法折半查找也稱為二分查找，其適用條件是數(shù)組中各個(gè)記錄按關(guān)鍵字有序排列，所以折半查找只適用于有序表折半查找并不從有序表的一端開始查找，而是從中間開始查找給定有序表1115182233456065828697使用折半查找方法查找22，給出查找過程初始時(shí)查找22的過程查找85的過程折半查找的具體算法效率折半查找的平均查找長(zhǎng)度可以用二叉樹進(jìn)行分析折半查找判定樹折半查找的平均查找長(zhǎng)度為logn索引順序查找索引順序查找又稱為分塊查找，是結(jié)合了順序查找和二分查找特點(diǎn)的一種查找方法，適用于數(shù)據(jù)較多的情況將眾多的數(shù)據(jù)分成若干塊，即將大的查找池分為若干小的查找池每塊中的值可以有序，也可以無(wú)序，但塊與塊之間必須有序第1塊中的所有關(guān)鍵字都小于第2塊中的所有關(guān)鍵字第2塊中的所有關(guān)鍵字都小于第3塊中的所有關(guān)鍵字第i塊中的所有關(guān)鍵值都小于第i+1塊中的所有關(guān)鍵值分塊后，將每個(gè)塊中的最大關(guān)鍵字抽取出來(lái)，按塊的次序保存在一個(gè)一維數(shù)組中。這個(gè)一維數(shù)組稱為索引表索引表是個(gè)有序表索引順序查找的基本思想首先查找索引表，確定要查找的關(guān)鍵字可能在哪個(gè)塊中索引表是有序表，所以查找索引表時(shí)可以使用折半查找，當(dāng)然如果索引表較小則也可以使用順序查找然后在確定的塊內(nèi)再進(jìn)行進(jìn)一步的查找在每個(gè)塊內(nèi)，通常使用順序查找。當(dāng)然，如果塊內(nèi)是有序的，也可以使用折半查找第三節(jié)樹形結(jié)構(gòu)的查找利用樹形結(jié)構(gòu)來(lái)存儲(chǔ)記錄這些方法不僅能達(dá)到較高的查找效率，也能較好地解決在查找表中插入和刪除記錄的問題二叉查找樹定義8.2二叉查找樹（binarysearchtree，BST）或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹（1）若它的左子樹不空，則左子樹所有結(jié)點(diǎn)保存的記錄的關(guān)鍵字值均小于它的根結(jié)點(diǎn)保存的記錄的關(guān)鍵字值（2）若它的右子樹不空，則右子樹所有結(jié)點(diǎn)保存的記錄的關(guān)鍵字值均大于它的根結(jié)點(diǎn)保存的記錄的關(guān)鍵字值（3）它的左子樹、右子樹也都是二叉查找樹結(jié)點(diǎn)類及二叉查找樹的定義typedefintELEMType;typedefstruct BNode //二叉查找樹結(jié)點(diǎn){ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right; //指向左孩子、右孩子的指針}BstTNode;typedefBstTNode*BstTree;二叉查找樹的查找從根結(jié)點(diǎn)開始，如果根結(jié)點(diǎn)的關(guān)鍵字等于查找目標(biāo)target，則查找成功如果目標(biāo)target小于根結(jié)點(diǎn)的關(guān)鍵字值，則在它的左子樹繼續(xù)查找如果目標(biāo)target大于根結(jié)點(diǎn)的關(guān)鍵字值，則在它的右子樹繼續(xù)查找依此類推在BST中的查找，是沿著從根到葉結(jié)點(diǎn)的一條路徑向下查找，如果在路徑中某結(jié)點(diǎn)的關(guān)鍵字值與目標(biāo)相等，則查找成功，返回1；若遇到空指針則表示查找失敗，返回0，表示二叉查找樹中不存在查找目標(biāo)target示例在下面的二叉查找樹中，分別查找關(guān)鍵字為82和37二叉查找樹的查找算法采用遞歸程序方式二叉查找樹的查找算法采用迭代實(shí)現(xiàn)方式二叉查找樹的生成二叉查找樹的生成就是從空樹開始依次將結(jié)點(diǎn)插入到樹中的過程若二叉查找樹為空，則新結(jié)點(diǎn)為二叉查找樹的根結(jié)點(diǎn)；若二叉查找樹非空，則比較新結(jié)點(diǎn)的關(guān)鍵字值和根結(jié)點(diǎn)的關(guān)鍵字值，若新結(jié)點(diǎn)關(guān)鍵字小于根結(jié)點(diǎn)關(guān)鍵字，則新結(jié)點(diǎn)插入到根的左子樹中，否則插入到根的右子樹中插入新結(jié)點(diǎn)的算法示例在如下的BST中依次插入關(guān)鍵字58和17示例從空樹開始，依次插入關(guān)鍵字分別為h,a,r,d的結(jié)點(diǎn)，建立一棵二叉查找樹二叉查找樹的刪除假設(shè)要?jiǎng)h除的結(jié)點(diǎn)為x，它的雙親結(jié)點(diǎn)是f，不失一般性，設(shè)x為f的左孩子，分三種情況考慮x的度為0，即x為葉結(jié)點(diǎn)，此種情況最為簡(jiǎn)單，刪除該結(jié)點(diǎn)后，只須令f的左孩子指針為空即可x的度為1，即x只有左子樹LTree或只有右子樹RTree，刪除x結(jié)點(diǎn)后，只須令LTree或RTree直接成為其雙親結(jié)點(diǎn)f的左子樹即可。x的度為2，即x結(jié)點(diǎn)的左、右子樹均不空，這種情況比較復(fù)雜，可采用兩種辦法以x的直接前驅(qū)w來(lái)頂替它，再刪除w以x的直接后繼u來(lái)頂替它，再刪除u刪除示例分別刪除關(guān)鍵字45和60所在的結(jié)點(diǎn)同一組關(guān)鍵字，如果插入次序改變了，則可能會(huì)生成不同的二叉查找樹二叉查找樹的高度不僅決定了查找時(shí)最大的比較次數(shù)，也影響了平均查找長(zhǎng)度一般來(lái)說，對(duì)于n個(gè)記錄，當(dāng)它們的關(guān)鍵字隨機(jī)出現(xiàn)時(shí)，所構(gòu)成的二叉查找樹還是比較均衡的。在這樣的二叉查找樹上進(jìn)行查找，其查找成功的平均查找長(zhǎng)度為O(logn)AVL樹兩位數(shù)學(xué)家Adel’son-Vel’skii和Landis在1962年提出了一種新的樹結(jié)構(gòu)在二叉查找樹的每個(gè)結(jié)點(diǎn)中增加一個(gè)標(biāo)記，稱為平衡因子，定義為該結(jié)點(diǎn)左子樹的高度減去右子樹的高度當(dāng)每個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值不大于1時(shí)，稱二叉查找樹為AVL樹AVL樹是平衡的，有的教材也稱為平衡二叉樹樹定義8-3AVL樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉查找樹：（1）它的左子樹和右子樹都是AVL樹（2）它的左子樹和右子樹的高度之差的絕對(duì)值不大于1若二叉排序樹中所有結(jié)點(diǎn)的平衡因子均介于-1到+1之間時(shí)，稱樹是平衡的，否則稱為失平衡例8-12高度為4的AVL樹中，最少有多少個(gè)結(jié)點(diǎn)？解：有7個(gè)結(jié)點(diǎn)在所有等高的AVL樹中，滿足“除葉結(jié)點(diǎn)外，每個(gè)分支結(jié)點(diǎn)的平衡因子是-1或+1”條件的AVL樹所含的結(jié)點(diǎn)個(gè)數(shù)最少高度為0的AVL樹所含結(jié)點(diǎn)個(gè)數(shù)為0。高度為1的AVL樹僅含有1個(gè)結(jié)點(diǎn)。高度為2的AVL樹，一棵子樹的高度為1，另一棵子樹的高度為0，樹中含有的結(jié)點(diǎn)個(gè)數(shù)=1+0+1=2。依此類推。AVL樹的查找AVL樹是滿足平衡條件的特殊二叉查找樹，AVL樹的查找過程與二叉查找樹的查找過程是一樣的AVL樹的插入從空樹開始，向AVL樹中逐個(gè)插入關(guān)鍵字，生成AVL樹。每插入一個(gè)關(guān)鍵字，都要保證得到的樹是平衡的。將關(guān)鍵字插入AVL樹的過程分以下兩個(gè)步驟：①按照二叉查找樹的插入規(guī)則，將關(guān)鍵字插入到AVL樹中②如果得到的新樹是平衡的，則插入完成，否則進(jìn)行相應(yīng)的旋轉(zhuǎn)以恢復(fù)平衡共有四種旋轉(zhuǎn)稱為RR型如果u插入在v右子結(jié)點(diǎn)的右子樹中（稱為RR型），則進(jìn)行向左的單旋轉(zhuǎn)LL型旋轉(zhuǎn)RL型LR型雙旋轉(zhuǎn)例8-13將下列關(guān)鍵字添加到初始為空的AVL樹中，畫出生成樹的過程

70,80,90,20,10,50,60,40,30B樹定義8.3一棵m階B樹或者為空，或者為滿足下列性質(zhì)的m叉樹樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹；根結(jié)點(diǎn)至少有兩棵子樹；除根結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)至少有

m/2

棵子樹；所有葉結(jié)點(diǎn)都出現(xiàn)在同一層上；所有結(jié)點(diǎn)都包含如下形式的數(shù)據(jù)：

（n,A0,K1,A1,K2,A2,…,Kn,An）其中n為關(guān)鍵字的個(gè)數(shù)Ki(i=1,2,…,n)為關(guān)鍵字，且滿足K1<K2<…<KnAi(i=0,1,…,n)為指向子樹根結(jié)點(diǎn)的指針，且對(duì)于i=1,2,…,n-1Ai所指子樹中全部結(jié)點(diǎn)的關(guān)鍵字均大于Ki而小于Ki+1A0所指子樹中全部結(jié)點(diǎn)的關(guān)鍵字均小于K1An所指子樹中全部結(jié)點(diǎn)的關(guān)鍵字均大于Kn對(duì)于葉結(jié)點(diǎn)，所有指針Ai皆為空。對(duì)于具有n個(gè)關(guān)鍵字的非葉結(jié)點(diǎn)，將有n+1棵子樹一棵3階(m=3)B樹每個(gè)結(jié)點(diǎn)中或者含有一個(gè)關(guān)鍵字，或者含有兩個(gè)關(guān)鍵字B樹的查找類似二叉查找樹中的查找方法在如下的B樹中，分別查找關(guān)鍵字I和MB樹的建立建立B樹的過程，即是從空樹開始逐個(gè)插入關(guān)鍵字的過程給定數(shù)據(jù)序列如下18,15,41,10,45,30,25,3,71,60,50,72依次插入到初始為空的5階B樹中第四節(jié)哈希表及其查找哈希方法使用的存儲(chǔ)結(jié)構(gòu)是數(shù)組，它采用特殊的機(jī)制存放數(shù)據(jù)哈希方法把關(guān)鍵字值映射到數(shù)組中的一個(gè)位置，這通過一個(gè)函數(shù)來(lái)實(shí)現(xiàn)，這個(gè)函數(shù)稱為哈希函數(shù)，通常用H來(lái)表示存放記錄的數(shù)組稱為哈希表，用T來(lái)表示哈希表中的一個(gè)位置也稱為一個(gè)槽從數(shù)據(jù)存放到數(shù)據(jù)訪問的整套機(jī)制稱為哈希方法示例某個(gè)高校參加夏令營(yíng)的學(xué)生全部住在一棟宿舍大樓內(nèi)，該樓的樓層足夠高，樓中每層有足夠多的房間，每個(gè)房間內(nèi)只住一位學(xué)生為了便于管理和查詢，現(xiàn)以學(xué)生的姓名（假設(shè)不超過三個(gè)漢字）為關(guān)鍵字，以姓名的漢字筆劃數(shù)作為關(guān)鍵字的值，來(lái)決定他（她）所住的房間號(hào)，其中姓的筆劃數(shù)決定樓層號(hào)，名字的筆劃數(shù)決定本層的房間號(hào)又有一位名叫卞云的學(xué)生加入夏令營(yíng)，她的姓名編碼是404，可是404號(hào)房間已經(jīng)安排了學(xué)生王方，不能再住第二個(gè)人了。這就帶來(lái)了問題，這種情況稱為發(fā)生了“沖突”學(xué)生姓名房間號(hào)丁

一201于

立305王

方404田小華536劉力文624李中元744┆┆哈希方法需要解決的問題有兩個(gè)選擇什么樣的哈希函數(shù)當(dāng)有沖突發(fā)生時(shí)，如何解決沒有“沖突”的哈希函數(shù)稱為完美哈希函數(shù)哈希函數(shù)的構(gòu)造方法構(gòu)造哈希函數(shù)時(shí)通?？紤]的因素有計(jì)算哈希函數(shù)所需要的時(shí)間關(guān)鍵字的長(zhǎng)度哈希表的大小關(guān)鍵字的分布情況記錄的查找頻率構(gòu)造哈希函數(shù)的基本原則是算法簡(jiǎn)單，運(yùn)算量小均勻分布，減少?zèng)_突直接定址法哈希函數(shù)是關(guān)鍵字值的線性函數(shù)，H(k)=k或H(k)=a

k+b，其中a、b為常數(shù)設(shè)要統(tǒng)計(jì)某地區(qū)從1949年到2000年每年的出生人數(shù)，此時(shí)年份為關(guān)鍵字。H(k)=k-1949即可，其中k為年份數(shù)平方取中法一個(gè)數(shù)自乘后，乘積的中間幾位既能反映原數(shù)低位的情況，也能反映原數(shù)高位的情況關(guān)鍵字機(jī)內(nèi)代碼機(jī)內(nèi)代碼的平方數(shù)哈希地址ABCBCDCDEXYZ┆010203020304030405242526┆01041012090412252416092446402558818860676┆410225446886┆折疊法折疊法是另一類處理多位關(guān)鍵字的方法。當(dāng)關(guān)鍵字的位數(shù)較多，遠(yuǎn)超過哈希表地址的范圍時(shí)，可將關(guān)鍵字分割為位數(shù)相等的幾段，然后將各段疊加，疊加后將最高位的進(jìn)位舍去，所得結(jié)果即為哈希地址關(guān)鍵字值k