基本基础概念：
看这就不用去翻PPT了
查找：
根据给定的某个值，在查找表中确定一个与其关键字等于给定值的数据元素（或记录）
关键字：
用来表示一个数据元素（或记录）的某个数据项的值
主关键字：
可以唯一地表示一个记录的关键字【例（如）：准考证号】
次关键字：
用以识别若干记录的关键字【例（如）：姓名为xx，成绩为xx分...】
查找表：（动态静态）
由同一类型的数据元素（或记录）构成的集合。由于集合中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构
静态查找表：
做查询、检索操作的查找表
动态查找表：
做插入、删除操作的查找表
对查找表常进行的几个操作： 查找算法的评价标准：
关键字的平均比较次数，也叫平均查找长度(ASL)
回归程序：
一、顺序查找（线性查找） 前置条件：
#include
using namespace std;
typedef int KeyType;
//数据元素类型定义
struct ElemType
{
KeyType key; //关键字域
//... //其他域
};
struct SSTable
//Sequential Search Table
{
ElemType* R; //表基址
int length; //表长
};
第一种形式：（常规）
int Search_Seq(SSTable ST, KeyType key)
//Seq：顺序
//此查找表为从1开始，0号位置为空，可按需更改
{
//正序
for (int i = 1; i = 1 ; i--)
if (ST.R[i].key == key)
return i;
return 0;
*/
第二种形式：
倒序则遍历顺序相反
int Search_Seq(SSTable ST, KeyType key)
{
//正序
int i;
for (i = 1; ST.R[i].key != key; i++)
{
if (i >= ST.length)
break;
}
if (i > 0)
return i;
else
return 0;
//倒序
/*
int i;
for (i = ST.length; ST.R[i].key != key; i--)
{
if (i 0)
return i;
else
return 0;
*/
第三种形式：
int Search_Seq(SSTable ST, KeyType key)
{
//正序
int i;
for (i = 1 ; ST.R[i].key != key && i 0; i--);
return i;
*/
类似：
第二、三种形式的思想从根本上和第一种没有什么区别
只是第二、三种形式把不相等就进入下一轮循环放到循环的判断语句当中
的 for循环没有执行语句
顺序查找最终最简算法：
以上算法的问题（不足）：
每次循环都需要进行两次比较
那么我们如何将它改进为：每次循环只需要进行一次比较，不需要进行两次比较 呢？
改进操作：
把待查关键字key存入表头（哨兵/监视哨），从后往前逐个比较
办法原理：
免去查找过程中每一步都要检查是否查找完毕的步骤
且保证无论如何函数都会有最终的返回结果
程序实现：
int Search_Seq(SSTable ST, KeyType key)
{
//正序
ST.R[0].key = key;
int i;
for (i = 1; ST.R[i].key != key; i++);
return i;
//倒序
/*
ST.R[0].key = key;
int i;
for (i = ST.length; ST.R[i].key != key; i--);
return i;
*/
当ST.较大时，此改进能使进行一次查找所需的平均时间几乎减少一半
时间空间复杂度：（不算哨兵）
时间复杂度O(n)、空间复杂度O(1)，ASL=(n+1)/2
关于使用【ST.R[ ]】的纠纷问题数据结构与算法导论数据结构与算法导论 数据结构与算法基础（王卓）（25）线性表的查找（1）：顺序查找（线性查找)，详见：
数据结构与算法基础（王卓）（26）线性表的查找（2）：顺序查找（二分查找、分块查找)
中的问题（1）：【ST.R[mid].key】
文章来源:https://blog.csdn.net/Zz_zzzzzzz__/article/details/130084277