数据结构 数组

1.多维数组的存储
2.特殊矩阵(数组)的压缩存储
3.数组的应用

定义与地址计算

数组是由n(n>1)个具有相同数据类型的数据元素a1,a2,...,an组成的有序序列，且该序列必须存储在一块地址连续的存储单元中。

• 数组中的数据元素具有相同数据类型。
• 数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。
• 数组中的数据元素个数是固定的。

通常有两种顺序存储方式：

1. 行优先顺序 Row Major Order
   LOC(amj)=LOC(a11) + (m-1)nl + (j-1)*l,j=1,2,...,n
2. 列优先顺序 Column Major Order
   LOC(ajn)=LOC(a11) + (n-1)ml + (j-1)*l,j=1,2,...,m

二维数组中任一元素aij的(首)地址为
LOC(aij)=LOC(a11) + [(j-1)m + (i-1)]l, i=1,2,...,n ,j=1,2,...,m // ??????

特殊矩阵(数组)的压缩存储

非零元素或非零元素的分布有一定规律的矩阵。

对称矩阵

n^2个元素压缩到 n(n+1)/2

对称矩阵元素aij保存在向量sa中时的下标值k与(i,j)之间的对应关系为：
k= i(i-1)/2 +j-1, 当i>=j时 1<=i,j<=n
k= j(j-1)/2 +i-1, 当i<j时 1<=i,j<=n

三角矩阵

以主对角线划分，上三角矩阵、下三角矩阵

下三角矩阵元素aij保存在向量sa中时的下标值k与(i,j)之间的对应关系为：
k= i(i-1)/2 +j-1, 当i>=j时 1<=i,j<=n
k= n(n+1)/2, 当i<j时 1<=i,j<=n

上三角矩阵元素aij保存在向量sa中时的下标值k与(i,j)之间的对应关系为：
k= (i-1)(2n-i+2)/2 +j-i, 当i>=j时 1<=i,j<=n
k= n(n+1)/2, 当i<j时 1<=i,j<=n

对角矩阵

LOC[aij] = LOC[a11] + [3(i-1)-1 + (j-i+1)]l