[数据结构与算法]基本数据结构——顺序表

顺序表的基本形式

1. 顺序表的基本布局：逻辑地址+元素存储+物理地址
2. 元素外置的顺序表：逻辑地址+物理地址——>元素
   其中
   逻辑地址为：0，1，…，n-1
   物理地址为：l_0+1xc , l_0+2xc, … , l_0+(n-1)xc

顺序表的结构与实现

顺序表的结构

表头信息：存储区容量+元素个数
数据区：存储的数据

顺序表有一体式结构和分离式结构

元素存储区的扩充

1. 每次扩充固定数目的存储位置：节省空间，但操作频繁次数多
2. 每次扩充容量加倍：操作执行次数相对较少，但浪费空间资源。以空间换时间

顺序表的操作

增加元素

1. 尾端增加元素，时间复杂度O(1)
2. 非保序加入元素，O(1)
3. 保序地加入元素，O(n)

删除元素

1. 删除表尾元素，O(1)
2. 非保序的元素删除，O(1)
3. 保序的元素删除，O(n)

Python中的顺序表

Python中有 list 和 tuple 两种类型采用了顺序表的实现技术
其中tuple是不可变的顺序表

list的基本实现技术

list中可以加入和删除元素，在操作中维持已有元素的顺序，具有以下特征：

1. 基于下标的高效元素访问和更新，时间复杂度O(1)，采用顺序表技术
2. 允许任意加入元素，且在不断加入元素的过程中，表对象的id不变，采用分离式顺序表

注意：

1. 建立空表时，操作系统分配能容纳8个元素的存储区
2. 执行插入操作，元素存储区满，更换4倍大的存储区
3. 如果表已经很大，则改变策略，增加1倍存储区以避免出现过多空闲存储位置