1 查找的基本概念

2 順序查找法

3 分塊查找法

4 折半查找法

5 B樹及其基本操作返咱、B+樹的基本概念

B樹的基本概念

一棵度為m的B樹稱為m階B樹氮帐，是一棵平衡的m路查找樹，其定義是：
一棵m階B樹洛姑，或者是空樹，或者是滿足以下性質(zhì)的m叉樹：
(1)根結(jié)點(diǎn)或者是葉子結(jié)點(diǎn)皮服，或者至少有兩棵子樹楞艾，至多有m棵子樹参咙；
(2)除根結(jié)點(diǎn)外，所有非葉子結(jié)點(diǎn)至少有?m/2?棵子樹硫眯，至多有m棵子樹蕴侧；
(3)所有葉子結(jié)點(diǎn)都在樹的同一層上。
(4)每個結(jié)點(diǎn)應(yīng)包含如下信息：

其中n是結(jié)點(diǎn)中關(guān)鍵字的個數(shù)两入，且?m/2?-1≤n≤m-1净宵，n+1為子樹的棵樹。
是關(guān)鍵字裹纳，且择葡，即遞增。
為指向孩子結(jié)點(diǎn)的指針剃氧，且所指向的子樹中所有結(jié)點(diǎn)的關(guān)鍵字都小于敏储，所指向的子樹中的所有結(jié)點(diǎn)的關(guān)鍵字都大于；

一棵3階B樹

#define M 5 //根據(jù)實(shí)際需要定義B樹的階數(shù)
typedef struct BTNode {
    int keyNum;//結(jié)點(diǎn)中關(guān)鍵字的個數(shù)
    struct BTnode *parent;//指向父結(jié)點(diǎn)的指針
    int key[M + 1];//關(guān)鍵字?jǐn)?shù)組朋鞍，key[0]未用
    struct BTNode *ptr[M + 1];//子樹指針向量
} BTNode;

B樹的查找

類似二叉排序樹的查找已添，所不同的是 B 樹每個結(jié)點(diǎn)上是多關(guān)鍵碼的有序表，在到達(dá)某個結(jié)點(diǎn)時(shí)滥酥，先在有序表中查找更舞，若找到，則查找成功;否則坎吻，到按照對應(yīng)的指針信息指向的子樹中去查找缆蝉，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí)，則說明樹中沒有對應(yīng)的關(guān)鍵碼禾怠，查找失敗返奉。即在 B 樹上的查找過程是一個順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)中查找關(guān)鍵碼交叉進(jìn)行的過程。

int BT_seartch(BTNode *T, int K, BTNode *p) {
    //查找關(guān)鍵字K吗氏，查找成功返回在結(jié)點(diǎn)中的位置及結(jié)點(diǎn)指針p芽偏；否則返回0及最后一個結(jié)點(diǎn)指針
    BTNode *q;
    p = q = T;
    while (q != NULL) {
        p = q;
        q->key[0] = K;//設(shè)置查找哨兵
        for (int i = q->keyNum; K < q->key[i]; i--) {
            if (i > 0 && q->key[i] == K) {
                return i;
            }
            q = q->ptr[i];
        }
    }
    return 0;
}

B樹的插入

B樹的生成也是從空樹起，逐個插入關(guān)鍵字弦讽。
插入時(shí)不是每插入一個關(guān)鍵字就添加一個葉子結(jié)點(diǎn)污尉，而是首先在最低層的某個葉子結(jié)點(diǎn)中添加一個關(guān)鍵字，然后有可能“分裂”往产。
(1)插入思想
①在B樹種查找關(guān)鍵字K被碗，若找到，表明關(guān)鍵字已存在仿村，返回锐朴；否則，K的查找操作失敗于某個葉子結(jié)點(diǎn)蔼囊，轉(zhuǎn)②
②將K插入到該葉子結(jié)點(diǎn)中焚志，插入時(shí)衣迷，若
※葉子結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)<m-1，則直接插入酱酬；
※葉子結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)=m-1壶谒，將結(jié)點(diǎn)“分裂”
(2)分裂方法
設(shè)待分裂結(jié)點(diǎn)p包含信息為：，從其中間位置分為兩個結(jié)點(diǎn)： 膳沽。并將中間關(guān)鍵字插入到p的父結(jié)點(diǎn)中汗菜，以分裂后的兩個結(jié)點(diǎn)作為中間關(guān)鍵字的兩個子結(jié)點(diǎn)。
當(dāng)把中間關(guān)鍵字插入到p的父結(jié)點(diǎn)后挑社，父結(jié)點(diǎn)可能也不滿足m階B樹的要求陨界，則必須對父結(jié)點(diǎn)進(jìn)行分裂，一直進(jìn)行下去滔灶，直到?jīng)]有父結(jié)點(diǎn)或分裂后的父結(jié)點(diǎn)滿足要求普碎。
當(dāng)根結(jié)點(diǎn)分裂時(shí)，因沒有父結(jié)點(diǎn)录平，則建立一個新的根麻车，B樹增高一層。

3階B樹的分裂

一棵三階 B 樹(2-3 樹)斗这，(b) 插入 30 之后; (c) 动猬、(d) 插入 26 之后;(e)~(g) 插入 85 之 后; (h)~(j) 插入 7 之后變化如下圖：

B樹的插入

B樹的刪除

如果想要在 B 樹上刪除一個關(guān)鍵字，首先需要找到這個關(guān)鍵字所在的結(jié)點(diǎn)表箭，從中刪去這個關(guān)鍵字赁咙。若 N 不是葉子結(jié)點(diǎn)，設(shè) K 是 N 中的第 i 個關(guān)鍵字免钻，則將指針 所指子樹中的最大關(guān)鍵字(或最小關(guān)鍵字)K’放在(K)的位置彼水，然后刪除 K’，而 K’一定在葉子結(jié)點(diǎn)上极舔。
從葉子結(jié)點(diǎn)中刪除一個關(guān)鍵字的情況是：
(1)若結(jié)點(diǎn)N中的關(guān)鍵字個數(shù)>?m/2?-1凤覆，在結(jié)點(diǎn)中直接刪除關(guān)鍵字K。
(2)若結(jié)點(diǎn)N中的關(guān)鍵字個數(shù)=?m/2?-1拆魏，若兄弟結(jié)點(diǎn)關(guān)鍵字個數(shù)>?m/2?-1盯桦，則將兄弟結(jié)點(diǎn)的最大(或最小)關(guān)鍵字上移到父結(jié)點(diǎn)中，再把父結(jié)點(diǎn)中下移一個到結(jié)點(diǎn)N渤刃。
下圖為刪除65借用兄弟結(jié)點(diǎn)示例：

兄弟可借

下圖演示了刪除50(兄弟可借)和刪除37(兄弟不可借且父結(jié)點(diǎn)兄弟也不可借)的刪除過程：

B樹的刪除

在實(shí)際的文件系統(tǒng)中，基本上不使用B樹随闪，而是使用B樹的一種變體，稱為m階樹骚勘。
它與B樹的主要不同是葉子結(jié)點(diǎn)中存儲記錄铐伴，所有的非葉子結(jié)點(diǎn)可以看成是索引，而其中的關(guān)鍵字是作為“分界關(guān)鍵字”俏讹，用來界定某一關(guān)鍵字的記錄所在的子樹当宴。
一棵 m 階的 B+樹和 m 階的 B 樹的差異在于:
(1)若一個結(jié)點(diǎn)有 n 棵子樹，則必含有n個關(guān)鍵字泽疆；
(2)所有葉子結(jié)點(diǎn)中包含了全部記錄的關(guān)鍵字信息以及這些關(guān)鍵字記錄的指針户矢，而且葉子結(jié)點(diǎn)按關(guān)鍵字的大小從小到大順序鏈接。
(3)所有的非葉子結(jié)點(diǎn)可以看成是索引的部分殉疼，結(jié)點(diǎn)中只含有其子樹的根結(jié)點(diǎn)中的最大(或最小)關(guān)鍵字梯浪。

B+樹

6 哈希(散列)表

哈希表的基本概念

基本思想：在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系堡掏；這樣，不經(jīng)過比較淤井，一次存取就能得到所查元素的查找方法布疼。
哈希函數(shù)：在記錄的關(guān)鍵字與記錄的存儲地址之間建立的一種對應(yīng)關(guān)系叫哈希函數(shù)。
哈希表：應(yīng)用哈希函數(shù)币狠，由記錄的關(guān)鍵字確定記錄在表中的地址游两，并將記錄放入此地址，這樣構(gòu)成的表叫哈希表漩绵。
哈希查找(又叫散列查找)：利用哈希函數(shù)進(jìn)行查找的過程叫哈希查找贱案。
沖突：對于不同的關(guān)鍵字，哈希值相同的現(xiàn)象叫沖突。
同義詞：具有相同函數(shù)值的兩個不同的關(guān)鍵字宝踪，稱為該哈希函數(shù)的同義詞侨糟。

設(shè)計(jì)散列表的方法

設(shè)計(jì)一個散列表應(yīng)包括：
①散列表的空間范圍，即確定散列函數(shù)的值域瘩燥。
②構(gòu)造合適的散列函數(shù)秕重，使得對于所有可能的元素，函數(shù)值均在散列表的地址空間范圍內(nèi)厉膀，且出現(xiàn)沖突的可能盡量小溶耘。
③處理沖突的方法。

1.直接定址法
取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)作哈希地址服鹅，即H(key) = key 或 H(key) = a * key + b凳兵。
特點(diǎn)：直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生重復(fù)企软，但實(shí)際中很少使用庐扫。

2.數(shù)字分析法
假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由 s 位數(shù)字組成(k1, k2, ..., kn)，分析關(guān)鍵字集中的全體仗哨，并從中提取分布均勻的若干位或它們的組合作為地址形庭。
此法僅適合于:能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。

3.平方取中法
若關(guān)鍵字的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象藻治，則先求關(guān)鍵字的平方值碘勉，以通過“平方”擴(kuò)大差別，同時(shí)平方值的中間幾位受到整個關(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 % p p≤m (表長)
即取關(guān)鍵碼除以 p 的余數(shù)作為散列地址症脂。使用除留余數(shù)法涝涤，選取合適的 p 很重要媚狰，若散列表表長為 m，則要求 p≤m阔拳，且接近 m 或等于 m崭孤。p 一般選取質(zhì)數(shù)，也可以是不包含小于 20 質(zhì)因子的合數(shù)。

6.隨機(jī)數(shù)法
H(key) = Random(key)辨宠，其中遗锣，Random 為偽隨機(jī)函數(shù)。
通常嗤形，此方法用于對長度不等的關(guān)鍵字構(gòu)造散列函數(shù)精偿。實(shí)際造表時(shí)，采用何種構(gòu)造散列函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))赋兵，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小还最。

沖突處理的方法

沖突處理：出現(xiàn)沖突時(shí)，為沖突元素找到另一個存儲位置毡惜。
1.開放定址法
基本方法：當(dāng)沖突發(fā)生時(shí)，形成某個探測序列斯撮，按此序列逐個探測散列表中的其它地址经伙，直到找到給定的關(guān)鍵字或一個空地址為止，將發(fā)生沖突的記錄放到該地址中勿锅。
①線性探測法
將散列表T看成循環(huán)向量帕膜。設(shè)初次發(fā)生沖突的地址是h，則依次探測T[h+1]溢十、T[h+2]...垮刹，直到T[m-1]時(shí)又循環(huán)到表頭，再次探測T[0],T[1]...张弛。
計(jì)算公式是：

其中Hash(key)是哈希函數(shù)荒典，m是散列表長度，是第i次探測時(shí)的增量序列吞鸭。

設(shè)散列表長為 7寺董，記錄關(guān)鍵字組為:15, 14, 28, 26, 56, 23，散列函數(shù):H(key)=key MOD 7刻剥，沖突處理采用線性探測法遮咖。
H(15) = 15 % 7 = 1
H(14) = 14 % 7 = 0
H(28) = 28 % 7 = 0 沖突
又沖突

H(26) = 26 % 7 = 5
H(56) = 56 % 7 = 0 沖突
又沖突
又沖突

H(23) = 23 % 7 = 2 沖突
又沖突

線性探測法的特點(diǎn)
優(yōu)點(diǎn)：只要散列表未滿，總能找到一個不沖突的散列地址漓藕。
缺點(diǎn)：每個產(chǎn)生沖突的記錄被散列到離沖突最近的空地址上陶珠，從而又增加了更多的沖突機(jī)會(稱為沖突的“聚集”)。

②二次探測法
增長序列為:
上面例題采用二次探測法進(jìn)行沖突處理
H(15) = 15 % 7 = 1
H(14) = 14 % 7 = 0
H(28) = 28 % 7 = 0 沖突
又沖突
又沖突

二次探測法的特點(diǎn)
優(yōu)點(diǎn)：探測序列跳躍式地散列到整個表中撵术，不易產(chǎn)生沖突的聚集現(xiàn)象背率。
缺點(diǎn)：不能保證探測到散列表的所有地址

③偽隨機(jī)探測法
增長序列使用一個偽隨機(jī)函數(shù)來產(chǎn)生一個落在閉區(qū)間[1,m-1]的隨機(jī)序列。

2.再哈希法
構(gòu)造若干個哈希函數(shù)，當(dāng)發(fā)生沖突時(shí)寝姿，利用不同的哈希函數(shù)再計(jì)算下一個新哈希地址交排，直到不發(fā)生沖突為止。
優(yōu)點(diǎn)：不易產(chǎn)生沖突的聚集現(xiàn)象饵筑。
缺點(diǎn)：計(jì)算時(shí)間增加埃篓。

3.鏈地址法
方法：將所有關(guān)鍵字為同義詞的記錄存儲在一個單鏈表中，并用一維數(shù)組存放鏈表的頭指針根资。哈希值相同的元素插入時(shí)可以在表頭或表尾插入架专。
優(yōu)點(diǎn):不易產(chǎn)生沖突的“聚集”;刪除記錄也很簡單。

例: 已知一組關(guān)鍵字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) 玄帕，哈希函數(shù)為:H(key)=key % 13部脚，用鏈地址法處理沖突 。

4.建立公共溢出區(qū)
方法：在基本散列表外裤纹，另外設(shè)立一個溢出表保存與基本表中記錄沖突的所有記錄委刘。
設(shè)散列表長為 m，設(shè)立基本散列表 hashtable[m]鹰椒，每個分量保存一個記錄;溢出表overtable[m]锡移，一旦某個記錄的散列地址發(fā)生沖突，都填入溢出表中漆际。
已知一組關(guān)鍵字(15, 4, 18, 7, 37, 47) 淆珊，散列表長度為 7 ，哈希函數(shù)為:H(key)=key % 7奸汇，用建立公共溢出區(qū)法處理沖突施符。
得到的基本表和溢出表如下:

hash表

溢出表

哈希查找過程及分析

7 字符串模式匹配

串的基本概念:串是零個或多個字符組成的有限序列。一般為:S=“c1c2c3...cn”其 中擂找，s 是串名;將一個串中若干個相連字符組成的子序列稱為該串的子串操刀。包含子串的串相應(yīng)地稱為主串。
串的模式匹配:子串在主串中的定位稱為模式匹配或串匹配(字符串匹配) 婴洼。模式匹配成功是指在主串 S 中能夠找到模式串 T骨坑，否則，稱模式串 T 在主串 S 中不存在柬采。(注意算法描述都是從 1 開始欢唾，c 語言設(shè)計(jì)是從 0 開始)

KMP算法
例:設(shè)有串 s=“abacabab” ，t=“abab” 粉捻。則第一次匹配過程如圖所示礁遣。

KMP核心思想

定義 next[j]函數(shù)為:

例:若模式串 P 為’ abaabc’，由定義可得 next 函數(shù)值(從頭尾比較相等的串)
j = 1 next[1] = 0
j = 2 a next[2] = 1
j = 3 ab next[3] = 1
j = 4 aba next[4] = 2
j = 5 abaa next[5] = 2
j = 6 abaab next[6] = 3

主串 S = 'a c a b a a b a a b c a c a a b c'
模式串 P = 'a b a a b c'

KMP匹配過程