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<n）行上恰好有n-m个元素，按行优先顺序存储上三角矩阵中元素a_{ij}时，a _{ij}之前有i行（0~i-1），一共有元素个数：
∑
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<j时，下三角矩阵中仅有一个存储位置。因此，该对应关系为：
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\ \ \ \ \ \ \ \ i<j，\ \ \ \ \ \ \ \ 2}
k={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。
|