一 稀疏矩阵的存储

1.三元组顺序表

三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组(i,j,aij)唯一确定。矩阵中所有非零元素存放在由三元组组成的顺序表中(通常用数组)。所以三元组的逻辑结构如下：

注意，此处的非零元素的三元组是以行序为主序顺序排列的。

2.行逻辑链接顺序表

行逻辑链接顺序表的实质就是在三元组顺序表的基础上加了一个数组，这个数组用于存储稀疏矩阵中每行的第一个非零元素的在三元组顺序表中的位置(此处一定要理解对，是在三元组顺序表中的位置)。所以其逻辑结构如下：

 3.十字链表

当稀疏矩阵的非零元个数和位置在操作过程中变化较大时，就不易采用顺序存储结构来表示三元组的线性表。对于这种类型得矩阵，采用链式存储结构表示三元组的线性表更为恰当。

在链表中，每个非零元可用一个含5个域的结点表示，其中$i$、$j$、$val$这三个域分别表示该非零元所在的行、列和非零元的值(就是三元组中的那三个域)，向右域right用以链接同一行中下一个非零元，向下域down用以链接同一行中的下一个非零元。

所以，同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，所以才称为十字链表。十字链表中，可以使用两个分别存储行链表的头指针和列链表的头指针的一维数组表示。所以，其逻辑结构如下：

二 稀疏矩阵的乘法　

1.一般矩阵的乘法操作　

对于一般矩阵而言，通常用二维数组表示矩阵。对于矩阵$M∈R^{m \times n}$和矩阵$N∈R^{n \times p}$而言，它们的乘法操作表示如下：