文档介绍：第8章查找
1、查找表——也叫检索,是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在完全松散的关系,因此查找表是一种非常灵便的数据结构。
2、查找表的操作
查找某个“特定”的数据元素是否在查找表中;
检索某个“特定”的数据元素的各种属性;
在查找表中插入一个数据元素;
从查找表中删除某个数据元素。
3、静态查找表、动态查找表
若对查找表只作前两种统称为“查找”的操作,则此类查找为静态查找表。
若在查找过程中同时插入查找表中不存在的数据元素,或从查找表中删除已存在的某个数据元素,则称此类表为动态查找表。
4、关键字、次关键字
关键字:是数据元素(或记录)中某个数据项的值,用它可以标识(识别)一个数据元素(或记录)。若此关键字可以唯一地标识一个记录,则称此关键字为主关键字。反之,则称此关键字为次关键字。
第8章查找
5、查找
根据给定的某个值,在查找表中确定一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录,则称查找是成功的,此时查找的结果为给出整个记录的信息,或指示该记录在查找表中的位置;
6、查找方法评价
查找速度、占用存储空间多少、算法本身复杂程度
平均查找长度ASL(Average Search Length):为确定记录在表中的位置,需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度。
若表中不存在关键字等于给定值的记录,则称查找不成功。此时查找的结果可给出一个“空”记录或“空”指针。
第8章查找
i
例
0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找64
64
监视哨
i
i
i
i
比较次数=5
比较次数:
查找第n个元素:1
查找第n-1个元素:2
静态查找表
一、顺序表的查找(顺序查找)
1、顺序查找从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功,找到所查找记录;反之,若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录,查找不成功。
查找第1个元素:n
查找第i个元素:n+1-i
查找失败: n+1
2、查找操作的性能分析
对于含有n个记录的表,查找成功时的平均查找长度为:
其中: n 为表长,Pi 为查找表中第i个记录的概率,且, Ci为找到该记录时,曾和给定值比较过的关键字的个数。
从顺序查找的过程可见, Ci取决于所查找记录在表中的位置。查找表中最后一个记录是,仅需比较一次,而查找表中第一个记录时,则需比较n次。一般情况下Ci等于n-i+1。
ASL = nP1 +(n-1)P2 + +2Pn-1+Pn
从上式可知,在不等概率查找的情况下,ASLss 在 Pn≥Pn-1≥···≥P2≥P1时取极小值。
应对记录的查找概率进行排序,使表中记录按查找概率由小到大重新排列,以便提高查找效率。
查找概率无法事先测定,则查找过程采取的改进办法是,在每次查找之后,将刚刚查找到的记录直接移至表尾的位置上。
顺序查找的缺点是平均查找长度较大,特别是当n很大时,查找效率低。然而,它有很大的优点是:算法简单且适应面广。
当查找不成功时的情形不忽视时,查找算法的平均查找长度应是查找成功时的平均查找长度与查找不成功时的平均查找长度之和。
对于顺序查找,不论给定值key为何值,查找不成功时和给定值进行比较的关键字个数均为n+1。假设查找成功与不成功的可能性相同,对每个记录的查找概率也相等,则,此时顺序查找的平均查找长度为:
一、顺序表的查找(顺序查找)
1、折半查找折半查找的查找过程是:先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。每次将待查记录所在区间缩小一半。
二、有序表的查找(折半查找)
算法实现:假设表长为n,low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值,初始时,令low=1,high=n,mid=(low+high)/2
让k与mid指向的记录比较
若k==r[mid].key,查找成功
若k<r[mid].key,则high=mid-1
若k>r[mid].key,则low=mid+1
重复上述操作,直至low>high时,查找失败。
low
high
mid
例
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找21
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low
high