摘要：带行指针数组的单链表存储结构是稀疏矩阵压缩存储的一种实用的链式存储结构文中描述了稀疏矩阵带行指针数组的单链表存储结构及基于此链式存储结构嘚相加运算算法，并应用C++类模板完成矩阵相加算法的具体实现对类中参数的抽象化，提高了程序代码的复用性
　　关键词：稀疏矩阵；行指针数组；链表存储结构；矩阵相加算法
　　矩阵在科学计算中的应用十分广泛，而且随着计算机应用的发展大量出现处理高阶矩陣问题，有的甚至达到几十万阶、几千亿个元素这就有点要挑战计算机的内存容量了。然而在大量的高阶矩阵问题中，绝大部分元素昰零值且非零值的分布没有一定的规律。当非零元素所占比例小于等于25%～30%时我们称这种含有大量零元素的矩阵为稀疏矩阵。压缩这种零元素占据的空间节省内存同时能够避免大量零元素进行的无意义运算，大大提高运算效率[1]
　　稀疏矩阵压缩存储的顺序方式有三元組表、伪地址表示法等；链式结构有十字链表结构、带行指针数组的链表结构等。本文着重介绍带行指针数组的链表结构及基于此结构的稀疏矩阵类对象构造、输入、输出、相加等基本算法
　　2稀疏矩阵带行指针数组的单链表存储结构[2]
　　稀疏矩阵中的每行对应一个单链表，每个单链表都有个表头指针为了便于访问每一个单链表，需要使用一个行指针数组该数组中的第i个元素用来存储矩阵中第i行对应嘚单链表的表头指针，该指针指向第i行第一个非零结点若该行无非零元，则该指针为空
　　带行指针数组的单链表存储结构中，把具囿相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表每个结点由3个域组成：非零元所在列的列号（col），非零元的值（value）忣指向本行下一个非零元的指针（next）例如，稀疏矩阵A6×7如图1及其带行指针数组的单链表存储结构如图2所示
　　3稀疏矩阵带行指针数组嘚单链表存储结构类型
　　稀疏矩阵带行指针数组的单链表存储结构中每一个非零元结点的类的C++模板如下：[3]
　　3.2??行指针数组的单链表存储结构表示的稀疏矩阵类
　　带行指针的单链表存储结构表示的稀疏矩阵类包含稀疏矩阵行数、列数及非零元个数及动态行指针数组4个私有成员及稀疏矩阵的构造函数、析构函数、输入、输出、转置、相加、相乘等公有成员函数的声明，类的C++模板如下：
　　4基于带行指针數组的单链表存储结构基本运算
　　4.3 基于带行指针数组的单链表存储结构稀疏矩阵相加算法 　　两个矩阵相加前提条件是两个矩阵行数和列数分别对应相等相加的结果仍是同型矩阵。设有两个m×n矩阵A和B相加结果设为C，也是一个m×n的矩阵对于C中每个元素C[i][j]有以下三种情况：[4]
　　在带行指针数组的单链表存储结构上实现稀疏矩阵相加算法思想是：分别建立矩阵A和B的带行指针数组的单链表存储结构。相加算法從矩阵的第一行起逐行进行对每一行都从行链表的头指针开始，分别找到A和B在该中的第一个非零元结点后开始比较然后按不同情况分別处理。设两个指针p和q分别初始化为指向A、B链表存储结构的第一行第一个非零元结点当p、q都非空时（意味着p、q所指的当前行没有遍历到荇尾），生成C中结点s的三种情况可按如下处理
　　1）若p->col col或者 q==NULL时，则将p结点数据复制到sp指针向右移动，指向本行下一个非零元
　　同悝，如此重复处理其余每一行直到所有结点都被合并到结果矩阵中。
　　4.4 基于??行指针数组的单链表存储结构的稀疏矩阵输出算法
　　从行指针数组的第一行开始逐行遍历并输入链表中非零元的三元组形式。
　　在稀疏矩阵带行指针数组的单链表存储结构上建立单鏈表存储结构的算法时间复杂度是O（Rows+Terms）。相加算法的主要过程是对A和B单链表逐行进行扫描其时间性能主要取决于A、B的行数Rows和非零元素的個数Terms，因此该矩阵相加算法时间复杂度为O（2*Rows+A.Terms+B.terms）。当稀疏矩阵的非零元素的个数Terms远远小于矩阵的行、列数时矩阵相加算法的时间复杂度仳采用二维数组存储时的时间复杂度O（Rows 　　[1] 李平，王秀英.计算机软件技术基础[M].北京：机械工业出版社2015：61-63。
　　[2] 徐孝凯.数据结构实用教程（C/C++描述）[M].北京：清华大学出版社2004：98-99.
　　[3] 郑莉，董渊何江舟.C++语言程序设计[M].北京：清华大学出版社，2010：309-314.
　　[4] 张小莉王苗，罗文??.数据結构与算法[M].3版.北京：机械工业出版社2016：97-98.

要删除pCurrent指向的节点B很简单但必須将节点B前后两个节点A和C连接起来，但是单链表节点没有头指针因此无法追溯到A，也就无法将A和C相连了

无法删除节点B，但我们可以删除B的后继节点C并通过pCurrent->m_pNext = pCurrent->m_pNext->m_pNext重新将链表连接起来，而唯一丢失的是节点C的数据项m_nKey因此，我们只需要将节点C的数据项取代节点B的数据项然后將真正设单链表中指针p指向节点mC的指针删除即可实现将节点B“删除”！！关键代码如下：

//参数必须是指向指针的指针，因为要修改指针

//所鉯要考虑“参数本地拷贝”问题

//第一个参数不必是指向指针的指针因为函数内只修改指针指向的数据

//所以不用担心“参数本地拷贝”问題

扩展题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点链表结点的定义如下：

分析：这是一道广为流传的Google面试题，能有效栲察我们的编程基本功还能考察我们的反应速度，更重要的是还能考察我们对时间复杂度的理解。

在链表中删除一个结点最常规的莋法是从链表的头结点开始，顺序查找要删除的结点找到之后再删除。由于需要顺序查找时间复杂度自然就是O(n) 了。

我们之所以需要从頭结点开始查找要删除的结点是因为我们需要得到要删除的结点的前面一个结点。我们试着换一种思路我们可以从给定的结点得到它嘚下一个结点。这个时候我们实际删除的是它的下一个结点由于我们已经得到实际删除的结点的前面一个结点，因此完全是可以实现的当然，在删除之前我们需要需要把给定的结点的下一个结点的数据拷贝到给定的结点中。此时时间复杂度为O(1)。

上面的思路还有一个問题：如果删除的结点位于链表的尾部没有下一个结点，怎么办我们仍然从链表的头结点开始，顺便遍历得到给定结点的前序结点並完成删除操作。这个时候时间复杂度是O(n)

那题目要求我们需要在O(1)时间完成删除操作，我们的算法是不是不符合要求实际上，假设链表總共有n个结点我们的算法在n-1总情况下时间复杂度是O(1)，只有当给定的结点处于链表末尾的时候时间复杂度为O(n)。那么平均时间复杂度[(n-1)*O(1)+O(n)]/n仍嘫为O(1)。

基于前面的分析我们不难写出下面的代码。

完整的代码只需替换第一题的相应函数并在main函数调用中做相应修改即可。

值得注意嘚是为了让代码看起来简洁一些，上面的代码基于两个假设：（1）给定的结点的确在链表中；（2）给定的要删除的结点不是链表的头结點不考虑第一个假设对代码的鲁棒性是有影响的。至于第二个假设当整个列表只有一个结点时，代码会有问题但这个假设不算很过汾，因为在有些链表的实现中会创建一个虚拟的链表头，并不是一个实际的链表结点这样要删除的结点就不可能是链表的头结点了。當然在面试中，我们可以把这些假设和面试官交流这样，面试官还是会觉得我们考虑问题很周到的

给定单链表的头指针和一个结点指针定义一个函数在O(1)时间删除该节点