数据结构（其四）--特殊矩阵的存储
目录
11.特殊矩阵的压缩存储
（1）.一维数组的储存结构
（2）.二维数组的存储结构
（3）.普通矩阵的存储
（4）.特殊矩阵的压缩存储
i.对称矩阵
ii.三角矩阵
iii.三对角矩阵
iiii.稀疏矩阵
11.特殊矩阵的压缩存储
（1）.一维数组的储存结构
int a[10];
一维数组的地址是连续的，只要知道了起始地址（LOC，默认是a[0]的地址），就可以知道所有元素的地址。
a[i] 地址的计算 ：LOC + i * sizeof(int) .
注意：有时候给出的LOC可能不是a[0] 的，此时，就要在上式子的i 中减去，如给出的是a[1]的，则计算公式变为 LOC + (i - 1) * sizeof(int).
（2）.二维数组的存储结构
int b[2][4]
二维数组在内存中有两种存储方法，行优先和列优先。
当然，从逻辑视角上看，将数据配列成矩阵的样式，更方便进行操作。
有int b[M][N]，b[0][0] 的地址为LOC，则b[i][j]
行优先：LOC + (i*N + j)*sizeof(int)
列优先：LOC + (j*M + i)*sizeof(int)
（3）.普通矩阵的存储
一般是用二维数组，
需要注意的是，矩阵的下标是从(1, 1) 开始的，数组是从(0, 0) 开始的。
（4）.特殊矩阵的压缩存储
i.对称矩阵
· 是方阵（n阶），
· 恒有 aij == aji，
因为对称，所以可以只存储下三角区和对称轴（或上三角区和对称轴）（这样就是所谓的压缩存储）
按行优先将各元素存入一维数组（也可以列优先），
如此便要思考，
数组的大小，显然，第一行一个元素，第二行两个元素...第N行N个元素，总数就是n*(n+1)/2.
数据的调用，因为矩阵的下标与数组的下标规则不同，可以写一个简单的映射函数进行转换
aij => b[k]
总结上图，可知
k = (i+1)*i/2 + j - 1 ,
即当前元素行数往上为等差数列求和，再加上列数，就是在数组中的第几个元素，再减一，就成了数组下标。（如果，题干给出的数组起始下标为1，k就不需要减去那个1）
ii.三角矩阵
压缩存储策略：储存aij的三角区，将常数储存在数组最后一位。（以下三角为例）
数组大小，n*(n+1)/2 + 1.
aij的ij 与数组下标之间的相互转换与上文相同。
获取常数项，数组下标就是 n*(n+1)/2。
值得一提的，在上三角中，求aij是数组中的第几个元素，观察图可知，每行的元素数由N个依次递减。所以，aij 前面有 [n + ... + (n - i + 2)] + (j - i)个元素，中括号里的是此行往上的，那个j-i是当前行内aij 之前的元素。
iii.三对角矩阵
以行优先为例，
数组大小，3n - 2。
数组下标（对于aij），前(i - 1)行，有3(i - 1) - 1个元素(每行有三个元素，但第一行只有两个)；第i 行中，aij是第j - i + 2个元素，所以aij 就是第2i + j - 2(前后相加)。
k = 2i + j - 3
由数组下标逆推矩阵下标ij
已知b[k]
是第k + 1个元素，在前i-1行，与前i行之间，3(i - 1) - 1 < k + 1 <= 3i - 1
i >= (k + 2)/3，左式算出结果后向上取整就是i 值
（向上取整：如1.2，向上取整就是2，向下就是1）
iiii.稀疏矩阵
压缩策略：
① 顺序存储------设置一个类，其中包含三个数组，分别存储i、j、非零数据。
② 十字链表法----此为链式存储，
结点中，包含行、列、值以及两个指针。
两个指针分别指向同一列的下一个结点和同一行的下一个结点。