大家好
数据结构与算法
这一讲我们继续学习第二章
线性表的内容
今天我们学习顺序表
顺序表呢
也通常称为向量
是用数组来实现的
我们一般讨论的简单线性表
它的元素都是同类型的
也就是说它的长度也整齐划一
在我们的顺序表实现里面呢
我们保留了这样的性质
因此我们可以用一维数组
来存储这些数据元素
它的存储结构呢
就完整的保留了原来的逻辑结构
因此我们在查找顺序表里面
任何一个元素位置的时候
可以非常快捷的定位到
我们这个下标位
所指向的这个元素
因此它就是一个随机存储的
数据结构
我们来看
计算顺序表里面
某一个元素的存储地址的
一个公式
知道了这样的一个数组的变量以后
我们应该知道
它的一个始地址
也就是说下标为0的
那个元素的地址
同时我们也知道
它每一个元素的存储的长度
第i个数据呢
那就是我们的下标0的始地址
然后再加上我们的数组元素长度c
再乘以i
然后就得到了我们相应的
这样一个元素的位置
我们来看顺序表的类定义
它基本上是继承了
我们线性表里面的那个类定义模板
有一些区别呢就是
首先我们要实现一个数组
然后呢这个数组呢
是规定了一个最大的长度
这个长度呢可能会大于
我们当前的这个数据元素的个数
当前的元素个数
当然也是非常重要的一个指标
只有在下标0到当前元素个数
这样的长度的这个区间
是我们逻辑上有效的
这个区间
在current length
当前元素长度
到max length
就是我们数组最大的存储长度
那一个区间段呢
是预留的这样的存储空间
另外呢
有一个当前的元素位置
这也非常重要
在线性表里面
我们往往都是先定位再操作
在我们顺序表里面呢
当前位置往往就是表现为
我们当前的下标的数值
其他的这些函数接口呢
就跟我们的线性表是一样的
其实在数据结构里面
ADT的定义
它就有这么一个好处
我们定义了线性表的统一的
这样的类模板接口以后呢
那我们的顺序实现也好
或者是链式实现也好
它的函数接口都一样
因此在构造上一层的
这些应用的时候
完全可以是保留一样的
这种调用的方式
只是修改相应的
这种头文件的引用就可以了
我们再来看顺序表的实现
这里我们讨论它的插入和删除操作
其他的操作呢
在我们课程网站上
有源代码包
大家可以先思考一下
然后再看一下这些代码的实现
顺序表的插入
我们要使得插入了以后
这样的一个新的逻辑结构
还能够完整的表达在
它的存储结构中
因此我们就需要
在这个当前的代插入位置之后
把相应的这些数据元素呢往下移
移出一个空位
才能够把我们这个当前的元素呢
填入到我们所移出的空位来
我们来看顺序表插入的算法
首先就是我们有当前位置
和代插入的这样一个值
作为参数传进来
然后呢我们需要判断一下
这个表里面的当前元素个数
是不是已经达到了
我们表的最大的存储的限制
如果是这样呢
就是表已经满了
我们不能再插入任何元素
另外呢我们还要看
当前代插入的位置
它是不是在我们这个表的
逻辑的有效个数里面
如果是说超出了我们当前的
顺序表里面有效的元素个数
这样一个范围
我们也是不允许插入的
这两种情况
都是返回假
如果是一个有效的当前位置
而且这个表也没满
我们可以插入
那我们就从表尾
到当前位置呢
进行一个循环
依次从表尾开始
把这个表尾的元素
往后面再移一个
然后上面的这个元素
就接着填入我们刚才移走的
这个空间
一直操作到当前位置
这个当前位置也是空了
那我们就可以填入
代插入的这个元素值
整体来说呢
我们这个线性表
它的规模是增加了1
而且我们的插入是成功的返回真
我们再来看顺序表的删除
删除也是类似
它是插入的逆操作
为了保持这个逻辑的序
在删掉当前这个元素之后
我们从当前元素的下一个元素
一直到表尾
这些元素呢
要逐个的往上移
然后就是一直移到
我们这个表尾为止
当前的这个线性表
它的元素个数呢就减少了1
我们来看一下顺序表的删除算法
首先传入代删除的下标位置p
我们首先要检查
当前这个表的表长
是不是大于0
如果小于等于0
那就是空表
不允许删除
接着检查下标p
是不是在顺序表的
合理的元素范围之内
如果超出了这个下标范围
那也返回假
对于合法的下标范围的p
那我们从当前这个p开始
把后面的元素呢
逐个往前填充
一直到表尾
表的实际长度呢
就减少了1
而且删除以后
顺序表它还保持了
紧密的存储的特性
也就是说它的存储
保留了它的逻辑的顺序关系
我们来看一下
顺序表插入和删除算法的代价
在顺序表里面
插入删除运算
最主要的是其中元素的移动
对于插入算法来说呢
从最后一个位置
到当前代插的这个位置
我们是顺序往下移的
这个移动呢
是要有n-i次
对于删除来说呢
从当前的待删除的下标位置i
我们顺序的把后面的元素
往前移动
一直到顺序表的末尾
需要移动的元素个数是n-i-1
假设在位置i上
插入和删除的概率
分别是pi和pi’
那插入的平均移动次数呢
就是从0到n求和
这个求和的项呢
就是（n-i）pi
这是因为我们插入的位置
除了从当前0到n-1这几个元素
它们之前的位置都可以插入以外
其实n-1之后这个位置
也是可以插入的
所以总共有n+1次求和
删除算法呢
它的平均移动次数呢
就是n-i-1乘以pi’
从0到n-1求和总共是n次
因为对于删除来说
当前这个数组里面
正好有n个元素
我们只能对当前的n个元素
进行删除的操作
如果在顺序表中的每个位置上
插入和删除的概率呢
是等概率的
那也就是pi=1/n+1
而pi’=1/n
代入刚才的公式
就可以算出平均情况下
如果等概率分布
那插入算法
它所需要移动的元素个数呢
是n/2
而删除算法呢
它所需要移动的元素个数呢
是n-1/2
从大O的量级来说它都是一样的
也就是说时间代价都是大On
最后给大家留两个思考题
在顺序表中
插入和删除操作
各需要考虑哪些问题
另外顺序表有哪些优缺点呢
谢谢大家