基本算法查找-完整版PPT_第1页
基本算法查找-完整版PPT_第2页
基本算法查找-完整版PPT_第3页
基本算法查找-完整版PPT_第4页
基本算法查找-完整版PPT_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

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

文档简介

1、查找定义：给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的提示信息。分为：顺序查找、二分查找基本算法-查找2022/9/12是一种最简单的查找方法基本思想：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较，若相等则查找成功；若扫描结束后，仍未找到则查找失败。顺序查找2022/9/12顺序查找的算法：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!);顺序查找2022/9/12算法分析：平均查找长度ASL ASL = (n+2+1)/n = (n+1)/2 成功 ASL = n 不成功优点：适合线性表、链式表缺点：效率低，当n较大时，不宜采用顺序查找顺序查找2022/9/12是一种效率较高的查找方法要求：线性表是有序表基本思想：（设Rlow.high当前查找区间）确定中间位置mid=(low+high)/2将Rmid与给定值K比较，若相等，则查找成功返回此位置；否则须确定新的查找区间，继续用二分查找。若RmidK，则新的

3、查找区间是左子表R1.mid-1若RmidK，则新的查找区间是右子表Rmid+1.n二分查找（折半查找）2022/9/12Procedure 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;二分查找算法：2022/9/12算法分析优点：效率高缺点：只适合线性表，链表上无法实现二分查找有序表二分查找2022/9/121、对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、5练习2022/9/12DC3、利用逐点插入法建立序列50，72，43，85，75，20，35，45，65，30对应的二叉

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

温馨提示

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

最新文档

评论

0/150

提交评论