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个。

一维数组还可用来实现哈希表等，二维数组可用来保存图的邻接矩阵等，将在后续章节详细讲述。