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

稀疏矩阵带行指针数组的单链表存储结构及相加算法实现 　　摘要：带行指针数组的单链表存储结构是稀疏矩阵压缩存储的一种实用的链式存储结构。文中描述了稀疏矩阵带行指针数组的单链表存储结构及基于此链式存储结构的相加运算算法，并应用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=（TripleNodex） 　　{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（SparseMatrixb，SparseMatrixc）； 　　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；IRows；i++）PROWS[i]=NULL；} 　　4.2 建立带行指针数组的单链表存储结构 　　在实例化稀疏矩阵时通过构造函数建立只有行指针数组的空的稀疏矩阵。在此基础上按行优先，列号从小到大顺序输入非零元所在行、列和值，申请一个结点所需存储空间，并将非零元的列号和值存入相应域，按列号从小到大的顺序将此结点插入到对应行尾部。构造函数及建立链表结构代码： 　　template 　　voidcreate_SparseMatrix（） 　　{ int r，c； 　　T v； 　　Two_tuple *p，*q，*s； 　　for （int i=0；iTerms；i++） 　　{cinrc