算法与数据结构(part4)--顺序表

学习笔记，仅供参考，有错必纠

---

文章目录

算法与数据结构–基于python顺序表什么是线性表什么是顺序表 顺序表的基本形式顺序表的结构与实现顺序表的结构顺序表的两种基本实现方式扩容策略 顺序表的操作插入元素删除元素 Python中的顺序表列表的基本实现

---

算法与数据结构–基于python

顺序表

什么是线性表

在程序中，经常需要将一组数据元素作为整体管理和使用，我们需要创建一种元素组，并用变量记录它们。

一组数据中包含的元素个数可能发生变化(增加或删除元素)。

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示数据之间的某种关系。

这样的一组序列元素的组织形式，我们可以将其抽象为线性表。

一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。

线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。

什么是顺序表

根据线性表的实际存储方式，分为两种实现模型：

顺序表，将元素有顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。

链表，将元素存放在通过链接构造起来的一系列存储块中。

顺序表的基本形式

基本存储形式(L = [1, 2, 3])

元素外置的顺序表(L = [1, 2.5, true])

顺序表的结构与实现

顺序表的结构

一个顺序表的完整信息包括两部分：

一部分是表中的元素集合;

另一部分是有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项.

顺序表的两种基本实现方式

一体式存储，类似于数组，不可变长度

分离式存储，类似于列表，可变长度

扩容策略

每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。

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

顺序表的操作

插入元素

在顺序表中插入新元素111的三种方式：

解释：

a: 在顺序表的末尾插入111b: 在顺序表中索引为1处存入111，将索引1处原来的元素693放入顺序表末尾c: 在顺序表中索引为1处放入111，并将后面的元素向后依次移动1格

复杂度：

a: $O(1)$b: $O(1)$c: $O(n)$

删除元素

删除顺序表中元素的三种方式：

解释：

a:删除顺序表的末尾的元素b: 删除顺序表中索引为1处的元素，并将末尾的元素154存放在索引1处c: 删除顺序表中索引为1处的元素，并将索引1后的元素向前依次移动1格

复杂度：

a: $O(1)$b: $O(1)$c: $O(n)$

Python中的顺序表

Python中的list和tuple两种类型采用了顺序表的实现技术，具有前面讨论的顺序表的性质；

tuple是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类似；

列表的基本实现

Python标准类型list就是一种元素个数可变的线性表，可以添加和删除元素，并在各种操作中维持已有元素的顺序（即保序），而且还具有以下行为特征：

基于下标（位置）的高效元素访问和更新，时间复杂度为$O(1)$，为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区中。

允许任意加入元素，而且在不断加入元素的过程中，表对象（id()方法得到的值）不变，为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时list对象的标识id不变，只能采用分离式实现技术。

在Python的官方实现中，list就是一种采用分离式技术实现的动态顺序表。这就是为什么用list.append(x)或list.insert(len(list), x)，即尾部插入，比在指定位置插入元素效率高。

在Python的官方实现中，list实现采用了如下的策略：

在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区。

在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。

但如果此时的表已经很大（目前的阈值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。