查找表

标签：折半记录 ST 关键字查找 key

查找表：是由同以类型的数据元素(或记录)构成的集合。由于"集合"中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构

什么查找？

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录。

关键字：用来标识一个数据元素(或记录)的某个数据项的值。

主关键字：可唯一地标识一个记录的关键字是主关键字；

次关键字：反之，用以识别若干记录的关键字是次关键字。

查找的结果

查找结果给出整个记录的信息，或指示该记录的在查找表中的位置
查找不成功：给出"空记录"或"空指针"

查找表分类

静态查找表
仅作"查询"(检索)操作的查找表
*动态查找表
作"插入"和"删除"操作的查找表
有时在查询之后，还需要"查询"结果为"不在查找表中"的数据元素插入到查找表中；或者，从查找表中删除其查询结果为在查找表中的数据元素
，此类表为动态查找表

查找算法的评价指标

关键字的平均比较次数，也称平均查找长度
ASL(Average Search Length)

线性表的查找

顺序查找(线性查找)

顺序表或线性链表表示的静态查找表
表内元素之间无序
顺序表的表示：
数据元素类型定义

typedef struct{
 KeyType key;//关键子域
  ....//其他域
}ElemType;

typeder struct{
    ElemType *R ;//表基址
    int length；//表长
}SSTable;//SequentialSeearch Table

SSTable ST; //定义顺序表ST

伪代码

匹配

int Search_Seq(SSTable ST, KeyType key)
{
  //若成功返回其位置信息，否则返回0
  for(i=ST.length;i>=1;--i)
  {
   if(ST.R[i].key == key)
   return i;
  }
  return 0;
}

int Search_Seq(SSTableST,KeyType key)
{

 for(i=ST.length;ST.R[i].key!=key;--i)
  if（i<=0）break;
  if(i>0) return i;
  else return 0;
}

改进：把待查关键字key存入表头("哨兵"、"监视哨")从后往前逐个比较，可卖你去查找过程中每一步都要检测是否查找完毕，加快速度。

设置监视哨的顺序查找

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

当ST.length较大时，此改进能使进行一次查找所需的平均时间几乎减少一半
比较次数与key位置有关：

查找第i个元素，需要比较n-i+1次
查找失败需要比较n+1次

思考

记录的查找概率不相等时如何提高查找效率

查找概率越高，比较次数越少。
查找概率越低，比较次数较多。

记录的查找概率无法测定时如何提高查找效率

方法-----在查找概率动态调整记录顺序：
（1）在每个记录中设一个访问频度域
(2)始终保持记录按非递增有序的次序排列
（3）每次查找后均将刚查到的记录直接移到表头

折半查找(二分或对分查找)

折半查找：每次将待查记录所在区间缩小一半
查找过程

折半查找算法(非递归算法)

设表长n,low,high 和mid分别指向待查元素所在区间的上界、下界和中点，key为给定的要查找的值：
初始，令low=1,high=n,mid=(low+high)/2(向下取整)
让k与mid指向的记录比较
若key== R[mid].key ,查找成功
若key<R[mid].key,则high=mid-1
若key>R[mid].key,则low=mid+1
重复上述操作，直至low>high时，查找失败

折半查找算法

int Search_Bin(SSTable ST,KeyType key)
{
  int low =1;
  int high =ST.length;
  int mid = (low+high)/2
   while(low<=high)
   {
    if(ST.R[mid].key == key)
    return mid;//找到待查元素
    else if(key<ST.R[mid].key)//缩小查找区间
         high = mid-1; //继续在前半个区间进行查找
    else
        low = mid+1;//继续在后半区间进行查找
  }
return 0；//顺序表中不存在待查元素
}Serach_bin