第4章　应用直接存取类线性表编程

直接存取类线性表，指的是可以直接存取某一指定项而不须先访问其前驱或后继的线性表。数组是这类数据结构的最典型代表。

数组是存储于一个连续存储空间中且具有相同数据类型的数据元素的集合，是一种定长的线性表。若数组元素不再有分量，则该序列是一维数组；若数据元素为数组，则称该序列为多维数组。在数组中，数据元素的下标间接反映了数据元素的存储地址，在数组中存取一个数据元素只要通过下标计算它的存储地址就行了，因此在数组中存取任意一个元素的时间都为O(1)。从这个意义上讲，数组的存储结构是一个可直接存取的结构。字符串、表格都属于直接存取类线性表，例如，可以按下标直接存取字符串中的某一字符，也可以按记录号检索表格中的某一记录。

以数组为代表的直接存取类线性表是程序设计中使用最多的数据结构。