查找查找 - 锐客网

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 = https://www.it610.com/article/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 = https://www.it610.com/article/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); } }