#include <iostream>using namespace std;
template<class T>class LinkedList{ public: LinkedList(); ~LinkedList(); void Insert(const T & value); T * Get(int index); int GetLength() const{return length; } T * Find(const T & value); void display() const; public: T * head; int length;};
template<class T>T * LinkedList<T>::Get(int index){ if(index<0 || index>length) return NULL; T * temp=head; while(--index) temp=temp->next; return temp;}
template<class T>void LinkedList<T>::display() const{ T * temp=head; while(temp) { temp->display(); temp=temp->next; }}
class SparseNode{public: SparseNode(int col,int value):_col(col),_value(value){ } SparseNode(const SparseNode & element); ~SparseNode(){ } void display() const{ cout<<"col: "<<_col<<" value: "<<_value<<" "; }public: int _col; int _value;public: SparseNode * next;};
class HeadNode{public: HeadNode(int row):_row(row){ } HeadNode(const HeadNode & other){ _row=other._row; } ~HeadNode(){} void display() const; void Insert(const SparseNode & value); bool operator==(const HeadNode & other);public: HeadNode * next;public: int _row; //行 LinkedList<SparseNode> elements; //行列表};void HeadNode::display() const{ cout<<"row: "<<_row<<endl; elements.display(); cout<<endl;}bool HeadNode::operator==(const HeadNode & other){ if(_row==other._row) return false; else return true;}
class SparseMatrix{public: SparseMatrix(); ~SparseMatrix(); void Set(int row,int col,int value); void display() const; void Add(const SparseMatrix & other);private: LinkedList<HeadNode> head;};
void SparseMatrix::Add(const SparseMatrix & other){ HeadNode * first=head.head; //源矩阵的第一行 HeadNode * second=other.head.head; //目的矩阵的第一行
while(first && second) { int distance=first->_row-second->_row; //判断行数是否相等 if(distance<0) //源行小于目的行 first=first->next; else if(distance==0)//两行相等 { SparseNode * sp1=first->elements.head;//源行的第一列 SparseNode * sp2=second->elements.head;//目的行的第一列 while(sp1 && sp2) { int dis=sp1->_col-sp2->_col;//判断列数是否相等 if(dis<0) //源列小 sp1=sp1->next; else if(dis==0) //两列相等 { sp1->_value+=sp2->_value; sp1=sp1->next; sp2=sp2->next; } else //目的列小 { Set(first->_row,sp2->_col,sp2->_value); //插入这一列 sp2=sp2->next; } } while(sp2) //如果目的列还有剩余，则全部插入 { Set(first->_row,sp2->_col,sp2->_value); sp2=sp2->next; }
first=first->next; second=second->next; } else //目的列小,则全部插入 { SparseNode * temp=second->elements.head; while(temp) { Set(second->_row,temp->_col,temp->_value); temp=temp->next; } second=second->next; } } //如果目的矩阵还有行数，则全部插入 if(second) { HeadNode * temp=second; while(temp) { SparseNode * node=temp->elements.Get(1); while(node) { Set(temp->_row,node->_col,node->_value); node=node->next; } temp=temp->next; } }
}
void SparseMatrix::display() const{ head.display();}
template<class T>LinkedList<T>::LinkedList(){ head=NULL; length=0;
}
template<class T>LinkedList<T>::~LinkedList(){ T * temp=head; T * next; while(temp) { next=temp->next; delete temp; temp=next; }}
template<class T>void LinkedList<T>::Insert(const T & value){ T * temp=new T(value); length++; if(!head) { head=temp; head->next=NULL;
return; } T * tail=head; while(tail->next) tail=tail->next; tail->next=temp; temp->next=NULL;}
template<class T>T * LinkedList<T>::Find(const T & value){ T * temp=head; while(temp && *temp==value) temp=temp->next; if(temp) return temp; else return NULL;}
SparseNode::SparseNode(const SparseNode & element){ _col=element._col; _value=element._value;}
void HeadNode::Insert(const SparseNode & value){ elements.Insert(value);}
SparseMatrix::SparseMatrix(){ //do nothing}
SparseMatrix::~SparseMatrix(){ //do nothing}
void SparseMatrix::Set(int row,int col,int value){ HeadNode * location=head.Find(HeadNode(row)); if(!location) { head.Insert(HeadNode(row)); location=head.Find(HeadNode(row)); } location->Insert(SparseNode(col,value));}
int main(){ SparseMatrix matrix; matrix.Set(1,3,10);
matrix.Set(1,5,20); matrix.Set(2,4,8); matrix.Set(4,3,20); matrix.display();
SparseMatrix matrix2; matrix2.Set(4,3,3); matrix2.Set(5,1,20); matrix2.Set(5,3,3); matrix2.Set(6,2,4);
matrix.Add(matrix2); cout<<"**********************/n"; matrix.display();
return 0;}
