稀疏矩阵的加减乘求逆运算

1、稀疏矩阵的加、减、乘、求逆运算#include <iostream>#include <iomanip>using namespace std;const int MAXSIZE = 100;/定义非零元素的最多个数const int MAXROW = 10;定义数组行数的最大值const int SIZENUM = 10;typedef struct定义三元组元素int r, c;矩阵的行号和列号int v;/矩阵元素值Triple;typedef struct/定义普通三元组对象Triple dataMAXSIZE+1;int rows, cols, nzeroNu

2、ms;行数、列数、非零元素个数TSMatrix;typedef struct/定义行逻辑链接的顺序表Triple dataMAXSIZE+2;非 0 元三元组表int rposMAXROW+1;各行第一个非零元素的位置表int rows, cols, nzeroNums;行数、列数、非零元素个数RLSMatrix;/输入三元组矩阵template <class T>bool InputTSMatrix(T &M, int y)cout << ”输入矩阵的行数、列数和非零元素个数："cin >> M.rows >> M.cols

3、>> M.nzeroNums;<< endl;cout << "请输入非零元素对应的行号、列号和相应的元素值for (int i = 1; i <= M.nzeroNums; i+)cin >> M.datai.r >> M.datai.c >> M.datai.v;return true;/输出矩阵，按标准格式输出template <class T>bool OutputSMatrix(T M)(int i, j, k = 1;for (i = 0; i < M.rows; i+)(fo

4、r (j = 0; j < M.cols; j+)(if (M.datak.r-1) = i && (M.datak.c-1) = j)(cout << setw(4) << M.datak.v;k+;elsecout << setw(4) << "0"/end_jcout << endl;/end_ireturn true;/求稀疏矩阵的转置int TranSMatrix()(TSMatrix M, T;InputTSMatrix(M, 0);int col, p, q = 1;T.rows

5、 = M.cols;T.cols = M.rows;T.nzeroNums = M.nzeroNums;if (T.nzeroNums)(for (col = 1; col <= M.cols; col+)(for (p = 1; p <= M.nzeroNums; p+)(if (M.datap.c = col)(T.dataq.r = M.datap.c;T.dataq.c = M.datap.r;T.dataq.v = M.datap.v;+q;/end_p/end_col/end_ifcout << "运用普通转置算法，输入矩阵的转置矩阵为：-<

6、< endl;OutputSMatrix(T);return 1;/稀疏矩阵的快速转置 int FastTranMat()表示矩阵M中第col列非零元素的个数表示矩阵M中第col列第一个非0元素在b.data中的位置输入稀疏矩阵TSMatrix M, T;int numMAXROW+1;int cpotMAXROW+1;int p, q, col, t;InputTSMatrix(M, 0);T.rows = M.cols;T.cols = M.rows;T.nzeroNums = M.nzeroNums;if (T.nzeroNums)for (col = 1; col <= M

7、.cols; col+)/M中各列元素初始化numcol = 0;for (t = 1; t <= M.nzeroNums; t+)+numM.datat.c;/求M中每一列非零元个数/求第col列第一个非零元在 b.data中的序号cpot1 = 1;for (col = 2; col <= M.cols; col+)cpotcol = cpotcol-1 + numcol-1;for (p = 1; p <= M.nzeroNums; p+)col = M.datap.c;/稀疏矩阵 M中每个元素对应的列号q = cpotcol;稀疏矩阵M中第一个非零元素位置T.data

8、q.r = M.datap.c;T.dataq.c = M.datap.r;T.dataq.v = M.datap.v;+cpotcol;/end_for/end_ifcout << "运用快速算法，输入矩阵的转置为："<< endl;OutputSMatrix(T);return 1;/求取稀疏矩阵每一行非零元个数bool Count(RLSMatrix &M)int row, p;int numMAXROW+1;for (row = 1; row <= M.rows; row+)numrow = 0;/清零for (p = 1; p

9、 <= M.nzeroNums; p+)+numM.datap.r;/统计M每一行非零元个数M.rpos1 = 1;/M中每一行非零元的起始位置for (row = 2; row <= M.rows; row+)M.rposrow = M.rposrow-1 + numrow-1;return true;/两个稀疏矩阵的乘法bool MultSMatrix()RLSMatrix M, N, Q;/构建三个带链接信息的三元组表示的数组InputTSMatrix(M, 1);用普通三元组形式输入数组InputTSMatrix(N, 1);Count(M);Count(N);if (M.

10、cols != N.rows)cout << "Error!"return false;/Q的初始化Q.rows = M.rows;Q.cols = N.cols;Q.nzeroNums = 0;int mrow, nrow, p, q, t, tp, qcol;int ctempMAXROW+1;辅助数组/如果Q是非零矩阵if (M.nzeroNums * N.nzeroNums)for (mrow = 1; mrow <= M.rows; mrow+)当前行各元素累加器清零for (int x = 1; x <= N.cols; x+)ctemp

11、x = 0;/end_x当前行的首个非零元素在三元组中的位置为此行前所有非0元素加1Q.rposmrow = Q.nzeroNums + 1;if (mrow < M.rows)tp = M.rposmrow+1;elsetp = M.nzeroNums + 1;for (p = M.rposmrow; p < tp; p+)对当前行的每个非零元素操作nrow = M.datap.c;/在N中找到与 M操作元素的c值相等的行值 rif (nrow < N.rows) t = N.rposnrow+1; elset = N.nzeroNums + 1;/对找出的行的每个非零元素

12、进行操作for (q = N.rposnrow; q < t; q+)qcol = N.dataq.c;/将乘得到的对应值放在相应元素的累加器里面ctempqcol += M.datap.v * N.dataq.v;/p_end_for/对已经求出的累加器中的值压缩到Q中for (qcol = 1; qcol <= Q.cols; qcol+) if (ctempqcol) if (+Q.nzeroNums > MAXSIZE)(cout << "Error!" << endl;return 0;Q.dataQ.nzeroNum s

13、.r = mrow;Q.dataQ.nzeroNums.c = qcol;Q.dataQ.nzeroNums.v = ctempqcol;/qcol_end_for/arow_end_for/end_ifcout << "两个稀疏矩阵相乘的结果为：n”;OutputSMatrix(Q);return 1;两个稀疏矩阵的加法int AddMatrix()(TSMatrix A, B, C;int i = 1, j = 1, k = 1;/i, j, k分别用以保存 A、B、C非零元素个数int value = 0;InputTSMatrix(A, 0);InputTSMat

14、rix(B, 0);if (A.rows != B.rows | A.cols != B.cols)(cout << "两个稀疏矩阵的大小不等，不能相加！" << endl;return 0;if (A.rows = B.rows && A.cols = B.cols)(while (i <= A.nzeroNums && j <= B.nzeroNums)(if (A.datai.r = B.dataj.r)(if (A.datai.c < B.data田.c)(C.datak.r = A.data

15、i.r;C.datak.c = A.datai.c;C.datak.v = A.datai.v;k+;i+;else if (A.datai.c > B.dataj.c)(C.datak.r = B.dataj.r;C.datak.c = B.dataj.c;C.datak.v = B.dataj.v;k+;j+；else(value = A.datai.v + B.dataj.v;if (value != 0)(C.datak.r = A.datai.r;C.datak.c = A.datai.c;C.datak.v = value;k+;i+;j+;/end_ifelse if (A

16、.datai.r < B.dataj.r)(C.datak.r = A.datai.r;C.datak.c = A.datai.c;C.datak.v = A.datai.v;k+;i+;else(C.datak.r = B.dataj.r;C.datak.c = B.dataj.c;C.datak.v = B.dataj.v;k+;j+;把剩余部分元素存入C中if (i > A.nzeroNums && j <= B.nzeroNums) (for (; j <= B.nzeroNums; j+)(C.datak.r = B.dataj.r;C.dat

17、ak.c = B.dataj.c;C.datak.v = B.dataj.v; k+;if (i <= A.nzeroNums && j > B.nzeroNums)(for (; i <= A.nzeroNums; i+)(C.datak.r = A.datai.r;C.datak.c = A.datai.c;C.datak.v = A.datai.v;k+;/end_whileC.rows = A.rows;C.cols = A.cols;C.nzeroNums = k-1;cout << "输出两个稀疏矩阵的和："<

18、< endl;OutputSMatrix(C);return 1;/end_ifelsereturn 0;两个稀疏矩阵的减法int SubMatrix()(TSMatrix A, B, C;int m = 1, n = 1, k = 1, temp;InputTSMatrix(A, 0);InputTSMatrix(B, 0);C.rows = A.rows;C.cols = A.cols;C.nzeroNums = 0;if (A.rows = B.rows && A.cols = B.cols)(while (m <= A.nzeroNums &&

19、; n <= B.nzeroNums)(if (A.datam.r = B.datan.r)(if (A.datam.c = B.datan.c) temp = A.datam.v - B.datan.v; if (temp != 0)(C.datak.r = A.datam.r;C.datak.c = A.datam.c;C.datak.v = temp;k+;m+;n+;else if (A.datam.c < B.datan.c)(C.datak.r = A.datam.r;C.datak.c = A.datam.c;C.datak.v = A.datam.v;k+;m+;e

20、lse(C.datak.r = B.datan.r;C.datak.c = B.datan.c;C.datak.v = -B.datan.v;k+;n+;else if (A.datam.r < B.datan.r)(C.datak.r = A.datam.r;C.datak.c = A.datam.c;C.datak.v = A.datam.v;k+;m+;else(C.datak.r = B.datan.r;C.datak.c = B.datan.c;C.datak.v = -B.datan.v;k+;n+;/end_whileif (m <= A.nzeroNums)(for

21、 (; m <= A.nzeroNums; m+)(C.datak.r = A.datam.r;C.datak.c = A.datam.c;C.datak.v = A.datam.v;k+;if (n <= B.nzeroNums)(for (; n <= B.nzeroNums; n+)(C.datak.r = B.datan.r;C.datak.c = B.datan.c;C.datak.v = -B.datan.v;k+;C.nzeroNums = k-1;cout << "两个稀疏矩阵的差为：n”;OutputSMatrix(C);return

22、1; /end_ifelse(cout << "两个稀疏矩阵的大小不同，不能相减 ！n”;return 0;/得到矩阵元素Mi田的值int value(TSMatrix M, int i, int j)(int k;for (k = 1; k <= M.nzeroNums; k+)(if (M.datak.r = i && M.datak.c = j)(return M.datak.v;return 0;矩阵乘法的算法2int MultMat()(TSMatrix A, B, C;InputTSMatrix(A, 0);InputTSMatrix(B

23、, 0);int i, j, k, temp = 0, p = 1;if (A.cols != B.rows)(cout << "矩阵A的列数不等于矩阵B的行数不能相乘！n”;return 0;else(for (i = 1; i <= A.rows; i+)(for (j = 1; j <= B.cols; j+)(temp = 0;for (k = 1; k <= A.cols; k+)(temp += value(A, i, k) * value(B, k, j);if (temp != 0)(C.datap.r = i;C.datap.c = j

24、;C.datap.v = temp;p+;C.rows = A.rows;C.cols = B.cols;C.nzeroNums = p-1;OutputSMatrix(C);return 1;/计算矩阵的行列式，通过递归算法来实现int JsMatrix(int sMAXROW, int n)(int i, j, k, r, total = 0;int bSIZENUMSIZENUM; /bNN用于存放在矩阵sNN中元素 s0的余之式if (n = 1)(total = s00;else if (n = 2)(total = s00 * s11 - s01 * s10;else(for (i

25、 = 0; i < n; i+)(for (j = 0; j < n-1; j+)(for (k = 0; k < n-1; k+)(if (k >= i)(bjk = sj+1k+1;else(bjk = sj+1k;/end_for_k/end_for_jif (i % 2 = 0)(r = s0i * JsMatrix(b, n-1);递归调用else(r = (-1) * s0i * JsMatrix(b, n-1);total += r;/end_for_i/end_elsereturn total;求原矩阵个元素对应的余之式，存放在bnn中,定义为float

26、型void N1Matrix(int sSIZENUM, float bSIZENUM, int n)(int i, j, k, l, m, g, aSIZENUMSIZENUM;for (i = 0; i < n; i+)(m = i;for (j = 0; j < n; j+)(g = j;for (k = 0; k < n-1; k+)(for (l = 0; l < n-1; l+)(if (k >= m && l >= g)(akl = sk+1l+1;else if (k < m && l >= g)(

27、akl = skl+1;else if (k >= m && l < g)(akl = sk+1l;else(akl = skl;/end_for_l/end_for_kbij = JsMatrix(a, n-1);/end_for_j/end_for_i/稀疏矩阵求逆void InverseMat()(TSMatrix M;InputTSMatrix(M, 0);int i, j, k, n = M.rows;float temp;int aSIZENUMSIZENUM;float bSIZENUMSIZENUM, cSIZENUMSIZENUM;for (i =

28、 0; i < n; i+)初始化矩阵 afor (j = 0; j < n; j+)aij = 0;for (i = 1; i <= M.nzeroNums; i+)给矩阵 a 赋值aM.datai.r-1M.datai.c-1 = M.datai.v;cout << "稀疏矩阵对应的普通矩阵为：n"for (i = 0; i < n; i+)打印原矩阵for (j = 0; j < n; j+)cout << setw(4) << aij << setw(4);cout << en

29、dl;k = JsMatrix(a, n);cout << "矩阵的行列式值：|A| = " << k << endl;if (k = 0)cout << "行列式的值为0,原矩阵无逆矩阵！" << endl;elseN1Matrix(a, b, n);调用函数，得到原矩阵各元素对应的余之式存放在数组bnn求代数余之式cout << "普通矩阵各元素对应的代数余之式矩阵为：n”;for (i = 0; i < n; i+)for (j = 0; j < n; j

30、+)if (i+j)%2 != 0 && bij != 0)bij = -bij;cout << setw(4) << bij << setw(4);cout << endl;/end_for_i/对bNN转置，此时bnn存放的为原矩阵的伴随矩阵for (i = 0; i < n; i+)for (j = i+1; j < n; j+)temp = bij;bij = bji;bji = temp;cout << "伴随矩阵 A*: " << endl;for (i = 0;

31、 i < n; i+)/打印伴随矩阵 A*for (j = 0; j < n; j+)cout << setw(4) << bij << setw(4);cout << endl;for (i = 0; i < n; i+)/求逆矩阵，此时 cnn中存放的是原矩阵的逆矩阵for (j = 0; j < n; j+)cij = bij/k;cout << "逆矩阵(A*)/|A|: " << endl;for (i = 0; i < n; i+)/打印逆矩阵for (j =

32、0; j < n; j+)cout << setw(6) << cij << setw(6);cout << endl;/end_else int main()char c;cout << setw(50) << "*欢迎使用稀疏矩阵的相关操作！*"<< endl << endl;cout.fill('*');cout << setw(20) << '*'cout << "请选择要进行的操作"cout << setw(20) << '*' << endl;稀疏矩阵的普通转置算法"<< endl;稀疏矩阵的快速转置算法"<< endl;稀疏矩阵的乘法的快速算法"<< endl