数据结构笔记——顺序表
-
python中的list就是顺序表的结构
-
一体式结构
等量大小的数据，可以只指定一个首地址和总长度即可（还有一个默认单位存储地址），取值则可以通过这上述参数计算而得。
list1 = [1, 2020, 2008]
-
元素外置
地址，用一个顺序表存地址（地址码是等大的）
list2 = [‘张三’， 2， True]
内存以一个字节为索引单位
python中已经对顺序表进行了封装，不用自己构造
在其他语言中要实现的话
顺序表的两种基本实现方式
-
链表与顺序表都是线性表
-
顺序表的扩展
扩充方式一：每次扩充一个batch
扩充方式二：翻倍扩充，较上一种快一点（空间换时间）
-
顺序表的增加
-
表尾端加入元素
-
非保序的元素插入
在指定索引处插入值，将索引处的原值添加的表尾，时间复杂度为O(1)
-
保序的元素插入
在指定索引处插入值，将后续值依次后移。实际中应用较多的一种插入方式
-
-
顺序表的删除
-
删除表尾元素
-
非保序的元素删除
删去指定索引处的值，将表尾元素移至索引处
-
保序的元素删除
删去指定索引处的值，将后续元素依次前移。实际中应用比较多的一种删除方式
-
-
python中的list就是通过顺序表实现的
-
允许扩充的顺序表——动态顺序表
python中实现动态扩充，初始化分配8个元素的存储区；如果存满，采用4倍增的方式扩展空间，当超过50000个元素的时候，采用翻倍增的策略。
-
list中操作的时间复杂度