Design a class Sparse that implements interface Matrix: Sparse should has the following public object functions in addition:
A constructor Sparse(int rows, int column), which initializes all elements in the matrix to 0's.
A function Sparse Sparse::operator * (Sparse & sparse2), which returns the matrix-matrix multiplication of the two sparse matrixes.
EXAMPLE INPUT
1000000 2000000 3000000
1 1 10
1 2000000 50
1000000 2000000 20
1 3000000 30
2000000 1 40
1 1 -10
EXAMPLE OUTPUT
(1,1,1900)
(1,3000000,300)
(1000000,1,800)
主程序 (不能修改)
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;
};
#include "source.cpp"
#include <iostream>
using namespace std;
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;
int & rows2 = columns;
int columns2;
cin >> rows >> columns >> columns2;
Sparse sparse1(rows, columns);
readAndSetMultipleElements(sparse1, 3);
Sparse sparse2(rows2, columns2);
readAndSetMultipleElements(sparse2, 3);
Sparse sparse3 = sparse1 * sparse2;
print(sparse3);
}参考答案
#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);
}