解:(1)若查 二分查 找给定值为20的元 找判定 素,依次与表中 树 25,10,15,20元素比 较,共比较4次。 (2)若查找给定值为26的元素,依次与25,30,28元素比较, 共比较3次 (3)在查找成功时,会找到图中某个圆形节点,则成功 时的平均查找长度: 1x1+2×2+4×3+4×4 ASLSucc= 3 在查找不成功时会找到图中某个方形节点则不成功时 的平均查找长度 ASLunsucc≈4×3+8×4 =3.67 12
25 10 30 2 15 28 35 3 20 29 40 二分查 找判定 树 （2）若查找给定值为26的元素，依次与25,30,28元素比较， 共比较3次。 （3）在查找成功时，会找到图中某个圆形节点，则成功 时的平均查找长度： 3 11 1 1 2 2 4 3 4 4 ASLsucc＝ ＝ + + + 解：（1）若查 找给定值为20的元 素 , 依 次 与 表 中 25,10,15,20 元素比 较，共比较4次。 在查找不成功时,会找到图中某个方形节点,则不成功时 的平均查找长度： 3.67 12 4 3 8 4 ASLunsucc ＝ ＝ +
从上例看到,成功的折半查找过程恰好是走了一条从判定 树的根到被查记录的路径,经历比较的关键字次数恰为该记录 在树中的层数 若查找失败,则其比较过程是经历了一条从判定树根到某 个外部节点的路径,所需的关键字比较次数是该路径上內部节 点的总数
从上例看到，成功的折半查找过程恰好是走了一条从判定 树的根到被查记录的路径，经历比较的关键字次数恰为该记录 在树中的层数。 若查找失败，则其比较过程是经历了一条从判定树根到某 个外部节点的路径，所需的关键字比较次数是该路径上内部节 点的总数
8.23索引存储结构和分块查找 1.索引存储结构 索引存储结构是在存储数据的同时,还建立附加的索 引表。索引表中的每一项称为索引项,索引项的一般形式 如下: (关键字地址) 关键字唯一标识一个结点,地址作为指向该关键字对应结 点的指针,也可以是相对地址
8.2.3 索引存储结构和分块查找 1. 索引存储结构 索引存储结构是在存储数据的同时，还建立附加的索 引表。索引表中的每一项称为索引项，索引项的一般形式 如下： （关键字,地址） 关键字唯一标识一个结点，地址作为指向该关键字对应结 点的指针，也可以是相对地址
2.分块查找 分块查找又称索引顺序查找,它是一种性能介于顺序 查找和折半查找之间的查找方法。 它要求按如下的索引方式来存储线性表:将表R0.n 均分为b块,前b-1块中元素个数为m/b1,最后一块即第b 块的元素数小于等于s;每一块中的关键字不一定有序,但 前一块中的最大关键字必须小于后一块中的最小关键字, 即要求表是“分块有序”的;抽取各块中的最大关键字及 其起始位置构成一个索引表IX|0.b-11,即DX[i(0≤还b1) 中存放着第i块的最大关键字及该块在表R中的起始位置。 由于表R是分块有序的,所以索引表是一个递增有序表
2. 分块查找 分块查找又称索引顺序查找，它是一种性能介于顺序 查找和折半查找之间的查找方法。 它要求按如下的索引方式来存储线性表：将表R[0..n-1] 均分为b块，前b-1块中元素个数为s=n/b，最后一块即第b 块的元素数小于等于s；每一块中的关键字不一定有序，但 前一块中的最大关键字必须小于后一块中的最小关键字， 即要求表是“分块有序”的；抽取各块中的最大关键字及 其起始位置构成一个索引表IDX[0..b-1]，即IDX[i]（0≤i≤b-1） 中存放着第i块的最大关键字及该块在表R中的起始位置。 由于表R是分块有序的，所以索引表是一个递增有序表
例如,设有一个线性表采用顺序表R存储,其中包含25 个元素,其关键字序列为 (8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100, 94,88,96,87)。 假设将25个元素分为5块(b=5),每块中有5个元素 (s=5),该线性表的索引存储结构如下图所示。第一块中最 大关键字14小于第2块中最小关键字18,第2块中最大关键字 34小于第3块中最小关键字38,如此等等 346685100k 索引表 05101520link 数据表 8山49102|1814028sf4l7|28×0810(× 0123456789101112131415161718192021222324
例如，设有一个线性表采用顺序表R存储，其中包含25 个元素，其关键字序列为 （8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100, 94,88,96,87）。 假设将25个元素分为5块（b=5），每块中有5个元素 （s=5），该线性表的索引存储结构如下图所示。第一块中最 大关键字14小于第2块中最小关键字18，第2块中最大关键字 34小于第3块中最小关键字38，如此等等。 14 34 66 85 100 0 5 10 15 20 8 14 6 9 10 22 34 18 19 31 40 38 54 66 46 71 78 68 80 85 100 94 88 96 87 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 key link 索引表 数据表