數(shù)據(jù)結(jié)構(gòu)第7章

1第7章集合和搜索7.1集合及其表示7.2順序搜索7.3二分搜索7.4*搜索算法的時(shí)間下界數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第1頁。27.1集合及其表示7.1.1集合和搜索集合是一個(gè)基本的數(shù)學(xué)概念。在數(shù)學(xué)上，集合(set)是不同對象的無序匯集(collection)。集合的對象稱為元素或成員(member)。多重集(multi-set)是元素的無序匯集，其中，每個(gè)元素可出現(xiàn)一次或多次。例如，多重集{1,1,2,3}與{1,2,3,1}相同，但與{1,2,3}不同。通常用大括號(hào)表示無序集。一個(gè)有序集(orderedset)是元素的匯集，其中，每個(gè)元素可以出現(xiàn)一次或多次，并且它們的出現(xiàn)次序是重要的(如同向量一樣)。通常用圓括號(hào)表示有序集，例如，(2，1，3)。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第2頁。3

數(shù)學(xué)意義上的集合運(yùn)算主要有：集合的并，集合的差，集合的交，判斷兩個(gè)集合是否相等，判斷一個(gè)元素是否在集合中，以及判斷一個(gè)集合是否為另一個(gè)集合的子集合等。上一章中討論的并查集和集合按等價(jià)關(guān)系劃分的問題也是集合問題。集合結(jié)構(gòu)(簡稱集合)作為一種數(shù)據(jù)結(jié)構(gòu)，我們將它視為同類型數(shù)據(jù)元素的匯集。集合的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的聯(lián)系之外沒有其他關(guān)系。一般地，我們假定所討論的集合不包含相同元素。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第3頁。4

為了討論方便，我們假定集合的元素具有如下定義的結(jié)構(gòu)類型：

typedefstructentry{KeyTypeKey;DataTypeData;}Entry;其中，KeyType和DataType是用戶定義的數(shù)據(jù)類型，KeyType被稱為關(guān)鍵字類型，Key是關(guān)鍵字，我們要求類型KeyType是C語言所允許的、可以比較大小的類型。除關(guān)鍵字外的其他數(shù)據(jù)項(xiàng)歸入Data域部分，DataType可以是簡單類型，也可以是結(jié)構(gòu)類型。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第4頁。5

在數(shù)據(jù)結(jié)構(gòu)中，關(guān)鍵字(key)是用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)。我們可以進(jìn)一步定義，若一個(gè)關(guān)鍵字可以惟一標(biāo)識(shí)一個(gè)元素，則稱此關(guān)鍵字為主關(guān)鍵字(primarykey)。在集合中，不同數(shù)據(jù)元素有不同的主關(guān)鍵字值。若一個(gè)關(guān)鍵字可用以識(shí)別若干數(shù)據(jù)元素，則此關(guān)鍵字為次關(guān)鍵字(secondarykey)。當(dāng)數(shù)據(jù)元素是初等數(shù)據(jù)類型時(shí)，其關(guān)鍵字值即數(shù)據(jù)元素值。在本章討論中，若非特殊說明，都假定被搜索的關(guān)鍵字為主關(guān)鍵字。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第5頁。6

由于在集合結(jié)構(gòu)中，數(shù)據(jù)元素除了同屬于一個(gè)集合的聯(lián)系外，沒有其他特殊關(guān)系，所以像“在線性表上搜索第i個(gè)元素”，“在二叉樹上搜索一個(gè)結(jié)點(diǎn)的雙親”等運(yùn)算是不存在的，“搜索、插入和刪除指定關(guān)鍵字的元素”等運(yùn)算是集合上最基本的運(yùn)算。通常所說的搜索，簡單地說就是查表。這里所指的表(table)是信息表。表和文件都是數(shù)據(jù)元素的集合。當(dāng)信息量較少，整個(gè)集合的元素都存放在內(nèi)存中時(shí)，稱為表，否則稱為文件(file)。文件也常被歸入線性數(shù)據(jù)結(jié)構(gòu)中。在本章的敘述中，表和文件一律稱之為表。表和文件在數(shù)據(jù)處理中占有重要地位。搜索運(yùn)算是表和文件上最典型的運(yùn)算。在下面幾節(jié)中，我們將以搜索為主線討論集合結(jié)構(gòu)(信息表)。對文件的介紹將在第12章進(jìn)行。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第6頁。7

雖然在前幾章中已介紹過搜索運(yùn)算，這里我們再給搜索運(yùn)算下一個(gè)明確的定義。搜索(search)：根據(jù)給定的某個(gè)值，在表中確定一個(gè)關(guān)鍵字值等于給定值的數(shù)據(jù)元素，若表中存在這樣的元素，則稱搜索成功，搜索結(jié)果可以返回整個(gè)數(shù)據(jù)元素，也可指示該元素在表中的地址；若表中不存在關(guān)鍵字值等于給定值的元素，則稱搜索不成功(也稱搜索失敗)。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第7頁。87.1.2集合ADT

現(xiàn)在我們給出集合抽象數(shù)據(jù)類型(見ADT7－1)的定義。ADT7－1Set{數(shù)據(jù)：同類元素的有限匯集。元素由關(guān)鍵字標(biāo)識(shí)。通常，集合由不同元素組成，其最大允許長度為MaxSet。運(yùn)算：voidCreateList(Set*s，intmaxsize);后置條件:已創(chuàng)建一個(gè)空集合。BOOLIsEmpty(Sets)后置條件:若集合為空，則返回TRUE，否則返回FALSE。

BOOLIsFull(Sets)數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第8頁。9

后置條件:若集合滿，則返回TRUE，否則返回FALSE。

BOOLSearch(Sets，KeyTypek,T*x)

后置條件:在集合中搜索關(guān)鍵字值為k的元素。如果存在該元素，則將其放入*x，并且函數(shù)返回TRUE，否則返回FALSE。

BOOLInsert(Set*s，Tx)

后置條件:在集合中搜索關(guān)鍵字值為k的元素。如果不存在該元素，則在集合中插入x，并且函數(shù)返回TRUE，否則返回FALSE。

BOOLRemove(Set*s，KeyTypek,T*x)

后置條件:在集合中搜索關(guān)鍵字值為k的元素。如果存在該元素，則將該元素賦給*x，并從集合中刪除之，函數(shù)返回TRUE，否則返回FALSE。}

數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第9頁。107.1.3集合的表示組織集合的方法很多，組織的方法不同，搜索等運(yùn)算的算法也不同，所以集合的表示方法將直接影響集合運(yùn)算的效率。集合可以用線性表、搜索樹、跳表和散列表表示。本章討論集合的線性表表示；下一章介紹多種表示集合的搜索樹：二叉搜索樹、二叉平衡樹、B－樹和Trie樹；跳表和散列表是另外兩種表示集合的數(shù)據(jù)結(jié)構(gòu)，它們是第9章討論的主題。這些數(shù)據(jù)結(jié)構(gòu)可以在不同的條件下，有效地表示集合結(jié)構(gòu)，以滿足不同的應(yīng)用需求。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第10頁。117.2順序搜索

1.順序搜索無序表集合可以用無序表表示，在無序表搜索一個(gè)指定關(guān)鍵字值的元素的方法是順序搜索。所謂順序搜索(sequentialsearch)，就是從頭開始，逐個(gè)檢查，若能在表中找到關(guān)鍵字值等于給定關(guān)鍵字值的元素，則查找成功；否則查找失敗。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第11頁。12為了簡化搜索算法的描述，我們對集合的元素作如下假定：typedefintKeyType;typedefstructentry{KeyTypeKey;DataTypeData;}Entry;typedefEntryT;數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第12頁。13

程序7－1是順序搜索無序表的C語言程序，線性表采用順序存儲(chǔ)方式。算法從頭開始檢查表lst，令待查關(guān)鍵字值k與表中元素的關(guān)鍵字值lst.Elements[i].Key進(jìn)行比較，如果相等，則將該元素lst.Elements[i]賦給變量*x，并返回TRUE，即搜索成功；否則如果查完整個(gè)表，都未找到待查關(guān)鍵字值的元素，則返回FALSE，即搜索失敗。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第13頁。14【程序7－1】順序搜索無序表。BOOLSeqSearch(Listlst,KeyTypek,T*x){inti;for(i=0;i<lst.Size;i++)if(lst.Elements[i].Key==k){x=lst.Elements[i];returnTRUE; /*搜索成功*/}returnFALSE; /*搜索失敗*/}數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第14頁。15

2.順序搜索有序表集合可以用有序表表示。一個(gè)有序表是一個(gè)線性表(a0，a1,…,an－1)，并且表中元素的關(guān)鍵字值有如下關(guān)系：

ai.Key≤ai+1.Key(0≤i＜n－1)其中，ai.Key代表元素ai的某個(gè)指定的關(guān)鍵字域。程序7－2是順序搜索有序表的C語言程序。程序中增設(shè)了一個(gè)被稱作哨兵的元素an，an.Key為+(。這樣，表的實(shí)際長度不能超過MaxList－1。增加了哨兵元素后，在for循環(huán)中可以省去下標(biāo)間的比較，不再需要通過下標(biāo)比較來判定是否已經(jīng)查完整個(gè)表。當(dāng)lst.Elements[i].Key≥k時(shí)就可以結(jié)束for循環(huán)。此時(shí)，有兩種可能的情況，或者已搜索成功，有l(wèi)st.Elements[i].Key==k，或者搜索失敗。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第15頁。16【程序7－2】順序搜索有序表。#defineMaxNum1000BOOLSeqSearch2(Listlst,KeyTypek,T*x){inti;lst.Elements[lst.Size].Key=MaxNum;for(i=0;lst.Elements[i].Key<k;i++);if(lst.Elements[i].Key==k){*x=lst.Elements[i];returnTRUE;/*搜索成功*/}elsereturnFALSE; /*搜索失敗*/}數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第16頁。17

需要說明的是，我們完全可以采用ADT7－1Set的函數(shù)Search的名稱作為函數(shù)SeqSearch和SeqSearch2的名稱，這里使用不同的名稱是為了表明它們是Search函數(shù)的不同版本，但它們都嚴(yán)格符合函數(shù)Search的定義。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第17頁。18

3．平均搜索長度分析一個(gè)搜索算法的時(shí)間復(fù)雜性，通常分成功搜索一個(gè)指定關(guān)鍵字值的元素以及搜索失敗兩種情況加以討論。搜索中所需的關(guān)鍵字值之間的比較次數(shù)的期望值，被稱為搜索算法的平均搜索長度ASL(AverageSearchLength)。求成功搜索的平均搜索長度，需要給定表中元素ai被搜索的概率pi。設(shè)表長為n，假定每個(gè)元素的搜索概率是相等的，即pi=1/n，則程序7－1中順序搜索線性表在搜索成功時(shí)的平均搜索長度為(7－1)數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第18頁。19

函數(shù)SeqSearch在搜索失敗的情況下，總要進(jìn)行n次關(guān)鍵字值之間的比較。有序表搜索函數(shù)SeqSearch2，其成功搜索的平均搜索長度與函數(shù)SeqSearch大致相同。但在搜索失敗的情況下，函數(shù)SeqSearch2大約平均比SeqSearch快一倍。設(shè)有序表為(a0,a1,…,an－1)，通?？梢约俣ù樵氐闹滴挥赼0之前，a0與a1之間，a1與a2之間,…,an－2與an－1之間以及an－1之后的共n+1個(gè)區(qū)間內(nèi)的概率是相等的。搜索失敗的平均搜索長度為(7－2)數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第19頁。204．元素按搜索概率排列上面的分析都假定表中的元素被查詢的概率是相等的，但大多數(shù)情況下，表中元素的搜索概率并不相等。例如，在一個(gè)由全體教職工的病歷檔案組成的表中，顯然體弱多病的教職工的病歷記錄被搜索的概率必然高于年輕力壯的教職工的病歷記錄。在這種情況下，如果能事先知道每個(gè)記錄的搜索概率，就可以將線性表中的記錄按搜索概率從大到小排列，把搜索概率最大的記錄放在表的最前面，這樣，我們就能得到最小的平均搜索長度。可以證明，順序搜索搜索成功時(shí)的平均搜索長度ASLS，在表中記錄按p0≥p1≥…≥pn－1排列時(shí)有最小值。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第20頁。21

5．自組織線性表實(shí)際上，我們往往無法事先知道哪個(gè)記錄最經(jīng)常被訪問。更復(fù)雜的情況是，有的記錄可能在一段時(shí)間內(nèi)頻繁地被訪問，此后就極少被訪問了，也就是說搜索概率是隨時(shí)間變化的。自組織線性表(self-organizinglist)就是為了解決這些問題而設(shè)計(jì)的。有三種可能的自組織表方法：計(jì)數(shù)方法(count)、移至開頭(move-to-front)和互換位置(transposition)。計(jì)數(shù)方法是為每個(gè)記錄保存一個(gè)訪問計(jì)數(shù)，每成功訪問一次，將該計(jì)數(shù)器加一，當(dāng)此記錄的訪問次數(shù)已大于它前面的記錄時(shí)，將此記錄移到前面去，即線性表按記錄的訪問次數(shù)非遞增排列。這種方法的缺點(diǎn)是移動(dòng)記錄需要時(shí)間，計(jì)數(shù)器需要空間。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第21頁。22

移至開頭的方法在成功搜索了一個(gè)記錄后，就把它放在表的開頭。移至開頭的方法對訪問頻率的局部變化能很好地適應(yīng)。如果一個(gè)記錄近期被頻繁訪問，在這段時(shí)間內(nèi)，它就會(huì)靠近線性表的前端。這種方法適用于鏈接結(jié)構(gòu)，采用順序表存儲(chǔ)時(shí)開銷太大?；Q位置的方法是把被成功搜索的記錄與它前面的一個(gè)記錄互換位置?；Q位置的方法可適用于順序表和鏈表。隨著時(shí)間的推移，最常用的記錄慢慢被移到線性表的最前端。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第22頁。237.3二分搜索

當(dāng)有序表采用順序方式存儲(chǔ)時(shí)，可以采用二分搜索的方法搜索指定關(guān)鍵字值的記錄。二分搜索的基本思想是選擇表中某一位置i的元素，設(shè)元素ai的關(guān)鍵字值為Ki，將Ki與待查元素的關(guān)鍵字值tkey比較，比較結(jié)果有三種可能性：

(1)tkey<Ki:若關(guān)鍵字值為tkey的元素在表中，則必定在子表(a0,a1,…,ai－1)中，可以在此子表中繼續(xù)進(jìn)行搜索；

(2)tkey==Ki:搜索成功；數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第23頁。24(3)tkey>Ki:若關(guān)鍵字值為tkey的元素在表中，則必定在子表(ai+1,ai+2,…,an－1)中，可以在此子表中繼續(xù)進(jìn)行搜索。使用不同的規(guī)則來分割搜索區(qū)間，確定位置i，可得到不同的二分搜索方法，如對半搜索、一致對半搜索、斐波那契搜索和插值搜索等。在本節(jié)，我們將討論對半搜索和斐波那契搜索。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第24頁。257.3.1對半搜索對半搜索是一種二分搜索。設(shè)當(dāng)前搜索的子表為(alow,alow+1,…,ahigh),若令i=(low+high)/2則這種二分搜索稱為對半搜索。對半搜索算法將表劃分成幾乎相等的兩個(gè)子表。對半搜索算法要求有序表采用順序存儲(chǔ)。程序7－3是對半搜索的C語言程序。對半搜索的遞歸算法包括兩個(gè)函數(shù)：bSch和BSearch。其中，bSch是實(shí)現(xiàn)對半搜索的遞歸算法，函數(shù)BSearch是面向用戶的接口函數(shù)。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第25頁。26

函數(shù)bSch中，mid、low和high均為元素下標(biāo)。如果當(dāng)前搜索的表不空，則令待查關(guān)鍵字與表中mid位置上的元素的關(guān)鍵字比較，如果相等，則搜索成功，返回mid；如果小于mid，則繼續(xù)查找左半部分子表，其下標(biāo)范圍為[low,mid－1],否則繼續(xù)查找右半部分子表，其下標(biāo)范圍為[mid+1,high];如果當(dāng)前搜索的表是空表，則搜索失敗，返回－1。函數(shù)BSearch調(diào)用函數(shù)bSch提供對半搜索的用戶接口。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第26頁。27【程序7－3】對半搜索的遞歸算法。intbSch(Listlst,KeyTypek,intlow,inthigh){intmid; if(low<=high){ mid=(low+high)/2; if(k<lst.Elements[mid].Key)returnbSch(lst,k,low,mid－1); elseif(k>lst.Elements[mid].Key)returnbSch(lst,k,mid+1,high);elsereturnmid; /*搜索成功*/ }數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第27頁。28return－1; /*搜索失敗*/}BOOLBSearch(Listlst,KeyTypek,T*x){ inti; i=bSch(lst,k,0,lst.Size); if(i==－1)returnFALSE; /*搜索失敗*/ else{ *x=lst.Elements[i];returnTRUE; /*搜索成功*/ }}數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第28頁。29【程序7－4】對半搜索的迭代算法。BOOLBSearch2(Listlst,KeyTypek,T*x){ intmid,low=0,high=lst.Size－1; while(low<=high){ mid=(low+high)/2; if(k<lst.Elements[mid].Key)high=mid－1; elseif(k>lst.Elements[mid].Key)low=mid+1; else{*x=lst.Elements[mid];returnTRUE; /*搜索成功*/ } }returnFALSE; /*搜索失敗*/}數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第29頁。30

函數(shù)BSearch和BSearch2是Search函數(shù)的不同版本，它們嚴(yán)格符合Search函數(shù)的定義。順序搜索適用于有序表，也適用于無序表。雖然在我們的例子中，線性表采用順序存儲(chǔ)。事實(shí)上，在鏈接存儲(chǔ)的線性表上進(jìn)行順序搜索，具有與順序表基本相同的效率。但對半搜索只適用于有序表，并且要求有序表采用順序存儲(chǔ)。鏈接存儲(chǔ)的有序表無法有效地實(shí)現(xiàn)對半搜索，這是因?yàn)閷Π胨阉饕箅S機(jī)存取位于mid處的元素，這只有在順序表情況下，才能有效實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第30頁。317.3.2二叉判定樹我們可以用下面的具體例子來模擬對半搜索算法的執(zhí)行過程。其中，方括號(hào)內(nèi)是當(dāng)前搜索的表，帶下畫線的整數(shù)是當(dāng)前與待查關(guān)鍵字值key比較的關(guān)鍵字值Ki。

(1)key=66，搜索成功：[21 30 36 41 52 54 66 72 83 97]21 30 36 41 52 [54 66 72 83 97]21 30 36 41 52 [54 66] 72 83 9721 30 36 41 52 54 [66] 72 83 97數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第31頁。32(2)key=35，搜索失?。篬21 30 36 41 52 54 66 72 83 97][21 30 36 41] 52 54 66 72 83 9721 30 [36 41] 52 54 66 72 83 9721 30] [36 41 52 54 66 72 83 97數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第32頁。33

上述搜索過程可以用一棵二叉樹來描述。通常稱描述搜索算法執(zhí)行過程的二叉樹為二叉判定樹(binarydecisiontree)。一個(gè)以比較關(guān)鍵字值為基礎(chǔ)的搜索算法的二叉判定樹模型可以這樣建立:(1)待查關(guān)鍵字值key與表中關(guān)鍵字值Ki之間的一次比較操作，表現(xiàn)為二叉判定樹中的一個(gè)內(nèi)結(jié)點(diǎn)，用一個(gè)圓形結(jié)點(diǎn)表示，并用i標(biāo)識(shí)。如果key等于Ki，則算法在該結(jié)點(diǎn)處成功終止。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第33頁。34(2)二叉判定樹的根結(jié)點(diǎn)，代表算法中首先與key比較的關(guān)鍵字值Ki，用i標(biāo)識(shí)。

(3)結(jié)點(diǎn)i的左孩子是當(dāng)key＜Ki時(shí)，算法接下去與key比較的元素的序號(hào)所標(biāo)識(shí)的結(jié)點(diǎn)，其右孩子是當(dāng)key＞Ki時(shí)，算法接下去與key比較的元素的序號(hào)所標(biāo)識(shí)的結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第34頁。35(4)如果根據(jù)算法，在key與Ki比較之后有key<Ki，且算法終止，那么，結(jié)點(diǎn)i的左孩子用一個(gè)方形結(jié)點(diǎn)表示，結(jié)點(diǎn)的標(biāo)號(hào)為i－1。反之，在key與Ki比較之后有key＞Ki，且算法終止，那么，結(jié)點(diǎn)i的右孩子用一個(gè)方形結(jié)點(diǎn)表示，結(jié)點(diǎn)的標(biāo)號(hào)為i。方形結(jié)點(diǎn)稱為外結(jié)點(diǎn)。換句話說，如果算法在方形結(jié)點(diǎn)i處終止，這意味著：當(dāng)0＜i＜n－1時(shí)，Ki＜key＜Ki+1；當(dāng)i=－1時(shí)，key＜K0；當(dāng)i=n－1時(shí)，key>Kn－1。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第35頁。36(5)從根結(jié)點(diǎn)到每個(gè)內(nèi)結(jié)點(diǎn)的一條路徑代表成功搜索的一條比較路徑。如果搜索成功，則算法在內(nèi)結(jié)點(diǎn)處終止，否則算法在外結(jié)點(diǎn)處終止。圖7－1是對有10個(gè)元素的有序表執(zhí)行對半搜索算法的二叉判定樹。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第36頁。37圖7－1對半搜索二叉判定樹(n=10)數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第37頁。38

一棵有n個(gè)結(jié)點(diǎn)的二叉判定樹的高度(不計(jì)代表失敗的方形結(jié)點(diǎn))為lb?n+1。所以，對半搜索在成功搜索的情況下，關(guān)鍵字值之間的比較次數(shù)不超過lbn+1。對于不成功的搜索，算法需要作

lbn

或

lbn+1次比較。那么，對于成功搜索，它的平均搜索長度是多少呢？為簡單起見，假定表的長度n=2k－1，即k=lb(n+1)，則對半搜索的二叉判定樹是一棵滿二叉樹。樹中層數(shù)為1的結(jié)點(diǎn)有1個(gè)，層數(shù)為2的結(jié)點(diǎn)有2個(gè)，…,層數(shù)為i的結(jié)點(diǎn)有2i-1個(gè)。又假定表中每個(gè)元素的搜索概率是相等的(pi=1/n)，則成功搜索的平均搜索長度為數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第38頁。39(7－3)數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第39頁。407.3.3*斐波那契搜索斐波那契(Fibonacci)序列的定義是：(n=0,1)(n≥2)數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第40頁。41

取有序表的長度n＝fm+1－1(不考慮nfm+1－1的情況)。為了討論方便，我們對有序表從1開始編號(hào)，其范圍為[1,fm+1－1]。我們可以設(shè)計(jì)一種新的二分搜索算法，它按下面描述的方式將一個(gè)表分成并不相等的兩部分，即首先與待查關(guān)鍵字值key比較的元素的位置將是mid=fm，如同對半搜索，此元素將表分成左、右兩部分：[1,mid－1]和[mid+1,n]。左右兩個(gè)子集的大小分別為fm－1和fm－1－1。這就是所謂的黃金分割。這樣的二分搜索稱為斐波那契搜索。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第41頁。42

斐波那契算法的二叉判定樹是滿足下面定義的斐波那契樹(以下簡稱斐樹)。一棵m階斐樹有fm+1－1個(gè)內(nèi)結(jié)點(diǎn)和fm+1個(gè)外結(jié)點(diǎn)。外結(jié)點(diǎn)的個(gè)數(shù)比內(nèi)結(jié)點(diǎn)多一個(gè)。設(shè)Tm是一棵m階斐樹，則

(1)當(dāng)m=0或m=1時(shí)，有T0=T1，則斐樹是只有一個(gè)編號(hào)為0的外結(jié)點(diǎn)的樹。

(2)當(dāng)m>1時(shí)，Tm的根是編號(hào)為fm的內(nèi)結(jié)點(diǎn)，而Tm的根的左子樹是m－1階斐樹Tm－1，其右子樹是m－2階斐樹Tm－2+fm。符號(hào)Tm－2+fm表示將斐樹Tm－2的每個(gè)元素的編號(hào)加上fm后得到的斐樹。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第42頁。43

圖7－2是一棵n=f7－1=12的6階斐樹。從圖中我們可以看到，對于任何編號(hào)為i的結(jié)點(diǎn)，如果以它為根的子樹是一棵u階斐樹，其左、右子樹分別是一棵u－1和u－2階斐樹，并且它的左孩子的編號(hào)為i－fu－2，而它的右孩子的編號(hào)為i+fu－2(如果存在的話)。進(jìn)一步我們還看到，若以i為根的子樹是u=2或3階斐樹，這時(shí)有fu－1=f1=1或fu－1=f2=1，那么當(dāng)Ki<key時(shí)，算法到達(dá)葉結(jié)點(diǎn)，以失敗而結(jié)束。若以i為根的子樹是u=2的斐樹，fu－2=f0=0，那么當(dāng)Ki>key時(shí)，算法到達(dá)葉子結(jié)點(diǎn)，也以失敗結(jié)束。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第43頁。44圖7－26階斐波那契樹(n=f7－1=12)數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第44頁。45

如果我們以i指示正在與key作比較的元素，且它是一棵u階斐樹的根，令p=fu－1，q＝fu－2，則i的左子樹是u－1階斐樹，其根編號(hào)為i－fu－2，新的p應(yīng)為fu－2，新的q為fu－3，這時(shí)只需對各變量作修正：i=i－q；t=p；p=q;q=t－q；即可。而i的右子樹是u－2階斐樹，其根編號(hào)為i＋fu－2，新的p應(yīng)為fu－3，新的q為fu－4，這時(shí)只需對各變量作修正：i=i+q;p=p－q;q=q－p;即可。通過上述修正，便可實(shí)現(xiàn)對左或右子樹中結(jié)點(diǎn)的繼續(xù)搜索，直到搜索成功，或者到達(dá)葉子結(jié)點(diǎn)為止(有(key<Ki&&q==0)或者(key>Ki&&p==1))。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第45頁。46

程序7－5是斐波那契搜索的C語言程序。算法的開始部分計(jì)算得到i＝fm，p＝fm－1，q=fm－2，然后令待查關(guān)鍵字值k與lst.Elements[i－1].Key比較。注意，由于在討論斐樹時(shí)，對樹中元素從1開始編號(hào)，但事實(shí)上元素在數(shù)組Elements中的下標(biāo)從0開始編號(hào)，所以i是編號(hào)，i－1即為元素在數(shù)組中的下標(biāo)。圖7－2的斐樹中的數(shù)字是元素的編號(hào)，如果斐波那契搜索二叉判定樹的結(jié)點(diǎn)采用元素下標(biāo)標(biāo)識(shí)，只需將圖7－2中的所有結(jié)點(diǎn)的編號(hào)減一，便得到相應(yīng)的斐波那契搜索的二叉判定樹。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第46頁。47【程序7－5】斐波那契搜索。BOOLBFSearch(Listlst,KeyTypek,T*x){ intt,i=1,p=1,q=2,n=lst.Size; while(q<=n){ p=q;q=i+q;i=p; }p=q－i;q=i－p; /*計(jì)算得到i＝fm，p＝fm－1，q=fm－2*/for(;;)if(k==lst.Elements[i－1].Key){*x=lst.Elements[i－1];returnTRUE;/*搜索成功*/數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第47頁。48 } else if(k<lst.Elements[i－1].Key)if(q==0)returnFALSE; /*搜索失敗*/ else{ i=i－q;t=p;p=q;q=t－q; }elseif(p==1)returnFALSE; /*搜索失敗*/ else{ i=i+q;p=p－q;q=q－p; }}數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第48頁。497.4*搜索算法的時(shí)間下界

從順序搜索算法的時(shí)間分析，我們可以看到，使用順序搜索算法在一個(gè)有n個(gè)元素的集合中搜索一個(gè)指定關(guān)鍵字值的元素，在最壞情況下需要進(jìn)行n次元素間的比較才能確定元素是否在表中。對半搜索所需的關(guān)鍵字值間的比較次數(shù)，從對半搜索二叉判定樹上可以看到，它不會(huì)超過判定樹的高度(不包括失敗結(jié)點(diǎn))，為lbn+1。那么，是否存在一個(gè)比對半搜索更好的算法，使得在n個(gè)元素的集合中，搜索指定關(guān)鍵字值的元素所需的關(guān)鍵字值之間的比較次數(shù)少于lbn+1呢？數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第49頁。50

我們已經(jīng)知道，可以用二叉判定樹描述對半搜索算法的行為。一個(gè)通過關(guān)鍵字值間的比較來搜索集合中的元素的算法，如果是正確的，就可以斷定該搜索算法的判定樹上至少有n個(gè)內(nèi)結(jié)點(diǎn)。我們可以用反證法證明這一點(diǎn)。數(shù)據(jù)結(jié)構(gòu)第7章全文共56頁，當(dāng)前為第50頁。51

假設(shè)有一個(gè)通過比較關(guān)鍵字值實(shí)施搜索的搜索算法，當(dāng)元素個(gè)數(shù)為n時(shí)，二叉判定樹中的內(nèi)結(jié)點(diǎn)數(shù)小于n，則對于從0到n－1之間的某個(gè)下標(biāo)i，判定樹中沒有對應(yīng)標(biāo)號(hào)為i的結(jié)點(diǎn)。這時(shí)，如果我們有兩個(gè)長度都為n的有序表L和L'