用数组表示特殊矩阵 下三角矩阵图例 三角矩阵:上三角、下三角 一维数组list[0.(n2+n)/2-1] 1+2:G> 应元素的对应位量为 ■对称矩阵 对角矩阵 ■稀疏矩阵 7090 0102 帖國写 03015 3040 对称矩阵 0406 对角矩阵 元素满足性质aa1,0(j)60 对角矩阵是指所有的非零元亲都集中在主对角 例如无向图的相邻矩阵 线及以它为中心的其他对角线上。如果 存储其下三角的值,对称关系映射 ij1,那么数组元素 aille=0。 ■存储于一维数组sa0.n(n+1)2-1 下面是一个3对角矩阵 sa和矩阵元之间存在着一一对应的关 f(+1) 北京大息啦_张铭写 权有。印乡究 北大啦孔写 叔新有命剑 稀疏矩阵 稀疏矩阵中的非零元素非常少,而且分布也不 ■稀疏因子 规律 0007005 雋为的矩阵中,有个非零元票,则稀疏 01500000 m xn 当这个值小于005时,可以认为是稀疏矩阵 三元组〔i,j,a1):输入/输出常用 078000220 1是该元素的行 j是该元素的列号 是该元素的值 00420 北大学到3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 用数组表示特殊矩阵 „ 三角矩阵：上三角、下三角 „ 对称矩阵 „ 对角矩阵 „ 稀疏矩阵 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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 ⎡ ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 对角矩阵 „ 对角矩阵是指所有的非零元素都集中在主对角 线及以它为中心的其他对角线上。如果 |i-j|>1，那么数组元素a[i][j]=0。 „ 下面是一个3对角矩阵： a0,0 a1,1 a0,1 a1,0 an-1,n-2 an-1,n-1 an-2,n-1 a1,2 0 0 …… …… …… 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 稀疏矩阵 „ 稀疏矩阵中的非零元素非常少，而且分布也不 规律 × ⎛ ⎞ ⎜ ⎟ − = ⎝ ⎠ 6 7 0 0 0 7005 0 15 0 0 0 0 0 0 0 0 6 0 17 0 A 0 78 0 0 0 22 0 11 0 0 0 0 0 0 0 0 42 0 0 0 0 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 „ 稀疏因子 „ 在m ×n的矩阵中，有t个非零元素，则稀疏 因子为: „ 当这个值小于0.05时，可以认为是稀疏矩阵 „ 三元组(i, j, aij )：输入/输出常用 „ i是该元素的行号 „ j是该元素的列号 „ aij是该元素的值 m n t × δ =