稀疏矩阵带行指针数组的单链表存储结构及相加算法实现

邬恩杰　张静

摘要：带行指针数组的单链表存储结构是稀疏矩阵压缩存储的一种实用的链式存储结构。文中描述了稀疏矩阵带行指针数组的单链表存储结构及基于此链式存储结构的相加运算算法，并应用C++类模板完成矩阵相加算法的具体实现，对类中参数的抽象化，提高了程序代码的复用性。

关键词：稀疏矩阵；行指针数组；链表存储结构；矩阵相加算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）36-0035-03

1稀疏矩阵

矩阵在科学计算中的应用十分广泛，而且随着计算机应用的发展，大量出现处理高阶矩阵问题，有的甚至达到几十万阶、几千亿个元素，这就有点要挑战计算机的内存容量了。然而，在大量的高阶矩阵问题中，绝大部分元素是零值，且非零值的分布没有一定的规律。当非零元素所占比例小于等于25%～30%时，我们称这种含有大量零元素的矩阵为稀疏矩阵。压缩这种零元素占据的空间，节省内存同时能够避免大量零元素进行的无意义运算，大大提高运算效率。[1]

稀疏矩阵压缩存储的顺序方式有三元组表、伪地址表示法等；链式结构有十字链表结构、带行指针数组的链表结构等。本文着重介绍带行指针数组的链表结构及基于此结构的稀疏矩阵类对象构造、输入、输出、相加等基本算法。

2稀疏矩阵带行指针数组的单链表存储结构[2]

稀疏矩阵中的每行对应一个单链表，每个单链表都有个表头指针，为了便于访问每一个单链表，需要使用一个行指针数组，该数组中的第i个元素用来存储矩阵中第i行对应的单链表的表头指针，该指针指向第i行第一个非零结点，若该行无非零元，则该指针为空。

带行指针数组的单链表存储结构中，把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个结点由3个域组成：非零元所在列的列号（col），非零元的值（value）及指向本行下一个非零元的指针（next）。例如，稀疏矩阵A6×7如图1及其带行指针数组的单链表存储结构如图2所示。

3稀疏矩阵带行指针数组的单链表存储结构类型

3.1结点类定义

稀疏矩阵带行指针数组的单链表存储结构中每一个非零元结点的类的C++模板如下：[3]

template

structTripleNode

{int col；

T value；

TripleNode*next；

TripleNode& operator=（TripleNode&x）

{col=x.col；value=x.value；next=NULL；return *this；}}

3.2帶行指针数组的单链表存储结构表示的稀疏矩阵类

带行指针的单链表存储结构表示的稀疏矩阵类包含稀疏矩阵行数、列数及非零元个数及动态行指针数组4个私有成员及稀疏矩阵的构造函数、析构函数、输入、输出、转置、相加、相乘等公有成员函数的声明，类的C++模板如下：

template

classSparseMatrix

{private：

int Rows，Cols，Terms；

TripleNode **PROWS；

public：

SparseMatrix（int rc，int cc，int tc）；

～SparseMatrix（）{delete []PROWS；}

void Add（SparseMatrix&b，SparseMatrix&c）；

void create_SparseMatrix（）；

void print_SparseMatrix（）；}；

4基于带行指针数组的单链表存储结构基本运算

4.1构造函数

template

SparseMatrix（intrc，intcc，inttc）

{ Rows=rc； Cols=cc； Terms=tc；

PROWS=newTwo_tuple *[Rows]；

for （intI=0；I

4.2 建立带行指针数组的单链表存储结构

在实例化稀疏矩阵时通过构造函数建立只有行指针数组的空的稀疏矩阵。在此基础上按行优先，列号从小到大顺序输入非零元所在行、列和值，申请一个结点所需存储空间，并将非零元的列号和值存入相应域，按列号从小到大的顺序将此结点插入到对应行尾部。构造函数及建立链表结构代码：

template

voidcreate_SparseMatrix（）

{ int r，c；

T v；

Two_tuple *p，*q，*s；

for （int i=0；i

{cin>>r>>c>>v；

s=newTwo_tuple；

s->col=c；s->value=v；s->next=NULL；

p=PROWS[r]；

q=p；

while（p）

{ q=p；p=p->next；}

if （p==q）{ PROWS[r]=s；} else { q->next=s；}}}

4.3 基于带行指针数组的单链表存储结构稀疏矩阵相加算法

两个矩阵相加前提条件是两个矩阵行数和列数分别对应相等。相加的结果仍是同型矩阵。设有两个m×n矩阵A和B，相加结果设为C，也是一个m×n的矩阵。对于C中每个元素C[i][j]有以下三种情况：[4]

[CIJ=aijbijaij+bijbij=0aij=0aij=0且bij=0 ]

在带行指针数组的单链表存储结构上实现稀疏矩阵相加算法思想是：分别建立矩阵A和B的带行指针数组的单链表存储结构。相加算法从矩阵的第一行起逐行进行。对每一行都从行链表的头指针开始，分别找到A和B在该中的第一个非零元结点后开始比较，然后按不同情况分别处理。设两个指针p和q分别初始化为指向A、B链表存储结构的第一行第一个非零元结点，当p、q都非空时（意味着p、q所指的当前行没有遍历到行尾），生成C中结点s的三种情况可按如下处理。

1）若p->col < q->col或者 q==NULL时，则将p结点数据复制到s，p指针向右移动，指向本行下一个非零元。

2）若p->col > q->col或者 p==NULL时，则将q结点数据复制到s，q指针向右移动，指向本行下一个非零元。

3）若p->col == q->col且p->value + q->value[≠]0，则将q结点数据复制到s，s->value=p->value+q->value， p和q指针分别向右移动，指向各自行下一个非零元。

同理，如此重复处理其余每一行，直到所有结点都被合并到结果矩阵中。

template

voidAdd（SparseMatrix&b，SparseMatrix&C）

{ TripleNode *p，*q，*s，*t；

int i；

T v；

if （Rows ！= b.Rows||Cols ！= b.Cols）

{ cerr<<"Incompatible Matrix！"<

for （ i =0；i

{ p = PROWS[i]；

q = b.PROWS[i]；

while（p && q）

{ s=newTripleNode ；

if （p->col< q->col）

{ *s=*p；C.insert（i，s）； C.Terms++；p=p->next；}

elseif （p->col> q->col）

{ *s=*q；C.insert（i，s）； C.Terms++；q=q->next；}

else

{v=p->value+q->value；

if （v）

{ *s=*p；s->value=v；C.insert（i，s）；C.Terms++；}

p=p->next；q=q->next；}}

while（p）

{ s=newTripleNode ； *s=*p；

C.insert（I，s）；C.Terms++；p=p->next；}

while（q）

{ s=newTripleNode ；*s=*q；

C.insert（i，s）；C.Terms++；q=q->next； } }}

4.4 基于帶行指针数组的单链表存储结构的稀疏矩阵输出算法

从行指针数组的第一行开始，逐行遍历并输入链表中非零元的三元组形式。

template

voidprint_SparseMatrix（）

{Two_tuple *p；

cout<<"rows："<

for （int i =0；i

{ p=PROWS[i]；

while（p）

{ cout<<"（"<col<<"，"<value<<'）'<

p=p->next；}}}

5算法性能分析

在稀疏矩阵带行指针数组的单链表存储结构上，建立单链表存储结构的算法时间复杂度是O（Rows+Terms）。相加算法的主要过程是对A和B单链表逐行进行扫描，其时间性能主要取决于A、B的行数Rows和非零元素的个数Terms，因此，该矩阵相加算法时间复杂度为O（2*Rows+A.Terms+B.terms）。当稀疏矩阵的非零元素的个数Terms远远小于矩阵的行、列数时，矩阵相加算法的时间复杂度比采用二维数组存储时的时间复杂度O（Rows [× ]Cols）要好很多。

参考文献：

[1] 李平，王秀英.计算机软件技术基础[M].北京：机械工业出版社，2015：61-63。

[2] 徐孝凯.数据结构实用教程（C/C++描述）[M].北京：清华大学出版社，2004：98-99.

[3] 郑莉，董渊，何江舟.C++语言程序设计[M].北京：清华大学出版社，2010：309-314.

[4] 张小莉，王苗，罗文劼.数据结构与算法[M].3版.北京：机械工业出版社，2016：97-98.