常用查找算法[定义].pdf
版权申诉
192 浏览量
2021-10-12
03:57:02
上传
评论
收藏 101KB PDF 举报
目录
1 概念
2 顺序查找
3 二分查找
4 分块查找
5 哈希表查找
展开全部
1 概念
2 顺序查找
3 二分查找
4 分块查找
5 哈希表查找
收起
摘要
请用一段简单的话描述该词条，马上 添加摘要 。
查找算法 -概念
查找是在大量的信息中寻找一个特定的信息元素， 在计算机应用中， 查找是常用的基本运算，
例如 编译 程序中符号表的查找。 用关键字标识一个 数据元素 ，查找时根据给定的某个值， 在
表中确定一个关键字的值等于给定值的记录或数据元素。 在计算机中进行查找的方法是根据
表中的记录的 组织结构 确定的。
顺序查找 也称为线形查找， 从数据结构线形表的一端开始， 顺序扫描， 依次将扫描到的结点
关键字与给定值 k 相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于 k
的结点，表示查找失败。
二分查找 要求线形表中的结点按 关键字 值升序或降序排列， 用给定值 k 先与中间结点的关键
字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等， 再根据 k 与该中
间结点关键字的比较结果确定下一步查找哪个子表， 这样递归进行， 直到查找到或查找结束
发现表中没有这样的结点。
分块查找 也称为索引查找， 把线形分成若干块， 在每一块中的数据元素的存储顺序是任意的，
但要求块与块之间须按关键字值的大小有序排列， 还要建立一个按关键字值递增顺序排列的
索引表，索引表中的一项对应线形表中的一块，索引项包括两个内容：① 键域存放相应块
的最大关键字；② 链域存放指向本块第一个结点的指针。分块查找分两步进行，先确定待
查找的结点属于哪一块，然后在块内查找结点。
哈希表查找 是通过对记录的关键字值进行运算， 直接求出结点的地址， 是关键字到地址的直
接转换方法，不用反复比较。假设 f 包含 n 个结点， Ri 为其中某个结点（ 1≤i ≤ｎ）， keyi 是
资源评论
czq131452007
- 粉丝: 2
- 资源: 12万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减4.47元 开通VIP
