《軟件技術(shù)基礎(chǔ)》第三章 查找與排序技術(shù)

第三章

查找與排序技術(shù)軟件技術(shù)基礎(chǔ)》課件制作人：錢玉文第

三

章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算(上)

（有*號的標(biāo)題表示最基本的內(nèi)容）

3.1基本的查找技術(shù)

3.1.1

順序查找

*

3.1.2

有序表的對分查找

3.1.3

分塊查找3.2哈希表技術(shù)

3.2.1

哈希表

3.2.2

哈希查找課件制作人：錢玉文本節(jié)內(nèi)容提要——查找查找

就是在給定的DS中找出滿足某種條件的結(jié)點(diǎn)；若存在這樣的結(jié)點(diǎn)，則查找成功；否則，查找失敗。（找）查找表

是一組待查數(shù)據(jù)元素的集合。（待找）靜態(tài)查找

是僅僅進(jìn)行查詢和檢索操作，不改變查找表中數(shù)據(jù)元素間的邏輯關(guān)系的查找。（不改變元素關(guān)系）動(dòng)態(tài)查找

是除了進(jìn)行查詢和檢索操作外，還對查找表進(jìn)行插入、刪除操作的查找，動(dòng)態(tài)地改變查找表中數(shù)據(jù)元素之間的邏輯關(guān)系。（改變元素關(guān)系）平均查找長度

與關(guān)鍵字進(jìn)行比較的平均次數(shù)。對含有n個(gè)數(shù)據(jù)元素的查找表，查找成功時(shí)的平均查找長度為Pi為查找第i個(gè)數(shù)據(jù)元素的概率Ci為查找第i個(gè)數(shù)據(jù)元素的比較次數(shù)。課件制作人：錢玉文查找的基本概念

就是在給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素（結(jié)點(diǎn)）；若存在這樣的結(jié)點(diǎn)，查找成功；否則，查找失敗。3.1基本的查找技術(shù)課件制作人：錢玉文一、平均查找長度在查找過程中，要對每個(gè)結(jié)點(diǎn)記錄中的關(guān)鍵字進(jìn)行反復(fù)比較，以確定其位置。因此，與關(guān)鍵字進(jìn)行比較的平均次數(shù)，就稱為平均查找長度。是用來評價(jià)算法好壞的一個(gè)依據(jù)。(算法的評價(jià))對含有n個(gè)數(shù)據(jù)元素的查找表，查找成功時(shí)的平均查找長度為：其中：Pi

為查找表中第i個(gè)數(shù)據(jù)元素的概率，且

Ci為查找第i個(gè)數(shù)據(jù)元素時(shí)需比較的次數(shù)。

Ci隨查找過程及DS的不同而各異。（Ci與方法和結(jié)構(gòu)有關(guān)）課件制作人：錢玉文二、主要查找算法(1)順序查找(2)對分（折半）查找(3)分塊查找課件制作人：錢玉文3.1.1順序查找算法思想：

從第1個(gè)元素到最后1個(gè)元素，逐個(gè)進(jìn)行比較。特點(diǎn)：最簡單、最普通的查找方法。適用范圍（查找表的存儲結(jié)構(gòu)）：既適用于順序存儲結(jié)構(gòu)也適用于鏈?zhǔn)酱鎯Y(jié)構(gòu)

課件制作人：錢玉文操作步驟：step1

從第1個(gè)元素開始查找；step2

用待查關(guān)鍵字值與各結(jié)點(diǎn)（記錄）的關(guān)鍵字值逐個(gè)進(jìn)行比較；若找到相等的結(jié)點(diǎn)，則查找成功；否則，查找失敗。逐個(gè)比較課件制作人：錢玉文

int

seq_search(item,n,key)

int*item,n,key;{inti=0;while(i<n&&item[i]!=key)i++;if(item[i]==key){printf(“查找成功!\n”);return(i);}else{printf(“查找失敗!\n”);return(-1);}}item待查表

n元素個(gè)數(shù)

key要找的值While中，有兩個(gè)判斷條件，改進(jìn)一下，可以減少一半課件制作人：錢玉文（改進(jìn)算法）int

seq_search_adv(item,n,key)

int*item,n,key;{inti=0;//？哨兵的作用？

item[n]=key;/*設(shè)置哨兵*/while(item[i]!=key)i++;/*查找key*/if(i<n)/*如果i=n，沒找到*/{printf(“查找成功!\n”);return(i);}else{printf(“查找失敗!\n”);return(-1);}}注:順序查找算法中,執(zhí)行頻率最高的是while語句,改進(jìn)后,可以節(jié)省近一半的時(shí)間。?改進(jìn)后與改進(jìn)前的不同之處？

主要是取消了原來i<n的判斷課件制作人：錢玉文算法評價(jià)平均查找長度ASL在等概率的情況下一般情況下優(yōu)點(diǎn):對結(jié)點(diǎn)的邏輯次序(不必有序)和存儲結(jié)構(gòu)(順序、鏈表均可）無要求；當(dāng)序列中的記錄“基本有序”或N值較小時(shí)，是較好的算法；缺點(diǎn)：ASL較長討論：能否減少比較次數(shù)，以提高效率。例如：……二分法等，（比較學(xué)號查找和姓名查找）課件制作人：錢玉文3.1.2對分查找1.基本思想：

將有序序列的中點(diǎn)設(shè)置為比較對象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分。

即通過一次比較，將查找區(qū)間縮小一半。2.特點(diǎn)：二分查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。但是，二分查找的先決條件是查找表中的數(shù)據(jù)元素必須有序。課件制作人：錢玉文一、算法描述算法步驟：step1

首先確定整個(gè)查找區(qū)間的中間位置，

mid=int(（left+right）/2)step2

用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較；若相等，則查找成功；若大于，則在后半?yún)^(qū)域繼續(xù)進(jìn)行二分查找；若小于，則在前半?yún)^(qū)域繼續(xù)進(jìn)行二分查找。Step3

對確定的縮小區(qū)域再按二分公式，重復(fù)上述步驟；最后，得到結(jié)果：要么，查找成功，要么，查找失敗。存儲結(jié)構(gòu)用一維數(shù)組存放。課件制作人：錢玉文對分查找算法舉例對給定數(shù)列（有序）{3，5，11，17，21，23，28，30，32，50}，共10個(gè)數(shù)，按折半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。找30：

第1次：{3，5，11，17，21，23，28，30，32，50}mid1=int（1+10）/2=5

第2次：{23，28，30，32，50}mid2=int

（6+10）/2=8leftrightmidleftrightmid課件制作人：錢玉文對分查找演示（1）012mid=4但key=9<10,向左key

48

9

10

11

131934567high=7low=1在有序數(shù)4、8、9、10、11、13、19中查找

9初始：low=1,high=7 mid=int[(1+7)/2]=4比較key=9

<A[4]=10向左

High=mid-1=3對分查找演示（1）012mid=4key

48

9

10

11

131934567high=3（mid-1）low=1在有序數(shù)4、8、9、10、11、13、19中查找9初始：low=1,high=3

對分查找演示（1）012mid=2key

48

9

10

11

131934567high=3（mid-1）low=1在有序數(shù)4、8、9、10、11、13、19中查找9初始：low=1,high=3

mid=int[(1+3)/2]=2對分查找演示（1）012mid=2;但key=9>8,向右key

48

9

10

11

131934567high=3（mid-1）low=1在有序數(shù)4、8、9、10、11、13、19中查找9初始：low=1,high=3 mid=int[(1+3)/2]=2比較key=9>A[2]=8向右

low=mid+1=3對分查找演示（1）012key

48

9

10

11

131934567high=3low=3（mid+1）mid=2在有序數(shù)4、8、9、10、11、13、19中查找9初始：low=3,high=3對分查找演示（1）012mid=3;key

48

9

10

11

131934567high=3low=3在有序數(shù)4、8、9、10、11、13、19中查找9初始：low=3,high=3

mid=int[(3+3)/2]=3對分查找演示（1）012mid=3;但key=9中點(diǎn)值也為9，找到key

48

9

10

11

131934567high=3low=3在有序數(shù)4、8、9、10、11、13、19中查找9初始：low=3,high=3 mid=int[(3+3)/2]=3比較key=9=A[3]=9

查找成功！《oncemore》對分查找演示（2）012mid=4但key=5<10,向左key

48

9

10

11

131934567high=7low=1在有序數(shù)4、8、9、10、11、13、19中查找5初始：low=1,high=7 mid=int[(1+7)/2]=4比較key=5

<

A[4]=10向左

High=mid-1=3對分查找演示（2）012mid=4key

48

9

10

11

131934567high=3（mid-1）low=1在有序數(shù)4、8、9、10、11、13、19中查找5初始：low=1,high=3對分查找演示（2）012mid=2key

48

9

10

11

131934567high=3low=1在有序數(shù)4、8、9、10、11、13、19中查找5初始：low=1,high=3

mid=int[(1+3)/2]=2對分查找演示（2）012mid=2;但key=5<8,向左key

48

9

10

11

131934567high=3low=1在有序數(shù)4、8、9、10、11、13、19中查找5初始：low=1,high=3 mid=int[(1+3)/2]=2比較key=5<A[2]=8向左

high=mid-1=1對分查找演示（2）012mid=2key

48

9

10

11

131934567high=1（mid-1）low=1在有序數(shù)4、8、9、10、11、13、19中查找5初始：low=1,high=1對分查找演示（2）012mid=1key

48

9

10

11

131934567high=1low=1在有序數(shù)4、8、9、10、11、13、19中查找5初始：low=1,high=1

mid=int[(1+1)/2]=1對分查找演示（2）012mid=1;但key=5>4,向右key

48

9

10

11

131934567high=1low=1在有序數(shù)4、8、9、10、11、13、19中查找5初始：low=1,high=1 mid=int[(1+1)/2]=1比較key=5>A[1]=4向右

low=mid+1=2對分查找演示（2）012mid=1;但key=5>4,向右key

48

9

10

11

131934567high=1low=2（mid+1）失敗條件：low>high;處于間隙中的鍵值導(dǎo)致這種情況！在有序數(shù)4、8、9、10、11、13、19中查找5初始：low=2,high=1

LOW>HIGH,查找失敗《oncemore》

intbin_search(item,n,key)

int*item,n,key;//n為元素個(gè)數(shù)

{intleft,right,mid;left=0;right=n-1;while(leftright){mid=(left+right)/2;/*計(jì)算中點(diǎn)位置*/if(key<item[mid])right=mid-1;/*待查區(qū)間在左部*/elseif(key>item[mid])left=mid+1;/*待查區(qū)間在右部*/else{printf(“Successfulsearch\n”);returnmid;/*查找成功*/}

printf(“Searchfailure\n”);return-1;/*查找失敗*/}二、算法課件制作人：錢玉文三、算法評價(jià)優(yōu)點(diǎn):

ASLlog2n；即每經(jīng)過一次比較,查找范圍就縮 小一半。經(jīng)log2n次比較就可以完成查找過程。缺點(diǎn)：因要求有序，所以對所有數(shù)據(jù)元素按大小排序是非常費(fèi)時(shí)的操作。另外，順序存儲結(jié)構(gòu)的插入、刪除操作不大便利?？紤]：能否一次比較拋棄更多的部分（即一次比較，使查找范圍縮得更?。?，以達(dá)到提高效率的目的；……？把兩種方法（順序查找和二分查找）結(jié)合起來，即取順序查找簡單和二分查找高效之所長，來達(dá)到提高效率的目的？課件制作人：錢玉文3.1.3分塊查找分塊查找又稱索引順序查找，這是順序查找的一種改進(jìn)方法，用于在分塊有序表中進(jìn)行查找。(1)分塊：將n個(gè)數(shù)據(jù)元素“按塊有序”劃分為m塊（mn）。每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須“按塊有序”；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素，……。每個(gè)塊中元素不一定是有序的。課件制作人：錢玉文一、分塊查找算法描述1.算法描述:

step1

先選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表；step2查找分兩個(gè)部分：先對索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊中；在已確定的塊中用順序法進(jìn)行查找。課件制作人：錢玉文2.分塊查找數(shù)據(jù)描述將查找表分成3塊，每塊3個(gè)元素83660147塊最大關(guān)鍵字塊起始地址索引表塊最大關(guān)鍵字有序387363521406012345678947索引順序表塊內(nèi)關(guān)鍵字無序（也可有序）課件制作人：錢玉文分塊查找舉例有數(shù)列如下：

{22,12,13,9,8,33,42,44,38,24,48,60,58,74,47}

按“塊有序”分三塊:(22,12,13,9,8),(33,42,44,38,24),(48,60,58,74,47)。選取每塊中最大的關(guān)鍵字組成索引表[22,44,74],查找關(guān)鍵字值為60的元素。用二分法，確定在索引表中的位置為mid=2，key值60與a[2]比較，60>a[2],取第3個(gè)塊;在第3塊中用順序法查找,比較兩次,就可以找出60的元素來。4422742212139833424438244860587447List[1]List[2]List[3]11121314151611課件制作人：錢玉文二、索引表結(jié)構(gòu)定義#include"stdio.h"typedef

struct{

intkey;/*塊中元素最大值*/

intlink;/*指向塊入口地址*/

}index;課件制作人：錢玉文index_seq_search(index

ls[],int

s[],int

m,int

key,intl){

int

i,j,block_end;i=0;while(i<m&&key>ls[i].key)i++;/*確定在哪塊查找*/if(i>=m){printf(“Searchingfailure\n");return(-1);}else/*否則，查找成功處理*/三、分塊查找算法（c語言）ls[]索引表S[]待查表M

塊數(shù)key要找的值l

塊長度課件制作人：錢玉文

{j=ls[i].link;/*塊入口地址*/

if(j==m-1)block_end=n;elseblock_end=ls[i+1].link-1;while(key!=s[j]&&j<=block_end)j++;if(key==s[j]&&j<=block_end

)/*查找成功*/{printf("Successfulsearch\n”）；

return(j);}else/*查找失敗*/ {printf("Searchingfailure\n"); return(-1); }}}/*結(jié)束*/課件制作人：錢玉文四、算法評價(jià)

其中：n為表長，S為塊長（假設(shè)各塊長度相等）。優(yōu)點(diǎn)：插入、刪除操作方便；只要找到對應(yīng)的塊，在塊中任意位置操作均可。缺點(diǎn)：

索引表增加了輔助存儲空間。注：索引表在數(shù)據(jù)庫系統(tǒng)中廣泛使用。還有什么方法嗎？樹表查找

設(shè)索引表使用二分法，則有：課件制作人：錢玉文查找

就是在給定的DS中找出滿足某種條件的結(jié)點(diǎn)；若存在這樣的結(jié)點(diǎn)，則查找成功；否則，查找失敗。（找）查找表

是一組待查數(shù)據(jù)元素的集合。（待找）靜態(tài)查找

是僅僅進(jìn)行查詢和檢索操作，不改變查找表中數(shù)據(jù)元素間的邏輯關(guān)系的查找。（不改變元素關(guān)系）動(dòng)態(tài)查找

是除了進(jìn)行查詢和檢索操作外，還對查找表進(jìn)行插入、刪除操作的查找，動(dòng)態(tài)地改變查找表中數(shù)據(jù)元素之間的邏輯關(guān)系。（改變元素關(guān)系）平均查找長度

與關(guān)鍵字進(jìn)行比較的平均次數(shù)。對含有n個(gè)數(shù)據(jù)元素的查找表，查找成功時(shí)的平均查找長度為Pi為查找第i個(gè)數(shù)據(jù)元素的概率Ci為查找第i個(gè)數(shù)據(jù)元素的比較次數(shù)?？偨Y(jié):ASL=Pi*Cini=1課件制作人：錢玉文3.2哈希（Hash）查找哈希查找也稱為散列查找。它不同于前面介紹的幾種查找方法。上述方法都是把查找建立在比較的基礎(chǔ)上，而哈希查找則是通過計(jì)算存儲地址的方法進(jìn)行查找的。計(jì)算是計(jì)算機(jī)的特點(diǎn)之一，因此，建立在計(jì)算基礎(chǔ)上的哈希查找是一種快速查找方法。課件制作人：錢玉文直接查找技術(shù)

直接查找表的操作主要有以下兩種：

直接查找表的填入

直接查找表的取出

設(shè)表的長度為n。如果存在一個(gè)函數(shù)i=i（k），對于表中的任意一個(gè)元素的關(guān)鍵字k，滿足以下條件：（1）1≤i≤n。（2）對于任意元素的關(guān)鍵字，恒存在則稱此表為直接查找表，其中函數(shù)i＝i（k）稱為關(guān)鍵字k的映像函數(shù)。課件制作人：錢玉文3.2.1Hash表

設(shè)表的長度為n。如果存在一個(gè)函數(shù)i=i（k），對于表中的任意一個(gè)元素的關(guān)鍵字k滿足1≤i≤n，則稱此表為Hash表。其中，函數(shù)i=i(k)稱為關(guān)鍵字k的Hash碼。將關(guān)鍵字序列（09，31，26，19，01，13，02，11，27，16，05，21）依次填入長度為n＝12的表中。設(shè)映像函數(shù)為i＝INT（k／3）＋1，其中INT為取整符。Hash表技術(shù)的關(guān)鍵是要處理好表中元素的沖突問題，它主要包括以下兩方面的工作：（1）構(gòu)造合適的Hash碼，以便盡量減少表中元素沖突的次數(shù)。即Hash碼的均勻性要比較好。（2）當(dāng)表中元素發(fā)生沖突時(shí)，要進(jìn)行適當(dāng)?shù)奶幚怼?/p>

課件制作人：錢玉文一、哈希查找的基本概念哈希表

由哈希函數(shù)的值組成的表。哈希查找是建立在哈希表的基礎(chǔ)上，它是線性表的一種重要存儲方式和檢索方法。在哈希表中可以實(shí)現(xiàn)對數(shù)據(jù)元素的快速檢索。哈希函數(shù)

哈希表中的元素是由哈希函數(shù)確定的。將數(shù)據(jù)元素的關(guān)鍵字K作為自變量，通過一定的函數(shù)關(guān)系（稱為哈希函數(shù)）計(jì)算出的值，即為該元素的存儲地址。表示為：

Addr=H（key）

這個(gè)函數(shù)就是哈希函數(shù)建立哈希函數(shù)的原則均勻性：H（key）的值均勻分布在哈希表中；簡單：以提高地址計(jì)算的速度。

（位置均勻，計(jì)算簡單）課件制作人：錢玉文二、哈希函數(shù)常用的構(gòu)造方法數(shù)字分析法（截?cái)喾ǎ┱郫B法除留余數(shù)法（求模取余法）乘法課件制作人：錢玉文三、沖突及沖突處理由于哈希函數(shù)是一個(gè)壓縮映像，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象在哈希元素（地址）求解過程中，不同關(guān)鍵字值對應(yīng)到同一個(gè)存儲地址的現(xiàn)象稱為沖突。即關(guān)鍵字K1K2，但哈希函數(shù)值H（K1）=H（K2）。均勻的哈希函數(shù)可以減少?zèng)_突，但不能避免沖突。發(fā)生沖突后，必須解決；也即必須尋找下一個(gè)可用地址。處理沖突是建立哈希表過程中不可缺少的一部分。處理沖突有兩種方法：開放地址法鏈地址法課件制作人：錢玉文1.處理沖突——開放地址法當(dāng)發(fā)生地址沖突后，求解下一個(gè)地址用

Hi=(H（key）+di）MODmi=1,2,…,k(km-1)

其中:H(key)為哈希函數(shù),m為哈希表長度,di為增量序列。增量序列的不同取法，又構(gòu)成不同的開放地址法。

線性探測再散列

di=1,2,…,m-1

隨機(jī)再散列

di=RN(i)RN隨機(jī)數(shù)序列課件制作人：錢玉文2.處理沖突——鏈地址法當(dāng)發(fā)生地址沖突后,將所有函數(shù)值相同的記錄連成一個(gè)單鏈表。0123456789∧∧∧∧∧∧∧∧∧K1K2K3∧K4K5K6∧同義鏈，同一散列地址。同義鏈，同一散列地址。課件制作人：錢玉文3.2.2哈希查找操作步驟1.用給定的哈希函數(shù)構(gòu)造哈希表2.根據(jù)選擇的沖突處理方法解決地址沖突3.在哈希表的基礎(chǔ)上執(zhí)行哈希查找課件制作人：錢玉文一、建立哈希表建立哈希表操作步驟：step1

取數(shù)據(jù)元素的關(guān)鍵字key，計(jì)算其哈希函數(shù)值（地址）。若該地址對應(yīng)的存儲空間還沒有被占用，則將該元素存入；否則執(zhí)行step2解決沖突。step2

根據(jù)選擇的沖突處理方法，計(jì)算關(guān)鍵字key的下一個(gè)存儲地址。若下一個(gè)存儲地址仍被占用，則繼續(xù)執(zhí)行step2，直到找到能用的存儲地址為止。

課件制作人：錢玉文舉例對給定數(shù)列{22,41,53,46,30,13,1,67

},建立哈希表。表長取9,即[0～8]。哈希函數(shù)設(shè)定為:H(key)=keyMOD8,用線性探測解決沖突Hi=(H(key)+di)MODm,di=1,2,…,m-1。取22，計(jì)算H（22）=22mod8=6，該地址空，可用；

0123456782222

01234567841比較次數(shù)：11取41，計(jì)算H（41）=41mod8=1，該地址空，可用；課件制作人：錢玉文舉例（續(xù)一）取53，計(jì)算H（53）=53mod8=5，該地址空，可用；224101234567853比較次數(shù)：11122415346012345678比較次數(shù)：1112取46，計(jì)算H（46）=6，該地址沖突，用線性探測法計(jì)算下一個(gè)可用地址Hi=（6+1）MOD8=7，該地址空，可用；{22,41,53,46,30,13,1,67

}課件制作人：錢玉文舉例（續(xù)二）取30，計(jì)算H（30）=6，該地址沖突，用線性探測法計(jì)算下一個(gè)可用地址

Hi=（6+1）MOD8=7，該地址沖突，再用線性探測法計(jì)算下一個(gè)可用地址；Hi=0，地址空，可用；224101234567853

比較次數(shù)：3111246302241534601234567