第5章 数组
内容提要：
本章首先介绍数组的定义；接着介绍数组的顺序存储结构；最后介绍4中矩阵的压缩存储，包括：对称矩阵、三角矩阵、对角矩阵和稀疏矩阵。
学习目标与重点：
◆理解数组的特点；
◆掌握数组的存储；
◆掌握特殊矩阵的存储及运算。
关键术语：数组；压缩存储；对称矩阵；三角矩阵；对角矩阵；稀疏矩阵
5.1 数组的定义
数组（Array）可以看成是一种特殊的线性表，其特点是结构中的元素本身可以是具有某种结构的数据。比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。
在二维数组中的每一个元素最多可以有两个直接前驱和两个直接后继（边界除外），在n维数组中，每一个元素最多可以有n个直接前驱和n个直接后继。所以多维数组是一种非线性数据结构。
数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。一般情况下，在数组上不做插入、删除数据元素的操作，所以采用顺序存储结构存储数组是很合适的。
在数组中通常做下面两种操作：
（1）取值操作：给定一组下标，读取其对应的数据元素。
（2）赋值操作：给定一组下标，存储或修改与其相对应的数据元素。
本章着重研究二维和三维数组，因为它们的应用是最基本的也是最广泛的，尤其是二维数组。
5.2 数组的顺序存储结构
在计算机内，存储地址空间是一维的。所以，对于一维数组只要按下标顺序分配即可；而对多维数组分配时，必须把数组元素存储在一维存储器中。对二维数组存储时，一般有两种存储方式：一是以行序为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列序为主序（先列后行）的顺序存放，如FORTRAN语言就是采用以列序为主序的分配顺序，即一列一列地分配。
5.3 矩阵的压缩存储
所谓压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。在矩阵中非零元素或零元素的分布有一定规律的矩阵称为特殊矩阵，如：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵等。
压缩存储时，节约了存储单元，可是怎样在压缩后找到某元素呢？因此还必须给出压缩前的下标和压缩后下标之间变换公式，才能使压缩存储变得有意义。
5.3.1 对称矩阵
若一个n阶方阵A中元素满足条件：aij=aji，其中1 ≤i, j≤n，则称A为对称矩阵。
5.3.2 三角矩阵
（1）上三角矩阵
矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0。
（2）下三角矩阵
矩阵的下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0。
三角矩阵的存储与对称矩阵的存储类似，不同之处在于存完上三角（或下三角）中的元素之后，紧接着存储对角线另一方的常量。因为是同一个常数，所以只存一个元素，即只要增加一个存储单元即可，这样一共存储了n*(n+1)/2+1个元素。
