第七章学习小结-蒲公英云

一、本章内容小结：

本章主要学习了查找的基本概念以及对于基于不同的数据结构的各种查找表适用的查找方法的定义、查找及算法，其中主要包括3种不同结构的查找表：线性表、树表和散列表。

1、线性表的查找：

（1）顺序查找：从表的一段开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和定值相等的记录，则查找失败。

顺序查找算法描述：

int Search_Seq(SSTable ST,keyType key)
{
    for(i = ST.length;i>=1;--i)
      if(ST.R[i].key == key)    return i;
    return 0;
}

设置监视哨的顺序查找算法描述：

int Search_Seq(SSTable ST,KeyType key)
{
    ST.R[0].key=key;
    for(i=ST.length;ST.R[i].key!=key;--i);
    return i;
}

（2）折半查找：折半查找要求线性表必须采用顺序存储结构，并且表中的元素按关键字有序排列。从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的一半中查找，重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。

算法描述：

int Search_Bin(SSTable ST,KeyType key)
{
    low=1;high=ST.length;
    while(low<=high)
  {
     mid=(low+high)/2;
     if(key==ST.R[mid].key)  return mid;
     else if(key<ST.R[mid].key)  high=mid-1;
     else low=mid+1;   
   }
     return 0;
 }

（3）分块查找：分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。

2、树表的查找：本章介绍了关于二叉排序树、平衡二叉树以及B-树的定义、创建、查找及插入等操作。

（1）二叉排序树的查找算法描述：

BSTree SearchBST(BSTree T,KeyType key)
{
    if((!T||key==T->data.key)  return T;
    else if(key<T->data.key)  return SearchBST(T->lchild,key);
    else return SearchBST(T->rchild,key);
}

（2）平衡二叉树的定义：平衡二叉树（Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。平衡二叉树是一种高度平衡的二叉排序树，即要么是一棵空树，要么它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡树。

（3）B-树的查找算法描述：

Result SearchBTree(BTree T,KeyType key)
{
    p=T;q=NULL;found=FALSE;i=0;
    while(p&&!found)
 {
    i=Search(p,key);
    if(i>0&&p->K[i]==key)  found=TRUE;
    else(q=p;p=->pptr[i];
 }
   if(found) return(p,i,l);
   else return(q,i,0);
}

3、散列表：

（1）概念：若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。对不同的关键字可能得到同一散列地址，即k1**≠k2，而f(k1)=f(k2)，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)**和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

（2）散列函数的构造方法：数字分析法、平方取中法、折叠法、除留余数法。

（3）处理冲突的办法：

a、开放地址法：其中包括线性探测法、二次探测法、伪随机探测法。

b、链地址法。

（4）散列表的查找算法描述：

#define NULLKEY 0
int SearchHash(HashTable HT,KeyType key)
{
    H0=H(key);
    if(HT[H0].key==NULLKEY) return -1;
    else if(HT[H0].key==key)  return H0;
    else
  {
     for(i=1;=<m;++i)
     {  Hi=(H0+i)%m;
         if(HT[Hi].key==NULLKEY)   return -1;
         else if(HT[Hi].key==key)    return Hi;
      }
      return -1;
    }
 }

4、顺序查找、折半查找和分块查找的比较：

	顺序查找	折半查找	分块查找
查找时间复杂度	O（n）	O（log₂n)	与确定所在块的查找方法有关
特点	算法简单，对表结构无任何要求，但查找效率较低	对表结构要求较高，查找效率较高	对表结构有一定要求，查找效率介于折半查找和顺序查找之间
适用情况	任何结构的线性表，不经常做插入和删除	有序的顺序表，不经常做插入和删除	块间有序、块内无序的顺序表，经常做插入和删除

5、二叉排序树在形态均匀时性能最好，因此，二叉排序树最好的一颗平衡二叉树，平衡二叉树的平衡调整方法就是确保二叉排序树在任何情况下的深度均为O（log2n），平衡调整方法分为4种：LL型、RR型、LR型和RL型。

B-树是一种平衡的多叉查找树，是一种在外存文件系统中常用的动态索引技术。在B-树上进行查找的过程和二叉排序树类似，是一个顺指针查找结点和在结点内的关键字中查找交叉进行的过程。

B+树是一种B-树的变型树，更适合做文件系统的索引。

6、散列表中处理冲突的方法的比较：

	开放地址法	链地址法
空间	无指针域，存储效率较高	附加指针域，存储效率较低
查找	有二次聚集现象，查找效率较低	无二次聚集现象，查找效率较高
插入、删除	不易实现	易于实现
适用情况	表的大小固定，适于表长无变化的情况	结点动态生成，适于表长经常变化的情况