算法 8.3.txt

数据结构各种算法原代码及图形示例

算法 8.3
int Search_Idx ( SSTable ST,  indexTable ID,  KeyType kval ) 
{
  // 在顺序表ST中分块查找其关键字等于给定值kval的数据元素，ID为索引表。
  // 若找到，则返回该数据元素在ST中的位置，否则返回0
   low = 0;  high = ID.length-1;  found = FALSE;
   if (kval>ID.elem[high].key) return 0;   // 给定值kval大于查找表中所有关键字
   while ( low <=high && !found ) { // 折半查找索引表，确定记录查找区间
     mid = (low+high)/2;
     if ( kval < ID.elem[mid].key )  high = mid - 1;
     else if ( kval > ID.elem[mid].key )  low = mid +1;
        else {  found = TRUE;  low = mid;  }
    }//while
   s = ID.elem[low].stadr; // 经索引表查找后，下一步的查找范围定位在第low块
   if ( low < ID.length-1 )  t = ID.elem[low +1].stadr-1; 
   else t = ST.length;    
        // s和t为在ST表进行查找的下界和上界，若不是最后一块，则上界为“下一块的起始位置之前”
   if ( ST.elem[t].key== kval )  return t;
   else {              // 在ST.elem[s] 至ST.elem[t-1]的区间内进行顺序查找
     ST.elem[0] = ST.elem[t]; // 暂存ST.elem[t]
     ST.elem[t].key = kval;   // 设置监视哨
     for ( k=s;  ST.elem[k].key !=kval;  k++ ) ;
     ST.elem[t] = ST.elem[0]; // 恢复暂存值
     if ( k != t ) return k;
     else return 0;
   } // else
} // Search_Idx