1 / 98
文档名称:

九章查找Search课件.ppt

格式:ppt   大小:1,924KB   页数:98页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

九章查找Search课件.ppt

上传人:aluyuw1 9/19/2022 文件大小:1.88 MB

下载得到文件列表

九章查找Search课件.ppt

相关文档

文档介绍

文档介绍:该【九章查找Search课件 】是由【aluyuw1】上传分享,文档一共【98】页,该文档可以免费在线阅读,需要了解更多关于【九章查找Search课件 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。第九章查找(Search)




——若表中存在特定元素,称查找成功;
——否则,称查找不成功(应输出失败标志或失败位置);
查找表
查找
查找成功
查找不成功
静态查找
动态查找
关键字
主关键字
次关键字
——由同一类型的数据元素(或记录)构成的集合。
——查询(Searching)特定元素是否在表中。
——只查找,不改变集合内的数据元素。
——既查找,又改变(增减)集合内的数据元素。
——记录中某个数据项的值,可用来识别一个记录
——可以唯一标识一个记录的关键字
例如“学号”
例如“女”
——识别若干记录的关键字

对查找表常用的操作有哪些?
查询某个“特定的”数据元素是否在表中;
查询某个“特定的”数据元素的各种属性;
在查找表中插入一元素;
从查找表中删除一元素。
查找的过程是怎样的?
给定一个值K,在含有n个记录的文件中进行搜索,寻找一个关键字值等于K的记录,如找到则输出该记录,否则输出查找不成功的信息。

如何评估查找方法的优劣?
查找的过程就是将给定的值与文件中各记录的关键字逐项进行比较的过程。所以用比较次数的平均值来评估算法的优劣,称为平均查找长度(ASL:averagesearchlength)。
其中:
n是文件记录个数;
Pi是查找第i个记录的查找概率;
Ci是找到第i个记录时所经历的比较次数。
显然,ASL值越小,时间效率越高。

一、顺序查找(线性查找)
二、折半查找(二分或对分查找)
三、分块查找(索引顺序查找)
(搜索)表
静态查找表可用顺序表或单链表存储,
本章只讨论顺序表。
所谓顺序查找,又称线性查找,主要用于在线性结构中进行查找。
设若表中有n个记录,则顺序查找从表的先端开始,顺序用各记录的关键码与给定值x进行比较,直到找到与其值相等的记录,则称查找成功,给出该记录在表中的位置。
若整个表都已检测完仍未找到关键码与x相等的记录,则查找失败,给出失败信息。
一、顺序查找(Linearsearch,又称线性查找)
2).算法的实现:
编程技巧:把待查关键字key存入表头或表尾(俗称“哨兵”),这样可以加快执行速度(避免每一次查找都检测整个表是否查找完毕)。
例:
若将待查找的特定值key存入顺序表的首部
(如0号单元),则顺序查找的算法思想为:
从后向前逐个比较!
一、顺序查找
intSearch_Seq(SSTableST,KeyTypekey){
//在顺序表ST中,查找关键字与key相同的元素;若成功,返回其位置信息,否则返回0。
[0].key=key;
for(i=;[i].key!=key;--i);
//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)
returni;
}//Search_Seq
同学们自己考虑对单链表如何线性查找?
2).算法的实现:
一、顺序查找
为确定记录在查找表中的位置,需给定值进行比较的关键字个数的期望值
其中:n为表长,Pi为查找表中第i个记录的概率,假设每次查找都是成功的,则有pi=1
Ci为找到该记录时,比较过的关键字的个数,
Ci=n-i+1,ASL=nP1+(n-1)P2+…+2Pn-1+Pn,如果要查找的元素在表中的任何位置的概率是相等的,p=1/n,ASL=(n+1)/2
3).顺序查找算法的平均查找长度(ASL)
一、顺序查找
如果有查找不成功的情况时,假设要查找的元素在表中的概率是p,查找不成功的概率为q=1-p
查找成功的平均查找长度为ASL=p(n+1)/2
查找不成功的平均查找长度为q(n+1)
平均查找长度为
3).顺序查找算法的平均查找长度(ASL)