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

龙源期刊网 https://www.wendangku.net/doc/d34251295.html,

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

作者：邬恩杰张静

来源：《电脑知识与技术》2016年第36期

摘要：带行指针数组的单链表存储结构是稀疏矩阵压缩存储的一种实用的链式存储结构。文中描述了稀疏矩阵带行指针数组的单链表存储结构及基于此链式存储结构的相加运算算法，并应用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稀疏矩阵带行指针数组的单链表存储结构类型