压缩矩阵

来源:转载

根据数据结构书本上敲打的,讲述内容较少,但是添加了一些注释。

//稀疏矩阵的压缩存储,最多存储10*10的矩阵#include<iostream>#include<iomanip>//use setwusing namespace std;typedef struct{ int row;//非零元的行下标 int column;//非零元的列下标 int e;//非零元}Triple;typedef struct{ Triple data[100]; int mu;//矩阵的行数 int nu;//矩阵的列数 int tu;//非零元的个数}TSMatrix;/*1.输入矩阵,进行压缩*/void InitMatrix(TSMatrix &matrix){ matrix.tu = 0; int a[100][100] = { 0 }; cout << "请输入矩阵的行数和列数:/n"; int rowNum, columnNum;//行数和列数 cin >> rowNum >> columnNum; matrix.mu = rowNum; matrix.nu = columnNum; cout << "请输入矩阵/n";//矩阵的输入 for (int i = 0; i < rowNum; i++) for (int j = 0; j < columnNum; j++) cin >> a[i][j]; //进行压缩矩阵 for (int i = 0; i < rowNum; i++) { for (int j = 0; j < columnNum; j++) { if (a[i][j] != 0) { matrix.data[matrix.tu].e = a[i][j];//好好理解这个句子 matrix.data[matrix.tu].row = i; matrix.data[matrix.tu++].column = j; } } } cout << "矩阵压缩成功/n";}/*2.矩阵转置*/void MatrixTransposition(const TSMatrix & tsmatrix, TSMatrix & tsmatrix1)//tsmatrix1是转置后的三元组表{ /* 在此预设num和cpot两个向量。num[col]表示矩阵tsmatrix中第col列中非零元的个数, cpot[col]指示tsmatrix中第col列的第一个非零元在tsmatrix1.data中的恰当位置 */ tsmatrix1.mu = tsmatrix.nu;//转置后行列数要交换 tsmatrix1.nu = tsmatrix.mu; tsmatrix1.tu = tsmatrix.tu; int num[100] = { 0 }; int cpot[100] = { 0 }; if (tsmatrix1.tu) { for (int i = 0; i < tsmatrix.tu; i++) num[tsmatrix.data[i].column]++;//num[col]代表第col列中非零元的个数 } for (int i = 1; i < tsmatrix.tu; i++) cpot[i] = cpot[i - 1] + num[i - 1];//cpot[col]代表第col列的第一个非零元在data数组中的位置 for (int i = 0; i < tsmatrix.tu; i++) { int col = tsmatrix.data[i].column; int p = cpot[col]; tsmatrix1.data[p].row = tsmatrix.data[i].column; tsmatrix1.data[p].column = tsmatrix.data[i].row; tsmatrix1.data[p].e = tsmatrix.data[i].e; cpot[col]++; }}/*3.乘积矩阵*/void MatrixMult(const TSMatrix & M, const TSMatrix & N, TSMatrix & Q)//_____M*N=Q{ int numM[100] = { 0 };//num[row]_____第row行的非零元个数 int rposM[100] = { 0 };//rpos[row]____第row行中第一个非零元在data数组的位置 int numN[100] = { 0 }; int rposN[100] = { 0 }; //preparation //for M for (int i = 0; i < M.tu; i++) numM[M.data[i].row]++; rposM[0] = 0; for (int i = 1; i < M.mu; i++) rposM[i] = rposM[i - 1] + numM[i - 1]; //for N for (int i = 0; i < N.tu; i++) numN[N.data[i].row]++; rposN[0] = 0; for (int i = 1; i < N.mu; i++) rposN[i] = rposN[i - 1] + numN[i - 1]; //matrix mult if (M.nu != N.mu) { cout << "矩阵无法运算/n"; return; } //Q的初始化 Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; // if (M.tu*N.tu != 0)//Q是非零矩阵 { for (int i = 0; i < M.mu; i++)//对于M的每一行 { int tp; int ctemp[10] = { 0 };//当前行各元素累加器清零 // if (i < M.mu - 1) tp = rposM[i + 1]; else tp = M.tu; // for (int j = rposM[i]; j < tp; j++)//对于当前行的每一个非零元 { int t; int brow = M.data[j].column;//由M中的列坐标找到对应的行坐标 // if (brow < N.mu - 1) t = rposN[brow + 1]; else t = N.tu; // for (int k = rposN[brow]; k < t; k++) { ctemp[N.data[k].column] += M.data[j].e *N.data[k].e; } } // for (int p = 0; p < Q.nu; p++) { if (ctemp[p])//如果不是非零元,则放入Q的data数组中 { Q.data[Q.tu].e = ctemp[p]; Q.data[Q.tu].column = p; Q.data[Q.tu++].row = i; } } }//for (int i = 0; i < M.mu; i++)______对于M的每一行 }//if (M.tu*N.tu != 0)______Q是非零矩阵}/*4.打印矩阵*/void MatrixPrint(const TSMatrix & matrix){ cout << "------------------------------------------" << endl; cout << "矩阵打印是:/n"; int num = 0; for (int i = 0; i < matrix.mu; i++)//每一行 { for (int j = 0; j < matrix.nu; j++)//当前行的每一列 { if (num != matrix.tu) { if (matrix.data[num].column == j&&matrix.data[num].row == i) cout << setw(3)<<matrix.data[num++].e << " "; else cout << setw(3)<<0 << " "; } else cout <<setw(3)<< 0 << " "; } cout << endl; } cout << "------------------------------------------" << endl;}int main(){ TSMatrix matrixM,matrixN; TSMatrix temp; //矩阵初始化 InitMatrix(matrixM); InitMatrix(matrixN); //矩阵转置,输出 MatrixTransposition(matrixM, temp); cout << "/n/n转置后输出/n"; MatrixPrint(temp); MatrixTransposition(matrixN, temp); cout << "/n/n转置后输出/n"; MatrixPrint(temp); ////矩阵乘积 cout << "/n/n矩阵乘积输出/n"; TSMatrix matrixQ; MatrixMult(matrixM, matrixN, matrixQ); MatrixPrint(matrixQ); return 0;}




分享给朋友:
您可能感兴趣的文章:
随机阅读: