• 2 顺序表
  • 2.1 顺序表的基本形式
  • 2.2 顺序表的结构与实现
  • 2.3 顺序表的操作
  • 2.4 Python中的顺序表
    • 2.4.1 list的基本实现技术

2 顺序表

在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，

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

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

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

• 顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。
• 链表，将元素存放在通过链接构造起来的一系列存储块中。

2.1 顺序表的基本形式

顺序表有两种：
1. 基本结构
2. 元素外置结构

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

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

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

如果元素的大小不统一（或类型不同），则须采用图b的元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）。

由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。

2.2 顺序表的结构与实现

一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。

2.3 顺序表的操作

1. 增加元素：尾端加入元素，时间复杂度为O(1);保序的元素加入，时间复杂度为O(n)
2. 删除元素:同上

2.4 Python中的顺序表

Python中的 list 和 tuple 两种类型采用了顺序表的实现技术，具有前面讨论的顺序表的所有性质。（tuple是不可变类型）

2.4.1 list的基本实现技术

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

• 基于下标（位置）的高效元素访问和更新，时间复杂度应该是O(1)；

为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区中。

• 允许任意加入元素，而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。

为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时list对象的标识id不变，只能采用分离式实现技术。

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

原文链接：https://lookme.blog.csdn.net/article/details/79842410

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。