|
|
|
矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中主要讨论如何在尽可能节省存储空间的情况下，使矩阵的各种运算能高效地进行。
|
|
|
|
在一些矩阵中，存在很多值相同的元素或者是零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元，对零元不分配存储单元。
|
|
|
|
|
|
常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵，由于其非零元的分布都有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非零元在矩阵中的位置与其在一维数组中的位置之间的对应关系。
|
|
|
|
若矩阵An×n中的元素有aij=aji（1≤i，j≤n）的特点，则称之为对称矩阵。
|
|
|
|
若为对称矩阵中的每一对元素分配一个存储单元，那么就可将n2个元素压缩存储到能存放n（n+1）/2个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组B［n（n+1）/2］作为n阶对称矩阵A中元素的存储空间，则B［k］（0≤k<n（n+1）/2）与矩阵元素aij（aji）之间存在着一一对应的关系。
|
|
|
|
|
|
对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。一个n阶的三对角矩阵如下图所示。
|
|
|
|
|
|
|
|
若以行为主序将n阶三对角矩阵An×n的非零元素存储在一维数组B［k］（0≤k<3n-2）中，则元素位置之间的对应关系为：
|
|
|
|
k=3×（i-1）-1+j-i+1=2i+j-3（1≤i，j≤n）
|
|
|
|
其他特殊矩阵可作类似的推导和计算，这里不再一一说明。
|
|
|
|
|
|
在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。
|
|
|
|
对于稀疏矩阵，存储非零元素时必须同时存储其位置（即行号和列号），所以三元组（i，j，aij）可唯一确定矩阵中的一个元素。由此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。
|
|
|
|
一个6行7列的稀疏矩阵如下图所示，其三元组表为（1，2，12），（1，3，9），（3，1，-3），（3，6，14），（4，3，24），（5，2，18），（6，1，15），（6，4，-7））。
|
|
|
|
|
|
|
|
稀疏矩阵的三元组表构成一个线性表，其顺序存储结构称为三元组顺序表，其链式存储结构称为十字链表。
|
|
|
