数据结构的学习_4.2 矩阵的压缩存储（三角矩阵）

4.2 矩阵的压缩存储（二）

4.2.1特殊矩阵

2.三角矩阵

以主对角线划分，三角矩阵有上三角和下三角两种。下三角矩阵正好相反，它的主对角线上方均为常数c或零；上三角矩阵是指矩阵的下三角（不包括对角线）中的元素均为常数c或是零的n阶方阵。一般情况下，三角矩阵的常数c均为零。

三角矩阵示意图：
[ a 00 c c . . . c a 10 a 11 c . . . c a 20 a 21 a 22 . . . . . . . . . . . . . . . . . . c a n − 10 a n − 11 a n − 12 . . . a n − 1 n − 1 ] [ a 00 a 01 a 02 . . . a 0 n − 1 c a 11 a 12 . . . a 1 n − 1 c c a 22 . . . a 2 n − 1 . . . . . . . . . . . . . . . c c c . . . a n − 1 n − 1 ] \begin{bmatrix} a_{00}&c&c&...&c \\ a_{10}&a_{11}&c&...&c\\ a_{20}&a_{21}&a_{22}&...&...\\ ...&...&...&...&c\\ a_{n-10}&a_{n-11}&a_{n-12}&...&a_{n-1n-1}\\ \end{bmatrix} \begin{bmatrix} a_{00}&a_{01}&a_{02}&...&a_{0n-1}\\ c&a_{11}&a_{12}&...&a_{1n-1}\\ c&c&a_{22}&...&a_{2n-1}\\ ...&...&...&...&...\\ c&c&c&...&a_{n-1n-1}\\ \end{bmatrix} ⎣⎢⎢⎢⎢⎡​a00​a10​a20​...an−10​​ca11​a21​...an−11​​cca22​...an−12​​...............​cc...can−1n−1​​⎦⎥⎥⎥⎥⎤​⎣⎢⎢⎢⎢⎡​a00​cc...c​a01​a11​c...c​a02​a12​a22​...c​...............​a0n−1​a1n−1​a2n−1​...an−1n−1​​⎦⎥⎥⎥⎥⎤​
​                            （a）下三角矩阵                   （b）上三角矩阵

三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩在一维数据

sa[n(n+1)/2+1]中，其中c存放在数组的最后一个元素中。

在上三角矩阵中，主对角线上第m（0≤m ∑ m = 0 i − 1 ( n + m ) = i ( 2 n − i + 1 ) / 2 \sum_{m=0}^{i-1}(n+m)=i(2n-i+1)/2 m=0∑i−1​(n+m)=i(2n−i+1)/2

来分析上面的公式，2n-i+1这个其实是n+(n-i+1)，因为是n阶方阵，上三角矩阵中，主对角线上第i行有n-i+1个元素。前面的n就是第一行元素个数。

刚开始有点懵，不知道什么情况，后面自己琢磨了下（原谅我还没开始学高等数学。。），换汤不换药，头+尾然后再乘多少对然后再除以2，这不就是1+2+…+100这个公式套用吗！

所以，n是头，n-i+1是尾。有i对，再除以2，就是元素个数。

在第i行，a_{ij}之前有j-i个元素，因此sa[k]和a _{ij}存储位置的对应关系为：
k = { n ∗ ( n + 1 ) / 2 i > j ， 2 i ∗ ( 2 n − i + 1 ) / 2 + j − i i ≤ j ， 1 k=\begin{cases} \end{cases} ^{i*(2n-i+1)/2+j-i\ \ \ \ \ \ i≤j，\ \ \ \ \ \ \ \ 1} _{n*(n+1)/2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i>j，\ \ \ \ \ \ \ \ \ \ \ \ \ 2} k={n∗(n+1)/2                i>j，             2i∗(2n−i+1)/2+j−i      i≤j，        1​

1的表达式不难看出，a_{ij}在上三角矩阵，这个比较好理解。

2的表达式也很简单，a_{ij}在下三角矩阵，开头就说了，存储在一维数组最后一个，数组从零开始的，所以求出元素个数就是它所在数组的位置。

在下三角矩阵中，sa[k]和a_{ij}存储位置对应关系与前面介绍的对称矩阵压缩存储类似，只是在当i k = { n ∗ ( n + 1 ) 2 i < j ， 2 i ∗ ( i + 1 ) 2 + j i ≥ j ， 1 k=\begin{cases} \end{cases} ^{i*(i+1)2+j\ \ \ \ \ \ i≥j，\ \ \ \ \ \ \ \ 1} _{n*(n+1)2\ \ \ \ \ \ \ \ ik={n∗(n+1)2        i<j，        2i∗(i+1)2+j      i≥j，        1​

这个应该就不用讲了，因为跟对称矩阵压缩存储一样。。。

例题

（例题·填空题）假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，若矩阵中的第一个元素
a 11 a_{11} a11​
在B中的存储位置k=0，则元素
a 55 a_{55} a55​
在B中的存储位置k=_____________。

题目说了a_{11}时第一个元素，所以a _{55}前面已经有5-1=4行，每行存储的元素个数是10，9，8，7，10+9+8+7=34个元素，因为是上三角矩阵，a _{5,5}就是第5行第一个，本来是要+1的，因为下标要减1，所以得到存储位置还要-1
k =（10 + 9 + 8 + 7）+ 1 - 1 = 34
所以 k = 34。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！