稀疏矩阵类

0
13

稀疏矩阵类

Design a class Sparse that implements interface Matrix: Sparse should has the following public object functions in addition:

1. A constructor Sparse(int rows, int column), which initializes all elements in the matrix to 0’s.
2. A function Sparse Sparse::operator + (Sparse & sparse2), which returns the pair-wise sum of two sparse matrixes.
3. A function Sparse Sparse::operator * (Sparse & sparse2), which returns the product of two sparse matrixes.

HINT

``````A、B都是1000000*1000000的矩阵

(1,1,10)
(1,2000000,50)
(1000000,2000000,20)

(1,3000000,30)
(2000000,1,40)
(1,1,-10)
``````
``````C是1000000*2000000的矩阵
D是2000000*3000000的矩阵

(1,1,10)
(1,2000000,50)
(1000000,2000000,20)

(1,3000000,30)
(2000000,1,40)
(1,1,-10)
``````
``````A+B得:
(1,1000000,80)
(1000000,1,40)
(1000000,1000000,20)
C*D得:
(1,1,1900)
(1,3000000,300)
(1000000,1,800)
``````
``````#include<vector>
#include<algorithm>
#include <iostream>
using namespace std;

class Entry
{
public:
int row;
int column;
double value;
};

class Matrix
{
public:
virtual int size(int dimension) const = 0;

virtual void set(int row, int column,
double value) = 0;

virtual double get(int row, int column)
const = 0;

virtual void print() = 0;

};

bool Comp1(const Entry &a,const Entry &b)
{
return a.row<b.row;
}
bool Comp2(const Entry &a,const Entry &b)
{
return (a.row==b.row&&a.column<b.column);
}
class Sparse : public Matrix
{
private:
int _rows, _columns;
vector<Entry> entry;
public:
Sparse(int rows, int column)
{
_rows = rows;
_columns = column;
entry = vector<Entry>();
}
int size(int dimension) const
{
if(dimension == 1) return _rows;
if(dimension == 2) return _columns;
}
void set(int row, int column, double value)
{
Entry e;
e.row = row;
e.column = column;
e.value = value;
entry.push_back(e);
}
double get(int row, int column) const
{
for(int i=0; i < entry.size();i++)
{
if(entry[i].row == row
&& entry[i].column == column ){
return entry[i].value;
}
}
}
void print()
{
for(int i=0; i < entry.size();i++)
{
cout<<"("<<entry[i].row<<","<<entry[i].column<<","
<<entry[i].value<<")\n";
}
}
//稀疏矩阵的 加法运算
Sparse operator + (Sparse & sparse2)
{
Sparse s(_rows, _columns);

for(int i=0; i < this->entry.size(); i++)
{
for(int j = 0 ;j< sparse2.entry.size(); j++)
{
if(this->entry[i].row == sparse2.entry[j].row
&& this->entry[i].column == sparse2.entry[j].column){
Entry e;
e.row = sparse2.entry[j].row;
e.column =  sparse2.entry[j].column;
e.value = this->entry[i].value + sparse2.entry[j].value;

if(e.value)
s.entry.push_back(e);

this->entry[i].value = 0;
sparse2.entry[j].value = 0;
}

}
}
for(int i=0; i < this->entry.size(); i++)
{
Entry e;
e.row = this->entry[i].row;
e.column = this->entry[i].column;
e.value = this->entry[i].value;
if(e.value)
s.entry.push_back(e);
}
for(int i=0; i < sparse2.entry.size(); i++)
{
Entry e;
e.row = sparse2.entry[i].row;
e.column = sparse2.entry[i].column;
e.value = sparse2.entry[i].value;
if(e.value)
s.entry.push_back(e);
}
sort(s.entry.begin(),s.entry.end(),Comp1);
sort(s.entry.begin(),s.entry.end(),Comp2);

return s;
}
};
//稀疏矩阵的 乘法运算
Sparse operator * (Sparse & sparse2)
{
Sparse s(_rows, sparse2._columns);

for(int i=0; i < this->entry.size(); i++)
{
for(int j = 0 ;j< sparse2.entry.size(); j++)
{
if(this->entry[i].column == sparse2.entry[j].row ){

Entry e;
e.row =this->entry[i].row;
e.column =  sparse2.entry[j].column;
e.value = this->entry[i].value * sparse2.entry[j].value;
int isIns = 0;
int index = -1;
for(int k = 0 ; k < s.entry.size();k++){
if(s.entry[k].row == e.row && s.entry[k].column == e.column){
isIns = 1;
index = k;
}
}
if(e.value && isIns == 0)
s.entry.push_back(e);
if(e.value && isIns == 1){
s.entry[index].value += e.value;
}
}

}
}

sort(s.entry.begin(),s.entry.end(),Comp1);
sort(s.entry.begin(),s.entry.end(),Comp2);

return s;
}
void print(Matrix & matrix) {
matrix.print();
}

void readAndSetElement(Matrix & matrix) {
int row;
int column;
double value;
cin >> row >> column >> value;
matrix.set(row, column, value);
}

void readAndSetMultipleElements(Matrix & matrix, int count) {
for (int i = 0; i < count; ++ i) {
readAndSetElement(matrix);
}
}

int main() {
int rows;
int columns;
cin >> rows >> columns;

Sparse sparse1(rows, columns);
readAndSetMultipleElements(sparse1, 3);

Sparse sparse2(rows, columns);
readAndSetMultipleElements(sparse2, 3);

Sparse sparse3 = sparse1 + sparse2;
print(sparse3);
}
``````

<