数据结构课程设计 报告（十字链表实现稀疏矩阵的加法）(3)

friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b); };

template istream&operator>>(istream&in,LinkMatrix&a) { int m,n,terms,s; MatrixNode**cp,*p,*q; cout<<\输入矩阵的行数、列数、和非零元素个数\ in>>m>>n>>terms; if(n>m)s=n;else s=m; a.head=new MatrixNode; a.head->row=m; a.head->col=n; a.head->right=a.head->down=NULL; cp=new MatrixNode*[s+1]; cp[0]=a.head; int i; for(i=1;i<=s;i++) { p=new MatrixNode; p->row=p->col=0; p->right=p->down=p; cp[i]=p;cp[i-1]->next=p; } cp[s]->next=a.head; for(i=1;i<=terms;i++) { cout<<\输入一个非零元三元组(row,col,value)\ p=new MatrixNode; in>>p->row>>p->col>>p->data; q=cp[p->row]; while((q->right!=cp[p->row]&&(q->right->colcol)))q=q->right; p->right=q->right; q->right=p; q=cp[p->col]; while((q->down!=cp[p->row]&&(q->down->colcol)))q=q->down; p->down=q->down; q->down=p; } delete[]cp; return in;

}

template MatrixNode* LinkMatrix::Head(int i) {

MatrixNode*a; a=head->next; for(int j=1;jnext; } return a; }

templatevoid LinkMatrix::InsertInCol(MatrixNode*p) { MatrixNode*pre,*ch=Head(p->col); pre=ch; while(pre->down!=ch&&pre->down->rowrow)pre=pre->down; p->down=pre->down; pre->down=p; }

templatevoid LinkMatrix::DeleteInCol(MatrixNode*p) { MatrixNode*pre,*ch=Head(p->col); pre=ch; while(pre->down!=ch&&pre->down!=p)pre=pre->down; if(pre->down==p) { pre->down=p->down; delete p; } //else throw invalid_arguement(\}

template //重载符合赋值运算符+=

LinkMatrix&LinkMatrix::operator +=(const LinkMatrix &a) { MatrixNode *pre,*pa,*h,*ah,*p,*tmp; if(head->col !=a.head->col||head->row !=a.head->row)//非同型矩阵不可相加 cout<<\ //throw domain_error(\

h=head->next;ah=a.head->next; //h、ah指向当前处理行的头结点 while(h !=head){ //逐一处理各行 pre=h; p=h->right; //p指向被加矩阵的当前结点，pre指向其前驱 pa=ah->right; //pa分别指向加矩阵的当前结点 while(pa !=ah) { //处理当前行 if(p !=h&&(p->colcol)){ //若被加矩阵的列标更小，则比较下一个 pre=p; p=p->right; } else if(p==h||p->col>pa->col){ //若加矩阵的列标更小，则插入 tmp=new MatrixNode(*pa) ; pre->right=tmp; //在行链表中插入pa复制结点tmp tmp->right=p; InsertInCol(tmp); //在列表中插入tmp pre=tmp; //当前指针p的前驱变为tmp pa=pa->right; } else { //列标相同，则做加法 p->data +=pa->data; if(!p->data) { //和为0，则删除之 （行、列都要删除） tmp=p;p=p->right;pre->right=p;//在行链表中将tmp摘下 DeleteInCol(tmp); //在列链表中将tmp删除 } pre=p;p=p->right;pa=pa->right; } } h=h->next; ah=ah->next; //处理下一行 }

return *this; }

template //重载加法运算符+

LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b){ LinkMatrix c(a); //复制构造函数得到被加矩阵A的一个副本放在矩阵C中 c+=b;return c; }

template

ostream & operator<<(ostream & out ,LinkMatrix& a) { for(int i=1;i<=a.head->row;i++) { MatrixNode*b=a.Head(i); b=b->right;

for(int j=1;j<=a.head->col;j++) { if(b->row==i&&b->col==j) { cout<data<<' '; b=b->right; } else { cout<<'0'<<' '; } } cout<

int main() { LinkMatrixa,b,c; cin>>a; cout<<\矩阵为：\\n\ cin>>b; cout<<\矩阵为：\\n\ c=a+b; cout<<\ system(\ return 0; }