2014/47 §5.1多维数组 S5.1多维数组 例：行主序Ax,·A1m,1.可 ·多维推广：以C为例，行主序。 原理：a,的地址=基址+排在a,之前的元素个数×每 444→40.4-1,0.4-1，，0.d.-1] 个元素的大小 Lacta)=Loc(an)+(hxdxd.xd+jxdx.xd++jxd+j)xL Loc(a,)=Loc(an)+[(i-1)xnt(i]XL 。思考：Acd,cd] 前一1行结点总数第行上4之前的结点数 Loc(a,FLoc(aeaH匹.slX(d-c+lt-c】XL 在C语言中，Anx是[0m-1,0m-l],故有： 1山行前行数第2维长度 1h行0，之前结点数 Loc(a)=Loc(apo)+[ixnj]XL 。特点：随机存取。 S5.2矩阵的压缩存储 S5.2矩阵的压缩存储 用二维数组表示的特点：随机存取，存储密 1,对称阵 度为1。但对特殊和稀琉矩阵的存储则浪费空 n阶方阵4，若ay=a:0≤i,j≤n-L,则称4为对称阵。 间，尤其是大规模科学与工程计算。 因为矩阵元素关于主对角线对称，故只存上三角或 下三角元素即可，节约近一半空间。 55.2.1特殊矩阵 不失一般性，存储下三角（包括主对角线），以行 主序存储： 有规建：压缩后可找到地址变换公式，保持 随机存取功能。 元素个数 艺e+=a+D/2 承复元素 分布有规律 yam au an 零元素 →a0 a 85.2矩阵的压缩存储 s5.2矩阵的压缩存储 。压缩存佛： ②上三角中有1<】 将其存于向量sa0.mt1)y2一1]中。 :a:=ay,只需交换上式的和即可得 如何访问a,?必须将其与sak的对应关系找出来。 k=jU+1)/2+1 地址计算： 令=max(i,0,=min(,),则k和i,j之关系可统 ①下三角中有j≤i 一表示为：k=11+)/2+J 4y之前有行(0~-1) 2 三角矩阵 元米个数=克e+D=0+0/2 压缩方式同上，在3中多增加一个单元： sa[0..n(n+1y2] 第行上a之前元素个数为0-~1)， 将C存于最后一个分量中。 .k=i(i+0/2+j 22014/4/7 2 §5.1 多维数组 例：行主序 。 A[1..m,1..n] 原理：aij的地址=基址+排在aij之前的元素个数×每 个元素的大小 Loc(aij)=Loc(a11)+[(i-1)×n+(j-1)] ×L 7 前i-1行结点总数 第i行上aij之前的结点数 在C语言中， 是A[0..m-1 , 0..n-1]，故有： Loc(aij)=Loc(a00)+[i×n+j] ×L §5.1 多维数组  多维推广：以C为例，行主序。  思考：A[c1..d1 , c2..d2] 8 Loc(aij)=Loc(ac1c2)+[(i-c1) ×(d2-c2+1)+(j-c2)] ×L i th行前行数 第2维长度 i th行aij之前结点数  特点：随机存取。 §5.2 矩阵的压缩存储  用二维数组表示的特点：随机存取，存储密 度为1。但对特殊和稀疏矩阵的存储则浪费空 间，尤其是大规模科学与工程计算。 §5 2 1 特殊矩阵 9 §5.2.1 特殊矩阵  有规律：压缩后可找到地址变换公式，保持 随机存取功能。 §5.2 矩阵的压缩存储 1. 对称阵 n阶方阵A，若 则称A为对称阵。 因为矩阵元素关于主对角线对称，故只存上三角或 下三角元素即可，节约近一半空间。 不失一般性，存储下三角（包括主对角线），以行 10 不失 般性，存储下 角 包括 对角线 ，以行 主序存储： 元素个数 §5.2 矩阵的压缩存储  压缩存储： 将其存于向量sa[0..n(n+1)/2－1]中。 如何访问aij？必须将其与sa[k]的对应关系找出来。  地址计算： ① 下三角中有j ≤ i 11 ① 下三角中有j ≤ i. aij之前有i行（0 ~ i-1） 第i行上aij之前元素个数为j(0 ~ j-1). §5.2 矩阵的压缩存储 ② 上三角中有i < j ,只需交换上式的j和i即可得： 令I=max (i , j)，J=min (i , j)，则k和i，j之关系可统 一表示为： 12 2. 三角矩阵 压缩方式同上，在sa中多增加一个单元： sa[0..n(n+1)/2] 将C存于最后一个分量中