当前课程知识点：数据结构 > 第7章 查找 > 7.2 静态查找表 > 讲解（上）
同学们好，本节，我们来学习静态查找表
第一类查找算法，顺序查找
需要注意，我们前面讲过顺序表，顺序表
是指元素在内存当中，以顺序方式存储
而这里的顺序查找，跟元素的存储方式，是没有关系的
它表示的是一种查找思想
顺序查找又称为逐个查找
或者说，挨个查找，它的本质
是从查找表的一端开始
逐个取出下一元素，与给定的关键字k进行比较
如果找到了
就返回元素所在的位置
如果在查找的过程当中
一直到表的另一端，都没有找到给定的关键字k
这时候，就说明查找不成功
顺序查找适用于线性结构
注意，我们讲到线性结构
实际上是一种逻辑结构
它跟线性结构在内存当中的存储方式，是没有关系的
换句话说
顺序查找既适合于以顺序方式存储的线性结构
也适合于以链式方式存储的线性结构
因为，无论是顺序结构还是链式结构
总能找到第一个元素
总能找到当前元素的下一个元素
现在，我们给出顺序查找它的算法实现
我们在静态查找表ST当中，去找关键字等于k的记录它的位置
首先，我们给出了一个循环变量i
将来，i作为循环变量，同时
也作为第i个元素
它的位置
紧接着，我们将要查找的关键字，放到下标为0的位置
刚才，我们已经约定了，elem这个数组下标为0的位置
不存放元素
我们在初始化ST这个静态查找表的时候
需要注意，有n个元素
你要有意地为数组增加一个容量
也就是说，长度为n的数组，你为它分配n+1个元素所占的空间
紧接着
我们进入查找的过程
循环变量i，初始值是length
也就是，第n个元素它的下标
i--
说明，我们查找的方向，是从右到左
比如，5个元素
5、3、1、2、4，它们的下标
刚才已经说了，就是1、2、3、4、5，下标为0的
这个位置，我们不存放元素
现在，5个元素
要为它们分配6个元素
所占的空间
循环继续执行的条件，是第i个元素
它的关键字，不等于给定的关键字k
只有在这个条件成立的情况下
我们才有必要向左去找
如果我们要找的k，假设是2
那么，i值从5开始，不相等
向左减，i被减到了4
这时候，和2是相等的
那我们直接返回i，就可以了
大家注意到，这个for循环
它的循环体比较奇怪
是一个空语句
因为，我们在循环的第三个表达式当中
实际上，已经完成了要做的操作
也就是，当没有找到给定的关键字
k的时候
i向左去减
因为，最终我们返回的值，就是第几个元素，就是关键字等于k的那个元素
它的位置
现在，我们再来看
查找一个不存在的元素
那么，i一直向左减
i会不会等于-1呢
我们知道，下标是不能取到-1的
因为这时候，下标就越界了
这个for循环
它的第二个表达式，并没有写上i大于等于0
这个条件
为什么没有写呢
这是因为，我们将要找的k，这一行，放到了下标为0的位置
也就是，要找的6，放到了0这个位置
它实际上就可以做一个监视哨
它在这里，做一个拦截的工作
即使我们要找的东西
不存在，向左找
一直向左找
i一直减
当i被减到0的时候
这个条件一定不成立
也就是相等了
循环就退出了
所以，我们没必要再放上这个条件
这个算法
它的平均查找长度是多少呢
根据我们刚才的定义
Pi一般是等概率的
那就是，查找每一个元素，经历的比较次数之和，除以一个n
做一个算术均值就可以了
通过分析
我们很容易发现
找第n个元素(最后一个元素)
经历的比较次数
应该是1次，注意，ASL是指查找成功的情况下，我们找4
只需要经历1次比较
我们找倒数第二个元素
也就是第n-1个元素
这时候，经历2次比较
找第1个元素，很明显，经历n次比较
所以，最后就是
这样一个式子，(n+1)/2
如果查找不成功呢
假设，我们找这里的6
查找不成功
一定会经历n+1次比较
所以，查找不成功
它的平均查找长度，总是n+1
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
