第7章查找(Search)

7.1查找基本概念7.2基于線性表靜態(tài)查找7.3基于樹表動態(tài)查找7.4哈希查找1/6/20231第7章查找第7章查找(Search)7.1查找基本概念1/6Introduction查找是非數(shù)值處理中一種最基本、最重要的操作。查找，也稱檢索，是一種運算，是軟件設計中經(jīng)常遇到的一種運算。數(shù)據(jù)結(jié)構(gòu)不同，查找方法也會不同。查找方法的好壞直接影響著計算機的使用效率。查找概述1/6/20232第7章查找Introduction查找是非數(shù)值處理中一種最基本、最重要7.1、查找基本概念1）查找Search：又稱檢索，是指在大量的數(shù)據(jù)中尋找關(guān)鍵字等于給定值的記錄。若存在這樣一個記錄，則稱查找成功，否則稱查找不成功。分為:靜態(tài)查找;動態(tài)查找;2）關(guān)鍵字(Keyword)：就是數(shù)據(jù)元素中可以唯一標識一個數(shù)據(jù)元素的數(shù)據(jù)項。例如：學生管理登記卡中的學號。3）平均查找長度(AverageSearchLength)(ASL)

算法評價:評價時考慮：（1）速度；（2）占用存儲空間；（3）復雜程度。1/6/20233第7章查找7.1、查找基本概念1）查找Search：又稱檢索，是指在

引入平均查找長度，作為查找算法評價的依據(jù)。平均查找長度：為確定記錄在表中的位置所進行的和關(guān)鍵字比較的次數(shù)的期望值，簡寫為ASL.含有n個元素的表中找一個元素成功的ASL為：Pi為查找第i個元素的概率；Ci為查到第i個元素所需的比較次數(shù)。

ASL=∑Pi×Cii=1n1/6/20234第7章查找引入平均查找長度，作為查找算法評價的依據(jù)。含有n個元素結(jié)構(gòu)體數(shù)組

typedefstruct{charname[10];KeyTypekey;}DataType;DataTyper[Maxnum];name[0]…name[9]keyr[0]r[1]………r[Maxnum]name[0]…name[9]key設表中記錄以順序存儲結(jié)構(gòu)組織。每個記錄包括：關(guān)鍵字，其他數(shù)據(jù)項等。其類型說明用C語言描述如下：4)類型說明：1/6/20235第7章查找結(jié)構(gòu)體數(shù)組name[0]…name[9]keyr[0]r[1

5）查找方法:

順序表靜態(tài)查找，樹表動態(tài)查找，哈希查找7.2、基于線性表的靜態(tài)查找順序表上的查找主要有三種方法:順序查找法:針對順序表存儲結(jié)構(gòu)折半查找法:針對有序順序表存儲結(jié)構(gòu)分塊查找:針對索引順序表存儲結(jié)構(gòu)

1/6/20236第7章查找5）查找方法:

順序表靜態(tài)查找，樹表動態(tài)查i=01826322137566475i=1i=5i=4i=3i=2基本思想：從第一個元素開始，將給定值與表中逐個元素的關(guān)鍵字比較，直至檢索成功或直至最后一個元素檢索失敗為止。1.順序查找：1/6/20237第7章查找i=01826322137566475i=1i=5i=4i=intSeqsearch(DataTyper[],intkey,intn){inti=0;while(r[i].key!=key&&i<n)i++;if(r[i].key==key)returni;elsereturn-1;}順序查找算法：i=01826322137566475i=1i=5i=4i=3i=2演示：查找key=561/6/20238第7章查找intSeqsearch(DataTyper[],算法分析：ASL=∑Pi×Ci=1/n(1+2+……..+n)*2=n+1i=1n表從r[1]-r[Max],r[0]存放key。改進算法：希望盡量減少比較次數(shù)。1/6/20239第7章查找算法分析：ASL=∑Pi×Cii=1n表從r[1]-r32intseqsearch(DataTyper[],intkey,intn){inti;r[0].key=key;i=n;while(r[i].key!=key)i--;returni;}算法描述i=81826322137566475i=7i=6i=5i=4i=3012345678演示：查找key=321/6/202310第7章查找32intseqsearch(DataTyper[],算法分析算法簡單，效率較低算法特點ASL=∑Pi×Ci=(1/n)×(1+2+……..+n)=(n+1)/2i=1n1/6/202311第7章查找算法分析算法簡單，效率較低算法特點ASL=∑Pi×Ci2.折半查找法（對半或二分查找）

針對有序表使用的查找方法，是簡單有效的方法。有序表：記錄的關(guān)鍵字以遞增（或遞減）順序排列的表。基本思想：給定值key與中間位置的記錄的關(guān)鍵字比較，若相等則查找成功；若給定值大于中間位置記錄的關(guān)鍵字值，則在表的后半部分繼續(xù)折半查找；否則在表的前半部分進行折半查找，直至查找成功或不成功。1/6/202312第7章查找2.折半查找法（對半或二分查找）有序表：記錄的關(guān)鍵字以遞增（步驟：（1）計算中間位置mid=(low+high)/2取整。（2）key與R[mid].key比較若key=R[mid].key則查找成功；若key<R[mid].key,則high=mid-1,轉(zhuǎn)（3）。若key>R[mid].key,則low=mid+1,轉(zhuǎn)（3）。（3）若low≤high,則重復（1）否則：查找不成功，結(jié)束。

1/6/202313第7章查找步驟：1/6/202313第7章查找Searchlow1826324552668091highmid52668091

lowhighmid8091highLowmid用折半查找法在順序表中查找關(guān)鍵字為80的記錄！1/6/202314第7章查找Searchlow1826324552668091highmlow1826324552668091highmid

lowhighmidhighLowmid18263245526680911826324552668091

low1826324552668091high查找關(guān)鍵字為10的記錄！注意：使用折半查找算法時，線性表中的元素必須按照關(guān)鍵字排列有序；并且必須以順序存儲方式存儲。1/6/202315第7章查找low1826324552668091highmidintbinsearch(DataTyper[],intn,intkey){intlow,high,mid;low=0;high=n-1;while(low<=high){mid=(low+high)/2;if(key==r[mid].key)returnmid;elseif(key>r[mid].key)low=mid+1;elsehigh=mid-1;}returu–1;}算法描述初始化循環(huán)條件計算中間下標查找成功前半部分后半部分查找失敗1/6/202316第7章查找intbinsearch(DataTyper[],intintbinsearch(DataTyper[],intn,intkey){intlow,high,mid;low=0;high=n-1;while(low<=high){mid=(low+high)/2;if(key==r[mid].key)returnmid;elseif(key>r[mid].key)low=mid+1;elsehigh=mid-1;}returu–1;}low1826324552668091highmid52668091lowhighmid8091highLowmid用折半查找法在順序表中查找關(guān)鍵字為80的記錄！1/6/202317第7章查找intbinsearch(DataTyper[],int假設：查找關(guān)鍵字為0-6的數(shù)據(jù)折半法算法分析3564102二叉判定樹假設：有序表長度為n,且n≤2h-1若n=2h-1則：查找過程為一棵深度為h的滿二叉樹,查找的過程形成二叉判定樹ASL=1/7(1+2×2+4×3)=2.431/6/202318第7章查找假設：查找關(guān)鍵字為0-6的數(shù)據(jù)折半法算法分析3564102二比順序查找效率高只適用于有序的順序存儲的表，算法特點:ASL≈log2(n+1)-1ASL=∑[(1/n)×2i-1×i]i=1n則滿二叉樹的第i層有2i-1個結(jié)點。1/6/202319第7章查找比順序查找效率高算法特點:ASL≈log2(n+1)-1AS3.分塊查找（索引順序表查找）

將順序查找法與折半查找法結(jié)合

基本思想：使用分塊查找算法時，要求將線性表均勻地分成若干塊，每塊的元素不要求有序，但一定要保證塊間有序。另外，對表要進行索引存儲。即新建一個索引表，存放各塊中最大關(guān)鍵字。分塊查找實際上是先在索引表中進行順序查找或折半查找，再在塊內(nèi)進行順序查找。1/6/202320第7章查找3.分塊查找（索引順序表查找）將順序查找法與折半查找法結(jié)索引表類型:1.對單關(guān)鍵字建立索引表:2.對多關(guān)鍵字建立索引表:完全索引表,多級索引表.3.分塊個數(shù)建立索引表:等長,不等長主表索引表主表完全索引表索引表分塊查找的基本過程如下：(1)首先，將待查關(guān)鍵字K與索引表中的關(guān)鍵字進行比較，以確定待查記錄所在的塊。具體的可用順序查找法或折半查找法進行。(2)進一步用順序查找法，在相應塊內(nèi)查找關(guān)鍵字為K的元素。1/6/202321第7章查找索引表類型:1.對單關(guān)鍵字建立索引表:主表索引表主表完全索引

例如：{17，8，21，19，31，33，25，22，43，37，35,40，61，78，73，55}分塊[17，8，21，19]，[31，33，25，22]，[43，37，35，40],[61，73，78，55]索引表：2133437821334378關(guān)鍵字地址數(shù)據(jù)表8…21…31…33…25…43…61…37…35…73…78…19…22…40…55…17…1/6/202322第7章查找例如：{17，8，21，19，31，33，25，22，

typedefstruct{charname[10];KeyTypekey;}DataType;DataTyper[Max];

typedefstruct{KeyTypekey;intlink;}indextype;indextypeLr[m]索引表結(jié)構(gòu)：順序表結(jié)構(gòu)：表結(jié)構(gòu)說明：1/6/202323第7章查找typedefstructtypedefstruintindexsearch(indextypeLr[],DataTyper[],intkey,intL,intm){inti,j;i=0;//*在索引表中順序查找*//while(i<m&&Lr[i].key<key)i++;if(i>=m)return-1;else//*在順序表中順序查找*//{j=Lr[i].link;while(key!=r[j].key&&j-Lr[i].link<L)j++;if(key==r[j].key)returnj;elsereturn-1;}}索引表：Lr[0~m-1]順序表：r[]塊長度：L算法描述限制查找的范圍1/6/202324第7章查找intindexsearch(indextypeLr[]intindexsearch(indextypeLr[],DataTyper[],intkey,intL,intm){inti,j;i=0;//*在索引表中順序查找*//while(i<m&&Lr[i].key<key)i++;if(i>=m)return-1;else//*在順序表中順序查找*//{j=Lr[i].link;while(key!=r[j].key&&j-Lr[i].link<L)j++;if(key==r[j].key)returnj;elsereturn-1;}}演示:key=25L=4;M=32103344388…21…31…33…25…43…37…35…19…22…40…17…Lr[]Keylinkr[]i=0i=1j=4j=5j=61/6/202325第7章查找intindexsearch(indextypeLr[]索引表采用順序查找算法分析假設：長度為n的順序表分成m塊，每塊長度為L,ASLb=∑[(1/m)×i]=(m+1)/2i=1mASLw=∑[(1/L)×i]=(L+1)/2i=1L塊內(nèi)采用順序查找ASLblocks=(m+1)/2+(L+1)/21/6/202326第7章查找索引表采用順序查找算法分析假設：長度為n的順序表分成m塊，每

效率介于順序查找和折半查找之間線性表存儲結(jié)構(gòu)為索引存儲結(jié)構(gòu)算法特點索引表中采用折半查找ASLb=log2(m+1)-1ASLblocks=log2(m+1)-1+(L+1)/2ASLw=(L+1)/2總之：順序表結(jié)構(gòu)適用于查找操作，不適于做插入和刪除的操作。1/6/202327第7章查找效率介于順序查找和折半查找之間算法特點索引表中采用折半7.3.基于樹的查找用樹結(jié)構(gòu)存儲記錄既可查找又可插入和刪除1.樹表查找方法：二叉排序樹查找平衡二叉排序樹查找B-樹查找與折半查找類似，逐步縮小查找范圍。2.二叉排序樹查找1/6/202328第7章查找7.3.基于樹的查找用樹結(jié)構(gòu)存儲記錄既可查找又可插入和刪除(1)二叉排序樹的定義: 或是空樹,或具有以下性質(zhì)的二叉樹: ①其左子樹上所有結(jié)點的數(shù)據(jù)均小于根結(jié)點的數(shù)據(jù)值. ②其右子樹上所有結(jié)點的數(shù)據(jù)均大于或等于根結(jié)點的數(shù)據(jù)值.③左、右子樹又各是一棵二叉排序樹。 例：21181118201615101/6/202329第7章查找(1)二叉排序樹的定義:例：211811182016151（2）二叉排序樹的生成生成一棵二叉排序樹,過程如下:①若二叉排序樹為空，則令待插結(jié)點為根結(jié)點,

②若二叉排序樹非空，則比較待插結(jié)點(k1)和根結(jié)點(k2)的數(shù)據(jù)值。若k1<k2,則將其插入到左子樹中；否則，將其插入到右子樹中.

③結(jié)點插入二叉排序樹的左、右子樹過程同上.例:將序列{15,10,18,2,11,8,16,25,11}構(gòu)成一棵二叉排序樹,過程:15101821181625111/6/202330第7章查找（2）二叉排序樹的生成生成一棵二叉排序樹,過程如下:課堂練習:用以下序列組成一棵二叉排序樹.{23,4,12,89,9,43,4,56,23}4892312943562341/6/202331第7章查找課堂練習:用以下序列組成一棵二叉排序樹.4892312943typedefstructbsnode{KeyTypekey;structbsnode*L;structbsnode*R;}BiTree;二叉排序樹結(jié)點結(jié)構(gòu)C語言描述1/6/202332第7章查找typedefstructbsnode二叉排序樹結(jié)點結(jié)構(gòu)（3）二叉排序樹的生成算法BiTree*insertbt(BiTree*s,BiTree*t)/*將s所指的結(jié)點插入到t所指的二叉樹中*/{if(t==NULL)t=s;/*若t為空，則將s作為根*/elseif(s->key<t->key)t->L=insertbt(s,t->L);elset->R=insertbt(s,t->R);returnt;}1/6/202333第7章查找（3）二叉排序樹的生成算法BiTree*insertbt(①插入的新結(jié)點都是二叉排序樹的葉子結(jié) 點.不必移動其它結(jié)點.常用于有序二叉樹 的插入,刪除.②對二叉排序樹采用中序遍歷,其結(jié)果為一有序序列.③根結(jié)點的選擇,決定二叉樹的形狀,其形狀決定檢索的效率.根結(jié)點數(shù)據(jù)值最好選擇元素序列的中間值.特點:1/6/202334第7章查找①插入的新結(jié)點都是二叉排序樹的葉子結(jié) 點.不必移動其它BiTree*btsearch(BiTree*p,intkey)//p指向二叉排序樹的根結(jié)點{while(p!=NULL){if(key==p->key)returnp;elseif(key<p->key)p=p->L;elsep=p->R;}returnNULL;}算法描述：結(jié)束條件查找成功在左子樹中查找在右子樹中查找查找失敗3.二叉排序樹查找1/6/202335第7章查找BiTree*btsearch(BiTree*p,inBiTree*btsearch(BiTree*p,intkey)//p指向二叉排序樹的根結(jié)點{while(p!=NULL){if(key==p->key)returnp;elseif(key<p->key)p=p->L;elsep=p->R;}returnNULL;}1510182118162511pppp演示：Key=81/6/202336第7章查找BiTree*btsearch(BiTree*p,in4.算法分析ASL≈log2(n+1)-1二叉排序樹查找與折半法查找類似，與關(guān)鍵字比較的次數(shù)不會超過樹的深度。最好情況：二叉排序樹為一棵平衡二叉樹最壞情況：二叉排序樹為一棵單支樹，與順序查找情況相同。(n+1)/2適用于經(jīng)常做插入,刪除和查找運算的表.1/6/202337第7章查找4.算法分析ASL≈log2(n+1)-1二叉排序樹查找與7.4哈希查找（散列查找）前述的查找方法建立在“比較”的基礎上，查找的次數(shù)依賴于查找過程中進行比較的次數(shù)。問題：能否不用比較就能直接計算出記錄的存儲地址，從而找到所要的結(jié)點？----采用散列（hash）方法。1/6/202338第7章查找7.4哈希查找（散列查找）前述的查找方法建立在“比較”的基1.哈希(散列)表的基本概念哈希（又稱雜湊、散列）的基本思想：

以記錄的關(guān)鍵字值k為自變量，通過一定的函數(shù)關(guān)系h計算出對應的函數(shù)值h(k),把這個值解釋為記錄的存儲地址（哈希地址），將記錄存入該地址中去。函數(shù)h---哈希函數(shù)h(k)---哈希地址基本區(qū)---分配給哈希表的連續(xù)存儲空間。沖突的概念：若對于不同的鍵值k1和k2,即k1<>k2,但h(k1)=h(k2)，即具有相同的散列地址，稱為沖突。1/6/202339第7章查找1.哈希(散列)表的基本概念哈希（又稱雜湊、散列）的基本思想例：key={3,15,20,24}，m=5（連續(xù)內(nèi)存長度），h(k)=k%m，h(15)=h(20)，產(chǎn)生沖突。同義詞---發(fā)生沖突的兩個或多個鍵值。哈希(散列)表---是根據(jù)設定的哈希(散列)函數(shù)和相應解決沖突的方法為一組結(jié)點建立的一張表，表中的結(jié)點的存儲位置依賴于設定的哈希(散列)函數(shù)和處理沖突的方法。1/6/202340第7章查找例：key={3,15,20,24}，m=5（連續(xù)內(nèi)存長度）哈希(散列)表和查找哈希法主要包括以下兩方面的內(nèi)容：（1）如何選擇一個好的哈希(散列)函數(shù)？要考慮：哈希(散列)函數(shù)簡單；將鍵值均勻地分布在整個地址空間，使沖突機會盡量少。（2）如何解決沖突?選定一個解決沖突的辦法（即如何存儲沖突的同義詞）。下面分別介紹：

假設:有n個數(shù)據(jù)元素,存放在m個內(nèi)存單元.通常m>n。1/6/202341第7章查找哈希(散列)表和查找哈希法主要包括以下兩方面的內(nèi)容：1/6/2.幾種常用的哈希函數(shù)（1）直接定址法：

當關(guān)鍵字是整型數(shù)時，取關(guān)鍵字作為哈希地址。H(k)=k或H(k)=ak+b（a，b為常數(shù)）特點：簡單；浪費空間；例：一組關(guān)鍵碼：{942148,941269,940527,941630,941805,941558,942047,940001}。散列函數(shù)為

H(k)=k

-940000

則有H(942148)=2148H(941269)=1269H(940527)=527H(941630)=1630H(941805)=1805H(941558)=1558H(942047)=2047H(940001)=11/6/202342第7章查找2.幾種常用的哈希函數(shù)（1）直接定址法：例：一組關(guān)鍵碼：{（2）除留余數(shù)法：

選擇一個適當?shù)恼麛?shù)P，用P去除鍵值，取其余數(shù)作為散列地址，即：h(k)=k%PP的取法：小于等于哈希表表長m的最大素數(shù).例如，已知待散列元素為（18,75，60，43，54，90，46），表長m=10，p=7，則有H(18)=18%7=4H(75)=75%7=5H(60)=60%7=4H(43)=43%7=1H(54)=54%7=5H(90)=90%7=6H(46)=4沖突較多。為減少沖突，可取較大的m值和p值，如:m=p=13，結(jié)果如下：1/6/202343第7章查找（2）除留余數(shù)法：1/6/202343第7章查找H(18)=18%13=5H(75)=75%13=10H(60)=60%13=8H(43)=43%13=4H(54)=54%13=2H(90)=90%13=12H(46)=46%13=7P最好取1.1n~1.7n的素數(shù)。例：設n=7，P=11或13則：n=100P=113,127,1395443184660759001234567891011121/6/202344第7章查找H(18)=18%13=5H(75)=75%13=1（3）數(shù)字分析法設有n個d位數(shù)，每一位可能有r種不同的符號。這r種不同的符號在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布均勻些；在某些位上分布不均勻，只有某幾種符號經(jīng)常出現(xiàn)?？筛鶕?jù)散列表的大小，選取其中各種符號分布均勻的若干位作為散列地址。計算各位數(shù)字中符號分布的均勻度k的公式：其中，αik表示第i個符號在第k位上出現(xiàn)的次數(shù)，n/r表示各種符號在n個數(shù)中均勻出現(xiàn)的期望值。計算出的k值越小，表明在該位(第k位)各種符號分布得越均勻。1/6/202345第7章查找（3）數(shù)字分析法1/6/202345第7章查找例:942148 ①位，1=510.60941269 ②位，2=510.60940527 ③位，3=110.60941630 ④位，4=110.60941805 ⑤位，5=110.60941558 ⑥位，6=110.60942047 940001①②③④⑤⑥

數(shù)字分析法僅適用于事先明確知道表中所有關(guān)鍵碼每一位數(shù)值的分布情況，它完全依賴于關(guān)鍵碼集合。如果換一個關(guān)鍵碼集合，選擇哪幾位要重新決定。若散列表地址范圍有3位數(shù)字,取各關(guān)鍵碼的④⑤⑥位做為記錄的散列地址。也可以把第①，②，③和第⑤位相加，舍去進位位，變成一位數(shù)，與第④，⑥位合起來作為散列地址。還有其它方法。1/6/202346第7章查找例:942148 ①位，（4）折疊法此方法把關(guān)鍵碼自左到右分成位數(shù)相等的幾部分，每一部分的位數(shù)應與散列表地址位數(shù)相同，只有最后一部分的位數(shù)可以短一些。把這些部分的數(shù)據(jù)疊加起來，就可以得到具有該關(guān)鍵碼的記錄的散列地址。兩種疊加方法：

移位法—把各部分的最后一位對齊相加；

分段折疊法—各部分不折斷，沿各部分的分界來回折疊，然后對齊相加，將相加的結(jié)果當做散列地址。例：設給定的關(guān)鍵碼為key=23938587841，若存儲空間限定3位,則劃分結(jié)果為每段3位.上述關(guān)鍵碼可劃分為4段：

239

385

878

411/6/202347第7章查找（4）折疊法1/6/202347第7章查找把超出地址位數(shù)的最高位刪去,僅保留最低的3位，做為可用的散列地址。239

385

878

41分段折疊1/6/202348第7章查找把超出地址位數(shù)的最高位刪去,僅保留最低的3位，做為可用的散（5）平方取中法此方法在詞典處理中使用十分廣泛。它先計算構(gòu)成關(guān)鍵碼的標識符的內(nèi)碼的平方，然后按照散列表的大小取中間的若干位作為散列地址。設標識符可以用一個計算機字長的內(nèi)碼表示。因為內(nèi)碼平方數(shù)的中間幾位一般是由標識符所有字符決定，所以對不同的標識符計算出的散列地址大多不相同，即使其中有些字符相同。當無法確定關(guān)鍵字中哪幾位分布較均勻時，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因為：平方后中間幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會以較高的概率產(chǎn)生不同的哈希地址。1/6/202349第7章查找（5）平方取中法此方法在詞典處理中使用十分廣泛。它先計算構(gòu)成例如：下列八進制數(shù)的關(guān)鍵字及其哈希地址關(guān)鍵字(關(guān)鍵字)2哈希地址010000100000101100121000021012001440000440116013704003702061431054131020624314704314216147347417342162474130474121634745651745…1/6/202350第7章查找例如：下列八進制數(shù)的關(guān)鍵字及其哈希地址關(guān)鍵字(關(guān)鍵字)2哈希(6).偽隨機數(shù)法采用一個偽隨機函數(shù)作哈希函數(shù)，即H(key)=random(key)。在實際應用中，應根據(jù)具體情況，靈活采用不同的方法。通常應考慮以下五個因素：計算哈希函數(shù)所需的時間（簡單）。關(guān)鍵字的長度。哈希表的大小。關(guān)鍵字的分布情況。記錄查找的頻率。1/6/202351第7章查找(6).偽隨機數(shù)法1/6/202351第7章查找3.哈希沖突解決方法四種處理沖突的基本方法：鏈地址法(鏈表法)、開放定址法(再散列)再哈希法、建立公共溢出區(qū)（1）鏈地址法：基本思想:將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中.查找、插入和刪除主要在同義詞鏈中進行。因此鏈地址法適用于經(jīng)常進行插入和刪除的情況。1/6/202352第7章查找3.哈希沖突解決方法四種處理沖突的基本方法：1/6/2023例：已知一組關(guān)鍵字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表長度為13，哈希函數(shù)為：H（key）=key%13，則用鏈地址法處理沖突的結(jié)果如圖所示。鏈地址法示例本例的平均查找長度：ASL=(1×7+2×4+3×1)=1.51/6/202353第7章查找例：已知一組關(guān)鍵字（32，40，36，53，16，4（2）開放定址法基本思想：當關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突，再以p1為基礎，產(chǎn)生另一個哈希地址p2，……，直到找出一個不沖突的哈希地址pi，將相應元素存入其中。這種方法有一個通用的再散列函數(shù)形式：Hi(k)=(H(k)+di)%m(i=1,2,…,k(km-1))或:hi=(h0+di)%mm:表長di:每次探測時的地址增量1/6/202354第7章查找（2）開放定址法基本思想：當關(guān)鍵字key的哈希地址p=H（di不同取值：(1)di=1,2,3,…線性探測再散列(2)di=12,-12,22,-22,…二次探測再散列(3)di=20,21,22,23,…平方探測再散列(3)di=偽隨機序列偽隨機探測再散列例如:3,9,33,551/6/202355第7章查找di不同取值：1/6/202355第7章查找

分類：線性探測再散列法、平方探測再散列法、二次探測再散列法、偽隨機探測再散列。例：記錄集合：{R1,R2,R3,…,R8},m=10,它們的哈希地址為：H(k1)=2,H(k2)=2,H(k3)=3,H(k4)=3,H(k5)=8,H(k6)=0,H(k7)=7,H(k8)=9,用線性探測再散列和二次探測再散列法構(gòu)造哈希表1/6/202356第7章查找分類：1/6/202356第7章查找H(k1)=2,H(k2)=2,H(k3)=3,H(k4)=3,H(k5)=8,H(k6)=0,H(k7)=7,H(k8)=9,線性探測法0123456789R1R2R3R4R5R6R7R8二次探測再散列法0123456789R1R2R3R4R5R6R7R8R2(2+12)MODmR3(3+12)MODmR4(3+12)MODmR4(3-12)MODmR4(3+22)MODmR7(7+12)MODmR7(7-12)MODm1/6/202357第7章查找H(k1)=2,H(k2)=2,H(k3)=3,H(k練習H(k1)=2,H(k2)=2,H(k3)=3,H(k4)=2,H(k5)=8,H(k6)=0,H(k7)=7,H(k8)=9,平方探測再散列法0123456789R1R2R3R4R5R6R7R81/6/202358第7章查找練習H(k1)=2,H(k2)=2,H(k3)=3,H（3）再哈希法：這種方法是同時構(gòu)造多個不同的哈希函數(shù)Hi=RHi（key），i=1，2，…，k當哈希地址H1=RH1（key）發(fā)生沖突時，再計算H2=RH2（key）……直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計算時間。1/6/202359第7章查找（3）再哈希法：這種方法是同時構(gòu)造多個不同的哈希函數(shù)（4）.建立公共溢出表基本思想:將哈希表分為基本表A[m]和溢出表O[v]兩部分，凡是與基本表發(fā)生沖突的元素一律填入溢出表。

1/6/202360第7章查找（4）.建立公共溢出表基本思想:1/6/202360第7章4.哈希表的查找方法：計算哈希函數(shù)，得出哈希地址H(ki)若R(H(ki))=NULLKEY則：查找失敗，退出；否則，進入3）R(H(ki)).key=key?,相等，則查找成功，退出；否則，進入4）不相等，用解決沖突的方法，繼續(xù)查找(1)用解決沖突的方法,找出下一個哈希地址pi，(2)如果單元pi為空，則所查元素不存在；(3)如果單元pi中元素的關(guān)鍵字為K，則找到所查元素。1/6/202361第7章查找4.哈希表的查找方法：1/6/202361第7章查找例：哈希表如下：解決沖突方法：線性探測法0123456789R1R2R3R4R5R6R7R8查找R4.keyH(k4)=3R4.keyR2.keyR4.keyR3.key查找成功1/6/202362第7章查找例：哈希表如下：解決沖突方法：線性探測法0R1R2R3R4RintHashSearch(HashTableht,KeyTypeK){intp0;p0=hash(K);if(ht［p0］.key==NULLKEY)return(-1);elseif(ht［p0］.key==K)return(p0);else/*用線性探測再散列解決沖突*/{for(i=1;i<=m-1;i++){pi=(p0+i)%m;if(ht［pi］.key==NULLKEY)return(-1);elseif(ht［pi］.key==K)return(pi);}return(-1);}}＃definem<哈希表長度>＃defineNULLKEY<代表空記錄的關(guān)鍵字值>typedefintKeyType;typedefstruct{KeyTypekey;…}RecordType;typedefRecordTypeHashTable［m］;1/6/202363第7章查找intHashSearch(HashTableht5.哈希法性能分析

由于沖突的存在，哈希法仍需進行關(guān)鍵字比較，因此仍需用平均查找長度來評價哈希法的查找性能。哈希法中影響關(guān)鍵字比較次數(shù)的因素有三個：哈希函數(shù)、處理沖突的方法以及哈希表的裝填因子。哈希表的裝填因子α的定義如下：α=哈希表中元素個數(shù)

哈希表的長度

1/6/202364第7章查找5.哈希法性能分析由于沖突的存在，哈希法仍需進■線性探測再散列

查找成功時

查找失敗時

■偽隨機探測再散列、二次探測

查找成功時

查找失敗時

1/6/202365第7章查找■線性探測再散列查找成功時查找失敗時■偽隨機探測再散■鏈址法查找成功時查找失敗時

從以上討論可知：哈希表的平均查找長度是裝填因子α的函數(shù)，而與待散列元素數(shù)目n無關(guān)。因此，論元素數(shù)目n有多大，都能通過調(diào)整α，使哈希表的平均查找長度較小。1/6/202366第7章查找■鏈址法從以上討論總結(jié)：概念：關(guān)鍵字，平均查找長度算法及算法評價：順序查找（原理及算法）折半查找（原理及算法）分塊查找（原理）二叉排序樹查找（原理及算法）哈希查找（原理）作業(yè)：P2951，3,4，5(1,2)，12(1)1/6/202367第7章查找總結(jié)：概念：1/6/202367第7章查找第7章查找(Search)

7.1查找基本概念7.2基于線性表靜態(tài)查找7.3基于樹表動態(tài)查找7.4哈希查找1/6/202368第7章查找第7章查找(Search)7.1查找基本概念1/6Introduction查找是非數(shù)值處理中一種最基本、最重要的操作。查找，也稱檢索，是一種運算，是軟件設計中經(jīng)常遇到的一種運算。數(shù)據(jù)結(jié)構(gòu)不同，查找方法也會不同。查找方法的好壞直接影響著計算機的使用效率。查找概述1/6/202369第7章查找Introduction查找是非數(shù)值處理中一種最基本、最重要7.1、查找基本概念1）查找Search：又稱檢索，是指在大量的數(shù)據(jù)中尋找關(guān)鍵字等于給定值的記錄。若存在這樣一個記錄，則稱查找成功，否則稱查找不成功。分為:靜態(tài)查找;動態(tài)查找;2）關(guān)鍵字(Keyword)：就是數(shù)據(jù)元素中可以唯一標識一個數(shù)據(jù)元素的數(shù)據(jù)項。例如：學生管理登記卡中的學號。3）平均查找長度(AverageSearchLength)(ASL)

算法評價:評價時考慮：（1）速度；（2）占用存儲空間；（3）復雜程度。1/6/202370第7章查找7.1、查找基本概念1）查找Search：又稱檢索，是指在

引入平均查找長度，作為查找算法評價的依據(jù)。平均查找長度：為確定記錄在表中的位置所進行的和關(guān)鍵字比較的次數(shù)的期望值，簡寫為ASL.含有n個元素的表中找一個元素成功的ASL為：Pi為查找第i個元素的概率；Ci為查到第i個元素所需的比較次數(shù)。

ASL=∑Pi×Cii=1n1/6/202371第7章查找引入平均查找長度，作為查找算法評價的依據(jù)。含有n個元素結(jié)構(gòu)體數(shù)組

typedefstruct{charname[10];KeyTypekey;}DataType;DataTyper[Maxnum];name[0]…name[9]keyr[0]r[1]………r[Maxnum]name[0]…name[9]key設表中記錄以順序存儲結(jié)構(gòu)組織。每個記錄包括：關(guān)鍵字，其他數(shù)據(jù)項等。其類型說明用C語言描述如下：4)類型說明：1/6/202372第7章查找結(jié)構(gòu)體數(shù)組name[0]…name[9]keyr[0]r[1

5）查找方法:

順序表靜態(tài)查找，樹表動態(tài)查找，哈希查找7.2、基于線性表的靜態(tài)查找順序表上的查找主要有三種方法:順序查找法:針對順序表存儲結(jié)構(gòu)折半查找法:針對有序順序表存儲結(jié)構(gòu)分塊查找:針對索引順序表存儲結(jié)構(gòu)

1/6/202373第7章查找5）查找方法:

順序表靜態(tài)查找，樹表動態(tài)查i=01826322137566475i=1i=5i=4i=3i=2基本思想：從第一個元素開始，將給定值與表中逐個元素的關(guān)鍵字比較，直至檢索成功或直至最后一個元素檢索失敗為止。1.順序查找：1/6/202374第7章查找i=01826322137566475i=1i=5i=4i=intSeqsearch(DataTyper[],intkey,intn){inti=0;while(r[i].key!=key&&i<n)i++;if(r[i].key==key)returni;elsereturn-1;}順序查找算法：i=01826322137566475i=1i=5i=4i=3i=2演示：查找key=561/6/202375第7章查找intSeqsearch(DataTyper[],算法分析：ASL=∑Pi×Ci=1/n(1+2+……..+n)*2=n+1i=1n表從r[1]-r[Max],r[0]存放key。改進算法：希望盡量減少比較次數(shù)。1/6/202376第7章查找算法分析：ASL=∑Pi×Cii=1n表從r[1]-r32intseqsearch(DataTyper[],intkey,intn){inti;r[0].key=key;i=n;while(r[i].key!=key)i--;returni;}算法描述i=81826322137566475i=7i=6i=5i=4i=3012345678演示：查找key=321/6/202377第7章查找32intseqsearch(DataTyper[],算法分析算法簡單，效率較低算法特點ASL=∑Pi×Ci=(1/n)×(1+2+……..+n)=(n+1)/2i=1n1/6/202378第7章查找算法分析算法簡單，效率較低算法特點ASL=∑Pi×Ci2.折半查找法（對半或二分查找）

針對有序表使用的查找方法，是簡單有效的方法。有序表：記錄的關(guān)鍵字以遞增（或遞減）順序排列的表。基本思想：給定值key與中間位置的記錄的關(guān)鍵字比較，若相等則查找成功；若給定值大于中間位置記錄的關(guān)鍵字值，則在表的后半部分繼續(xù)折半查找；否則在表的前半部分進行折半查找，直至查找成功或不成功。1/6/202379第7章查找2.折半查找法（對半或二分查找）有序表：記錄的關(guān)鍵字以遞增（步驟：（1）計算中間位置mid=(low+high)/2取整。（2）key與R[mid].key比較若key=R[mid].key則查找成功；若key<R[mid].key,則high=mid-1,轉(zhuǎn)（3）。若key>R[mid].key,則low=mid+1,轉(zhuǎn)（3）。（3）若low≤high,則重復（1）否則：查找不成功，結(jié)束。

1/6/202380第7章查找步驟：1/6/202313第7章查找Searchlow1826324552668091highmid52668091

lowhighmid8091highLowmid用折半查找法在順序表中查找關(guān)鍵字為80的記錄！1/6/202381第7章查找Searchlow1826324552668091highmlow1826324552668091highmid

lowhighmidhighLowmid18263245526680911826324552668091

low1826324552668091high查找關(guān)鍵字為10的記錄！注意：使用折半查找算法時，線性表中的元素必須按照關(guān)鍵字排列有序；并且必須以順序存儲方式存儲。1/6/202382第7章查找low1826324552668091highmidintbinsearch(DataTyper[],intn,intkey){intlow,high,mid;low=0;high=n-1;while(low<=high){mid=(low+high)/2;if(key==r[mid].key)returnmid;elseif(key>r[mid].key)low=mid+1;elsehigh=mid-1;}returu–1;}算法描述初始化循環(huán)條件計算中間下標查找成功前半部分后半部分查找失敗1/6/202383第7章查找intbinsearch(DataTyper[],intintbinsearch(DataTyper[],intn,intkey){intlow,high,mid;low=0;high=n-1;while(low<=high){mid=(low+high)/2;if(key==r[mid].key)returnmid;elseif(key>r[mid].key)low=mid+1;elsehigh=mid-1;}returu–1;}low1826324552668091highmid52668091lowhighmid8091highLowmid用折半查找法在順序表中查找關(guān)鍵字為80的記錄！1/6/202384第7章查找intbinsearch(DataTyper[],int假設：查找關(guān)鍵字為0-6的數(shù)據(jù)折半法算法分析3564102二叉判定樹假設：有序表長度為n,且n≤2h-1若n=2h-1則：查找過程為一棵深度為h的滿二叉樹,查找的過程形成二叉判定樹ASL=1/7(1+2×2+4×3)=2.431/6/202385第7章查找假設：查找關(guān)鍵字為0-6的數(shù)據(jù)折半法算法分析3564102二比順序查找效率高只適用于有序的順序存儲的表，算法特點:ASL≈log2(n+1)-1ASL=∑[(1/n)×2i-1×i]i=1n則滿二叉樹的第i層有2i-1個結(jié)點。1/6/202386第7章查找比順序查找效率高算法特點:ASL≈log2(n+1)-1AS3.分塊查找（索引順序表查找）

將順序查找法與折半查找法結(jié)合

基本思想：使用分塊查找算法時，要求將線性表均勻地分成若干塊，每塊的元素不要求有序，但一定要保證塊間有序。另外，對表要進行索引存儲。即新建一個索引表，存放各塊中最大關(guān)鍵字。分塊查找實際上是先在索引表中進行順序查找或折半查找，再在塊內(nèi)進行順序查找。1/6/202387第7章查找3.分塊查找（索引順序表查找）將順序查找法與折半查找法結(jié)索引表類型:1.對單關(guān)鍵字建立索引表:2.對多關(guān)鍵字建立索引表:完全索引表,多級索引表.3.分塊個數(shù)建立索引表:等長,不等長主表索引表主表完全索引表索引表分塊查找的基本過程如下：(1)首先，將待查關(guān)鍵字K與索引表中的關(guān)鍵字進行比較，以確定待查記錄所在的塊。具體的可用順序查找法或折半查找法進行。(2)進一步用順序查找法，在相應塊內(nèi)查找關(guān)鍵字為K的元素。1/6/202388第7章查找索引表類型:1.對單關(guān)鍵字建立索引表:主表索引表主表完全索引

例如：{17，8，21，19，31，33，25，22，43，37，35,40，61，78，73，55}分塊[17，8，21，19]，[31，33，25，22]，[43，37，35，40],[61，73，78，55]索引表：2133437821334378關(guān)鍵字地址數(shù)據(jù)表8…21…31…33…25…43…61…37…35…73…78…19…22…40…55…17…1/6/202389第7章查找例如：{17，8，21，19，31，33，25，22，

typedefstruct{charname[10];KeyTypekey;}DataType;DataTyper[Max];

typedefstruct{KeyTypekey;intlink;}indextype;indextypeLr[m]索引表結(jié)構(gòu)：順序表結(jié)構(gòu)：表結(jié)構(gòu)說明：1/6/202390第7章查找typedefstructtypedefstruintindexsearch(indextypeLr[],DataTyper[],intkey,intL,intm){inti,j;i=0;//*在索引表中順序查找*//while(i<m&&Lr[i].key<key)i++;if(i>=m)return-1;else//*在順序表中順序查找*//{j=Lr[i].link;while(key!=r[j].key&&j-Lr[i].link<L)j++;if(key==r[j].key)returnj;elsereturn-1;}}索引表：Lr[0~m-1]順序表：r[]塊長度：L算法描述限制查找的范圍1/6/202391第7章查找intindexsearch(indextypeLr[]intindexsearch(indextypeLr[],DataTyper[],intkey,intL,intm){inti,j;i=0;//*在索引表中順序查找*//while(i<m&&Lr[i].key<key)i++;if(i>=m)return-1;else//*在順序表中順序查找*//{j=Lr[i].link;while(key!=r[j].key&&j-Lr[i].link<L)j++;if(key==r[j].key)returnj;elsereturn-1;}}演示:key=25L=4;M=32103344388…21…31…33…25…43…37…35…19…22…40…17…Lr[]Keylinkr[]i=0i=1j=4j=5j=61/6/202392第7章查找intindexsearch(indextypeLr[]索引表采用順序查找算法分析假設：長度為n的順序表分成m塊，每塊長度為L,ASLb=∑[(1/m)×i]=(m+1)/2i=1mASLw=∑[(1/L)×i]=(L+1)/2i=1L塊內(nèi)采用順序查找ASLblocks=(m+1)/2+(L+1)/21/6/202393第7章查找索引表采用順序查找算法分析假設：長度為n的順序表分成m塊，每

效率介于順序查找和折半查找之間線性表存儲結(jié)構(gòu)為索引存儲結(jié)構(gòu)算法特點索引表中采用折半查找ASLb=log2(m+1)-1ASLblocks=log2(m+1)-1+(L+1)/2ASLw=(L+1)/2總之：順序表結(jié)構(gòu)適用于查找操作，不適于做插入和刪除的操作。1/6/202394第7章查找效率介于順序查找和折半查找之間算法特點索引表中采用折半7.3.基于樹的查找用樹結(jié)構(gòu)存儲記錄既可查找又可插入和刪除1.樹表查找方法：二叉排序樹查找平衡二叉排序樹查找B-樹查找與折半查找類似，逐步縮小查找范圍。2.二叉排序樹查找1/6/202395第7章查找7.3.基于樹的查找用樹結(jié)構(gòu)存儲記錄既可查找又可插入和刪除(1)二叉排序樹的定義: 或是空樹,或具有以下性質(zhì)的二叉樹: ①其左子樹上所有結(jié)點的數(shù)據(jù)均小于根結(jié)點的數(shù)據(jù)值. ②其右子樹上所有結(jié)點的數(shù)據(jù)均大于或等于根結(jié)點的數(shù)據(jù)值.③左、右子樹又各是一棵二叉排序樹。 例：21181118201615101/6/202396第7章查找(1)二叉排序樹的定義:例：211811182016151（2）二叉排序樹的生成生成一棵二叉排序樹,過程如下:①若二叉排序樹為空，則令待插結(jié)點為根結(jié)點,

②若二叉排序樹非空，則比較待插結(jié)點(k1)和根結(jié)點(k2)的數(shù)據(jù)值。若k1<k2,則將其插入到左子樹中；否則，將其插入到右子樹中.

③結(jié)點插入二叉排序樹的左、右子樹過程同上.例:將序列{15,10,18,2,11,8,16,25,11}構(gòu)成一棵二叉排序樹,過程:15101821181625111/6/202397第7章查找（2）二叉排序樹的生成生成一棵二叉排序樹,過程如下:課堂練習:用以下序列組成一棵二叉排序樹.{23,4,12,89,9,43,4,56,23}4892312943562341/6/202398第7章查找課堂練習:用以下序列組成一棵二叉排序樹.4892312943typedefstructbsnode{KeyTypekey;structbsnode*L;structbsnode*R;}BiTree;二叉排序樹結(jié)點結(jié)構(gòu)C語言描述1/6/202399第7章查找typedefstructbsnode二叉排序樹結(jié)點結(jié)構(gòu)（3）二叉排序樹的生成算法BiTree*insertbt(BiTree*s,BiTree*t)/*將s所指的結(jié)點插入到t所指的二叉樹中*/{if(t==NULL)t=s;/*若t為空，則將s作為根*/elseif(s->key<t->key)t->L=insertbt(s,t->L);elset->R=insertbt(s,t->R);returnt;}1/6/2023100第7章查找（3）二叉排序樹的生成算法BiTree*insertbt(①插入的新結(jié)點都是二叉排序樹的葉子結(jié) 點.不必移動其它結(jié)點.常用于有序二叉樹 的插入,刪除.②對二叉排序樹采用中序遍歷,其結(jié)果為一有序序列.③根結(jié)點的選擇,決定二叉樹的形狀,其形狀決定檢索的效率.根結(jié)點數(shù)據(jù)值最好選擇元素序列的中間值.特點:1/6/2023101第7章查找①插入的新結(jié)點都是二叉排序樹的葉子結(jié) 點.不必移動其它BiTree*btsearch(BiTree*p,intkey)//p指向二叉排序樹的根結(jié)點{while(p!=NULL){if(key==p->key)returnp;elseif(key<p->key)p=p->L;elsep=p->R;}returnNULL;}算法描述：結(jié)束條件查找成功在左子樹中查找在右子樹中查找查找失敗3.二叉排序樹查找1/6/2023102第7章查找BiTree*btsearch(BiTree*p,inBiTree*btsearch(BiTree*p,intkey)//p指向二叉排序樹的根結(jié)點{while(p!=NULL){if(key==p->key)returnp;elseif(key<p->key)p=p->L;elsep=p->R;}returnNULL;}1510182118162511pppp演示：Key=81/6/2023103第7章查找BiTree*btsearch(BiTree*p,in4.算法分析ASL≈log2(n+1)-1二叉排序樹查找與折半法查找類似，與關(guān)鍵字比較的次數(shù)不會超過樹的深度。最好情況：二叉排序樹為一棵平衡二叉樹最壞情況：二叉排序樹為一棵單支樹，與順序查找情況相同。(n+1)/2適用于經(jīng)常做插入,刪除和查找運算的表.1/6/2023104第7章查找4.算法分析ASL≈log2(n+1)-1二叉排序樹查找與7.4哈希查找（散列查找）前述的查找方法建立在“比較”的基礎上，查找的次數(shù)依賴于查找過程中進行比較的次數(shù)。問題：能否不用比較就能直接計算出記錄的存儲地址，從而找到所要的結(jié)點？----采用散列（hash）方法。1/6/2023105第7章查找7.4哈希查找（散列查找）前述的查找方法建立在“比較”的基1.哈希(散列)表的基本概念哈希（又稱雜湊、散列）的基本思想：

以記錄的關(guān)鍵字值k為自變量，通過一定的函