《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第8章 检索
80页1、8.1 检索的基本概念 8.2 线性表的检索 8.3 树表的检索 8.4 B树 8.5 散列检索技术,第8章 检索,8.1 检索的基本概念 1、检索定义 (1)关键字 关键字(Key)是数据元素(或记录)中某个数据项的值,用它可以标识(或识别)一个数据元素(或记录)。在一个记录中,每个数据项都可作为该记录的关键字。 主关键字是指在一个记录众多的关键字中能唯一地标识一个数据元素(或记录)的关键字,其它的关键字称为从关键字,也叫辅助关键字。 (2)检索表 检索表是由同一类型的数据元素(或记录)组成的集合,是检索操作所依赖的数据结构。 (3)检索定义 检索,又叫查找,是根据给定的某个值,在一个检索表中确定一个其关键字等于给定值的记录或数据元素的操作运算。若检索表中存在这样的一条记录,则称检索是成功;若表中不存在这样的记录,则称检索是不成功的,是失败的,此时检索的结果在静态环境下可给出不存在此记录的提示信息;在动态环境下,可插入此关键字等于给定值的记录。,2、检索方法 依据数据的存储方式的不同,我们将检索分为线性表检索、树表检索和散列表检索等。 3、平均检索长度 将“为检索到具有给定关键字值的
2、数据元素或记录所需要关键字的比较次数的平均值”作为衡量检索算法好坏的依据,即通过平均检索长度来衡量。具体地说,即指为确定欲检索的记录在表中的位置,需与给定值进行比较的关键字个数的期望值,称为检索算法在检索成功时的平均检索长度(Average Search Length)。,其中,pi为检索第i个记录的概率,且 。若不特别说明,均认为每个记录的检索概率相等(即为等概率情形),从而有p1 =p2=pn=1/n,ci为检索到第i个记录需要和给定关键值比较的关键字个数。一般情形下,ci依赖于所采用的检索方法。,线性表的检索按照检索方法的不同可分为顺序检索、折半检索和分块检索。 8.2.1 顺序检索 1、基本思想 基本思想是:从表的第n个记录开始,用给定的值与表中各个记录的关键字逐个地进行比较,如果检索到某一个记录的关键字与给定值相等,则检索成功;若整个表中的记录均比较过,仍未检索到关键字等于给定值的记录,则检索失败。,8.2 线性表的检索,2、类型定义与算法实现 typedef struct keytype key ; /*关键字类型 */ elemtype other ; /*其他的域 */
3、 sqlist ; sqlist Rn+1 ; /* 顺序表 */ 顺序检索算法: int seqsrch (sqlist R , keytype k) int i ; R0.key = k ; /* 将R0作为监视哨 */ i = n ; /* 从第n个记录起向前扫描 */ while (Ri.key! =k) i- ; if (i= =0) return(0) ; else return i ; /*seqsrch */,3、顺序检索性能分析 在等概率情况下,顺序检索的平均检索长度为:,顺序检索成功时的平均比较次数约等于表长的一半。若所检索的给定值k不在表中,则需进行n+1次比较才可确定检索失败。其算法简单,且适用面广,对表的存储结构、记录是否按关键字有序等方面不作要求。,8.2.2 折半检索 1、基本思想 折半检索又称二分检索,其基本思想是:先将待检索的给定值和检索表的中间位置上的记录的关键字值进行比较,若相等,则检索成功,否则,若给定值比该中间位置上记录的关键字值大,则只要在右半部分中继续进行折半检索,否则,只要在左半部分中继续进行折半检索。这样,经过一次关键字比较就缩小一半的
4、检索区间,如此进行下去,直到检索到关键字值为给定值的记录,或者未检索到,即检索失败。需注意的是,作为折半检索对象的表必须是顺序存储方式的有序表。,2、折半检索过程示例 已知一个含11个记录的有序表,其关键字序列为 ( 08,10,12,19,25,31,39,42,47,52,57 ) (1)检索k=12:,此时mid = 5,由于k = 12 Rmid-1.key,只要在其左子表R0R4中继续检索中继续进行折半检索。,此时mid = 2,由于 k =12 = Rmid.key,说明检索成功。,此时mid=5,由于k = 42 Rmid.key,所以只要在其右子表中继续进行折半检索,即在R6R10中继续检索。,此时mid = 8,由于k = 52 Rmid.key,可缩小检索区间,即缩小为R9R10。此时mid = 9 , 且有 k = 52 = Rmid.key,则检索成功。,(2)检索k=52的记录过程:,此时,k = 87 Rmid.key,则下一步为:,此时,k87Rmid.key,则下一步为:,此时,mid =9,k Rmid.key ,则又缩小区间为R10R10,此时mid
《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第8章 检索》由会员E****分享,可在线阅读,更多相关《《数据结构——用C语言描述(第二版)》-宁正元-电子教案 第8章 检索》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课3稿
当代大学生人生信仰及追求的调查研究
长相思 纳兰性德-ppt课件
课件:危机意识 一
英语ppt演讲关于阿甘正传
发达国家基础教育改革的动向与趋势 修改版
中国民间美术 课件.ppt
生物质发电技术与系统 课程ppt 第1章 生物质发电技术现状及发展趋势 2学时 -----2016
现代信号处理思考题 含答案
执业药师继续教育 抑郁症的药物治疗 100分
小学生的成长档案模板不用修改 万能型
增订六版 现代汉语 上册 第二章文字 思考与练习答案
国家财政ppt课件
加拿大英语介绍
六年级统计图的选择课件
中学生成长档案ppt
中国现代文学史期末复习整理
lohi和hihilo训练对女子赛艇运动员运动能力影响的比较研究
风雨贾平凹阅读答案
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页
2024-04-11 34页
2024-04-11 32页