第5章　应用顺序存取类线性表编程

顺序存取类线性表是一种按顺序存储所有元素的线性表，这种线性表的第一个数据元素在表头位置，最后一个数据元素在表尾位置（如下图所示）。

顺序存取类线性表有如下两个特点：

1）表长在创建时没有大小限制，这意味着它们可以动态地扩展和收缩。

2）对表中数据元素的存取只能顺序进行，不能直接存取。为了访问某个元素，需要从第1个数据元素（或者最后1个数据元素）出发，按从前至后的顺序或者从后至前的顺序逐个访问，直到指定的数据元素，也可以双向遍历，即从前向后和从后向前遍历。

顺序存取类线性表的一个简单实例就是购物清单。顺次写下要购买的全部商品，就会创建一张购物清单。在购物时，一旦找到某种商品就把它从清单中划掉。这类线性表既可以是有序的，也可以是无序的。无序线性表是由无序元素组成的，有序线性表具有顺次对应的有序值。表中数据元素的有序性对查找数据元素的效率会产生很大的影响。例如，在有序线性表中进行二分查找的效率比顺序查找高许多。按照存取方式分类，顺序存取类线性表包括：

1）按照数据元素位置存取的顺序表（包括数组和链表）。

2）存取位置有限制的队列和栈，其中队列包括顺序队列、优先队列和双端队列。