当前课程知识点：数据结构 > 第2章 线性表 > 2.2 线性表的顺序实现——顺序表 > 讲解（下）
继续来看顺序表的删除操作
现在，我们要删除顺序表
L当中的第i个元素
并且，把被删除的元素放在e当中
凡是涉及到位置的参数
我们通常都要检查它的合法性
既然是删除
被删除点后面的所有元素都要向前移动
具体来说
应该先移动第i+1个元素
比如，在图当中，i等于3的时候，我们应该先移动它的下一个元素7
把它移到
8的位置
不应该先移动3
如果先移动3，会把7覆盖掉
现在，我们来看具体的实现
这个if语句
很明显是判断i的合法性
i的最小值是1
也就是删除第一个元素
i的最大值是L.length
也就是删除最后一个元素
如果不在这个范围
我们直接返回
然后，把被删除的元素ai，也就是下标为i-1的那个元素
把它放到第3个参数e里面
紧接着
用一个for循环，把第i+1个元素及其后的所有元素，都向前移动
刚才说过，移动的时候，要移动第i+1个元素
所以大家看到，这里的循环
变量m，它的值是从i开始的
最后一个值，是L.length-1
我们向前移动
原来下标为i的元素，放到下标为i-1的位置
同时
别忘了将表长减一
因为删除了一个元素
现在，我们来分析一下删除操作
它的时间复杂度
最好的情况下，也就是删除的元素是最后一个元素
这时候
是不需要移动元素的
那么，循环执行的次数是0
我们把它记成O(1)
这是最好的情况
最坏的情况
删除的是第1个元素
这时候，循环会执行n-1次
也就是说，从第2个元素开始
一直到第n个元素，都要向前移动
移动了
n-1个元素
所以，它的时间复杂度
我们记成O(n)。那一般的情况呢
同样
我们求一下，i取每一个值
它的期望就可以了
我们可以总结一下
当i等于
1的时候
移动的是n-1个元素
当i是2的时候
比如，这里i指向4，我们移动的是
n-2个元素
可见
i取最后一个值n的时候
我们移动的是0个元素
那么，i和移动次数相加
是恒等于n的
所以，我们可以总结出，移动次数
应该是n-i
最后
将i能取到的n个值
累加
然后，求一个平均值
就是
(n-1)/2
现在再来看，查找元素e的首次出现位置
具体来说
我们在顺序表L当中，去找一个值为e的元素
然后，把找到的这个元素
它的位置放在i里面
注意，这里的i
是表示自然计数
当然
也可以设计为，将e在L当中出现的位置
作为函数的返回值
我们采用的算法思想很简单
就是从头到尾，依次与顺序表
L当中的每一个元素进行比较
找到了e
就返回它的位置
如果没有找到
我们就返回一个特殊的值
在图当中
我们去找
值为8的元素
i在初始状态
应该指向第1个元素
一直向后找
找到了8
这时候，返回i的值就可以了
右边这个图
是找
值为9的元素
在这个表当中，没有值为9的元素
最后，循环变量i会超过表长
我们在写算法的时候，需要注意一下
也就是，当e不存在的时候
要怎么处理
现在来看算法的实现
首先
设一个循环计数器
它从1开始
因为最终，我们修改的i值，它是自然计数
如果找到了
最小值应该是1
紧接着
有一个while循环
这个while循环有两个条件
第一个条件
是
i小于等于表长
并且
ai
不等于e
因为，ai在下标i-1的位置
这两个条件表示的是
没有找到e
当前，还没有找到e，并且
表还没有找完
只有在这两个条件同时成立的情况下，才有继续找下去的意义
这时候，i++，往下找
当这个循环结束的时候
实际上有两种情况
换句话说
当程序执行到这个if语句的时候
是因为上面的while循环结束了
上面的while循环结束了
实际上有两种情况
因为，在数学上
我们知道
两个条件与
不成立了
while循环才结束
那不成立
A && B
它的非
应该是A非 ||
B非
先看第一个条件
第一个条件不成立，i <= L.length
那就是 i > L.length
i > L.length
说明，前面的循环
把所有的表元素都找完了
还没有找到e
这时候，就说明e在L当中不存在
直接返回一个特殊的值
比如0，就可以了
我们将i修改成0
因为前面说过，用来描述位置
的最小值，应该是第1个
将i修改成0
就意味着未找到
当然，也可以用特殊的值，比如-1这样的值
其他的情况，就说明e是存在的
e是存在的
因为，在循环当中已经修改了i
而且，我们用第3个参数
来作为e在L当中出现的位置
所以，在这个if语句后面，什么都没有了
也就是，这个条件不成立了
说明，i-1这个位置的元素
等于e
现在，我们来分析一下，查找算法的时间复杂度
当e出现在表头的时候
也就是，要找的元素是a1
这时候，循环只执行了1次，时间复杂度
是O(1)；当e不存在的时候
我们找完了线性表
L当中所有的元素
所有的n个元素
都没有找到，循环执行了n次
所以，时间复杂度是O(n)
在e存在的情况下
查找的平均时间复杂度是多少呢
这时候，我们也是求i取每一个值的时候
比较次数的数学期望，就可以了
通过分析
很容易找出
i
取1的时候
循环比较了1次
i取2的时候，比较2次；很明显
i取i的时候
比较了i次
这是比较的次数
所以
最后就是Σi
i取1到n累加
然后，取一个平均值就可以了
最后就是(n+1)/2
现在，我们来总结一下顺序表
的优缺点
它的优点是实现相对简单
因为，直接使用了C的数组语法
支持随机存取。刚才已经说过了
随机存取是顺序存储的一个优点
也是它的一个特性
只有顺序存储才支持随机存取
我们找
任何一个元素
不需要做循环
直接取下标就可以了
缺点也很明显
大家看到，刚才的插入算法、删除算法都需要移动大量的元素
特别是插入点
删除点在比较靠前的位置的时候
这时候，移动的元素个数是比较多的
另外
它需要预先分配内存
可能会造成空间的浪费
前面讲初始化算法的时候
一次分配了LIST_INIT_SIZE
当时我们定义的是100
后面空间不够的时候
我们追加了10个
如果每次只追加1个元素的空间
可能需要频繁地追加内存
所以，我们一次追加了10个
但是，追加了10个
很有可能用不完
包括第一次分配的初始大小100个，很有可能也用不完
因为要预先分配空间
可能造成浪费
解决方案
就是我们下一节要讲的链表
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
