数据结构(7.2_1)——序次查找

序次查找，又叫"线性查找"，通常用于线性表（大概序次表和链表）。
算法头脑：重新至尾全部查找出来（大概反过来也OK）
序次查找的实现

2. typedef struct {//查找表的数据结构(顺序表)
3.         ElemType* elem;//动态数组地址
4.         int TableLen;//表的长度
5. }SSTable;
6. //顺序查找
7. int Search_Seq(SSTable ST, ElemType key) {
8.         int i;
9.         for (i = 0; i < ST.TableLen && ST.elem[i]!= key; ++i);
10.         //查找成功，则返回下标；查找失败，则返回-1
11.         return i == ST.TableLen ? -1 : i;
12. }

复制代码

查找乐成：

 
查找失败：

 
 
序次查找的实现（哨兵）

2. typedef struct {//查找表的数据结构(顺序表)
3.         ElemType* elem;//动态数组地址
4.         int TableLen;//表的长度
5. }SSTable;
6. //顺序查找
7. int Search_Seq(SSTable ST, ElemType key) {
8.         ST.elem[0] = key;//"哨兵"
9.         int i;
10.         for (i = ST.TableLen; ST.elem[i] != key;--i);//从后往前找
11.         return i;//查找成功，则返回元素下标；查找失败，则返回0
12. }

复制代码

查找乐成的环境：

 查找失败的环境：

 
”哨兵“方法查找的优点：无需判断是否越界，服从更高
查找服从分析

默认每个元素的查找概率为1/n

 
序次查找的优化(对有序表) 

用查找判断树分析ASL

一个乐成结点的查找长度=自身所在层数
一个失败结点的查找长度=其父节点所在层数
默认环境下，各种失败环境或乐成环境都等概率发生

 
序次查找的优化(被查概率不相称) 

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

总结