线性表的基本概念

2.3.1　线性表的基本概念

线性表（Linear List）是最简单、最常用的一种数据结构。

线性表由一组数据元素构成。数据元素的含义很广泛，在不同的具体情况下，它可以有不同的含义。例如，一个n维向量（x₁，x₂，…，x_n）是一个长度为n的线性表，其中的每一个分量就是一个数据元素。又如，英文小写字母表（a，b，c，…，z）是一个长度为26的线性表，其中的每一个小写字母就是一个数据元素。再如，一年中的四个季节（春，夏，秋，冬）是一个长度为4的线性表，其中的每一个季节名就是一个数据元素。

矩阵也是一个线性表，只不过它是一个比较复杂的线性表。在矩阵中，既可以把每一行看成是一个数据元素（即一个行向量为一个数据元素），也可以把每一列看成是一个数据元素（即一个列向量为一个数据元素）。其中每一个数据元素（一个行向量或一个列向量）实际上又是一个简单的线性表。

数据元素可以是简单项（如上述例子中的数、字母、季节名等）。在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括姓名、学号、性别、年龄和健康状况5个数据项。在这种复杂的线性表中，由若干数据项组成的数据元素称为记录（record），而由多个记录构成的线性表又称为文件（file）。因此，上述学生情况登记表就是一个文件，其中每一个学生的情况就是一个记录。

非空线性表有如下一些结构特征：

①有且只有一个根节点a₁，它无前件；

②有且只有一个终端节点a_n，它无后件；

③除根节点与终端节点外，其他所有节点有且只有一个前件，也有且只有一个后件。线性表中节点的个数n称为线性表的长度。当n=0时称为空表。