数据结构导论之第六章查找表

1571 0 0

作者:君子生非异也

一、概念

查找表(Search Table)是由同一类型的数据元素构成的集合，它是一种以查找为“核心”，同时包括其他运算的非常灵活的数据结构。

查找就是从大量的数据元素中找出某个指定的数据元素。关键字分为主关键字和次关键字两种。前者可以唯一标识一个数据元素，即对于不同的数据元素其主关键字均不同；后者则可以识别若干数据元素。

静态查找表是以具有相同特性的数据元素集合为逻辑结构，包括下列三种基本运算：建表 Create(ST)、查找 Search(ST, key)、读表中元素 Get(ST, pos)

动态查找表是以集合为逻辑结构，包括下列五种基本运算：初始化 Initiate (ST)、查找 Search(ST，key)、读表中元素 Get(ST, pos)、插入 Insert(ST，key)、删除 Delete(ST，key)。、

二、静态查找表

1、顺序查找

从表中最后一个记录开始顺序进行查找，若当前记录的关键字= 给定值，则查找成功；否则，继续查上一记录…；若直至第一个记录尚未找到需要的记录，则查找失败

//使用一种 设计技巧 ：设立 岗哨
int SearchSqtable(Sqtable T, KeyType key){  
   /* 在顺序表R 中顺序查找其关键字等于key 的元素。
    若找到，则函数值为该元素在表中的位置，否则为0*/
    T.elem[0].key=key; //设置岗哨
    i=T.n;//设置比较位置初值
    while ( T.elem[i].key!=key ){
        i--
    } 
    return i ;
}

例如：假设顺序表的（b1,b2,b3）的概率是0.2,0.2,0.6，顺序查找的平均长度？

ASL=0.2*(3-1+1)+0.2(3-2+1)+0.6(3-3+1)=1.6

2、有序表上的查找—二分查找

二分查找基本思想： 每次将处于查找区间中间位置上的数据元素与给定值K 比较，若不等则缩小查找区间并在新的区间内重复上述过程，直到查找成功或查找区间长度为0 （查找不成功）为止
有序表：如果顺序表中数据元素是按照键值大小的顺序排列的，则称为有序表。

算法过程：

1、用给定值 key 与处在中间位置的数据元素 T.elem[mid]的键值 T.elem[mid] .key 进行比较，可根据三种比较结果区分三种情况：
2、key=T.elem[mid].key，查找成功，T.elemEmid]即为待查元素；
3、key<t.elem[mid].key,说明若待查元素若在表中，则一定排在 t.elem[mid]="" 之前；
4、key>T.elem[mid].key,说明若待查元素若在表中，则一定排在 T.elem[mid]之后。

/*在有序表 T 中，用二分查找法查找键值等于 key 的元素，变量 low,hig 分别标记查找
区间的下界和上界*/
int SearchBin{SqTable T,KeyType key){ 
    int low,high;
    low=l;high=T.n; //置查找区间初值
    while (low<=high){ 
        //区间长度不为 0 时继续查找
        mid= (low+high) /2; //对区间进行折半，〃/〃为整除
        if (key==T.elem[mid].key){
            return mid;
        } else if(key<T.elem[mid] .key){
            high=mid-1; //在前半区间查找
        } else {
       　　 low=mid+1; //在后半区间查找
        }
    }
    return 0; //查找不成功，则返回
}

3、索引顺序表上的查找-分块查找

索引顺序表是结合了顺序查找和二分查找的优点构造的一种带索引的存储结构

一个索引顺序表由两部分组成：一个索引表和一个顺序表。其中的顺序表在组织形式上与普通的顺序表完全相同，而索引表本身在组织形式上也是一个顺序表。索引表通过索引将顺序表分割为若干块，而顺序表呈现出“按块有序”的性质。

若静态查找表用索引顺序表表示，则查找操作可用分块查找来实现，也称为索引顺序查找。根据上面对索引顺序表的描述，在索引顺序表上的查找即分块查找分两步进行：先确定待查数据元素所在的块；然后在块内顺序查找。

二、动态查找表

1、二叉排序树上的查找

二叉排序树：一种实现动态查找的树表——二叉排序树，这种树表的结构本身是在查找过程中动态生成的，即对于给定 key,若表中存在与 key 相等的元素，则查找成功，不然，插入关键字等于 key 的元素。一棵二叉排序树(Binary Sort Tree)(又称二叉查找树)或者是一棵空二叉树，或者是具有下列性质的二叉树：