数组的存储
假如有一个二维数组a[m][n]，第一个数据元素a[0][0] 存储地址为 loc(a[0][0])，每个元素所占存储单元为k，则按行存储
loc(a[i][j]) = loc(a[0][0]) + ( i*n + j) * k
同理可得按列存储
loc(a[i][j]) = loc(a[0][0]) +?( j*m +?i) * k
图解
?例：
特殊矩阵的压缩
(1)第一类：特殊矩阵的压缩存储
(2)第二类：稀疏矩阵的压缩存储(三元组表的存储结构、十字链表的存储结构)?
?
特殊矩阵：
0元素或非0元素的分布具有一定的规律，比如对称矩阵、三角矩阵、对角矩阵
因此，特殊矩阵的压缩就是对所有的非0元素分配一个存储空间，0元素不分配
1、 对称矩阵的压缩?
对称矩阵： 对角线两边元素相等
矩阵中的元素满足a[i][j] = a[j][i] 的矩阵称之为对称矩阵（矩阵必须是方阵)
?
按行
（1）如果存储的是主对角线+下三角，且从a[1][1]开始，推出公式后由于一维数组的存储从0开始，所以我们再-1
比如我现在只存下半部分，因为第一行有一个元素，第二行两个元素....第n行n个元素类推，一共就是n(n-1)/2个，但是由于下标从0开始，所以最后一个元素的下标是n(n-1)/2-1
数组大小如图：
?
如果存储的是主对角线+上三角：（一样的反过来）?
总结：
?将一个对称矩阵高效的存储在一维数组的情况如图：【注意三个关键位置】
按列
如果表示a[i][j]，那么第一列有n个，第二列有n-1个，以此类推，j之前会有j-1列
第j列，用行号减去列号就可以知道它之前还有i-j个元素，再加上a[i][j]自己
n+(n-1)+(n-2)+.....+n-[(j-1)-1] + (i-j) + 1
最后再根据一维数组的下标是从几开始确定是不是要-1
数组大小：
2、三角矩阵的压缩
c可为0
以上三角为例，上三角每个元素存储在一维后位置如图，C常熟都是一样的所以我们只存一个就好，它的下标为n(n+1)/2
下三角矩阵?
下三角的坐标和对称矩阵的规律一样
而上三角的元素，因为都是常数，所以它的下标我们通通记为n(n+1)/2
上三角矩阵?
第一行有n个，第二行n-1个，所以第i-1行就有n-(i-1-1)，第i行有j-i个元素
可以看成是首项为n，尾项是n-i+2，一共是i-1个，由等差数列求和公式可知?
?
?3、对角矩阵的压缩
只有中间带状部分有值，其余位置都是0
以三对角为例，如下图：
可以发现，观察可知，第一行和最后一行只有两个非0元素，其余都是三行
所以如果有n行的话，所有的非0元素就是3n-2（头尾各少一个）
存储到一维数组中，由于下标从0开始，所以a[n][n]存储过来就是3n-3
所以，分两种情况：?
（1）由于当 | i-j | >1时，a[i][j]=0，所以这些元素不必讨论不存一维数组中
（2）当 | i-j |≤1时 ，前i-1行每行都是3个，除了第一行少了一个，所以是3(i-1)-1
若已知一维数组下标，求i、j??
因为B[k] 代表的是第k+1个元素，所以第k+1个元素首先要大于它前面i-1行的元素，并且小于前i行的所有元素，解出来就是一个i的不等式，然后我们向上取整就知道了行数
知道了 i 后，又由于前面推出来的公式k=2i+j-3，所以可推出 j 的表达式 j=k-2i+3，最终得到 i 和 j
稀疏矩阵
非零元素个数远远小于矩阵元素的个数
1、三元组表的存储结构
定义一个三元组<行 列 值>
然后我们可以定义许多个struct{? int i
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int j
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int?v}? ?，每一个struct里包含一个非零数
n个struct结构构成一个一维数组
?缺点： 如果访问其中某一个元素，必须逐个扫描，失去了随机存取的特性
2、十字链表法
十字链表为每一行和每一列都单独设置了链表，这样每一个非零元素就同时包含在了两个链表中，这就大大降低了链表长度，down和right分别为向下指针和向右指针，用来连接同列和同行中的下一个非零元素
注意：?
头节点个数：
m行n列十字链表表示时，每行有一个头节点，每列有一个头节点，且同行和同列的头节点是共享的，另外再加上一个总的头节点，所以头节点个数为MAX{m,n}+1
单链表个数：?
每一行元素都会构成一个单链表所以一共m个，每一列元素也会构成一个单链表共n个，并且所有的头节点也会构成一个单链表，所以总的单链表个数是m+n+1?