第七章--查找-EW帮帮网

查找表

定义

由同一类型的数据元素(或记录)构成的集合。

1）特点：数据元素的类型相同；结构松散→先后次序无关紧要，只关心是否在集合内。

2）常用操作：查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素的各种属性；在查找表中插入一个数据元素；从查找表中删去某个数据元素。

查找表分类

1、静态查找：仅作查询和检索操作的查找表。

2、动态查找：有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中(如手机通讯录)；或者从查找表中删除其“查询”结果为“在查找表中”的数据元素。

关键字

关键字是数据元素(或记录)中某个数据项的值，用以标识（识别）一个数据元素(或记录)。

若此关键字可以识别唯一的一个记录，则称之谓 "主关键字"。若此关键字能识别若干记录，则称之谓"次关键字"。

查找

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

若查找表中存在这样一个记录，则称“查找成功”，

查找结果：

给出整个记录的信息
指示该记录在查找表中的位置；
否则称“查找不成功”，查找结果给出“空记录”或“空指针”。

查找的方法

查找的方法取决于查找表的结构：

如果查找表中的数据元素之间不存在明显的组织规律，那么就不便于查找。为了提高查找的效率，

可以在查找表中的元素之间人为地附加某种确定的关系→用另外一种结构来表示查找表。(索引)

静态查找

抽象数据类型静态查找表的定义：

ADT StaticSearchTable {

数据对象D：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字, 可唯一标识数据元素。

数据关系R：数据元素同属一个集合。

基本操作P：

Create(&ST, n);

Destroy(&ST);

Search(ST, key);

Traverse(ST, Visit());

} ADT StaticSearchTable

静态查找表的顺序存储结构：

typedef struct {
    keyType key;    // 关键字域
   ... ...        // 其它属性域
} ElemType ;

typedef struct {
    ElemType *elem; // 数据元素存储空间基址, 建表时按实际长度分配，0号单元留空
    int length;     // 表的长度
} SSTable;

顺序表查找

1、基础版

int LocateElem(SqList L, ElemType e)
{
    for (k = 1; k <= L.length; k++)
        if (L.elem[k] == e)
            return k;
    return 0;
}

2、精良版（采用“哨兵”）

int LocateElem(SqList L, ElemType e) {
    L.elem[0] = e;  // 将e放置在表头作为哨兵
    int k = L.length;
    while (L.elem[k] != e) {
        k--;
    }
    return k;  // 如果k为0表示没找到（因为哨兵在0号单元），否则返回找到的位置
}

基础版在每次循环时都要判断 k 是否小于等于 L.length ，这增加了额外的判断开销。采用 “哨兵” 可以改良：在顺序表的表头（0 号单元，前面定义顺序存储结构时 0 号单元留空）放置要查找的元素 e ，然后从后往前遍历（或者从前往后，这里以从后往前为例）。这样可以避免在循环中每次都判断是否越界。

顺序查找的时间性能：

查找算法的平均查找长度(Average Search Length)：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值：
$ASL =\sum_{i=1}^{n}P_{i}C_{i}$
其中:n 为表长， $P_{i}$ 为查找表中第 i 个记录的概率，且 $\sum_{i=1}^{n}P_{i}=1$ ， $C_{i}$ 为找到该记录时，曾和给定值比较过的关键字的个数。

对顺序表而言， $C_{i} = n - i + 1$

$ASL = nP_{1} + (n - 1)P_{2} + \cdots + 2P_{n - 1} + P_{n}$

1）等概率查找： $P_{i}=\frac{1}{n}$ ， $ASL_{ss} = \frac{1}{n}\sum_{i = 1}^{n}(n - i + 1)=\frac{n + 1}{2}$

2）不等概率查找： $ASL_{ss}$ 在 $P_{n}\geq P_{n - 1}\geq\cdots\geq P_{2}\geq P_{1}$ 时取极小值。

有序表的折半查找

int Search_Bin(SSTable ST, KeyType key ) {
    low = 1; high = ST.length;  // 置区间初值
    while (low <= high) {
        mid = (low + high) / 2;
        if (key == ST.elem[mid].key)
            return mid;  // 找到待查元素。随机访问
        else if (key < ST.elem[mid].key)
            high = mid - 1; // 继续在前半区间进行查找
        else low = mid + 1; // 继续在后半区间进行查找
    }
    return 0;        // 顺序表中不存在待查元素
}

一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。假设 $n = 2^h - 1$ 并且查找概率相等，则

$ASL_{bs} = \frac{1}{n}\sum_{i = 1}^{n}C_{i} = \frac{1}{n}\left[\sum_{j = 1}^{h}j\times2^{j - 1}\right] = \frac{n + 1}{n}\log_{2}(n + 1) - 1$

在 n>50 时，可得近似结果：

$ASL_{bs} \approx \log_{2}(n + 1) - 1$

查找更快的方法

1、分块索引

2、倒排索引

3、稠密索引

动态查找 (树表)

特点：表结构本身在查找过程中动态生成。

抽象数据类型动态查找表的定义：

ADT DynamicSearchTable {

数据对象：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。

数据关系：数据元素同属一个集合。

基本操作：

InitDSTable(&DT);

DestroyDSTable(&DT);

SearchDSTable(DT, key);

InsertDSTable(&DT, e);

DeleteDSTable(&T, key);

TraverseDSTable(DT, Visit());

}ADT DynamicSearchTable;

二叉排序树

（上一张有提到，指路：第六章--树和二叉树-CSDN博客）

第七章--查找

查找表

定义

查找表分类

关键字

查找

查找的方法

静态查找

顺序表查找

顺序查找的时间性能：

有序表的折半查找

查找更快的方法

动态查找 (树表)

二叉排序树

待更，，（我才学到这）

网站公告

今日签到

热门文章

最新发布