4.1 查找.pdfVIP

第九章 查找 9.25 int Search_Sq(SSTable ST,int key)// , 在有序表上顺序查找的算法监视哨设在高下 标端 { ST.elem[ST.length+1].key=key; for(i=1;ST.elem[i].keykey;i++); if(iST.length||ST.elem[i].keykey) return ERROR; return i; }//Search_Sq : ST.length/2, 分析本算法查找成功情况下的平均查找长度为 不成功情况下为 ST.length. 9.26 int Search_Bin_Recursive(SSTable ST,int key,int low,int high)//折半查找的递归算 法 { if(lowhigh) return 0; //查找不到时返回0 mid=(low+high)/2; if(ST.elem[mid].key==key) return mid; else if(ST.elem[mid].keykey) return Search_Bin_Recursive(ST,key,low,mid-1); else return Search_Bin_Recursive(ST,key,mid+1,high); } }//Search_Bin_Recursive 9.27 int Locate_Bin(SSTable ST,int key)// , 折半查找返回小于或等于待查元素的最后一 个结点号 { int *r; r=ST.elem; if(keyr .key) return 0; else if(key=r[ST.length].key) return ST.length; low=1;high=ST.length; while(low=high) { mid=(low+high)/2; if(key=r[mid].keykeyr[mid+1].key) //查找结束的条件 return mid; else if(keyr[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(keyL.idx[L.blknum]