疎行列-三元グループ
アルゴリズム思想は厳書から来ています.厳書に基づく三元組のデータ構造を実現します.勉強したいのは参考にしてください.
/* Author : Moyiii
* Mail: [email protected]
* -
* ， ， 。
* BUG， ，
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_MATRIX_NUM = 100;
const int MAX_MATRIX_SIZE = 20;
//
class Triple
{
public:
int row;
int col;
int data;
};
//
class SMatrix
{
public:
void input();
void copyMat(SMatrix &dest);
//
static void addMat(SMatrix &a,SMatrix &b, SMatrix &dest);
static void mulMat(SMatrix &a,SMatrix &b, SMatrix &dest);
static void subMat(SMatrix &a,SMatrix &b, SMatrix &dest);
static void countf(SMatrix &dest);
//
void tran(SMatrix &dest);
void print();
private:
int nrow,ncol,nelems;
// ，
Triple datas[MAX_MATRIX_NUM];
// datas
int fpos[MAX_MATRIX_SIZE];
};
void SMatrix :: input()
{
//
cout << "Please enter the num of row and colums:" ;
cin >> nrow>> ncol;
while(nrow < 0 || ncol < 0)
{
cout << "rows or colums must be positive integers" << endl;
cout << "Please enter the num of row and colums:";
cin >> nrow >> ncol;
}
cout << "Please input the num of non-zero elems:";
cin >> nelems;
while(nelems < 0 || nelems > MAX_MATRIX_NUM)
{
cout << "Num of nelems is invalid" << endl;
cout << "Please input the num of non-zero elems:";
cin >> nelems;
}
cout << "Please input n lines datas like: row col data:" << endl;
for(int i = 0; i < nelems; ++i)
{
cin >> datas[i].row >>datas[i].col >> datas[i].data;
}
SMatrix :: countf(*this);
}
// fpos ， 。
// +
void SMatrix :: countf(SMatrix &dest)
{
int nums[dest.ncol];
for(int i = 0; i < dest.ncol; ++i)
{
nums[i] = 0;
}
for(int i = 0; i < dest.nelems; ++i)
{
++nums[dest.datas[i].row - 1];
}
dest.fpos[0] = 0;
for(int i = 1; i <= dest.ncol; ++i)
{
dest.fpos[i] = dest.fpos[i-1] + nums[i-1];
}
dest.fpos[dest.nrow] = dest.nelems;
return;
}
// ，
void SMatrix :: print()
{
int index = 0;
printf(" ");
//
for(int i = 1; i <= ncol; ++i)
{
printf("%2d ",i);
}
printf("
");
printf(" ");
for(int i = 1; i <= ncol; ++i)
{
printf("%2c ",'-');
}
printf("
");
for(int i = 1; i <= nrow; ++i)
{
//
printf("%d|",i);
for(int j = 1; j <= ncol; ++j)
{
//
if(index > nelems)
{
printf("%2d ",0);
}
else
{
//
if(i == datas[index].row && j == datas[index].col)
{
printf("%2d ",datas[index].data);
index++;
}
else
{
printf("%2d ",0);
}
}
}
cout << endl;
}
cout << endl;
}
// dest
void SMatrix :: copyMat(SMatrix &dest)
{
if(&dest == this)
{
return;
}
for(int i = 0; i < this->nelems; ++i)
{
dest.datas[i] = this->datas[i];
}
dest.nelems = this->nelems;
dest.ncol = this->ncol ;
dest.nrow = this->nrow ;
for(int i = 0; i < nrow; ++i)
{
dest.fpos[i] = this->fpos[i];
}
return;
}
// 。 。。
void SMatrix :: tran(SMatrix &dest)
{
Triple temp[MAX_MATRIX_NUM];
//
int nums[ncol];
int tfpos[ncol];
for(int i = 0; i < ncol; ++i)
{
nums[i] = 0;
}
for(int i = 0; i <nelems; ++i)
{
++nums[datas[i].col - 1];
}
dest.fpos[0] = 0;
tfpos[0] = 0;
for(int i = 1; i <= ncol; ++i)
{
dest.fpos[i] = dest.fpos[i-1] + nums[i-1];
tfpos[i] = dest.fpos[i];
}
int trows = this->ncol;
int tcols = this->nrow;
int telems = this->nelems;
// ，
for(int i = 0; i < telems; ++i)
{
int &t = tfpos[this->datas[i].col - 1];
temp[t].col = this->datas[i].row;
temp[t].row = this->datas[i].col;
temp[t].data = this->datas[i].data;
t++;
}
// ， 。
for(int i = 0; i < telems; ++i)
{
dest.datas[i] = temp[i];
}
dest.ncol = tcols;
dest.nrow = trows;
dest.nelems = telems;
return;
}
// ， 。
void SMatrix :: addMat(SMatrix &a,SMatrix &b, SMatrix &dest)
{
if(a.nrow != b.nrow || a.ncol != b.ncol)
{
cout << "Error, the two matrix are not the same size!" << endl;
return;
}
int index = 0;
int cura = 0,curb = 0;
while(cura < a.nelems && curb < b.nelems)
{
int ra = a.datas[cura].row,rb = b.datas[curb].row;
int ca = a.datas[cura].col,cb = b.datas[curb].col;
// ，
if((ra-1)*a.nrow + ca < (rb-1)*b.nrow + cb)
{
dest.datas[index++] = a.datas[cura++];
}
else if((rb-1)*b.nrow + cb <(ra-1)*a.nrow + ca)
{
dest.datas[index++] = b.datas[curb++];
}
else
{
dest.datas[index] = a.datas[cura++];
dest.datas[index++].data += b.datas[curb++].data;
if(dest.datas[index].data == 0)
{
index--;
}
}
}
while(cura < a.nelems)
{
dest.datas[index++] = a.datas[cura++];
}
while(curb <b.nelems)
{
dest.datas[index++] = a.datas[curb++];
}
dest.ncol = a.ncol;
dest.nrow = a.nrow;
dest.nelems = index;
SMatrix :: countf(dest);
return ;
}
// b -1，
void SMatrix :: subMat(SMatrix &a,SMatrix &b, SMatrix &dest)
{
SMatrix temp;
b.copyMat(temp);
for(int i = 0; i < temp.nelems; ++i)
{
temp.datas[i].data *= -1;
}
SMatrix :: addMat(a,temp,dest);
return;
}
void SMatrix :: mulMat(SMatrix &a,SMatrix &b, SMatrix &dest)
{
// a b ， b ， a b 。
// ，
SMatrix temp;
b.tran(temp);
int trow = a.nrow;
int tcol = b.ncol;
int index = 0;
// ，
int res[tcol];
for(int i = 0; i < a.nrow; ++i)
{
//res i ， 0
for(int k = 0; k < tcol; ++k)
{
res[k] = 0;
}
for(int j = 0; j < temp.nrow; ++j)
{
// M[i][j]
int cura = a.fpos[i];
int curb = temp.fpos[j];
// ，
while(cura < a.fpos[i+1] && curb < temp.fpos[j+1])
{
if(a.datas[cura].col < temp.datas[curb].col)
{
++cura;
}
else if(temp.datas[curb].col < a.datas[cura].col)
{
++curb;
}
else
{
res[j] += temp.datas[curb].data * a.datas[cura].data;
curb++;
cura++;
}
}
}
for(int k = 0; k < tcol ; ++k)
{
//
if(res[k] != 0)
{
dest.datas[index].row = i + 1;
dest.datas[index].col = k + 1;
dest.datas[index].data = res[k];
index++;
}
}
}
dest.nelems = index;
dest.nrow = trow;
dest.ncol = tcol;
SMatrix :: countf(dest);
return ;
}
/* ,
6 6
8
1 2 12
1 3 9
3 1 -3
3 6 14
4 3 24
5 2 18
6 1 15
6 4 -7
*/
int main()
{
SMatrix a;
a.input();
a.print();
SMatrix b;
b.input();
b.print();
SMatrix c;
SMatrix :: mulMat(a,b,c);
c.print();
return 0;
}