北京邮电大学自动化学院：《数据结构》第八章 查找

第8章查找 1、查找表——也叫检索,是由同一类型的数据元素(或记 录)构成的集合。由于“集合”中的数据元素之间存在完全 松散的关系,因此查找表是一种非常灵便的数据结构。 2、查找表的操作 查找某个“特定”的数据元素是否在查找表中; ●检索某个“特定”的数据元素的各种属性; 在查找表中插入一个数据元素; 从査找表中删除某个数据元素。 北京邮电大学自动化学院

北京邮电大学自动化学院 1 第8章 查找 ⚫ 1、查找表——也叫检索，是由同一类型的数据元素（或记 录）构成的集合。由于“集合”中的数据元素之间存在完全 松散的关系，因此查找表是一种非常灵便的数据结构。 ⚫ 2、查找表的操作 ⚫ 查找某个“特定”的数据元素是否在查找表中； ⚫ 检索某个“特定”的数据元素的各种属性； ⚫ 在查找表中插入一个数据元素； ⚫ 从查找表中删除某个数据元素

第8章查找 ●3、静态査找表、动态査找表 ●若对查找表只作前两种统称为“査找”的操作,则此 类查找为静态查找表 若在查找过程中同时插入查找表中不存在的数据元素, 或从查找表中删除已存在的某个数据元素,则称此类表 为动态查找表。 4、关键字、次关键字 ●关键字:是数据元素(或记录)中某个数据项的值,用 它可以标识(识别)一个数据元素(或记录)。若此关 键字可以唯一地标识一个记录,则称此关键字为主关键 字。反之,则称此关键字为次关键字。 北京邮电大学自动化学院

北京邮电大学自动化学院 2 ⚫ 3、静态查找表、动态查找表 ⚫ 若对查找表只作前两种统称为“查找”的操作，则此 类查找为静态查找表。 ⚫ 若在查找过程中同时插入查找表中不存在的数据元素， 或从查找表中删除已存在的某个数据元素，则称此类表 为动态查找表。 ⚫ 4、关键字、次关键字 ⚫ 关键字：是数据元素（或记录）中某个数据项的值，用 它可以标识（识别）一个数据元素（或记录）。若此关 键字可以唯一地标识一个记录，则称此关键字为主关键 字。反之，则称此关键字为次关键字。 第8章 查找

第8章查找 5、查找 根据给定的某个值,在査找表中确定一个其关键字等于给定 值的记录或数据元素。若表中存在这样的一个记录,则称查 找是成功的,此时查找的结果为给出整个记录的信息,或指 示该记录在查找表中的位置; 若表中不存在关键字等于给定值的记录,则称查找不成功 此时查找的结果可给出一个“空”记录或“空”指针。 6、查找方法评价 查找速度、占用存储空间多少、算法本身复杂程度 平均查找长度ASL( Average Search Length):为确定记录 在表中的位置,需和给定值进行比较的关键字的个数的期望 值叫查找算法的平均查找长度。 北京邮电大学自动化学院

北京邮电大学自动化学院 3 ⚫ 5、查找 ⚫ 根据给定的某个值，在查找表中确定一个其关键字等于给定 值的记录或数据元素。若表中存在这样的一个记录，则称查 找是成功的，此时查找的结果为给出整个记录的信息，或指 示该记录在查找表中的位置； ⚫ 6、查找方法评价 ⚫ 查找速度、占用存储空间多少、算法本身复杂程度 ⚫ 平均查找长度ASL(Average Search Length)：为确定记录 在表中的位置，需和给定值进行比较的关键字的个数的期望 值叫查找算法的平均查找长度。 ⚫ 若表中不存在关键字等于给定值的记录，则称查找不成功。 此时查找的结果可给出一个“空”记录或“空”指针。 第8章 查找

81静态查找表 ChT l.trt 、顺序表的查找(顺序查找) 、顺序査找从表中最后一个记录开始,逐个进行记录的关键 字和给定值的比较,若某个记录的关键字和给定值比较相等, 则查找成功,找到所查找记录;反之,若直至第一个记录,其 关键字和给定值比较都不等,则表明表中没有所查记录,查找 不成功。 找64比较次数5 例 0123456 7 64513192137566475808892 蓝监视哨 比较次数 ●查找第1个元素:n ●查找第n个元素: 查找第个元素:n+1 ●查找第n-1个元素:2·查找失败: n+1 北京邮电大学自动化学院 4

北京邮电大学自动化学院 4 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 8.1 静态查找表 ⚫ 一、顺序表的查找（顺序查找） ⚫ 1、顺序查找 从表中最后一个记录开始，逐个进行记录的关键 字和给定值的比较，若某个记录的关键字和给定值比较相等， 则查找成功，找到所查找记录；反之，若直至第一个记录，其 关键字和给定值比较都不等，则表明表中没有所查记录，查找 不成功。 ⚫ 查找第1个元素：n ⚫ 查找第i个元素：n+1-i ⚫ 查找失败： n+1

2、查找操作的性能分析 ●对于含有n个记录的表,查找成功时的平均查找长度为: ASL=>P 其中:n为表长,P为查找表中第i个记录的概率, 且∑P=1,C为找到该记录时,曾和给定值比较过的关 键字的个数。 从顺序查找的过程可见,c取决于所查找记录在表中的位 置。查找表中最后一个记录是,仅需比较一次,而查找表中 第一个记录时,则需比较n次。一般情况下c等于n-i+1。 北京邮电大学自动化学院

北京邮电大学自动化学院 5 2、查找操作的性能分析 ⚫ 对于含有n个记录的表，查找成功时的平均查找长度为： ⚫ 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 ， Ci为找到该记录时，曾和给定值比较过的关 键字的个数。 1 1  = = n i Pi = = n i ASL pi ci 1 ⚫ 从顺序查找的过程可见， Ci取决于所查找记录在表中的位 置。查找表中最后一个记录是，仅需比较一次，而查找表中 第一个记录时，则需比较n次。一般情况下Ci等于n-i+1

ASLnP, +(n-1)P2++2Pn-+P 设表中每个元素的查找概率相等Pn 则A=∑n=1=1.m+=+1 从上式可知,在不等概率査找的情况下, ASLSS在 Pn≥Pn位…≥P2≥P1时取极小值。 应对记录的查找概率进行排序,使表中记录按查找概率由 小到大重新排列,以便提高查找效率。 查找概率无法事先测定,则查找过程采取的改进办法是 在每次查找之后,将刚刚查找到的记录直接移至表尾的位 置上。 北京邮电大学自动化学院

北京邮电大学自动化学院 6 ASL = nP1 +(n-1)P2 + +2Pn-1+Pn 2 1 2 1 1 ( 1) 1 1 1 + = + = = =  =   = = n n n n i n ASL p c n p n i n i i i i 则 设表中每个元素的查找概率相等 ⚫ 从上式可知，在不等概率查找的情况下，ASLss 在 Pn≥Pn-1≥···≥P2≥P1时取极小值。 ⚫ 应对记录的查找概率进行排序，使表中记录按查找概率由 小到大重新排列，以便提高查找效率。 ⚫ 查找概率无法事先测定，则查找过程采取的改进办法是， 在每次查找之后，将刚刚查找到的记录直接移至表尾的位 置上

、顺序表的查找(顺序查找) 顺序查找的缺点是平均查找长度较大,特别是当n很大 时,查找效率低。然而,它有很大的优点是:算法简单且 适应面广。 当査找不成功时的情形不忽视时,査找算法的平均查找长 度应是查找成功时的平均查找长度与查找不成功时的平均 查找长度之和。 对于顺序查找,不论给定值key为何值,查找不成功时和 给定值进行比较的关键字个数均为n+1。假设查找成功与 不成功的可能性相同,对每个记录的查找概率也相等, 则P ,此时顺序查找的平均查找长度为 2n AS ∑(m-i+1)+(n+1)=7(m+1) 4 北京邮电大学自动化学院

北京邮电大学自动化学院 7 ⚫ 顺序查找的缺点是平均查找长度较大，特别是当n很大 时，查找效率低。然而，它有很大的优点是：算法简单且 适应面广。 n Pi 2 1 = ( 1) 4 3 ( 1) 2 1 ( 1) 2 1 1 ' =  − + + + = + = n i n n n ASL n i S S ⚫ 当查找不成功时的情形不忽视时，查找算法的平均查找长 度应是查找成功时的平均查找长度与查找不成功时的平均 查找长度之和。 ⚫ 对于顺序查找，不论给定值key为何值，查找不成功时和 给定值进行比较的关键字个数均为n+1。假设查找成功与 不成功的可能性相同，对每个记录的查找概率也相等， 则 ，此时顺序查找的平均查找长度为： 一、顺序表的查找（顺序查找）

有序表的查找(折半查找) 、折半查我折半查找的查找过程是:先确定待查记录 所在的范围(区间),然后逐步缩小范围直到找到或找不到 该记录为止。每次将待查记录所在区间缩小一半。 ●算法实现:假设表长为n,loW、high和mid分别指向待查 元素所在区间的上界、下界和中点k为给定值,初始时,令 low=1, high=n, mid=L(low+high)/2] 让k与mid指向的记录比较 若k=rmid]key,查找成功 ·若krmid]key,则 lowEmid+1 重复上述操作,直至 owPhigh时,查找失败 北京邮电大学自动化学院

北京邮电大学自动化学院 8 ⚫ 1、折半查找 折半查找的查找过程是：先确定待查记录 所在的范围（区间），然后逐步缩小范围直到找到或找不到 该记录为止。每次将待查记录所在区间缩小一半。 二、有序表的查找（折半查找） ⚫ 算法实现：假设表长为n，low、high和mid分别指向待查 元素所在区间的上界、下界和中点,k为给定值，初始时，令 low=1,high=n,mid=(low+high)/2 ⚫ 让k与mid指向的记录比较 ⚫ 若k==r[mid].key，查找成功 ⚫ 若kr[mid].key，则low=mid+1 ⚫ 重复上述操作，直至low>high时，查找失败

1、折半查找 例如:已知如下11个数据元素的有序表(05,13,19, 21,37,56,64,75,80,88,92),现要查找关键 字为21和70的数据元素。 找21 1234567891011 例 51319213756647580889 low mI high 1234 67891011 513192137566475808892 d high 345678 0 1011 513192137566475808892 Ch7 2.c lowmid high Ch 2 txt 北京邮电大学自动化学院

北京邮电大学自动化学院 9 low mid high 例 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 mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 Ch7_2.c lowmid high 例如：已知如下11个数据元素的有序表（05，13，19， 21，37，56，64，75，80，88，92），现要查找关键 字为21和70 的数据元素。 1、折半查找

34567891011 例 找70 513192137566475808892 low mid high 12345678910 513192137566475808892 low mid 13191213756 7891011 6475808892 low mid high 1234 67891011 513192137566475808892 low high mid 2345678910 513192137566475808892 北京邮电大学白他胜dow 10

北京邮电大学自动化学院 10 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 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 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 high low