㈠ 查找、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。