高中信息技术 信息学奥赛_PASCAL语言查找课件_第1页
高中信息技术 信息学奥赛_PASCAL语言查找课件_第2页
高中信息技术 信息学奥赛_PASCAL语言查找课件_第3页
高中信息技术 信息学奥赛_PASCAL语言查找课件_第4页
高中信息技术 信息学奥赛_PASCAL语言查找课件_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、基本算法：查找 查找定义：给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的提示信息。 分为：顺序查找、二分查找顺序查找 是一种最简单的查找方法 基本思想：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较，若相等则查找成功；若扫描结束后，仍未找到则查找失败。顺序查找 顺序查找的算法：顺序查找的算法： VAR K:ktype; R:array 1.n of ktype; t = false; for i:=1 to n do if Ri=k then begin t:=true

2、; break; end; if t then writeln( i ) else writeln(No answer!);顺序查找 算法分析：算法分析： 平均查找长度平均查找长度ASL ASL = (n+2+1)/n = (n+1)/2 成功成功 ASL = n 不成功不成功 优点：适合线性表、链式表优点：适合线性表、链式表 缺点：效率低，当缺点：效率低，当n较大时，不宜采用顺序查找较大时，不宜采用顺序查找二分查找（折半查找） 是一种效率较高的查找方法 要求：线性表是有序表 基本思想：（设Rlow.high当前查找区间）确定中间位置mid=(low+high)/2将Rmid与给定值K比较，若

3、相等，则查找成功返回此位置；否则须确定新的查找区间，继续用二分查找。若RmidK，则新的查找区间是左子表R1.mid-1若RmidK，则新的查找区间是右子表Rmid+1.n二分查找算法： Procedure binsearch ( VAR R:array1.n of ktype; K:ktype ); VAR low,high,mid :integer; BEGIN low:=1; high:=n; while lowK then high:=mid-1 else low:=mid+1; end; writeln(No answer!); END;二分查找 算法分析 优点：效率高 缺点： 只适合线性表，链表上无法实现二分查找 有序表练习 1、对18个元素的有序表作二分查找，则查找A3的比较序列的下标为（ ） A、1-2-3 B、9-5-2-3 C、9-5-3 D、9-4-2-32、在顺序表（2，5，7，10，14，15，18，23，35，41，52）中，用二分查找12，所需的关键字比较的次数为（ ） A、2 B、3 C、4 D、5DC练习 3、利用逐点插入法建立序列50，72，43，85，75，20，35，45

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论