数组的基本概念
数组是一个由二元组（idx，value）组成的集合，其中每个idx都对应一个value值。idx被称为下标，它可以是一个整数，也可以是由多个整数构成的组合，由几个整数构成的组合称为数组的维数。数组根据维数可以分为一维数组、二维数组和数组。
数组具有以下特点：
1. 数组中所有元素都具有统一的数据类型。
2. d（d≥1）维数组中的非边界元素具有d个前驱和d个后继。
3. 一旦数组的维数确定，其元素个数和元素之间的关系就不会再改变，特别适合于顺序存储。
4. 每个下标都对应一个唯一的数组元素值。
关于数组的抽象数据类型，其主要操作是存取元素值，没有插入和删除操作，因此通常采用顺序存储方式来实现。一维数组的所有元素按照逻辑次序存放在连续的内存存储单元中。对于数组，如二维数组（也称为矩阵），其存储方式可以按行优先或列优先进行。
接下来我们讨论一个实际问题：设有二维数组a[1..50，1..80]，其a[1][1]元素的地址为2000，每个元素占2个存储单元。若按照行优先存储，元素a[45][68]的存储地址可以通过计算得出。同样地，若按照列优先存储，也可以计算出元素a[45][68]的存储地址。
除了常规矩阵，还有一些特殊矩阵如对称矩阵、三角矩阵、对角矩阵等，它们都有相应的压缩存储方式。当矩阵中的非零元素个数相对于总元素个数非常少时，我们称之为稀疏矩阵。例如，一个100100的矩阵中只有100个非零元素就可以被认为是稀疏矩阵。特殊矩阵中的特殊元素分布有规律，而稀疏矩阵的非零元素分布则没有规律。
为了更有效地处理稀疏矩阵，我们采用了一些特殊的存储方式，如三元组表示法和十字链表表示法。在三元组表示法中，每个非零元素都被看作是一个结点，所有非零元素按照一定的顺序（通常是行优先）存放在一个列表中。而在十字链表表示法中，每个非零元素对应一个结点，所有行和列的结点都被链接起来，形成一个循环单链表，方便进行矩阵运算。为了统一管理，还设计了一个总头结点，将所有行、列头结点链接起来。
