【Data Structure】矩阵

Posted by 西维蜀黍 on 2019-05-24, Last Modified on 2022-12-10

矩阵

数据结构中,提供针对某些特殊矩阵的压缩存储结构。

这里所说的特殊矩阵,主要分为以下两类:

  • 含有大量相同数据元素的矩阵,比如对称矩阵
  • 含有大量 0 元素的矩阵,比如稀疏矩阵、上(下)三角矩阵

针对以上两类矩阵,数据结构的压缩存储思想是:矩阵中的相同数据元素(包括元素 0)只存储一个

对称矩阵

上图的矩阵中,数据元素沿主对角线对应相等,这类矩阵称为对称矩阵

矩阵中有两条对角线,其中图 1 中的对角线称为主对角线,另一条从左下角到右上角的对角线为副对角线。对称矩阵指的是各数据元素沿主对角线对称的矩阵。

结合数据结构压缩存储的思想,我们可以使用一维数组存储对称矩阵。由于矩阵中沿对角线两侧的数据相等,因此数组中只需存储对角线一侧(包含对角线)的数据即可

对称矩阵的实现过程是,若存储下三角中的元素,只需将各元素所在的行标 i 和列标 j (矩阵中元素的行标和列标都从 1 开始)代入下面的公式:

存储上三角的元素要将各元素的行标 i 和列标 j 代入另一个公式:

最终求得的 k 值即为该元素存储到数组中的位置。

例如,在数组 skr[6] 中存储上图中的对称矩阵,则矩阵的压缩存储状态如下图所示(存储上三角和下三角的结果相同):

上(下)三角矩阵

如上图所示,主对角线下的数据元素全部相同的矩阵为上三角矩阵(上图 a)),主对角线上元素全部相同的矩阵为下三角矩阵(上图 b))。

对于这类特殊的矩阵,压缩存储的方式是:上(下)三角矩阵采用对称矩阵的方式存储上(下)三角的数据(元素 0 不用存储)。

稀疏矩阵

如上图所示,如果矩阵中分布有大量的元素 0,即非 0 元素非常少,这类矩阵称为稀疏矩阵

压缩存储稀疏矩阵的方法是:只存储矩阵中的非 0 元素,与前面的存储方法不同,稀疏矩阵非 0 元素的存储需同时存储该元素所在矩阵中的行标和列标。

例如,存储上图中的稀疏矩阵,需存储以下信息:

  • (1,1,1):数据元素为 1,在矩阵中的位置为 (1,1);
  • (3,3,1):数据元素为 3,在矩阵中的位置为 (3,1);
  • (5,2,3):数据元素为 5,在矩阵中的位置为 (2,3);

除此之外,还要存储矩阵的行数 3 和列数 3;

由此,可以成功存储一个稀疏矩阵。

注意,以上 3 种特殊矩阵的压缩存储,除了将数据元素存储起来,还要存储矩阵的行数值和列数值。

矩阵压缩存储的 3 种方式

对于以上 3 种特殊的矩阵,对阵矩阵和上下三角矩阵的实现方法是相同的,且实现过程比较容易,仅需套用上面给出的公式即可。

稀疏矩阵的压缩存储,数据结构提供有 3 种具体实现方式:

  • 三元组顺序表;
  • 行逻辑链接的顺序表;
  • 十字链表;

三元组顺序表

稀疏矩阵的压缩存储,至少需要存储以下信息:

  • 矩阵中各非 0 元素的值,以及所在矩阵中的行标和列标;
  • 矩阵的总行数和总列数;

例如,上图是一个稀疏矩阵,若对其进行压缩存储,矩阵中各非 0 元素的存储状态如下图所示:

上图的数组中,存储的是三元组(即由 3 部分数据组成的集合),组中数据分别表示(行标,列标,元素值)。

注意,这里矩阵的行标和列标都从 1 开始。

行逻辑链接的顺序表

十字链表

矩阵(稀疏矩阵)的转置算法

Reference