矩阵
一、对称矩阵
- 定义：矩阵元素
aij = aji; -
一维数组存储
对称矩阵存储方式
如图所示，由于对称矩阵的对称性，我们使用二维数组存储，会使得二维数组重复存储一部分数据，我们可以使用逻辑处理来节省这部分重复数据。
- 处理方式
我们按照行存储来存储三角区域元素, 包含了对角线，下三角区域。 - 解决两个问题
1.存储的数据多大?
第一行有:1
第二行有:2
第三行有:3
第n行有:n
总共有:1+2+3+4....+n = (1+n)n/2个元素.
2.元素aij对应一维数组存储的index是多少？
i:行，j:列，按行存储 =>index =( 1+i-1)(i-1)/2 + j-1 = i(i-1)/2 + j - 1，注意元素从a11开始的。
3.上三角怎么逻辑处理？
由于aij = aji=>index上三角 = j(j-1)/2 + i -1
4.总结
index下三角=( 1+i-1)(i-1)/2 + j-1 = i(i-1)/2 + j - 1
index上三角= j(j-1)/2 + i -1
二、上下三角矩阵
-
下三角矩阵定义： 除了主对角线和下三角区，其余元素都相同
下三角矩阵，c为常数 解决问题
1.如何存储常数项,因为数组从零开始所以存储下三角，最后一个元素，索引为(1+n)*n/2 -1，故常数项存储位置为(1+n)*n/2。
2.如何存储下三角？
按行存储，和对称矩阵下三角是一样的
index下三角=( 1+i-1)(i-1)/2 + j-1 = i(i-1)/2 + j - 1-
上三角矩阵定义：除了主对角线和上三角区，其余元素都相同。
上三角矩阵 解决问题
1.如何存储？
第一行：有n个
第二行：有n-1个
第n行：有1个
总计：(1+n)n/2个，故常数部分存储index为(1+n)n/2
第aij元素存储位置：
index上三角 = (n-(i-1) + 1 + n) * (i-1)/2 + j-i = (2n-i+2)(i-1)/2 + j -i
三、三对角矩阵
-
定义：|i-j| > 1 时，有aij = 0 （i>=1,j<=n）
对三角矩阵 - 如何存储
1.只需要存储带区域中的元素，
总共有：3*n-2个元素，一共n行，首行末行均为2个。
2.第aij元素对应的index为？
index =3*(i-1)-1 + j-i+2 -1 = 2i+j-3
3.知道数组中索引为k的元素如何推出时aij中的i和j?
索引为k，对应的是k+1个元素
第i-1行有3*(i-1)-1个元素
第i行有3i-1个元素
3(i-1) < k+1<=3i-1 => i = k+2/3向上取整.
因为k = 2i+j-3联立可得j = k-2i +3
四、稀疏矩阵
-
定义： 非零元素远远小于矩阵元素的个数.
稀疏矩阵 - 存储方式
1.三元组<行，列，值> 不支持随机存储
2.十字链表 支持随机存储.
