FORTRANI的列优先存储 a 11c311 k11 8121 a321…8k21 a m a112a212 a312 k12 a122a222a322 k22 a aRme 3 m2 a 11n 21n a 31n kln a 12n a 32n a 2mn a IIn 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 11
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 FORTRAN FORTRAN的列优先存储 a111 a211 a311 … ak11 a121 a221 a321 … ak21 ………………………… a1m1 a2m1 a3m1 … akm1 a112 a212 a312 … ak12 a122 a222 a322 … ak22 ………………………… a1m2 a2m2 a3m2 … akm2 ┇ a11n a21n a31n … ak1n a12n a22n a32n … ak2n ………………………… a1mn a2mn a3mn … akmn 12 3 k C 1 2 m 2 2 2 2 2 2 2 2 2 2 2 2
■C++多维数组 ELEM Ald[d2].[dn loc([1,2,…,jn])=loc(4[0,0…,0]) 2 +12 =(40…0)d②自4+m 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 12
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 C++多维数组ELEM A[d ELEM A[d1][ d2]…[dn]; 1 2 12 23 1 1 1 1 ( [ , , , ]) ( [0,0, ,0]) [ ] ( [0,0, ,0]) [ ] n n n n nn n n i kn i k i loc A j j j loc A d jd d j d d jdj loc A d j d j − − = = + = +⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ ++ ⋅+ = +⋅ + ∑ ∏ … … … … … …
用数组表示特殊矩阵 三角矩阵:上三角、下三角 对称矩阵 ■对角矩阵 ■稀疏矩阵 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 13
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 用数组表示特殊矩阵 三角矩阵：上三角、下三角 对称矩阵 对角矩阵 稀疏矩阵
下三角矩阵图例 一维数组list[0..(n2+n)/2-1] n矩阵元素a::与线性表相应元素的对应位置为 list[(12+1)/2+j](i>=j) 0 750 0010 900 8 062207 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 14
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 下三角矩阵图例 一维数组list[0..(n2+n)/2-1] 矩阵元素ai,j与线性表相应元素的对应位置为 list[(i2+i)/2 + j]（i>=j） 0 0 0 7 5 0 0 0 1 0 9 0 0 1 8 0 6 2 2 0 7
03015 3040 对称矩阵 0406 15060 元素满足性质a1=a1;0<=(i,j)<n 例如无向图的相邻矩阵 ■存储其下三角的值,对称关系映射 ■存储于一维数组sa0.n(n+1)/2-1 asak和矩阵元a1;之间存在着一一对应的关 系 j(j+1)+i 当 i(i+ 当i 2 北京大学信息学院张铭编写 版权所有,转载或翻印必究 Page 15
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 对称矩阵 元素满足性质 ai,j=aj,i ，0<= （i, j ）<n 例如无向图的相邻矩阵 存储其下三角的值，对称关系映射 存储于一维数组sa[0..n(n+1)/2-1] sa[k]和矩阵元 ai,j之间存在着一一对应的关 系 ： ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + ≥ + + < + = j i j i i i i j j j k 当 当 , 2 ( 1 ) , 2 ( 1 ) 3 15 3 4 4 0 0 0 0 0 0 0 0 6 15 6 ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦