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

文档介绍：该【《数据结构》第七章查找课件 】是由【yuzonghong1】上传分享，文档一共【60】页，该文档可以免费在线阅读，需要了解更多关于【《数据结构》第七章查找课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第7章查找
第7章查找
学****目的要求:
顺序表、有序表、索引顺序表的定义、查找及算法。
散列表的定义及构造法。
散列表冲突的处理方法。





第7章查找
对查找表经常进行的操作:
1)查询(检索)某个“特定的”数据元素是否在查找表中及各种属性;
2)在查找表中插入一个数据元素;
3)从查找表中删去某个数据元素。

仅作查询和检索操作的查找表。
静态查找表
有时还需将“查询”结果为“不在查找表中”的数据元素插入到表中;或者,从查找表中删除其“查询”结果为“在查找表中”的数据元素。
动态查找表
查找表可分为两类:

顺序查找
二分查找
分块查找
静态查找表

A
顺序表的查找过程:
假设给定值e=64,
要求A[k]=e,问:k=?
k
k

顺序查找的查找过程为:从表中最后一个记录开始,逐个地将记录的关键字值和给定值的比较,若某个数据元素的关键字值和给定值相等,则查找成功,找到所查记录;反之,若一直找到第一个,其关键字值和给定值都不相等,则表明数组中没有所查元素,查找不成功。

i
01234567891011
513192137566475808892
找64
64
监视哨
i
i
i
i
比较次数:
查找第n个元素:1 (最好情况)
查找第n-1个元素:2
……….
查找第1个元素:n (最坏情况)
查找第i个元素:n+1-i
查找失败:n+1
本例比较次数:5

在顺序存储的条件下,若各记录是按其关键字值的大小依次存放的,则这个查找表称为有序表。
在有序表中可采用二分法查找(或称为折半查找)的方法进行查找。
假设表中元素为升序排列。