引子 – 数组的存储结构

阿Q注：下标都从0开始，L为元素所占的存储单元
一维数组：
A[n]， LOC(ai) = LOC(a0) + (i – 0) 第i个位置前有多少元素-不包括自身 * L

二维数组：
A[m][n]
按行优先：LOC(ai,j) = LOC(a0,0) + ( n * i + j ）* L
按列优先：LOC(ai,j) = LOC(a0,0) + (m * j + i ) * L

三维数组：
A[p][m][n]
页->行->列：LOC(ax,y,z) = LOC(a0,0,0) + (x * m * n + y * n + z) * L

阿Q：ai,j 推导在一维数组的位置k时，要注意三点：

①、矩阵的最小下标是1还是0（a0,0 / a1,1）

②、数组的下标是1还是0（A[0 .. n] / A[1 … n]）

③、矩阵按行优先还是列优先，是选择上三角还是下三角

阿Q：数组一经定义，结构不可变，因此不做增删操作哦！

对称矩阵

n * n 矩阵 ——存入——> A[0 … {(n + 1) * n]/2 -1}] ( 定义 A[n * (n + 1) / 2] )

三角矩阵

与对称矩阵完全一样，就是多了一个存储单元（在一维数组末存 `上三角/下三角` 相同的元素c）。

n * n 矩阵 ——存入——> A[0 … {n * (n + 1) / 2} ] ( 定义 A[n * (n + 1) / 2 + 1] )

三对角矩阵

阿Q提问：

已知 ai,j，可得到 其在一维数组中存储的位置 k = 2i + j – 3; 那么知道 k ，怎么反推出 ai,j呢?

稀疏矩阵

δ = 矩阵非零元素个数 / 行 * 列 = t / (m * n) <= 0.05，则称为稀疏矩阵 （也就是绝大部分都存了0）

稀疏矩阵的存储方式

三元组表 – 二维数组存储

此时的修改操作 可能 会导致三元组的前移或后移 （情况：0 -> 非零 / 非零 -> 0）

十字链表

如果以三元组存，那改查都很复杂。

阿Q吐槽：其实修改操作也蛮复杂的，将一个零改为非零，那就得维护 该行和该列的头指针 + 当前结点的指针 + 前驱结点的指针 （头要炸了）

阿Q 觉得将稀疏矩阵压缩 属于是 以时间换空间（但是最近空间还是那么值钱嘛？），现在基本都是以空间换时间吧（什么省时用什么）