数据结构-4.1.特殊矩阵的压缩存储

一.一维数组的存储结构：

1.知道一维数组的起始地址，就可以求出任意下标对应的元素所在的地址；

2.注：如果数组下标从1开始，上述公式的i就要改为i-1；

3.数组里的元素类型相同，因此所占空间也相同。

二.二维数组的存储结构：

1.注：数组的存储是连续(计算机的存储是线性的)的，针对非线性的二维数组，为了将其拉成线性结构，就有了行优先和列优先两种存储方式；

2.将非线性的二维数组整成线性的好处就是可以实现随机存取；

3.行优先时计算存储地址：公式中i为行，j为列

4.列优先时计算存储地址：公式中i为行，j为列

三.普通矩阵的存储：

四.对称矩阵(行数=列数且关于主对角线对称)的压缩存储：

由于对称矩阵关于主对角线对称，因此在存储对称矩阵的数据时只需要存储对称的一部分即可。

以只存储主对角线+下三角区域为例：

1.数组大小即数组存储的数据个数；

2.行优先中计算某个元素是第几个元素的公式推导：i为行，j为列，i和j全从1开始(一定要注意下标起始位置)

该元素上方有i-1行，第i行有i个元素(第i-1行有i-1个元素)，因此前i-1行共有1+2+...+(i-1)个元素，

该元素所在行从第一个元素到该元素需要j个元素，所以该元素位置公式为[1+2+...+(i-1)]+j

根据对称性，下三角区域的元素将下标的行和列互换位置就可以访问上三角区域的元素：

总结：

要注意出题内容，以进行对应的分析：

五.三角矩阵的压缩存储：

1.下三角矩阵：除了主对角线和下三角区域外，都是常量且值相同；

2.上三角矩阵：除了主对角线和上三角区域外，都是常量且值相同；

3.对于是常量且值相同的那一部分，是无需重复存放那么多数据的，因此只需要处理主对角线和对应的三角区域(不是常量的一部分)即可；

4.将主对角线和对应的三角区域(不是常量的一部分)的数据存入一维数组，需要的内存大小为(1+2+...+n)+1：

公式解读：第n行有n个元素，所以n行需要1+2+...+n，最后还需要一个空间存放常量，因此

总内存大小为(1+2+...+n)+1

注：上三角区域的数据都是值相同的常量，被存放在同一个空间中，在一维数组中下标都一样

同理，对于上三角矩阵，第一行有n个元素，第二行有n-1个元素，由此可得第i行有n-(i-1)个元素

所以第i-1行有n-[(i-1)-1]=n-i+2个元素，前i-1行有1+2+...+(n-i+2)个元素

六.三对角矩阵的压缩存储：

i为行，j为列

1.存储时只需要存储三对角矩阵中的非0元素即可；

2.对于上述图片中三对角矩阵里蓝色框内的部分，第一行和最后一行只有两个元素，其他行都有三个元素，

因此，共有n行，共有2+3(n-2)+2=3n-2个元素,存储三对角矩阵的一维数组的长度为3n-2；

3.求前i-1行有几个元素时，只需要考虑第一行仅两个元素即可，因为重点在前几行，因此

前i-1行有2+3(i-1-1)=3(i-1)-1个元素

4.此时第i行就是当前行，所以小于或者等于；第i-1行就是上面的行，比他们大，不可能取等；

王道书中的k可以理解为要找的元素前总共有k个元素：

七.稀疏矩阵的压缩存储：

1.对于顺序存储稀疏矩阵，可以创建一个结构体，里面创建变量记录行，列，值，也就是该结构体对应一个数据，

再创建一个与该结构体对应的一维数组，就可以顺序的存储稀疏矩阵，

缺点：顺序存储稀疏矩阵访问其中的元素时只能依次遍历，无法随机存取：

2.对于十字链表法，定义如下图的数组，数组里存指针(指针数组)，都指向非0元素：

八.总结：