数据结构（其四）--特殊矩阵的存储

目录

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、非零数据。

        ② 十字链表法----此为链式存储，

        结点中，包含行、列、值以及两个指针。

        两个指针分别指向同一列的下一个结点和同一行的下一个结点。