全屏显示专题章节

所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。

矩阵中的非零元素呈某种规律分布或矩阵中出现大量的零元素的情况下,为了节省存储空间,可以对这类矩阵进行压缩存储。即为多个相同的非零元素只分配一个存储空间,并且对零元素不分配存储空间。

1.对阵矩阵定义

若一个n阶方阵A中的元素满足下列条件。

如图5－3便是一个5阶对称矩阵。

2.对称矩阵压缩存储

对称矩阵中的元素关于主对角线是对称的,因此对称矩阵的存储可以只存储下三角部分的数据元素,让每两个对称的元素共享一个存储空间,则可将n²个元素存储到n（n＋1）/2个存储空间中,能节省近一半的存储空间。对称矩阵对应的下三角部分如图5－4所示。

假设以一维数组sa[n（n＋1）/2]作为n阶对称矩阵A的存储结构,则sa[k]和矩阵元素a_ij之间存在一一对应关系。

（1）当i≥j时,则a_ij位于下三角形中。a_ij之前的i行（从第0行到第i－1行）一共有1＋2＋…＋i＝i（i＋1）/2个元素,在第i行上,a_ij之前恰有j个元素（即a_i,0,a_i,1,a_i,2,…,a_i,j－1）,因此有:

（2）当i＜j时,则a_ij位于上三角形中。因为a_ij＝a_ji,所以只要交换上述对应关系式中的i和j即可得:

对于任意给定的一组下标值（i,j）,均可在一维数组sa中找到矩阵元素a_ij；反之,对于所有的k（0≤k＜n（n＋1）/2）,都能确定sa[k]中元素在矩阵中位置（i,j）。因此,称一维数组sa[n（n＋1）/2]为n阶对称矩阵A的压缩存储,如图5－5所示。

3.对称矩阵元素地址计算

计算对称矩阵A中元素a_ij地址LOC（a_ij）,即为计算a_ij在一维数组sa[n（n＋1）/2]中的存储地址LOC（sa[k]）。为了方便计算,令I＝max（i,j）,J＝min（i,j）,则k＝I（I＋1）/2＋J,那么a_ij的地址可用下列式子计算。

LOC（a_ij）＝LOC（sa[k]）

　　　　＝LOC（sa[0]）＋k×d

　　　　＝LOC（sa[0]）＋（I（I＋1）/2＋J）×d

1.对角矩阵定义

若矩阵（方阵）中所有非零元素都集中在以主对角线为中心的带状区域中,区域外的值全为0,则称该矩阵为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。图5－6所示为7×7的三对角矩阵（即有三条对角线上元素非0）。

其中,非零元素出现在对角线、主对角线上方紧邻的对角线和主对角线下方紧邻的对角线上。

2.对角矩阵压缩存储

对角矩阵中的非零元素集中在以对角线为中心的带状区域,因此对角矩阵的存储可以只存储带状区域的数据元素。按照行优先顺序存储,可将一个k对角矩阵（k为奇数）压缩存储到一个向量中,并且也能找到每个非零元素和向量下标的对应关系。

假设一个n阶k对角矩阵（k为奇数）中每行有k个元素,则矩阵中一共有n×k个元素。事实上,在对角矩阵中,第0行和第n－1行的元素个数相同,为（k＋1）/2个元素；第1行和第n－2行的元素个数相同,为（k＋1）/2＋1个元素,依此类推。即在k对角矩阵中,第0行和第n－1缺少（k－1）/2个元素,第1行和第n－2行缺少（k－1）/2－1个元素…则第i行缺少（k－1）/2－i个元素（0≤i＜（k－1）/2）。因此,在n阶k对角矩阵中的实际元素个数如下。

根据上式,很容易计算出n阶三对角矩阵中的元素个数为3n－2,五对角矩阵中元素个数为5n－6等,依此类推。

此处以三对角矩阵为例讨论对角矩阵与一维向量之间关系。n阶三对角矩阵A元素个数为3n－2个,因此可将矩阵中的非零元素存储在向量sa[3n－2]中,则sa[k]和矩阵元素a_ij之间存在着一一对应关系。

（1）当i＝0时,a_ij位于第0行,则a_ij之前一共有j元素,因此有:

（2）当0＜i≤n－1时,a_ij前面有i行,除0行外,每行有3个元素,则前i行一共有3i－1个元素。而a_ij所在的i行上,a_ij之前有j－i＋1个元素,因此有:

将（1）（2）统一起来,则有k＝2i＋j（0≤k＜3n－2）。对于任意给定的一组下标值（i,j）,均可在一维数组sa中找到矩阵元素a_ij；反之,对于所有的0≤k＜3n－2的元素,都能确定sa[k]中元素在矩阵中位置（i,j）。因此,称一维数组sa[3n－2]为n阶三对角矩阵A的压缩存储,如图5－7所示。

其他五对角矩阵、七对角矩阵可以按此思路进行分析。

3.三对角矩阵元素地址的计算

计算n阶三对角矩阵A中元素a_ij地址LOC（a_ij）,即计算a_ij在一维数组sa[3n－2]中的存储地址LOC（sa[k]）。

LOC（a_ij）＝LOC（sa[k]）

　　　　＝LOC（sa[0]）＋k×d

　　　　＝LOC（sa[0]）＋（2i＋j）×d

上述的特殊矩阵,其非零元素的分布都是有规律的,因此总能找到一种方法将它们压缩存储到一个向量中,并且一般都能找到矩阵中的元素与该向量之间的对应关系,通过这个关系,仍能对矩阵的元素进行随机存取。而下面所述的稀疏矩阵则有很大不同。

1.稀疏矩阵的定义

什么是稀疏矩阵？简单说,设矩阵A中有s个非零元素,若s远远小于矩阵元素的总数（m×n）时,称A为稀疏矩阵。即令δ＝

（δ称为稀疏因子）,若矩阵A对应的δ≤0.05时,称A为稀疏矩阵。例如,图5－8所示矩阵A。

2.稀疏矩阵抽象数据类型定义

稀疏矩阵的抽象数据类型定义如下。

3.稀疏矩阵的压缩存储

在稀疏矩阵中,由于绝大部分是零元素,而这些零元素如果也要存储在计算机的存储空间中,则会浪费大量的存储空间。为了节省存储单元,很自然地想到使用压缩存储的方法。但由于非零元素的分布一般是没有规律的,因此在存储非零元素的同时,还必须同时记下它所在的行和列的位置（i,j）。反之,一个三元组（i,j,a_ij）唯一确定了矩阵A的一个非零元素。此外,为了唯一确定一个矩阵,还必须给出矩阵的行数m和列数n。因此,稀疏矩阵可由表示非零元的三元组及其行列值唯一确定。

如图5－8所示的7×8的稀疏矩阵A,用三元组表示如下。

（（0,2,3）,（0,7,1）,（2,0,9）,（3,4,7）,（4,6,5）,（5,1,1）,（5,5,2）,（6,3,4））

4.稀疏矩阵的存储结构

稀疏矩阵利用三元组进行压缩存储时,通常采用顺序存储（三元组顺序表）、线性链表存储和十字链表存储等存储方式。

1）三元组顺序表

将表示稀疏矩阵非零元素的三元组按行优先的顺序排列,依次存放在向量中,这种稀疏矩阵的顺序存储方式称为三元组顺序表。其类型描述如下。

图5－9为图5－8所示稀疏矩阵A所对应的三元组顺序表A.data。

2）行逻辑链接顺序表

为了便于随机存取任意一行的非零元素,则需要知道每一行的第一个非零元素在三元组表中的位置。为此,在稀疏矩阵的三元组顺序存储结构中增加指示各行第一个非零元素位置的向量,这种三元素组表被称为行逻辑链接顺序表,其类型描述如下。

图5－8所示的稀疏矩阵A对应行逻辑链接顺序表如图5－10所示。

采用十字链表存储是将稀疏矩阵中同一行的非零元素链接成一个行线性链表,同一列的非零元素链接成一个列线性链表。这样,每一个非零元素就包含在两个链表中,即该非零元素既在所在行的行链表中也在所在列的列链表中,整个矩阵构成了一个十字交叉的链表。

在采用十字链表存储稀疏矩阵时,非零元素用一个包含五个域的结点表示:行号域row、列号域col、值域e、列链接指针域down、行链接指针域right。结点结构如图5－11所示。