《c語言數(shù)據(jù)結(jié)構(gòu)查找算法大全.ppt》由會員分享，可在線閱讀，更多相關(guān)《c語言數(shù)據(jù)結(jié)構(gòu)查找算法大全.ppt（45頁珍藏版）》請在匯文網(wǎng)上搜索。

1、查 找19.1 9.1 基本概念基本概念查找是指從一組記錄集合中找出滿足給定條件的記錄。查找是指從一組記錄集合中找出滿足給定條件的記錄。查找表查找表 在討論查找時，通常假設(shè)被查找的對象是由一組在討論查找時，通常假設(shè)被查找的對象是由一組同一類型的記錄構(gòu)成的集合，稱這個集合為查找表。同一類型的記錄構(gòu)成的集合，稱這個集合為查找表。關(guān)鍵字關(guān)鍵字 是指記錄的某個數(shù)據(jù)項，用它可以標(biāo)識一個記錄。是指記錄的某個數(shù)據(jù)項，用它可以標(biāo)識一個記錄。若此關(guān)鍵字可以唯一地標(biāo)識一個記錄，則稱此關(guān)鍵字為若此關(guān)鍵字可以唯一地標(biāo)識一個記錄，則稱此關(guān)鍵字為主關(guān)鍵主關(guān)鍵字字；反之，把可以識別若干記錄的關(guān)鍵字稱為；反之，把可以識別若干

2、記錄的關(guān)鍵字稱為次關(guān)鍵字次關(guān)鍵字。查找查找 是指根據(jù)某個給定的值，在查找表中查找一個其是指根據(jù)某個給定的值，在查找表中查找一個其關(guān)鍵字值等于給定值的記錄。若表中存在這樣的一個記錄，則關(guān)鍵字值等于給定值的記錄。若表中存在這樣的一個記錄，則稱稱查找成功查找成功；若表中不存在關(guān)鍵字值等于給定值的記錄，則稱；若表中不存在關(guān)鍵字值等于給定值的記錄，則稱查找失敗查找失敗。2查找技術(shù)分為：1 靜態(tài)查找表技術(shù)順序查找、折半查找、索引順序查找 2 動態(tài)查找表技術(shù)二叉查找樹 3哈希表技術(shù)哈希表技術(shù)3在查找一個記錄時所做的主要操作是關(guān)鍵字的比較，在查找一個記錄時所做的主要操作是關(guān)鍵字的比較，所以通常所以通常把查找過

3、程中對關(guān)鍵字的平均比較次數(shù)作為衡量把查找過程中對關(guān)鍵字的平均比較次數(shù)作為衡量一個查找算法效率優(yōu)劣的標(biāo)準(zhǔn)一個查找算法效率優(yōu)劣的標(biāo)準(zhǔn)，并稱平均比較次數(shù)為，并稱平均比較次數(shù)為平均平均查找長度查找長度（Average Search LengthAverage Search Length）。平均查找長度的）。平均查找長度的定義為：定義為：ASL=ASL=其中，其中，n n為元素的個數(shù)；為元素的個數(shù)；c ci i是查找第是查找第i i 個記錄需進行個記錄需進行的比較次數(shù)；的比較次數(shù)；p pi i是查找第是查找第i i個記錄的概率，一般可認為查找個記錄的概率，一般可認為查找每個記錄的概率是相等的，即每個記錄

4、的概率是相等的，即p p1 1=p=p2 2=p=pn n=1/n=1/n。查找算法的衡量指標(biāo)查找算法的衡量指標(biāo)當(dāng)當(dāng)ASLASL不易計算時，使用不易計算時，使用最大查找長度最大查找長度MSLMSL來衡量算法。來衡量算法。4 9.2 9.2 靜態(tài)查找表靜態(tài)查找表 基于線性表的查找基于線性表的查找 此類此類查找主要有查找主要有順序查找順序查找、折半查找折半查找和和索引順序查找索引順序查找三種三種方法。為簡便起見，假設(shè)查找表中的方法。為簡便起見，假設(shè)查找表中的記錄記錄為為整型整型，記錄的關(guān)，記錄的關(guān)鍵字即為該整數(shù)，記錄的個數(shù)為鍵字即為該整數(shù)，記錄的個數(shù)為N N，存放在數(shù)組，存放在數(shù)組R R中。中。查

5、找表的查找表的C C語言定義如下：語言定義如下：#define N 100int RN+1;/*/*使用的地址空間使用的地址空間1.N*/1.N*/59.2.1順序查找順序查找基本思想：基本思想：從查找表的一端開始，逐個將記錄的關(guān)從查找表的一端開始，逐個將記錄的關(guān)鍵字值和給定值進行比較，如果某個記錄的關(guān)鍵字值和鍵字值和給定值進行比較，如果某個記錄的關(guān)鍵字值和給定值相等，則稱給定值相等，則稱查找成功查找成功；否則，說明查找表中不存；否則，說明查找表中不存在關(guān)鍵字值為給定值的記錄，則稱在關(guān)鍵字值為給定值的記錄，則稱查找失敗查找失敗。6順序查找算法如下順序查找算法如下:intseqsearch(in

6、tR,intk)/*/*元素存放在元素存放在R R的的1-N1-N處處*/*/*/*在查找表在查找表R R中查找關(guān)鍵字為中查找關(guān)鍵字為k k的記錄，查找成功，返回記錄在的記錄，查找成功，返回記錄在R R中的下中的下標(biāo)值，否則返回標(biāo)值，否則返回0*/0*/inti;R0=k;/*/*將將k k放入放入R0R0中中*/i=N;/*/*從最后一個元素開始查找從最后一個元素開始查找*/while(Ri!=k)/*R0/*R0用來控制循環(huán)退出，起用來控制循環(huán)退出，起“監(jiān)視哨監(jiān)視哨”的作用的作用*/i-;return(i);/*/*若若i i為為0 0，表示查找失敗，否則，表示查找失敗，否則RiRi為要找

7、的記錄為要找的記錄*/7順序查找算法性能分析順序查找算法性能分析:在順序查找中，在順序查找中，比較次數(shù)比較次數(shù)ci取決于所查記錄在表中的位置。如查找記錄取決于所查記錄在表中的位置。如查找記錄Rn時，僅需比較一次，而查找記錄時，僅需比較一次，而查找記錄R1時，則需比較時，則需比較n次。一般來說，查找次。一般來說，查找第第i個記錄的比較次數(shù)為個記錄的比較次數(shù)為ci=n-i+1，因此，查找成功的平均查找長度為：，因此，查找成功的平均查找長度為：在等概率情況下，即在等概率情況下，即pi=1/n時，查找成功的平均查找長度為（時，查找成功的平均查找長度為（n+1）/2。若關(guān)鍵字不在表中，則必須經(jīng)過若關(guān)鍵字

8、不在表中，則必須經(jīng)過n+1次比較后才能確定查找失敗。所以查找次比較后才能確定查找失敗。所以查找失敗的平均查找長度為失敗的平均查找長度為n+1。這個結(jié)果表明：。這個結(jié)果表明：順序查找的查找長度是與記錄順序查找的查找長度是與記錄的個數(shù)的個數(shù)n成正比的。成正比的。結(jié)論：順序查找的優(yōu)點是算法簡單，且對表的結(jié)構(gòu)沒有任何要求。它的缺點是查找效率低，因此，當(dāng)表中元素個數(shù)比較多時，不宜采用順序查找。ASL成功成功=pici=pi(n-i+1)8已知含有已知含有10個整數(shù)的查找表如下：（個整數(shù)的查找表如下：（9，13，15，7，45，32，56，89，60，36），從鍵盤上輸入一個整數(shù)，用順序查找的方法在查找表

9、中查找該整數(shù)。），從鍵盤上輸入一個整數(shù)，用順序查找的方法在查找表中查找該整數(shù)。若存在，輸出該元素的下標(biāo)值，否則，給出相應(yīng)的信息。若存在，輸出該元素的下標(biāo)值，否則，給出相應(yīng)的信息。程序如下程序如下:例例9-1#include#defineN10main()intx,p;intaN+1=0,9,13,15,7,45,32,56,89,60,36;scanf(%d,&x);p=seqsearch(a,x);/*調(diào)用順序查找算法調(diào)用順序查找算法*/if(p=0)printf(Thisnumberdoesnotexistinthisarray.n);elseprintf(a%d=%dn,p,x);9 9

10、.2.2 9.2.2 折半查找折半查找(二分查找二分查找)使用使用使用使用折半查找折半查找折半查找折半查找必須具備兩個必須具備兩個必須具備兩個必須具備兩個前提條件前提條件前提條件前提條件:（1 1 1 1）要求查找表中的記錄按關(guān)鍵字有序）要求查找表中的記錄按關(guān)鍵字有序）要求查找表中的記錄按關(guān)鍵字有序）要求查找表中的記錄按關(guān)鍵字有序(設(shè)設(shè)設(shè)設(shè),從小到大有序從小到大有序從小到大有序從小到大有序)（2 2 2 2）只能適用于順序存儲結(jié)構(gòu)）只能適用于順序存儲結(jié)構(gòu)）只能適用于順序存儲結(jié)構(gòu)）只能適用于順序存儲結(jié)構(gòu) 基本思想：基本思想：基本思想：基本思想：先取查找表的先取查找表的先取查找表的先取查找表的中間

11、位置中間位置中間位置中間位置的關(guān)鍵字值與給定關(guān)鍵字值作比較，若它們的關(guān)鍵字值與給定關(guān)鍵字值作比較，若它們的關(guān)鍵字值與給定關(guān)鍵字值作比較，若它們的關(guān)鍵字值與給定關(guān)鍵字值作比較，若它們的值相等，則查找成功；如果給定值比該記錄的關(guān)鍵字值大，說明要查的值相等，則查找成功；如果給定值比該記錄的關(guān)鍵字值大，說明要查的值相等，則查找成功；如果給定值比該記錄的關(guān)鍵字值大，說明要查的值相等，則查找成功；如果給定值比該記錄的關(guān)鍵字值大，說明要查找的記錄一定在查找表的后半部分，則在查找表的后半部分繼續(xù)使用折找的記錄一定在查找表的后半部分，則在查找表的后半部分繼續(xù)使用折找的記錄一定在查找表的后半部分，則在查找表的后半

12、部分繼續(xù)使用折找的記錄一定在查找表的后半部分，則在查找表的后半部分繼續(xù)使用折半查找；若給定值比該記錄的關(guān)鍵字值小，說明要查找的記錄一定在查半查找；若給定值比該記錄的關(guān)鍵字值小，說明要查找的記錄一定在查半查找；若給定值比該記錄的關(guān)鍵字值小，說明要查找的記錄一定在查半查找；若給定值比該記錄的關(guān)鍵字值小，說明要查找的記錄一定在查找表的前半部分，則在查找表的前半部分繼續(xù)使用折半查找。找表的前半部分，則在查找表的前半部分繼續(xù)使用折半查找。找表的前半部分，則在查找表的前半部分繼續(xù)使用折半查找。找表的前半部分，則在查找表的前半部分繼續(xù)使用折半查找。直到查直到查直到查直到查找成功，或者直到確定查找表中沒有待查

13、找的記錄為止，即查找失敗。找成功，或者直到確定查找表中沒有待查找的記錄為止，即查找失敗。找成功，或者直到確定查找表中沒有待查找的記錄為止，即查找失敗。找成功，或者直到確定查找表中沒有待查找的記錄為止，即查找失敗。10設(shè)有一個設(shè)有一個設(shè)有一個設(shè)有一個1111個記錄的有序表的關(guān)鍵字值如下：個記錄的有序表的關(guān)鍵字值如下：個記錄的有序表的關(guān)鍵字值如下：個記錄的有序表的關(guān)鍵字值如下：812263745566472818995812263745566472818995假設(shè)指針假設(shè)指針假設(shè)指針假設(shè)指針lowlow和和和和highhigh分別指示待查元素所在區(qū)間的下界和上界，指針分別指示待查元素所在區(qū)間的下界

14、和上界，指針分別指示待查元素所在區(qū)間的下界和上界，指針分別指示待查元素所在區(qū)間的下界和上界，指針midmid指示區(qū)間的中間位置。指示區(qū)間的中間位置。指示區(qū)間的中間位置。指示區(qū)間的中間位置。查找關(guān)鍵字值為查找關(guān)鍵字值為26的過程：的過程：812263745566472818995low(1)mid(6)high(11)取取mid位置的關(guān)鍵字值位置的關(guān)鍵字值56與與26作比較，顯然作比較，顯然2656，說明要查找的記錄在后，說明要查找的記錄在后半部分，待查區(qū)間變?yōu)榘氩糠?，待查區(qū)間變?yōu)?，11，low=mid+1=6+1=7，求得，求得mid=9。812263745566472818995lowmi

15、dhigh再取再取mid位置的關(guān)鍵字值位置的關(guān)鍵字值81與與75作比較，顯然作比較，顯然7564，low=mid+1=8，待查區(qū)間變?yōu)?，待查區(qū)間變?yōu)?，8，求得，求得mid=8。812263745566472818995low,mid,high顯然顯然7572，待查區(qū)間變?yōu)?，待查區(qū)間變?yōu)閘ow=mid+1=9，high=8，此時，此時highlow，說明查，說明查找表中沒有關(guān)鍵字值為找表中沒有關(guān)鍵字值為75的記錄，查找失敗。的記錄，查找失敗。12折半查找算法：折半查找算法：intbinsearch(intR,intk)intlow,high,mid,find=0;low=1;high=n;/*

16、置區(qū)間初值置區(qū)間初值*/while(lowRmid)low=mid+1;/*在后半?yún)^(qū)查找，修改在后半?yún)^(qū)查找，修改low*/elsehigh=mid-1;/*在前半?yún)^(qū)查找，修改在前半?yún)^(qū)查找，修改high*/if(find)return(mid);/*查找成功，返回找到的元素位置查找成功，返回找到的元素位置*/elsereturn(-1);/*查找失敗，返回查找失敗，返回-1*/13折半查找算法性能分析折半查找算法性能分析:在折半查找的過程中，每經(jīng)過一次比較，查找范圍都要縮小一半，所以在折半查找的過程中，每經(jīng)過一次比較，查找范圍都要縮小一半，所以折半查找的最大查找長度為折半查找的最大查找長度為MSL=log2n+1當(dāng)當(dāng)n足夠大時，可近似的表示為足夠大時，可近似的表示為log2(n)。可見在查找速度上，折半查找?？梢娫诓檎宜俣壬?，折半查找比順序查找速度要快的多，這是它的主要優(yōu)點。比順序查找速度要快的多，這是它的主要優(yōu)點。結(jié)論：折半查找要求查找表按關(guān)鍵字有序，而排序是一種很費時的運算；另外，折半查找要求表是順序存儲的，為保持表的有序性，在進行插入和刪除操作時，都必須移動大量記錄。因此，折半查找