first edit:20170702
last edit:20170704
一、概念
- 查找表：同一类型数据元素的集合
- 关键字：数据元素中某个数据项的值
- 主关键字：可以唯一地标识一个记录的关键字。如成绩表中学生学号
- 次关键字：可以识别多个数据元素的关键字。如成绩表中学生总成绩
- 静态查找表：只作查找操作
- 动态查找表：查找过程中插入表中不存在元素，或者从表中删除已经存在的某个元素
二、顺序表查找
- 顺序查找
- 思想
从表中首个元素开始逐个查找 - 实现
int sequentialSearch(int *a, int n, int key) {
// a为数组，n为要查找元素的个数，key为要查找的关键字
// 查找成功返回匹配元素位置，否则返回INFINITY
for (int i = 0; i < n; i++)
if (a[i] == key)
return i;
return INFINITY;
}
- 分析
-- 复杂度O(n)
-- 可以将被查找概率较大的元素放在前面，不常用记录放在后面，这样可以提高实际使用时的效率
三、有序表查找
- 二分查找
- 思想
在有序表中，取中间记录作为比较对象。每次未命中比较都会将搜索范围减半 - 实现
// 二分查找
int binarySearch(int *a, int n, int key) {
// a为有序数组，n为要查找元素的个数，key为要查找的关键字
// 查找成功返回匹配元素位置，否则返回INFINITY
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (key < a[mid])
high = mid - 1;
else if (key > a[mid])
low = mid + 1;
else
return mid;
}
return INFINITY;
}
- 分析
-- 复杂度 O(logn)
-- 要求查找表内元素有序
-- 对静态查找表，该算法较好
-- 对于需要频繁执行插入或删除操作的动态查找表，维护表内元素有序的代价较高
- 插值查找
-
思想
二分查找每次从中间查找并非最优→例如，在字典中查找apple，会从靠前的位置先查找→更新mid的计算公式为
大话数据结构p302→这样能快速的使查找范围逼近待查找值
- 实现
int insertSearch(int *a, int n, int key) {
// a为有序数组，n为要查找元素的个数，key为要查找的关键字
// 查找成功返回匹配元素位置，否则返回INFINITY
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low)*(key - a[low]) / (a[high] - a[low]);// 插值计算公式
if (key < a[mid])
high = mid - 1;
else if (key > a[mid])
low = mid + 1;
else
return mid;
}
return INFINITY;
}
3.分析
-- 复杂度仍为O(logn)
-- 但对于表长较大，且关键字分布较均匀的查找表来说。平均性能要优于二分查找
- 裴波那契查找
- 思想
- 实现
- 分析
四、线性索引查找
- 概念
- 索引：把每个关键字和它对应的记录相关联的过程
- 线性索引：将索引项集合组织为线性结构
- 稠密索引：在线性索引中，每个元素对应一个索引项→索引项按关键码有序排列→查找快，但索引量大。
- 分块索引：对数据集进行分块，使其块间有序，块内无序→索引项包括三个数据项：最大关键码，块中的记录个数→指向块首元素数据的指针→**兼顾了减少索引项数目和查找速度
- 倒排索引：查找具有相同次关键字的所有记录的记录号→索引项包括两个数据项：次关键吗、记录号表→优点是查找快，缺点是记录号表不定长
五、二叉排序树
- 概念
二叉排序树/二叉查找树，或者是一颗空树，或者具有以下性质：- 若它的做子树不为空，则左子树上所有节点均小于它的根结构的值；
- 若右子树不为空，则右子树上所有节点均大于它的根节点的值；
- 左右子树也是二叉排序树
- 中序遍历二叉排序树，得到有序序列
- 同时兼顾插入删除和查找操作的速度
- 查找操作
- 递归调用查找函数，程序调用方法为SearchBST(v,key,NULL,NULL)→初始的father和result为NULL→如果是写成BST类的方法，那么应该是返回result，father可以作为类的一个私有成员
bool SearchBST(BiTree v, int key,BiTree father, BiTree &result){
// 查找成功→返回true，result保存指向命中节点的指针
// 查找失败→返回false,result保存指向查找路径上访问的最后一个节点
// 如果是空树的话，result也是空指针
if (!v) {
result = father;
return false;
}
else if (key == v->data) {
result = v;
return true;
}
else
SearchBST(((key < v->data ? v->lchild : v->rchild)), key, v,result);
}
- 插入操作
- 先用查找操作找到合适的插入位置，注意新建分配节点
bool InsertBST(BiTree &v, int key) {
// 当二叉树v中不存在关键字key时，插入并返回true
// 当二叉树v中存在关键字key时，返回false
BiTree p = NULL;
if (!SearchBST(v, key, NULL, p)) { //查找不成功
// 这里就体现出了p的作用，p为查找路径上访问的最后一个节点，
// 同时，p节点肯定是有一个子节点是空的，所以key的插入后即为p的子节点
BiTNode *s = new BiTNode;
s->data = key;
s->lchild = NULL; s->rchild = NULL;
// 注意如果当且仅当v是空树，p为空，此时新建节点为跟节点
if (!p)
v = s;
else if (key < p->data)
p->lchild = s;
else
p->rchild = s;
return true;
}
else
return false;
}
- 删除操作
- 使用delete(p)删除需要删除的节点，因为所有节点都是用new新建的
- 考虑四种情况：
- 不存在待删除的节点→返回false
- 待删除节点为叶子节点→直接删除
- 只有左子树或只有右子树→删除原有节点，并用左子树替代
-
左右子树都存在→先找到左子树中最大的值，替代该节点的值；删除左子树中最大节点，然后重接其父节点的左右子树→**注意要考虑待删除节点的左子节点就没有右子节点的情况
image.png
待删除节点的左子节点就没有右子节点的情况
bool deleteBST(BiTree &v) {
if (v->rchild == NULL) {
BiTree q = v;
v = v->rchild;
delete(q);
}
else if (v->lchild == NULL){
BiTree q = v;
v = v->rchild;
delete(q);
}
else {
BiTree q = v;
BiTree s = v->lchild; //转左，然后向右到尽头，这样就是左子树中最大的
while (s->rchild) {
q = s; // q指向左子树最大节点的父节点
s = s->rchild; // s指向左子树中最大的节点
}
v->data = s->data;
if (q != v)
q->rchild = s->lchild;
else // 如果v的左子节点就没有右节点
q->lchild = s->lchild;
delete(s);
}
return true;
}
bool DeleteBST(BiTree &v, int key) {
if (!v) //不存在关键字等于key的节点
return false;
else {
if (key == v->data)
return deleteBST(v);
else if (key < v->data)
return DeleteBST(v->lchild, key);
else
return DeleteBST(v->rchild, key);
}
}
