一.顺序查找的算法思想：
1.概念：
线性表分为顺序储存和链式存储，但无论是哪种存储方式，顺序查找都是适用的。
2.实例：
以上述图片为例，比如要查找关键字43，只需要从线性表的第一个元素开始，依次往后找，最终找到了43，如下图：
二.顺序查找的实现（从头到尾）：
1.代码实现：
上述图片中的代码解读：
查找表采用顺序表实现，即数据元素采用顺序存储（注：查找表也可以采用单链表、双链表等链式存储，只是Search_Seq函数里的for循环和return语句会有差别）
结构体SSTable采用了动态数组（类似Java的ArrayList集合，动态数组不是链表，动态数组在CSDN收藏里有详解）的方式，其中elem指针会指向动态数组的起始地址，初始化时用malloc函数申请一片连续的存储空间，然后用elem指针指向malloc函数分配的这片空间的首地址；TableLen代表顺序表的长度
Search_Seq函数的返回值是int型，形参SSTable ST是查找表（也就是本例的顺序表），ElemType key是要查找的元素（key的类型ElemType因题而异）
Search_Seq函数里的for循环，i为顺序表SSTable ST的索引，ST.TableLen是顺序表的长度，ST.elem[i]!=key表示当前i索引上的元素不等于要查找的元素
Search_Seq函数里的for循环中，索引i从0开始，如果i<ST.TableLen&&ST.elem[i]!=key即i没有越界且没有找到要查找的元素，这里for循环没有循环体，那么就执行++i即索引后移，当i越界或者找到了要找的元素就跳出for循环
return i==ST.TableLen?-1:i;，指的是如果索引i等于ST.TableLen即顺序表的长度，那么就返回-1，代表全部遍历完顺序表都没有找到；反之返回i，代表找到了要查找的元素
2.例一：
以上述图片为例，假设顺序表SSTable ST中存储了11个元素，那么TableLen的值为11。
现在要查找关键字43，调用Search_Seq函数实现顺序查找，如下图：
如上图，i初始为0，即从起始位置出发，不断往后找，当i为8时，最终找到了关键字43，跳出for循环，i的值为8，最终Search_Seq函数返回8，如下图：
3.例二：
以上述图片为例，假设顺序表SSTable ST中存储了11个元素，那么TableLen的值为11。
现在要查找关键字66，调用Search_Seq函数实现顺序查找，
i初始为0，即从起始位置出发，不断往后找，由图可知一直扫描到最后即i越界都没有找到关键字66，此时会跳出for循环，由于此时i等于TableLen的值，说明始终没有找到要找的数据元素66，因此Search_Seq函数返回-1，表示查找失败，如下图：
三.顺序查找的实现（从尾到头）：
1.代码实现：
上述图片中的代码解读：
查找表采用顺序表实现，即数据元素采用顺序存储（注：查找表也可以采用单链表、双链表等链式存储，只是Search_Seq函数里的for循环和return语句会有差别）
结构体SSTable采用了动态数组（类似Java的ArrayList集合，动态数组不是链表，动态数组在CSDN收藏里有详解）的方式，其中elem指针会指向动态数组的起始地址，初始化时用malloc函数申请一片连续的存储空间，然后用elem指针指向malloc函数分配的这片空间的首地址；TableLen代表顺序表的长度
Search_Seq函数的返回值是int型，形参SSTable ST是查找表（也就是本例的顺序表），ElemType key是要查找的元素（key的类型ElemType因题而异）
Search_Seq函数里的ST.elem[0]=key;是"哨兵"（"哨兵"名称的由来：当索引i为0时，就不能再往前移动了，相当于终止循环），这里之所以把0索引上的元素赋值为要查找的元素，是因为此时顺序表中的数据是从1索引开始存，如果顺序表中没有要查找的元素，会从1索引越界到0索引（因为是"从尾到头"），此时0索引上就是要查找的元素key，会使for循环结束，此时i为0，因此当i为0时表示查找失败，此外查找成功，如下图：
上述图片中的代码解读：
Search_Seq函数里的for循环，i为顺序表SSTable ST的索引，ST.TableLen是顺序表的长度，ST.elem[i]!=key表示当前i索引上的元素不等于要查找的元素
Search_Seq函数里的for循环中，索引i从ST.TableLen开始（因为此时顺序表中的数据从1索引开始存），如果ST.elem[i]!=key即没有找到要查找的元素，这里for循环没有循环体，那么就执行--i即索引前移，当ST.elem[i]等于key就跳出for循环
return i;，返回0代表查找失败，此外查找成功
2.例一：
以上述图片为例，假设顺序表SSTable ST中存储了11个元素，那么TableLen的值为11（从1索引开始添加11个元素后顺序表的长度ST.TableLen为11，虽然之后会在顺序表的0索引上添加元素，但添加0索引上的元素后并没有把顺序表的长度加1，因此顺序表从0索引开始虽然有12个元素，但实际在代码中长度ST.TableLen为11）。
现在要查找关键字16，调用Search_Seq函数实现顺序查找，其中会把关键字16放到0索引上，
i初始为ST.TableLen，即从末尾位置出发（注：此时顺序表从1索引开始存数据元素），不断往前找，如果当前指向的元素的值与key不同，就会把i前移，当i移动到5索引上时，找到了关键字16，此时跳出for循环，Search_Seq函数返回5，表示查找成功，如下图：
3.例二：
以上述图片为例，假设顺序表SSTable ST中存储了11个元素，那么TableLen的值为11（从1索引开始添加11个元素后顺序表的长度ST.TableLen为11，虽然之后会在顺序表的0索引上添加元素，但添加0索引上的元素后并没有把顺序表的长度加1，因此顺序表从0索引开始虽然有12个元素，但实际在代码中长度ST.TableLen为11）。
现在要查找关键字66，调用Search_Seq函数实现顺序查找，其中会把关键字66放到0索引上，
i初始为ST.TableLen，即从末尾位置出发（注：此时顺序表从1索引开始存数据元素），不断往前找，如果当前指向的元素的值与key不同，就会把i前移，由图可知顺序表中没有关键字66，直到i为0时才出现关键字66，此时跳出for循环，Search_Seq函数返回0，表示查找失败，如下图：
四.顺序查找的实现：从头到尾 V.S. 从尾到头
"从头到尾"的代码，如下图：
"从尾到头"的代码，如下图：
"从头到尾"和"从尾到头"的代码主要差距在Search_Seq函数里的for循环上，
"从头到尾"的代码中执行for循环的条件有i<ST.TableLen&&ST.elem[i]!=key，
"从尾到头"的代码中执行for循环的条件只有ST.elem[i]!=key，
相比之下"从尾到头"的代码中执行for循环的条件更加高效，只需要判断当前i索引上的元素是否等于要查找的元素，因为无论这个查找表中原来有没有要查找的数据元素，只要i一直前移，当i减为0时，也能正常跳出for循环，所以这么做的好处在于不需要判断i索引是否越界，执行效率更高，如下图：
五.顺序查找的效率分析：
通常要计算查找算法的ASL来评估查找算法的效率，
ASL又分为查找成功和查找失败两种情况。
如上图，以顺序查找中"从尾到头"的查找算法为例，假设查找表中共有n个关键字（虽然0索引上有关键字，但不属于查找表中，因为此时查找表从1索引开始存储->从1索引开始的话查找表中有n个关键字，从0索引开始的话有n+1个关键字），
1.查找成功的情况：
假设查找任何一个关键字的概率都相同，因此查找每一个关键字的概率Pi都为1/n，
如果要查找顺序表中倒数第一个关键字37，那么所需要对比的关键字次数Ci就是1，所以求ASL的第一项是1/n * 1，
如果要查找顺序表中倒数第二个关键字41，那么所需要对比的关键字次数Ci就是2，所以求ASL的第二项是1/n * 2，
以此类推，总共有n个关键字（长度为n的查找表，这里0索引上的关键字不属于查找表中的关键字，所以不需要做任何处理），
如果要查找顺序表中倒数第n个关键字，那么所需要对比的关键字次数Ci就是n，所以求ASL的第n项是1/n * n，
那么查找成功的ASL=1/n * 1 + 1/n * 2 + ... + 1/n * n = (1+2+...+n) * 1/n=(n+1)/2，数量级为O( (n+1)/2 )，等价于O(n)。
2.查找失败的情况：
查找失败意味着整个查找表中都没有所需的关键字，查找失败只有一种情况，
查找失败是最终的结果，每个关键字都必须以相同的概率1遍历一遍才能得出找不到所需的关键字，因此查找概率Pi为1，
查找的过程需要从倒数第一个元素开始依次往前找，把所有的元素都依次对比一遍，直到对比到0号元素，才得知没有所需的关键字，所以查找失败的情况下，总共需要对比n+1次关键字，即查找长度Ci为n+1，
所以ASL=1 * (n+1)=n+1，数量级为O(n+1)，等价于O(n)。
六.顺序查找的优化（对有序表）：
如果查找表中的关键字（即数据元素）是有序的，即关键字是递增或者递减排序，
以上述图片为例，比如要查找关键字21，由图可知查找表中没有21，由于查找表中的数据元素是递增排序的，如果采用"从头到尾"的查找方式，当扫描到29的时候就可以停止，因为29大于21，29之后的关键字只会比21更大，
因此顺序查找如果用于有序表，可以进行优化，提高效率。
上述图片中左下角的是该有序表的查找判定树，
此时要查找的关键字是21，从根结点7开始，
21是大于7的，所以进入右子树13，接下来对比13，
21是大于13的，所以进入右子树19，接下来对比19，
21是大于19的，所以进入右子树29，接下来对比29，
到这一步发现21小于29，所以进入左子树，相当于要找的目标关键字21是落在区间(19,29)内，因此查找失败。
如上图，假设有序表中有n个关键字，那么总共会出现n+1种查找失败的情况，因为由查找判定树可知共有n+1个查找失败的结点（紫色的结点），
所以在查找失败的情况下计算ASL(平均查找长度)，
假设出现这n+1种查找失败的情况的概率都是相等的，因此
如果要查找的关键字落在了第一个区间(负无穷,7)，发生这种情况的查找概率Pi为1/(n+1)，且需要对比一次关键字，所以查找长度Ci为1，所以求ASL的第一项为1/(n+1) * 1，
如果要查找的关键字落在了第二个区间(7,13)，发生这种情况的查找概率Pi为1/(n+1)，且需要对比两次关键字，所以查找长度Ci为2，所以求ASL的第二项为1/(n+1) * 2，
以此类推，
如果要查找的关键字落在了第六个区间(37,43)，发生这种情况的查找概率Pi为1/(n+1)，且需要对比六次关键字，所以查找长度Ci为6，所以求ASL的第六项为1/(n+1) * 6，
但要注意的是，要查找的关键字还可能落在了第七个区间(43,正无穷)，发生这种情况的查找概率Pi为1/(n+1)，且需要对比六次关键字，所以查找长度Ci为6，所以求ASL的第七项为1/(n+1) * 6，
因此，如果有序表中有n个关键字，在查找失败的情况下计算ASL(平均查找长度)需要n+1项，第n项和第n+1项是相等的，因为是针对于同一个关键字（且是有序表中的最后一个关键字）的左右区间，本例中求ASL的第n项为1/(n+1) * n，求ASL的第n+1项也为1/(n+1) * n，
所以把这n+1种失败的情况都考虑进去，就可以得到查找失败情况下的ASL=1/(n+1) * 1 + 1/(n+1) * 2 + ... + 1/(n+1) * n + 1/(n+1) * n = (1+2+...+n+n) * 1/(n+1) = n * 1/2 + n * (n+1)。
七.用查找判定树分析ASL：
要体会如何画查找判定树，因为根据查找判定树可以更容易的分析ASL。
如上图，把紫色的方形结点称为"失败结点"，把蓝色的圆形结点称为"成功结点"，
如果要查找的关键字在"成功结点"中，那么查找的该关键字所付出的查找长度（即关键字的对比次数）等于存储该关键字的结点所在的层数->比如要查找19，那么总共需要3次对比，因此查找长度Ci为3；
查找判定树里的"失败结点"对应的各种有可能出现的查找失败的情况，对于每一个"失败结点"的查找长度，是等于"失败结点"的父结点所在层数->比如要查找的关键字落在了(13,19)，那么直到确定查找失败，总共需要对比3次关键字，因此查找长度Ci为3。
八.顺序查找的优化（被查概率不相等）：
以上述图片为例，如果各个关键字被查找的概率不相等的话，其实可以把被查找的概率更大的关键字放在靠前的位置，这么做可以使当查找成功的情况下，平均查找长度即ASL能够更进一步地缩短，因为被查找的概率更大的关键字在前面，就意味着对比次数Ci会更小（这里的查找概率Pi是已经确定的）。
如果按照"被查找的概率更大的关键字放在靠前的位置"的策略来给各个数据进行排序的话，那这些关键字的顺序又可能产生乱序，所以该策略可以提高查找成功时的平均查找长度，但是对于查找失败的情况又是只能从头扫到尾，一直扫到最后一个元素才可以确定到底是否查找失败。
因此什么样的优化方式更好，还得结合实际的场景->
如果实际应用当中查找成功的情况更多，那么"被查找的概率更大的关键字放在靠前的位置"的策略会更好；
如果实际应用当中查找失败的情况更多，那么"把查找表中的关键字进行有序排序后再进行查找"的策略会更好。
九.总结：
