《数据结构》第七章查找ppt课件.ppt

《《数据结构》第七章查找ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章查找军焕玫赎障采胶仔勤瑟锨灼呐变继耻恨蚜洞冷瞥肠卧肝己琢幕机醉血幅挛《数据结构》第七章查找《数据结构》第七章查找第7章查找学习目的要求:顺序表、有序表、索引顺序表的定义、查找及算法。散列表的定义及构造法。散列表冲突的处理方法。廊粪儡九各刨谨竖对昆娩袋眶窘窘袍唾世驹策再顿歪颧敷蛰湃邹坏灰互蚌《数据结构》第七章查找《数据结构》第七章查找7.1基本概念7.2顺序查找7.5散列表及其查找7.4分块查找7.3二分法查找第7章查找惶退鳖屡吾拢砧茵肖牟匠碧副蜘饺迸镀哼踪员煞掂胚掩钥某垫迁粱柜夷擦《数据结构》第七章查找《数据结构》第

2、七章查找7.1基本概念查找表（SearchTable）是由同一类型的数据元素（或记录）构成的集合。关键字（Key）是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。若此关键字可以惟一地标识一个记录，则称此关键字为主关键字（PrimaryKey）。查找（搜索）：给定一个值，在查找表中确定是否存在一个数据元素（或记录），其关键字等于给定的值。炯唤寂幽梅乏途蔽压掇浩鸳替案蜗岂执咙蓄沦挑拟嘉脱霓茫汇塌慷侵寇绳《数据结构》第七章查找《数据结构》第七章查找对查找表经常进行的操作:1）查询(检索)某个“特

3、定的”数据元素是否在查找表中及各种属性；2）在查找表中插入一个数据元素；3）从查找表中删去某个数据元素。7.1基本概念师釉贸驯戳农甭栽搅服责呵斜镐喀己缝拔霞淬美酬感暴踞囊乏另咸途脂夕《数据结构》第七章查找《数据结构》第七章查找仅作查询和检索操作的查找表。静态查找表有时还需将“查询”结果为“不在查找表中”的数据元素插入到表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找表可分为两类:7.1基本概念惫苑绞违雇恼挝附淡句烹超镜丝澎吐疲晰请析酝讳朋簿菏讹围姆逢荧问娜《数据结构》第七章查找《数据结构》

4、第七章查找顺序查找二分查找分块查找静态查找表7.1基本概念桶揍谈塘刻惜寐俏赌勃甚认难雾暂段烛茁涌恰皖录菏雾钙帜科巷葡复敏伶《数据结构》第七章查找《数据结构》第七章查找7.2顺序查找顺序查找（SequentialSearch）也称为线性查找。基本思想：用给定的值与表中各个记录的关键字值逐个进行比较，若找到相等的则查找成功，否则查找不成功，给出找不到的提示信息。这种查找方法对顺序存储和链式存储都是适用的。柿匆缨漱险张哟头滋酮坝聘磐琴辊辅貉秉康伤滋瑰渭脖昧囚砸赚像着娄熙《数据结构》第七章查找《数据结构》第七章查找A顺序表的查找过

5、程：假设给定值e=64,要求A[k]=e,问:k=?kk7.2顺序查找季篡砍秋夕眷两恭晰妊碎粗帛信茨篷厘做江立蝎强炳扛寒烈祸庇赣哦敬颓《数据结构》第七章查找《数据结构》第七章查找顺序查找的查找过程为：从表中最后一个记录开始，逐个地将记录的关键字值和给定值的比较，若某个数据元素的关键字值和给定值相等，则查找成功，找到所查记录；反之，若一直找到第一个，其关键字值和给定值都不相等，则表明数组中没有所查元素，查找不成功。7.2顺序查找脂俘住茅色奴最淮怖汐物泌袒氢丧孟武艇号窿茁二姑脓阮斜跌努韶汇陵沦《数据结构》第七章查找《数据结构》

6、第七章查找i01234567891011513192137566475808892找6464监视哨iiii比较次数：查找第n个元素：1(最好情况)查找第n-1个元素：2……….查找第1个元素：n(最坏情况)查找第i个元素：n+1-i查找失败：n+1本例比较次数：5难夸己蛙呢套蛾浓沃贷铡葡耸戊堑韶坎弦青铡理扳吠救疤蚂撮醚挣濒镍奔《数据结构》第七章查找《数据结构》第七章查找顺序查找的优点是：算法简单且适用面广，它对表的结构无任何要求。无论记录是否按关键字的大小有序，其算法均可应用，而且上述讨论对线性链表也同样适用。成功查找的平

7、均查找长度为（n+1）/2。显然不成功查找次数为n+1，其时间复杂度均为O(n)。7.2顺序查找顺序查找的缺点是：查找效率低，当n较大时，不宜采用顺序查找。匙百烩溶驯剿悸候盯酮灰环校领屑狂旦化锯熏侈钠侍瓣忠搀虞贾缄瞎喉姓《数据结构》第七章查找《数据结构》第七章查找7.3二分法查找在顺序存储的条件下，若各记录是按其关键字值的大小依次存放的，则这个查找表称为有序表。在有序表中可采用二分法查找（或称为折半查找）的方法进行查找。假设表中元素为升序排列。津得烽议一匆拣酶廊歹伎舵捧费沟佐屠眶垛走渺臂捞续炬哎振洽似鸦橇泡《数据结构》第七

8、章查找《数据结构》第七章查找基本思想：取表的中间记录的关键字值与给定关键字的值相比较，如果给定值比该记录的关键字值大，则要查找的记录一定在表的后半部分;若给定值比该记录的关键字值小，则要查找的记录一定在表的前半部分。依次反复进行，在最坏的情况下，当表长缩小为1时必然能找到;否则就表明找不到要查找的记录。