数组和稀疏矩阵

数组具有以下性质：
(1) 数组中的数据元素数目固定。一旦定义了一个数组,其数据元素数目不再有增减变化。
(2) 数组中的数据元素具有相同的数据类型。
(3) 数组中的每个数据元素都和一组惟一的下标值对应。
(4) 数组是一种随机存储结构。可随机存取数组中的任意数据元素。

数组的存储结构
在一维数组中,一旦a1的存储地址LOC(a1)确定,并假设每个数据元素占用k个存储单元,则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出：
LOC(ai)=LOC(a1)+(i-1)*k (0≤i≤n)
上式说明,一维数组中任一数据元素的存储地址可直接计算得到,即一维数组中任一数据元素可直接存取,因此,一维数组是一种随机存储结构。同样,二维及多维数组也满足随机存储特性。

显然,二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。以此类推,任何多维数组都可以看作一个线性表,这时线性表中的每个数据元素也是一个线性表。多维数组是线性表的推广。

对一个已知以行序为主序的计算机系统中,当二维数组第一个数据元素a1,1的存储地址LOC(a1,1)和每个数据元素所占用的存储单元k确定后,则该二维数组中任一数据元素ai,j的存储地址可由下式确定：
LOC(ai,j)=LOC(a1,1)+[(i-1)*n+(j-1)]*k
其中n为列数。

同理可推出在以列序为主序的计算机系统中有：
LOC(ai,j)=LOC(a1,1)+[(j-1)*m+(i-1)]*k
其中m为行数。

例5.1 对二维数组float a[5][4]计算：
(1) 数组a中的数组元素数目；
(2) 若数组a的起始地址为2000,且每个数组元素长度为32位(即4个字节),数组元素a[3][2]的内存地址。

解：由于C语言中数组的行、列下界均为0,该数组行上界为5-1=4,列上界为4-l=3,所以该数组的元素数目共有(4-0+1)*(3-0+1)=5*4=20个。
又由于C语言采用行序为主序的存储方式,则有：
LOC(a3,2)=LOC(a0,0)+(i*n+j)*k
=2000+(3*4+2)*4=2056

5.1.3 特殊矩阵的压缩存储
特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵,为了节省存储空间,特别是在高阶矩阵的情况下,可以利用特殊矩阵的规律,对它们进行压缩存储,也就是说,使多个相同的非零元素共享同一个存储单元,对零元素不分配存储空间。
特殊矩阵的主要形式有对称矩阵、对角矩阵等,它们都是方阵,即行数和列数相同。