分块检索思想 “按块有序” 口设线性表中共有n个数据元素,将表分成 块 不需要均匀 每一块可能不满 a每一块中的关键码不一定有序 口但前一块中的最大关键码必须小于后一块 中的最小关键码 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 分块检索思想 ◼ “按块有序” ❑ 设线性表中共有n个数据元素，将表分成 b块 ◼ 不需要均匀 ◼ 每一块可能不满 ❑ 每一块中的关键码不一定有序 ❑ 但前一块中的最大关键码必须小于后一块 中的最小关键码
索引表 索引表 口各块中的最大关键码 口及各块起始位置 口可能还需要块中元素个数(每一块可能不 满) 索引表是一个递增有序表 口由于表是分块有序的 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 索引表 ◼ 索引表 ❑ 各块中的最大关键码 ❑ 及各块起始位置 ❑ 可能还需要块中元素个数（每一块可能不 满） ◼ 索引表是一个递增有序表 ❑ 由于表是分块有序的
分块检索—一索引顺序结构 01234567891011121314151617 22139833|42442448 608074498653 link 0 0 块内最大关键码 Key 22 4886■块起始位置 count 0556■块内有效元素个数 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 分块检索——索引顺序结构 link: Key: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 22 13 9 8 33 42 44 24 48 60 80 74 49 86 53 0 0 6 12 - 22 48 86 0 5 5 6 ◼ 块内最大关键码 ◼ 块起始位置 count: ◼ 块内有效元素个数
typedef struct t int maxkey, firstloc, count 3 Index typedef struct t int *elen, length, blknum;∥块的数目 ndex idx[MAXBLOCK];∥块起始位置 ∥和最大元素,其中idx[0]不利用 3 IdxsqList; ∥索引顺序表类型 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 typedef struct { int maxkey, firstloc, count; } Index; typedef struct { int *elem, length, blknum; // 块的数目 Index idx[MAXBLOCK]; // 块起始位置 // 和最大元素，其中idx[0]不利用 } IdxSqList; // 索引顺序表类型
int Search IdxSeq IdxsqList L, int key)t if (key>L idx[L blknum]. maxkey) return ErroR: int i, j, temp, mid, low, high, found lOw=1; high=L blknum; found=false; while(low<=high & found)i mid =(lowthigh)2 if (key <=Lidx[mid]. markey & key >L idx[mid-1]. maxkey found=true;∥就在第mid块中 else if (key >Lidx[mid]. maxkey loW=mid+1;∥向右找 else high=mid-1;∥向左找 一五”国家规划教材。张铭,王腾蛟,赵海燕,《飙据结构与算法》,高教社,B008.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 int Search_IdxSeq(IdxSqList L,int key) { if (key>L.idx[L.blknum].maxkey) return ERROR; int i, j, temp, mid, low, high, found; low=1; high=L.blknum; found=false; while (low<=high && !found) { mid = (low+high)/2 if (key <= L.idx[mid].maxkey && key > L.idx[mid-1].maxkey) found = true; // 就在第mid块中 else if (key > L.idx[mid].maxkey) low = mid+1; // 向右找 else high = mid-1; // 向左找 }