大家好
我们学习数据结构与算法
第二章线性表
最后的内容
我们对顺序表和链表
进行一下比较
顺序表 因为它是用数组来实现的
它没有指针
所以在操作上呢
是非常便捷的
而且在顺序表里面
我们指定一个序
也就是它的下标值
然后再来读取相应的元素
是非常方便的
而链表呢
它的优点就是
我不需要事先指定
这个线性表的大小
我根据需要呢
动态的去生成这个结点
这样的话呢
它非常适合于动态插入删除的情况
因此顺序表它更适合于
比较静态的场景
而链表适合于比较动态的应用环境
我们再来看顺序表和链表
它们在时间和空间上头的
一些特点
对于顺序表来说呢
它的插入和删除
为了保持存储和逻辑关系的一致
我们大概需要平均情况下
移动一半左右的元素
因此它的代价是大O（n）的
但是在查找上它又非常便捷
因此是大O（1）的
顺序表它需要
一次申请固定长度的连续数组
这种情况
我们在有些时候
你申请特别大的数组的时候
系统没有连续的空间了
可能会失败
还有呢就是
如果这个顺序表
它的数组元素很满的时候
因为我们不需要额外的
这样的空间来维护顺序表里面
它的元素之间的逻辑关系
因此呢
它的结构性开销呢
是很低的
它的存储密度是很高的
链表呢
它的插入和删除操作
从这样单一的算法来说
也就是定位了以后
我只需要对这个当前待插入
或者是待删除这的元素的位置
进行某一些局部的
指针的修改
是非常快捷的
是大O（1）的时间
但是这个定位操作就非常麻烦
我要在链表里面找第i个元素
往往是要从表头开始逐个去找
也要是平均情况下
遍历这个链表里面
一半左右的元素
因此它的查找第i个元素的代价
是大O（n）的
我们把这个定位再加上操作
合起来看呢
顺序表和链表
都是大O（n）的时间
而链表在存储上呢
它利用了指针的这么一个优势
因此呢可以动态的根据需要
来申请或者是释放空间
它的存储的效率呢
不是那么高
没有顺序表高
它每一个结点都有结构性的开销
要维护它下一个元素
就是next域
同时还要维护上一个元素prev域
这样的结构的内容
所以呢它的存储密度呢
是比顺序表要低的
我们来看一下顺序表和链表
它们存储密度的一个估算
我假设当前有n个有效的元素
而指针的开销是P
我们数据域的开销是E
对于顺序表来说呢
因为我要预先申请一个
比较大的空间
可能还稍微大于你当前元素的
个数n
这个D就是顺序表
它申请的那个可以容纳
最大的元素个数的这个数目
顺序表的空间需求呢
就是DE
而链表的空间需求呢
它是n（P+E）
我们就可以发现
n有一个临界的情况
也就是DE/（P+E）
当n越大的时候呢
这个顺序表它的空间效率就更高
如果当P=E的时候
我们可以估算出这个临界值
是D/2
也就是说当整个这个顺序表里面
有一半以上的元素
是满的时候呢
我们这个顺序表
它的存储效率就超过了链表
对于顺序表和链表来说呢
它们分别有一些场景
是不太适合的
例如对于顺序表
如果是你经常要插入删除
对这个表的元素
有很多的动态修改
或者是说你这个表长呢
你也不知道
你不能够预先估计
我需要预留多大的空间
这种情况呢
都不是很适合
对于链表来说呢
就是如果我经常要读
里面的第i个元素
要从表头然后逐个读
读到表尾
这种操作太频繁的话
链表也不是一个很好的数据结构
还有一种情况就是
指针相对于数据域
它所占用的空间更大
如果我们这个线性表呢
它的元素是字符型的
字符相对于指针来说呢
它的空间是小很多
如果你强行的用链表来实现
它的存储效率是非常低的
顺序表和链表
它们分别适合的一些场景
我们可以总结为
对于顺序表来说
如果你的整个线性表
它的结点数目
你大致可以估计出来
以及它的结点呢
是比较稳定的
也就是插入删除不是那么频繁的
还有就是这个n呢
它大于这样的一个临界值的情况
我们都很适合于用顺序表
链表呢就是
如果你这个线性表结点的数目
你无法预知
还有就是插入删除
它的变化特别的频繁
还有是n小于这个临界值
也就是说如果采用链表呢
它的存储密度损失也不是那么大
这种情况我们就适合使用链表
最后给大家留一下思考
顺序表和链表呢
我们在选择的时候
需要考虑哪些问题
例如结点变化的动态性
就是插入删除是不是频繁
还有存储密度等等问题
我们再给大家一个线性表的
应用的例子
对于一元多项式来说
我们每一项呢
它有相应的系数
在线性表里面
我们可以这么来表达
假设表里面的每一个元素
对应的就是我们那个多项式的项
比如说pi就对应于xi它的系数
这样的话
我们把它的所有的系数呢
给它顺序的收集起来
就形成了一个线性表
对于这个线性表
如果我们把它存在数组里面
我只需要把它的系数给保存好
pi呢对应于相应的第i个元素
xi的系数
这个是能够很好的表达
这样的一元多项式的
对于数据密集的情况
这个没有问题
但是如果这些项是很稀疏的情况
我们来看这个例子
对这种情况
如果你还开这么一个大数组
像这个例子的话
你要开4万以上的这么一个数组
而里面呢非0元只有两个
显然是非常低效的存储
基于这个存储呢
我们运算也是非常低效的
要你恢复出它的一个一元多项式的
这样的表达
你要在数组里面去挨个找
来查找它的非0元
在这种情况下
我们用链表来表示
就非常方便了
我的链表的结点呢
我除了系数以外
我还把它的指数也给保留起来
然后再多一个指针域
这个多项式
我们就可以表达成这样的形式
可以看到呢
它是非常方便就可以从表头结点
一直到表尾
马上就把它的非0项
就都给找出来了
对于这样一个一元多项式的应用
我们可以来试验一下
编写一元多项式的加法的算法
还有减法的算法
谢谢大家