矩阵

压缩存储的矩阵可以分为特殊矩阵和稀疏矩阵。对于那些具有相同元素或零元素在矩阵中分布具有一定规律的矩阵，被称之为特殊矩阵。对于那些零元素数据远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称之为稀疏矩阵。

k维数组的行主映射和列主映射

行主映射map(i1, i2, ..., ik) = i1 u2 u3 ... uk + i2 u3 ... uk + ... + ik-2 uk-1 uk + ik-1 uk + ik

列主映射 map(i1, i2, i3, i4) = i4 u3 u2 u1 + i3 u2 u1 + i2 u1 + i1

特殊矩阵——三对角矩阵

三对角矩阵的概念 三对角矩阵就是对角线、邻近对角线的上下次对角线上有元素，其他位置均为0的矩阵。三对角矩阵是一种特殊的上Hessenberg矩阵(这个就是上三角矩阵加上下三角部分的第一条次对角线有元素，其他都为0元素)。
三对角矩阵的特性 设一个n*n的方阵A，对于矩阵A中的任一元素aijaij，当|i-j|>1时，有aij=0(0≤i≤n−1，0≤j≤n−1)aij=0(0≤i≤n−1，0≤j≤n−1)时，矩阵A为三对角矩阵。三对角矩阵中除主对角线及在主对角线上下最邻近的两条对角线上的元素外，所有其他元素均为0。
三对角矩阵的压缩存储 可以利用三对角矩阵的上述特性，只存储主对角线及其上、下两侧次对角线上的元素，其他的零元素一律不存储。对一个nn的三对角方阵A，元素总数有n2n2个，而其中非零的元素共有3n-2个。因此，存储三对角矩阵时最多只需存储3*n-2个元素。

可以仿照对称矩阵的压缩存储，可用一维数组B存储三对角矩阵A(这要区分两种存储方式：行优先方式和列优先方式)。

(1)行优先方式存储

(2)列优先方式存储

(3)补充：对角线

特殊矩阵——对称矩阵

对称矩阵的概念元素以主对角线为对称轴对应相等的矩阵。
对称矩阵的特性对角矩阵都是对称矩阵，对称矩阵必须是方形矩阵。设一个n*n的方阵A，对于矩阵A中的任一元素aijaij，当且仅当aijaij=ajiaji时(0≤i≤n-1，0≤j≤n-1)时，矩阵A为对称矩阵。
对称矩阵的压缩存储可以利用对称矩阵的上述特性，只存储对角线及对角线以下的元素，或者只存储对角线及对角线以上的元素，前者称之为下三角阵，后者称之为上三角阵。

对一个nn的对称方阵A，元素总数有n2n2个，而上三角阵或下三角阵的元素共有n+(n-1)+(n-2)+……+2+1=n(n+1)/2个元素。因此，存储对称方阵时最多只需存储n*(n+1)/2个元素。利用对称矩阵的对称性，可以用一维数组B存储对称矩阵A(这主要要区分四种存储方式：行优先方式存储下三角阵、行优先方式存储上三角阵、列优先方式存储下三角阵和列优先方式存储上三角阵)。 (1)行优先方式存储下三角阵

(2)行优先方式存储上三角阵

(3)列优先方式存储下三角阵

(4)列优先方式存储上三角阵

稀疏矩阵

非零元素远远少于矩阵元素个数

![](D:\myknowledgeworld\算法与数据结构\images\屏幕截图 2022-11-05 003506.png)

![](D:\myknowledgeworld\算法与数据结构\images\屏幕截图 2022-11-05 003742.png)

public static int[] generateRandomArray(int maxSize, int maxValue) {
        // 大小在[1, maxSize]范围的随机数组
        int[] arr = new int[(int)((maxSize + 1) * Math.random())];
        // 向数组中填充随机数,范围时-maxValue到maxValue
        for(int i = 0; i < arr.length; i++) {
            arr[i] = (int)((maxValue + 1) * Math.random()) - (int)((maxValue + 1) * Math.random());
        }
        return arr;
    }