数据结构-常用的查找算法
總第124篇/張俊紅
本篇講講數據結構里面常用的幾個查找算法，數據結構理論篇系列差不多接近尾聲了，接下來會分享一些比較特殊的概念，比如KMP、郝夫曼樹等等，講完概念以后會進入刷題階段。刷題會用Python來，請持續關注。
1.順序表查找
順序查找又叫線性查找，是最基本的查找技術，它的關鍵流程為：從表中第一個或最后一個記錄開始，逐個對比該記錄中的關鍵詞與待查找關鍵詞是否相等，如果某條記錄中的關鍵詞與待查找關鍵詞相等，則表示查找成功，返回所查找記錄；如果直到最后一條記錄，其關鍵詞與待查找關鍵詞都不相等，則查找失敗。
具體實現代碼如下：
int?Sequential_Search(int?*a,int?n,int?key)????//a為數組，n為要查找數組長度，key為待查找關鍵詞 {int?i;for(i?=?1;i?<=?n;i++)????//遍歷數組內的每一條記錄,元素記錄是從1開始{if(a[i]?==?key)????//如果查找到，則返回記錄所在位置return?i;}return?0;????//如果未查找到，則返回0 }上面基本版查找算法在遍歷完一條記錄以后，需要將下一條記錄的位置i與數組長度n做一個比較，看是超出數組的范圍，改進版的查找算法省略了這一步，具體實現過程：讓a[0]=key,i = n表示a[0]為待查找關鍵詞，且從數組的末尾依次往前查找，實現代碼如下：
int?Sequential_Search(int?*a,int?n,int?key)????//a為數組，n為要查找數組長度，key為待查找關鍵詞 {int?i;a[0]?=?key;i?=?n;while(a[i]?!=?key){i--;}return?i;????//如果未查找到，則返回0 }2.有序表查找
有序查找是指線性表中的記錄是有序的（從大到小或從小到大），且線性表是采用順序存儲的。
2.1折半查找
對于滿足有序表這樣存儲結構的數據，我們采用的第一種方法是折半查找，又稱二分查找。折半查找的基本思想是：在有序表中，先取中間記錄作為比較對象，若給定值與中間記錄的關鍵字相等，則查找成功；若給定值小于中間記錄的關鍵字，則在中間記錄的左半區繼續查找；若給定值大于中間記錄的關鍵字，則在中間記錄的右半區繼續查找。不斷重復上述過程，直到查找成功，或所有查找區域無記錄，查找失敗為止。實現代碼：
int?Binary_Search(int?*a,int?n,int?key) {int?low,high,mid;low?=?1;//定義最開始位置high?=?n;//定義結束位置while(low?<=?high){mid?=?(low?+?high)/2;????//先折半????if(key?<?a[mid])??????????????//如果查找值比中值小，結束位置變為中值-1high?=?mid?-?1;else?if(key?>?a[mid])????//如果查找值比中值大，起始位置變為中值+1low?=?mid?+?1;elsereturn?mid;??????????????//如果相等，則說明mid就是待查找位置}return?0; }2.2插值查找
折半查找很方便也很好理解，但是有的時候會增加不必要的查找次數。比如說，你要在0-10000之間查找10，如果按折半查找的話，會有多次無用查找。那么有沒有什么方法可以避免這種問題的發生，也就是一開始就從待查找值附近開始查找，而沒必要非要從中間位置開始查找。插值查找就是用來解決這個問題的。
就是把折半查找中的1/2變成了(key-a[low])/(a[high]-a[low]),這樣就可以快速定位到待查找值附近開始查找，這種方法就叫做插值查找。
2.3斐波那契查找
在講什么是斐波那契查找之前，先看看什么是斐波那契數列。
斐波那契數列，又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：1、1、2、3、5、8、13、21、34、……在數學上，斐波納契數列以如下被以遞推的方法定義：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
兔子數列斐波那契查找算法具體步驟如下：
生成一個斐波那契序列的數組，便于之后使用。數組名記為f，例如f[1]=1，f[2]=1，f[3]=2，f[4]=3，f[5]=5，f[6]=8，f[7]=13，f[8]=21……
比較待查找數組長度n是否等于f[k]-1，其中k為滿足條件的最小值，若等于，則進入下一步，若不等于則將待查找數組長度擴充到f[k]-1。
找到mid元素low+(f[k-1]-1)，不斷進行二分比較，直到查找成功為止。
3.線性索引查找
我們前面講的幾種查找方法都是基于有序的基礎上的，現實業務中，每時每刻都在產生大量新數據，如果對這些數據進行排序的話，耗費時間會很大，效率會很低。這個時候就需要想新的查找方法，就是我們這一節要講的線性索引查找。
索引就是把一個關鍵字與它對應的記錄相關聯的過程，一個索引由若干個索引項組成，每個索引至少應包含關鍵字和其對應的記錄在存儲器中的位置信息。
索引按照結構可分為：線性索引、樹形索引和多級索引。常用的主要是線性索引。所謂線性索引就是將索引項集合組織成線性結構，也稱為索引表。重點介紹三種線性索引：稠密索引、分塊索引和倒排索引。
3.1稠密索引
稠密索引是指在線性索引中，將數據集中的每個記錄對應一個索引項,其中，稠密索引中的索引項一定是按照關鍵碼有序排列的。
索引項有序，我們就可以按照前面提到的幾種有序查找法先在左表中查找需要的關鍵詞，然后再在右表中查找該關鍵詞對應的數據項。如果我們不利用索引項的話，我們就只能在右表按照順序查找的方式依次遍歷每一個關鍵碼。利用索引項可以大大縮短查找時間。但是如果數據集過大，索引也得數據集長度規模，這樣每查找一個關鍵詞時，都會去查找一遍很長的關鍵碼，會大大降低查詢效率。
3.2分塊索引
稠密索引是因為索引項過長，會降低查詢效率。那么有沒有一種方法可以把索引項長度變短呢？那就是分塊索引。圖書館的書架大家應該都見過，那種擺放其實就是一種分塊索引，每個書架放一類書（建立一個索引），這樣索引項就會大幅度縮短。
分塊索引就是根據某個原則將數據分為若干塊，讓每一塊對應一個索引項。
分塊索引的索引項結構分三個數據項：
最大關鍵碼，存儲每一塊中的最大關鍵字，這樣就使得在它之后的下一塊中的最小關鍵字也能比這一塊最大的關鍵字要大；
存儲塊中國的記錄個數，用于循環的時候使用；
用于指向塊首數據元素的指針，便于開始這一塊記錄進行遍歷。
分塊索引查找順序：
先在分塊索引表中查找要查找的關鍵詞所在的塊，由于分塊索引的塊間是有序的，因此可以利用有序查找的方法進行查找。
根據塊首指針找到相應的塊，并在塊中順序查找關鍵碼。
3.3倒排索引
我們先想想我們平常都是怎么使用搜索引擎的？我們輸入一個我們想要查詢的關鍵詞，然后搜索引擎會返回一堆包含查找關鍵詞的網頁鏈接，然后我們根據自己需求，點擊不同的網頁即可。這背后利用的原理就是倒排索引。
倒排索引具體原理：
獲取關鍵詞，搜索引擎會爬取互聯網上幾乎所有的信息，然后將每條信息/每篇文檔進行分詞，所謂分詞就是將一大段文字變為一個個關鍵詞。
建立倒排索引，獲取到關鍵詞以后，我們就可以針對關鍵詞建立倒排索引，就是將關鍵詞與該關鍵詞的出現位置，即哪篇文章，對應起來。除此之外，還需要指明該關鍵詞在文章中具體的位置，為了快速飄紅顯示。還有關鍵詞在一篇文章中出現的次數。
文章號就表示在第幾篇文章中出現，出現頻率表示在該篇文章中出現了幾次，出現位置表示關鍵詞在該篇文章中具體的位置。
索引建立好之后，當用戶搜索一個關鍵詞，先會在關鍵詞列遍歷查找關鍵詞，然后返回該關鍵詞對應的文章號以及出現位置。
4.二叉排序查找
二叉排序是一種動態查找表，這種表可以在查找時插入或刪除數據，且不需要改變其他數據元素。
二叉排序樹又稱為二叉查找樹，這棵樹可以為空，如果不為空時有如下性質：
若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值。
若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值。
它的左右子樹也分別為二叉排序樹。
二叉排序樹首先是一顆二叉樹，構建一顆二叉排序樹的目的，其實并不是為了排序，而是為了提高查找和插入刪除關鍵字的速度。
二叉樹結構定義：
typedef?struct?BiTNode {int?data;????//結點數據struct?BiTNode?*lchild,*?rchild;????//左右孩子指針 }BiTNode,*BiTree;二叉樹查找實現
Status?SearchBST(BiTree?T,int?key,BiTree?f,BiTree?*p) {if(!T)????//判斷當前結點是否為空,如果為空，則執行{*p?=?f;return?FALSE;}else?if(key?==?T?->?data)????//如果待查找關鍵詞等于該節點值，則返回結點位置{*p?=?T;retuen?TRUE;}else?if(key?<?T->?data)????//如果待查找值小于結點值，則在左子樹繼續查找，否則在右子樹查找return?SearchBST(T?->?lchild,key,T,p)elsereturn?SearchBST(T?->?rchild,key,T,p) }4.1平衡二叉樹(AVL樹)
平衡二叉樹是一種二叉排序樹,其中每個節點的左子樹和右子樹的高度差至多等于1。
之所以又稱AVL樹是因為有兩位數學家G.M.Adelsom-Velskii和E.M.Landis發明了一種解決平衡二叉樹的算法。
我們將二叉樹結點的左子樹深度減去右子樹深度的值稱為平衡因子BF，那么平衡二叉樹上所有結點的平衡因子只可能是-1、0、1,只要二叉樹上有一個結點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。
第一棵樹是平衡二叉樹，第二顆不是平衡二叉樹，主要是因為平衡因子BF大于1。
注意：平衡二叉樹前提是一種排序樹。
4.2多路查找樹（B樹）
多路查找樹中每一個結點的孩子數可以多于兩個，且每個結點處可以存儲多個元素。如下圖中的根節點的左右子樹均有三個孩子。
B樹有一個很重要的特性就是：下層結點的關鍵字取值總是落在由上層結點關鍵字所劃分的區間內，具體落在哪個區間內，由指針指向可以看出。
比如上圖中，根節點的左子樹3、6可以將區間劃分為負無窮到3，3到6，6到正無窮；1和2則落到了負無窮到3之間，4和5則落在3到6區間內，7、8、9則落在6到正無窮區間內。
B樹的查找也正是基于這一特性來的，具體查找步驟如下：
先讓關鍵字key與根節點的關鍵字比較，如果key=ki，則查找成功。
若key<k[1]，則到p[0]所指示的子樹中進行繼續尋找。
若key>k[n]，則到p[n]所指示的子樹中進行繼續尋找。
若k[i]<key<k[i+1]，則到p[i]所指示的子樹中繼續查找。
如果遇到空指針，則證明查找不成功。
5.散列表（哈希表）查找
我們前面介紹的幾種方法，都需要將待查找關鍵詞與數據結構中存儲的內容進行比較，如果查找成功，則返回該關鍵詞對應的地址。如果不成功，則不返回值。那么有沒有一種方法可以不需要比較，直接返回地址的呢？答案是有的，具體方式就是通過哈希表來查找。具體的實現原理其實就是將關鍵詞與地址之間建立某種聯系（映射），關鍵詞相當于x,關鍵詞對應的地址相當于y，y和x之間可以用一個函數來表示，我們把這個函數叫做散列函數，這樣只要輸入一個x就會得到y。不再需要去做對比。
5.1散列函數的構造方法
散列表查找的前提是數據是以散列形式存儲的，所以我們首先來看看如何將數據以散列表的形式存儲呢，即如何構造散列函數。
5.1.1直接定址法
直接地址法就是直接取關鍵詞的某個線性值作為該關鍵詞的散列地址。
f(key)?=?a*key?+?b?(a,b為常數)很多公寓編號就是采用的這種散列方法，比如208房間，你就可以知道這個房間在2樓第8個位置。
這種方法很簡單，也不會出現位置沖突的情況，但是需要事先知道關鍵詞的分布情況，適合于查找表較小且連續的情況。
5.1.2數字分析法
就是通過分析數字間的規律來分配地址。
比如我們拿每個人的手機號作為關鍵字，那么就可以取每個關鍵詞（手機號）的后四位作為關鍵詞的位置。如果公司人數過多（超過1w）的話很有可能會遇到地址沖突的情況，也就是兩個人的尾號是相同的，關于地址沖突的解決方法我們后面來說。
這種方法適合處理關鍵字位數比較大的情況，因為位數足夠大，才會不太可能出現位置沖突的情況，但是需要事先知道數據分布情況。
5.1.3平方取中法
這個方法就是字面意思，先對關鍵字平方，然后取中間3位數作為散列地址。
比如關鍵字1234的平方是1522756，那么該關鍵字的散列地址就是227。
這種方法適合不知道關鍵詞的分布，而位數又不是很大的情況。
5.1.4折疊法
折疊法是將關鍵字從左到右分割成位數相等的幾部分(最后一部分位數不夠時可以短些),然后將這幾部分疊加求和，并按散列表表長，取后幾位作為散列地址。
比如現在有關鍵字9876543210，散列表表長為3位(可以是4位)，可以將其分為4組，987|654|321|0，然后 將他們疊加求和987+654+321+0 = 1962，再求后3位得到散列地址962。
這種方法適合關鍵字位數較多，且事先不需要知道關鍵字分布的情況。
5.1.5除留取余數法
又是一個字面意思，對關鍵字除某個數得到的余數作為該關鍵字的散列地址。
f(key)?=?key?mod?p?5.1.6隨機數法
這個就更比較簡單直接了，直接利用random方法。具體方法如下：
f(key)?=?random(key)上面說到的這幾種方法假設關鍵字都是數字，那如果關鍵字是字符該怎么辦呢？其實所有的字符，不管是中文還是英文，都可以轉化為數字（ASCII碼或者是Unicode碼）。
5.2處理散列沖突的方法
我們上面介紹的幾種構建散列地址的方法中，有的方法會出現地址沖突，也就是不同關鍵詞對應同一個散列地址，這肯定是不允許的，當出現地址沖突時，我們需要想辦法去解決，接下來介紹幾種解決地址沖突的方法。
5.2.1開放定址法
開放定址法就是一旦位置發生沖突，就去尋找下一個空的散列地址（直接給地址不停加1即可），只要散列表足夠大，就一定會找到空的散列地址。
5.2.2再散列函數法
再散列函數就是剛開始選擇一種散列地址構造方法去構造散列地址，當地址出現矛盾時，就換一種構造方法重新構造散列地址，直到把沖突解除。
5.2.3鏈地址法
鏈地址法就是當地址出現沖突時，將同一位置的不同元素以鏈表的形式存儲，這樣就會出現一個位置對應多個元素。
5.2.4公共溢出區法
公共溢出區法是建立一個溢出區表，專門用來存放那些地址發生沖突的元素。相當于把所有的元素放在兩個表中。在查找的時候，先在主表里面進行查找，如果主表沒有，則再去溢出表進行查找。
5.3散列表的查找實現
首先需要定義一個散列表結構HashTable,這個結構用來存儲關鍵字和關鍵字對應的散列地址，具體定義如下：
typedef?struct {int?*elem;????//數據元素存儲地址int?count;????//當前數據元素個數 }HashTable;int?m?=?0；????//散列表表長，是一個全局變量有了結構（容器）以后，我們就可以對散列表進行初始化，具體定義如下：
Status?InitHashTable(HashTable?*H) {int?i;m?=?HASHSIZE;H?->?count?=?m;H?->?elme?=?(int?*)malloc(m*sizeof(int));for(i?=?0;i?<?m;i?++)H?->?elme[i]?=?NULLKEY;return?OK; }為了在插入數據時，計算每個關鍵字對應的散列地址，我們需要定義一個散列函數，具體定義如下：
int?Hash(int?key) {return?key?%?m;????//這里用過的除留取余法，也可也是其他方法 }散列表初始化好了，散列函數也定義好了，這個時候就可以往散列表里面加數據了，具體實現如下：
void?InsertHash(HashTable?*H,int?key) {int?addr?=?Hash(key);????//獲取散列地址while(H?->?elem[addr]?!?=?NULLKEY)????//如果散列地址不為空，說明地址沖突addr?=?(addr?+?1)?%?m;????//開放尋址，尋找下一個不沖突的位置 }插入數據以后，就等著需要用到的時候被查找，具體實現代碼如下：
Status?SearchHash(HashTable?H,int?key,int?*addr) {*addr?=?Hash(key);????//求散列地址while(H.elem[*addr]?!=?key)????//如果該散列地址對應的關鍵字與實際關鍵字不等，則沖突{*addr?=?(*addr?+?1)?%?m;????//開放尋址if(H.elem[*addr]?==?NULLKEY)?||?*addr?==?Hash(key)){return?UNSUCESS;????//說明關鍵字不存在}}return?SUCCESS; }你還可以看：
數據結構—線性表
數據結構-棧和隊列
數據結構—字符串
數據結構—樹與二叉樹
數據結構-圖
數據結構-常用的排序算法
總結
以上是生活随笔為你收集整理的数据结构-常用的查找算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 数据结构-常用的排序算法
- 下一篇： 关于2019的一些想法