(三)分块查找 分块查找( Blocking Search)又称索引顺序查找。它 是一种性能介于顺序查找和二分查找之间的查找方法。 分块查找表存储结构 分块查找表由“分块有序”的线性表和索引表组成 (1)“分块有序”的线性表 表Rn均分为b块,前b-1块中结点个数为s=m/b, 第b块的结点数小于等于s;每一块中的关键字不一定有 序,但前一块中的最大关键字必须小于后一块中的最小 关键字,即表是分块有序"的。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 （三） 分块查找 分块查找(Blocking Search)又称索引顺序查找。它 是一种性能介于顺序查找和二分查找之间的查找方法。 1、 分块查找表存储结构 分块查找表由“分块有序”的线性表和索引表组成。 （1）“分块有序”的线性表 表R[1..n]均分为b块，前b-1块中结点个数为 s=[n/b], 第b块的结点数小于等于s；每一块中的关键字不一定有 序，但前一块中的最大关键字必须小于后一块中的最小 关键字，即表是"分块有序"的
(2)索引表 抽取各块中的最大关键字及其起始位置构成 个索引表ID[1.b],即:ID[i](1≤i≤b)中存 放第i块的最大关键字及该块在表R中的起始位 置。由于表R是分块有序的,所以索引表是一个 递增有序表。 例】对于关键字序列为 9,22,12,14,35,42,44,38,48,60,58,4778,80,77,82 的线性表建分块索引表上例中共有16个元素,可 以将其分为四块,其块表与索引表为: 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 抽取各块中的最大关键字及其起始位置构成一 个索引表ID[l..b]，即：ID[i] (1≤i≤b)中存 放第 i块的最大关键字及该块在表R中的起始位 置。由于表R是分块有序的，所以索引表是一个 递增有序表。 【例】 对于关键字序列为： ｛9,22,12,14,35,42,44,38,48,60,58,4778,80,77,82｝ 的线性表建分块索引表上例中共有16个元素,可 以将其分为四块，其块表与索引表为： （2）索引表
块表 234567891011123141516 9222148354244384860847781807782 索引表 data low high 22m4 4458 6009-12 821316 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 块表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 9 22 12 14 35 42 44 38 48 60 58 47 78 80 77 82 索引表 data low high 22 1 4 44 5 8 60 9 12 82 13 16
2、分块查找的基本思想 分块査找的基本思想是 (1)首先查找索引表 索引表是有序表,可采用二分查找或顺 序查找,以确定待査的结点在哪一块 (2)然后在已确定的块中进行顺序査找 由于块内元素无序,只能采用顺序查找 的方法实现块内查找 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 分块查找的基本思想是： （1）首先查找索引表 索引表是有序表，可采用二分查找或顺 序查找，以确定待查的结点在哪一块。 （2）然后在已确定的块中进行顺序查找 由于块内元素无序，只能采用顺序查找 的方法实现块内查找。 2、分块查找的基本思想
3、分块查找示例 【例】对于上例的存储结构: (1)查找关键字等于给定值K=35的结点 因为索引表比较小,不妨用顺序查找方法 查找索引表。即首先将K依次和索引表中各关 键字比较,直到找到第1个关键宇大小等于K的 结点,由于K<44,所以关键字为35的结点若存 在的话,则必定在第二块中;然后,由 I|2|addr找到第二块的起始地址5,从该地址 开始在R5.8中进行顺序查找, 直到R5key=K为止。此时查找成功 汉理工 系
武汉理工大学华夏学院-信息工程 系 3、分块查找示例 【例】对于上例的存储结构： （1）查找关键字等于给定值K=35的结点 因为索引表比较小，不妨用顺序查找方法 查找索引表。即首先将K依次和索引表中各关 键字比较，直到找到第1个关键宇大小等于K的 结点，由于K<44，所以关键字为35的结点若存 在的话，则必定在第二块中；然后，由 ID[2].addr找到第二块的起始地址5，从该地址 开始在R[5..8]中进行顺序查找， 直到 R[5].key=K为止。此时查找成功