• 分块查找

    分块查找

    1. #include <stdio.h>
    2. #define MaxSize 100
    3. #define MaxBlk 20
    5. typedef int KeyType;
    7. typedef char ElemType[10];
    9. typedef struct
    10. {    
    11.     KeyType key;       /*存放关键字,KeyType为关键字类型*/
    12.     ElemType data;    /*其他数据, ElemType为其他数据的类型*/
    13. } LineList;
    15. typedef struct
    16. {    
    17.     KeyType key;
    18.     int low,high;
    19. } IDXType;            /*索引表的类型*/
    21. int BlkSearch(LineList R[],IDXType idx[],int m,KeyType k)
    22. {
    23.     int low=0,high=m-1,mid,i,j,find=0;
    24.     while (low<=high && !find)    /*二分查找索引表*/
    25.     {
    26.         mid=(low+high)/2;
    27.         if (k<idx[mid].key) 
    28.             high=mid-1;
    29.         else if (k>idx[mid].key) 
    30.             low=mid+1;
    31.         else 
    32.         {
    33.             high=mid-1;
    34.             find=1;
    35.         }
    36.     }
    37.     if (low<m)                     /*k小于索引表内最大值*/
    38.     {
    39.         i=idx[low].low;            /*在索引表中定块起始地址*/
    40.         j=idx[low].high;        /*在索引表中定块终止地址*/
    41.        }
    42.     while (i<j && R[i].key!=k) /*在指定的块内采用顺序方法进行查找*/
    43.         i++;
    44.      if (i>=j)
    45.          return(-1);
    46.     else
    47.         return(i);
    48. }
    50. void main()
    51. {
    52.     KeyType a[]={9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82},k=48;
    53.     LineList R[MaxSize];
    54.     IDXType I[MaxBlk];
    55.     int n=16,m=4,i;
    56.     for (i=0;i<n;i++)
    57.         R[i].key=a[i];
    58.     I[0].key=22;I[0].low=0;I[0].high=3;
    59.     I[1].key=44;I[1].low=4;I[1].high=7;
    60.     I[2].key=60;I[2].low=8;I[2].high=11;
    61.     I[3].key=82;I[3].low=12;I[3].high=15;
    62.     i=BlkSearch(R,I,m,k);
    63.     if (i>=0)
    64.         printf("R[%d].key=%d\n",i,k);
    65.     else
    66.         printf("%d不在a中\n",k);
    67. }