数据结构（16）特殊矩阵的压缩存储

server/2024/12/2 20:25:50/

前言

特殊矩阵的压缩存储是数据结构中的一个重要概念，它旨在通过找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中，从而节省存储空间。

一、特殊矩阵的定义

特殊矩阵是指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵和稀疏矩阵等。

二、特殊矩阵的压缩存储方法

1. 对称矩阵的压缩存储

对称矩阵是指矩阵中的元素关于主对角线对称，即满足a(ij)=a(ji)（0<i,j<n-1）。由于这种对称性，可以只存储上三角或下三角矩阵中的元素，从而将存储空间从nn个元素压缩至n(n-1)/2个元素。

存储方法：可以使用一维数组s[k]来存储对称矩阵A(i,j)的下三角元素。k和(i,j)之间的对应关系可以通过等差数列公式推导出来，如k=i(i-1)/2+j（当i>=j时）或k=j(j-1)/2+i（当i<j时）。

2. 三角矩阵的压缩存储

三角矩阵分为上三角矩阵和下三角矩阵。上三角矩阵是指下三角元素均为常数的矩阵，而下三角矩阵是指上三角元素均为常数的矩阵。

存储方法：与对称矩阵存储相似，可以使用一维数组s来存储三角矩阵的元素，其中s的最后一位用来存储常数项。对于上三角矩阵，其存储相当于对称矩阵的以列为主的压缩存储；对于下三角矩阵，其存储则与对称矩阵的以行为主的压缩存储类似。

3. 对角矩阵的压缩存储

对角矩阵是指所有非零元素集中在主对角线两侧的带状区域内的矩阵。常见的对角矩阵有三对角矩阵、m对角矩阵等。

存储方法：对于三对角矩阵，可以使用一维数组s[k]来存储其元素，其中k和A[i][j]的对应关系为k=2*i+j-3（当|i-j|<=1时）。对于m对角矩阵，则需要根据具体的m值来确定存储方式。

4. 稀疏矩阵的压缩存储

稀疏矩阵是指大多数元素均为零的矩阵。如果矩阵mn中有t个非零元素，那么s=t/mn称为矩阵的稀疏因子。当s<=0.05时，通常认为该矩阵为稀疏矩阵。

存储方法：稀疏矩阵可以使用三元组顺序表来表示，其中三元组格式为(i,j,e)，记录了非零元素的行号、列号以及非零元素的值。这种方法可以极大地节省存储空间。