数组和矩阵

数组

定义

这里所说的数组即是我们大家所通常使用的数组。

性质

• 数组中的数据元素数目固定（即数组定长）。
• 数组中的数据元素具有相同的数据类型。
• 数组中的每个元素都和一组唯一的下标值对应。
• 数组是一种随机存储结构，可以随机存取数组中的任意数据元素。

映射顺序

映射方式有两种，分别是行主映射和列主映射，简单的看，即行主映射是横着看，列主映射是竖着看。

在大部分情况下，我们还是使用行主映射。

上述的区别主要是在地址的计算当中。比较简单，不再进行过多的阐述。

矩阵

矩阵大家可以理解成数学中的矩阵，在这个内容当中，主要涉及的是特殊矩阵的存储方式（考虑如何才能节约空间）。

定义

一个 m x n 的矩阵是一个 m 行、n 列的表，其中 m 和 n 是矩阵的维数。

矩阵类 matrix 的声明如下：

压缩存储

由于矩阵本身维度较大，且矩阵中可能会有大量的非零元素和零元素，因此矩阵有2个压缩存储原则：

• 零元素不分配存储空间；
• 多个相同的非零元素只分配一个存储空间。

对角矩阵

M 是一个对角矩阵，当且仅当 i ≠ j 时， M(i, j ) = 0 。

若使用二维数组进行存储，则需要 $rows^2$个类型为T的数据空间，然而在对角矩阵中至多只有 rows 个非0 的元素，因此没有必要将其他数值为 0 的元素存储下来。可以使用一维数组 element[rows] 来对数据进行存储，其中 element[i - 1] 表示的是矩阵M(i, i ) 的元素。

三对角矩阵

与对角矩阵同理，在三对角矩阵中同样存在许多数值为 0 的元素，同时，三对角矩阵的非0元素分布也具有规律性。因此可以用一维数组进行存储，其中：

• 主对角线———i = j；
• 主对角线之下的对角线——–i = j + 1；
• 主对角线之上的对角线——-i = j - 1;

另外，在进行矩阵到数组的元素映射时，可以选择逐行映射，也可以选择逐列映射。当然，个人还是推荐逐行进行映射，一是符合普遍的思维惯性，二则是与底层的存储挂钩。

上/下三角矩阵

M是一个下（上）三角矩阵，当且仅当 i < j（i > j ） 时， M(i, j ) = 0 。

同理，对于三角矩阵，只需要存储需要存储的元素（不是），对于这两种矩阵，都可以用一个大小为 $\frac{n(n + 1)}{2}$ 的一维数组来进行存储。

对称矩阵

M 是一个对称矩阵，当且仅当对于所有的 i 和 j,M(i, j) = M(j, i)。

和三角矩阵的存储方式相同，不再赘述。

稀疏矩阵

对于 m x n 的矩阵，如果大多数元素都是 0，则被称为稀疏矩阵，反之，则是稠密矩阵。在稀疏矩阵和稠密矩阵之间没有明确的界限。

由于在稀疏矩阵中，元素的分布不像上述的特殊矩阵具有规律性，因此在使用单个线性表进行存储时，数组元素需要三个域：row（矩阵元素所在行）、col（矩阵元素所在列）和 value（矩阵元素的值）。

转置

十字链表

广义表

(待补充)

定义

广义表是 n 个元素的有限序列。记作 $LS = (a_1, a_2, a_3,……,a_n)$ 。

特点：

• 广义表的元素可以是广义表（嵌套；
• 一个广义表可以为其他多个广义表共享；
• 广义表可以是递归表。

存储结构