第九章　查找　题解

核心提示：第九章 查找 9.25 int Search_Sq(SSTable ST,int key)/*在有序表上顺序查找的算法,监视哨设在高下标端{ ST.elem[ST.length+1].key=key; for(i=1;ST.elem[i].key>key;i++); if(i>ST.lengthST.

　　　　　　　　　　　　　　　　　　　第九章 查找
9.25
int Search_Sq(SSTable ST,int key)/*在有序表上顺序查找的算法,监视哨设在高下标端
{
  ST.elem[ST.length+1].key=key;
  for(i=1;ST.elem[i].key>key;i++);
  if(i>ST.lengthST.elem[i].key<key) 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(low>high) return 0; /*查找不到时返回0
  mid=(low+high)/2;
  if(ST.elem[mid].key==key) return mid;
  else if(ST.elem[mid].key>key)
　  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(key<r .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].key&&key<r[mid+1].key) /*查找结束的条件
　　  return mid;
　  else 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
分析:在块内进行顺序查找时,假如需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.
9.29
typedef struct {
　　　　　　　　　　 LNode *h; /*h指向最小元素
　　　　　　　　　　 LNode *t; /*t指向上次查找的结点
　　　　　　　　  } CSList;
LNode *Search_CSList(CSList &L,int key)/*在有序单循环链表存储结构上的查找算法,假定每次查找都成功
{
  if(L.t->data==key) return L.t;
  else if(L.t->data>key)
　  for(p=L.h,i=1;p->data!=key;p=p->next,i++);
  else
　  for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);
  L.t=p; /*更新t指针
  return p;
}/*Search_CSList
分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.
9.30
typedef struct {
　　　　　　　　　　 DLNode *PRe;
　　　　　　　　　　 int data;
　　　　　　　　　　 DLNode *next;
　　　　　　　　  } DLNode;
typedef struct {
　　　　　　　　　　 DLNode *sp;
　　　　　　　　　　 int length;
　　　　　　　　  } DSList; /*供查找的双向循环链表类型
DLNode *Search_DSList(DSList &L,int key)/*在有序双向循环链表存储结构上的查找算法,假定每次查找都成功
{
  p=L.sp;
  if(p->data>key)
  {
　  while(p->data>key) p=p->pre;
　  L.sp=p;
  }
  else if(p->data<key)
  {
　  while(p->data<key) p=p->next;
　  L.sp=p;
  }
  return p;
}/*Search_DSList
分析:本题的平均查找长度与上一题相同,也是n/3.
9.31
int last=0,flag=1;
int Is_BSTree(Bitree T)/*判定二叉树T是否二叉排序树,是则返回1,否则返回0
{
  if(T->lchild&&flag) Is_BSTree(T->lchild);
  if(T->data<last) flag=0; /*与其中序前驱相比较
  last=T->data;
  if(T->rchild&&flag) Is_BSTree(T->rchild);
  return flag;
}/*Is_BSTree
9.32
int last=0;
void MaxLT_MinGT(BiTree T,int x)/*找到二叉排序树T中小于x的最大元素和大于x的最小元素
{
  if(T->lchild) MaxLT_MinGT(T->lchild,x); /*本算法仍是借助中序遍历来实现
  if(last<x&&T->data>=x) /*找到了小于x的最大元素
　  printf("a=%d\n",last);
  if(last<=x&&T->data>x) /*找到了大于x的最小元素
　  printf("b=%d\n",T->data);
  last=T->data;
  if(T->rchild) MaxLT_MinGT(T->rchild,x);
}/*MaxLT_MinGT
9.33
void Print_NLT(BiTree T,int x)/*从大到小输出二叉排序树T中所有不小于x的元素
{
  if(T->rchild) Print_NLT(T->rchild,x);
  if(T->data<x) exit(); /*当碰到小于x的元素时立即结束运行
  printf("%d\n",T->data);
  if(T->lchild) Print_NLT(T->lchild,x); /*先右后左的中序遍历
}/*Print_NLT
9.34
void Delete_NLT(BiTree &T,int x)/*删除二叉排序树T中所有不小于x元素结点,并释放空间
{
  if(T->rchild) Delete_NLT(T->rchild,x);
  if(T->data<x) exit(); /*当碰到小于x的元素时立即结束运行
  q=T;
  T=T->lchild;
  free(q); /*假如树根不小于x,则删除树根,并以左子树的根作为新的树根
  if(T) Delete_NL