如何只存储下三角部分?对下三角部分以行为主序顺序 存储到一个向量中去,在下三角中共有n*(n+1)2个元素, 因此,不失一般性,设存储到向量SA[n+1)2]中,存储 顺序可用下图示意,这样,原矩阵下三角中的某一个元素 a则具体对应一个sa,下面的问题是要找到与、记之间的 关系。 n(n+1)2-1 21 22 32 第1行 第2 第3行 第n行 般对称矩阵的压縮存储 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 16 • 如何只存储下三角部分？对下三角部分以行为主序顺序 存储到一个向量中去，在下三角中共有n*(n+1)/2个元素， 因此，不失一般性，设存储到向量SA[n(n+1)/2]中，存储 顺序可用下图示意，这样，原矩阵下三角中的某一个元素 aij则具体对应一个sak，下面的问题是要找到k与i、j之间的 关系
对于下三角中的元素a,其特点是:且1m,存储到 4SA中后,根据存储原则,它前面有1行,共有1+2++ 1=i*(1)2个元素,而a1又是它所在的行中的第j个,所以 在上面的排列顺序中,a1是第(1)2个元素,因此它在 SA中的下标k与i、j的关系为: k=i*(-1)2+j-1(0<k<n*(n+1)/2) ·若i,则是上三角中的元素,因为=41,这样,访问 上三角中的元素a时则去访问和它对应的下三角中的a1即 可,因此将上式中的行列下标交换就是上三角中的元素在 SA中的对应关系: kj*(j-1)2+-1(0<kn*(n+1)/2) 综上所述,对于对称矩阵中的任意元素a1,若令 I=max(ij),J=min(ij),则将上面两个式子综合起来得到: k=1*(1-1)2+J-1。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 17 • 对于下三角中的元素aij，其特点是：i≥j且1≤i≤n，存储到 SA中后，根据存储原则，它前面有i-1行，共有1+2+…+i- 1=i*(i-1)/2个元素，而aij又是它所在的行中的第j个，所以 在上面的排列顺序中，aij是第i*(i-1)/2+j个元素，因此它在 SA中的下标k与i、j的关系为： k=i*(i-1)/2+j-1 (０≤k<n*(n+1)/2 ) • 若i<j，则aij是上三角中的元素，因为aij=aji ，这样，访问 上三角中的元素aij时则去访问和它对应的下三角中的aji即 可，因此将上式中的行列下标交换就是上三角中的元素在 SA中的对应关系： k=j*(j-1)/2+i-1 (０≤k<n*(n+1)/2 ) 综上所述 ，对 于 对 称矩 阵 中的 任 意 元素 aij ， 若 令 I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到： k=I*(I-1)/2+J-1
522三角矩阵 ◆形如下图的矩阵称为三角矩阵,其中C为某个常数。其 中(a)为下三角矩阵:主对角线以上均为同一个常数;(b) 为上三角矩阵,主对角线以下均为同一个常数;下面讨 论它们的压缩存储方法。 36 CC CC 3481n CCC C2946 48 CC Cc157 7460c CC C0 8 8295 (a)下三角矩阵 b)上三角矩阵 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 18 5.2.2 三角矩阵 形如下图的矩阵称为三角矩阵，其中c为某个常数。其 中(a)为下三角矩阵：主对角线以上均为同一个常数；(b) 为上三角矩阵，主对角线以下均为同一个常数；下面讨 论它们的压缩存储方法
1.下三角矩阵 与对称矩阵类似,不同之处在于存完下三角中的元素 中之后,紧接着存储对角线上方的常量,因为是同一个常 数,所以存一个即可,这样一共存储了n*(n+1)+1个元素, 设存入向量:SAn+(m+1)1中,这种的存储方式可节约 n*(n1)-1个存储单元,sak与a1的对应关系为: *(-1)/2+-1当诊j n"(n+1)/2 当 n(n+12 11 22a31a32|a3 第1行 第2行第3行 第n行 下三角矩阵的压缩存储 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 19 1. 下三角矩阵 与对称矩阵类似，不同之处在于存完下三角中的元素 之后，紧接着存储对角线上方的常量，因为是同一个常 数，所以存一个即可，这样一共存储了n*(n+1)+1个元素， 设存入向量：SA[n*(n+1)+1]中，这种的存储方式可节约 n*(n-1)-1个存储单元，sak 与aji 的对应关系为：
2.上三角矩阵 对于上三角矩阵,存储思想与下三角类似,以行为主序 顺序存储上三角部分,最后存储对角线下方的常量。对于 第1行,存储n个元素,第2行存储n-1个元素,…,第p行存 储(n-p+1)个元素,a的前面有i1行,共存储 n+(n-1)++(n-+1)>(x-P)+1=(1-1)+(2n1+2)/2 个元素,a1是它所在的行中要存储的第(ji+1)个也就是 上三角存储顺序中的第(1)(2n1计2)2+(+1)个,因此它 在SA中的下标为:k=(i-1)+(2n-+2)2+ji 综上,s与a1的对应关系为 1)(2n+2)/2+j1当 n(n+1)2 当 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 20 2. 上三角矩阵 对于上三角矩阵，存储思想与下三角类似，以行为主序 顺序存储上三角部分，最后存储对角线下方的常量。对于 第1行，存储n个元素，第2行存储n-1个元素，…，第p行存 储(n-p+1)个元素，aij的前面有i-1行，共存储： 个元素，aij 是它所在的行中要存储的第（j-i+1）个也就是 上三角存储顺序中的第 (i-1)*(2n-i+2)/2+(j-i+1)个，因此它 在SA中的下标为：k=(i-1)*(2n-i+2)/2+j-i。 综上， sak 与aji 的对应关系为：