数据结构：查找算法与二叉排序树详解

查找

基本概念

• 查找：在数据集合中，寻找满足特定条件的元素的过程。
• 查找表：由同一类型的数据元素构成的集合。
• 关键字：唯一标识。例如学号，其他信息可能重复，但关键字通常不重复。

查找表可以是表格形式或图的形式。

常见操作

• 静态查找表：只进行查找操作。
• 动态查找表：支持查找、插入和删除操作。

评价指标

• 查找长度：对比次数（与关键字对比）。
• 平均查找长度 (ASL)：对比次数的平均值。

查找成功时，ASL = Σ(层数 × 该层节点个数) / 总节点数。 查找失败时，对应到外部节点（空叶子节点）的层数计算。

顺序查找

算法思想

从头到尾依次遍历，无特殊技巧。

算法实现

普通实现

// 定义顺序表的数据结构
typedef struct {
    ElemType *elem; // 指向动态数组的基地址
    int TableLen;   // 表中当前元素的个数
} SSTable;

// 顺序查找函数
int Search_Seq(SSTable ST, ElemType key) {
    int i;
    for (i = 0; i < ST.TableLen && ST.elem[i] != key; ++i);
    return i == ST.TableLen ? -1 : i;
}

哨兵实现

在下标为 0 的位置存入待查关键字作为'哨兵'，避免循环中的越界判断。

int Search_Seq(SSTable ST, ElemType key) {
    ST.elem[0] = key; // 设置哨兵
    int i;
    for (i = ST.TableLen; ST.elem[i] != key; --i);
     i;
}