稀疏矩阵压缩存储之十字链表

发表于 | 分类于

基础知识

在使用三元组顺序表实现矩阵压缩存储时，三元组存放在连续的内存区域中，在进行矩阵运算时非零的元素可能变成零元素，非零元素会出现新值，此时需要移动数组中的三元组，对空间消耗是巨大的（本人三元组顺序表实现中直接开辟了一个新的数组），如果结合链表的优点，那么可以使用称为十字链表的数据结构，本文将实现之并完成矩阵常用的操作（可直接采用三元组顺序表中定义的操作）。

在实现十字链表压缩存储稀疏矩阵之前，预先定义十字链表三元组节点结构如下：

1
2
3
4
5
6
7
8
9
10
template<typename DataType>
struct OrthAtom
{
        int row;       /*行号*/
        int col;       /*列号*/
        DataType ele;  /*存放的数据*/
        OrthAtom *rowNext; /*同一行下一个元素*/
        OrthAtom *colNext; /*同一列下一个元素*/
        OrthAtom() : row(0), col(0), rowNext(nullptr), colNext(nullptr) {}
};

上述结构和三元组顺序表最大的不同是增加了两个链接指针。

需要是实现的矩阵基本运算主要有：

  • 矩阵转置：TransposeMatrix
  • 矩阵加法：AddMatrix
  • 矩阵减法：SubMatrix
  • 矩阵乘法：MultiMatrix
  • 打印矩阵：PrintMatrix
  • 清空整个矩阵：MakeEmpty

十字链表基本定义

根据上述分析可定义如下基本ADT:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <vector>
using std::vector;

template<typename DataType>
class OrthList
{
public:
        OrthList(vector<vector<DataType>> &inArray);
        ~OrthList();
        void TransposeMatrix();         /*转置矩阵*/
        void AddMatrix(OrthList<DataType> &otherMatrix); /*加上另外一个矩阵，第二个矩阵保持不变*/
        void SubMatrix(OrthList<DataType> &otherMatrix); /*减去另外一个矩阵，第二个矩阵保持不变*/
        void MultiMatrix(OrthList<DataType> &otherMatrix); /*乘上另外一个矩阵，第二个矩阵保持不变*/
        vector<vector<DataType>> TransformTo2DArray(); /*转换成二维数组*/
        void PrintMatrix(); /*打印矩阵*/
        void MakeEmpty();   /*清空并释放内存*/
private:
        vector<OrthAtom<DataType>> rowDummy; /*行哑节点，内含矩阵行数*/
        vector<OrthAtom<DataType>> colDummy; /*列哑节点，内含矩阵列数*/
};

如上即为整个十字链表的ADT基本结构，基本仿照三元组顺序表中的定义，具体含义可见注释。接下来依次实现个函数。

三元组顺序表ADT的实现

  • 构造函数

构造函数主要将二维存储的稀疏矩阵转变为十字链表矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template<typename DataType>
OrthList<DataType>::OrthList(vector<vector<DataType>> &inArray) : rowDummy(inArray.size()), colDummy(inArray.size() > 0 ? inArray[0].size() : 0)
{
        if (inArray.size() > 0 && inArray[0].size() > 0) {
                for (int i = 0; i < int(inArray.size()); i++) {
                        for (int j = 0; j < int(inArray[i].size()); j++) {
                                if (inArray[i][j] != DataType(0)) {
                                        OrthAtom<DataType> *rowIter = &rowDummy[i]; /*行遍历*/
                                        OrthAtom<DataType> *colIter = &colDummy[j]; /*列遍历*/
                                        while (rowIter->rowNext != nullptr && rowIter->rowNext->col < j+1) {
                                                rowIter = rowIter->rowNext;
                                        }
                                        while (colIter->colNext != nullptr && colIter->colNext->row < i+1) {
                                                colIter = colIter->colNext;
                                        }
                                        OrthAtom<DataType> *newNode = new OrthAtom<DataType>; /*新节点*/
                                        newNode->row = i+1; /*下标从1开始*/
                                        newNode->col = j+1; /*下标从1开始*/
                                        newNode->ele = inArray[i][j];
                                        newNode->rowNext = rowIter->rowNext;
                                        newNode->colNext = colIter->colNext;
                                        rowIter->rowNext = colIter->colNext = newNode;
                                }
                        }
                }
        }
}

上述在定位插入点位置时可以进一步优化。

  • 析构函数

析构主要释放创建十字链表节点时申请的空间，直接调用MakeEmpty函数即可，具体代码如下：

1
2
3
4
5
template<typename DataType>
OrthList<DataType>::~OrthList<DataType>()
{
        MakeEmpty();
}
  • 矩阵转置

和三元组顺序表不同的是，十字链表转置只需交换节点内数据即可，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <algorithm>
using std::swap;

template<typename DataType>
void OrthList<DataType>::TransposeMatrix()
{
        OrthAtom<DataType> *cycleIter = nullptr; /*遍历迭代器*/
        for (size_t i = 0; i < rowDummy.size(); i++) {
                cycleIter = rowDummy[i].rowNext;
                while (cycleIter != nullptr) {
                        OrthAtom<DataType> * tmp = cycleIter;
                         cycleIter = cycleIter->rowNext;
                         /*交换下标和指针*/
                         swap(tmp->row, tmp->col);
                         swap(tmp->rowNext, tmp->colNext);
                 }
                 swap(rowDummy[i].rowNext, rowDummy[i].colNext);
         }

         for (size_t i = 0; i < colDummy.size(); i++) {
                 swap(colDummy[i].rowNext, colDummy[i].colNext);
         }
         swap(rowDummy, colDummy);
}
  • 矩阵相加

在进行矩阵加法，首先需要判断两个矩阵是否能够相加，然后我们也可以借鉴三元组顺序表的处理方式，不过我们在进行加法时按照行的顺序一行一行加并且保持一个列节点数组用来指定列插入的顺序以节省插入时间，具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
template<typename DataType>
void OrthList<DataType>::AddMatrix(OrthList<DataType> &otherMatrix)
{
        if (rowDummy.size() != otherMatrix.rowDummy.size() || colDummy.size() != otherMatrix.colDummy.size() ) {
                return;
        }

        vector<OrthAtom<DataType> *> colCycleIter(colDummy.size(), nullptr); /*列指针，方便快速插入列中*/
        for (size_t i = 0; i < colDummy.size(); i++) {
                colCycleIter[i] = &colDummy[i];
        }

        for (size_t i = 0; i < rowDummy.size(); i++) {
                /*重定位列节点*/
                for (size_t j = 0; j < colCycleIter.size(); j++) {
                        while (colCycleIter[j]->colNext != nullptr && colCycleIter[j]->colNext->row < int(i)+1) {
                                colCycleIter[j] = colCycleIter[j]->colNext;
                        }
                }

                OrthAtom<DataType> *firstIter = &rowDummy[i]; /*第一个矩阵*/
                OrthAtom<DataType> *secondIter = &otherMatrix.rowDummy[i]; /*第二个矩阵*/
                while (firstIter->rowNext != nullptr && secondIter->rowNext != nullptr) {
                        if (firstIter->rowNext->row < secondIter->rowNext->row) {
                                firstIter = firstIter->rowNext;
                        }
                        else if (firstIter->rowNext->row > secondIter->rowNext->row) {
                                OrthAtom<DataType> *newNode = new OrthAtom<DataType>; /*新节点*/
                                int colIndex = secondIter->rowNext->col;
                                newNode->rowNext = firstIter->rowNext;
                                newNode->colNext = colCycleIter[colIndex-1]->colNext;
                                newNode->ele = secondIter->rowNext->ele;
                                newNode->row = secondIter->rowNext->row;
                                newNode->col = secondIter->rowNext->col;
                                firstIter->rowNext = newNode;
                                colCycleIter[colIndex-1]->colNext = newNode;
                                secondIter = secondIter->rowNext;
                                firstIter = firstIter->rowNext;
                        }
                        else if (firstIter->rowNext->col < secondIter->rowNext->col) {
                                firstIter = firstIter->rowNext;
                        }
                        else if (firstIter->rowNext->col > secondIter->rowNext->col) {
                                OrthAtom<DataType> *newNode = new OrthAtom<DataType>; /*新节点*/
                                int colIndex = secondIter->rowNext->col;
                                newNode->rowNext = firstIter->rowNext;
                                newNode->colNext = colCycleIter[colIndex-1]->colNext;
                                newNode->ele = secondIter->rowNext->ele;
                                newNode->row = secondIter->rowNext->row;
                                newNode->col = secondIter->rowNext->col;
                                firstIter->rowNext = newNode;
                                colCycleIter[colIndex-1]->colNext = newNode;
                                secondIter = secondIter->rowNext;
                                firstIter = firstIter->rowNext;
                        }
                        else {
                                if (firstIter->rowNext->ele + secondIter->rowNext->ele != DataType(0)) {
                                        firstIter->rowNext->ele += secondIter->rowNext->ele;
                                        firstIter = firstIter->rowNext;
                                }
                                else {
                                        OrthAtom<DataType> *toBeDelete = firstIter->rowNext; /*待删除节点*/
                                        firstIter->rowNext = toBeDelete->rowNext;
                                        int colIndex = toBeDelete->col;
                                        colCycleIter[colIndex-1]->colNext = toBeDelete->colNext;
                                        delete toBeDelete;
                                }
                                secondIter = secondIter->rowNext;
                        }
                }

                /*剩下的第二个矩阵的非零元*/
                while (secondIter->rowNext != nullptr) {
                        OrthAtom<DataType> *newNode = new OrthAtom<DataType>; /*新节点*/
                        int colIndex = secondIter->rowNext->col;
                        newNode->rowNext = firstIter->rowNext;
                        newNode->colNext = colCycleIter[colIndex-1]->colNext;
                        newNode->ele = secondIter->rowNext->ele;
                        newNode->row = secondIter->rowNext->row;
                        newNode->col = secondIter->rowNext->col;
                        firstIter->rowNext = newNode;
                        colCycleIter[colIndex-1]->colNext = newNode;
                        secondIter = secondIter->rowNext;
                        firstIter = firstIter->rowNext;
                }
        }
}
  • 矩阵减法

将加法代码稍作修改即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
template<typename DataType>
void OrthList<DataType>::SubMatrix(OrthList<DataType> &otherMatrix)
{
        if (rowDummy.size() != otherMatrix.rowDummy.size() || colDummy.size() != otherMatrix.colDummy.size() ) {
                return;
        }

        vector<OrthAtom<DataType> *> colCycleIter(colDummy.size(), nullptr); /*列指针，方便快速插入列中*/
        for (size_t i = 0; i < colDummy.size(); i++) {
                colCycleIter[i] = &colDummy[i];
        }

        for (size_t i = 0; i < rowDummy.size(); i++) {
                /*重定位列节点*/
                for (size_t j = 0; j < colCycleIter.size(); j++) {
                        while (colCycleIter[j]->colNext != nullptr && colCycleIter[j]->colNext->row < int(i)+1) {
                                colCycleIter[j] = colCycleIter[j]->colNext;
                        }
                }

                OrthAtom<DataType> *firstIter = &rowDummy[i]; /*第一个矩阵*/
                OrthAtom<DataType> *secondIter = &otherMatrix.rowDummy[i]; /*第二个矩阵*/
                while (firstIter->rowNext != nullptr && secondIter->rowNext != nullptr) {
                        if (firstIter->rowNext->row < secondIter->rowNext->row) {
                                firstIter = firstIter->rowNext;
                        }
                        else if (firstIter->rowNext->row > secondIter->rowNext->row) {
                                OrthAtom<DataType> *newNode = new OrthAtom<DataType>; /*新节点*/
                                int colIndex = secondIter->rowNext->col;
                                newNode->rowNext = firstIter->rowNext;
                                newNode->colNext = colCycleIter[colIndex-1]->colNext;
                                newNode->ele = -secondIter->rowNext->ele;
                                newNode->row = secondIter->rowNext->row;
                                newNode->col = secondIter->rowNext->col;
                                firstIter->rowNext = newNode;
                                colCycleIter[colIndex-1]->colNext = newNode;
                                secondIter = secondIter->rowNext;
                                firstIter = firstIter->rowNext;
                        }
                        else if (firstIter->rowNext->col < secondIter->rowNext->col) {
                                firstIter = firstIter->rowNext;
                        }
                        else if (firstIter->rowNext->col > secondIter->rowNext->col) {
                                OrthAtom<DataType> *newNode = new OrthAtom<DataType>; /*新节点*/
                                int colIndex = secondIter->rowNext->col;
                                newNode->rowNext = firstIter->rowNext;
                                newNode->colNext = colCycleIter[colIndex-1]->colNext;
                                newNode->ele = -secondIter->rowNext->ele;
                                newNode->row = secondIter->rowNext->row;
                                newNode->col = secondIter->rowNext->col;
                                firstIter->rowNext = newNode;
                                colCycleIter[colIndex-1]->colNext = newNode;
                                secondIter = secondIter->rowNext;
                                firstIter = firstIter->rowNext;
                        }
                        else {
                                if (firstIter->rowNext->ele - secondIter->rowNext->ele != DataType(0)) {
                                        firstIter->rowNext->ele -= secondIter->rowNext->ele;
                                        firstIter = firstIter->rowNext;
                                }
                                else {
                                        OrthAtom<DataType> *toBeDelete = firstIter->rowNext; /*待删除节点*/
                                        firstIter->rowNext = toBeDelete->rowNext;
                                        int colIndex = toBeDelete->col;
                                        colCycleIter[colIndex-1]->colNext = toBeDelete->colNext;
                                        delete toBeDelete;
                                }
                                secondIter = secondIter->rowNext;
                        }
                }

                /*剩下的第二个矩阵的非零元*/
                while (secondIter->rowNext != nullptr) {
                        OrthAtom<DataType> *newNode = new OrthAtom<DataType>; /*新节点*/
                        int colIndex = secondIter->rowNext->col;
                        newNode->rowNext = firstIter->rowNext;
                        newNode->colNext = colCycleIter[colIndex-1]->colNext;
                        newNode->ele = -secondIter->rowNext->ele;
                        newNode->row = secondIter->rowNext->row;
                        newNode->col = secondIter->rowNext->col;
                        firstIter->rowNext = newNode;
                        colCycleIter[colIndex-1]->colNext = newNode;
                        secondIter = secondIter->rowNext;
                        firstIter = firstIter->rowNext;
                }
        }
}
  • 矩阵乘法

在进行矩阵乘法时，三元组顺序表需要一个额外的数组来快速定位行，而十字链表由于自身的特性可以快速寻址任意一行，因此在仿照三元组的顺序表乘法时可以简化一部分代码，但是乘法可能会改变矩阵列数，因此需要做一些特别的处理，具体见如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
template<typename DataType>
void OrthList<DataType>::MultiMatrix(OrthList<DataType> &otherMatrix)
{
        if (colDummy.size() != otherMatrix.rowDummy.size()) {
                return; /*是否可以相乘*/
        }

        /*只是为了快速生成数组，并不是为了复制哑节点*/
        vector<OrthAtom<DataType>> newColDummy(otherMatrix.colDummy.begin(), otherMatrix.colDummy.end());

        vector<OrthAtom<DataType> *> colCycleIter(newColDummy.size(), nullptr); /*列指针，方便快速插入列中*/
        for (size_t i = 0; i < newColDummy.size(); i++) {
                colCycleIter[i] = &newColDummy[i];
                newColDummy[i].colNext = nullptr; /*清空原始数据*/
        }

        DataType *tmpAccumulate = new int[otherMatrix.colDummy.size()]; /*记录每行各列的累加和*/

        /*一行一行处理*/
        for (size_t i = 0; i < rowDummy.size(); i++) {

                for (size_t j = 0; j < otherMatrix.colDummy.size(); j++) {
                        tmpAccumulate[j] = DataType(0); /*清空累加器*/
                }

                OrthAtom<DataType> *firstIter = rowDummy[i].rowNext; /*第一个矩阵*/

                while (firstIter != nullptr) {
                        int rowIndex = firstIter->col - 1; /*相乘矩阵的行号*/
                        OrthAtom<DataType> *secondIter = otherMatrix.rowDummy[rowIndex].rowNext; /*第二个矩阵*/
                        while (secondIter != nullptr) {
                                tmpAccumulate[secondIter->col-1] += firstIter->ele * secondIter->ele;
                                secondIter = secondIter->rowNext;
                        }
                        firstIter = firstIter->rowNext;
                }

                /*一行计算结束后进行压缩*/

                firstIter = &rowDummy[i]; /*重定位扫描器*/

                for (size_t j = 0; j < otherMatrix.colDummy.size(); j++) {
                        if (tmpAccumulate[j] != DataType(0)) {
                                /*行不为空*/
                                if (firstIter->rowNext != nullptr) {
                                        /*删除多余的节点*/
                                        while (firstIter->rowNext != nullptr && firstIter->rowNext->col < int(j) + 1) {
                                                OrthAtom<DataType> *toBeDelete = firstIter->rowNext; /*待删除节点*/
                                                firstIter->rowNext = toBeDelete->rowNext;
                                                delete toBeDelete;
                                        }
                                        /*如果下标相等直接修改值*/
                                        if (firstIter->rowNext != nullptr && firstIter->rowNext->col == int(j) + 1) {
                                                firstIter->rowNext->ele = tmpAccumulate[j];

                                                firstIter->rowNext->colNext = colCycleIter[j]->colNext;
                                                colCycleIter[j]->colNext = firstIter->rowNext;

                                                firstIter = firstIter->rowNext;

                                                colCycleIter[j] = colCycleIter[j]->colNext; /*由于逐行压缩，列指针向后移*/
                                        }
                                        else { /*否则需要创建一个新节点*/
                                                OrthAtom<DataType> *newNode = new OrthAtom<DataType>; /*新节点*/

                                                newNode->rowNext = firstIter->rowNext;
                                                newNode->colNext = colCycleIter[j]->colNext;
                                                newNode->ele = tmpAccumulate[j];
                                                newNode->row = i+1;
                                                newNode->col = j+1;

                                                colCycleIter[j]->colNext = newNode;
                                                colCycleIter[j] = colCycleIter[j]->colNext;

                                                firstIter->rowNext = newNode;
                                                firstIter = firstIter->rowNext;
                                        }
                                }
                                else { /*直接空了，需要新建节点*/
                                        OrthAtom<DataType> *newNode = new OrthAtom<DataType>; /*新节点*/

                                        newNode->rowNext = firstIter->rowNext;
                                        newNode->colNext = colCycleIter[j]->colNext;
                                        newNode->ele = tmpAccumulate[j];
                                        newNode->row = i+1;
                                        newNode->col = j+1;

                                        colCycleIter[j]->colNext = newNode;
                                        colCycleIter[j] = colCycleIter[j]->colNext;

                                        firstIter->rowNext = newNode;
                                        firstIter = firstIter->rowNext;
                                }
                        }
                }

                /*如果此时行后面还有元素说明是遗留的元素，需要删除*/
                while (firstIter->rowNext != nullptr) {
                        OrthAtom<DataType> *toBeDelete = firstIter->rowNext; /*待删除节点*/
                        firstIter->rowNext = toBeDelete->rowNext;
                        delete toBeDelete;
                }
        }

        /*修改列数哑节点*/
        colDummy.assign(newColDummy.begin(), newColDummy.end());

        delete [] tmpAccumulate;
}
  • 压缩矩阵转成二维数组

直接按行遍历，具体代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename DataType>
vector<vector<DataType>> OrthList<DataType>::TransformTo2DArray()
{
        vector<vector<DataType>> result(rowDummy.size(), vector<DataType>(colDummy.size(), DataType(0)));

        for (size_t i = 0; i < rowDummy.size(); i++) {
                OrthAtom<DataType> *cycleIter = rowDummy[i].rowNext; /*按行遍历*/
                while (cycleIter != nullptr) {
                        result[cycleIter->row-1][cycleIter->col-1] = cycleIter->ele;
                        cycleIter = cycleIter->rowNext;
                }
        }

        return result;
}
  • 打印矩阵

先调用转二维函数然后直接打印即可，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using std::cout;
using std::endl;

template<typename DataType>
void OrthList<DataType>::PrintMatrix()
{
        vector<vector<DataType>> result = TransformTo2DArray();

        for (size_t i = 0; i < result.size(); i++) {
                for (size_t j = 0; j < result[i].size(); j++) {
                        cout << result[i][j] << ";";
                }
                cout << endl;
        }
}
  • 清空矩阵

一行一行释放空间，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename DataType>
void OrthList<DataType>::MakeEmpty()
{
        vector<vector<DataType>> result(rowDummy.size(), vector<DataType>(colDummy.size(), DataType(0)));

        for (size_t i = 0; i < colDummy.size(); i++) {
                colDummy[i].colNext = nullptr; /*置空指针*/
        }
        for (size_t i = 0; i < rowDummy.size(); i++) {
                while (rowDummy[i].rowNext != nullptr) {
                        OrthAtom<DataType> *toBeDelete = rowDummy[i].rowNext; /*即将被删除*/
                        rowDummy[i].rowNext = toBeDelete->rowNext;
                        delete toBeDelete;
                }
        }
        return;
}

代码测试

通过随机生成两个稀疏矩阵，然后依次测试各个函数是否正确，测试代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <vector>
#include <random>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <chrono>
#include <functional>
using namespace std;
using namespace chrono;

int main()
{
	default_random_engine randEngine(unsigned(time(nullptr)));
	uniform_int_distribution<int> intDis(int(-100), int(100)); /*不能太大，防止溢出*/
        uniform_int_distribution<int> mnDis(int(1), int(100));

        int testTimes = 50;

	while ((testTimes--) > 0) {

                int m = mnDis(randEngine);
                int n = mnDis(randEngine);
                int k = mnDis(randEngine);

                uniform_int_distribution<int> deltaDis1(int(1), int(m*n));
                uniform_int_distribution<int> deltaDis2(int(1), int(n*k));

                vector<vector<int>> testMatrix1(m, vector<int>(n, 0));
                vector<vector<int>> testMatrix2(m, vector<int>(n, 0));
                vector<vector<int>> testMatrix3(n, vector<int>(k, 0));

                int delta1 = deltaDis1(randEngine);

                /*这里偷个懒，矩阵1，2同时生成*/
                for (int i = 0; i < delta1; i++) {
                        int row = mnDis(randEngine) % m;
                        int col = mnDis(randEngine) % n;
                        testMatrix1[row][col] = intDis(randEngine);

                        row = mnDis(randEngine) % m;
                        col = mnDis(randEngine) % n;
                        testMatrix2[row][col] = intDis(randEngine);
                }

                int delta2 = deltaDis2(randEngine);

                for (int i = 0; i < delta2; i++) {
                        int row = mnDis(randEngine) % n;
                        int col = mnDis(randEngine) % k;
                        testMatrix3[row][col] = intDis(randEngine);
                }

                OrthList<int> orthListTest1(testMatrix1);
                OrthList<int> orthListTest2(testMatrix2);
                OrthList<int> orthListTest3(testMatrix3);

                orthListTest1.TransposeMatrix(); orthListTest1.TransposeMatrix();
                cout << "矩阵转置测试结果：" << (orthListTest1.TransformTo2DArray() == testMatrix1 ? "Correct" : "Wrong") << endl;

                vector<vector<int>> addMatrix(m, vector<int>(n, 0));
                for (size_t i = 0; i < addMatrix.size(); i++) {
                        for (size_t j = 0; j < addMatrix[i].size(); j++) {
                                addMatrix[i][j] = testMatrix1[i][j] + testMatrix2[i][j];
                        }
                }

                orthListTest1.AddMatrix(orthListTest2);
                cout << "矩阵加法测试结果：" << (orthListTest1.TransformTo2DArray() == addMatrix ? "Correct" : "Wrong") << endl;

                orthListTest1.SubMatrix(orthListTest2);
                cout << "矩阵减法测试结果：" << (orthListTest1.TransformTo2DArray() == testMatrix1 ? "Correct" : "Wrong") << endl;

                vector<vector<int>> multiMatrix(m, vector<int>(k, 0));

                for (size_t i = 0; i < multiMatrix.size(); i++) {
                        for (size_t j = 0; j < multiMatrix[i].size(); j++) {
                                for (int k = 0; k < n; k++) {
                                        multiMatrix[i][j] += testMatrix1[i][k]*testMatrix3[k][j];
                                        /*矩阵乘法*/
                                }
                        }
                }

                orthListTest1.MultiMatrix(orthListTest3);
                cout << "矩阵乘法测试结果：" << (orthListTest1.TransformTo2DArray() == multiMatrix ? "Correct" : "Wrong") << endl;

                /*orthListTest1.PrintMatrix();*/
        }
	return 0;
}

参考资料

稀疏矩阵

数据结构