【DSaAA】矩阵和广义表

约定不等于承诺〃 2022-05-25 13:41 199阅读 0赞

# 矩阵和广义表 #

*  矩阵和广义表
    
     *  二维数组
     *  ADT
     *  简单矩阵
     *  对称矩阵
     *  稀疏矩阵
     *  对角矩阵
     *  矩阵的应用场景
     *  广义表

## 二维数组 ##

数组是在逻辑和物理上都相邻的一组有序数据，二维数组是一组在逻辑和物理上都相邻的一维数组。二维数组展开就是矩阵，一般的矩阵都可以用一个维维数组表示，但是针对一些特殊的二维数组，可以用更少的空间来存储，达到压缩的目的。

## ADT ##

假设矩阵的操作只有初始化和打印。

## 简单矩阵 ##

简单矩阵直接使用二维数组存储：[SimpleMatrix.java][]

## 对称矩阵 ##

对称矩阵是沿主对角线（左上到右下）对称的矩阵，这种矩阵只需要存储上三角或下三角就可以推导出另外一半，这一半的数据（包括对角线上的数据）直接存储在一维数组中。

可以算出一维数组`s[k]`的元素个数为n(n\+1)2  n ( n + 1 ) 2 个，那么对于矩阵中的元素aij  a i j ，有  
aij=aji=smax(i,j)∗(max(i,j)\+1)/2\+min(i,j)  a i j = a j i = s m a x ( i , j ) ∗ ( m a x ( i , j ) + 1 ) / 2 + m i n ( i , j )

最终矩阵存储的数据大约只有整个矩阵的一半：[SymmetricMatrix.java][]

## 稀疏矩阵 ##

稀疏矩阵是矩阵中大部分元素都是`null`或`0`，只需要记录非`0`元素的位置就可以了，可以用一个三列的数组`data[n][3]`来记录。其中`n`是矩阵中非`0(null)`元素的个数`+1`，`+1`是因为第一行需要记录矩阵的行列数和非`0`元素个数，这样才能在打印时确定矩阵的行列；其余行的前两列是元素在矩阵中对应的行列坐标，最后一列是坐标上的具体元素：[SparseMatrix.java][]

## 对角矩阵 ##

对角矩阵是只有主对角线上有非`0(null)`元素的矩阵，这就非常明显了，只需要记录对角线上的元素即可：[DiagonalMatrix.java][]

## 矩阵的应用场景 ##

图像处理方面用的很多，平时应用开发过程中用的不多，如果仅仅是存储数据，很多情况都可以简化为一维表，如果需要做矩阵相关的计算，才会使用到矩阵，目前没有特别使用过矩阵的场景。

## 广义表 ##

如果表中的所有元素都是原子的、不可再分的非集合元素，这个表就是线性表；如果某个元素是一个可分的集合元素，那么这样的“线性表”成为广义表。

广义表由于元素在广度上的不确定性，就像是稀疏矩阵一样，如果使用数组存储，将浪费很多空间，所以一般都使用链式存储。

诸如树、图、散列等都是广义表，后面的数据结构都是对广义表的研究。

[SimpleMatrix.java]: https://github.com/clyoudu/dsaaa/blob/master/src/main/java/github/clyoudu/matrix/SimpleMatrix.java
[SymmetricMatrix.java]: https://github.com/clyoudu/dsaaa/blob/master/src/main/java/github/clyoudu/matrix/SymmetricMatrix.java
[SparseMatrix.java]: https://github.com/clyoudu/dsaaa/blob/master/src/main/java/github/clyoudu/matrix/SparseMatrix.java
[DiagonalMatrix.java]: https://github.com/clyoudu/dsaaa/blob/master/src/main/java/github/clyoudu/matrix/DiagonalMatrix.java