1、查找表和查找效率的概念

查找表是指由同一類型的數據元素構成的集合。分為靜態查找表和動態查找表。

1.1 靜態查找表

1、查詢某個特定元素是否在查找表的集合當中

2、查詢某個特定元素的各種屬性

1.2 動態查找表

1、在查找表中插入一個數據元素

2、在查找表中刪除一個元素

1.3 關鍵字

它是數據元素的某個數據項的值。用來識別該元素。主關鍵字是唯一能表示該元素的值。次關鍵字用來表示多個數據元素的關鍵字。

1.4 查找

根據給定的值在查找表中查詢是否存在一個其關鍵字等于給定值的記錄或者數據元素。

1.5 平均查找長度

關鍵字和給定值進行比較的記錄個數的平均值。也是衡量查找算法好壞的依據。

2、順序查找

從數據集合的一端，逐個記錄的關鍵字和給定值進行比較，找到則為查找成功。整個數據集合比較完后仍然找不到，則為查找失敗。

順序查找適用于順序存儲和鏈式存儲。其平均查找長度為(n+1)/2.

順序查找算法簡單、適應性廣。當數據集合數據量大的話，查詢效率會較低。

3、折半查找

折半查找也稱為二分查找。

平均查找長度：(n+1)/n*log^2(n+1) -1,當n值較大 log^2(n+1) -1

折半查找效率比順序查找高，它比較合適順序存儲和關鍵字有序排列。所以折半查找適合數據表不經常變動，查詢頻率較高的情況。

? ? ? ? ? ? ?

4、索引順序查找

索引順序查找又稱為分塊查找，是順序查找的一個改進查找算法。

原理：分塊查找首先將表分為若干塊。每一塊可以無序。但塊之間是要有序的。即后一塊所記錄的關鍵字均大于前一塊的關鍵字。另外還會創建一個索引塊表，索引塊表關鍵字有序。

查詢過程：1、在索引表中確認待查記錄所在數據塊。2、在該數據塊內順序查找。

平均查找長度：1/2(n/s + s) +1

它的效率優于順序查找，比不上折半查找。

5、樹表查找

常見的樹表查找有二叉查找樹、B-樹、紅黑樹等常見查找算法。二叉查找樹是一種動態查找表

5.1 二叉查找樹查找過程

利用二叉查找樹左小右大的特性，可以很容易實現查找任意值和最大/小值。

在二叉查找樹中查找一個給定的關鍵字n的過程與折半查找很類似，

查找過程如下：

1.若二叉樹是空樹，則查找失敗。

2.若x等于根節點的數據，則查找成功，否則。

3.若x小于根節點的數據，則遞歸查找其左子樹，否則。

4.遞歸查找其右子樹。

5.2 二叉樹查找樹b插入操作x的過程

1.若b是空樹，則直接將插入的節點作為根節點插入。

2.x等于b的根節點的數據的值，則直接返回，否則。

3.若x小于b的根節點的數據的值，則將x要插入的節點的位置改變為b的左子樹，否則。

4.將x要插入的節點的位置改變為b的右子樹。

注：如果二叉樹是單枝樹。查詢效率和順序查找相當。

6、哈希查找

6.1 概念

通過計算數據元素的存儲地址進行元素查找的一種查找算法。

根據設定的哈希函數和處理沖突的方法，將一組關鍵字映射到一個有限的連續的地址集上，并以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表稱為哈希表。這一映射過程稱為哈希造表或散列。所得的存儲位置稱為哈希位置或者散列地址。

哈希算法要解決兩個問題：哈希函數的構造、沖突的解決。

6.2 解決沖突

解決沖突就是為出現沖突的關鍵字找到另一個“空”的哈希地址。

常用的解決沖突的方法有：開放定址法、鏈地址法、再哈希法、建立公共溢區法。

6.2.1開放定址法

最簡單的產生探測序列的方法是進行線性探測，發生沖突后，順序到下一個存儲單元進行探測。

6.2.2 鏈地址法

鏈地址法是常用并且很有效的方法。它將具有相同哈希函數值記錄組成一個鏈表，當鏈域值為NULL時，表示沒有后繼記錄。

6.2.3 哈希查找

線性探測解決沖突的方式下：某一個位置上找到關鍵字等于key的記錄，表示查找成功；探測序列查不到key關鍵字的記錄，又遇到了空單元，表示找不到該元素，查找失敗。

鏈地址法解決沖突構造的哈希表中查找元素，就是根據哈希函數得到的元素所在鏈表的頭指針，然后在鏈表中順序查找的過程。

IT技術分享社區

個人博客網站：https://programmerblog.xyz

文章推薦程序員效率：畫流程圖常用的工具程序員效率：整理常用的在線筆記軟件遠程辦公：常用的遠程協助軟件，你都知道嗎？51單片機程序下載、ISP及串口基礎知識硬件：斷路器、接觸器、繼電器基礎知識