《算法设计与分析》一一第3章　线性表的遍历

第3章　线性表的遍历
线性表是一种简单又广泛使用的数据结构。线性表中所有的元素组成线性序列。除头尾之外的每个元素都有唯一的前驱和后继；头元素只有后继，没有前驱，而尾元素只有前驱，没有后继。线性表的特征决定了我们很容易从头至尾依次扫描其中的每一个元素，而这一简单的遍历过程可以解决很多重要的算法问题。
线性表的遍历是在算法的简单性与高效性之间的一种权衡。基于线性表遍历的算法往往原理简单、易于实现和维护；但是其效率往往较低，有较大的提升空间。以线性表遍历为基础，我们可以进行更复杂的算法设计，例如，以遍历为基础对线性表中的元素进行划分以使用分治策略(参见6.1节)，在线性表的元素间建立堆结构(参见7章)，将线性表扩展到二维以表示图(参见第4、5章)等。但是在提升效率的同时，算法的设计、实现、维护的难度相应地增加。
线性表在实际存储的时候，有两种不同的方式：一种是数组，另一种是链表。数组是常数时间寻址，即访问任何位置的元素都是常数时间。链表是线性时间寻址，访问第k个元素的时间大致为O(k)。但是数组的大小是预先指定的，不能运行时动态调整。链表可以在运行时动态调整其大小。数组和链表的这一差别对有些算法是关键性的，如折半查找(参见9.1节)等。
本章我们以排序、选择、查找这3个经典算法问题为例，讨论基于线性表遍历的算法设计与分析。