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 时,则采用一倍的策略,其目的是为了能避免出现过多的空闲存储位置。
网友评论