第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