顺序查找
1.一般线性表
typedef struct{
ElemType *elem;//0号单元留空
int length;
}STable;
int search(STable table,ElemType key){
table.elem[0] = key;//哨兵
for(int i = table.length;table.elem[i] != key; --i);
return i;
}
折半查找
int binary_search(SeqList list,ElemType key){
int low = 0;high = list.length-1;mid;
while(low <= high){
mid = (low+high)/2;
if(list.elem[mid] == key)
return mid;
else if(list.elem[mid] < key)
low = mid+1;
else
high = mid-1;
}
return -1;//查找失败
}
B树和B+树
$B$树中所有结点的子结点数的最大值称为$B$树的阶，一个 $m$ 阶的$B$树是一个有以下属性的树：
1.每一个结点最多有 $m $个子结点，即每个结点至多含有$m-1$个关键字
2.每一个非叶子结点（除根结点）最少有 $⌈m/2⌉$ 个子结点,即至少含有$[m/2]-1$个关键字
3.如果根结点不是叶子结点，那么它至少有两个子结点
4.有 $k$ 个子结点的非叶子结点拥有 $k − 1$ 个键
5.所有的叶子结点都在同一层
非根内部结点的关键字个数$n$范围：$[m/2]-1 \leq n \leq m-1$,根结点关键字个数$n$范围：$1 \leq n\leq m-1$
每一个内部结点的键将结点的子树分开。
例如，如果一个内部结点有3个子结点（子树），那么它就必须有两个键： $a_1 $和 $a_2$
左边子树的所有值都必须小于 $a_1$ ，中间子树的所有值都必须在 $a_1$ 和$a_2$ 之间，右边子树的所有值都必须大于$ a_2$
B树的查找
1.在$B$中找结点 (读入内存) 2.在结点内找关键字(通过顺序查找或折半查找查找等于key的关键字)
B树的插入
所有的插入都从根结点开始，要插入一个新的元素，首先搜索这棵树，找到新元素应该被添加到的叶子结点
将新元素插入到这一结点中的步骤如下：
如果结点拥有的元素数量小于最大值，那么有空间容纳新的元素，将新元素插入到这一结点，且保持结点中元素有序，否则这一结点已经满了，将它平均地分裂成两个结点：从叶子结点的元素和新的元素中选择出中位数；小于这一中位数的元素放入左边结点，大于这一中位数的元素放入右边结点，中位数作为分隔值.
分隔值被插入到父结点中，这可能会造成父结点分裂，分裂父结点时可能又会使它的父结点分裂，以此类推.如果没有父结点（这一结点是根结点），就创建一个新的根结点（增加了树的高度）,即如果分裂一直上升到根节点，那么一个新的根节点会被创建，它有一个分隔值和两个子节点
以5阶B树为例
[]: https://www.cnblogs.com/nullzx/p/8729425.html
1.空树中插入39
2.继续插入22，97和41
3.继续插入53
插入后超过了最大允许的关键字个数4，需以中位数(41)为中心进行分裂
4.依次插入13，21，40，同样会造成分裂，结果如下图
5.依次插入30，27, 33 ；36，35，34 ；24，29
6.插入key值为26的记录
当前结点需要以27为中心分裂,并向父结点插入27
插入后导致当前结点（即根结点）也需要分裂
B树的删除
删除时，需要判断结点中关键字的个数$\geqslant [m/2]-1$
5阶B树为例，结点最多有4个key,最少有2个key
[]: https://www.cnblogs.com/nullzx/p/8729425.html
1.B树中删除21，删除后结点中的关键字个数仍然大于等2，删除结束
2.删除27，27位于非叶子结点中，利用27的后继28替代
删除后，当前叶子结点的关键字的个数小于2，而它的兄弟结点中有3个关键字，从兄弟结点中借取一个关键字
3.删除32
删除后，当前结点中只有一个关键字，而兄弟结点中也仅有2个关键字，只能让父结点中的30下移并和兄弟结点中的关键字合并，成为一个新的结点，当前结点的指针指向父结点
4.删除40
同理，当前结点的关键字数小于2，兄弟结点中没有多余关键字，所以父结点中的关键字下移，和兄弟结点(左右兄弟结点都可)的关键字合
当前结点关键字个数小于2，继续合并
B+树
1.每个分支结点最多有$m$个子结点
2.结点的子结点个数与关键字个数相等(或结点的子结点个数 = 关键字个数+1)
3.所有叶结点包含全部关键字及指向记录的指针，且叶结点中关键字按大小顺序排列，所有相邻结点按大小顺序互相链接
4.非根内部结点的关键字个数$n$范围：$[m/2] \leq n \leq m$,根结点关键字个数$n$范围：$1 \leq n\leq m$
B+树的插入
以5阶B树为例
1.空树中插入5
2.依次插入8，10，15
3.插入16
插入16后超过了关键字的个数限制，需进行分裂
4.插入17
5.插入18
当前结点的关键字个数大于限制的个数，需进行分裂
6.插入若干数据
7.插入7
当前结点的关键字个数大于限制的个数，需进行分裂
当前结点的关键字个数大于限制的个数，需进行分裂
B+树的删除
以5阶B树为例
1.删除22
2.删除15
删除后当前结点只有一个关键字，不满足条件，而兄弟结点有三个关键字，从兄弟结点中借关键字为9,同时更新将父结点中的关键字由10变为9，删除结束
3.删除7
散列(hash)表
散列函数
一个把查找表中的关键字映射为该关键字对应的地址函数，记$Hash(key)=Address$
1.直接定址法 $Hash(key)=a\times key+b$，($a,b$未常数)
2.除留余数法 $Hash(key)=key\%p$，($p$为质数)
3.数字分析法 设关键字是$r$进制数，选取数码分布较为均匀的若干位作为散列地址
4.平方取中法 取关键字的平方值的中间几位作为散列地址
5.折叠法 将关键字分割成位数相同的块，取块的叠加和作为散列地址
冲突处理
散列函数可能会把两个或两个以上的的不同关键字映射到同一地址，这种情况称为”冲突”
设散列函数为$Hash(key),H_i$表示发生冲突后第$i$次探测的散列地址
1.开放定址法
$m$表示散列表长度，$d_i$为增量序列
$d_i$的选取方法：
1) 线性探测法 $d_i=0,1,2,3,\cdots,m-1$
2) 平方探测法 $d_i=0^2,1^2,-1^2,2^2,-2^2,\cdots ,k^2,-k^2(k\leqslant m/2)$
3) 再散列法或双散列法 $d_i=Hash_2(key)$，即$H_i=(Hash(key)+i*Hash_2(key))\%m$($i$为冲突次数)
4) 伪随机序列法 $d_i=$伪随机数序列
2.拉链法
同义词存储在一个线性链表$L_i$中,散列地址为$i$的同义词链表$L_i$的头指针存放在散列表第$i$个单元中
散列查找过程
1.初始化：$address = Hash(key)$
2.若$L[address]=NULL$,则查找失败；若$L[address]\neq NULL$且$L[address]\neq key$，则$H_1=(address+1)\%m$,若$L[H_1]\neq NULL$且$L[H_1]\neq key$,则$H_2=(H_1+2)\%m$,若$L[H_2]\neq NULL$且$L[H_1]\neq key$,则$H_3=\cdots$
重复执行$H{i+1}=(H_i+(i+1))\%m$ ($i=1,2,3,\cdots,m-1$),直到$L[H{i+1}]=key或L[H_{i+1}]=NULL$
字符串模式匹配
1.简单的模式匹配算法
从主串S的指定字符开始，和模式串的第一个字符比较，若相等则继续逐个比较后续字符，直到模式串中的每个字符依次和主串的一个连续字符序列相等，则匹配成功；若比较过程中有某对字符不相等，则从主串的下一个字符重新与模式串的第一个字符相比较。
int matching(String target, String pattern, int begin) {
// i为目标串target的索引
int i = begin;
// j为模式串pattern的索引
int j = 0;
if (target == null || pattern == null || begin > target.length()) {
return -1;
}
while (i < target.length() && j < pattern.length()){
if (target[i] == pattern[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
// 模式串是否存在于目标串
if (j == pattern.length()) {
return i - pattern.length() ;
}
return -1;
}
2.KMP模式匹配算法
wait
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0协议 。转载请注明出处！