顺序表（二）

2.1 线性表

线性表是最基本的数据结构之一，它是某类元素的集合，记录着元素之间的一种顺序关系，是实现更复杂数据结构的基础。

根据存储方式不同，可分为（顺序存储和链式存储）：

• 顺序表：将元素放在一块连续的内存空间中，顺序存储，存储元素是连续的
• 链表：元素之间链接起来，不需要连续的内存空间，链式存储，存储元素不一定连续，元素节点中存放数据元素以及相邻元素的地址信息

2.2 顺序表

顺序表在内存中是以连续存储的方式存储的，即元素之间没有其他数据结构的内存空间，基本布局方式存储每个元素所占的存储单元大小相同。

顺序表结构

image

图 a 表示顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素下表为逻辑地址，而元素存储的物理地址（即实际内存地址）可通过存储区的起始地址 Loc(e0) 加上逻辑地址（第 i 个元素）与存储单元大小 c 的乘积计算而得：

Loc(ei) = Loc(e0) + c*i

故，访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。

---

顺序表计算

假设每个顺序表中每个元素占用内存空间为 c，起始物理地址（内存地址）为 L0，那么相应地：

# 第一个元素
L0

# 第二个元素
L0 + 1c

# 第三个元素
L0 + 2c

# 第 n 个元素
L0 + (n-1)c

# 由此可以推算出顺序表的计算公式为：
L(n) = L(a0) + c*i              # c 为每个元素占用的内存大小，i 为元素的逻辑地址，即下标

访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。

元素外置型

基本布局结构，每个元素所占的存储单元大小相同，若元素大小不统一，则须采用图 b 的元素外置的形式。

而顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。注意，图b中的c不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。

2.3 顺序表结构

一个完整的顺序表由两部分组成：元素集合区以及表结构信息记录区（存储表中元素个数和存储区容量大小）。

image

顺序表两种基本实现方式

image

• 一体式：存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。
• 分离式：表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

元素存储区扩充

分离式结构在扩充时（即新增元素时），可在不改变表对象的前提下对数据存储区进行扩充，这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。

扩充容量有两种策略：

• 线性增长：

  • 每次按固定数量增加，如：每次增加 10 个元素位置
  • 节省空间，但是扩充操作频繁，操作次数多。

• 成倍增长

  • 每次扩充容量加倍，如每次扩充增加一倍存储空间。

  • 减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。

2.4 顺序表操作

在前面我们说了，数据的常用操作有插入、删除、查找、修改、排序，而在五个操作中最常用的两个操作应该就是插入和删除了，下面来看看顺序表的插入、删除操作。

插入元素

image

在一个顺序表中插入一个元素有三种方式：

• 表的尾部插入：时间复杂度为 O(1)，不需要改变其他元素的位置
• 中间插入：
  • 非保序（不常见）：即要插入的元素放在相应位置，将该位置之前的元素放置在最后一位，时间复杂度 O(1)
  • 保序：需要改变要插入位置后面所有元素所有的位置，往后移动一位（如果空间不够还要扩容），时间复杂度 O(n)
• 头部插入：和保序插入一样，时间复杂度也是 O(n)，因为它需要将所有元素往后移动

---

删除元素

image

删除元素和插入元素类似：

• 表尾元素：O(1)
• 非保序：O(1)
• 保序：O(n)

2.5 Python中的顺序表

Python 中的所有数据类型，tuple 和 list 是基于顺序表实现的。tuple 不可变，采用的是基本布局（即表信息区和元素区在一块）。而 list 从用的是 分离式结构。

list 实现技术

Python list 就是一种元素个数可变的线性表，可加入、删除元素，并在各种操作中维持已有元素的顺序（即保序），并具有以下特征：

• 基于下标访问或更新元素，时间复杂度为 O(1)，因此元素应保存在一块连续的存储空间中
• 允许任意加入元素，且在不断加入元素的过程中，表对象的身份标识（即 ID）不变；因此就必须要能更换元素存储区，并且为保证更换存储区时 list 对象的标识 ID 不变，只能采用分离式结构实现

list 采用 分离式技术实现的动态顺序表，同时在插入、删除时能保序，是一种标准的可变线性表。存储计划：新建空表时，分配一块能存储 8 个元素大小的空间，如果插入操作时空间不够则换一块 4 倍大小的空间。当整个空间超过 50000 时，则采用一倍的策略，其目的是为了能避免出现过多的空闲存储位置。