《數(shù)據(jù)結(jié)構(gòu)單元7查找課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)單元7查找課件.ppt（48頁珍藏版）》請在匯文網(wǎng)上搜索。

1、國家教學(xué)資源庫建設(shè)項目國家教學(xué)資源庫建設(shè)項目數(shù)據(jù)結(jié)構(gòu)單元單元7 7 查找查找2數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 教學(xué)目標(biāo)教學(xué)目標(biāo)【知識目標(biāo)知識目標(biāo)】了解查找的基本概念掌握順序查找的基本思想、算法實現(xiàn)和查找效率分析掌握二分查找的基本思想、算法實現(xiàn)和查找效率分析掌握分塊查找的基本思想、算法實現(xiàn)和查找效率分析掌握二叉查找樹的插入、刪除、建樹和查找算法及時間性能掌握哈希查找方法、哈希函數(shù)的構(gòu)造和解決沖突的方法【能力目標(biāo)能力目標(biāo)】具有選擇恰當(dāng)?shù)牟樵兯惴ń鉀Q實際問題的能力 單元單元7 7 查找查找3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 引例描述引例描述高校最低錄取分?jǐn)?shù)線查詢高校最低錄取分?jǐn)?shù)線查詢 該系統(tǒng)用于學(xué)生、學(xué)生家長和其他人員查詢各高校

2、的最低錄取分?jǐn)?shù)線，為他們的了解高校錄取情況、做出正確的選擇和決策提供有必要的信息。該系統(tǒng)有以下六項功能：（1）按考生分?jǐn)?shù)查詢高校信息；（2）按給定分?jǐn)?shù)查詢一定范圍內(nèi)的高校信息，包括：查詢錄取分?jǐn)?shù)線比給定分?jǐn)?shù)高（包括相等）的高校信息和錄取分?jǐn)?shù)線比給定分?jǐn)?shù)低（包括相等）的高校信息；（3）按給定的分?jǐn)?shù)范圍查詢高校信息；（4）能夠添加高校信息；（5）為用戶提供系統(tǒng)幫助，以便更好的使用系統(tǒng)；（6）安全退出本系統(tǒng)。演示執(zhí)行演示執(zhí)行 單元單元7 7 查找查找4數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 一、基本概念一、基本概念1查找定義查找定義 給定一個值K，在含有n個結(jié)點(diǎn)的表中找出關(guān)鍵字等于給定值K的結(jié)點(diǎn)。若找到，則查找成功，返回

3、該結(jié)點(diǎn)的信息或該結(jié)點(diǎn)在表中的位置；否則查找失敗，返回相關(guān)的指示信息。2動態(tài)查找表和靜態(tài)查找表動態(tài)查找表和靜態(tài)查找表 若在查找的同時對表做修改操作（如插入和刪除），則相應(yīng)的表稱之為動態(tài)查找表。否則稱之為靜態(tài)查找表。3內(nèi)查找和外查找內(nèi)查找和外查找 若整個查找過程都在內(nèi)存進(jìn)行，則稱之為內(nèi)查找；反之，若查找過程中需要訪問外存，則稱之為外查找。7.1 查找的基本概念查找的基本概念 知識儲備知識儲備單元單元7 7 查找查找5數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 4平均查找長度（平均查找長度（Average Search Length）ASL 查找運(yùn)算的主要操作是關(guān)鍵字的比較，所以通常把查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)

4、（也稱為平均查找平均查找長度長度）作為衡量一個查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。平均查找長度平均查找長度 ASL定義：定義：即ASL等于每個結(jié)點(diǎn)的查找概率pi與比較次數(shù)ci的乘積的和。其中：（1）n是結(jié)點(diǎn)的個數(shù)；（2）pi是查找第i個結(jié)點(diǎn)的概率。若不特別聲明，認(rèn)為每個結(jié)點(diǎn)的查找概率相等，即pl=p2=pn=1/n；（3）ci是找到第i個結(jié)點(diǎn)所需進(jìn)行的比較次數(shù)。單元單元7 7 查找查找6數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 一、順序查找（一、順序查找（sequential search）順序查找又稱線性查找，是最基本的查找方法之一。順序查找既適用于順序表，也適用于鏈表。1基本思想基本思想 從表的一端開始，順序掃描線性表，依次

5、按給定值kx與關(guān)鍵字（Key）進(jìn)行比較，若相等，則查找成功，并給出數(shù)據(jù)元素在表中的位置；若整個表查找完畢，仍未找到與kx相同的關(guān)鍵字，則查找失敗，給出失敗信息。2基于順序結(jié)構(gòu)的順序查找算法的類型描述基于順序結(jié)構(gòu)的順序查找算法的類型描述 7.2 靜態(tài)查找靜態(tài)查找#define N 20typedef int KeyType;/關(guān)鍵字字段類型定義typedef char OtherdataType;/非關(guān)鍵字字段類型定義typedef structKeyType key;OtherdataType data;NodeType;typedef NodeType SeqListN+1;/0號單元用作監(jiān)

6、視哨單元單元7 7 查找查找7數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3具體算法具體算法4算法分析算法分析（1）算法中監(jiān)視哨）算法中監(jiān)視哨R0的作用的作用 為了在for循環(huán)中省去判定防止下標(biāo)越界的條件i1，從而節(jié)省比較的時間。（2）成功時的順序查找的平均查找長度）成功時的順序查找的平均查找長度 在等概率情況下，pi=1/n(1in)，故成功的平均查找長度為(n+2+1)/n=(n+1)/2，即查找成功時的平均比較次數(shù)約為表長的一半，若K值不在表中，則須進(jìn)行n+1次比較之后才能確定查找失敗。（3）順序查找的優(yōu)缺點(diǎn)）順序查找的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)是算法簡單，且對表的結(jié)構(gòu)無任何要求，無論是用向量還是用鏈表來存放結(jié)點(diǎn)，也無論結(jié)點(diǎn)之

7、間是否按關(guān)鍵字有序，它都同樣適用。缺點(diǎn)是查找效率低，因此，當(dāng)n較大時不宜采用順序查找。int SeqSearch(Seqlist R,KeyType K)/在順序表R1.n中查找關(guān)鍵字為K的結(jié)點(diǎn)int i;R0.key=K;/設(shè)置哨兵for(i=n;Ri.key!=K;i-);/從表后往前找return i;/若i為0，表示查找失敗，否則Ri是要找的結(jié)點(diǎn) 單元單元7 7 查找查找8數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 2二、二分查找（二、二分查找（binary search）1二分查找：二分查找：二分查找又稱折半查找，它是一種效率較高的查找方法。二分查找要求：二分查找要求：線性表是有序表，即表中結(jié)點(diǎn)按關(guān)鍵字有序，

8、并且要用向量作為表的存儲結(jié)構(gòu)。不妨設(shè)有序表是遞增有序的。2二分查找的基本思想二分查找的基本思想 設(shè)Rlow.high是當(dāng)前的查找區(qū)間。（1）首先確定該區(qū)間的中點(diǎn)位置：mid=(low+high)/2;（2）然后將待查的K值與Rmid.key比較：若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下：單元單元7 7 查找查找9數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 若Rmid.keyK，則由表的有序性可知Rmidn.key均大于K，因此若表中存在關(guān)鍵字等于K的結(jié)點(diǎn),則該結(jié)點(diǎn)必定是在位置mid左邊的子表R1mid-1中，故新的查找區(qū)間是左子表R1.mid-1；若Rmid.keyK，類似地，

9、則新的查找區(qū)間是右子表Rmid+1n。下次在新的查找區(qū)間進(jìn)行查找。因此，從初始的查找區(qū)間R1.n開始，每經(jīng)過一次與當(dāng)前查找區(qū)間的中點(diǎn)位置上的結(jié)點(diǎn)關(guān)鍵字的比較，就可確定查找是否成功，不成功則當(dāng)前的查找區(qū)間就縮小一半。這一過程重復(fù)直至找到關(guān)鍵字為K的結(jié)點(diǎn)，或者直至當(dāng)前的查找區(qū)間為空（即查找失?。r為止。單元單元7 7 查找查找10數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3二分查找算法二分查找算法int BinSearch(SeqList R,KeyType K)int low=1,high=n,mid;/置當(dāng)前查找區(qū)間的初值while(lowK)high=mid-1;elselow=mid+1;return 0;/當(dāng)l

10、owhigh時查找區(qū)間為空，查找失敗 單元單元7 7 查找查找11數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 4算法分析算法分析（1）二分查找的平均查找長度：）二分查找的平均查找長度：在等概率假設(shè)下，二分查找成功時平均查找長度為：ASLbn=(n+1)/n)lg(n+1)-1；最壞情況下查找成功的比較次數(shù)為：。（2）二分查找的優(yōu)缺點(diǎn)：）二分查找的優(yōu)缺點(diǎn)：二分查找效率高，但要將表按關(guān)鍵字排序；二分查找只適用順序存儲結(jié)構(gòu)。對經(jīng)常進(jìn)行插入和刪除操作的表，不宜采用此方法。單元單元7 7 查找查找12數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 三、三、分塊查找（分塊查找（block search）分塊查找又稱索引順序查找。它是一種性能介于順序查找和二分查

11、找之間的查找方法。1二分查找表存儲結(jié)構(gòu)二分查找表存儲結(jié)構(gòu) 二分查找表由“分塊有序”的線性表和索引表組成。（1）“分塊有序分塊有序”的線性表：的線性表：表R1.n均分為b塊，前b-1塊中結(jié)點(diǎn)個數(shù)為是s=n/b，第b塊的結(jié)點(diǎn)數(shù)小于等于s；每一塊中的關(guān)鍵字不一定有序，但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即表是“分塊有序”的。（2）索引表：）索引表：抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個索引表IDl.b，即：IDi(1ib)中存放第i塊的最大關(guān)鍵字及該塊在表R中的起始位置。由于表R是分塊有序的，所以索引表是一個遞增有序表?！臼纠繄D7-1給出的就是滿足上述要求的存儲結(jié)構(gòu)，其中R只有

12、15個結(jié)點(diǎn)，被分成3塊，每塊中有5個結(jié)點(diǎn)，第一塊中最大關(guān)鍵字22小于第二塊中最小關(guān)鍵字24，第二塊中最大關(guān)鍵字44小于第三塊中最小關(guān)鍵字47。圖圖7-1 7-1 分塊查找分塊查找2247416111234567891011121314152212139833424438244860587447最大關(guān)鍵字值最大關(guān)鍵字值塊地址塊地址IDR單元單元7 7 查找查找13數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 2分塊查找的基本思想分塊查找的基本思想 先在索引表中采用二分查找或順序查找，以確定待查的結(jié)點(diǎn)在哪一塊；然后在已確定的塊中進(jìn)行順序查找。3算法分析算法分析（1）平均查找長度）平均查找長度ASL：將含有n個元素的線性表平均

13、分成b塊，每塊有s個元素。整個查找過程的平均查找長度是兩次查找的平均查找長度之和。以二分查找來確定塊，分塊查找成功時的平均查找長度ASLblk=ASLbn+ASLsq=lg(b+1)-1+(s+1)/2。以順序查找確定塊，分塊查找成功時的平均查找長度ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)。（2）分塊查找的優(yōu)缺點(diǎn)：）分塊查找的優(yōu)缺點(diǎn)：在表中插入或刪除記錄時，只要找到該記錄所屬的塊，就在該塊內(nèi)進(jìn)行插入和刪除運(yùn)算；因塊內(nèi)記錄的存放是任意的，所以插入或刪除無須移動大量記錄；分塊查找的主要代價是增加輔助存儲空間和將初始表分塊排序的運(yùn)算。單元單元7 7 查找查找14數(shù)據(jù)

14、結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 一、二叉排序樹（一、二叉排序樹（Binary Sort Tree）1二叉排序樹的定義二叉排序樹的定義 二叉排序樹又稱二叉查找（搜索）樹（Binary Search Tree）。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質(zhì)的二叉樹：（1）若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；（2）若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；（3）左、右子樹本身又各是一棵二叉排序樹。上述性質(zhì)簡稱二叉排序樹性質(zhì)（BST性質(zhì)），故二叉排序樹實際上是滿足BST性質(zhì)的二叉樹。7.3 動態(tài)查找動態(tài)查找 單元單元7 7 查找查找15數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 2二叉排序樹的特點(diǎn)二叉

15、排序樹的特點(diǎn)（1）二叉排序樹中任一結(jié)點(diǎn)x，其左(右)子樹中任一結(jié)點(diǎn)y（若存在）的關(guān)鍵字必?。ù螅┯趚的關(guān)鍵字。（2）二叉排序樹中，各結(jié)點(diǎn)關(guān)鍵字是惟一的。（3）按中序遍歷該樹所得到的中序序列是一個遞增有序序列。注意：注意：實際應(yīng)用中，被查找的數(shù)據(jù)集中各元素的關(guān)鍵字可能相同，所以可將BST性質(zhì)（1）里的“小于”改為“小于等于”，或?qū)⑿再|(zhì)（2）里改為“大于等于”。【示例】如圖7-2所示的兩棵樹均是二叉排序樹，滿足BST性質(zhì)，它們的中序序列均為有序序列2，3，4，5，7，8。圖圖7-2-2 二叉排序樹二叉排序樹238574(a)(b)723845單元單元7 7 查找查找16數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3二叉排序

16、樹的結(jié)構(gòu)描述二叉排序樹的結(jié)構(gòu)描述 typedef int KeyType;/關(guān)鍵字類型定義typedef char OtherdataType;/非關(guān)鍵字字段類型定義typedef struct node /結(jié)點(diǎn)類型KeyType key;/關(guān)鍵字項OtherdataType data;/其它數(shù)據(jù)域struct node*lchild,*rchild;/左右孩子指針 BSTNode;typedef BSTNode*BSTree;/BSTree是二叉排序樹的類型單元單元7 7 查找查找17數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 二、二叉排序樹上的運(yùn)算二、二叉排序樹上的運(yùn)算1二叉排序樹的插入二叉排序樹的插入 二叉排序樹插入新結(jié)點(diǎn)的過程：在二叉排序樹中插入新結(jié)點(diǎn)，要保證插入后仍滿足BST性質(zhì)。插入過程是：（1）若二叉排序樹T為空，則為待插入的關(guān)鍵字key申請一個新結(jié)點(diǎn)，并令其為根；（2）若二叉排序樹T不空，則將key和根的關(guān)鍵字比較：若二者相等，則樹中已有此關(guān)鍵字key，無須插入；若keykey，則將key插入根的左子樹中；若keyT-key，則將它插入根的右子樹中。子樹中的插入過程與上述的樹中插入過程相同。如此