2.1 线性表的逻辑结构

2.1.1 线性表的定义

线性表（Linear List）是一种线性结构。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子很多，如学生情况信息表（表中数据元素的类型为学生信息记录类型）、字符串（表中数据元素的类型为字符型）等。

综上所述，线性表定义如下。

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，通常记为：

（a1, a2, …, ai-1, ai, ai+1, …, an）

其中n为表长，当n=0时称该线性表为空表。

表中相邻元素之间存在着前后次序关系。将ai-1称为ai的直接前趋，ai+1称为ai的直接后继。即，对于ai，当i=2, …, n时，有且仅有一个直接前趋ai-1，当i=1, 2, …, n-1时，有且仅有一个直接后继ai+1，而a1是表中第一个元素，它没有前趋，an是最后一个元素，它无后继。

需要说明的是：ai为序号为i的数据元素（i=1, 2, …, n），在本书中，将它的数据类型抽象为datatype，而在实际应用中，datatype可根据具体应用问题而代之以不同的数据类型。例如，在学生情况信息表中，它是用户自定义的学生类型；在字符串中，它是字符型。

2.1.2 线性表的基本操作

在第1章中提到，数据结构中元素的操作（或称运算）是定义在逻辑结构层次上的，而操作的具体实现是建立在存储结构上的，因此下面定义的线性表的基本操作作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。

线性表上的基本操作有以下几种。

（1）线性表初始化：Init_List(L)。

初始条件：表L不存在。

操作结果：构造一个空的线性表L。

（2）求线性表的长度：Length_List (L)。

初始条件：表L存在。

操作结果：返回线性表中的所含元素的个数。

（3）取表元：Get_List (L, i)。

初始条件：表L存在且1≤i≤Length_List(L)。

操作结果：返回线性表L中的第i个元素的值或地址。

（4）按值查找：Locate_List (L, x)。

初始条件：线性表L存在，x是给定的一个数据元素。

操作结果：在表L中查找值为 x 的数据元素，其结果返回在L中首次出现的值为 x的那个元素的序号或地址，称为查找成功；否则，在L中未找到值为 x 的数据元素，返回一特殊值表示查找失败。

（5）插入操作：Insert_List (L, i, x)。

初始条件：线性表L存在，插入位置正确（1≤i≤n+1, n为插入前的表长）。

操作结果：在线性表L的第i个位置上插入一个值为x的新元素，这样使原序号为i , i+1, … , n的数据元素的序号变为i+1, i+2, … , n+1，插入后，新表长=原表长+1。

（6）删除操作：Delete_List (L, i)。

初始条件：线性表L存在，1≤i≤n。

操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为i+1, i+2, …, n的元素的序号变为i, i+1, …, n-1，新表长=原表长-1。需要说明以下几点。

（1）数据结构上的基本操作（或运算）不是它的全部操作（或运算），而是一些常用的基本操作（或运算），每一个基本操作（或运算）在实现时也可能根据不同的存储结构派生出一系列相关的操作（或运算）。例如，线性表的查找在链式存储结构中还有按序号查找；再如，插入操作，可能是将新元素插入到某一元素之前，也可能是将新元素插入到某一元素之后，还可能是将新元素插入到其他适当的位置，等等。不可能也没有必要全部定义出一种数据结构的运算集，读者掌握了某一数据结构上的基本运算后，其他运算可以通过基本运算来实现，也可以直接去实现。

（2）在上面各操作中定义的线性表L只是一个在逻辑结构层次上抽象的线性表，尚未涉及它的存储结构，因此每个操作在逻辑结构层次上尚不能用具体的程序设计语言写出具体的算法，其算法只有在存储结构确立之后才能用具体程序设计语言实现。

（3）正因为这些操作仅是逻辑上的说明，因此以上用来定义操作的函数中所列的参数的数据类型并不明确说明，只是隐含在函数说明中，对于参数的传递方式也不予考虑，这是因为只有在涉及具体实现时才去明确其参数的数据类型和传递方式。