2.2　线性表

从这一节开始介绍各种常用的数据结构。首先要看的便是线性表。线性表是一种典型的线性结构，是最简单、最常用的数据结构。

2.2.1　什么是线性表

谈到线性表（Linear List），首先应该分析其逻辑定义。从逻辑上来看，线性表就是由n（n≥0）个数据元素a1，a2，…，an组成的有限序列。这里需要说明如下几点：

・数据元素的个数为n，也称为表的长度，当n=0的时候称为空表；

・如果一个线性表非空，即n>0，则可以简单地记作（a1，a2，…，an）；

・数据元素ai（1≤i≤n）表示了各个元素，在不同的场合，其含义也不同。

在现实生活中，可以找到很多线性表的例子。比如英文字母表就是最简单的线性表，英文字母表（A，B，C，…，Z）中，每个英文字符就是一个数据元素，也称为数据结点。另外，表2-1某班级学生成绩表也是一个线性表。在这里，数据元素就是某个学生的记录，其中包括学号、姓名、各个科目的成绩等。

对于一个非空的线性表，其逻辑结构特征如下：

・有且仅有一个开始结点a1，没有直接前趋结点，有且仅有一个直接后继结点a2；

・有且仅有一个终结结点an，没有直接后继结点，有且仅有一个直接前趋结点an-1；

・其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋结点ai-1和一个直接后继结点ai+1；

・对于同一线性表，各数据元素ai必须具有相同的数据类型，即同一线性表中各数据元素具有相同的类型，每个数据元素的长度相同。

2.2.2　线性表的基本运算

前面介绍的是线性表的逻辑结构，再来分析线性表的基本运算。线性表的基本运算包括如下内容。

1）初始化

初始化表（InitList）即构造一个空的线性表L。

2）计算表长

计算表长（ListLength）即计算线性表L中结点的个数。

3）获取结点

获取结点（GetNode）即取出线性表L中第i个结点的数据，这里1≤i≤ListLength（L）。

4）查找结点

查找结点（LocateNode）即在线性表L中查找值为x的结点，并返回该结点在线性表L中的位置。如果在线性表中没有找到值为x的结点，则返回一个错误标志。这里需要注意的是，线性表中有可能含有多个与x值相同的结点，那么此时就返回第一次查找到的结点。

5）插入结点

插入结点（InsertList）即在线性表L的第i个位置插入一个新的结点，使得其后的结点编号依次加1。这时，插入一个新结点之后，线性表L的长度将变为n+1。

6）删除结点

删除结点（DeleteList）即删除线性表L中的第i个结点，使得其后的所有结点编号依次减1。删除一个结点之后，线性表L的长度将变为n-1。

上述内容是一个线性表最基本的运算，当然读者根据需要还可以定义其他一些运算。

至此，线性表的逻辑结构和数据运算讨论完毕，线性表的存储结构还没有介绍。其实，在计算机中线性表可以采用两种方法来保存，一种是顺序存储结构，另一种是链式存储结构。顺序存储结构的线性表称为顺序表，而链式存储结构的线性表称为链表。顺序表和链表就是下面要介绍的内容。