数据结构 数组
1.多维数组的存储
2.特殊矩阵(数组)的压缩存储
3.数组的应用
定义与地址计算
数组是由n(n>1)个具有相同数据类型的数据元素a1,a2,...,an组成的有序序列,且该序列必须存储在一块地址连续的存储单元中。
- 数组中的数据元素具有相同数据类型。
- 数组是一种随机存取结构,给定一组下标,就可以访问与其对应的数据元素。
- 数组中的数据元素个数是固定的。
通常有两种顺序存储方式:
- 行优先顺序 Row Major Order
LOC(amj)=LOC(a11) + (m-1)nl + (j-1)*l,j=1,2,...,n - 列优先顺序 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
标签:LOC,...,元素,矩阵,数组,aij,数据结构,408 From: https://www.cnblogs.com/yongchao/p/17157247.html