典型查找算法編程第一頁，共三十頁，2022年，8月28日第8章

典型查找算法

8.1實例：學(xué)生分配座位8.2靜態(tài)查找8.3動態(tài)查找8.4散列查找本章總結(jié)第二頁，共三十頁，2022年，8月28日8.1實例：學(xué)生分配座位

8.1.1問題描述

8.1.2問題的分析

8.1.3實現(xiàn)算法

8.1.4基本概念

第三頁，共三十頁，2022年，8月28日8.1.1問題描述

教室中的學(xué)生座位分配是一個最簡單的例子。假定某教室有35個座位，如果不加限定任意就坐或按某種規(guī)律就座，則要查找某學(xué)生時就要將待查找的學(xué)生與當(dāng)前座位上的學(xué)生進(jìn)行比較。

第四頁，共三十頁，2022年，8月28日8.1.2問題的分析

用計算機來解決查找學(xué)生問題，通常需要做以下工作：第一，學(xué)生信息以什么形式表示和存儲；第二，查找的具體實現(xiàn)方法(算法)。第五頁，共三十頁，2022年，8月28日structstudent{intnum1;//表示座號intnum2;//表示學(xué)號charname[12];//表示姓名

┆}；structlist{Studentstu[size];//保存學(xué)生記錄Intlen;//學(xué)生人數(shù)};

學(xué)生信息的存儲方式：第六頁，共三十頁，2022年，8月28日

從第一個學(xué)生開始，依次與查找的學(xué)生進(jìn)行比較。在查找過程中，若某個學(xué)生的記錄與所查找學(xué)生記錄相等，則查找成功，返回該學(xué)生在表中位置；若全部比較完畢，沒有符合條件的學(xué)生記錄，則查找不成功，返回-1。查找學(xué)生的方法：第七頁，共三十頁，2022年，8月28日8.1.3實現(xiàn)算法

intsearch(List&L,int,s)//從表L.stu[0],L.stu[1],……L.stu[n-1]的n個元素中查找關(guān)鍵字為S元素，若查找成功返回該生學(xué)號，否則返回-1{inti;for(i=0;i<L.len;i++)if(L.stu[i]==S)break;if(i<n)returnL.stu[i].num2;elsereturn-1;}第八頁，共三十頁，2022年，8月28日8.1.4基本概念

查找表：利用計算機查找時，首先要確定原始數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，變?yōu)橛嬎銠C中處理的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)稱為存儲表。

查找：在一個含有眾多數(shù)據(jù)元素(或記錄)的查找表中找出某個“特定的”數(shù)據(jù)元素（或記錄）。查找成功，返回該記錄的存儲位置；查找失敗，返回一個特定值。平均查找長度：在查找成功情況下的平均比較次數(shù)。對于含有n個記錄的表，查找成功時的平均查找長度為：

ASL=其中：Ci為查找第i個元素時同給定值K進(jìn)行比較的次數(shù)；Pi為查找第i個記錄的概率，且

在等概率情況下，則P1=P2=…=Pn=第九頁，共三十頁，2022年，8月28日8.2靜態(tài)查找8.2.1順序查找

8.2.2折半查找

8.2.3分塊查找

第十頁，共三十頁，2022年，8月28日8.2靜態(tài)查找

查找過程中，進(jìn)行如下操作：查詢某個特定的數(shù)據(jù)元素是否在查找表中或檢索某個數(shù)據(jù)元素的各種屬性。此查找表稱為靜態(tài)查找表(StaticSearchTable)。查找表定義為順序存儲的線性表，數(shù)據(jù)類型定義如下：structElemtype//數(shù)據(jù)元素類型定義{keytypekey;//關(guān)鍵字項┆}；#definemaxlenmaxsize//分配的存儲單元個數(shù)structListSq{Elemtypee[maxsize];intlen;};第十一頁，共三十頁，2022年，8月28日8.2.1順序查找

順序查找（線性查找）基本思想：從線性表的一端開始，依次將每個元素的關(guān)鍵字同給定值K進(jìn)行比較，若某元素關(guān)鍵字與K相等，則查找成功；若所有元素都比較完畢，仍找不到關(guān)鍵字為K的元素，則查找失敗。

實現(xiàn)算法：（略）ASL：等概率前提下，ASL==(n+1)/2；若查找失敗，需要比較n+1次，所以時間復(fù)雜為O(n)。

第十二頁，共三十頁，2022年，8月28日8.2.2折半查找

使用折半查找（二分查找）的前提：有序表形式表示。

折半查找的思想：設(shè)存在順序有序表ListSqL，表中元素的下界為0，上界為L.len-1。先取整個有序表的中間點元素L.e[mid](mid=（(上界+下界)/2）的關(guān)鍵字同給定值K進(jìn)行比較。若相等，則查找成功，返回該元素的下標(biāo)mid；若K<L.e[mid].key，則說明待查元素若存在只能在左子表(下標(biāo)從0到mid－1的范圍)中，只要在左子表中繼續(xù)折半查找即可；若K>L.e[mid].key，則說明待查元素若存在只能在右子表(下標(biāo)從mid+1到n－1的范圍)中，只要在右子表中繼續(xù)二分查找即可。重復(fù)執(zhí)行，直到找到關(guān)鍵字為K的元素或當(dāng)前查找區(qū)間為空(即表明查找失敗)為止。

第十三頁，共三十頁，2022年，8月28日實現(xiàn)算法：（略）二叉判定樹：表示折半查找的查找過程。樹中的每個結(jié)點表示表中一個元素，每棵子樹的根結(jié)點表示當(dāng)前查找區(qū)間的中間點元素，它的左子樹和右子樹分別對應(yīng)該區(qū)間的左子表和右子表。

二叉判定樹是一棵二叉排序樹。

二分查找的平均查找長度為：

第十四頁，共三十頁，2022年，8月28日8.2.3分塊查找

分塊查找(索引順序查找)基本思想：

首先把一個線性表(即主表)按照一定的函數(shù)關(guān)系或條件劃分成若干個邏輯子表，為每個子表分別建立一個索引項，由所有子表的索引項構(gòu)成一個索引表。當(dāng)進(jìn)行分塊查找時，先根據(jù)所給的關(guān)鍵字查找索引表，從中查找出給定值K剛好小于等于索引值的那個索引項，找到待查塊，然后再到主表中查找該塊，從中查找待查的記錄。

實現(xiàn)算法：（略）

索引表是有序的，所以在索引表上既可以采用順序查找，也可以采用折半查找，而每個塊中的記錄排列是任意的，所以在塊內(nèi)只能采用順序查找。

第十五頁，共三十頁，2022年，8月28日平均查找長度為：設(shè)將長度為n的表均勻分成b塊，每塊有s個記錄，則b=[n/s]，查找表中每條記錄的概率相等，則每塊查找的概率為1/b，塊中每條記錄的查找概率為1/s。則順序查找索引表時：

第十六頁，共三十頁，2022年，8月28日8.3動態(tài)查找

8.3.1二叉排序樹查找8.3.2二叉平衡樹

動態(tài)查找表特點：表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的，即對于給定值key，若表中存在關(guān)鍵字等于key的記錄，則查找成功；否則插入關(guān)鍵字為key的元素。第十七頁，共三十頁，2022年，8月28日8.3.1二叉排序樹查找

二叉排序樹(二叉搜索樹、二叉查找樹)：或者是一棵空樹，或是一棵有如下特性的非空二叉樹：l

若它的左子樹非空，則左子樹上所有結(jié)點的關(guān)鍵字均小于根結(jié)點的關(guān)鍵字。l

若它的右子樹非空，則右子樹上所有結(jié)點的關(guān)鍵字均大于等于根結(jié)點的關(guān)鍵字。l

左、右子樹本身又各是一棵二叉搜索樹。結(jié)論：二叉排序樹中序遍歷得到的必是一個有序序列。

第十八頁，共三十頁，2022年，8月28日二叉排序樹的查找過程（遞歸查找過程）：查找一個給定值為k的結(jié)點，若二叉樹不為空，首先將它與根結(jié)點進(jìn)行比較，若K與根結(jié)點相等，查找成功；若K小于根結(jié)點，則表示若K存在，應(yīng)在其左子樹中；否則若K存在，應(yīng)在其右子樹中。對左、右子樹同樣按上述過程先與子樹的根結(jié)點進(jìn)行比較，根據(jù)比較的結(jié)果定下一步的操作。若在查找過程中遇到葉子結(jié)點，還沒有找到待找結(jié)點，則表示二叉排序樹中不存在該結(jié)點，查找不成功。

實現(xiàn)算法：（略）第十九頁，共三十頁，2022年，8月28日時間復(fù)雜度：分析：在二叉排序樹上進(jìn)行查找的過程中，根結(jié)點為待查結(jié)點時，給定值同樹中結(jié)點的比較次數(shù)僅為一次，待查結(jié)點位于最后一層時，比較的次數(shù)為樹的深度。普通情況下，對二叉排序樹進(jìn)行查找的時間復(fù)雜度為O()；最差情況下(二叉排序樹為一棵單支樹)，其時間復(fù)雜度為O(n)。

第二十頁，共三十頁，2022年，8月28日8.3.2二叉平衡樹

二叉平衡樹(AVL樹)：或者是一棵空樹，或者是一棵具有如下性質(zhì)的非空二叉樹：它的左子樹和右子樹都是二叉平衡樹，且左子樹和右子樹的深度之差的絕對值不大于1。二叉平衡樹中結(jié)點的左子樹的深度減去它的右子樹的深度的值定義為平衡因子BF，則BF的值只可能為－1、0和1。

第二十一頁，共三十頁，2022年，8月28日對二叉排序樹插入結(jié)點而構(gòu)造平衡二叉樹的規(guī)律：設(shè)最小子樹根結(jié)點的指針為a，則失去平衡后進(jìn)行調(diào)整的規(guī)律：

LL型：單向右旋平衡處理

RR型：單向左旋平衡處理

LR型：雙向旋轉(zhuǎn)(先左后右)平衡處理

RL型：雙向旋轉(zhuǎn)(先右后左)平衡處理時間復(fù)雜度：在查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)不超過樹的深度，所以，在二叉平衡樹上進(jìn)行查找的時間復(fù)雜度為O(log2n)。

第二十二頁，共三十頁，2022年，8月28日8.4散列查找

8.4.1散列存儲和散列函數(shù)的構(gòu)造方法

8.4.2解決沖突的方法

8.4.3散列查找實現(xiàn)算法和性能分析

第二十三頁，共三十頁，2022年，8月28日8.4.1散列存儲和散列函數(shù)構(gòu)造基本術(shù)語：散列存儲：以數(shù)據(jù)中每個元素的關(guān)鍵字K為自變量，通過一個函數(shù)f(k)計算出函數(shù)值，把這個值同存儲空間中一個唯一的存儲位置相對應(yīng)，將該元素存儲到這個存儲位置中。函數(shù)f(k)稱為散列函數(shù)或哈希函數(shù)。f(k)的值稱為散列地址或哈希地址；進(jìn)行散列存儲的地址空間稱為散列表或哈希表。

沖突：實際應(yīng)用中，由于散列函數(shù)的構(gòu)造方法不同，常會出現(xiàn)多個元素同時占用一個存儲單元的情況，即散列地址相同，這種現(xiàn)象叫沖突。具有相同函數(shù)值的不同關(guān)鍵字的元素，稱為同義詞。

第二十四頁，共三十頁，2022年，8月28日常用的構(gòu)造散列函數(shù)的方法：直接定址法數(shù)字分析法平方取中法折疊法除留余數(shù)法

第二十五頁，共三十頁，2022年，8月28日8.4.2解決沖突的方法

常用的解決沖突的方法有以下幾種：開放定地址鏈地址法第二十六頁，共三十頁，2022年，8月28日從發(fā)生沖突的那個單元開始，按照一定次序，從散列表中查找出一個空閑存儲單元，把發(fā)生沖突的待插入元素存入到該單元中的一類解決沖突的方法。設(shè)H(key)為散列函數(shù)，m為散列表長度。則開放定址法中找下一個空閑空間的散列函數(shù)為：Hi=(H(key)+di)%m

其中，i=1,2…k；di稱為增量，以di的取值分為以下三種：(1)di=1,2,3…m-1,稱線性探測再散列。(2)di=12,-12，22，-22，…±k2,(k≤m/2)稱二次探測再散列。(3)di=隨機數(shù)序列，稱為隨機探測再散列。開放定址法：第二十七頁，共三十頁，2022年，8月28日把具有相同散列地址的關(guān)鍵字放在同一鏈表中，稱為同義詞鏈表。通常把具有相同散列地址的關(guān)鍵字都存放在一個同義詞鏈表中，有m個散列地址就有m個鏈表，同時用數(shù)組t[m]存放各個鏈表的頭指針,凡是散列地址為i的記錄都以結(jié)點方式插入到以t[i]為頭指針