分块查找

  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. }