一、问题描述
十字链表实现稀疏矩阵的加法
1、 功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。
2、 输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行 数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。 若输入
4 3 2
则表示这个稀疏矩阵有4行3列2个非零元
然后用户需要为这两个非零元输入行、列、非零元的值 如：
1 2 2 4 1 1
表示第一个非零元行为1，列为2,，值为2；第二个非零元行为4，列为1，值为1。 此过程输入的稀疏矩阵为：
0 2 0 0 0 0 0 0 0 1 0 0
3、 输出要求：输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非 零元则输出“0”。各元素之间用空格隔开。最后输出完整的矩阵。
二、概要设计
1．稀疏矩阵的抽象数据类型定义如下： ??ADT SparseMatrix {??
数据对象： ??D={aij|i=1,2,3??m,j=1,2,3??n;
aij属于ElemSet,m和n分别是稀疏矩阵的行数和列数} 数据关系：?? R={ Row, Col } Row={|1<=i<=m,1<=j<=n-1} Col={|1<=i<=m-1,1<=j<=n} 基本操作：
CreateSMatrix(&M); //建立稀疏矩阵M DestroySMatrix(&M); //销毁稀疏矩阵M； TransposeSMatrix(M); //求稀疏矩阵的转置矩阵 AddSMatrix(&M,&N); //求稀疏矩阵M和N之和 MulSMatrix(&M,&N);
//求稀疏矩阵M和N之积 }ADT SparseMatrix
2、存储结构选择
采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点内。每一个节点除了存储非零元素的三元组以外，还设置了right和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元结点。 3、其他函数
1）主函数main（）
2）作为友元函数的加法运算。
三、选择数据结构
结点MatrixNode 链表LinkMatrix
四、详细算法
用十字链表表示稀疏矩阵，需要定义结点类和链表类两个类 1、结点类MatrixNode
templateclass MatrixNode {
friend class LinkMatrix; friend istream&operator>>(istream&,LinkMatrix&); friend ostream&operator<<(ostream&out, LinkMatrix&);
friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b); private: int row,col; MatrixNode*right,*down; union{ Type data; MatrixNode*next; }; };
2、链表类
templateclass LinkMatrix { private: MatrixNode *head; void InsertInCol(MatrixNode*p); void DeleteInCol(MatrixNode*p); public:
friend istream&operator>>(istream&in,LinkMatrix&); friend ostream&operator<<(ostream&out,LinkMatrix&); MatrixNode* Head(int i); LinkMatrix&operator +=(const LinkMatrix &a); friend LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b); };
3、求头结点函数
template MatrixNode* LinkMatrix::Head(int i) {
MatrixNode*a; a=head->next; for(int j=1;jnext; } return a; }
4、将结点p插入p->col列中
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; }
5、在p->col列中删除结点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; } }
6、重载>>函数
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; }
7、重载<<函数
template
loading