1.4 數組的應用

1.4.1 線性表的順序存儲

一維數組可用來實現線性表的順序存儲。

線性表的順序存儲又稱為順序表。其中，需分清線性表與順序表的概念。線性表的概念是一種邏輯結構，表示元素之間一對一的相鄰關系，而順序表和鏈表（后續章節介紹）是存儲結構。兩者屬于不同層面的概念，請不要將二者混淆。

注意：線性表中元素的位序是從1開始的，而數組中元素的下標是從0開始的。

順序表最主要的特點是可以進行隨機存取，即通過首地址和元素序號可以在O(1)的時間內找到指定的元素。但是插入和刪除操作需要移動大量元素。

在表長為n的順序表L中共有n+1個可以插入結點的地方。插入操作結點移動的次數不僅與表長n有關，而且與插入的位置i有關：

最好情況：在表尾插入，時間復雜度為O(1)；最壞情況：在表頭插入，整個數組元素都將后移，時間復雜度為O(n)；平均情況：假設pi(pi=1/(n+1))是在第i個位置上插入一個結點的概率，則在長度為n的順序表中插入一個結點時所需移動結點的平均次數為：

因此，順序表插入算法的平均時間復雜度為O(n)。

在表長為n的順序表L中共有n個可以被刪除的地方。

最好情況：刪除表尾元素，無須移動元素，時間復雜度為O(1)；最壞情況：刪除表頭元素，需要移動除第一個元素外的所有元素，時間復雜度為O(n)；平均情況：假設pi(pi=1/n)是刪除第i個位置上結點的概率，則在長度為n的順序表中刪除一個結點時所需移動結點的平均次數為：

因此，順序表刪除算法的平均時間復雜度為O(n)。

按值查找的最好情況：查找的元素就在表頭，僅需比較一次，時間復雜度為O(1)。最壞情況：查找的元素在表尾，需要比較n次，時間復雜度為O(n)。平均情況：假設pi(pi=1/n)是查找的元素在第i個位置上的概率，則在長度為n的順序表中查找值為e的元素所需比較的平均次數為：

因此，順序表按值查找算法的平均時間復雜度為O(n)。

例1：在n個結點的順序表中，算法的時間復雜度是O(1)的操作是______。（2012·騰訊）

A.訪問第i個結點（1<=i<=n）和求第i個結點的直接前驅(2<=i<=n)

B.在第i個結點后插入一個新結點（1<=i<=n）

C.刪除第i個結點（1<=i<=n）

D.將n個結點從小到大排序（1<=i<=n）

解答：A。

1.4.2 對稱矩陣的壓縮

若一個n階方陣A[1…n][1…n]中的任一個元素ai,j，都有ai,j=aj,i（1≤i，j≤n），則稱其為對稱矩陣。對稱矩陣可以壓縮然后存儲到一維數組中。

例1：將10階對稱矩陣壓縮存儲到一維數組A中，則數組A的長度最少為（　　）。（2012·搜狗）

A.100

B.40

C.55

D.80

解答：C。10階對稱矩陣共有10×10個元素，壓縮到一維數組存儲時，需要存儲對角線以上或以下的元素共45個，加上對角線上的元素，共55個。

一維數組還可用來實現哈希表等，二維數組可用來保存圖的鄰接矩陣等，將在后續章節詳細講述。