数据结构 检索方法

数据结构 检索方法

搜索优化admin2020-11-21 21:40:398A+A-

  数据结构 检索方法_工学_高等教育_教育专区。第5章 检索方法 检索的定义:在特定的数据元素集合中寻找关键字与给定值相 检索的定义 在特定的数据元素集合中寻找关键字与给定值相 查找, 检索。 等的元素并输出寻找结果的过程称为查找 也叫检索 等的元

  第5章 检索方法 检索的定义:在特定的数据元素集合中寻找关键字与给定值相 检索的定义 在特定的数据元素集合中寻找关键字与给定值相 查找, 检索。 等的元素并输出寻找结果的过程称为查找 也叫检索 等的元素并输出寻找结果的过程称为查找,也叫检索。 关键字:指的是数据元素中用以标识该数据元素的某个数据项 关键字 指的是数据元素中用以标识该数据元素的某个数据项 的值,如学生成绩表中,学生可以同名,同分等, 的值,如学生成绩表中,学生可以同名,同分等,只有学号是各 不相同的,一个学号就对应一个学生,所以学号是关键字。 不相同的,一个学号就对应一个学生,所以学号是关键字。如果 某数据元素只有一个数据项,那么该数据元素的值就是关键字。 某数据元素只有一个数据项,那么该数据元素的值就是关键字。 检索方法包括:顺序查找;二分查找(又称折半查找);索 检索方法包括:顺序查找;二分查找(又称折半查找);索 ); 引查找(又称分块查找); );Hash查找(哈希表,散列表)。 查找( 引查找(又称分块查找); 查找 哈希表,散列表)。 顺序查找 1.顺序查找的基本思想 . 顺序查找是一种最简单的查找方法,它的基本思想是: 顺序查找是一种最简单的查找方法,它的基本思想是:从 表的一端开始,顺序扫描线性表,依次将扫描到的结点关键字 表的一端开始, 顺序扫描线性表, 和待找的值K相比较,若相等,则查找成功, 和待找的值K相比较,若相等,则查找成功,若整个表扫描完 仍末找到关键字等于K的元素,则查找失败。 毕,仍末找到关键字等于K的元素,则查找失败。 顺序查找既适用于顺序表,也适用于链表。若用顺序表, 顺序查找既适用于顺序表,也适用于链表。若用顺序表, 既适用于顺序表 查找可从前往后扫描,也可从后往前扫描,但若采用单链表, 查找可从前往后扫描,也可从后往前扫描,但若采用单链表, 则只能从前往后扫描。另外, 则只能从前往后扫描。另外,顺序查找的表中元素可以是无序 的。 衡量一个查找算法性能优劣的标准是平均查找长度, 衡量一个查找算法性能优劣的标准是平均查找长度,即在 查找成功的情况下所需的平均比较次数。对于等概率顺序查找, 查找成功的情况下所需的平均比较次数。对于等概率顺序查找, 它的平均查找长度为: 它的平均查找长度为 : ( n+1) /2。 若失败 , 平均比较结点个 ) 。 若失败, 数为n+1。 。 数为 二分查找 1.二分查找的基本思想 二分查找的基本思想 二分查找,也称折半查找,是一种高效率的查找方法。 二分查找,也称折半查找,是一种高效率的查找方法。 但要求表中元素必须按关键字有序(升序或降序 升序或降序)。 但要求表中元素必须按关键字有序 升序或降序 。不妨假 设表中元素为升序排列。二分查找的基本思想是: 设表中元素为升序排列。二分查找的基本思想是:首先将 待查值K与有序表 与有序表array[0]到array[n-1]的中点 的中点mid上的关 待查值 与有序表 到 的中点 上的关 键字array[mid].key进行比较,若相等,则查找成功;否 进行比较, 键字 进行比较 若相等,则查找成功; 则在array[1]到array[mid-1] 则,若array[mid].keyk , 则在 到 中继续查找,若有array[mid].keyk , 则在 则在array[mid+1] 中继续查找,若有 中继续查找。 到array[n-1]中继续查找。每通过一次关键字的比较,区 中继续查找 每通过一次关键字的比较, 间的长度就缩小一半,区间的个数就增加一倍, 间的长度就缩小一半,区间的个数就增加一倍,如此不断 进行下去,直到找到关键字为K的元素 的元素; 进行下去,直到找到关键字为 的元素;若当前的查找区 间为空(表示查找失败 表示查找失败)。 间为空 表示查找失败 。 例 如 , 假 设 给 定 有 序 表 中 关 键 字 为 05,13,19,21,37,56,64,74,80,88,92 将 查 找 K=21 和 K=85的情况描述为图8-1及图8-2形式。 0 0 11 22 33 4 4 5 5 6 6 7 7 88 9 9 1010 [ 05 13 19 21 37 56 64 74 80 88 92 ] low (a) 初始情形 hig 0 [ 05 1 13 2 19 3 21 4 37 ] 5 56 6 64 7 74 8 9 10 80 88 92 low (b) hig mid 经过一次比较后的情形 0 [05 1 13 2 19 3 21 4 37 5 ] 56 6 64 7 74 8 9 10 80 88 92 low mid hig (c ) 经过二次比较后的情形 图 8-1 (array[mid].key=19) 查找 K=21 的示意图 0 05 1 13 2 19 [ 3 21 4 37 5 ] 56 6 64 7 74 8 80 9 10 88 92 mid low hig (d ) 经过三次比较后的情形 图 8-1 (array[mid].key=21) 查找成功) 查找 K=21 的示意图 (查找成功 查找成功 0 0 [ 05 1 1 13 2 2 19 3 7 3 44 55 66 7 21 37 56 64 74 8 10 8 99 10 80 88 92 ] low (a) 初始情形 hig 0 05 1 13 2 19 3 21 4 37 5 56 [ 6 64 7 74 8 80 9 10 88 92 ] mid (b) low hig 经过一次比较后的情形 0 05 1 13 2 19 3 21 4 37 5 56 [ 6 64 7 74 8 80 9 10 88 92 ] low (c) mid hig 经过二次比较后的情形 0 05 1 13 2 19 3 21 4 37 5 56 6 64 7 74 8 80 [ 9 10 88 92 ] low (d) 经过三次比较后的情形 mid hig 0 05 1 13 2 19 3 21 4 37 5 56 6 64 7 74 8 80 9 10 88 92 ] hig (e) 经过四次比较后的情形(higlow) 经过四次比较后的情形 low 图8-2 查找 查找K=85 的示意图 (查找不成功 查找不成功) 查找不成功 二分查找需事先对数据元素进行排序, 二分查找需事先对数据元素进行排序,并且 只适用于顺序存储结构的线性表, 只适用于顺序存储结构的线性表,无法灵活的适 应动态变化的要求。因为若插入新元素, 应动态变化的要求。因为若插入新元素,则需将 序列从新排序,若删除元素, 序列从新排序,若删除元素,则需移动该元素后 的所有元素。但它具有比较次数少、 的所有元素。但它具有比较次数少、查找时间短 的特点。 的特点。 若二分查找成功, 若二分查找成功,则给定值最多与 「㏒2 」 个关键字进行比较 个关键字进行比较。 「㏒ n」+1个关键字进行比较。 二叉排序树查找 二叉排序树( 二叉排序树(Binary Sorting Tree),它或者是一棵空树, ) 它或者是一棵空树, 或者是一棵具有如下特征的非空二叉树: 或者是一棵具有如下特征的非空二叉树: (1)若它的左子树非空, 则左子树上所有结点的关键字均小于 若它的左子树非空, 若它的左子树非空 根结点的关键字; 根结点的关键字; (2)若它的右子树非空, 则右子树上所有结点的关键字均大于 若它的右子树非空, 若它的右子树非空 等于根结点的关键字; 等于根结点的关键字; (3)左、右子树本身又都是一棵二叉排序树。 左 右子树本身又都是一棵二叉排序树。 二叉排序 树的查找思想 若二叉排树为空, 失败,否则, 若二叉排树为空,则查找 失败,否则,先拿根结点值与待查 值进行比较,若相等,则查找成功,若根结点值大于待查值, 值进行比较,若相等,则查找成功,若根结点值大于待查值, 则进入左子树重复此步骤,否则,进入右子树重复此步骤, 则进入左子树重复此步骤,否则,进入右子树重复此步骤, 若在查找过程中遇到二叉排序树的叶子结点时, 若在查找过程中遇到二叉排序树的叶子结点时,还没有找到 待找结点,则查找不成功。 待找结点,则查找不成功。

点击这里复制本文地址 免责声明:本站内容由程序自动采集于互联网,无人工干预,只作交流和学习使用,本站不储存任何资源内容,如有侵权请联系qq邮箱798244092@qq.com立刻删除,谢谢!

支持Ctrl+Enter提交

测评网 © All Rights Reserved.  
Powered by 多多资源网 Themes by 多多资源网
联系我们| 关于我们| 留言建议| 网站管理