矩阵存储方法及其向量表示方式

在稀疏存储方法中，只存储n×n阶矩阵A的非零元素及其索引信息，这些索引信息在逐个元素遍历矩阵时是需要的。这样，每个元素必须存储其真实值（a_ij）及其在矩阵中的位置信息（行号和列号）。基本的存储单元可以形象化为如图4.1所示的对象。

除了基本信息外，对象中还必须包含索引信息，诸如同一行中的下一个元素的链接信息或者同一列中下一个元素的链接信息等，如图4.2所示。

图4.1 a_ij的基本存储单元

图4.2 元素a_ij以链接表示的存储单元

不管是按行还是按列完全遍历一个矩阵，所需要的唯一额外信息是每行或每列第一个元素的位置信息。这是单独的一个链接信息集合，标示了每行或每列第一个元素的位置。

例4.1 确定描述如下稀疏矩阵的链表。

解4.1 描述此矩阵的链表如图4.3所示。每列和每行的最后一个元素都被链接到一个零点。注意，矩阵中每个非零元都按列和按行被链接到与它相邻的非零元上。这样，通过从第一个元素开始并按照链接关系直到想要的元素，就可以从任何方向遍历整个矩阵。

如果一个指令需要一个特定的矩阵元素，那么不管采用按列搜索还是按行搜索，沿着链接方向前进就能定位该元素。如果在搜索过程中到达了零点，那么说明该想要的元素是不存在的，并返回一个零值。此外，如果矩阵元素是通过递增的指标来链接的话，当到达一个元素其指标已大于想要的元素的指标值时，那么就终止前进的过程并返回一个零值。

图4.3 例4.1的链表

稀疏矩阵的链表描述法不是唯一的，并且元素间并不必须按照指标递增的方式来链接。但是，通过采用指标递增的方式来对元素进行排序可以简化搜索过程，因为一旦链接的对象的指标值超过了想要元素的指标值，就可以在到达零点前终止搜索的过程。如果矩阵元素不是按照顺序链接的，就必须遍历整行或者整列以确定想要的元素是否为非零元。有序表的缺点是在矩阵中插入新的非零元时需要对行和列的链接都进行更新。

例4.2 在例4.1的链表中插入矩阵元素A（4，5）=10。(www.xing528.com)

解4.2 新元素插入后的链表如图4.4所示。该元素的插入需要对矩阵遍历两次并更新链接；一次按行遍历，一次按列遍历。从链表第4行的第一个元素（值为-3）开始搜索，按照链接关系前进并监视列指标，可以发现列指标为3的元素（值为2）是该行的最后一个元素，因为它指向零点。由于新元素的列指标为5，它应被插入在该元素（值为2）和该行链表的零点之间。类似地，从链表第5列的第一个元素（值为-2）开始搜索，遍历该列并且在行指标为3（值为-2）和5（值为-4）的两个元素之间插入新元素，再更新该列的链接以反映插入情况。

如果该矩阵的链表不是按照指标值排序的，那么不需要遍历行和列就可以添加新元素。通过将新元素插入到第一个元素的前面并更新该行或该列第一个元素的指针，一个新元素可以插入到每一行或者每一列中。

图4.4 插入矩阵元素A（4，5）=10

然而，很多软件语言并不支持使用对象、指针和链表。这种情况下，有必要开发一个程序，通过使用向量来模拟链表结构。表示一个非零元对象需要三个向量：一个包含行号的向量（NROW），一个包含列号的向量（NCOL）以及一个包含非零元数值的向量（VALUE）。这些向量的长度都为nnz，这里nnz为非零元的个数。还需要2个长度也为nnz的向量，用来表示行中下一个元素的链接关系（NIR）和列中下一个元素的链接关系（NIC）。如果一个元素是该行或者该列的最后一个元素，那么对应这个元素的NIR或者NIC的值为0。最后，还需要2个长度为n的向量，包含各行第一个元素（FIR）和各列第一个元素（FIC）的链接关系。

矩阵的元素根据它们在NROW、NCOL、VALUE、NIR和NIC向量中的排序被赋予一个（可能是任意的）编号。这个排序方案对这五个向量的每一个都是一样的。FIR与FIC向量则根据上述编号方案而定。

例4.3 求例4.1中稀疏矩阵的NROW、NCOL、VALUE、NIR、NIC、FIR和FIC向量。

解4.3 例4.1的矩阵重新给出如下，所采用的编号方案见每个非零元左边的括号。此编号方案是按行连续编号的，从1到nnz=12。

上述编号方案产生以下长度为nnz的向量：

和以下长度为n的向量：

考察矩阵元素A（2，2）=8，这是此编号方案中的第4个元素，因此它的信息被存储在向量VALUE、NROW、NCOL、NIR和NIC的第4个位置。这样，VALUE（4）=8，NROW（4）=2，NCOL（4）=2。第2行的下一个元素是A（2，4）=1，它在此编号方案中是第5个元素。因此NIR（4）=5，意味着第5个元素与第4个元素处在同一行中且紧随第4个元素之后（但请注意这里并没有标示出是在哪一行）。类似地，第2列中的下一个元素是A（4，2）=-3，它在此编号方案中是第8个元素。因此NIC（4）=8。