当前课程知识点：数据结构 > 第2章 线性表 > 2.2 线性表的顺序实现——顺序表 > 讲解（中）
再看第二个算法：得到第i个元素
getElem，得到线性表L的第i个元素
把这个元素的值放到e里面
需要注意的是
这里的i值表示自然计数
它的最小值是1
最大值是n
当然
也可以用返回值来设计这个操作
比如，不用第3个参数e来接收第i个元素
而用返回值来接收第i个元素，也行
需要注意的是
有可能给定的i值超过了合法的范围
所以，要先判断一下i的合法性
刚才我们说了
i的最小值是应该是1
也就是
最少取第1个元素
最多取最后一个元素
也就是，i的最小值是1
最大值是length
L.length
注意，这里的i是自然计数，不是下标
所以，当i不在这个范围内的时候
直接return
正常情况下
直接找到第i个元素
大家看到，直接访问L.elem[i - 1]
无论找第几个元素
无论i是多少
始终是执行这个表达式
根本不用做循环
这就是随机存取
我们刚才说了
在一段连续存储空间当中，找任何一个元素
无非就是首地址加上一个偏移量
这就是随机存取
它的时间复杂度，因为没有循环
所以就是O(1)
再来看下一个算法：插入。在线性表L的第i个位置之前，插入一个e，注意
这里约定：是在第i个位置之前插入
同样，我们要检查i的合法性
另外
还需要注意
因为，线性表很可能在插入之前已经满了
这时候，应该先追加内存
然后，再去做插入
所以，在插入之前
先要判断线性表是否已经满了
比如
在这个图当中
在线性表的第3个位置，也就是8所在的位置
之前，插入一个元素e
怎么插入呢
应该从8开始，一直到后面的7
3
全都向下移动一个位置
在移动的时候，需要注意，不能先移8
因为，先把8往下移
7会被覆盖掉
所以，先要从最后一个元素an，开始移动
我们先把3往下移动
再移动7，再移动8
最后，原来8的位置
放第3个参数
e
现在，来看它的算法实现
首先
判断i的合法性
i的最小值应该是1
也就是插在最前面
在第1个元素之前插入
因为，我们已经约定了
i表示的是在第i个元素之前插入，i的最大值
如果在已有线性表的末尾，去插入一个值
就相当于，在不存在的第n+1个元素之前，插入一个值
因为，我们约定的是在i的左侧插入
所以，i的最大值是能取到
L.length+1的
如果不在这个范围
我们直接退出
第2个if语句
是极端情况下，在插入线性表之前已经满了，线性表满的时候，很简单
它的长度是等于它的容量的
length是等于size的
这时候，我们要追加存储空间
我们调用的API是C语言里面的
realloc，重分配
realloc这个API
它的参数有2个
第1个，是当前已存在的连续的存储空间
它的首地址，那毫无疑问是L.elem；第2个参数
是新空间的
大小，注意，不是追加的大小
而是新空间的总大小
当前，线性表
它的空间已经是size了
现在，我们要为它追加
LIST_INCREMENT
也就是我们前面定义的第2个宏
它的值，我们当时定义的是10，空间不够的时候
一次追加10个元素所占的空间
再乘上每个元素占的字节数，作为realloc
的第2个参数。realloc的返回值
分配成功的时候，也是返回连续存储空间的首地址
我们要把这个地址赋值给L.elem
需要特别强调的是
realloc这个API
不一定是在旧空间的后面去追加
有的同学可能认为，追加10个，是不是在原来空间的后面去追加
这个不一定，这个完全是无法预期的
有可能是在
完全一段新的空间去追加的，前面这一部分，是原来的
长度
后面才是追加的长度
另外，还需要注意
realloc这个API，在重新分配内存的同时
还会自动地把旧空间里面的内容
比如，原来的10、4、8、7、3这些元素，全部复制到新空间的前一部分
这是realloc自动做的
如果你用别的编程语言
很可能需要自己来完成这部分操作
将旧空间已有的那些元素，复制到新空间相应的位置
realloc
如果空间不够
我们后面放一个if
语句
当内存不够时
我们直接退出
正常情况下
在内存够的情况下
返回的base首地址
我们把它赋值给L.elem
因为，有可能是在一块全新的空间去开辟新的内存
所以，要让L.elem重新指向新开辟的这一段空间的首地址
然后，再将它的长度修改成原来的长度
加上一个增量
也就是size自增
LIST_INCREMENT
从这个for循环开始
就执行真正的插入操作了
刚才讲了
需要先将插入点i指向的元素及其后的元素，全都向下移一个位置
移的时候，必须从an开始移
所以，大家看到，这个for循环
它的第1个表达式，m的取值是L.length - 1
也就是最后一个元素的下标
最后一个移动的元素的下标是
i-1，也就是ai
这个元素，是倒着移的
从后往前移
--m。向后移动一个位置
无非就是将原来下标在m的元素，放到m+1的位置
这个比较好理解
因为是后移
这个for循环执行完毕之后
原来ai的位置，它的值还是8
现在，我们要用第3个参数e来覆盖
ai
也就是i-1下标
我们用e覆盖这个元素
最后，别忘了将表长自增1
因为，已经多了一个元素了
现在，我们来看一下插入算法
它的时间复杂度
最好情况下
是在已有表的最末尾去插入的
an的后面去插一个元素
或者说，在不存在的第n+1个元素之前去插入，i的取值是n+1
这时候，是不需要移动任何元素的
它的时间复杂度
是O(1)
最坏情况下，也就是在表的最前面插入，在a1的前面插入
这时候，i的取值是1
那么，所有的n个元素全部需要向后移动
这是最坏的情况
所以，它的时间复杂度是O(n)
一般的情况，假设i取1到n+1
一共n+1个值的概率是一样的
这时候
我们只需要计算，i取每一个值的移动次数
最后累加，再求一个数学
期望、平均值就行了
我们可以推导出
当i
取n+1的时候
刚才我们说了，这个移动次数是0；当i取n的时候
这个移动次数是多少呢
i指向最后一个元素
那我们只需要移动最后一个元素
那是1
i取到最小值1的时候，要移动的元素个数是n
所以，我们可以总结出规律
如果取到i的时候
这二者相加，永远是等于n+1
所以，移动次数就是n+1-i
那可以推导出
在第i个位置插入的时候
移动的元素个数是n+1-i
最后，i能取到的n+1个值
我们求一下数学期望、平均值就可以了
移动次数就是n/2
当然
我们可以把这个1/2系数丢掉
这就是插入算法
它的时间复杂
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
