特殊矩阵的压缩存储

发表于   |   分类于

特殊矩阵有对称矩阵, 上三角, 下三角矩阵.

一. 对称矩阵的压缩存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>

/*
2017年11月8日 21:00:38
对称矩阵的压缩存储:
    矩阵应该是用二维数组存储, 但是由于对称矩阵的特殊性, 有一些元素是重复的.
    所以根据对称矩阵的特点, 把部分元素存储起来即可.
    这里是打印出该矩阵, 主要是想体现:
        当要取矩阵中某个元素的时候, 根据公式可以知道该元素在数组中的位置, 即还原出对称矩阵. 
        (推导过程用到等差数列的知识)
        k = i(i+1)/2+j;   --> i>=j
        k = j(j+1)/2+i;   --> i<j
*/

int main(int argc, char const *argv[])
{
    //用一个一维数组存储二维矩阵. i, j 是对称矩阵的行和列
    int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, i, j;

    for(i=0; i<4; i++)
    {
        for(j=0; j<4; j++)
        {
            if(i>=j)
            {
                printf("%d ", a[i*(i+1)/2+j]);
            }
            else
            {
                printf("%d ", a[j*(j+1)/2+i]);
            }
        }
        printf("\n");
    }
    
    return 0;
}

二. 上三角矩阵的压缩存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>

/*
2017年11月8日 21:22:05
上三角矩阵的压缩存储:
    与对称矩阵一样, 为了节省空间, 用一个一维数组存储上三角矩阵.
    一维数组第一个元素是下方重复出现的元素, 其余是上三角中的元素.
    通过输出矩阵来体现上三角矩阵的还原, 同样是用公式(我并不知道公式怎么来的):
    k = 0;   --> i>j
    k = i(2n-i+1)/2+j-i+1;   --> i<=j  (n 是阶数)
*/

int main(int argc, char const *argv[])
{
    //用一个一维数组存储上三角矩阵. i, j 是对称矩阵的行和列
    int a[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, i, j;
    for(i=0; i<4; i++)
    {
        for(j=0; j<4; j++)
        {
            if(i<=j)
            {
                printf("%d ", a[i*(2*4-i+1)/2+j-i+1]);
            }
            else
            {
                printf("%d ", a[0]);
            }
        }
        printf("\n");
    }
    
    return 0;
}

三. 下三角矩阵的压缩存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>

/*
2017年11月8日 21:33:09
下三角矩阵的压缩存储:
    同样使用是公式, 同样是不会求公式.
*/

int main(int argc, char const *argv[])
{
    int a[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, i, j;

    for(i=0; i<4; i++)
    {
        for(j=0; j<4; j++)
        {
            if(i<j)
            {
                printf("%d ", a[0]);
            }
            else
            {
                printf("%d ", a[(i*(i+1)/2+j+1)]);
            }
        }
        printf("\n");
    }
    
    return 0;
}

四. 总结

  • 压缩存储的目的都是为了节省存储空间.
  • 上面三种矩阵的压缩存储都是将元素放入一维数组中, 当要还原矩阵的时候, 根据公式, 取出一维数组中对应位置的元素.
  • 公式比较特殊的是上三角矩阵, 其他是用到等差数列求和公式来推导.