还剩1页未读,继续阅读
文本内容:
分块查找算法分块查找BlockingSearch又称索引挨次查找它是一种性能介于挨次查找和二分查找之间的查找方法
1、分块查找表存储结构分块查找表由“分块有序”的线性表和索引表组成1分块有序”的线性表表均分为b块,前b-1块中结点个数为・第b块的结点数小于等于s;每一块中的关键字不肯定有序,但前一块中的最大关键字必需小于后一块中的最小关键字,即表是“分块有序”的2索引表抽取各块中的最大关键字及其起始位置构成一个索引表ID[I…上]即ID[i]lViWb中存放第i块的最大关键字及该块在表R中的起始位置由于表R是分块有序的,所以索引表是一个递增有序表【例】下图就是满意上述要求的存储结构,其中R只有18个结点,被分成3块,每块中有6个结点,第一块中最大关键字22小于其次块中最小关键字24其次块中最大关键字48小于第三块中最小关键字49023456789101112131415161718J212133920334244382448605874498653分块有序表的索引存储表示.分块查找的基本思想1首先查找索引表索引表是有序表,可采纳二分查找或挨次查找,以确定待查的结点在哪一块2然后在已确定的块中进行挨次查找由于块内无序,只能用挨次查找.分块有找示例【例】对于上例的存储结构1查找关键字等于给定值K=24的结点由于索引表小,不妨用挨次查找方法查找索引表即首先将K依次和索引表中各关键字比较,直到找到第1个关键宇大小等于K的结点由于K48所以关键字为24的结点若存在的话,则必定在其次块中;然后,由ID
[2].addr找到其次块的起始地址7从该地址开头在R[
7.・12]中进行挨次查找,直到R[ll].key=K为止2查找关键字等于给定值K=30的结点先确定其次块,然后在该块中查找因该块中查找不胜利,故说明表中不存在关键字为30的结点。