数据结构与算法 王曙燕 chapter8 查找

《数据结构与算法 王曙燕 chapter8 查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1数据结构与算法8.1概述第8章查找8.2基于线性表的查找法8.3基于树的查找法8.4散列8.5算法总结28.1概述第8章查找查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。数据结构与算法3第8章查找对查找表常进行的操作:1）查询某个“特定的”数据元素是否在查找表中静态查找动态查找3）在查找表中插入一个数据元素2）检索某个“特定的”数据元素的各种属性4）从查找表中删去某个数据元素数据结构与算法8.1概述4第8章查找查找表的分类仅作查询和

2、检索操作静态查找表“不在查找表中”的数据元素插入到查找表中；删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找还可分为：内查找和外查找。8.1概述5第8章查找关键字：是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。主关键字：可以识别唯一的一个记录的关键字。次关键字：可以识别若干记录的关键字。8.1概述6根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（记录）。查找若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的

3、位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。第8章查找8.1概述7由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说,用另外一种结构来表示查找表。如何进行查找？查找的方法取决于查找表的结构。第8章查找8.1概述88.2基于线性表的查找第8章查找①顺序查找②折半查找③分块查找9数据结构8.2基于线性表的查找第8章查找①顺序查找key=64key=6021378819920564568072130123456

4、789101112iiiiiiiiiii结果：查找成功，返回位置7结果：查找不成功intSeqSearch(RecordListl,KeyTypek){inti;i=l.length;while(i>=1&&l.r[i].key!=k)i--;if(i>=1)return(i);elsereturn(0);}108.2基于线性表的查找第8章查找①顺序查找key=64key=60结果：查找成功，返回位置7结果：查找不成功6460intSeqSearch(RecordListl,KeyTypek){inti;l.r[0

5、].key=k;/*标识边界*/i=l.length;while(l.r[i].key!=k)i--;return(i);}技巧：r[0]起到监视哨兵的作用,可免去检查表是否查完,且提高算法的执行效率,但并不是真正的待查找记录。21378819920564568072130123456789101112iiiiiiiiiiii118.2基于线性表的查找第8章查找①顺序查找分析查找的时间性能:查找算法的平均查找长度(AverageSearchLength)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期

6、望值(查找成功时）ASL=∑PiCii=1n其中:n为表长；Pi为查找表中第i个记录的概率，且;Ci为找到该记录时，曾和给定值比较过的关键字的次数。∑Pi=1i=1n12在等概率查找的情况下，顺序表查找成功的平均查找长度为：Pi=1/n对顺序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn8.2基于线性表的查找第8章查找21111+=+-=å=n)i(nnASLniSUCC若查找概率无法事先测定，则查找过程采取的改进办法是，附设一个访问频度域或者在每次查找之后，将刚刚查找到的记录直接移至表

7、尾的位置上。①顺序查找138.2基于线性表的查找第8章查找数据结构②折半查找顺序查找的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。若以有序表表示查找表，则查找过程可以基于“折半”进行。148.2基于线性表的查找第8章查找②折半查找1.首先确定查找表的中间位置；2.然后将待查的值与中间位置的值进行比较，若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。基本思想:158.2基于线性表的查找第8章查找②折半查找例1:key=64的查找过程如下：lowmidhighlowmidmid

8、high①low=11211109876543219288807564563721191305low指示查找区间的下界high=11mid=(1+11)/2=6②key>mid指向的记录值low=mid+1=7mid=(7+11)/2=9③key