Python数据结构与算法（2.1）——线性表的基本概念
0. 学习目标
线性表是应用最为广泛的一种数据结构，如其名所示，是一种典型的线性结构。本节主要介绍线性表的有关概念和基本运算。
通过本节学习，应掌握以下内容：
- 线性表的定义
- 线性表的逻辑结构
1. 线性表的定义
线性表 (Linear List) 是最基础也是最常用的数据结构，是有
n
(
n
≥
0
)
n(n≥0)
n(n≥0) 个具有相同属性的数据元素组成的有限序列。序列中元素的个数
n
n
n 称为线性表的长度，当
n
=
0
n=0
n=0 时称为空表，即不含有任何元素。非空线性表L可以用以下形式表示：
L
=
(
a
1
,
a
2
,
…
,
a
i
,
a
i
+
1
,
…
,
a
n
)
L=( a_1, a_2, …, a_i, a_{i+1}, …, a_n)
L=(a1,a2,…,ai,ai+1,…,an)
其中
a
i
(
1
≤
i
≤
n
)
a_i(1≤i≤n)
ai(1≤i≤n) 表示 L 中的第
i
i
i 个数据元素，下标
i
i
i 为
a
i
a_i
ai 元素在线性表中的序号和位置。线性表中元素的顺序取决于添加顺序或移除顺序，某个元素被添加到线性表中后，它与前后元素的相对位置将保持不变。在线性表中，把
a
i
(
2
≤
i
≤
n
)
a_i(2≤i≤n)
ai(2≤i≤n) 的前一元素
a
i
−
1
a_{i-1}
ai−1 称为
a
i
a_i
ai 的直接前趋，后一元素
a
i
+
1
a_{i+1}
ai+1 称为
a
i
a_i
ai 的直接后继，第一个元素
a
1
a_1
a1 称为表头元素，最后一个元素
a
n
a_n
an 称为表尾元素。
非空线性表的逻辑结构可以用下图来表示：
由上图所示，我们不难发现非空线性表的逻辑结构具有如下特征：
- 线性表中的数据元素是按前后位置有序的，即第 i i i 个数据元素 a i a_i ai 在逻辑上是第 i + 1 i+1 i+1 个元素 a i + 1 a_{i+1} ai+1 的直接前趋，第 i + 1 i+1 i+1 个数据元素 a i + 1 a_{i+1} ai+1 在逻辑上是第 i i i 个数据元素 a i a_i ai 的直接后继。
- 线性表中第一个数据元素 a 1 a_1 a1 有且仅有一个直接后继而没有直接前驱，最后一个数据元素 a n a_n an 有且仅有一个直接前驱而没有直接后继。其余每个数据元素 a i ( 1 ＜ i ＜ n ) a_i(1＜i＜n) ai(1＜i＜n) 有且仅有一个直接前驱，并且有且仅有一个直接后继。
- 线性表中数据元素的类型是相同的，表长的取值是一个有限数，最小为 0。
线性表在现实世界的非常常见，例如：26个英文字母表——(a, b, c, …, z)，可以视为一个线性表，其中每个字母是一个数据元素；植物进化的演化过程也可以用线性表的形式表示——(藻类植物, 裸蕨类植物, 蕨类植物, 裸子植物, 被子植物)；在复杂的线性表中，一个数据元素可以由若干个数据项组成，一个学生基本信息表可以视为一个线性表，其中每个学生的所有相关信息组成一个数据元素(也可以称为记录，record)，每个数据元素包含学号、姓名、性别、年龄、班级、联系方式等数据项。
由上述示例可以看出，在现实世界的不同的情况下，线性表的数据元素的具体内容虽不相同，但是都反映了数据元素之间的相对位置是线性的逻辑结构特性。
2. 线性表的操作
数据结构的操作是定义在逻辑结构层次上的，而操作的具体实现则是建立在存储结构上的。因此下面定义的线性表的基本操作作为逻辑结构的一部分，给出了这些操作的功能是“做什么”，至于“如何做”则依赖于选定什么样的存储结构。
顺序表的主要操作包括：
- 初始化线性表：构造空的线性表
- 计数：返回列表中的元素数
- 按序号取元素：读取线性表指定位置的元素
- 按值查找：在列表中查找指定的数据元素
- 插入：在列表中插入一个元素
- 删除元素：从列表中删除并返回指定的位置元素
3. 抽象数据类型线性表定义
综上所述，抽象数据类型线性表的定义如下：
ADT List:
数据对象：D = a i ∣ a i ∈ D a t a T y p e , i = 1 , 2 , . . . , n , n ≥ 0 D={a_i|a_i∈DataType, i=1,2,...,n,n\geq0} D=ai∣ai∈DataType,i=1,2,...,n,n≥0数据关系：
R = < a i , a i + 1 > ∣ a i , a i + 1 ∈ D , i = 1 , 2 , . . . , n − 1 R={<a_{i},a_{i+1}>|a_i,a_{i+1}∈D,i=1,2,...,n-1} R=<ai,ai+1>∣ai,ai+1∈D,i=1,2,...,n−1基本操作：
1. itit(): 初始化线性表
将线性表 L 置为空表
2. len(): 求取并返回线性表所含元素的个数 n
若线性表为空，则返回整数0
3. getitem(i): 读取线性表 L 中第 i 个数据元素
其中 1 ≤ i ≤ len(L)
4. locate(x): 在线性表 L 中查找值为 x 的数据元素
若查找成功则返回第一个值为 x 的元素的序号；否则，返回一特殊值(例如-1)，表示查找失败
5. insert(i, x): 在线性表 L 第 i 个位置上插入值为 x 的新元素
其中 1 ≤ i ≤ len(L)+1，插入后表长增 1；原序号为 i, i+1, …, n 的数据元素的序号变为 i+1, i+2, …, n+1
6. delitem(i): 在线性表 L 中删除序号为 i 的数据元素
其中 1 ≤ i ≤ len(L)，删除后表长减 １；原序号为 i+1, i+2, …, n 的元素变为序号 i, i+1, …, n-1
以上只给出了定义在线性表逻辑结构上的最基本运算，在实际应用中可借助于这些基本运算构造出更为复杂的运算。
版权归原作者 盼小辉丶 所有， 如有侵权，请联系我们删除。