算法與數(shù)據(jù)結(jié)構(gòu)|查找

1.查找基本概念

分為靜態(tài)查找和動態(tài)查找；靜態(tài)查找時構(gòu)造的存儲結(jié)構(gòu)成為靜態(tài)查找表，動態(tài)查找時構(gòu)造的存儲結(jié)構(gòu)為動態(tài)哈招標(biāo)

2.靜態(tài)查找表

靜態(tài)查找表包括：順序表、有序順序表、索引順序表三種結(jié)構(gòu)。

2.1 順序表

在順序表上查找的基本思想是：從順序表的一端開始，用給定數(shù)據(jù)元素的關(guān)鍵字逐個與順序表中各數(shù)據(jù)元素的關(guān)鍵字比較，若存在，則查找成功；反之，則查找失敗。

查找成功的平均查找長度ASL_成功=(1+n)/2；查找失敗平均查找長度ASL_失敗=n

2.2 有序順序表

有序順序表上的查找算法主要有順序查找和二分查找方法

2.2.1 順序查找

與之前的查找一樣，但是由于是有序的因此在失敗時平均查找長度與之前是有不同的：

ASL_成功=(n+1)/2；ASL_失敗=(n+1)/2。

2.2.2 二分查找

基本思想：在一個查找區(qū)間，確定查找區(qū)間的中心位置，用待查找的元素的關(guān)鍵字與之對比，若相等則查找成功；否則，若若小于則把查找區(qū)間改為原區(qū)間的左部分；若大于則把查找區(qū)間改為原區(qū)間的右部分；這樣查找一直到查找區(qū)間的上界小于下界為止。

2.3 索引順序表

當(dāng)順序表的數(shù)據(jù)元素個數(shù)非常大時，無論使用哪種查找算法都需要很長的時間，此時，我們可以在順序表上建立索引表。我們把在其上建立索引表的順序表叫做主表，主表中存放數(shù)據(jù)元素的全部信息，索引表中只存放主表中要查找數(shù)據(jù)元素的主關(guān)鍵字和索引信息。

當(dāng)數(shù)據(jù)元素個數(shù)非常龐大時，可以對索引表再做索引表，這樣的索引表叫做耳機索引表或者多級索引表。

索引表還分為等長索引表、不等長索引表(多一個length域)(主表分段有序即可，要求比有序低)。

3.動態(tài)查找表

3.1 二叉排序樹

二叉排序樹：或者是一個空樹或者具有以下性質(zhì)：(1)若左子樹不空，則左子樹上所有節(jié)點的關(guān)鍵字值均小于根節(jié)點的關(guān)鍵字值；(2)若右子樹不空，則右子樹上所有節(jié)點的關(guān)鍵字均大于等于根節(jié)點的關(guān)鍵字值；

3.2 B_樹

與二叉排序樹相比，B_樹是一種平衡多叉排序樹。這里說的平衡是指所有葉節(jié)點都在同一層上，從而可避免出現(xiàn)像二叉排序樹那樣的分支退化現(xiàn)象；多叉指多余二叉，B_是一種動態(tài)查找效率高于二叉排序樹的樹。

B_樹中所有節(jié)點的孩子節(jié)點的最大值成為B_樹的階通常用m表示。一棵m階的B_樹或者是一棵空樹，或者是滿足下列要求的m叉樹：

1，樹中每個節(jié)點最多有m個孩子節(jié)點

2，除根節(jié)點外，其他節(jié)點至少有[m/2]（向上取整）個孩子節(jié)點

3，若根節(jié)點不是葉節(jié)點，則根節(jié)點至少有兩個孩子節(jié)點。

4，每個節(jié)點的結(jié)構(gòu)：

n表示該節(jié)點中關(guān)鍵字個數(shù)；Ki表示該節(jié)點的關(guān)鍵字且滿足Ki<Ki+1；Pi為該節(jié)點的孩子節(jié)點指針且滿足Pi指針?biāo)讣罢O但的關(guān)鍵字均大于等于Ki小于Ki+1。Pn指針?biāo)傅年P(guān)鍵字大于等于Kn

4.哈希表

哈希函數(shù)：把數(shù)據(jù)元素的關(guān)鍵字和該數(shù)據(jù)元素的存放位置之間的映射函數(shù)稱為哈希函數(shù)；哈希表就是通過哈希函數(shù)確定數(shù)據(jù)元素存放位置的一種特殊結(jié)構(gòu)。

哈希沖突，當(dāng)數(shù)據(jù)元素關(guān)鍵字不相等，但是經(jīng)過哈希函數(shù)映射的位置相同時，我們管這個叫做哈希沖突.哈希沖突主要與三個因素有關(guān)：a，裝填因子(存入元素與哈希池地址空間壁紙；b，使用的哈希函數(shù)相關(guān)；c，與解決哈希沖突的沖突解決函數(shù)有關(guān))

解決哈希沖突的方法，基本思想：當(dāng)哈希沖突時，通過哈希函數(shù)產(chǎn)生一個新的哈希地址是不產(chǎn)生沖突，通常哈希函數(shù)是一組函數(shù)。

一旦構(gòu)造好哈希表，只需要以關(guān)鍵字K和哈希函數(shù)來映射到地址，然后從地址中取出關(guān)鍵字元素對比是否相同，相同則查找成功，否則以建立哈希表時所用的沖突函數(shù)得到新的地址查看關(guān)鍵字是否相同，一直到查找成功或查找完成m次而未查找到。數(shù)據(jù)分析師培訓(xùn)

常用的哈希函數(shù)構(gòu)造方法：1，除留余數(shù)法；2，直接定址法；3，數(shù)字分析法。

哈希沖突解決方法：1，開放定址法(線性探查法、平方探查法、偽隨機數(shù)法)；2，鏈表法。