数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第九章 查找
53页1、第九章 查找,数据结构,第九章 查找,第八章 查找,知 识 点 查找的基本概念 三种基本查找方法:顺序查找、二分查找和分块查找 哈希表查找,要 求 熟练掌握以下内容: 三种基本查找方法的基本思想和算法 散列法基本思想、散列函数的常用构造方法及解决冲突方法,第八章目录,9.1 查找的基本概念 9.2 基本查找方法 9.3 哈希表查找 9.4 应用举例及分析 小 结 习题与练习,9.1 查找的基本概念,查找又称为查询或检索,是在一批记录中依照某个域的指定域值,找出相应的记录的操作。 在计算机中,被查找的数据对象是由同一类型的记录构成的集合,可称之为查找表(search table)。 在实际应用问题中,每个记录一般包含有多个数据域,查找是根据其中某一个指定的域进行的,这个作为查找依据的域称为关键字(key)。,对于给定的关键字的值,如果在表中经过查找能找到相应的记录,则称查找成功,一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录,则称查找不成功,此时应该给出不成功的信息。 查找算法中的基本运算是记录的关键字与给定值所进行的比较,其执行时间通常取决于比较的次数。
2、因此,通常以关键字与给定值进行比较的记录个数的平均值,作为衡量查找算法好坏的依据。,返回,9.2.1 顺序查找,顺序查找(Sequential search)也称为线性查找,是采用线性表作为数据的存储结构,对数据在表中存放的先后次序没有任何要求。 顺序查找是最简单的查找方法,它的基本思想是:查找从线性表的一端开始,顺序将各单元的关键字与给定值k进行比较,直至找到与k相等的关键字,则查找成功,返回该单元的位置序号;如果进行到表的另一端,仍未找到与k相等的关键字,则查找不成功,返回0作为查找失败的信息。,顺序查找的线性表定义如下: #define MAXITEM 100 /*最多项数*/ struct element keytype key; Elemtype data; ; typedef struct sqlistMAXITEM; 这里keytype和ElemType可以是任何相应的数据类型,如int、float或char等,在算法中我们规定它们缺省是int类型。,顺序查找算法,int sequsearch (sqlist r, int k, n) /*n为线性表r中元素个数*/ i=
3、1 while (ri.key!=k ,顺序查找算法分析,此函数的主要运算时间是用于循环语句逐单元进行比较判断ri.key是否等于k,因此顺序查找的速度较慢,最坏的情况查找成功需比较n次,最好的情况是比较1次,如果对每个关键字进行查找的概率相等,则查找成功所需的平均比较次数为(n+1)/2,而查找失败则需比较(n+1)次,时间复杂度为O(n)。 顺序查找的优点是算法简单、适应面广,且不要求表中数据有序。缺点是平均查找长度较大,特别是当n较大时,查找效率较低,不宜采用。,9.2.2 二分查找,二分查找(Birary search)也称为折半查找,它的查找速度比顺序查找快,但它要求数据在线性表中按查找的关键字域有序排列。 设n个数据存放于数组r中,且已经过排序,按由小到大递增的顺序排列。 采用二分查找,首先用要查找的给定值k与表正中间元素的关键值相比较,此元素的下标 。,比较结果有三种可能: 如果rm.keyk,说明如果存在欲查找的元素,该元素一定在数组的前半部分,查找范围缩小了一半,修改查找范围的的上界high=m-1,继续对数组的前半部分进行二分查找; 如果rm.keyk,说明如果存在
4、欲查找的元素,该元素一定在数组的后半部分,查找范围缩小了一半,修改查找范围的的下界low=m+1,继续对数组的后半部分进行二分查找; 如果rm.key=k,查找成功,m所指的记录就是查找到的数据。,重复上述过程,查找范围每次缩小1/2,当范围不断缩小,出现查找范围的下界大于上界时,则查找失败,确定关键字为key的记录不存在。 二分查找是一种效率较高的算法,最好的情况是第一次比较即找到所查元素,即使一次比较没有找到,也把进一步查找的范围了缩小一半。与此类似,每比较一次均使查找范围减半,故最坏的情况所需比较次数为O(logn),对于较大的n显然较顺序查找速度快得多。,二分查找算法,int binsearch(sqlist r,int k,n) int i,low=1,high=n,m,find=0; /*low和high分别表示查找范围的起始单元下标和终止单元下标,find为查找成功的标志变量*/ while (lowrm.key),二分查找算法续,low=m+1; else i=m; find=1; if (!find) i=0; return(i); ,9.2.3 分块查找,分块查找又
《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第九章 查找》由会员E****分享,可在线阅读,更多相关《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第九章 查找》请在金锄头文库上搜索。
逍遥游复习 知识点整理
近现代法德关系史 高三展示课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页