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

1.查找基本概念

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

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

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

2.1 順序表

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

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

2.2 有序順序表

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

2.2.1 順序查找

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

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

2.2.2 二分查找

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

2.3 索引順序表

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

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

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

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

3.1 二叉排序樹(shù)

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

3.2 B_樹(shù)

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

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

1，樹(shù)中每個(gè)節(jié)點(diǎn)最多有m個(gè)孩子節(jié)點(diǎn)

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

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

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

n表示該節(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)；Ki表示該節(jié)點(diǎn)的關(guān)鍵字且滿足Ki<Ki+1；Pi為該節(jié)點(diǎn)的孩子節(jié)點(diǎn)指針且滿足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ù)；哈希表就是通過(guò)哈希函數(shù)確定數(shù)據(jù)元素存放位置的一種特殊結(jié)構(gòu)。

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

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

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

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

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