else if(key <r[mid]. key)high=mid else low=mid }∥本算法不存在査找失败的情况,不需要 return0; 3//Locate Bin 928 typedef struct int mackey int firstloc ypedef struct i int length Index idx MAXBLOCK];∥每块起始位置和最大元素,其 中dx[O不利用,其内容初始化为{0,0}以利于折半查找 int blknun,∥块的数目 } IdxSqList;/索引顺序表类型 int Search IdxSeq( Idxsqlist L, int key )分块査找,用折半査找法确定记录所在块, 块内采用顺序查找法 ikey> L.idx[L blknum] markey) return ErroR;∥超过最大元素 low=l; high=L blknum found=0 whie(ow<high&&! found)∥折半查找记录所在块号md mid=dlow+highT key<=L idx[mid ] maxkey&&key>L idx[mid-1]. maxkey) found=1 else if(key>L idx[ mid mackey) low=mid+ else high=mid-1 i=Ldx[mid] firstloc;/块的下界 j=i计+ blksize-1;∥块的上界 temp=Llem[i-1]∥保存相邻元素 L elem[ill=key,∥设置监视哨 for(k= j, L elem(k!=keyk-),∥顺序查找 L elem[i1}=temp;∥恢复元素 if(ki) return ERROr;∥未找到 eturn k. i//Search IdxSeqelse if(key<r[mid].key) high=mid; else low=mid; } //本算法不存在查找失败的情况,不需要 return 0; }//Locate_Bin 9.28 typedef struct { int maxkey; int firstloc; } Index; typedef struct { int *elem; int length; Index idx[MAXBLOCK]; //每块起始位置和最大元素,其 中 idx[0]不利用,其内容初始化为{0,0}以利于折半查找 int blknum; //块的数目 } IdxSqList; //索引顺序表类型 int Search_IdxSeq(IdxSqList L,int key)//分块查找,用折半查找法确定记录所在块, 块内采用顺序查找法 { if(key>L.idx[L.blknum].maxkey) return ERROR; //超过最大元素 low=1;high=L.blknum; found=0; while(low<=high&&!found) //折半查找记录所在块号 mid { mid=(low+high)/2; if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey) found=1; else if(key>L.idx[mid].maxkey) low=mid+1; else high=mid-1; } i=L.idx[mid].firstloc; //块的下界 j=i+blksize-1; //块的上界 temp=L.elem[i-1]; //保存相邻元素 L.elem[i-1]=key; //设置监视哨 for(k=j;L.elem[k]!=key;k--); //顺序查找 L.elem[i-1]=temp; //恢复元素 if(k<i) return ERROR; //未找到 return k; }//Search_IdxSeq