《数据结构》第七章查找

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

1、第7章查找第7章查找学习目的要求:顺序表、有序表、索引顺序表的定义、查找及算法。散列表的定义及构造法。散列表冲突的处理方法。7.1基本概念7.2顺序查找7.5散列表及其查找7.4分块查找7.3二分法查找第7章查找7.1基本概念查找表（SearchTable）是由同一类型的数据元素（或记录）构成的集合。关键字（Key）是数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。若此关键字可以惟一地标识一个记录，则称此关键字为主关键字（PrimaryKey）。查找（搜索）：给定一个值，在查找表中

2、确定是否存在一个数据元素（或记录），其关键字等于给定的值。对查找表经常进行的操作:1）查询(检索)某个“特定的”数据元素是否在查找表中及各种属性；2）在查找表中插入一个数据元素；3）从查找表中删去某个数据元素。7.1基本概念仅作查询和检索操作的查找表。静态查找表有时还需将“查询”结果为“不在查找表中”的数据元素插入到表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。动态查找表查找表可分为两类:7.1基本概念顺序查找二分查找分块查找静态查找表7.1基本概念7.2顺序查找顺序查找（Sequentia

3、lSearch）也称为线性查找。基本思想：用给定的值与表中各个记录的关键字值逐个进行比较，若找到相等的则查找成功，否则查找不成功，给出找不到的提示信息。这种查找方法对顺序存储和链式存储都是适用的。A顺序表的查找过程：假设给定值e=64,要求A[k]=e,问:k=?kk7.2顺序查找顺序查找的查找过程为：从表中最后一个记录开始，逐个地将记录的关键字值和给定值的比较，若某个数据元素的关键字值和给定值相等，则查找成功，找到所查记录；反之，若一直找到第一个，其关键字值和给定值都不相等，则表明数组中没有所查元素，查找不成功

4、。7.2顺序查找i01234567891011513192137566475808892找6464监视哨iiii比较次数：查找第n个元素：1(最好情况)查找第n-1个元素：2……….查找第1个元素：n(最坏情况)查找第i个元素：n+1-i查找失败：n+1本例比较次数：5顺序查找的优点是：算法简单且适用面广，它对表的结构无任何要求。无论记录是否按关键字的大小有序，其算法均可应用，而且上述讨论对线性链表也同样适用。成功查找的平均查找长度为（n+1）/2。显然不成功查找次数为n+1，其时间复杂度均为O(n)。7.2顺序

5、查找顺序查找的缺点是：查找效率低，当n较大时，不宜采用顺序查找。7.3二分法查找在顺序存储的条件下，若各记录是按其关键字值的大小依次存放的，则这个查找表称为有序表。在有序表中可采用二分法查找（或称为折半查找）的方法进行查找。假设表中元素为升序排列。基本思想：取表的中间记录的关键字值与给定关键字的值相比较，如果给定值比该记录的关键字值大，则要查找的记录一定在表的后半部分;若给定值比该记录的关键字值小，则要查找的记录一定在表的前半部分。依次反复进行，在最坏的情况下，当表长缩小为1时必然能找到;否则就表明找不到要查找的

6、记录。7.3二分法查找midlowhigh1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid查找的数据在表中找到1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid123456789101

7、1513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid查找的数据不在表中1234567891011513192137566475808892lowhighlow>high查找失败从二分法查找的执行情况分析，每做一次比较，查找的范围都缩小一半。因此二分法查找的平均查找长度为ASL=log2(n+1)-1当n足够大时，可近似表示为log2n。优点：二分法查找比顺序查找的速度要快得多。当然，使用二分法查找必须是在顺序存储的

8、条件下，且事先必须做到按关键字值排序才行。7.3二分法查找练习1、若有一个由17个元素组成的有序表，利用二分法查找方法查找有序表的元素，问查找成功时，最少比较几次？最多比较几次？【答案】查找成功时，最少比较1次，最多比较5次。2、已知如下11个数据元素的有序表（6，14，19，21，36，57，63，76，81，89，93），请画出查找键值为21和85的查找过程。7.4分