《數(shù)據(jù)結(jié)構(gòu)（C++版）（第二版）》課件第08章

2023年11月28日1第8章查找本章學(xué)習(xí)內(nèi)容

8.1查找的基本概念8.2線性表的查找8.3樹(shù)表查找8.4散列查找2023年11月28日28.1查找的基本概念在前面幾章中，我們介紹了線性表、棧和隊(duì)列、串等線性結(jié)構(gòu)及多維數(shù)組、廣義表、樹(shù)和圖等非線性結(jié)構(gòu)，討論了它們的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及運(yùn)算，并且在運(yùn)算中，曾經(jīng)討論過(guò)一些簡(jiǎn)單的查找運(yùn)算。但由于查找運(yùn)算的使用頻率相當(dāng)高，幾乎在任何一個(gè)計(jì)算機(jī)系統(tǒng)中都會(huì)涉及到，所以當(dāng)問(wèn)題的規(guī)模相當(dāng)大時(shí)，查找算法的效率就顯得十分重要。因此，本章將著重討論各種查找方法，并通過(guò)對(duì)它們的效率分析來(lái)比較各種查找方法的優(yōu)劣。查找，也稱為檢索。在我們的日常生活中，隨處可見(jiàn)查找的實(shí)例。如查找某人的地址、電話號(hào)碼；查某單位45歲以上職工等，都屬于查找范疇。本書(shū)中，我們規(guī)定查找是按關(guān)鍵字進(jìn)行的。所謂關(guān)鍵字（key）是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)（或識(shí)別）一個(gè)數(shù)據(jù)元素。例如，描述一個(gè)考生的信息，可以包含：考號(hào)、姓名、性別、年齡、家庭住址、電話號(hào)碼、成績(jī)等關(guān)鍵字。但有些關(guān)鍵字不能惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，而有的關(guān)鍵字可以惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。如剛才的考生信息中，姓名不能惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（因有同名同姓的人），而考號(hào)可以惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（每個(gè)考生考號(hào)是惟一的，不能相同）。我們將能惟一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字稱為主關(guān)鍵字，而其他關(guān)鍵字稱為輔助關(guān)鍵字或從關(guān)鍵字。2023年11月28日3有了主關(guān)鍵字及關(guān)鍵字后，我們可以給查找下一個(gè)完整的定義。所謂查找，就是根據(jù)給定的值，在一個(gè)表中查找出其關(guān)鍵字等于給定值的數(shù)據(jù)元素，若表中有這樣的元素，則稱查找是成功的，此時(shí)查找的信息為給定整個(gè)數(shù)據(jù)元素的輸出或指出該元素在表中的位置；若表中不存在這樣的記錄，則稱查找是不成功的，或稱查找失敗，并可給出相應(yīng)的提示。因?yàn)椴檎沂菍?duì)已存入計(jì)算機(jī)中的數(shù)據(jù)所進(jìn)行的操作，所以采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來(lái)表示“表”，即表中結(jié)點(diǎn)是按何種方式組織的。為了提高查找速度，我們經(jīng)常使用某些特殊的數(shù)據(jù)結(jié)構(gòu)來(lái)組織表。因此在研究各種查找算法時(shí)，我們首先必須弄清這些算法所要求的數(shù)據(jù)結(jié)構(gòu)，特別是存儲(chǔ)結(jié)構(gòu)。查找有內(nèi)查找和外查找之分。若整個(gè)查找過(guò)程全部在內(nèi)存進(jìn)行，則稱這樣的查找為內(nèi)查找；反之，若在查找過(guò)程中還需要訪問(wèn)外存，則稱之為外查找。我們僅介紹內(nèi)查找。2023年11月28日4要衡量一種查找算法的優(yōu)劣，主要是看要找的值與關(guān)鍵字的比較次數(shù)，我們將找到給定值與關(guān)鍵字的比較次數(shù)的平均值來(lái)作為衡量一個(gè)查找算法好壞的標(biāo)準(zhǔn)，對(duì)于一個(gè)含有n個(gè)元素的表，查找成功時(shí)的平均查找長(zhǎng)度可表示為ASL=，其中pi為查找第i個(gè)元素的概率，且=1。一般情形下我們認(rèn)為查找每個(gè)元素的概率相等，ci為查找第i個(gè)元素所用到的比較次數(shù)。2023年11月28日58.2線性表的查找8.2.1順序查找1．順序查找的基本思想順序查找是一種最簡(jiǎn)單的查找方法，它的基本思想是：從表的一端開(kāi)始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和待找的值Ｋ相比較，若相等，則查找成功，若整個(gè)表掃描完畢，仍未找到關(guān)鍵字等于Ｋ的元素，則查找失敗。順序查找既適用于順序表，也適用于鏈表。若用順序表，查找可從前往后掃描，也可從后往前掃描，但若采用單鏈表，則只能從前往后掃描。另外，順序查找的表中元素可以是無(wú)序的。下面以順序表的形式來(lái)描述算法。2023年11月28日62．順序查找算法實(shí)現(xiàn)constintn=maxn //n為表的最大長(zhǎng)度structnode{…elemtypekey; //key為關(guān)鍵字，類型設(shè)定為elemtype};intseqsearch(nodeR[n+1],elemtypek) //在表R中查找關(guān)鍵字值為k的元素{R[0].key=k;inti=n; //從表尾開(kāi)始向前掃描while(R[i].key!=k)i--;returni;}2023年11月28日7在函數(shù)seqsearch中，若返回的值為０表示查找不成功，否則查找成功。函數(shù)中查找的范圍從R[n]到R[1]，R[0]為監(jiān)視哨，起兩個(gè)作用：其一，是為了省去判定while循環(huán)中下標(biāo)越界的條件i≥1，從而節(jié)省比較時(shí)間；其二，保存要找值的副本，若查找時(shí)遇到它，表示查找不成功。若算法中不設(shè)立監(jiān)視哨R[0]，程序花費(fèi)的時(shí)間將會(huì)增加，這時(shí)的算法可寫(xiě)為下面的形式：intseqsearch(nodeR[n+1]，elemtypek){inti=n;while(R[i].key!=k)&&(i>=1)i--;returni;}當(dāng)然上面的算法也可以改成從表頭向后掃描，將監(jiān)視哨設(shè)在右邊，這種方法請(qǐng)讀者自己完成。2023年11月28日83．順序查找性能分析假設(shè)在每個(gè)位置查找的概率相等，即有pi=1/n，由于查找是從后往前掃描，則有每個(gè)位置的查找比較次數(shù)cn=1，cn-1=2，…，c1=n，于是，查找成功的平均查找ASL===，即它的時(shí)間復(fù)雜度為O(n)。這就是說(shuō)，查找成功的平均比較次數(shù)約為表長(zhǎng)的一半。若k值不在表中，則必須進(jìn)行n+1次比較之后才能確定查找失敗。另外，從ASL可知，當(dāng)n較大時(shí)，ASL值較大，查找的效率較低。順序查找的優(yōu)點(diǎn)是算法簡(jiǎn)單，對(duì)表結(jié)構(gòu)無(wú)任何要求，無(wú)論是用向量還是用鏈表來(lái)存放結(jié)點(diǎn)，也無(wú)論結(jié)點(diǎn)之間是否按關(guān)鍵字有序或無(wú)序，它都同樣適用。順序查找的缺點(diǎn)是查找效率低，當(dāng)n較大時(shí)，不宜采用順序查找，而必須尋求更好的查找方法。2023年11月28日98.2.2二分查找1．二分查找的基本思想二分查找，也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制：要求表必須用向量作存儲(chǔ)結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序（升序或降序均可）。我們不妨假設(shè)表中元素為升序排列。二分查找的基本思想是：首先將待查值k與有序表R[1]～R[n]的中點(diǎn)mid上的關(guān)鍵字R[mid].key進(jìn)行比較，若相等，則查找成功；否則，若R[mid].key>k，則在R[1]～R[mid-1]中繼續(xù)查找，若有R[mid].key<k，則在R[mid+1]～R[n]中繼續(xù)查找。每通過(guò)一次關(guān)鍵字的比較，查找區(qū)間的長(zhǎng)度就縮小一半，如此不斷循環(huán)下去，直到找到關(guān)鍵字為k的元素止；或者，若當(dāng)前的查找區(qū)間為空，則表示查找失敗。從上述查找思想可知，每進(jìn)行一次關(guān)鍵字比較，區(qū)間數(shù)目增加一倍，故稱為二分（區(qū)間一分為二），而區(qū)間長(zhǎng)度縮小一半，故也稱為折半（查找的范圍縮小一半）。2023年11月28日102．二分查找算法實(shí)現(xiàn)intbinsearch(nodeR[n+1],elemtypek){intlow=1,high=n;while(low<=high){intmid=(low+high)/2; //取區(qū)間中點(diǎn)if(R[mid].key==k)returnmid; //查找成功elseif(R[mid].key>k)high=mid-1; //在左子區(qū)間中查找

elselow=mid+1; //在右子區(qū)間中查找}return0; //查找失敗}例如，假設(shè)給定有序表中關(guān)鍵字為8,17,25,44,68,77,98,100,115,125，將查找k=17和k=120的情況描述為圖8-1和圖8-2的形式。2023年11月28日11圖8-1查找k=17的示意圖（查找成功）2023年11月28日12（a）初始情形（b）經(jīng)過(guò)一次比較后的情形（c）經(jīng)過(guò)二次比較后的情形（d）經(jīng)過(guò)三次比較后的情形（e）經(jīng)過(guò)四次比較后的情形（high<low）圖8-2查找k=120的示意圖（查找不成功）2023年11月28日133．二分查找的性能分析為了分析二分查找的性能，可以用二叉樹(shù)來(lái)描述二分查找過(guò)程。把當(dāng)前查找區(qū)間的中點(diǎn)作為根結(jié)點(diǎn)，左子區(qū)間和右子區(qū)間分別作為根的左子樹(shù)和右子樹(shù)，左子區(qū)間和右子區(qū)間再按類似的方法，由此得到的二叉樹(shù)稱為二分查找的判定樹(shù)。例如，圖8-1給定的關(guān)鍵字序列的判定樹(shù)見(jiàn)圖8-3。圖8-3具有10個(gè)關(guān)鍵字序列的二分查找判定樹(shù)2023年11月28日14從圖8-3可知，查找根結(jié)點(diǎn)68，需一次查找，查找17和100，各需二次查找，查找8、25、77、115各需三次查找，查找44、98、125各需四次查找。于是，可以得到結(jié)論：二叉樹(shù)第k層結(jié)點(diǎn)的查找次數(shù)各為k次（根結(jié)點(diǎn)為第1層），而第k層結(jié)點(diǎn)數(shù)最多為2k-1個(gè)。假設(shè)該二叉樹(shù)的深度為h，則二分查找成功的平均查找長(zhǎng)度為（假設(shè)每個(gè)結(jié)點(diǎn)的查找概率相等）：ASL==≤(1+2

2+3

22+…+h

2h-1)因此，在最壞情形下，上面的不等號(hào)將會(huì)成立，并根據(jù)二叉樹(shù)的性質(zhì)，最大的結(jié)點(diǎn)數(shù)n=2h-1，h=log2(n+1)，于是可以得到平均查找長(zhǎng)度ASL=log2(n+1)-1。2023年11月28日15當(dāng)n很大時(shí)，ASL

log2(n+1)-1可以作為二分查找成功時(shí)的平均查找長(zhǎng)度，它的時(shí)間復(fù)雜度為O(log2n)。而二分查找在查找不成功時(shí)的平均查找長(zhǎng)度不會(huì)超過(guò)判定樹(shù)的深度。而判定樹(shù)有一個(gè)特點(diǎn)：它的中序序列是一個(gè)有序序列，即為二分查找的初始序列。在判定樹(shù)中，所有根結(jié)點(diǎn)值大于左子樹(shù)而小于右子樹(shù)，因此在判定樹(shù)上查找很方便，與根結(jié)點(diǎn)比較時(shí)若相等則查找成功，若待找的值小于根結(jié)點(diǎn)，進(jìn)入左子樹(shù)繼續(xù)查找，否則進(jìn)入右子樹(shù)查找。若找到葉子結(jié)點(diǎn)時(shí)還沒(méi)有找到所需元素，則查找失敗?，F(xiàn)將圖8-1中查找k=17的過(guò)程用判定樹(shù)形式來(lái)進(jìn)行描述，見(jiàn)圖8-3，首先找到根結(jié)點(diǎn)68，比17大，進(jìn)入左子樹(shù)查找，左子樹(shù)的根結(jié)點(diǎn)值17與待查值相同，故通過(guò)兩次查找就可以成功地找到k=17。再看查找k=120的過(guò)程。仍以圖8-3為例說(shuō)明，首先進(jìn)入根結(jié)點(diǎn)68，比120要小，進(jìn)入右子樹(shù)查找，右子樹(shù)根結(jié)點(diǎn)100，還比120要小，再進(jìn)入以100為根的右子樹(shù)繼續(xù)查找，根的值為115，仍然比120小，再進(jìn)入以115為根的右子樹(shù)查找，根的值為125，比120要大，則再進(jìn)入以125為根的左子樹(shù)查找，而125為葉子結(jié)點(diǎn)，無(wú)左子樹(shù)，故通過(guò)4次查找以后，發(fā)現(xiàn)查找k=120是不成功的。二分查找的優(yōu)點(diǎn)是比較次數(shù)較順序查找少，查找速度快，執(zhí)行效率高。缺點(diǎn)是表的存儲(chǔ)結(jié)構(gòu)只能是順序存儲(chǔ)，不能是鏈?zhǔn)酱鎯?chǔ)，且表中元素必須是有序的。2023年11月28日168.2.3索引查找1．索引查找的思想索引查找，又稱分級(jí)查找，它既是一種查找方法，又是一種存儲(chǔ)方法，稱為索引存儲(chǔ)。它在我們的日常生活中有著廣泛的應(yīng)用。例如，在漢語(yǔ)字典中查找某個(gè)漢字時(shí)，若知道某個(gè)漢字讀音，則可以先在音節(jié)表中查找到對(duì)應(yīng)正文中的頁(yè)碼，然后再在正文中所對(duì)應(yīng)的頁(yè)中查出待查的漢字；若知道該漢字的字形，但不知道讀音，則可以先在部首表中根據(jù)字的部首查找到對(duì)應(yīng)檢字表中的頁(yè)碼，再在檢字表中根據(jù)字的筆畫(huà)找到該漢字所在的頁(yè)碼。在這里，整個(gè)字典就是索引查找的對(duì)象，字典的正文是字典的主要部分，被稱為主表，而檢字表、部首表和音節(jié)表都有是為了方便查找主表而建立的索引，所以被稱為索引表。在索引查找中，主表只有一個(gè)，其中包含的是待查找的內(nèi)容，而索引表可以有多個(gè)，包含一級(jí)索引，二級(jí)索引……，所需的級(jí)數(shù)可根據(jù)具體問(wèn)題而定。如剛才的利用讀音查找漢字為一級(jí)索引，而利用字形查找漢字為二級(jí)索引（部首表→檢字表→漢字）。在此，我們僅討論一級(jí)索引。2023年11月28日17索引查找是在線性表（主表）的索引存儲(chǔ)結(jié)構(gòu)上進(jìn)行的，而索引存儲(chǔ)的基本思想是：首先將一個(gè)線性表（主表）按照一定的規(guī)則分成若干個(gè)邏輯上的子表，并為每個(gè)子表分別建立一個(gè)索引項(xiàng)，由所有這些索引項(xiàng)得到主表的一個(gè)索引表，然后，可采用順序或鏈接的方法來(lái)存儲(chǔ)索引表和各個(gè)子表。索引表中的每個(gè)索引項(xiàng)通常包含三個(gè)域：一是索引值域，用來(lái)存儲(chǔ)標(biāo)識(shí)對(duì)應(yīng)子表的索引值，它相當(dāng)于記錄的關(guān)鍵字，在索引表中由此索引值來(lái)惟一標(biāo)識(shí)一個(gè)索引項(xiàng)（子表）；二是子表的開(kāi)始位置，用來(lái)存儲(chǔ)對(duì)應(yīng)子表的第一個(gè)元素的存儲(chǔ)位置；三是子表的長(zhǎng)度，用來(lái)存儲(chǔ)對(duì)應(yīng)子表的元素個(gè)數(shù)。于是，索引表的類型可定義如下：structindexlist{indextypeindex; //索引值域

intstart; //子表中第一個(gè)元素在主表中的下標(biāo)位置

intlength; //子表的長(zhǎng)度}2023年11月28日18編號(hào)姓名部門(mén)職稱J001趙一科學(xué)系教授J002錢二科學(xué)系講師J003張三科學(xué)系副教授J004李四科學(xué)系助教D001王五工程系講師D002孫六工程系助教D003劉七工程系副教授G001朱八通訊系教授G002楊九通訊系講師C001羅十應(yīng)用系副教授表8-1教師檔案表2023年11月28日19例如，設(shè)有一個(gè)學(xué)校部分教師檔案表如表8-1所示，設(shè)編號(hào)為主關(guān)鍵字，則該表可以用一個(gè)線性表L=(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10)來(lái)表示，其中ai（1≤i≤n）表示第i位教師的信息（包含編號(hào)，姓名，部門(mén)，職稱），而它的索引表可以按部門(mén)進(jìn)行，也可以按職稱進(jìn)行，按部門(mén)的索引表中有4個(gè)子表，分別為：

科學(xué)系J=(a1,a2,a3,a4)

工程系D=(a5,a6,a7)

通訊系G=(a8,a9)

應(yīng)用系C=(a10)該4個(gè)子表表示成一個(gè)索引表如表8-2所示。2023年11月28日20表8-2按部門(mén)的索引表indexstartlengthK04G43T72Y91若按職稱進(jìn)行索引，則得到的索引表中也有4個(gè)子表，分別為：

教授=(a1,a8)

副教授=(a3,a7,a10)

講師=(a2,a5,a9)

助教=(a4,a6)2023年11月28日21這時(shí)的主表用順序存儲(chǔ)不太方便，因相同職稱的教師沒(méi)有連在一起，故用鏈?zhǔn)酱鎯?chǔ)得到主表較方便。具體的存儲(chǔ)如圖8-4所示。在圖8-4中，箭頭上面的數(shù)字表示該元素在主表中的下標(biāo)位置（指針），每個(gè)子表中最后一個(gè)元素的指針為-1，表示為空指針。于是，可以得到如表8-3所示的職稱索引表。表8-3按職稱的索引表indexstartlength教授02副教授23講師13助教32圖8-4按職稱的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2023年11月28日22從剛才的兩種索引表中，可以給出索引查找的基本思想如下：第一步，在索引表中按index域查找所給值K1，這時(shí)可得到子表起始位置start和長(zhǎng)度length，若找不到K1，結(jié)束查找，表示查找不成功。第二步，在主表的start位置開(kāi)始，長(zhǎng)度為length的范圍內(nèi)查找所給值K2，若找到，查找成功，否則，查找不成功。例如，對(duì)于按部門(mén)的索引查找，主表可以用順序存儲(chǔ)，假設(shè)K1=“G”，“G”代工程系，K2=“孫六”，則先在表8-2的索引表中找到的index域?yàn)椤癎”的項(xiàng)，得到start=4，length=3，然后從主表的第4個(gè)位置開(kāi)始（即a5）找姓名為“孫六”的人，則在主表的第5個(gè)位置可以找到，故查找成功。若假設(shè)K1=“G”，K2=“楊九”，則索引表的查找與上面相同，然后在主表的第4個(gè)位置開(kāi)始查找，沒(méi)找到，進(jìn)入第5個(gè)位置查找，還沒(méi)找到，進(jìn)入第6位置查找，仍然沒(méi)找到，但查找的length=3，即只允許3次查找，故查找不成功。若假設(shè)K1=“F”，K2=“張三”，則首先在索引表中就找不到“F”，故無(wú)需進(jìn)入主表進(jìn)行查找，查找不成功。對(duì)于按職稱的索引查找，主表是用鏈?zhǔn)酱鎯?chǔ)（見(jiàn)圖8-4），假設(shè)K1=“副教授”，K2=“劉七”，則首先在表8-3的索引表中找到index域?yàn)椤案苯淌凇钡捻?xiàng)，得到start=2，length=3，然后進(jìn)入主表（見(jiàn)圖8-4），找到指針為2（start=2）的那個(gè)鏈表，即找到a3，它的姓名域?yàn)椤皬埲?，故再往后找，找到a7，它的姓名域?yàn)椤皠⑵摺?，因此，查找成功。不成功的形式可類似地分析出?lái)。2023年11月28日232．索引查找的算法實(shí)現(xiàn)見(jiàn)書(shū)中算法3．索引查找的性能分析由于索引查找中涉及兩方面查找，第一個(gè)是索引表的查找，第二個(gè)是主表的查找，假設(shè)兩種查找都按順序查找方式進(jìn)行，則索引表的平均查找長(zhǎng)度為(m+1)/2，主表中的平均查找長(zhǎng)度為(s+1)/2，（m為索引表的長(zhǎng)度，s為主表中相應(yīng)子表的長(zhǎng)度），則索引查找的平均查找長(zhǎng)度為：ASL=(m+1)/2+(s+1)/2。若假定每個(gè)子表具有相同的長(zhǎng)度，而主表的長(zhǎng)度為n，則有n=m.s，這時(shí)當(dāng)s=時(shí)，索引查找具有最小的平均查找長(zhǎng)度，即ASL=1+。從該公式可以看出，索引查找的性能優(yōu)于順序查找，但比二分查找要差，時(shí)間復(fù)雜度介于O(log2n)~O(n)之間。2023年11月28日248.2.4分塊查找1．分塊查找的思想分塊查找實(shí)際上就是一種索引查找，但查找的性能優(yōu)于索引查找，其原因是分塊查找的索引表是一個(gè)有序表，故可以用二分查找來(lái)代替順序查找，實(shí)現(xiàn)索引表的快速查找。具體實(shí)現(xiàn)如下：將一個(gè)含有n個(gè)元素的主表分成m個(gè)子表，但要求子表之間元素是按關(guān)鍵字有序排列的，而子表中元素可以無(wú)序，然后建立索引表，索引表中索引域的值用每個(gè)子表的最大關(guān)鍵字代替，則可以按索引查找思想找到表中元素。例如，給定關(guān)鍵字序列如下：18，7，26，34，15，42，36，70，60，55，83，90，78，72，74，假設(shè)m=3，s=5，即將該序列分成3個(gè)子表，每個(gè)子表有5個(gè)元素，則得到的主表和索引表如圖8-5所示。2023年11月28日25（a）15個(gè)關(guān)鍵字序列得到的主表（b）按關(guān)鍵字序列遞增得到的索引表圖8-5分塊查找的主表和索引表2023年11月28日26假設(shè)在上述表中查找60，則可以先在索引表中查找60所在的子表，由于34≤60≤70，故60應(yīng)在第二塊中，這時(shí)start=5，length=5，故60應(yīng)在主表的第5個(gè)位置到第9個(gè)位置中查找。2．分塊查找的算法實(shí)現(xiàn)見(jiàn)書(shū)中算法3．分塊查找的性能分析分塊查找實(shí)際上就是索引查找,但分塊查找中索引的域的類型與主表的關(guān)鍵字域的類型相同，且索引表按索引域遞增（或遞減）有序，故它的平均查找長(zhǎng)度與索引查找接近，且優(yōu)于索引查找。2023年11月28日278.3樹(shù)表查找8.3.1二叉排序樹(shù)查找1．什么是二叉排序樹(shù)二叉排序樹(shù)（BinarySortingTree），它或者是一棵空樹(shù)，或者是一棵具有如下特征的非空二叉樹(shù)：（1）若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；（2）若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均大于等于根結(jié)點(diǎn)的關(guān)鍵字；（3）左、右子樹(shù)本身又都是一棵二叉排序樹(shù)。從上述定義可知，二叉排序樹(shù)的中序遍歷序列是一個(gè)從小到大排列的有序序列（與二分查找的判定樹(shù)類似）。2023年11月28日282．二叉排序樹(shù)的數(shù)據(jù)類型描述和第6章類似，可以用一個(gè)二叉鏈表來(lái)描述一棵二叉排序樹(shù)，具體為：classbtreenode{public:elemtypedata; //代表關(guān)鍵字btreenode

*left,*right; //代表左、右孩子};3．二叉排序樹(shù)的基本運(yùn)算（1）二叉排序樹(shù)的插入若二叉排序樹(shù)為空，則作為根結(jié)點(diǎn)插入，否則，若待插入的值小于根結(jié)點(diǎn)值，則作為左子樹(shù)插入，否則作為右子樹(shù)插入，算法描述為：2023年11月28日29voidInsert(btreenode*BST,elemtypeX){//在二叉排序樹(shù)BST中，插入值為x的結(jié)點(diǎn)if(BST==NULL){btreenode*p=newbtreenode;p->data=X;p->left=p->right=NULL;BST=p;}

elseif(BST->data>=X)Insert(BST->left,X); //在左子樹(shù)中插入

elseInsert(BST->right,X); //在右子樹(shù)中插入}2023年11月28日30（2）二叉排序樹(shù)的建立只要反復(fù)調(diào)用二叉排序樹(shù)的插入算法即可，算法描述為：btreenode*Creat(intn) //建立含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù){btreenode*BST=NULL;for(inti=1;i<=n;i++){cin>>x; //輸入關(guān)鍵字序列Insert(BST,x);}returnBST;}例如，結(jié)定關(guān)鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹(shù)的過(guò)程如圖8-6所示。（注：二叉排序樹(shù)與關(guān)鍵字排列順序有關(guān)，排列順序不一樣，得到的二叉排序樹(shù)也不一樣）。2023年11月28日31（a）（b）（c）（d）（e）（f）（g）（h）（i）（j）圖8-6二叉排序樹(shù)的生成過(guò)程2023年11月28日32（3）二叉排序樹(shù)的刪除二叉排序樹(shù)的刪除比插入要復(fù)雜得多，因?yàn)楸徊迦氲慕Y(jié)點(diǎn)都被鏈接到樹(shù)中的葉子結(jié)點(diǎn)上，故不會(huì)破壞樹(shù)的結(jié)構(gòu)，而刪除則不同，它可能是刪除葉子結(jié)點(diǎn)，也可能是刪除非葉子結(jié)點(diǎn)，當(dāng)刪除非葉子結(jié)點(diǎn)時(shí)，就會(huì)破壞原有結(jié)點(diǎn)的鏈接關(guān)系，需要重新修改指針，使得刪除后仍為一棵二叉排序樹(shù)。具體算法見(jiàn)書(shū)中。4．二叉排序樹(shù)上的查找（1）二叉排序樹(shù)的查找思想若二叉排序樹(shù)為空，則查找失敗，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹(shù)重復(fù)此步驟，否則，進(jìn)入右子樹(shù)重復(fù)此步驟，若在查找過(guò)程中遇到二叉排序樹(shù)的葉子結(jié)點(diǎn)時(shí)，還沒(méi)有找到待找結(jié)點(diǎn)，則查找不成功。2023年11月28日33（2）二叉排序樹(shù)查找的算法實(shí)現(xiàn)treenode*find(btreenode*BST,elemtypex)//在以BST為根指針的二叉排序樹(shù)中查找值為x的結(jié)點(diǎn){if(BST==NULL)returnNULL; //查找失敗

else{if(BST->data==x) //查找成功

returnBST;elseif(BST->data>x) //進(jìn)入左子樹(shù)查找

returnfind(BST->left,x);else //進(jìn)入右子樹(shù)查找

returnfind(BST->right,x);}}2023年11月28日34當(dāng)然，上述算法也可以改成如下的非遞歸算法：btreenode*find1(btreenode*BST,elemtypex){if(BST==NULL)returnNULL; //查找失敗

else{btreenodep=BST;while(p!=NULL){if(p->data==x)break;elseif(p->data>x)p=p->left;elsep=p->right;}if(p!=NULL)returnP; //查找成功elsereturnNULL; //查找不成功}}2023年11月28日355．二叉排序樹(shù)查找的性能分析在二叉排序樹(shù)查找中，成功的查找次數(shù)不會(huì)超過(guò)二叉樹(shù)的深度，而具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的深度，最好為log2n，最壞為n。因此，二叉排序樹(shù)查找的最好時(shí)間復(fù)雜度為O(log2n)，最壞時(shí)間復(fù)雜度為O(n)，一般情形下，其時(shí)間復(fù)雜度大致可看成O(log2n)，比順序查找效率要好，但比二分查找要差。【例8-1】給定關(guān)鍵字序列1,2,3，試寫(xiě)出它的所有二叉排序樹(shù)。分析：由于關(guān)鍵字序列1,2,3，有6種排列，故最多有6棵二叉排序樹(shù)。第一棵的關(guān)鍵字序列為1,2,3，生成的二叉排序樹(shù)見(jiàn)圖8-7（a）；第二棵的關(guān)鍵字序列為1,3,2，生成的二叉排序樹(shù)見(jiàn)圖8-7（b）；第三棵的關(guān)鍵字序列為2,1,3，生成的二叉排序樹(shù)見(jiàn)圖8-7（c）；第四棵的關(guān)鍵字序列為2,3,1，生成的二叉排序樹(shù)見(jiàn)圖8-7（d）；第五棵的關(guān)鍵字序列為3,2,1，生成的二叉排序樹(shù)見(jiàn)圖8-7（e）；第六棵的關(guān)鍵字序列為3,1,2，生成的二叉排序樹(shù)見(jiàn)圖8-7（f）。2023年11月28日36

（a）（b）（c）（d）（e）（f）圖8-7相同關(guān)鍵字序列得到的不同二叉排序樹(shù)2023年11月28日378.3.2平衡二叉樹(shù)查找1．平衡二叉樹(shù)的概念平衡二叉樹(shù)（balancedbinarytree）是由阿德?tīng)柹痪S爾斯（Adelson-Velskii）和蘭迪斯（Landis）于1962年首先提出的，所以又稱為AVL樹(shù)。若一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1，則稱這樣的二叉樹(shù)為平衡二叉樹(shù)。將該結(jié)點(diǎn)的左子樹(shù)深度減去右子樹(shù)深度的值，稱為該結(jié)點(diǎn)的平衡因子（balancefactor）。也就是說(shuō)，一棵二叉排序樹(shù)中，所有結(jié)點(diǎn)的平衡因子只能為0、1、-1時(shí)，則該二叉排序樹(shù)就是一棵平衡二叉樹(shù)，否則就不是一棵平衡二叉樹(shù)。圖8-8所示的二叉排序樹(shù)是一棵平衡二叉樹(shù)，而圖8-9所示的二叉排序樹(shù)就不是一棵平衡二叉樹(shù)。2023年11月28日38

圖8-8一棵平衡二叉樹(shù)圖8-9一棵非平衡二叉樹(shù)2023年11月28日392．非平衡二叉樹(shù)的平衡處理若一棵二叉排序樹(shù)是平衡二叉樹(shù)，插入某個(gè)結(jié)點(diǎn)后，可能會(huì)變成非平衡二叉樹(shù)，這時(shí)，就可以對(duì)該二叉樹(shù)進(jìn)行平衡處理，使其變成一棵平衡二叉樹(shù)。處理的原則應(yīng)該是處理與插入點(diǎn)最近的、而平衡因子又比1大或比-1小的結(jié)點(diǎn)。下面將分四種情況討論平衡處理。（1）LL型（左左型）的處理如圖8-10所示，在C的左孩子B上插入一個(gè)左孩子結(jié)點(diǎn)A，使C的平衡因子由1變成了2，成為不平衡的二叉排序樹(shù)。這時(shí)的平衡處理為：將C順時(shí)針旋轉(zhuǎn)，成為B的右子樹(shù)，而原來(lái)B的右子樹(shù)則變成C的左子樹(shù)，待插入結(jié)點(diǎn)A作為B的左子樹(shù)。（注：圖中結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)的平衡因子）。圖8-10LL型平衡處理平衡處理2023年11月28日40（2）LR型（左右型）的處理如圖8-11所示，在C的左孩子A上插入一個(gè)右孩子B，使得C的平衡因子由1變成了2，成為不平衡的二叉排序樹(shù)。這時(shí)的平衡處理為：將B變到A與C之間，使之成為L(zhǎng)L型，然后按第（1）種情形LL型處理。圖8-11LR的平衡處理旋轉(zhuǎn)平衡處理2023年11月28日41（3）RR型（右右型）的處理如圖8-12所示，在A的右孩子B上插入一個(gè)右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹(shù)。這時(shí)的平衡處理為：將A逆時(shí)針旋轉(zhuǎn)，成為B的左子樹(shù)，而原來(lái)B的左子樹(shù)則變成A的右子樹(shù)，待插入結(jié)點(diǎn)C成為B的右子樹(shù)。平衡處理圖8-12RR型的平衡處理2023年11月28日42（4）RL型（右左型）的處理如圖8-13所示，在A的右孩子C上插入一個(gè)左孩子B，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹(shù)。這時(shí)的平衡處理為：將B變到A與C之間，使之成為RR型，然后按第（3）種情形RR型處理。旋轉(zhuǎn)平衡處理圖8-13RL型的平衡處理2023年11月28日43【例8-2】給定一個(gè)關(guān)鍵字序列4，5，7，2，1，3，6，試生成一棵平衡二叉樹(shù)。分析：平衡二叉樹(shù)實(shí)際上也是一棵二叉排序樹(shù)，故可以按建立二叉排序樹(shù)的思想建立，在建立的過(guò)程中，若遇到不平衡，則進(jìn)行相應(yīng)平衡處理，最后就可以建成一棵平衡二叉樹(shù)。具體生成過(guò)程見(jiàn)下面的圖8-14各步驟。（a）插入4（b）插入5（c）插入7RR型2023年11月28日44

（d）插入2（e）插入1LL型LR型（f）插入32023年11月28日45RL型（g）插入6圖8-14平衡二叉樹(shù)的生成過(guò)程3．平衡二叉樹(shù)的查找及性能分析平衡二叉樹(shù)本身就是一棵二叉排序樹(shù)，故它的查找與二叉排序樹(shù)完全相同，但它的查找性能優(yōu)于二叉排序樹(shù)，不像二叉排序樹(shù)那樣，會(huì)出現(xiàn)最壞的時(shí)間復(fù)雜度O(n)，它的時(shí)間復(fù)雜度與二叉排序樹(shù)的最好時(shí)間復(fù)雜相同，都為O(log2n)。2023年11月28日46【例8-3】對(duì)例8-2給定的關(guān)鍵字序列4，5，7，2，1，3，6，試用二叉排序樹(shù)和平衡二叉樹(shù)兩種方法查找，給出查找6的次數(shù)及成功的平均查找長(zhǎng)度。分析：由于關(guān)鍵字序列的順序已經(jīng)確定，故得到的二叉排序樹(shù)和平衡二叉樹(shù)都是惟一的。得到的平衡二叉樹(shù)見(jiàn)圖8-14，得到的二叉排序樹(shù)見(jiàn)圖8-15。圖8-15由關(guān)鍵字序列4，5，7，2，1，3，6生成的二叉排序樹(shù)2023年11月28日47從圖8-15的二叉排序樹(shù)可知，查找6需4次，平均查找長(zhǎng)度ASL=(1+2+2+3+3+3+4)/7=18/7≈2.57。從圖8-14的平衡二叉樹(shù)可知，查找6需2次，平均查找長(zhǎng)度ASL=(1+2+2+3+3+3+3)=17/7≈2.43。從結(jié)果可知，平衡二叉樹(shù)的查找性能優(yōu)于二叉排序樹(shù)。2023年11月28日488.3.3B樹(shù)及B樹(shù)上的查找1．B樹(shù)的定義B樹(shù)是一種平衡的多路查找樹(shù)，一棵m階B樹(shù)定義如下：一棵m階B樹(shù)，或者為空樹(shù)，或者為滿足下列特性的m叉樹(shù)：（1）樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)；（2）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹(shù)；（3）除根結(jié)點(diǎn)以外的所有非終端結(jié)點(diǎn)至少有

m/2

棵子樹(shù)；（4）所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)（n,A0,K1,A1,K2,A2,K3,…,An-1,Kn,An）其中：Ki（i=1,2,…,n）為關(guān)鍵字，且Ki<Ki+1（i=1,2,…,n-1）；Ai（i=0,1,…,n）為指向子樹(shù)根結(jié)點(diǎn)的指針，且指針Ai-1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki（i=1,2,…,n），An所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字均大于Kn，n為關(guān)鍵字的個(gè)數(shù)（

m/2

-1≤n≤m-1）。（5）所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（可以看做是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，用F表示）。2023年11月28日49例如，圖8-16所示為一棵4階B樹(shù)，其深度為4。圖8-16一棵4階B樹(shù)2023年11月28日502．B樹(shù)的查找B樹(shù)的查找類似于平衡二叉樹(shù)的查找。例如，在圖8-16中，查找47的步驟如下：從根結(jié)點(diǎn)開(kāi)始，找到35，由于47>35，進(jìn)入A1指針?biāo)附Y(jié)點(diǎn)c，該結(jié)點(diǎn)有兩個(gè)關(guān)鍵字43、78，由于有43<47<78，故進(jìn)入A1指針?biāo)附Y(jié)點(diǎn)g，g中有三個(gè)關(guān)鍵字47、53、64，正好有符合條件的值47，所以查找成功。同理，若查找25，先找到根結(jié)點(diǎn)a，由于25<35，進(jìn)入A0指針?biāo)附Y(jié)點(diǎn)b，由于18<25，進(jìn)入A1指針?biāo)附Y(jié)點(diǎn)e，由于25<27，進(jìn)入A1指針?biāo)附Y(jié)點(diǎn)（27的左邊），該結(jié)點(diǎn)為F，所以查找不成功。3．B+樹(shù)的定義B+樹(shù)是B樹(shù)的一種變型樹(shù)。一棵m階B+樹(shù)和m階B樹(shù)的差異在于：（1）有n棵子樹(shù)的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字；（2）所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。（3）所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹(shù)（根結(jié)點(diǎn)）中的最大（或最?。╆P(guān)鍵字。2023年11月28日51例如，圖8-17所示為一棵3階的B+樹(shù)。圖8-17一棵3階的B+樹(shù)2023年11月28日524．B+樹(shù)的查找B+樹(shù)的查找與B樹(shù)類似，但除了從根結(jié)點(diǎn)出發(fā)進(jìn)行查找外，還可以從最小關(guān)鍵字的結(jié)點(diǎn)開(kāi)始查找。與B樹(shù)、B+樹(shù)類似的還有一種樹(shù)，稱為2-3樹(shù)。一棵2-3樹(shù)符合下面的定義：（1）一個(gè)結(jié)點(diǎn)包含一個(gè)或兩個(gè)關(guān)鍵字；（2）每個(gè)內(nèi)部結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)（包含一個(gè)關(guān)鍵字）或三個(gè)子結(jié)點(diǎn)（包含兩個(gè)關(guān)鍵字）；（3）所有葉子結(jié)點(diǎn)都在樹(shù)的同一層。2023年11月28日53例如，圖8-18所示的是一棵2-3樹(shù)。圖8-18一棵2-3樹(shù)2023年11月28日548.3.4鍵樹(shù)鍵樹(shù)又稱數(shù)字查找樹(shù)，它是一棵度≥2的樹(shù)，樹(shù)中的每個(gè)結(jié)點(diǎn)中不是包含一個(gè)或幾個(gè)關(guān)鍵字，而是只含有組成關(guān)鍵字的符號(hào)。若關(guān)鍵字是數(shù)值，則結(jié)點(diǎn)中只包含一個(gè)數(shù)位；若關(guān)鍵字是單詞，則結(jié)點(diǎn)中只包含一個(gè)字母字符。例如，給定關(guān)鍵字的集合{CAI、CAO、LI、LIU、YUE、YANG、WANG、WU、WEN}，可以對(duì)關(guān)鍵字按第一個(gè)字母分成四個(gè)子集合：{CAI、CAO}、{LI、LIU}、{YUE、YANG}、{WANG、WU、WEN}，對(duì)每一個(gè)子集合，又可以按第二、第三、第四個(gè)字母繼續(xù)劃分成多個(gè)子集合，直到每個(gè)子集合的關(guān)鍵字只含有一個(gè)字母為止，則按此規(guī)則可以得到一棵鍵樹(shù)。例如圖8-19所示為上面給定關(guān)鍵字的一棵鍵樹(shù)，圖中的$結(jié)點(diǎn)表示字符串的結(jié)束。為了查找和插入方便，我們規(guī)定鍵樹(shù)是有序樹(shù)，即同一層中兄弟結(jié)點(diǎn)之間依所含符號(hào)自左至右有序，并約定結(jié)束符$小于任何字符。2023年11月28日55圖8-19一棵鍵樹(shù)2023年11月28日568.4散列查找8.4.1基本概念散列查找，也稱為哈希查找。它既是一種查找方法，又是一種存儲(chǔ)方法，稱為散列存儲(chǔ)。散列存儲(chǔ)的內(nèi)存存放形式也稱為散列表。散列查找與前面介紹的查找方法完全不同。前面介紹的所有查找都是基于待查關(guān)鍵字與表中元素進(jìn)行比較而實(shí)現(xiàn)的查找方法，而散列查找是通過(guò)構(gòu)造散列函數(shù)來(lái)得到待查關(guān)鍵字的地址，按理論分析真正不需要用到比較的一種查找方法。例如，要找關(guān)鍵字為k的元素，則只需求出函數(shù)值H(k)，H(k)為給定的散列函數(shù)，代表關(guān)鍵字k在存儲(chǔ)區(qū)中的地址，而存儲(chǔ)區(qū)為一塊連續(xù)的內(nèi)存單元，可用一個(gè)一維數(shù)組（或鏈表）來(lái)表示。2023年11月28日57【例8-4】假設(shè)有一批關(guān)鍵字序列18，75，60，43，54，90，46，給定散列函數(shù)H(k)=k%13，存儲(chǔ)區(qū)的內(nèi)存地址從0到15，則可以得到每個(gè)關(guān)鍵字的散列地址為：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=7于是，根據(jù)散列地址，可以將上述7個(gè)關(guān)鍵字序列存儲(chǔ)到一個(gè)一維數(shù)組HT（散列表）中，具體表示為：其中HT就是散列存儲(chǔ)的表，稱為散列表。從散列表中查找一個(gè)元素相當(dāng)方便，例如，查找75，只需計(jì)算出H(75)=75%13=10，則可以在HT[10]中找到75。2023年11月28日58上面討論的散列表是一種理想的情形，即每一個(gè)關(guān)鍵字對(duì)應(yīng)一個(gè)惟一的地址。但是有可能出現(xiàn)這樣的情形，即兩個(gè)不同的關(guān)鍵字有可能對(duì)應(yīng)同一個(gè)內(nèi)存地址，這樣，將導(dǎo)致后放的關(guān)鍵字無(wú)法存儲(chǔ)，我們把這種現(xiàn)象叫做沖突（Collision）。在散列存儲(chǔ)中，沖突是很難避免的，除非構(gòu)造出的散列函數(shù)為線性函數(shù)。散列函數(shù)選得比較差，則發(fā)生沖突的可能性越大。我們把相互發(fā)生沖突的關(guān)鍵字互稱為“同義詞”。在散列存儲(chǔ)中，若發(fā)生沖突，則必須采取特殊的方法來(lái)解決沖突問(wèn)題，才能使散列查找能順利進(jìn)行。雖然沖突不可避免，但發(fā)生沖突的可能性卻與三個(gè)方面因素有關(guān)。第一是與裝填因子α有關(guān)，所謂裝填因子是指散列表中已存入的元素個(gè)數(shù)n與散列表的大小m的比值，即α=n/m。當(dāng)α越小時(shí)，發(fā)生沖突的可能性越小，α越大（最大為1）時(shí)，發(fā)生沖突的可能性就越大。但是，為了減少?zèng)_突的發(fā)生，不能將α變得太小，這樣將會(huì)造成大量存儲(chǔ)空間的浪費(fèi)，因此必須兼顧存儲(chǔ)空間和沖突兩個(gè)方面。第二是與所構(gòu)造的散列函數(shù)有關(guān)（前面已介紹）。第三是與解決沖突的方法有關(guān)，這些內(nèi)容后面將再作進(jìn)一步介紹。2023年11月28日598.4.2散列函數(shù)的構(gòu)造散列函數(shù)的構(gòu)造目標(biāo)是使散列地址盡可能均勻地分布在散列空間上，同時(shí)使計(jì)算盡可能簡(jiǎn)單。具體常用的構(gòu)造方法有如下幾種：1．直接定址法可表示為H(k)=a*k+b，其中a、b均為常數(shù)。這種方法計(jì)算特別簡(jiǎn)單，并且不會(huì)發(fā)生沖突，但當(dāng)關(guān)鍵字分布不連續(xù)時(shí)，會(huì)出現(xiàn)很多空閑單元，造成大量存儲(chǔ)單元的浪費(fèi)。2．?dāng)?shù)字分析法對(duì)關(guān)鍵字序列進(jìn)行分析，取那些位上數(shù)字變化多的、頻率大的作為散列函數(shù)地址。2023年11月28日60例如，對(duì)如下的關(guān)鍵字序列：

430104681015355430101701128352430103720818350430102690605351430105801226356……通過(guò)對(duì)上述關(guān)鍵字序列分析，發(fā)現(xiàn)前5位相同，第6、8、10位上的數(shù)字變化多些，若規(guī)定地址取3位，則散列函數(shù)可取它的第6、8、10位。于是有：H(430104681015355)=480H(430101701128352)=101H(430103620805351)=328H(430102690605351)=296H(430105801226356)=5022023年11月28日613．平方取中法取關(guān)鍵字平方后的中間幾位為散列函數(shù)地址。這是一種比較常用的散列函數(shù)構(gòu)造方法，但在選定散列函數(shù)時(shí)不一定知道關(guān)鍵字的全部信息，取其中哪幾位也不一定合適，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，因此，可以使用隨機(jī)分布的關(guān)鍵字得到函數(shù)地址。圖8-20中，隨機(jī)給出一些關(guān)鍵字，取平方后的第2到4位為函數(shù)地址。圖8-20利用平方取中法得到散列函數(shù)地址2023年11月28日624．折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為散列函數(shù)地址，稱為折疊法。例如，假設(shè)關(guān)鍵字為某人身份證號(hào)碼430104681015355，則可以用4位為一組進(jìn)行疊加，即有5355+8101+1046+430=14932，舍去高位，則有H(430104681015355)=4932為該身份證關(guān)鍵字的散列函數(shù)地址。5．除留余數(shù)法該方法是用關(guān)鍵字序列中的關(guān)鍵字k除以散列表長(zhǎng)度m所得余數(shù)作為散列函數(shù)的地址，即有H(k)=k％m。除留余數(shù)法計(jì)算簡(jiǎn)單，適用范圍廣，是一種最常使用的方法。這種方法的關(guān)鍵是選取較理想的m值，使得每一個(gè)關(guān)鍵字通過(guò)該函數(shù)轉(zhuǎn)換后映射到散列空間上任一地址的概率都相等，從而盡可能減少發(fā)生沖突的可能性。一般情形下，m取為一個(gè)素?cái)?shù)較理想，并且要求裝填因子α最好是在0.6~0.9之間，所以m最好取1.1n~1.7n之間的一個(gè)素?cái)?shù)較好，其中n為散列表中待裝元素個(gè)數(shù)。2023年11月28日638.4.3解決沖突的方法由于散列存儲(chǔ)中選取的散列函數(shù)不是線性函數(shù)，故不可避免地會(huì)產(chǎn)生沖突，下面給出常見(jiàn)的解決沖突的方法。1．開(kāi)放定址法開(kāi)放定址法就是從發(fā)生沖突的那個(gè)單元開(kāi)始，按照一定的次序，從散列表中找出一個(gè)空閑的存儲(chǔ)單元，把發(fā)生沖突的待插入關(guān)鍵字存儲(chǔ)到該單元中，從而解決沖突的發(fā)生。在開(kāi)放定址法中，散列表中的空閑單元（假設(shè)地址為K）不僅向散列地址為K的同義詞關(guān)鍵字開(kāi)放，即允許它們使用，而且還向發(fā)生沖突的其他關(guān)鍵字開(kāi)放（它們的散列地址不為K），這些關(guān)鍵字稱為非同義詞關(guān)鍵字。例如，設(shè)有關(guān)鍵字序列14，27，40，15，16，散列函數(shù)為H(k)=k%13，則14，27，40的散列地址都為1，因此發(fā)生沖突，即14，27，40互為同義詞，這時(shí)，假設(shè)處理沖突的方法是從沖突處順序往后找空閑位置，找到后放入沖突數(shù)據(jù)即可。則14放入第1個(gè)位置，27只能放入第2個(gè)位置，40就只能放入第3個(gè)位置，接著往后有關(guān)鍵字15，16要放入散列表中，而15，16的散列地址分別為2和3，即15應(yīng)放入第2個(gè)位置，16應(yīng)放入第3個(gè)位置，而第2個(gè)位置已放入了27，第3個(gè)位置已放入了40，故也發(fā)生沖突，但這時(shí)是非同義詞沖突，即15和27、16和40相互之間是非同義詞。這時(shí)，解決沖突后，15應(yīng)放入第4個(gè)位置，16應(yīng)放入第5個(gè)位置。因此，在使用開(kāi)放定址法處理沖突的散列表中，地址為K的單元到底存儲(chǔ)的是同義詞中的一個(gè)關(guān)鍵字，還是非同義詞關(guān)鍵字，就要看誰(shuí)先占用它。2023年11月28日64在開(kāi)放定址法中，解決沖突時(shí)具體使用下面一些方法。（1）線性探查法假設(shè)散列表的地址為0~m-1，則散列表的長(zhǎng)度為m。若一個(gè)關(guān)鍵字在地址d處發(fā)生沖突，則依次探查d+1，d+2，…，m-1（當(dāng)達(dá)到表尾m-1時(shí)，又從0，1，2，…，開(kāi)始探查）等地址，直到找到一個(gè)空閑位置來(lái)裝沖突處的關(guān)鍵字，將這種方法稱為線性探查法。假設(shè)發(fā)生沖突時(shí)的地址為d0=H(k)，則探查下一位置的公式為di=(di-1+1)%m（1≤i≤m-1），最后將沖突位置的關(guān)鍵字存入di地址中?！纠?-5】給定關(guān)鍵字序列為19，14，23，1，68，20，84，27，55，11，10，79，散列函數(shù)H(k)=k%13，散列表空間地址為0~12，試用線性探查法建立散列存儲(chǔ)（散列表）結(jié)構(gòu)。得到的散列表如圖8-21所示圖8-21用線性探查法建立的散列表2023年11月28日65對(duì)于關(guān)鍵字序列有：H(19)=6，故19放入第6個(gè)位置，H(14)=1，故14應(yīng)放入第1個(gè)位置，H(23)=10，故23放入第10個(gè)位置，H(1)=1，應(yīng)放入第1個(gè)位置，但與H(14)發(fā)生同義詞沖突，于是只能從第2個(gè)位置開(kāi)始順序找空閑位置，由于第2個(gè)位置為空閑，故可以將1放入第2個(gè)位置，接著有H(68)=3，故68應(yīng)放入第3個(gè)位置，H(20)=7，故20放入第7個(gè)位置，H(84)=6，與H(19)=6發(fā)生同義詞沖突，故84應(yīng)放入第7個(gè)位置，而第7個(gè)位置有關(guān)鍵字20，故再往后找到一個(gè)空閑位置8，即84應(yīng)放入第8個(gè)位置，接著有H(27)=1，與H(14)=1發(fā)生同義詞沖突，故順序往后找到空閑位置4，即27應(yīng)放入第4個(gè)位置，接著有H(55)=3，與H(68)=3發(fā)生同義詞沖突，故順序往后找到空閑位置5，即55應(yīng)放入第5個(gè)位置，接著有H(11)=11，放入第11個(gè)位置，H(10)=10與H(23)=10發(fā)生同義詞沖突，故順序往后找到一個(gè)空閑位置12，即10放入第12個(gè)位置，接著有H(79)=1，與H(14)=1發(fā)生同義詞沖突，故順序往后找到空閑位置9，即79放入第9個(gè)位置。算法描述如下：voidcreatl(elemtypeHT[m],intn)//建立散列表HT，表長(zhǎng)為m，表中元素個(gè)數(shù)為n{inti,j;elemtypek;for(i<0;i<m;i++)HT[i]=NULL;for(i=1;i<=n;i++){cin>>k; //輸入一個(gè)關(guān)鍵字

j=H(k); //j=H(k)為散列函數(shù)while(HT[j]!=NULL)j=(j+1)%m; //發(fā)生沖突時(shí)，查找空閑位置HT[j]=k;}}2023年11月28日66利用線性探查法處理沖突容易造成關(guān)鍵字的“堆積”，這是因?yàn)楫?dāng)連續(xù)n個(gè)單元被占用后，再散列到這些單元上的關(guān)鍵字和直接散列到后面一個(gè)空閑單元上的關(guān)鍵字都要占用這個(gè)空閑單元，致使該空閑單元很容易被占用，從而發(fā)生非同義沖突，造成平均查找長(zhǎng)度的增加。例如，在圖8-21中，插入關(guān)鍵字15，由于H(15)=2，故15應(yīng)放入第2個(gè)位置，但第2個(gè)位置已放入數(shù)據(jù)1，發(fā)生沖突（1與15不是同義詞，故為非同義詞沖突），這時(shí)，只能從第3個(gè)位置開(kāi)始順序查找到一個(gè)空閑位置9，才能放入關(guān)鍵字15。從圖8-21可以看出，第9個(gè)位置是空閑位置，可以為在第1到第8個(gè)位置發(fā)生沖突的關(guān)鍵字所占用（看哪一位置關(guān)鍵字先占用），這樣將造成第1到第9個(gè)位置的存儲(chǔ)關(guān)鍵字在第9個(gè)位置的大量堆積現(xiàn)象，造成某些關(guān)鍵字的查找次數(shù)增加，使平均查找長(zhǎng)度加大。為了克服堆積現(xiàn)象的發(fā)生，可以用下面的方法替代線性探查法。（2）平方探查法該方法規(guī)定，若在d地址發(fā)生沖突，下一次探查位置為d+12，d+22，…，直到找到一個(gè)空閑位置為止。2023年11月28日67算法描述如下：voidcreat2(elemtypeHT[m],intn){inti,j,d;elemtypek;for(i=0;i<m;i++)HT[i]=NULL;for(i=1;i=n;i++){cin>>k;j=H(k);d=1;while(HT[j]!=NULL){j=(j+d*d)%m;d++;}HT[j]=k;}}平方探查法是一種比較理想的處理沖突方法，它能夠較好地避免堆積現(xiàn)象。它的缺點(diǎn)是不能探查到散列表上的所有單元，但至少能探查到一半單元。例如，若表長(zhǎng)m=13，假設(shè)在第3個(gè)位置發(fā)生沖突，則后面探查的位置依次為4、7、12、6、2、0，即可以探查到一半單元。若解決沖突時(shí)，探查到一半單元仍找不到一個(gè)空閑單元，則表明此散列表太滿，需重新建立散列表。2023年11月28日68（3）雙散列函數(shù)探查法該方法使用兩個(gè)散列函數(shù)H和T，用H作散列函數(shù)建立散列存儲(chǔ)（散列表），用T來(lái)解決沖突。具體實(shí)施時(shí)，若H(k)在d0位置發(fā)生沖突，即d0=H(k)，則下一個(gè)探查位置序列應(yīng)該是di=(di-1+T(k))%m(1≤i≤m-1)。算法描述如下:voidcreat3(elemtypeHT[m],intn){inti,j,d;elemtypek;for(i=0;i<m;i++)HT[i]=NULL;for(i=1;i<=n;i++){cin>>k;j=H(k);d=T(k);while(HT[j]!=NULL)j=(j+d)%m;HT[j]=k;}}2023年11月28日692．拉鏈法拉鏈法也稱鏈地址法，是把相互發(fā)生沖突的同義詞用一個(gè)單鏈表鏈接起來(lái)，若干組同義詞可以組成若干個(gè)單鏈表?！纠?-6】對(duì)例8-5給定的關(guān)鍵字序列19，14，23，1，68，20，84，27，55，11，10，79，給定散列函數(shù)為H(k)=k%13，試用拉鏈法解決沖突建立散列表。由于H(14)=H(1)=H(27)=H(79)=1，故14、1、27、79互為同義詞，組成一個(gè)單鏈表；H(68)=H(55)=3，故68、55互為同義詞，組成一個(gè)單鏈表；H(19)=H(84)=6，故19、84互為同義詞，組成一個(gè)單鏈表；H(23)=H(10)=10，故23、10互為同義詞，組成一個(gè)單鏈表；H(26)=7單獨(dú)組成一個(gè)單鏈表，H(11)=11單獨(dú)組成一個(gè)單鏈表。H(k)為0，2，4，5，6，8，9，12時(shí)，無(wú)對(duì)應(yīng)關(guān)鍵字，故這些單鏈表為空。2023年11月28日70圖8-22為用尾插法建立的關(guān)于例8-6的拉鏈法解決沖突的散列表。圖8-22拉鏈法解決沖突的散列表2023年11月28日71拉鏈法建立散列表的算法描述如下（類似于圖的鄰接表）：structLnode{elemtypedata;Lnode*next;};constintm=maxm; //maxm代表散列表長(zhǎng)度constintn=maxn; //maxn代表關(guān)鍵字個(gè)數(shù)voidcreat4(Lnode*HT[m],intn){inti,j;elemtypek;for(i=0;i<m;i++)HT[i]=NULL;for(i=1;i<=n;i++){cin>>k; //輸入一個(gè)關(guān)鍵字j=H(k); //H(k)為散列函數(shù)s=newLnode; //申請(qǐng)一個(gè)結(jié)點(diǎn)s->data=k;s->next=HT[j]->next; //頭插法建鏈表HT[j]->next=s; //頭插法建鏈表}}2023年11月28日728.4.4散列查找算法實(shí)現(xiàn)1．線性探查法的查找intfind1(elemtypeHT[m],elemtypek)//在散列表HT中查找關(guān)鍵字k{intj=H(k);if(HT[j]==NULL)reurn–1; //查找失敗elseif(HT[j]==k)returnj; //一次查找成功else{while(HT[j]!=k)&&(HT[j]!=NULL)j=(j+1)%m;if(HT[j]==NULL)return-1; //多次查找失敗

elsereturnj; //多次查找成功}}2023年11月28日732．平方探查法的查找intfind2(elemtypeHT[m],elemtypek)//在散列表HT中查找關(guān)鍵字k{intj,d;j=H(k);if(