第一篇 线性表的解题策略

线性表是由有限个数据元素组成的有序集合，这种数据结构具有均匀性（线性表内数据元素的类型相同）和有序性（线性表内数据元素一个接一个排列）的特征。线性表有以下3种类型。

●直接存取类线性表，一种可直接存取某一指定项而不需要先访问其前驱或后继的线性表，数组和字符串是其中的典型代表。

●顺序存取类线性表，一种按顺序存储所有元素的线性表，其典型代表是链表、栈和队列。

●广义索引类线性表，一种通过关键码（key）进行索引的线性表，是（关键字，数据值）有序对的集合。

在《数据结构编程实验：大学程序设计课程与竞赛训练教材》（第3版）的第二篇“线性表的编程实验”，分别给出上述3种类型线性表的实验。而在这3种线性表中，直接存取类线性表中的数组是一种既简单又基础的数据结构。之所以说它简单，是因为它易于理解、易于编程实现；之所以说它基础，是因为任何一个有意义的程序都至少直接或间接地使用了这种线性结构，它几乎“无孔不入”。例如，顺序存取类的线性表和广义索引类的线性表都可使用数组实现。即便是非线性数据结构也以线性表的存储结构为基础。本书的第二篇“树的解题策略”介绍划分树、最小生成树、线段树、动态树、左偏树、伸展树和红黑树，其存储结构基本上都采用了数组。实现树的功能的跳跃表本身就是一个数组。本书的第三篇“图的解题策略”中介绍的网络流、二分图、分层图、平面图等，其存储结构也用数组表示。

本篇系统阐述以下3种利用线性表解题的策略。

●快速幂，快速幂运算策略不仅可以应用于整数幂运算，而且可以应用于矩阵的幂运算，能够大幅度提高计算整数幂和矩阵幂的效率。

●求解线性方程组的高斯消元法，并将这种策略拓展到求解模线性方程组、异或线性方程组以及求矩阵的秩。

●单调栈和单调队列分别应用于快速查找和DP优化。