典型查找算法編程

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

典型查找算法

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

8.1.1問題描述

8.1.2問題的分析

8.1.3實現算法

8.1.4基本概念

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

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

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

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

┆}；structlist{Studentstu[size];//保存學生記錄Intlen;//學生人數};

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

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

intsearch(List&L,int,s)//從表L.stu[0],L.stu[1],……L.stu[n-1]的n個元素中查找關鍵字為S元素，若查找成功返回該生學號，否則返回-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基本概念

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

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

ASL=其中：Ci為查找第i個元素時同給定值K進行比較的次數；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)查找

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

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

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

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

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

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

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

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

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

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

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

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

實現算法：（略）

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

第十五頁，共三十頁，2022年，8月28日平均查找長度為：設將長度為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)查找表特點：表結構本身是在查找過程中動態(tài)生成的，即對于給定值key，若表中存在關鍵字等于key的記錄，則查找成功；否則插入關鍵字為key的元素。第十七頁，共三十頁，2022年，8月28日8.3.1二叉排序樹查找

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

若它的左子樹非空，則左子樹上所有結點的關鍵字均小于根結點的關鍵字。l

若它的右子樹非空，則右子樹上所有結點的關鍵字均大于等于根結點的關鍵字。l

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

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

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

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

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

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

LL型：單向右旋平衡處理

RR型：單向左旋平衡處理

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

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

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

8.4.1散列存儲和散列函數的構造方法

8.4.2解決沖突的方法

8.4.3散列查找實現算法和性能分析

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

沖突：實際應用中，由于散列函數的構造方法不同，常會出現多個元素同時占用一個存儲單元的情況，即散列地址相同，這種現象叫沖突。具有相同函數值的不同關鍵字的元素，稱為同義詞。

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

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

常用的解決沖突的方法有以下幾種：開放定地址鏈地址法第二十六頁，共三十頁，2022年，8月28日從發(fā)生沖突的那個單元開始，按照一定次序，從散列表中查找出一個空閑存儲單元，把發(fā)生沖突的待插入元素存入到該單元中的一類解決沖突的方法。設H(key)為散列函數，m為散列表長度。則開放定址法中找下一個空閑空間的散列函數為：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=隨機數序列，稱為隨機探測再散列。開放定址法：第二十七頁，共三十頁，2022年，8月28日把具有相同散列地址的關鍵字放在同一鏈表中，稱為同義詞鏈表。通常把具有相同散列地址的關鍵字都存放在一個同義詞鏈表中，有m個散列地址就有m個鏈表，同時用數組t[m]存放各個鏈表的頭指針,凡是散列地址為i的記錄都以結點方式插入到以t[i]為頭指針