第8章 -1 (查找的基本概念)

1、第第8章章 查找查找 8.1 查找的基本概念查找的基本概念1. 查找查找:也稱為檢索。也稱為檢索。如如:查找某人的地址、電話號碼等，都屬于查找范疇。查找某人的地址、電話號碼等，都屬于查找范疇。 查找是按關(guān)鍵字進行的查找是按關(guān)鍵字進行的: 關(guān)鍵字關(guān)鍵字(key):是數(shù)據(jù)元素是數(shù)據(jù)元素(或記錄或記錄)中某個數(shù)據(jù)項的值，用中某個數(shù)據(jù)項的值，用 它可以標(biāo)識它可以標(biāo)識(或識別或識別)一個數(shù)據(jù)元素。一個數(shù)據(jù)元素。 例如例如:描述一個考生的信息，可以包含：考號、姓名、性別、描述一個考生的信息，可以包含：考號、姓名、性別、 年齡、家庭住址、電話號碼、成績等關(guān)鍵字。年齡、家庭住址、電話號碼、成績等關(guān)鍵字。 有些

2、關(guān)鍵字不能唯一標(biāo)識一個數(shù)據(jù)元素，而有的關(guān)鍵字可以有些關(guān)鍵字不能唯一標(biāo)識一個數(shù)據(jù)元素，而有的關(guān)鍵字可以 唯一標(biāo)識一個數(shù)據(jù)元素。唯一標(biāo)識一個數(shù)據(jù)元素。 如如:考生信息中，姓名不能唯一標(biāo)識一個數(shù)據(jù)元素考生信息中，姓名不能唯一標(biāo)識一個數(shù)據(jù)元素(因有同名同因有同名同 姓的人姓的人)，而考號可以唯一標(biāo)識一個數(shù)據(jù)元素，而考號可以唯一標(biāo)識一個數(shù)據(jù)元素(每個考生考每個考生考 號是唯一的，不能相同號是唯一的，不能相同)。 能唯一標(biāo)識一個數(shù)據(jù)元素的關(guān)鍵字稱為主關(guān)鍵字，而其能唯一標(biāo)識一個數(shù)據(jù)元素的關(guān)鍵字稱為主關(guān)鍵字，而其 它關(guān)鍵字稱為輔助關(guān)鍵字或從關(guān)鍵字。它關(guān)鍵字稱為輔助關(guān)鍵字或從關(guān)鍵字。查找就是根據(jù)給定的值，在一個

3、表中查找出其關(guān)鍵字等于查找就是根據(jù)給定的值，在一個表中查找出其關(guān)鍵字等于 給定值的數(shù)據(jù)元素給定值的數(shù)據(jù)元素:若表中有這樣的元素，則稱查找是成功的若表中有這樣的元素，則稱查找是成功的: 查找的信息為給定整個數(shù)據(jù)元素的輸出或指出該元素在表查找的信息為給定整個數(shù)據(jù)元素的輸出或指出該元素在表 中的位置；中的位置；若表中不存在這樣的記錄，則稱查找是不成功的，或稱查若表中不存在這樣的記錄，則稱查找是不成功的，或稱查 找失敗，并可給出相應(yīng)的提示。找失敗，并可給出相應(yīng)的提示。2.采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來表示采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來表示 “表表”:即表中結(jié)點是按何種方

4、式組織的。即表中結(jié)點是按何種方式組織的。3.為了提高查找速度，經(jīng)常使用某些特殊的數(shù)據(jù)結(jié)構(gòu)來組織表。4.研究各種查找算法時，首先必須弄清這些算法所要求的數(shù)據(jù)結(jié)構(gòu)，特別是存儲結(jié)構(gòu)。5.查找有內(nèi)查找和外查找之分: 若整個查找過程全部在內(nèi)存進行，則稱這樣的查找為內(nèi)查找 若在查找過程中還需要訪問外存，則稱之為外查找。我們僅介紹內(nèi)查找。6. 將找到給定值與關(guān)鍵字的比較次數(shù)的平均值來作為衡量將找到給定值與關(guān)鍵字的比較次數(shù)的平均值來作為衡量 一個查找算法好壞的標(biāo)準(zhǔn)一個查找算法好壞的標(biāo)準(zhǔn): 對于一個含有對于一個含有n個元素的表，查找成功時的平均查找長個元素的表，查找成功時的平均查找長 度可表示為度可表示為ASL

5、= i為查找第為查找第i個元素的概率，且個元素的概率，且 =1。 一般情形下我們認(rèn)為查找每個元素的概率相等，一般情形下我們認(rèn)為查找每個元素的概率相等， i為查找第為查找第i個元素所用到的比較次數(shù)。個元素所用到的比較次數(shù)。 niiicp1niip182 線性表的查找線性表的查找8.2.1 順序查找順序查找1順序查找的基本思想順序查找的基本思想:從表的一端開始，順序掃描線性表，依次從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點將掃描到的結(jié)點 關(guān)鍵字和待找的值相比較關(guān)鍵字和待找的值相比較: 若相等，則查找成功，若相等，則查找成功， 若整個表掃描完畢，仍末找到關(guān)鍵字等于的元素，若整個表掃描完畢，仍

6、末找到關(guān)鍵字等于的元素， 則查找失敗。則查找失敗。順序查找既適用于順序表，也適用于鏈表順序查找既適用于順序表，也適用于鏈表: 順序表查找可從前往后掃描，也可從后往前掃描順序表查找可從前往后掃描，也可從后往前掃描 采用單鏈表，則只能從前往后掃描。采用單鏈表，則只能從前往后掃描。 另外，順序查找的表中元素可以是無序的。另外，順序查找的表中元素可以是無序的。2順序查找算法實現(xiàn)順序查找算法實現(xiàn):const int n=maxn /n為表的最大長度為表的最大長度struct node elemtype key; /key為關(guān)鍵字為關(guān)鍵字; int seqsearch (node Rn+1,elemtyp

7、e k) /在表中查找關(guān)鍵字值為的元素在表中查找關(guān)鍵字值為的元素 R0.key=k; int i=n; /從表尾開始向前掃描從表尾開始向前掃描 while(Ri.key!=k) i-; return i;函數(shù)中查找的范圍從函數(shù)中查找的范圍從n到到，為監(jiān)視哨，起兩個作用為監(jiān)視哨，起兩個作用: 為了省去判定為了省去判定 while循環(huán)中下標(biāo)越界的條件循環(huán)中下標(biāo)越界的條件i1，從而，從而 節(jié)省比較時間節(jié)省比較時間 保存要找值的副本，若查找時，遇到它，表示查找不保存要找值的副本，若查找時，遇到它，表示查找不 成功。成功。若算法中不設(shè)立監(jiān)視哨若算法中不設(shè)立監(jiān)視哨R0，程序花費的時間將會增，程序花費的時間

8、將會增 加，這時的算法可寫為下面形式。加，這時的算法可寫為下面形式。int seqsearch(node Rn+1，elemtype k) int i=n; while(Ri.key!=k)&(i=1) i-; return i; 3.順序查找性能分析順序查找性能分析:假設(shè)在每個位置查找的概率相等，即有假設(shè)在每個位置查找的概率相等，即有pi=1/n，由于，由于 查找是從后往前掃描，則有每個位置的查找比較次數(shù)查找是從后往前掃描，則有每個位置的查找比較次數(shù) Cn=1，Cn-1=2，C1=n，于是，查找成功的平均查，于是，查找成功的平均查 找找ASL= = = 時間復(fù)雜度為時間復(fù)雜度為O(n)。 這

9、就是說，查找成功的平均比這就是說，查找成功的平均比 較次數(shù)約為表長的一半。較次數(shù)約為表長的一半。若若k值不在表中，則必須進行值不在表中，則必須進行n+1次比較之后才能確次比較之后才能確 定查找失敗。定查找失敗。另處另處:當(dāng)當(dāng)n較大時，較大時，ASL值較大，查找的效率較低。值較大，查找的效率較低。niiicp1ninin11)1(21n順序查找的特點順序查找的特點: 算法簡單，對表結(jié)構(gòu)無任何要求算法簡單，對表結(jié)構(gòu)無任何要求: 無論是用向量還是用鏈表來存放結(jié)點，無論是用向量還是用鏈表來存放結(jié)點， 也無論結(jié)點之間是否按關(guān)鍵字有序或無也無論結(jié)點之間是否按關(guān)鍵字有序或無 序，它都同樣適用。序，它都同樣適

10、用。 順序查找的缺點順序查找的缺點: 查找效率低，當(dāng)查找效率低，當(dāng)n較大時，不宜采用順序較大時，不宜采用順序 查找查找，而必須尋求更好的查找方法。，而必須尋求更好的查找方法。 8.2.2二分查找二分查找1.二分查找的基本思想二分查找的基本思想:二分查找，也稱折半查找，它是一種高效率的查找方法。二分查找，也稱折半查找，它是一種高效率的查找方法。 二分查找有條件限制：二分查找有條件限制：要求表必須用向量作存貯結(jié)構(gòu)，且表中元素要求表必須用向量作存貯結(jié)構(gòu)，且表中元素 必須按關(guān)鍵字有序必須按關(guān)鍵字有序(升序或降序均可升序或降序均可)。假設(shè)表中元素為升序排列。假設(shè)表中元素為升序排列。 二分查找的基本思想是

11、：首先將待查值二分查找的基本思想是：首先將待查值K與有序表與有序表R1到到Rn的中點的中點 mid上的關(guān)鍵字上的關(guān)鍵字Rmid.key進行比較進行比較: a.若相等，則查找成功；若相等，則查找成功； b.否則，若否則，若Rmid.keyk ， 則在則在R1到到Rmid-1中繼續(xù)查找，若有中繼續(xù)查找，若有 Rmid.keyk ， 則在則在Rmid+1到到Rn中繼續(xù)查找。中繼續(xù)查找。每通過一次關(guān)鍵字的比較，區(qū)間的長度就縮小一半，區(qū)間的個數(shù)就增每通過一次關(guān)鍵字的比較，區(qū)間的長度就縮小一半，區(qū)間的個數(shù)就增 加一倍加一倍，如此不斷進行下去，直到找到關(guān)鍵字為，如此不斷進行下去，直到找到關(guān)鍵字為K的元素；若

12、當(dāng)前的的元素；若當(dāng)前的 查找區(qū)間為空查找區(qū)間為空(表示查找失敗表示查找失敗)。 從上述查找思想可知，每進行一次關(guān)鍵字比較，區(qū)間數(shù)從上述查找思想可知，每進行一次關(guān)鍵字比較，區(qū)間數(shù)目增加一倍，故稱為二分（區(qū)間一分為二），而區(qū)間長目增加一倍，故稱為二分（區(qū)間一分為二），而區(qū)間長度縮小一半，故也稱為折半（查找的范圍縮小一半）。度縮小一半，故也稱為折半（查找的范圍縮小一半）。2二分查找算法實現(xiàn)二分查找算法實現(xiàn)int binsearch (node Rn+1, elemtype k) int low=1, high=n; while (lowk) high=mid-1; /在左子區(qū)間中查找在左子區(qū)間中查找

13、 else low=mid+1; /在右子區(qū)間中查找在右子區(qū)間中查找 return 0; /查找失敗查找失敗 例 如 ， 假 設(shè) 給 定 有 序 表 中 關(guān) 鍵 字 為例 如 ， 假 設(shè) 給 定 有 序 表 中 關(guān) 鍵 字 為8,17,25,44,68,77,98,100,115,125，將，將查找查找K=17和和K=120的情況描述為圖的情況描述為圖8-1及圖及圖8-2形式。形式。 8 17 25 44 68 77 98 10 115 125 low high (a) 初始情形初始情形 8 17 25 44 68 44 98 100 115 125 low high mid (b) 經(jīng)過一次

14、比較后的情形經(jīng)過一次比較后的情形 8 17 25 44 68 77 98 100 115 125 (c ) 經(jīng)過二次比較后的情形 (Rmid.key=17) low mid high 圖 8-1 查找 K=17 的示意圖 (查找成功) 8 17 25 44 68 77 98 100 115 125 (a) 初始情形 low high 8 17 25 44 68 77 98 100 115 125 (b) 經(jīng)過一次比較后的情形 mid low high 8 17 25 44 68 77 98 100 115 125 (c) 經(jīng)過二次比較后的情形 mid low high 8 17 25 44 6

15、8 77 98 100 115 125 (d) 經(jīng)過三次比較后的情形 mid low high 17 25 44 77 98 100 115 125 high low mid (e) 經(jīng)過四次比較后的情形(high data = X; p-left=p-right=NULL; BST=p; else if (BST-data = X ) Insert ( BST - left,X); /在左子樹中扦入在左子樹中扦入 else Insert (BST-right,X); /在右子樹中扦入在右子樹中扦入（2）二叉排序樹的建立）二叉排序樹的建立只要反復(fù)調(diào)用二叉排序樹的扦入算法即可，算法描述只要反復(fù)調(diào)

16、用二叉排序樹的扦入算法即可，算法描述為：為： Btreenode *Creat (int n) /建立含有建立含有n個結(jié)點的二叉?zhèn)€結(jié)點的二叉排序樹排序樹 Btreenode *BST= NULL; for ( int i=1; ix; /輸入關(guān)鍵字序列輸入關(guān)鍵字序列 Insert ( BST,x); return BST ;例如，結(jié)定關(guān)鍵字序列例如，結(jié)定關(guān)鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹過程如圖，生成二叉排序樹過程如圖8-6所示。所示。（注：二叉排序樹與關(guān)鍵字排列順序有關(guān)，排列順序（注：二叉排序樹與關(guān)鍵字排列順序有關(guān)，排列順序不一樣，得到的二

17、叉排序樹也不一樣）不一樣，得到的二叉排序樹也不一樣） 79 62 79 68 62 79 68 62 79 90 88 68 62 79 90 (a) (b) (c) (d) (e) 88 68 62 79 90 89 89 17 88 68 62 79 90 17 5 88 68 62 79 90 89 (f) (g) (h) 89 17 5 88 68 62 79 90 100 89 17 5 88 68 62 79 90 100 120 圖 8-6 二叉排序樹的生成過程 (i) (j) 4二叉排序二叉排序 樹上的查找樹上的查找 （1）二叉排序）二叉排序 樹的查找思想樹的查找思想若二叉排樹

18、為空，則查找若二叉排樹為空，則查找 失敗，否則，先拿根結(jié)點值與失敗，否則，先拿根結(jié)點值與待查值進行比較，若相等，則查找成功，若根結(jié)點值大待查值進行比較，若相等，則查找成功，若根結(jié)點值大于待查值，則進入左子樹重復(fù)此步驟，否則，進入右子于待查值，則進入左子樹重復(fù)此步驟，否則，進入右子樹重復(fù)此步驟，若在查找過程中遇到二叉排序樹的葉子樹重復(fù)此步驟，若在查找過程中遇到二叉排序樹的葉子結(jié)點時，還沒有找到待找結(jié)點，則查找不成功。結(jié)點時，還沒有找到待找結(jié)點，則查找不成功。（2）二叉排序樹查找的算法實現(xiàn)）二叉排序樹查找的算法實現(xiàn)Btreenode * find( Btreenode *BST,elentype

19、x) /在以在以BST為根指針的二叉排隊為根指針的二叉排隊 樹中查找值為樹中查找值為x的結(jié)點的結(jié)點 if ( BST= =NULL) return NULL; /查找失敗查找失敗 else if (BST-data= =x) /查找成功查找成功 return BST; else if (BST-datax) /進入左子樹查找進入左子樹查找 return find ( BST-left,x); else /進入右子樹查找進入右子樹查找 return find (BST-right,x); 5二叉排序樹查找的性能分析二叉排序樹查找的性能分析在二叉排序樹查找中，成功的查找次數(shù)不會超過二叉樹的在二叉排

20、序樹查找中，成功的查找次數(shù)不會超過二叉樹的深度，而具有深度，而具有n個結(jié)點的二叉排序樹的深度，最好為個結(jié)點的二叉排序樹的深度，最好為log2n，最壞為最壞為n。因此，二叉排序樹查找的最好時間復(fù)雜度為。因此，二叉排序樹查找的最好時間復(fù)雜度為O(log2n)，最壞的時間復(fù)雜度為，最壞的時間復(fù)雜度為O(n)，一般情形下，其時一般情形下，其時間復(fù)雜度大致可看成間復(fù)雜度大致可看成O(log2n)，比順序查找效率要好，但，比順序查找效率要好，但比二分查找要差。比二分查找要差。 8.3.2平衡二叉樹查找平衡二叉樹查找1平衡二叉樹的概念平衡二叉樹的概念平衡二叉樹平衡二叉樹(balanced binary tr

21、ee)是由阿德爾森一維爾斯是由阿德爾森一維爾斯和蘭迪斯和蘭迪斯(Adelson-Velskii and Landis)于于1962年首先提出的，年首先提出的，所以又稱為所以又稱為AVL樹樹。若一棵二叉樹中每個結(jié)點的左、右子樹的深度之差的絕對值若一棵二叉樹中每個結(jié)點的左、右子樹的深度之差的絕對值不超過不超過1，則稱這樣的二叉樹為，則稱這樣的二叉樹為平衡二叉樹平衡二叉樹。將該結(jié)點的左子。將該結(jié)點的左子樹深度減去右子樹深度的值，稱為該結(jié)點的樹深度減去右子樹深度的值，稱為該結(jié)點的平衡因子平衡因子(balance factor)。也就是說，一。也就是說，一棵二叉排序樹中，所有結(jié)點的平衡因棵二叉排序樹中，

22、所有結(jié)點的平衡因子只能為子只能為0、1、-1時，則該二叉排序樹就是一棵平衡二叉樹，時，則該二叉排序樹就是一棵平衡二叉樹，否則就不是一棵平衡二叉樹否則就不是一棵平衡二叉樹。如圖。如圖8-8所示二叉排序樹，是一所示二叉排序樹，是一棵平衡二叉樹，而如圖棵平衡二叉樹，而如圖8-9所示二叉所示二叉 排序樹，就不是一棵平衡排序樹，就不是一棵平衡二叉樹。二叉樹。 5 2 3 4 16 7 圖 8-8 一棵平衡二叉樹 6 1 2 3 4 8 5 7 圖 8-9 一棵非平衡二叉樹 2.非平衡二叉樹的平衡處理非平衡二叉樹的平衡處理 若一棵二叉排序樹是平衡二叉樹，扦入某個結(jié)點后，可能會變?nèi)粢豢枚媾判驑涫瞧胶舛鏄?/p>

23、，扦入某個結(jié)點后，可能會變成非平衡二叉樹，這時，就可以對該二叉樹進行平衡處理，使成非平衡二叉樹，這時，就可以對該二叉樹進行平衡處理，使其變成一棵平衡二叉樹。其變成一棵平衡二叉樹。處理的原則應(yīng)該是處理與扦入點最近處理的原則應(yīng)該是處理與扦入點最近的、而平衡因子又比的、而平衡因子又比1大或比大或比-1小的結(jié)點小的結(jié)點。下面將分四種情況。下面將分四種情況討論平衡處理。討論平衡處理。 （1）LL型型 的處理的處理(左左型左左型)如圖如圖8-10所示，在所示，在C的左孩子的左孩子B上扦入一個左孩子結(jié)點上扦入一個左孩子結(jié)點A，使，使C的平衡因子由的平衡因子由1變成了變成了2，成為不平衡的二叉樹。這時的平衡處

24、，成為不平衡的二叉樹。這時的平衡處理為：理為：將將C順時針旋轉(zhuǎn)，成為順時針旋轉(zhuǎn)，成為B的右子樹，而原來的右子樹，而原來B的右子樹則的右子樹則變成變成A的左子樹，待扦入結(jié)點的左子樹，待扦入結(jié)點A作為作為B的左子樹的左子樹。(注：圖中結(jié)點注：圖中結(jié)點旁邊的數(shù)字表示該旁邊的數(shù)字表示該 結(jié)點的平衡因子結(jié)點的平衡因子) 平衡外理 1 A B C 0 2 C B A 0 0 0 圖 8-10 LL 型平衡外理 （2）RR型的處理型的處理(右右型右右型)如圖如圖8-12所示，在所示，在A的右孩子的右孩子B上扦入一個右孩子上扦入一個右孩子C，使，使A的的平衡因子由平衡因子由-1變成變成-2，成為不平衡的二叉排

25、序樹。這時的平，成為不平衡的二叉排序樹。這時的平衡處理為：衡處理為：將將A逆時針旋轉(zhuǎn)，成為逆時針旋轉(zhuǎn)，成為B的左子樹，而原來的左子樹，而原來B的的左子樹則變成左子樹則變成A的右子樹，待扦入結(jié)點的右子樹，待扦入結(jié)點C成為成為B的右子樹。的右子樹。 平衡處理 -1 C B A 0 -2 C B A 0 0 0 圖 8-12 RR 型平衡處理 （3）RL型的處理型的處理(右左型右左型)如如 圖圖8-13所示，在所示，在A的右孩子的右孩子C上扦入一個左孩子上扦入一個左孩子B，使，使A的平衡因子由的平衡因子由-1變成變成-2，成為不平衡的二叉排序樹。這時，成為不平衡的二叉排序樹。這時的平衡處理為：的平衡

26、處理為：將將B變到變到A與與C之間，使之成為之間，使之成為RR型，然型，然后按第后按第(3) 種情形種情形RR型處理。型處理。 R 旋轉(zhuǎn) C B A 0 0 0 圖 8-13 RL 型平衡處理 -1 -2 C B A B 0 1 -2 A L 旋轉(zhuǎn) C （4）LR型的處理型的處理(左右型左右型)如圖如圖8-11所示，在所示，在C的左孩子的左孩子A上扦入一個右孩子上扦入一個右孩子B，使的使的C的平衡因子由的平衡因子由1變成了變成了2，成為不平衡的二叉排序，成為不平衡的二叉排序樹。這是的平衡處理為：樹。這是的平衡處理為：將將B變到變到A與與C 之間，使之成之間，使之成為為LL型，然后按第型，然后按

27、第(1)種情形種情形LL型處理型處理。 0 -1 C A B 2 0 1 C A B 2 B 0 0 C A 0 L 旋轉(zhuǎn) R 旋轉(zhuǎn) 圖 8-11 LR 型平衡處理 例例8-2，給定一個關(guān)鍵字序列，給定一個關(guān)鍵字序列4,5,7,2 ,1,3,6，試生成一棵平衡，試生成一棵平衡二叉樹。二叉樹。分析：平衡二叉樹實際上也是一棵二叉排序樹，故可以按建分析：平衡二叉樹實際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進行相應(yīng)平衡處理，最后就可以建成一棵平衡二叉樹。具則進行相應(yīng)平衡處理，最后就可以建成一棵平衡二

28、叉樹。具體生成過程見圖體生成過程見圖8-14。 (a)插入 4 (b)插入 5 (c)插入 7 RR 型 4 0 4 5 0 -1 7 4 5 -2 -1 0 0 0 4 5 7 0 LL 型 (d)插入 2 (e)插入 1 4 2 5 7 1 0 0 0 0 0 4 2 5 7 1 0 0 1 2 2 4 2 5 7 0 0 1 1 -1 5 2 1 4 3 7 2 0 1 0 0 5 2 1 4 3 7 -1 0 0 0 0 0 LR 型 (f)插入 3 5 2 1 4 3 7 -2 -1 0 1 0 0 6 0 RL 型 0 6 2 1 4 3 7 0 0 0 0 0 5 0 (g) 插

29、入 6 圖 8-14 平衡二叉樹的生成過程 3平衡二叉樹的查找及性能分析平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹，性能優(yōu)于二叉排序樹，不會出現(xiàn)最壞的時間復(fù)雜度不會出現(xiàn)最壞的時間復(fù)雜度O(n)，它的時間復(fù)雜度與二，它的時間復(fù)雜度與二叉排序樹的叉排序樹的最好時間復(fù)雜度相同，都為最好時間復(fù)雜度相同，都為O(log2n)。 84 散列查找散列查找 8.4.1 基本概念基本概念散列查找，也稱為散列查找，也稱為哈希查找哈希查找。它既是一種查找方法，

30、又是一。它既是一種查找方法，又是一種存貯方法，稱為散列存貯。種存貯方法，稱為散列存貯。散列存貯的內(nèi)存存放形式也稱散列存貯的內(nèi)存存放形式也稱為散列表。為散列表。散列查找，與前面介紹的查找方法完全不同，前面介紹的所散列查找，與前面介紹的查找方法完全不同，前面介紹的所有查找都是基于待查關(guān)鍵字與表中元素進行比較而實現(xiàn)的查有查找都是基于待查關(guān)鍵字與表中元素進行比較而實現(xiàn)的查找方法，找方法，而散列查找是通過構(gòu)造散列函數(shù)來得到待查關(guān)鍵字而散列查找是通過構(gòu)造散列函數(shù)來得到待查關(guān)鍵字的地址，按理論分析真正不需要用到比較的一種查找方法的地址，按理論分析真正不需要用到比較的一種查找方法。例如，要找關(guān)鍵字為例如，要找

31、關(guān)鍵字為k的元素，則只需求出函數(shù)值的元素，則只需求出函數(shù)值H（k），），H（k）為給定的散列函數(shù)，代表關(guān)鍵字）為給定的散列函數(shù)，代表關(guān)鍵字k在存貯區(qū)中的地址，在存貯區(qū)中的地址，而存貯區(qū)為一塊連續(xù)的內(nèi)存單元，可用一個一維數(shù)組而存貯區(qū)為一塊連續(xù)的內(nèi)存單元，可用一個一維數(shù)組(或鏈或鏈表表)來表示。來表示。例例8-4，假設(shè)有一批關(guān)鍵字序列，假設(shè)有一批關(guān)鍵字序列18,75,60,43,54,90,46，給定散列函數(shù)給定散列函數(shù)H（k）=k%13，存貯區(qū)的內(nèi)存地址從，存貯區(qū)的內(nèi)存地址從0到到15，則可以得到每個關(guān)鍵字的散列地址為：，則可以得到每個關(guān)鍵字的散列地址為： H（18）=18%13=5 H（75）=75%13=10 H（60）=60%13=8 H（43）=43%13=4 H（54）=54%13=2 H（90）=90%13=12 H（46）=46%13=7于是，于是，根據(jù)散列地址，可以將上述根據(jù)散列地址，可以將上述7個關(guān)鍵字序列存貯個關(guān)鍵字序列存貯到一個一維數(shù)組到一個一維數(shù)組HT（散列表）中（散列表）中，具體表示為：，具體表示為： 54 43 18 46 60 7