数据结构第九章

《数据结构第九章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章查找9.25intSearch_Sq(SSTableST,intkey)//在有序表上顺序查找的算法,监视哨设在高下标端{  ST.elem[ST.length+1].key=key;  for(i=1;ST.elem[i].key>key;i++);  if(i>ST.length

2、

3、ST.elem[i].key

4、arch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的递归算法{  if(low>high)return0;//查找不到时返回0  mid=(low+high)/2;  if(ST.elem[mid].key==key)returnmid;  elseif(ST.elem[mid].key>key)    returnSearch_Bin_Recursive(ST,key,low,mid-1);  elsereturnSearch_Bin_Recurs

5、ive(ST,key,mid+1,high);  }}//Search_Bin_Recursive9.27intLocate_Bin(SSTableST,intkey)//折半查找,返回小于或等于待查元素的最后一个结点号{  int*r;  r=ST.elem;  if(key=r[ST.length].key)returnST.length;  low=1;high=ST.length;  while(low<=high)  {    mid=(low+

6、high)/2;    if(key>=r[mid].key&&key

7、x;typedefstruct{                int*elem;                intlength;                Indexidx[MAXBLOCK];//每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找                intblknum;//块的数目              }IdxSqList;//索引顺序表类型intSearch_IdxSeq(IdxSqListL,intkey)//分块查找,用折半查

8、找法确定记录所在块,块内采用顺序查找法{  if(key>L.idx[L.blknum].maxkey)returnERROR;//超过最大元素  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;    elseif(key>L.idx[

9、mid].maxkey)      low=mid+1;    elsehigh=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

10、h_IdxSeq分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.9.29typedefstruct{                LNode*h;//h指向最小元素                LNode*t;//t指向上次查找的结点             }CSList;LNode*Search_CSList(CSLis