1、1數 據 結 構（第九章 查找） Data Structures張晶計算機與信息(xnx)學院 2022/7/25共六十頁2第九章 查 找 第九章 查 找 9.1 概述 9.2 順序表的查找(ch zho) 9.3 樹表的查找 9.4 散列表的查找 共六十頁39.1 概述(i sh)查找是現實生活和軟件設計中最常用的運算，例如，查字典、辭典、電話號碼(din hu ho m)，高考成績查詢 ，考試成績查詢因此，查找方法的性能會影響到軟件系統的性能。對此，涉及到幾個相關的問題：如何設計查找方法？如何評價查找性能？如何組織數據，以便能更好地提高查找的性能？本章主要內容：介紹查找的相關概念，圍繞幾種

2、常見的數據表， 討論查找的方法，并分析其性能。 共六十頁49.1 概述(i sh)查找： 在數據集（表）中找出一個特定元素（的位置）。這一概念中涉及到以下幾個相關的問題：（1）數據表：什么樣數據表？ 也就是數據表的組織形式？例如：漢語字典、英語辭典；一個城市的電話號碼簿。高考成績表。查找表： 同類型的數據元素（記錄）所構成的集合。 順序表：數據元素構成一個序列。 樹表：以樹結構的形式組織。 散列表：以某種函數的方式來確定(qudng)元素的地址，實現數據表的組織。 索引表：為元素建立索引，以提高查找的速度。顯然，查找的方法取決于數據表的組織形式。例如：在漢語字典和英語辭典中的查找就有明顯差異。

3、因此，需要注意：如何確定查表結構？如何實現對給定數據表的查找？共六十頁59.1 概述(i sh)（2）關于其中的特定元素 如何標識所需要(xyo)查找的元素？以高考成績為例，顯然是以準考證號標識的。更一般地說，涉及到字段 字段：如第一章所述，一個元素通常包括多個字段， 查找表中的元素也由多個字段（項）組成。例如，高考成績信息中，包括姓名、準考證號、各單科成績和總分等字段。 稱其中可以標識元素的字段關鍵字，分兩種情況： 主關鍵字：唯一標識一個元素的字段例如，高考成績信息中的“準考證號”字段。次關鍵字：可能標識到多個元素的字段例如，高考成績信息中的“考生姓名”字段， 因為現實中有太多同名同姓的人。

4、共六十頁69.1 概述(i sh)（3）如何查找？取決于查找表的組織方式。例如：漢語字典的查找方法；英語詞典的查找方法；某單位通信錄中查找特定單位的方法等。（4）查找成功和查找失敗：若找到指定的元素，則稱為查找成功；否則稱為查找失敗 （5）如何評價查找方法的性能？以查找長度來描述(mio sh)查找長度： 查找過程中所做的元素或關鍵字的比較次數。 涉及到: 平均查找長度ASL， 最大查找長度 失敗查找長度共六十頁79.2 順序(shnx)表的查找問題描述： 查找表以順序結構來存儲，典型(dinxng)地是一維數組；也可能是鏈表，或順序文件本章更多地討論是面向一維數組要求在此表中找出關鍵字的值為

5、x的元素的位置，若查找成功，則返回其位置（即下標），否則，返回一個表示元素不存在的下標（如0或-1）。按照查找表中數據的特性，以及對應的查找方法，可分為以下幾種：簡單順序查找-沒有任何關于數據元素分布的特性有序表查找-二分查找（折半查找）索引表查找-數據表分塊有序共六十頁89.2 順序(shnx)表的查找9.2.1 簡單順序查找 問題描述:在數組An中查找元素關鍵字為x的元素，若查找成功，則返回(fnhu)元素的下標，否則返回(fnhu)-1。分析：顯然只能依次搜索（比較元素）。按照什么樣的查找順序？即從前往后還是從后往前？A01234in-1a1a2a3a4a5ai-1anX共六十頁99.2

6、.1簡單順序(shnx)表的查找簡單順序(shnx)查找 從左向右int search ( elementtype A， keytype x) int i; for(i=0;in;i+) if (Ai.key=x) return(i); return(-1);i=0i=0;i-) if (Ai.key=x) return(i); return(-1);分析：比較操作的次數i=n-1;i=0Ai.key=xi-;NY未找到找到了A01234in-1a1a2a3a4a5ai-1aniY返回-1返回iN共六十頁119.2.1簡單順序(shnx)表的查找簡單(jindn)順序查找 從右向左+監視哨in

7、t search ( elementtype A， keytype x) int i; A0.key=x; while (Ai.key != x) i-; return(i);i=n-1;A0.key=x;Ai.key=xi-;NY未找到找到了A01234in-1a1a2a3a4a5ai-1aniY返回-1返回iNi=0共六十頁129.2.1簡單(jindn)順序表的查找算法分析 各元素(yun s)的查找長度： 1,2,3,n (或n-1: 設置監視哨時)等概率情況下的平均查找長度： ASL=(1+2+n)/n=(n+1)/2 失敗查找長度=n+1A01234in-1a1a2a3a4a5ai

8、-1ani共六十頁139.2.2 有序表的查找(ch zho)二分查找問題描述:在遞增有序（或遞減有序，在此不妨采用遞增）數組An中查找元素關鍵字為x的元素，若查找成功，則返回元素的下標，否則(fuz)返回-1。典型實例：英語詞典中查單詞。按照什么樣的方式查找更好？簡單順序查找二分查找A01234in-1a1a2a3a4a5ai-1an共六十頁149.2.2 有序表的查找(ch zho)二分查找查找方法描述：設查找區域的首尾下標分別為low和high（初值分別為0和n-1，取待查關鍵字x和區域的中間元素 (其下標mid=(low+high)/2) 的關鍵字進行比較，并根據比較的結果(ji gu

9、)分別作相應的處理：(1) x=Amid.key: 查找成功，返回mid的值。(2) xAmid.key: 說明待查元素只可能在右邊區域 下標：mid+1high) 。因此，應在此區域繼續查找。若表中存在所要查找的元素，則經上述若干次后，即可找到。問題是：如果不存在指定的元素，如何能判斷出來？ A01234in-1a1a2a3a4a5ai-1anhighlowmid共六十頁159.2.2 有序表的查找(ch zho)二分查找有序查找二分(r fn)查找（折半查找）例：在09號元素中查找元素值為47的元素2391530424753861000123456789lowhighmidhighlowm

10、idhighlowmidhighlowmid239153042475386100239153042475386100239153042475386100成功！問題：如果不存在所要搜索的元素，如何判斷出來？共六十頁169.2.2 有序表的查找(ch zho)二分查找算法(sun f)流程圖二分查找算法如下:int bin_search(elementtype A ,int n, keytype x) int mid,low=0,high=n-1; /初始化查找區域 while ( low=high) mid=(low+high)/2; if (x=Amid.key) return mid; el

11、se if (xAmid.key) high=mid-1; else low=mid+1; return -1; /返回查找失敗的標志XAmid.keyhigh=mid-1low=mid+1查找成功return midlowhigh) return -1; else mid=(low+high)/2; if (Amid.key= =x) return mid; else if(xAmid.key) return binsearch( A ,x,low,mid-1); else return binsearch( A ,x,mid+1,high); 遞歸算法(sun f)：參數？XAmid.ke

12、yhigh=mid-1low=mid+1查找成功return midlow=highmid=(low+high)/2low=0;high=n-1;Yreturn-1;N共六十頁189.2.2 有序表的查找(ch zho)二分查找算法分析：借助二分查找判定(pndng)樹來描述A01234in-1a1a2a3a4a5ai-1an5160231315109168017917079121417024746771211111214161717例：有序表A18 最壞查找長度=log2n+1共六十頁199.2.2 有序表的查找(ch zho)二分查找練習：采用二分查找法查找018號元素(yun s)，其中

13、查找長度為5的元素是 哪些？ 則查找長度為5的元素有3，8，13，18。共六十頁209.2 順序(shnx)表的查找9.2.3 索引表的查找(ch zho) 一些數據表具有這樣的特性：分塊有序塊間有序，塊內無序。如下圖所示：為便于查找， 可這樣處理：為每一塊設立一個塊首指針，并標注對應塊中的最大（小）關鍵字（可能是潛在的，不一定出現）將這兩項內容合并為一個索引項各索引項合在一起構成索引表。9092959185888678707762656390807060索引項索引表lchild;XT-data.keyT=T-rchild ;找到5040473020354549709065556780100T

14、二叉排序樹的查找 如何在二叉排序樹中查找給定關鍵字的結點？ 以在下圖所示樹中分別查找45、55、66為例來說明。 由此可得到(d do)查找的判定過程。 判定過程類似于二分查找的判定過程。失敗！共六十頁269.3.1 二叉排序(pi x)樹二分查找(ch zho)算法的流程圖XP-data.keyP=P-lchild;P=P-rchild;查找成功return PP!=NULLP=TYreturn NULL;N查找的非遞歸算法： bnode *bstsearch(bnode *T， elementtype x) p=T; while ( p != NULL ) if ( p - data =

15、= x ) return p; if ( x data ) p = p - lchild; else p = p - rchild; return NULL; 共六十頁279.3.1 二叉排序(pi x)樹 查找(ch zho)的遞歸算法： bnode *bstsearch(bnode *T, elementtype x) if ( T = NULL ) return T; if (T - data = x ) return T; if (x data) return bstsearch(T-lchild,x); else return bstsearch(T-rchild,x); XP-da

16、ta.keyP=P-lchild;P=P-rchild;查找成功return PP!=NULLP=TYreturn NULL;N共六十頁289.3.1 二叉排序(pi x)樹二叉排序樹的構造：從空樹出發，依次(yc)插入各結點（作為葉子結點）。二叉排序樹中插入結點：(1)若結點的值小于根結點的值， 則往左子樹中插入 -通過遞歸調用插入算法來實現。(2)若結點的值大于等于根結點的值， 則往右子樹中插入（遞歸調用）。按此方式遞歸調用若干次后， 可以搜索到一個空子樹位置，即要插入的位置。共六十頁299.3.1 二叉排序(pi x)樹構造過程：依次(yc)將結點作為葉結點插入到二叉排序樹中例：以下列數

17、據序列作為輸入構造一棵二叉排序樹。100，65，88，93，145，118，138，112，188，173，42，78，20, 197100654220789388118112138173197188145共六十頁309.3.1 二叉排序(pi x)樹二叉排序樹的插入算法(sun f)逐個插入元素來實現構造，插入的元素作為葉子結點。 void insert(bnode *& T, bnode *s) / 將s所指結點插入到以T為根指針的二叉排序樹中 if ( T = = NULL ) / T 為空時 T = = s; / 新結點作為根結點 else if ( s-data data ) ins

18、ert( T - lchild, s ); else insert( T - rchild, s ); 共六十頁319.3.1 二叉排序(pi x)樹二叉排序樹的構造算法void creat(bnode *&T) / 接受(jishu)讀入數據，從空樹開始構造二叉排序樹 T= =NULL; cinx; while (x!=結束符) s=new bnode; s - data=x; s - lchild=NULL; s - rchild=NULL; insert(T,s); cinx; 共六十頁329.3.1 二叉排序(pi x)樹二叉排序樹構造分析： 以下列數據序列作為輸入(shr)構造一棵二

19、叉排序樹。 100，65，88，93，145，118，138，112，188，173，42，78，20，197平均查找長度： （1223447）/14 = 45/14100654220789388118112138173197188145共六十頁339.3.1 二叉排序(pi x)樹二叉排序樹構造分析： 再看以下列數據序列作為輸入(shr)構造一棵二叉排序樹。20，42，65，78，88，93，100，112，118，138，145，173，188,197平均查找長度： （1214）/14 = 105/1420426578.由此而提出平衡二叉樹共六十頁349.3.1 二叉排序(pi x)樹二叉

20、排序樹刪除結點：刪除二叉排序樹中的結點可分幾種(j zhn)情況來實現 ：葉子結點 直接刪除即可非葉子結點頂替法重新連接法100654220789388118112138173197188145刪除葉子781006542209388118112138173197188145刪除非葉子4220100654220789388118112138173197188145刪除非葉子145173共六十頁359.3 樹表的查找(ch zho) 9.3.2 平衡二叉樹 定義：平衡二叉樹是一棵二叉排序樹，或者為空， 或者滿足以下(yxi)條件： 1)左右子樹高度差的絕對值不大于1； 2)左右子樹都是平衡二叉樹。

21、 平衡因子： 左子樹的高度減去右子樹的高度，顯然，在平衡二叉樹中， 每個結點的平衡因子的值為-1，0或1。 共六十頁369.3 樹表的查找(ch zho) 平衡二叉樹如何構造平衡二叉樹（樹） 在平衡的二叉排序樹中插入一個結點，當出現不平衡時，根據不平衡情況分四種調整方法 假設最低不平衡結點為A，根據新插入結點與A的位置關系來命名(mng mng)調整方法： LL型：新插入結點在A的左孩子(L)的左子樹(L)中； LR型：新插入結點在A的左孩子(L)的右子樹(R)中； RL型：新插入結點在A的右孩子(R)的左子樹(L)中； RR型：新插入結點在A的右孩子(R)的右子樹(R)中。共六十頁379.3

22、 樹表的查找(ch zho) 平衡二叉樹LL型（圖示）：ABCLL型BCAABBLBRARh+2hLL型ABBLBRAR共六十頁389.3 樹表的查找(ch zho) 平衡二叉樹LR型（圖示）：ABCLR型CBAABBLCLARh+2hLR型ACCRARCCRBBRCL共六十頁399.3 樹表的查找(ch zho) 平衡二叉樹RL型（圖示）：ABCRL型CABABALCLBRhh+2RL型BCCRBRCCRAARCL共六十頁409.3 樹表的查找(ch zho) 平衡二叉樹RR型（圖示）：ABCRR型BACABBLBRARh+2hRR型ABBLARBR共六十頁419.3 樹表的查找(ch zh

23、o) 平衡二叉樹構造練習：依次輸入(shr)下列數據構造一棵平衡二叉樹： 100，90，80，60，70，50，120，110，150，87。1009080LL型90801006070LR型9070100608050LL型9070100608050120110共六十頁429.3 樹表的查找 平衡(pnghng)二叉樹構造(續1)練習：依次輸入(shr)下列數據構造一棵平衡二叉樹： 100，90，80，60，70，50，120，110，150，87。9070100608050120110RL型9070110608050100120150RR型7060501109080100120150共六十頁4

24、39.3 樹表的查找(ch zho) 平衡二叉樹構造(續2)練習(linx)：依次輸入下列數據構造一棵平衡二叉樹： 100，90，80，60，70，50，120，110，150，87。706050110908010012015087RL型706050110908010012015087共六十頁449.3 樹表的查找(ch zho) 平衡二叉樹思考：至少要用7個數作為輸入序列，構造一棵平衡二叉樹， 構造過程中同時包含4種調整方法。請給出這樣的序列。在構造平衡二叉樹的過程中， 若A的平衡因子變為-2，A的左孩子的平衡因子為0， 右孩子的平衡因子為1，則進行何種調整？ 求高度(god)為n的平衡二叉

25、樹至少需要的結點個數。 一棵平衡二叉樹中的葉子結點高度之差能不能超過2？共六十頁459.3 樹表的查找(ch zho)9.3.3 B-樹定義：m階B-樹(m3)滿足如下條件： 1) 每一個結點分支數m; 2) 根結點分支數2(要求此根結點不為葉子結點)； 3) 其余分支結點的分支數 m/2 ； 4) 所有葉子結點在同一層； 5) 每一個結點的結構如下： 滿足： k1 kn 其中 表示Ai中的所有關鍵字，并且在結點中定義 keynum：記錄結點中的關鍵字個數， keysm：存儲(cn ch)結點中的各關鍵字， ptrsm+1：存儲結點中各指針。Ai k1k2.Kn A0A1A2AnA0A1An共

26、六十頁469.3.3 B-樹3階B-樹：例如(lr)：10060150 20020 4070 90120 140180210 260B-樹的查找：以上(yshng)圖為例，分別查找40、150、210、230等，由此，可得到查找算法共六十頁479.3.3 B-樹B-樹（插入）插入關鍵字插入方法：首先，插入到葉子(y zi)結點中，此時，若不溢出，則結束否則，分解結點（一分為二） 并且可能要執行多次10060150 20020 4070 90120 140180210 260180 190插入(ch r)190共六十頁489.3.3 B-樹插入(ch r)關鍵字10060150 20020 40

27、70 90120 140180 190210 260插入(ch r)160160 180 190160190150 180 2001006020 4070 90120 140210 260共六十頁499.3.3 B-樹插入(ch r)關鍵字插入(ch r)160160190150 180 2001006020 4070 90120 140210 260160190200100 1806020 4070 90120 140210 260150共六十頁509.3.3 B-樹刪除關鍵字若刪除的關鍵字不在葉子結點中，用其前驅或后繼來替換刪除葉子結點中的關鍵字 刪除關鍵字后依然能滿足B-樹的條件，則結束 否則，若左右兄弟(xingd)中有多余的關鍵字，則調整一下，否則合三為一。10060150 20020 4070 90120 1401