数据结构(7.2_1)——顺序查找
顺序查找，又叫"线性查找"，通常用于线性表（或者顺序表和链表）。
算法思想：从头到尾全部查找出来（或者反过来也OK）
顺序查找的实现
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;//"哨兵"
int i;
for (i = ST.TableLen; ST.elem[i] != key;--i);//从后往前找
return i;//查找成功，则返回元素下标；查找失败，则返回0
}
查找成功的情况：
查找失败的情况：
”哨兵“方法查找的优点：无需判断是否越界，效率更高
查找效率分析
默认每个元素的查找概率为1/n
顺序查找的优化(对有序表)
用查找判定树分析ASL
一个成功结点的查找长度=自身所在层数
一个失败结点的查找长度=其父节点所在层数
默认情况下，各种失败情况或成功情况都等概率发生
顺序查找的优化(被查概率不相等)
将概率大的元素优先放到前面(使用降序排列)
总结
