您的位置: 网站首页 > 程序开发 > 数据结构 > 第7章 查找 > 【7.3 分 块 查 找】

7.3 分 块 查 找

 

7.3 

分块查找又称为索引顺序查找,是顺序查找的一种改进,其性能介于顺序查找和对分查找之间。分块查找将线性表分成若干块,每一块中的元素存储顺序是任意的,但块与块之间必须按关键字大小有序排列。即前一块中的最大关键字值小于(或大于)后一块中的最小(或最大)关键字值。另外,还需要建立一个索引表,索引表中的一项对应线性表中的一块,索引项由关键字域和链域组成,关键字域存放相应块的最大关键字,链域存放指向本块第一个元素的指针。索引表按关键字值递增(或递减)顺序排列。

分块查找过程分为两步进行,首先确定待查找的元素属于哪一块,即查找其所在的块;然后在块内查找要找的元素。由于索引表是递增有序的,因此可采用对分查找;而块内元素个数较少,在块内可采用顺序法查找。在块内的顺序查找不会对执行速度有太大的影响。

【例7-3给定关键字序列如下:18726341542367060558390787274,假设m=3s=5,即将该序列分成3个表,每个子表有5个元素,则得到主表和索引表如图7-4所示。

7-4  分块查找的主表和索引表

假设在上述表中查找“60”,则可以先在索引表中查找“60”所在的子表,由于346070,故“60”应在第二块,这时start=5length=5,因此,“60”应在主表的第5个位置~第9个位置之间查找。

分块查找的运算如下(在线性表R和含m个元素的索引表中分块查找关键字为k的元素,若查找到,则返回其序号i;若未查找到,则返回-1):

int BlkSearch(LineList R[ ],IDXType idx[ ],int m,KeyType k)

{

    int low=0,high=m-1,mid,i,j,find=0;

    while(low<=high && !find)            /*对分查找索引表*/

    {  

        mid=(low+high)/2;

        if(k<idx[mid].key)

            high=mid-1;

        else if(k>idx[mid].key)

            low=mid+1;

        else

        {  

            high=mid-1;

            find=1;

        }

    }

    if(low<m)                            /*k小于索引表内最大值*/

    {  

        i=idx[low].low;                 /*在索引表中定块起始地址*/

        j=idx[low].high;                /*在索引表中定块终止地址*/

   }

    while(i<j && R[i].key!=k)           /*在指定的块内采用顺序方法进行查找*/

        i++;

     if(i>=j)

        return(-1);

    else

        return(i);

}

算法分析:分块查找实际上进行两次查找,整个算法的平均查找长度是两次查找的平均查找长度之和。

假设有n个元素,分成bn块,每块有s个元素,即bn=n/s,每块的查找概率为1/bn,块内每个元素的查找概率为1/s。平均查找长度为:

ASLlog2(bn+1)-1+(s+1)/2log2(n/s+1)+s/2

分块查找的优点是:在线性表中插入或删除一个元素时,只要找到相应的块,然后在该块内进行插入或删除即可。由于块内元素个数相对较少,而且是任意存放的,所以插入或删除操作比较容易,不需要移动大量的元素。