【数据结构】查找的基本概念、顺序查找

1. 查找的基本概念

1. 基本概念

查找——在数据集合中寻找满足条件的数据元素的过程称为查找。

查找表（查找结构）——用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成。

关键字——数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

示例：

查找表——学生成绩信息（线性结构、可顺序可链式存储）。

数据元素（记录）——每个学生的信息。

关键字——学号。

2. 对查找表的常见操作

查找符合条件的数据元素。
插入、删除某个数据元素。

示例：

上面我们图片中的成绩表只需进行操作1，这种称为静态查找表。

如果是一个客户订单表，除了进行操作1，还要进行操作2，这种称为动态查找表。

静态查找表仅关注查找速度即可。

动态查找表除了查找速度，也要关注插入/删除操作是否方便实现。

3. 查找算法的评价指标

查找长度——在查找运算中，需要对比关键字的次数称为查找长度。

平均查找长度（ASL,Average Search Length）——所有查找过程中进行关键字的比较次数的平均值。

通常认为查找任何一个元素的概率相同。

一个成功结点的查找长度=自身所在层数。

一个失败结点的查找长度=父节点所在层数。

默认情况下，各种失败情况或成功情况都等概率发生。

树的空链域为结点数+1，即n个成功结点，n+1个失败结点。

ASL的数量级反应了查找算法的时间复杂度。

评价一个查找算法的效率时，通常考虑查找成功/查找失败两种情况的ASL。

2. 顺序查找

1. 算法思想

顺序查找又称“线性查找”，它对于顺序表和链表都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，则通过指针来依次扫描每个元素。

算法思想：从头到尾挨个查找（反过来也可以）。

2. 代码实现

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){
        // 查找成功，则返回元素下标；查找失败，则返回-1
        return i==ST.TableLen?-1:i;
    }
}

哨兵的实现方法：

typedef struct{  // 查找表的数据结构（顺序表）
    ElemType *elem;  // 动态数据基址
    int TableLen;  // 表的长度
}SSTable;

// 顺序查找
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;  // 0号位置存“哨兵”
    int i;
    for(i=ST.TableLen;ST.elem[i]!=key;--i){  // 从后往前查找
        // 查找成功，则返回元素下标；查找失败，则返回0
        return i;
    }
}