矩阵是很多科学与工程计算问题中研究的数学对象。在此，我们感兴趣的不是矩阵本身，而是如何存储矩阵的元，以及如何使矩阵的各种运算能有效地进行。本章是线性表在科学计算中的应用。我们将要学习到：

数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。下图是一个m行n列的二维数组。

特点：

数组运算：

创建一个矩阵

分析上述算法，主要的工作是在\(p\)和\(col\)的两重循环中完成的，故算法的时间复杂度为\(O(nu\cdot tu)\)，即和\(M\)的列数及非零元的个数的乘积成正比。

一般矩阵转置算法：

快速算法仅比前一个算法多用了两个辅助向量。从时间上看，算法中有4个并列的单循环，循环次数分别为\(nu\)和\(tu\)，因而总的时间复杂度为\(O(nu+tu)\)。在\(M\)的非零元个数\(tu\)和\(mu\times nu\)等数量级时，其时间复杂度为\(O(mu\times nu)\)，和经典算法的时间复杂度相同。

三元组表特点：

三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需按行号存取某一行的非零元，则需从头开始进行查找。

为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可将上节快速转置矩阵的算法中创建的，指示“行”信息的辅助数组\(cpot\)固定在稀疏矩阵的存储结构中。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表，其类型描述如下：

\[C=A\times B\]

稀疏矩阵相乘的基本操作是：

对于\(A\)中每个元素\(A.data[p](p=1,2,\cdots ,A.tu)\)，找到\(B\)中所有满足条件\(A.data[p].j=B.data[q].i\)的元素\(B.data[q]\)，求得\(A.data[p].v\)和\(B.data[q].v\)的乘积，而从式得知，乘积矩阵\(C\)中每个元素的值是个累计和，这个乘积\(A.data[p].val\times B.data[q].val\)只是\(C[i][j]\)中的一部分。

为便于操作，应对每个元素设一累计和的变量，其初值为零，然后扫描数组\(A\)，求得相应元素的乘积并累加到适当的求累计和的变量上。

两个稀疏矩阵相乘的乘积不一定是稀疏矩阵。反之，即使式中每个分量值\(A(i,k)\times B(k,j)\)不为零，其累加值\(C[i][j]\)也可能为零。因此乘积矩阵\(C\)中的元素是否为非零元，只有在求得其累加和后才能得知。由于\(C\)中元素的行号和\(A\)中元素的行号一致，又\(A\)中元素排列是以\(A\)的行序为主序的，由此可对\(C\)进行逐行处理，先求得累计求和的中间结果（\(C\)的一行），然后再压缩存储到\(C.data\)中去

已知两个稀疏矩阵A和B，分别采用十字链表存储，计算 \(C=A+B\) ，C也采用十字链表方式存储，并且在A的基础上形成C，即A改成了C。

由矩阵的加法规则知，只有A和B行列对应相等，二者才能相加。

C中的非零元素 \(cij\) 只可能有３种情况：

因此当B加到A上时，对A十字链表的当前结点来说，对应下列四种情况：

整个运算从矩阵的第一行起逐行进行。对每一行都从行表的头结点出发，分别找到A和B在该行中的第一个非零元素结点后开始比较，然后按四种不同情况分别处理。

以矩阵\(A\)的行序为主循环，以矩阵\(B\)的列序为次循环。新得到的结点在相乘得到的矩阵\(C\)中的插入方式与转置操作类似。

用十字链表存储结稀疏矩阵，并完成：