第九章 查找
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.length||st.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\",last);
  if(last<=x&&t->data>x) /*找到了大于x的最小元素
    printf("b=%d\",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\",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_nlt(t,x); /*继续在左子树中执行算法
}/*delete_nlt
9.35
void print_between(bithrtree t,int a,int b)/*打印输出后继线索二叉排序树t中所有大于a且小于b的元素
{
  p=t;
  while(!p->ltag) p=p->lchild; /*找到最小元素
  while(p&&p->data<b)
  {
    if(p->data>a) printf("%d\",p->data); /*输出符合条件的元素
    if(p->rtag) p=p->rtag;
    else
    {
      p=p->rchild;
      while(!p->ltag) p=p->lchild;
    } /*转到中序后继
  }/*while
}/*print_between
9.36
void bstree_insert_key(bithrtree &t,int x)/*在后继线索二叉排序树t中插入元素x
{
  if(t->data<x) /*插入到右侧
  {
    if(t->rtag) /*t没有右子树时,作为右孩子插入
    {
      p=t->rchild;
      q=(bithrnode*)malloc(sizeof(bithrnode));
      q->data=x;
      t->rchild=q;t->rtag=0;
      q->rtag=1;q->rchild=p; /*修改原线索
    }
    else bstree_insert_key(t->rchild,x);/*t有右子树时,插入右子树中
  }/*if
  else if(t->data>x) /*插入到左子树中
  {
    if(!t->lchild) /*t没有左子树时,作为左孩子插入
    {
      q=(bithrnode*)malloc(sizeof(bithrnode));
      q->data=x;
      t->lchild=q;
      q->rtag=1;q->rchild=t; /*修改自身的线索
    }
    else bstree_insert_key(t->lchild,x);/*t有左子树时,插入左子树中
  }/*if
}/*bstree_insert_key
9.37
status bstree_delete_key(bithrtree &t,int x)/*在后继线索二叉排序树t中删除元素x
{
  btnode *pre,*ptr,*suc;/*ptr为x所在结点,pre和suc分别指向ptr的前驱和后继
  p=t;last=null; /*last始终指向当前结点p的前一个(前驱)
  while(!p->ltag) p=p->lchild; /*找到中序起始元素
  while(p)
  {
    if(p->data==x) /*找到了元素x结点
    {
      pre=last;
      ptr=p;
    }
    else if(last&&last->data==x) suc=p; /*找到了x的后继
    if(p->rtag) p=p->rtag;
    else
    {
      p=p->rchild;
      while(!p->ltag) p=p->lchild;
    } /*转到中序后继
    last=p;
  }/*while /*借助中序遍历找到元素x及其前驱和后继结点
  if(!ptr) return error; /*未找到待删结点
  delete_bstree(ptr); /*删除x结点
  if(pre&&pre->rtag)
    pre->rchild=suc; /*修改线索
  return ok;
}/*bstree_delete_key
void delete_bstree(bithrtree &t)/*课本上给出的删除二叉排序树的子树t的算法,按照线索二叉树的结构作了一些改动
{
  q=t;
  if(!t->ltag&&t->rtag) /*结点无右子树,此时只需重接其左子树
    t=t->lchild;
  else if(t->ltag&&!t->rtag) /*结点无左子树,此时只需重接其右子树
    t=t->rchild;
  else if(!t->ltag&&!t->rtag) /*结点既有左子树又有右子树
  {
    p=t;r=t->lchild;
    while(!r->rtag)
    {
      s=r;
      r=r->rchild; /*找到结点的前驱r和r的双亲s
    }
    t->data=r->data; /*用r代替t结点
    if(s!=t)
      s->rchild=r->lchild;
    else s->lchild=r->lchild; /*重接r的左子树到其双亲结点上
    q=r;
  }/*else
  free(q); /*删除结点
}/*delete_bstree
分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.
9.38
void bstree_merge(bitree &t,bitree &s)/*把二叉排序树s合并到t中
{
  if(s->lchild) bstree_merge(t,s->lchild);
  if(s->rchild) bstree_merge(t,s->rchild); /*合并子树
  insert_key(t,s); /*插入元素
}/*bstree_merge
void insert_node(bitree &t,btnode *s)/*把树结点s插入到t的合适位置上
{
  if(s->data>t->data)
  {
    if(!t->rchild) t->rchild=s;
    else insert_node(t->rchild,s);
  }
  else if(s->data<t->data)
  {
    if(!t->lchild) t->lchild=s;
    else insert_node(t->lchild,s);
  }
  s->lchild=null; /*插入的新结点必须和原来的左右子树断绝关系
  s->rchild=null; /*否则会导致树结构的混乱
}/*insert_node
分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.
9.39
void bstree_split(bitree &t,bitree &a,bitree &b,int x)/*把二叉排序树t分裂为两棵二叉排序树a和b,其中a的元素全部小于等于x,b的元素全部大于x
{
  if(t->lchild) bstree_split(t->lchild,a,b,x);
  if(t->rchild) bstree_split(t->rchild,a,b,x); /*分裂左右子树
  if(t->data<=x) insert_node(a,t);
  else insert_node(b,t); /*将元素结点插入合适的树中
}/*bstree_split
void insert_node(bitree &t,btnode *s)/*把树结点s插入到t的合适位置上
{
  if(!t) t=s; /*考虑到刚开始分裂时树a和树b为空的情况
  else if(s->data>t->data) /*其余部分与上一题同
  {
    if(!t->rchild) t->rchild=s;
    else insert_node(t->rchild,s);
  }
  else if(s->data<t->data)
  {
    if(!t->lchild) t->lchild=s;
    else insert_node(t->lchild,s);
  }
  s->lchild=null;
  s->rchild=null; 
}/*insert_key
9.40
typedef struct {
                     int data;
                     int bf;
                     int lsize; /*lsize域表示该结点的左子树的结点总数加1
                     blcnode *lchild,*rchild;
                  } blcnode,*blctree; /*含lsize域的平衡二叉排序树类型
btnode *locate_blctree(blctree t,int k)/*在含lsize域的平衡二叉排序树t中确定第k小的结点指针
{
  if(!t) return null; /*k小于1或大于树结点总数
  if(t->lsize==k) return t; /*就是这个结点
  else if(t->lsize>k)
    return locate_blctree(t->lchild,k); /*在左子树中寻找
  else return locate_blctree(t->rchild,k-t->lsize); /*在右子树中寻找,注意要修改k的值
}/*locate_blctree
9.41
typedef struct {
                 enum {leaf,branch} tag; /*结点类型标识
                 int keynum;
                 bplink parent; /*双亲指针
                 int key[maxchild]; /*关键字
                 union {
                         bplink child[maxchild];/*非叶结点的孩子指针
                         struct {
                                  rectype *info[maxchild];/*叶子结点的信息指针
                                  bpnode *next; /*指向下一个叶子结点的链接
                                  } leaf;
                         }
              } bpnode,*bplink,*bptree;/*b+树及其结点类型
status bptree_search(bptree t,int key,bpnode *ptr,int pos)/*b+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos
{
  p=t;
  while(p.tag==branch) /*沿分支向下查找
  {
    for(i=0;i<p->keynum&&key>p->key[i];i++); /*确定关键字所在子树
    if(i==p->keynum) return error; /*关键字太大
    p=p->child[i];
  }
  for(i=0;i<p->keynum&&key!=p->key[i];i++); /*在叶子结点中查找
  if(i==p->keynum) return error; /*找不到关键字
  ptr=p;pos=i;
  return ok;
}/*bptree_search  
9.42
void trietree_insert_key(trietree &t,stringtype key)/*在trie树t中插入字符串key,stringtype的结构见第四章
{
  q=(trienode*)malloc(sizeof(trienode));
  q->kind=leaf;
  q->lf.k=key; /*建叶子结点
  klen=key[0];
  p=t;i=1;
  while(p&&i<=klen&&p->bh.ptr[ord(key[i])])
  {
    last=p;
    p=p->bh.ptr[ord(key[i])];
    i++;
  } /*自上而下查找
  if(p->kind==branch) /*如果最后落到分支结点(无同义词):
  {
    p->bh.ptr[ord(key[i])]=q; /*直接连上叶子
    p->bh.num++;
  }
  else /*如果最后落到叶子结点(有同义词):
  {
    r=(trienode*)malloc(sizeof(trienode)); /*建立新的分支结点
    last->bh.ptr[ord(key[i-1])]=r; /*用新分支结点取代老叶子结点和上一层的联系
    r->kind=branch;r->bh.num=2;
    r->bh.ptr[ord(key[i])]=q;
    r->bh.ptr[ord(p->lf.k[i])]=p; /*新分支结点与新老两个叶子结点相连
  }
}/*trietree_insert_key
分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种情况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层.
9.43
status trietree_delete_key(trietree &t,stringtype key)/*在trie树t中删除字符串key
{
  p=t;i=1;
  while(p&&p->kind==branch&&i<=key[0]) /*查找待删除元素
  {
    last=p;
    p=p->bh.ptr[ord(key[i])];
    i++;
  }
  if(p&&p->kind==leaf&&p->lf.k=key) /*找到了待删除元素
  {
    last->bh.ptr[ord(key[i-1])]=null;
    free(p);
    return ok;
  }
  else return error; /*没找到待删除元素
}/*trietree_delete_key
9.44
void print_hash(hashtable h)/*按第一个字母顺序输出hash表中的所有关键字,其中处理冲突采用线性探测开放定址法
{
  for(i=1;i<=26;i++)
    for(j=i;h.elem[j].key;j=(j+1)%hashsize[sizeindex]) /*线性探测
      if(h(h.elem[j].key)==i) printf("%s\",h.elem[j]);
}/*print_hash
int h(char *s)/*求hash函数
{
  if(s) return s[0]-96; /*求关键字第一个字母的字母序号(小写)
  else return 0;
}/*h
9.45
typedef *lnode[maxsize] chashtable; /*链地址hash表类型
status build_hash(chashtable &t,int m)/*输入一组关键字,建立hash表,表长为m,用链地址法处理冲突.
{
  if(m<1) return error;
  t=malloc(m*sizeof(word)); /*建立表头指针向量
  for(i=0;i<m;i++) t[i]=null;
  while((key=inputkey())!=null) /*假定inputkey函数用于从键盘输入关键字
  {
    q=(lnode*)malloc(sizeof(lnode));
    q->data=key;q->next=null;
    n=h(key);
    if(!t[n]) t[n]=q; /*作为链表的第一个结点
    else
    {
      for(p=t[n];p->next;p=p->next);
      p->next=q; /*插入链表尾部.本算法不考虑排序问题.
    }
  }/*while
  return ok;
}/*build_hash
9.46
status locate_hash(hashtable h,int row,int col,keytype key,int &k)/*根据行列值在hash表表示的稀疏矩阵中确定元素key的位置k
{
  h=2*(100*(row/10)+col/10); /*作者设计的hash函数
  while(h.elem[h].key&&!eq(h.elem[h].key,key))
    h=(h+1)%20000;
  if(eq(h.elem[h].key,key)) k=h;
  else k=null;
}/*locate_hash
分析:本算法所使用的hash表长20000,装填因子为50%,hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为o(1).