数据结构笔记之特殊矩阵压缩

对称矩阵：特点是矩阵中的任意一个元素 ai,j 等于它的转置 aj,i。为了节省存储空间，我们只存储主对角线及以下三角区（或主对角线及以上三角区），因为其他区域可以通过对称性推导出来。

三角矩阵：分为上三角矩阵和下三角矩阵。上三角矩阵的下三角部分全为常数，而下三角矩阵的上三角部分全为常数。压缩存储时，可以按行优先或列优先规则依次存储非常量区域，并在最后一个位置存放常数 c。

三对角矩阵（带状矩阵）：特点是在主对角线附近有非零元素，即当 |i-j| > 1 时，ai,j 等于 0（i 和 j 是行和列的索引）。压缩存储时，可以按行优先或列优先规则依次存储带状区域。

稀疏矩阵：非零元素个数远小于零元素个数。在这种情况下，完全存储所有元素是不经济的。有两种常见的压缩存储方法：

• 顺序存储：将矩阵分解为三个有序元组 <行, 列, 值>，只存储非零元素。这种方式适用于矩阵中非零元素分布均匀的情况。

• 链式存储：使用十字链表法，将非零元素链接起来。这种方法更适合非零元素分布不均匀的情况，因为它允许快速定位非零元素。