稀疏矩阵的实现和转置算法

TriSparseMatrix.h

  1 #pragma once
  2
  3 #include
  4 #include<string.h>
  5 #include
  6 #define DEFAULT_SIZE 5
  7 #define MAX_SIZE 20
  8 typedef int Status;
  9 #define FALSE -1
 10 #define SUCCESS 1
 11 //定义默认尺寸
 12
 13 using namespace std;
 14
 15 template<class ElemType>
 16 struct Triple {
 17     //数据成员
 18     int row, col;        //非零元素的行下标和列下标
 19     ElemType value;        //非零元素的值
 20
 21     //构造函数
 22     Triple() {
 23         row = 0;
 24         col = 0;
 25         value = NULL;
 26     };        //无参构造函数
 27     Triple(int r, int c, ElemType v);        //有参构造函数
 28 };
 29
 30 template <class ElemType>
 31 Triple::Triple(int r, int c, ElemType v) {
 32     row = r;        //初始化行标
 33     col = c;        //初始化列标
 34     value = v;        //初始化非零元素
 35 }
 36
 37 template<class ElemType>
 38 class TriSparseMatrix {
 39 protected:
 40     //稀疏矩阵三元组顺序表的数据成员
 41     Triple* triElems;    //存储稀疏矩阵的三元组表
 42     int maxSize;                //非零元素的最大值
 43     int rows, cols, num;        //稀疏矩阵的行数，列数，非零元素个数
 44 public:
 45     //稀疏矩阵三元组顺序表的函数成员
 46     TriSparseMatrix(int rs = DEFAULT_SIZE, int cs = DEFAULT_SIZE, int size = DEFAULT_SIZE);
 47     ~TriSparseMatrix();            //析构函数
 48     int GetRows() const {        //返回稀疏矩阵行数
 49         return rows;
 50     }
 51
 52     int GetCols() const {
 53         return cols;
 54     }
 55
 56     int GetNum() const {
 57         return num;
 58     }
 59
 60     Status SetElem(int r, int c, const ElemType& v);        //修改指定元素的值
 61     Status GetElem(int r, int c, ElemType& v);                //取指定位置的值
 62     TriSparseMatrix(const TriSparseMatrix& copy);    //复制构造函数
 63     TriSparseMatrix& operator = (const TriSparseMatrix& copy);//赋值运算符重载
 64     void CreateElem(int i);        //创建第i个非零元素
 65     void TriPrint();        //打印矩阵
 66
 67     void SimpleTranspose(TriSparseMatrix& b);
 68     //将稀疏矩阵source转置成b的简单算法；
 69     void FastTranspose(TriSparseMatrix& b);
 70     //将稀疏矩阵source转置成b的快速算法；
 71 };
 72
 73
 74 template <class ElemType>
 75 TriSparseMatrix::TriSparseMatrix(int rs, int cs, int size) {
 76     rows = rs;
 77     cols = cs;
 78     num = size;
 79     maxSize = MAX_SIZE;
 80     triElems = new Triple[maxSize];
 81 }
 82
 83 template <class ElemType>
 84 TriSparseMatrix::~TriSparseMatrix() {
 85     delete[] triElems;
 86 }
 87
 88 template <class ElemType>
 89 Status TriSparseMatrix::SetElem(int r, int c, const ElemType& v) {
 90     if (r < 0 || c < 0 || r >= rows || c >= cols) {
 91         cout << "位置不合法" << endl;
 92         return FALSE;
 93     }
 94     else {
 95         for (int i = 0; i < num; i++) {
 96             if (triElems[i].row == r && triElems[i].col == c) {
 97                 triElems[i].value = v;
 98                 return SUCCESS;
 99             }
100         }
101         return 0;
102     }
103 }
104
105 template <class ElemType>
106 Status TriSparseMatrix ::GetElem(int r, int c, ElemType& v) {
107     if (r < 0 || c < 0 || r >= rows || c >= cols) {
108         cout << "位置不合法" << endl;
109         return FALSE;
110     }
111     else {
112         for (int i = 0; i < num; i++) {
113             if (triElems[i].row == r && triElems[i].col == c) {
114                 v = triElems[i].value;
115                 return SUCCESS;
116             }
117         }
118         return 0;
119     }
120 }
121
122 template <class ElemType>
123 TriSparseMatrix::TriSparseMatrix(const TriSparseMatrix& copy) {
124     int i = copy.GetNum();
125     num = i;
126     rows = copy.GetRows();
127     cols = copy.GetCols();
128     triElems = new Triple[i];
129 }
130
131 template<class ElemType>
132 void TriSparseMatrix< ElemType>::TriPrint() {
133     int i = 0;
134     for (int row = 0; row < rows; row++) {
135         for (int col = 0; col < cols; col++) {
136             if (triElems[i].row == row && triElems[i].col == col) {
137                 cout << triElems[i].value << " ";
138                 i++;
139             }
140             else {
141                 cout << 0 << " ";
142             }
143         }
144         cout << endl;
145     }
146 }
147
148 template <class ElemType>
149 TriSparseMatrix& TriSparseMatrix::operator=(const TriSparseMatrix& copy) {
150     if (© != this) {
151         delete[]triElems;
152         cols = copy.GetCols();
153         rows = copy.GetRows();
154         triElems = new Triple[copy.GetNum()];
155     }
156     return *this;
157 }
158
159 template <class ElemType>
160 void TriSparseMatrix::CreateElem(int i) {
161     int col, row;
162     ElemType val;
163     cout << "请输入非零元素的行数：";
164     cin >> row;
165     cout << "请输入非零元素的列数：";
166     cin >> col;
167     cout << "请输入非零元素的值：";
168     cin >> val;
169     triElems[i].row = row;
170     triElems[i].col = col;
171     triElems[i].value = val;
172 }
173
174 template<class ElemType>
175 void TriSparseMatrix::SimpleTranspose(TriSparseMatrix& b) {
176     //长宽进行转置，再删除已有空间
177     b.rows = cols;
178     b.cols = rows;
179     b.num = num;
180     b.maxSize = maxSize;
181     delete[]b.triElems;
182
183     b.triElems = new Triple[b.maxSize];
184     if (b.num > 0) {
185         int i = 0;        //稀疏矩阵b下一个三元组的存放位置
186         for (int col = 0; col < cols; col++) {//列为0的遍历一遍顺序存储，然后列为1、2、3……
187             for (int j = 0; j < num; j++) {
188                 if (triElems[j].col == col) {
189                     b.triElems[i].row = triElems[j].col;
190                     b.triElems[i].col = triElems[j].row;
191                     b.triElems[i].value = triElems[j].value;
192                     i++;
193                 }//if
194             }//for
195         }//for
196     }//if
197 }//SimpleTranspose时间复杂度O(cols*num)
198
199 template<class ElemType>
200 void TriSparseMatrix::FastTranspose(TriSparseMatrix& b) {
201     //在b中的存储位置只是指在b转换的一维数组中的存储位置，而不是在真实的m*n矩阵中的位置
202     b.rows = cols;
203     b.cols = rows;
204     b.num = num;
205     b.maxSize = maxSize;
206     delete[]b.triElems;
207     b.triElems = new Triple[b.maxSize];
208
209     int* cNum = new int[cols + 1];    //存放矩阵中每一列的非零元素的个数
210     int* cPos = new int[cols + 1];    //存放原矩阵中每一列的第一个非零元素在b中的位置
211
212     int col, i;
213     if (b.num > 0) {
214         for (col = 0; col < cols; col++) {    //初始化cNum数组
215             cNum[col] = 0;
216         }
217         for (i = 0; i < b.num; i++) {        //统计原矩阵中每一列的非零元素个数
218             cNum[triElems[i].col]++;
219         }
220         cPos[0] = 0;    //第0列的第一个非零元素就在0位置
221         for (col = 1; col < cols; col++) {
222             //循环求每一列的第一个非零元素在b存储的位置
223             cPos[col] = cPos[col - 1] + cNum[col - 1];
224         }
225         for (i = 0; i < num; i++) {
226             //循环遍历原矩阵中的三元组。
227             int j = cPos[triElems[i].col];
228             b.triElems[j].row = triElems[i].col;
229             b.triElems[j].col = triElems[i].row;
230             b.triElems[j].value = triElems[i].value;
231             ++cPos[triElems[i].col];    //为同一列的下一个元素标明位置。
232         }
233     }
234     delete[]cNum;
235     delete[]cPos;
236 }//由四个并列循环组成，时间复杂度O(num)

Client.cpp

 1 #include"TriSparseMatrix.h"
 2
 3 void Test() {
 4     TriSparseMatrix<int> tri1(5, 5, 10);    //创建一个5行5列非零元素最多10个的稀疏矩阵
 5     for (int i = 0; i < 10; i++) {
 6         tri1.CreateElem(i);
 7     }
 8     tri1.TriPrint();
 9     TriSparseMatrix<int> tri2 = NULL;
10     tri1.SimpleTranspose(tri2);
11     cout << "简单算法转置后：" << endl;
12     tri2.TriPrint();
13
14     tri1.FastTranspose(tri2);
15     cout << "快速算法转置后：" << endl;
16     tri2.TriPrint();
17 }
18
19 int main() {
20     Test();
21     return 0;
22 }

Original: https://www.cnblogs.com/JIAcheerful/p/16177036.html
Author: 云霄雨霁
Title: 稀疏矩阵的实现和转置算法