第一篇 線性表的解題策略

線性表是由有限個數據元素組成的有序集合，這種數據結構具有均勻性（線性表內數據元素的類型相同）和有序性（線性表內數據元素一個接一個排列）的特征。線性表有以下3種類型。

●直接存取類線性表，一種可直接存取某一指定項而不需要先訪問其前驅或后繼的線性表，數組和字符串是其中的典型代表。

●順序存取類線性表，一種按順序存儲所有元素的線性表，其典型代表是鏈表、棧和隊列。

●廣義索引類線性表，一種通過關鍵碼（key）進行索引的線性表，是（關鍵字，數據值）有序對的集合。

在《數據結構編程實驗：大學程序設計課程與競賽訓練教材》（第3版）的第二篇“線性表的編程實驗”，分別給出上述3種類型線性表的實驗。而在這3種線性表中，直接存取類線性表中的數組是一種既簡單又基礎的數據結構。之所以說它簡單，是因為它易于理解、易于編程實現；之所以說它基礎，是因為任何一個有意義的程序都至少直接或間接地使用了這種線性結構，它幾乎“無孔不入”。例如，順序存取類的線性表和廣義索引類的線性表都可使用數組實現。即便是非線性數據結構也以線性表的存儲結構為基礎。本書的第二篇“樹的解題策略”介紹劃分樹、最小生成樹、線段樹、動態樹、左偏樹、伸展樹和紅黑樹，其存儲結構基本上都采用了數組。實現樹的功能的跳躍表本身就是一個數組。本書的第三篇“圖的解題策略”中介紹的網絡流、二分圖、分層圖、平面圖等，其存儲結構也用數組表示。

本篇系統闡述以下3種利用線性表解題的策略。

●快速冪，快速冪運算策略不僅可以應用于整數冪運算，而且可以應用于矩陣的冪運算，能夠大幅度提高計算整數冪和矩陣冪的效率。

●求解線性方程組的高斯消元法，并將這種策略拓展到求解模線性方程組、異或線性方程組以及求矩陣的秩。

●單調棧和單調隊列分別應用于快速查找和DP優化。