㈠ 查找、B樹、哈希表、字元串模式匹配
一棵度為m的B樹稱為m階B樹，是一棵平衡的m路查找樹，其定義是：
一棵m階B樹，或者是空樹，或者是滿足以下性質的m叉樹：
(1)根結點或者是葉子結點，或者至少有兩棵子樹，至多有m棵子樹；
(2)除根結點外，所有非葉子結點至少有⌈m/2⌉棵子樹，至多有m棵子樹；
(3)所有葉子結點都在樹的同一層上。
(4)每個結點應包含如下信息：
其中n是結點中關鍵字的個數，且⌈m/2⌉-1≤n≤m-1，n+1為子樹的棵樹。
是關鍵字，且 ，即遞增。
為指向孩子結點的指針，且 所指向的子樹中所有結點的關鍵字都小於 ， 所指向的子樹中的所有結點的關鍵字都大於 ；
類似二叉排序樹的查找，所不同的是 B 樹每個結點上是多關鍵碼的有序表，在到達某個結點時，先在有序表中查找，若找到，則查找成功;否則，到按照對應的指針信息指向的子樹中去查找，當到達葉子結點時，則說明樹中沒有對應的關鍵碼，查找失敗。即在 B 樹上的查找過程是一個順指針查找結點和在結點中查找關鍵碼交叉進行的過程。
B樹的生成也是從空樹起，逐個插入關鍵字。
插入時不是每插入一個關鍵字就添加一個葉子結點，而是首先在最低層的某個葉子結點中添加一個關鍵字，然後有可能「分裂」。
(1)插入思想
①在B樹種查找關鍵字K，若找到，表明關鍵字已存在，返回；否則，K的查找操作失敗於某個葉子結點，轉②
②將K插入到該葉子結點中，插入時，若
※葉子結點的關鍵字數<m-1，則直接插入；
※葉子結點的關鍵字數=m-1，將結點「分裂」
(2)分裂方法
設待分裂結點p包含信息為： ，從其中間位置分為兩個結點： 。並將中間關鍵字 插入到p的父結點中，以分裂後的兩個結點作為中間關鍵字 的兩個子結點。
當把中間關鍵字 插入到p的父結點後，父結點可能也不滿足m階B樹的要求，則必須對父結點進行分裂，一直進行下去，直到沒有父結點或分裂後的父結點滿足要求。
當根結點分裂時，因沒有父結點，則建立一個新的根，B樹增高一層。
一棵三階 B 樹(2-3 樹)，(b) 插入 30 之後; (c) 、(d) 插入 26 之後;(e)~(g) 插入 85 之 後; (h)~(j) 插入 7 之後變化如下圖：
如果想要在 B 樹上刪除一個關鍵字，首先需要找到這個關鍵字所在的結點，從中刪去這個關鍵字。若 N 不是葉子結點，設 K 是 N 中的第 i 個關鍵字，則將指針 所指子樹中的最大關鍵字(或最小關鍵字)K』放在(K)的位置，然後刪除 K』，而 K』一定在葉子結點上。
從葉子結點中刪除一個關鍵字的情況是：
(1)若結點N中的關鍵字個數>⌈m/2⌉-1，在結點中直接刪除關鍵字K。
(2)若結點N中的關鍵字個數=⌈m/2⌉-1，若兄弟結點關鍵字個數>⌈m/2⌉-1，則將兄弟結點的最大(或最小)關鍵字上移到父結點中，再把父結點中下移一個到結點N。
下圖為刪除65借用兄弟結點示例：
下圖演示了刪除50(兄弟可借)和刪除37(兄弟不可借且父結點兄弟也不可借)的刪除過程：
在實際的文件系統中，基本上不使用B樹，而是使用B樹的一種變體，稱為m階 樹。
它與B樹的主要不同是葉子結點中存儲記錄，所有的非葉子結點可以看成是索引，而其中的關鍵字是作為「分界關鍵字」，用來界定某一關鍵字的記錄所在的子樹。
一棵 m 階的 B+樹和 m 階的 B 樹的差異在於:
(1)若一個結點有 n 棵子樹，則必含有n個關鍵字；
(2)所有葉子結點中包含了全部記錄的關鍵字信息以及這些關鍵字記錄的指針，而且葉子結點按關鍵字的大小從小到大順序鏈接。
(3)所有的非葉子結點可以看成是索引的部分，結點中只含有其子樹的根結點中的最大(或最小)關鍵字。
基本思想：在記錄的存儲地址和它的關鍵字之間建立一個確定的對應關系；這樣，不經過比較，一次存取就能得到所查元素的查找方法。
哈希函數：在記錄的關鍵字與記錄的存儲地址之間建立的一種對應關系叫哈希函數。
哈希表：應用哈希函數，由記錄的關鍵字確定記錄在表中的地址，並將記錄放入此地址，這樣構成的表叫哈希表。
哈希查找(又叫散列查找)：利用哈希函數進行查找的過程叫哈希查找。
沖突：對於不同的關鍵字，哈希值相同的現象叫沖突。
同義詞：具有相同函數值的兩個不同的關鍵字，稱為該哈希函數的同義詞。
設計一個散列表應包括：
①散列表的空間范圍，即確定散列函數的值域。
②構造合適的散列函數，使得對於所有可能的元素，函數值均在散列表的地址空間范圍內，且出現沖突的可能盡量小。
③處理沖突的方法。
1.直接定址法
取關鍵字或關鍵字的某個線性函數作哈希地址，即H(key) = key 或 H(key) = a * key + b。
特點：直接定址法所得地址集合與關鍵字集合大小相等，不會發生重復，但實際中很少使用。
2.數字分析法
假設關鍵字集合中的每個關鍵字都是由 s 位數字組成(k1, k2, ..., kn)，分析關鍵字集中的全體，並從中提取分布均勻的若干位或它們的組合作為地址。
此法僅適合於:能預先估計出全體關鍵字的每一位上各種數字出現的頻度。
3.平方取中法
若關鍵字的每一位都有某些數字重復出現頻度很高的現象，則先求關鍵字的平方值，以通過「平方」擴大差別，同時平方值的中間幾位受到整個關鍵字中各位的影響。
此方法適合於:關鍵字中的每一位都有某些數字重復出現頻度很高的現象。
4.折疊法
若關鍵字的位數特別多，則可將其分割成幾部分，然後取它們的疊加和為散列地址。可有:移位疊加和間界疊加兩種處理方法。
(1)移位法:將各部分的最後一位對齊相加。
(2)間界疊加法:從一端向另一端沿各部分分界來回折疊後，最後一位對齊相加。此方法適合於:關鍵字的數字位數特別多。
5.除留余數法
H(key) = key % p p≤m (表長)
即取關鍵碼除以 p 的余數作為散列地址。使用除留余數法，選取合適的 p 很重要，若散列表表長為 m，則要求 p≤m，且接近 m 或等於 m。p 一般選取質數，也可以是不包含小於 20 質因子的合數。
6.隨機數法
H(key) = Random(key)，其中，Random 為偽隨機函數。
通常，此方法用於對長度不等的關鍵字構造散列函數。實際造表時，採用何種構造散列函數的方法取決於建表的關鍵字集合的情況(包括關鍵字的范圍和形態)，總的原則是使產生沖突的可能性降到盡可能地小。
沖突處理：出現沖突時，為沖突元素找到另一個存儲位置。
1.開放定址法
基本方法：當沖突發生時，形成某個探測序列，按此序列逐個探測散列表中的其它地址，直到找到給定的關鍵字或一個空地址為止，將發生沖突的記錄放到該地址中。
①線性探測法
將散列表T看成循環向量。設初次發生沖突的地址是h，則依次探測T[h+1]、T[h+2]...，直到T[m-1]時又循環到表頭，再次探測T[0],T[1]...。
計算公式是：
其中Hash(key)是哈希函數，m是散列表長度， 是第i次探測時的增量序列。
設散列表長為 7，記錄關鍵字組為:15, 14, 28, 26, 56, 23，散列函數: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 沖突
又沖突
線性探測法的特點
優點：只要散列表未滿，總能找到一個不沖突的散列地址。
缺點：每個產生沖突的記錄被散列到離沖突最近的空地址上，從而又增加了更多的沖突機會(稱為沖突的「聚集」)。
②二次探測法
增長序列為:
上面例題採用二次探測法進行沖突處理
H(15) = 15 % 7 = 1
H(14) = 14 % 7 = 0
H(28) = 28 % 7 = 0 沖突
又沖突
又沖突
二次探測法的特點
優點：探測序列跳躍式地散列到整個表中，不易產生沖突的聚集現象。
缺點：不能保證探測到散列表的所有地址
③偽隨機探測法
增長序列使用一個偽隨機函數來產生一個落在閉區間[1,m-1]的隨機序列。
2.再哈希法
構造若干個哈希函數，當發生沖突時，利用不同的哈希函數再計算下一個新哈希地址，直到不發生沖突為止。
優點：不易產生沖突的聚集現象。
缺點：計算時間增加。
3.鏈地址法
方法：將所有關鍵字為同義詞的記錄存儲在一個單鏈表中，並用一維數組存放鏈表的頭指針。哈希值相同的元素插入時可以在表頭或表尾插入。
優點:不易產生沖突的「聚集」;刪除記錄也很簡單。
例: 已知一組關鍵字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) ，哈希函數為:H(key)=key % 13，用鏈地址法處理沖突 。
4.建立公共溢出區
方法：在基本散列表外，另外設立一個溢出表保存與基本表中記錄沖突的所有記錄。
設散列表長為 m，設立基本散列表 hashtable[m]，每個分量保存一個記錄;溢出表overtable[m]，一旦某個記錄的散列地址發生沖突，都填入溢出表中。
已知一組關鍵字(15, 4, 18, 7, 37, 47) ，散列表長度為 7 ，哈希函數為:H(key)=key % 7，用建立公共溢出區法處理沖突。
得到的基本表和溢出表如下:
串的基本概念:串是零個或多個字元組成的有限序列。一般為:S=「c1c2c3...cn」其 中，s 是串名;將一個串中若干個相連字元組成的子序列稱為該串的子串。包含子串的串相應地稱為主串。
串的模式匹配:子串在主串中的定位稱為模式匹配或串匹配(字元串匹配) 。模式匹配成功是指在主串 S 中能夠找到模式串 T，否則，稱模式串 T 在主串 S 中不存在。(注意演算法描述都是從 1 開始，c 語言設計是從 0 開始)
KMP演算法
例:設有串 s=「abacabab」 ，t=「abab」 。則第一次匹配過程如圖所示。
定義 next[j]函數為:
例:若模式串 P 為』 abaabc』，由定義可得 next 函數值(從頭尾比較相等的串)
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'
㈡ 數據結構中什麼是B樹
B 樹是為了磁碟或其它存儲設備而設計的一種多叉（下面你會看到，相對於二叉，B樹每個內結點有多個分支，即多叉）平衡查找樹。
B 樹又叫平衡多路查找樹。一棵m階的B 樹 (m叉樹)的特性如下：樹中每個結點最多含有m個孩子（m>=2）；除根結點和葉子結點外，其它每個結點至少有[ceil(m / 2)]個孩子（其中ceil(x)是一個取上限的函數）；若根結點不是葉子結點，則至少有2個孩子（特殊情況：沒有孩子的根結點，即根結點為葉子結點，整棵樹只有一個根節點）；所有葉子結點都出現在同一層，葉子結點不包含任何關鍵字信息(可以看做是外部接點或查詢失敗的接點，實際上這些結點不存在，指向這些結點的指針都為null)；每個非終端結點中包含有n個關鍵字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
a) Ki (i=1...n)為關鍵字，且關鍵字按順序升序排序K(i-1)< Ki。
b) Pi為指向子樹根的接點，且指針P(i-1)指向子樹種所有結點的關鍵字均小於Ki，但都大於K(i-1)。
c) 關鍵字的個數n必須滿足： [ceil(m / 2)-1]<= n <= m-1。
㈢ c語言數據結構 什麼叫 最下層的非葉結點 b樹里的
在b樹種，當在葉子結點處於第L+1層的B樹中插入關鍵字時，被插入的關鍵字總是進入第L層的結點。
b樹中所有葉子結點都在同一層,並且不帶任何信息。
所以你所說的最下層的非葉子節點是不是代表倒數第二層的能插入關鍵字的那一層，你是想要進行刪除操作嗎？
㈣ 高度為5的3階b樹至少有多少個關鍵字
高度為5的3階b樹至少有31個關鍵字。
B樹和B+樹區別：
關鍵字數量不同，B+樹分支結點M個關鍵字，葉子節點也有M個，B樹分支結點則存在 k-1 個關鍵碼。
數據存儲位置不同，B+樹數據存儲在葉子結點上，B樹存儲在每個結點上。
查詢不同，B+樹是從根節點到葉子節點的路徑，B樹是只需要找到數據就可以。
分支節點存儲信息不同，B+樹存索引信息，B樹存的是數據關鍵字。
B樹，二叉樹，每個結點只存儲一個關鍵字，等於則命中，小於走左結點，大於走右結點。
B-樹，多路搜索樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字范圍的子結點，所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中。
B+樹，在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引，B+樹總是到葉子結點才命中。
B*樹，在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率從1/2提高到2/3。