基本概念:

      如果一个m×n 矩阵中有“许多”元素为0，则称该矩阵为稀疏矩阵（sparse）。不是稀疏的矩阵被称为稠密矩阵（dense）。在稀疏矩阵和稠密矩阵之间并没有一个精确的界限。 n×n 的对角矩阵和三对角矩阵都是稀疏矩阵，二者都有 O (n)个非0元素和O (n2)个0元素。一个n×n 的三角矩阵是稀疏矩阵吗？它至少有 n(n- 1 ) / 2个0元素，最多有n(n+ 1 ) / 2个非0元素。在本节中我们规定若一个矩阵是稀疏矩阵，则其非 0元素的数目应小于n2 / 3，在有些情况下应小于n2 / 5，因此可将把三角矩阵视为稠密矩阵。

      诸如对角矩阵和三对角矩阵这样的稀疏矩阵，其非 0区域的结构很有规律，因此可以设计一个很简单的存储结构，该存储结构的大小就等于矩阵非 0区域的大小。本节中主要考察具有不规则非0区域的稀疏矩阵。

如图存储：

数组描述：

链表描述：

数组描述部分：

定义存储节点：

/*
数组结构中的  稀疏矩阵  数组与链表表示对应书中代码：数据结构算法与应用c++描述程序编写：比卡丘不皮编写时间：2020年7月10日 09:42:35
*/
#pragma once
#include <iostream>
#include "all_error.h"
using namespace std;//声明
template<class T>
class SparseMatrix;//数组描述节点值
template<class T>
class Term
{//这里添加友元，可以访问私有成员friend SparseMatrix<T>;
private:int row, col;T value;
};

 #include "all_error.h" 在我记录的博客： 传送门第一个创建

class SparseMatrix的定义：

template<class T>
class SparseMatrix
{//对于友元函数添加template<class T>，不是在其他文件中无法识别外部符号，这里一定要注意，书中没有写template<class T>friend  ostream & operator << (ostream & out, const SparseMatrix<T> & x);template<class T>friend  istream & operator >> (istream & in, const SparseMatrix<T> & x);
public:SparseMatrix(int maxTerms = 10);~SparseMatrix() { delete[] a; }void Transpose(SparseMatrix<T> &b) const;void Add(const SparseMatrix<T> &b, SparseMatrix<T> &c) const;
private:void Append(const Term<T>& t);int rows, cols; //矩阵维度int terms; //非0元素数目Term<T> *a;// 存储非0元素的数组int MaxTerms; //数组a的大小};

       这里要注意，在添加友元函数的时候，一定要加上template<class T>，要是想在其他文件中调用必须要加上，不然出现无法解析外部符号，毕竟是friend  有关模板类。

构造函数：

//稀疏矩阵的构造函数
template<class T>
SparseMatrix<T>::SparseMatrix(int maxTerms)
{if (maxTerms < 1){throw OutOfBounds();}MaxTerms = maxTerms;a = new Term<T>[MaxTerms];terms = cols = rows = 0;
}

输入和输出函数：

template<class T>
ostream & operator<<(ostream & out, const SparseMatrix<T>& x)
{//把*this 送至输出流//输出矩阵的特征out << " rows = " << x.rows << "columns = " << x.cols << endl;out << " nonzero = " << x.terms << endl;//输出非0元素，每行1个for (int i = 0; i < x.terms; i++){out << "a(" << x.a[i].row << "," << x.a[i].col << ")=" << x.a[i].value << endl;}return out;
}template<class T>
istream & operator >> (istream & in, const SparseMatrix<T>& x)
{//输入一个稀疏矩阵//输入矩阵的特征cout << "Enter number of rows, columns, and terms" << endl;in >> x.rows >> x.cols >> x.terms;if (x.terms > x.MaxTerms){throw OutOfBounds();}for (int i = 0; i< x.terms; i++){cout << "Enter row, column, and value of term " << (i+1) << endl;in >> x.a[i].row >> x.a[i].col >> x.a[i].value;}return in;
}

 转置一个稀疏矩阵：

template<class T>
void SparseMatrix<T>::Transpose(SparseMatrix<T>& b) const
{//把 *this 的转置结果送入 b//确信 b 有足够的空间if (terms > b.MaxTerms){throw Noman();}//设置转置特征b.cols = rows;b.rows = cols;b.terms = terms;//初始化int  ColSize[100] = {0};int  RowNext[100] = {0};//计算 * this每一列的非0元素数for (int i = 1; i <= cols; i++) // 初始化ColSize[i] = 0;for (int = 0; i < terms; i++)  ColSize[a[i].col]++;//给出b中每一行的起始点RowNext[1] = 0;for (int i = 2; i <= cols; i++)RowNext[i] = RowNext[i - 1] + ColSize[i - 1];//执行转置操作for (int i = 0; i < terms; i++){int j = RowNext[a[i].col]++;//在b中的位置b.a[j].row = a[i].col;b.a[j].col = a[i].row;b.a[j].value = a[i].value;}}

代码解析先看图：

ColSize[] 记录的数据：

ColSize 记录了每一列的个数，比如第一列非0个数是0，第2列数据有两个值，以此类推。

RowNext[]记录的数据：

表示当前列前面有多少个数，比如第2列，前一列没有数据，就是0，在比如第3列，前面有两个值，这里存储2.

本段程序中要注意一件事，源书中的代码：

int *ColSize = new int[cols + 1];
int *RowNext = new int[rows + 1];

       这里可以扩展成这个样子，但是，在程序结束后，回收的时候有可能会出现错误，出现代码卡顿的现象，这里就不推荐这样来了，其实用vector 来代替更加好，这里为了不适用stl的东西，就简化了。

for (int i = 0; i < terms; i++){int j = RowNext[a[i].col]++;//在b中的位置b.a[j].row = a[i].col;b.a[j].col = a[i].row;b.a[j].value = a[i].value;}

这段代码中就是记录每个元素b初始位置：

       如图，i 是原来数组的下标，j就是对应新的矩阵的下标，如i = 0的时候，是col是 4 对应的，对应前面有3个值，所以放在下面的第3下标 就是 b[3], 结束后 RowNext[4]++,为下一次访问这个位置是加一（因为已经取出一个数了）。比如value = 9的时候访问的也是 RowNext[4] 的值，但是前面有4个值，RowNext[4] 原本是3，这里++后就是4了。

append函数

template<class T>
void SparseMatrix<T>::Append(const Term<T>& t)
{//把一个非0元素 t添加到 * this之中if (terms >= MaxTerms){throw Noman();}a[terms] = t;terms++;
}

add函数

template<class T>
void SparseMatrix<T>::Add(const SparseMatrix<T>& b, SparseMatrix<T>& c) const
{//计算c = (*this) + b.if (rows != b.rows || cols != b.cols){throw OutOfBounds();}c.rows = rows;c.cols = cols;c.terms = 0; //初值//定义 *this 和 b 的游标int ct = 0, cb = 0;while (ct < terms && cb < b.terms){int indt = a[ct].row * cols + a[ct].col;int indb = b.a[cb].row * cols + b.a[cb].col;if (indt < indb){c.Append(a[ct]);ct++;}else{if (indt == indb){//和不是0才加入if (a[ct].value + b.a[cb].value){Term<T> t;t.row = a[ct].row;t.col = a[ct].col;t.value = a[ct].value + b.a[cb].value;c.Append(t);}ct++;cb++;}else{c.Append[b.a[cb]];cb++;}}// 复制剩余元素for (; ct < terms; ct++)c.Append(a[ct]);for (; cb < b.terms; cb++)c.Append(b.a[cb]);}}

      函数Add中的while循环最多会执行 terms + b.terms次，因为在循环过程中 ct , cb会不断增值。第一个for循环最多会执行terms次，而第二个for循环最多会执行O ( b.terms )次。另外，每个循环中的每一次循环只需要常量时间。因此函数 Add的时间复杂性为O( terms + b.terms )。如果用二维数组来描述每个矩阵，则两个矩阵相加需耗时 O ( rows * cols )。当terms + b.terms远小于rows * cols时，稀疏矩阵的加法执行效率将大大提高。

测试函数：

void testSparseMatrix()
{SparseMatrix<int> SpaMat(20);cout << "请输入" << endl;cin >> SpaMat;cout << SpaMat << endl;SparseMatrix<int> b;SpaMat.Transpose(b);cout << b << endl;SparseMatrix<int> c;SpaMat.Add(b, c);cout << c << endl;
}

测试结果：

有关相加的程序大家可以来写一下，这里时间关系就不在写了。

喜欢我的博客的小伙伴可以关注我，一起加油学习。