1．順序查找法以及平均查找長度(ASL)的計算吭服；
順序查找是一種最簡單的查找方法。其基本思想是將查找表作為一個線性表蝗罗，可以是順序表艇棕，也可以是鏈表蝌戒，依次用查找條件中給定的值與查找表中數(shù)據(jù)元素的關(guān)鍵字值進行比較，若某個記錄的關(guān)鍵字值與給定值相等沼琉，則查找成功北苟，返回該記錄的存儲位置，反之打瘪，若直到最后一個記錄友鼻，其關(guān)鍵字值與給定值均不相等，則查找失敗闺骚，返回查找失敗標(biāo)志彩扔。
下面以順序存儲為例實現(xiàn)順序查找:
typedef struct {
????ElemType *elem; //數(shù)據(jù)元素存儲空間基址，建表時按實際長度分配僻爽，0 號單元留空
????int length; // 表的長度
} SSTable;
int Search_Seq(SSTable ST, KeyType key) {
????ST.elem[0].key = key;// 設(shè)置“哨兵”
????for (i=ST.length; ST.elem[i].key!=key; --i);// 從后往前找
????return i;// 找不到時虫碉，i 為 0????
}
就順序查找法而言，對于 n 個數(shù)據(jù)元素的表胸梆，給定值 key 與表中第 i 個元素關(guān)鍵碼相等敦捧，即定位第 i 個記錄時，需進行 n-i+1 次關(guān)鍵碼比較碰镜，即 Ci=n-i+1兢卵。則查找成功時，順序查找的
平均查找長度為:
設(shè)每個數(shù)據(jù)元素的查找概率相等绪颖，即 Pi= 1/n 济蝉，則等概率情況下有
查找不成功時，關(guān)鍵碼的比較次數(shù)總是 n+1 次菠发。
算法中的基本工作就是關(guān)鍵碼的比較王滤，因此，查找長度的量級就是查找算法的時間復(fù)雜度滓鸠，其為 O(n)雁乡。
順序查找缺點是當(dāng) n 很大時，平均查找長度較大糜俗，效率低;優(yōu)點是對表中數(shù)據(jù)元素的存儲沒有要求踱稍，順序存儲或是鏈?zhǔn)酱鎯伞Ａ硗庥颇ǎ瑢τ诰€性鏈表珠月，只能進行順序查找
2．折半查找法以及平均查找長度(ASL)的計算，包括查找過程對應(yīng)的“判定樹”的構(gòu)造楔敌；
折半查找法以及平均查找長度(ASL)的計算
折半查找要求查找表用順序存儲結(jié)構(gòu)存放且各數(shù)據(jù)元素按關(guān)鍵字有序(升序或降序)排列啤挎，也就是說折半查找只適用于對有序順序表進行查找。折半查找的基本思想是:首先以整個查找表作為查找范圍卵凑，取中間元素作為比較對象庆聘，若給定值與中間元素的關(guān)鍵碼相等胜臊，則查找成功;若給定值小于中間元素的關(guān)鍵碼，則在中間元素的左半?yún)^(qū)繼續(xù)查找;若給定值大于中間元素的關(guān)鍵碼伙判，則在中間元素的右半?yún)^(qū)繼續(xù)查找象对。不斷重復(fù)上述查找過程，直到查找成功宴抚，或所查找的區(qū)域無數(shù)據(jù)元素勒魔，查找失敗。
int Search_Bin ( SSTable ST, KeyType key) {
low = 1; high = ST.length;?// 置區(qū)間初值
while (low <= high) {
mid = (low + high) / 2;
if(key == ST.elem[mid].key ) return mid; // 找到待查元素
else if (key < ST.elem[mid].key) )
high = mid - 1;// 繼續(xù)在前半?yún)^(qū)間進行查找
else low = mid + 1;// 繼續(xù)在后半?yún)^(qū)間進行查找
}
return 0;// 順序表中不存在待查元素
}
從折半查找過程看菇曲，以表的中點為比較對象沥邻，并以中點將表分割為兩個子表，對定位到的子表繼續(xù)這種操作羊娃。所以唐全，對表中每個數(shù)據(jù)元素的查找過程，可用二叉樹來描述蕊玷，稱這個描述查找過程的二叉樹為判定樹邮利。可以看到垃帅，查找表中任一元素的過程延届，即是判定樹中從根到該元素結(jié)點路徑上各結(jié)點關(guān)鍵碼的比較次數(shù)，也即該元素結(jié)點在樹中的層次數(shù)贸诚。對于 n 個結(jié)點的判定樹方庭，樹高為 k，則有
因此酱固，折半查找在查找成功時械念，所進行的關(guān)鍵碼比較次數(shù)至多為 log2(n+1) 。 运悲。
接下來討論折半查找的平均查找長度龄减。為便于討論，以樹高為k的滿二叉樹(n=2k-1)為例班眯。假設(shè)表中每個元素的查找是等概率的希停，即 Pi=1─n ，則樹的第 i 層有 2i-1 個結(jié)點署隘，因此宠能，折半查找的平均查找長度為:
所以，折半查找的時間效率為 O(log2n)磁餐。
查找過程對應(yīng)的“判定樹”的構(gòu)造
如何構(gòu)造二叉判定樹违崇？
3．散列(Hash)表的構(gòu)造、散列函數(shù)的構(gòu)造，散列沖突的基本概念亦歉、處理散列沖突的基本方法以及散列表的查找和平均查找長度的計算。
散列(Hash)表的構(gòu)造
散列函數(shù)的構(gòu)造
對數(shù)字的關(guān)鍵字可有下列散列函數(shù)的構(gòu)造方法畅哑，若是非數(shù)字關(guān)鍵字肴楷，則需先對其進行數(shù)字化處理。
1. 直接定址法
H(key) = key 或者 H(key) = a ?? key + b
即取關(guān)鍵碼的某個線性函數(shù)值為散列地址荠呐，這類函數(shù)是一一對應(yīng)函數(shù)赛蔫，不會產(chǎn)生沖突。
此法僅適合于:地址集合的大小 = = 關(guān)鍵字集合的大小
2. 數(shù)字分析法
假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由 s 位數(shù)字組成(k1, k2, ..., kn)泥张，分析關(guān)鍵字集中的全體呵恢，并從中提取分布均勻的若干位或它們的組合作為地址。
此法僅適合于:能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度媚创。
3.平方取中法
若關(guān)鍵字的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象渗钉，則先求關(guān)鍵字的平方值，以通過“平方”擴大差別钞钙，同時平方值的中間幾位受到整個關(guān)鍵字中各位的影響鳄橘。
此方法適合于:關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。
4. 折疊法
若關(guān)鍵字的位數(shù)特別多芒炼，則可將其分割成幾部分瘫怜，然后取它們的疊加和為散列地址”竟簦可有:移位疊加和間界疊加兩種處理方法鲸湃。
(1)移位法:將各部分的最后一位對齊相加。
(2)間界疊加法:從一端向另一端沿各部分分界來回折疊后子寓，最后一位對齊相加暗挑。
此方法適合于:關(guān)鍵字的數(shù)字位數(shù)特別多。
5. 除留余數(shù)法
H(key) = key MOD p? ? ?p≤m (表長)
即取關(guān)鍵碼除以 p 的余數(shù)作為散列地址斜友。使用除留余數(shù)法窿祥，選取合適的 p 很重要，若散列表表長為 m蝙寨，則要求 p≤m晒衩，且接近 m 或等于 m。p 一般選取質(zhì)數(shù)墙歪，也可以是不包含小于 20質(zhì)因子的合數(shù)听系。
6. 隨機數(shù)法
H(key) = Random(key)，其中虹菲，Random 為偽隨機函數(shù)靠胜。
通常，此方法用于對長度不等的關(guān)鍵字構(gòu)造散列函數(shù)。
實際造表時浪漠，采用何種構(gòu)造散列函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))陕习，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。
散列沖突的基本概念
處理散列沖突的基本方法
處理沖突的實際含義是:為產(chǎn)生沖突的地址尋找下一個散列地址址愿。
1. 開放定址法
所謂開放定址法该镣，即是由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，也就是說响谓，該地址已經(jīng)存放了數(shù)據(jù)元素损合，就去尋找下一個空的散列地址，只要散列表足夠大娘纷，空的散列地址總能找到嫁审，并將數(shù)據(jù)元素存入。
找空散列地址方法很多赖晶，下面介紹三種:
(1)線性探測法
Hi=(Hash(key)+di) mod m ( 1≤i < m )????其中: Hash(key)為散列函數(shù)律适，m 為散列表長度，di 為增量序列 1遏插，2擦耀，......，m-1涩堤，且di=i眷蜓。
這種方法的特點是:沖突發(fā)生時逼肯，順序查看表中下一單元炕檩， 直到找出一個空單元或查遍全表。
線性探測法可能使第i 個散列地址的同義詞存入第 i+1 個散列地址辑舷，這樣本應(yīng)存入第 i+1個散列地址的元素變成了第 i+2 個散列地址的同義詞白魂，......汽纤，因此，可能出現(xiàn)很多元素在相鄰的散列地址上“堆積”起來福荸，大大降低了查找效率蕴坪。為此，可采用二次探測法改善“堆積”問題敬锐。
(2)二次探測法Hi=(Hash(key)±di) mod m
其中:Hash(key)為散列函數(shù)背传，m 為散列表長度，m 要求是某個 4k+3 的質(zhì)數(shù)(k 是整數(shù))台夺，di 為增量序列 12径玖，-1222，-22颤介，......梳星，q2赞赖，-q2 且 q≤ 12 m。
這種方法的特點是:沖突發(fā)生時冤灾，在表的左右進行跳躍式探測前域，比較靈活。
(3)隨機探測再散列
di 是一組偽隨機數(shù)列韵吨，具體實現(xiàn)時匿垄，應(yīng)建立一個偽隨機數(shù)發(fā)生器，(如 i=(i+p) % m)学赛， 并給定一個隨機數(shù)做起點年堆。
2. 拉鏈法
這種方法的基本思想是將所有散列地址為i 的元素構(gòu)成一個稱為同義詞鏈的單鏈表吞杭，并將單鏈表的頭指針存在散列表的第 i 個單元中盏浇， 因而查找、插入和刪除主要在同義詞鏈中進行芽狗。 鏈地址法適用于經(jīng)常進行插入和刪除的情況绢掰。
散列表的查找
查找過程和造表過程一致。假設(shè)采用開放定址處理沖突童擎，則查找過程為:
對于給定值 K, 計算散列地址 i = H(K)滴劲，
若r[i] = NULL ，則查找不成功
若r[i].key = K 顾复，則查找成功
否則求下一地址 Hi班挖，直至 r[Hi] = NULL(查找不成功)
????????????????????????????????????或 r[Hi].key = K(查找成功)為止。
散列表平均查找長度的計算
散列表的查找過程基本上和造表過程相同芯砸。一些關(guān)鍵碼可通過散列函數(shù)轉(zhuǎn)換的地址直接找到萧芙，另一些關(guān)鍵碼在散列函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進行查找假丧。
在介紹的處理沖突的方法中双揪，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進行比較的過程。所以包帚，對散列表查找效率的量度渔期，依然用平均查找長度來衡量。
查找過程中渴邦，關(guān)鍵碼的比較次數(shù)疯趟，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少谋梭，查找效率就高迅办，產(chǎn)生的沖突多，查找效率就低章蚣。因此站欺，影響產(chǎn)生沖突多少的因素姨夹，也就是影響查找效率的因素。
影響產(chǎn)生沖突多少有以下三個因素:散列函數(shù)是否均勻;處理沖突的方法;散列表的裝填因子矾策。
分析這三個因素磷账，盡管散列函數(shù)的“好壞”直接影響沖突產(chǎn)生的頻度，但一般情況下贾虽，我們總認為所選的散列函數(shù)是“均勻的”逃糟，因此，可不考慮散列函數(shù)對平均查找長度的影響蓬豁。就線性探測法和二次探測法處理沖突的例子看绰咽，相同的關(guān)鍵碼集合、同樣的散列函數(shù)地粪，但在數(shù)據(jù)元素查找等概率情況下取募，它們的平均查找長度卻不同。
α 是散列表裝滿程度的標(biāo)志因子蟆技。由于表長是定值玩敏，α 與“填入表中的元素個數(shù)”成正比，所以质礼，α 越大旺聚，填入表中的元素較多，產(chǎn)生沖突的可能性就越大;α 越小眶蕉，填入表中的元素較少砰粹，產(chǎn)生沖突的可能性就越小。實際上造挽，散列表的平均查找長度是裝填因子 α 的函數(shù)碱璃，只是不同處理沖突的方法有不同的函數(shù)。
散列方法存取速度快刽宪，也較節(jié)省空間厘贼，但由于存取是隨機的，因此圣拄，不便于順序查找嘴秸。
