数据结构(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

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

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

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

顺序查找的优化(被查概率不相等) 

将概率大的元素优先放到前面(使用降序排列)

总结