十字链表实现稀疏矩阵的加法.docx

《十字链表实现稀疏矩阵的加法.docx》由会员分享，可在线阅读，更多相关《十字链表实现稀疏矩阵的加法.docx（15页珍藏版）》请在三一文库上搜索。

1、.实验二 十字链表 一、实验题目 以十字链表为储存结构，实现稀疏矩阵的求和运算。 二、问题描述1、 功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。2、 输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。 若输入3 3 2 则表示这个稀疏矩阵有3行3列2个非零元 然后用户需要为这两个非零元输入行、列、非零元的值 如：1 1 22 2 1 表示第一个非零元行为1，列为1,，值为2；第二个非零元行为2，列为2，值为1。 此过程输

2、入的稀疏矩阵为： 2 0 0 0 1 0 0 0 03、 输出要求：输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非零元则输出“0”。各元素之间用空格隔开。最后输出完整的矩阵。 三、概要设计1稀疏矩阵的抽象数据类型定义如下：ADT SparseMatrix 数据对象： D=aij|i=1,2,3m,j=1,2,3n; aij属于ElemSet,m和n分别是稀疏矩阵的行数和列数数据关系： R= Row, Col Row=<aij,aij+1>|1<=i<=m,1<=j<=n-1Col=<aij,ai+1j>|1<=i<=m

3、-1,1<=j<=n基本操作：CreateSMatrix(&M);/建立稀疏矩阵MDestroySMatrix(&M);/销毁稀疏矩阵M；TransposeSMatrix(M);/求稀疏矩阵的转置矩阵AddSMatrix(&M,&N);/求稀疏矩阵M和N之和MulSMatrix(&M,&N);/求稀疏矩阵M和N之积ADT SparseMatrix2、 存储结构选择采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点内。每一个节点除了存储非零元素的三元组以外，还设置了righ

4、t和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元结点。3、 其他函数1） 主函数main（）2） 作为友元函数的加法运算。4、 详细设计用十字链表表示稀疏矩阵，需要定义结点类和链表类两个类1、 结点类MatrixNodetemplate<class Type>class MatrixNode friend class LinkMatrix<Type>friend istream&operator>>(istream&,LinkMatrix<Type>&); friend ostream&

5、;operator<<(ostream&out, LinkMatrix<Type>&); friend LinkMatrix<Type> operator +(const LinkMatrix<Type> &a,const LinkMatrix<Type> &b);private:int row,col;MatrixNode<Type>*right,*down;unionType data;MatrixNode<Type>*next;2、 链表类template<class

6、 Type>class LinkMatrixprivate:MatrixNode<Type> *head;void InsertInCol(MatrixNode<Type>*p);void DeleteInCol(MatrixNode<Type>*p);public:friend istream&operator>>(istream&in,LinkMatrix<Type>&);friend ostream&operator<<(ostream&out,LinkMatrix<

7、;Type>&);MatrixNode<Type>* Head(int i);LinkMatrix<Type>&operator +=(const LinkMatrix<Type> &a);friend LinkMatrix<Type> operator +(const LinkMatrix<Type> &a,const LinkMatrix<Type> &b); ;3、 求头结点函数template<class Type> MatrixNode<Type&g

8、t;* LinkMatrix<Type>:Head(int i) MatrixNode<Type>*a;a=head->next;for(int j=1;j<i;j+)a=a->next; return a;4、 将结点p插入p->col列中template<class Type>void LinkMatrix<Type>:InsertInCol(MatrixNode<Type>*p)MatrixNode<Type>*pre,*ch=Head(p->col);pre=ch;while(pre-

9、>down!=ch&&pre->down->row<p->row)pre=pre->down;p->down=pre->down;pre->down=p;5、 在p->col列中删除结点p，并释放空间template<class Type>void LinkMatrix<Type>:DeleteInCol(MatrixNode<Type>*p)MatrixNode<Type>*pre,*ch=Head(p->col);pre=ch;while(pre->dow

10、n!=ch&&pre->down!=p)pre=pre->down;if(pre->down=p)pre->down=p->down;delete p;6、 重载>>函数template<class Type>istream&operator>>(istream&in,LinkMatrix<Type>&a)int m,n,terms,s;MatrixNode<Type>*cp,*p,*q;cout<<"输入矩阵的行数、列数、和非零元素个数&qu

11、ot;<<endl;in>>m>>n>>terms;if(n>m)s=n;else s=m;a.head=new MatrixNode<Type>a.head->row=m;a.head->col=n;a.head->right=a.head->down=NULL;cp=new MatrixNode<Type>*s+1;cp0=a.head;int i;for(i=1;i<=s;i+)p=new MatrixNode<Type>p->row=p->col=0;p-

12、>right=p->down=p;cpi=p;cpi-1->next=p;cps->next=a.head;for(i=1;i<=terms;i+)cout<<"输入一个非零元三元组(row,col,value)"<<endl;p=new MatrixNode<Type>in>>p->row>>p->col>>p->data;q=cpp->row;while(q->right!=cpp->row&&(q->right

13、->col<p->col)q=q->right;p->right=q->right;q->right=p;q=cpp->col;while(q->down!=cpp->row&&(q->down->col<p->col)q=q->down;p->down=q->down;q->down=p;deletecp;return in;7、 重载<<函数template<class Type>ostream & operator<<(o

14、stream & out ,LinkMatrix<Type>& a)for(int i=1;i<=a.head->row;i+)MatrixNode<Type>*b=a.Head(i);b=b->right;for(int j=1;j<=a.head->col;j+)if(b->row=i&&b->col=j)cout<<b->data<<' 'b=b->right;elsecout<<'0'<<'

15、 'cout<<endl;return out; 8、 重载+=实现求和函数template<class Type> /重载符合赋值运算符+=LinkMatrix<Type>&LinkMatrix<Type>:operator +=(const LinkMatrix<Type> &a)MatrixNode<Type> *pre,*pa,*h,*ah,*p,*tmp;if(head->col !=a.head->col|head->row !=a.head->row)/非同型矩

16、阵不可相加cout<<"The two matrice aren't isomorphic!"/throw domain_error("The two matrice aren't isomorphic!");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 !

17、=ah) /处理当前行if(p !=h&&(p->col<pa->col) /若被加矩阵的列标更小，则比较下一个pre=p; p=p->right;else if(p=h|p->col>pa->col) tmp=new MatrixNode<Type>(*pa) ;pre->right=tmp; /在行链表中插入pa复制结点tmptmp->right=p;InsertInCol(tmp); /在列表中插入tmppre=tmp; /当前指针p的前驱变为tmppa=pa->right;else /列标相同，则做

18、加法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;9、 重载+template<class Type> /重载加法运算符+LinkMatrix<Type> operator +

19、(const LinkMatrix<Type> &a,const LinkMatrix<Type> &b)LinkMatrix<Type> c(a); /复制构造函数得到被加矩阵A的一个副本放在矩阵C中c+=b;return c;5、 调试与测试1、 编译环境Visual C+ 6.02、 main函数int main()LinkMatrix<int>a,b,c;cin>>a;cout<<"A矩阵为：n"<<a<<endl;cin>>b;cout<

20、;<"B矩阵为：n"<<b<<endl;c=a+b;cout<<"A+B=n"<<c<<endl;system("pause");return 0;3、 具体步骤按F5编译，界面出现提示“请输入行数、列数、非零元个数”。输入3 3 3表示这个矩阵行数为3，列数为3，非零元个数为3，接着提示“请输入一个非零元三元组<row,col,value>”。输入1 1 1表示第一个三元组的行为1，列为1，值为1然后程序继续提示“输入一个非零元三元组<row,col

21、,value>”。按要求再依次输入2 2 23 1 5则矩阵A输入完成，程序按矩阵格式输出矩阵A程序继续提示“请输入行数、列数、非零元个数”在按上述操作继续输入3 3 41 1 22 1 13 1 13 3 3为矩阵B输入，完成后程序输入矩阵B程序同时输出A+B3、 结果分析程序提供输入和输出，根据输入的矩阵A和矩阵B，A+B计算结果准确无误。6、 使用说明使用本程序简单明了，只需根据提示为稀疏矩阵输入，就可以计算出稀疏矩阵的和。附录2： 十字链表实现稀疏矩阵相加源程序 软件3班 魏希 201005070301#include<iostream>using namespace

22、 std;template<class Type>class MatrixNode; template<class Type>class LinkMatrix;template<class Type>istream &operator>>(istream &,LinkMatrix<Type>&);template<class Type>ostream &operator<<(ostream &,LinkMatrix<Type>&);template&l

23、t;class Type>LinkMatrix<Type> operator +(const LinkMatrix<Type> &a,const LinkMatrix<Type> &b);template<class Type>class MatrixNode friend class LinkMatrix<Type>friend istream&operator>>(istream&,LinkMatrix<Type>&); friend ostream&o

24、perator<<(ostream&out, LinkMatrix<Type>&); friend LinkMatrix<Type> operator +(const LinkMatrix<Type> &a,const LinkMatrix<Type> &b);private:int row,col;MatrixNode<Type>*right,*down;unionType data;MatrixNode<Type>*next;template<class Type>

25、;class LinkMatrixprivate:MatrixNode<Type> *head;void InsertInCol(MatrixNode<Type>*p);void DeleteInCol(MatrixNode<Type>*p);public:friend istream&operator>>(istream&in,LinkMatrix<Type>&);friend ostream&operator<<(ostream&out,LinkMatrix<Type>

26、;&);MatrixNode<Type>* Head(int i);LinkMatrix<Type>&operator +=(const LinkMatrix<Type> &a);friend LinkMatrix<Type> operator +(const LinkMatrix<Type> &a,const LinkMatrix<Type> &b); ;int main()LinkMatrix<int>a,b,c;cin>>a;cout<<&q

27、uot;A矩阵为：n"<<a<<endl;cin>>b;cout<<"B矩阵为：n"<<b<<endl;c=a+b;cout<<"A+B=n"<<c<<endl;system("pause");return 0;template<class Type>istream&operator>>(istream&in,LinkMatrix<Type>&a)int m,

28、n,terms,s;MatrixNode<Type>*cp,*p,*q;cout<<"输入矩阵的行数、列数、和非零元素个数"<<endl;in>>m>>n>>terms;if(n>m)s=n;else s=m;a.head=new MatrixNode<Type>a.head->row=m;a.head->col=n;a.head->right=a.head->down=NULL;cp=new MatrixNode<Type>*s+1;cp0=a.h

29、ead;int i;for(i=1;i<=s;i+)p=new MatrixNode<Type>p->row=p->col=0;p->right=p->down=p;cpi=p;cpi-1->next=p;cps->next=a.head;for(i=1;i<=terms;i+)cout<<"输入一个非零元三元组(row,col,value)"<<endl;p=new MatrixNode<Type>in>>p->row>>p->col>

30、>p->data;q=cpp->row;while(q->right!=cpp->row&&(q->right->col<p->col)q=q->right;p->right=q->right;q->right=p;q=cpp->col;while(q->down!=cpp->row&&(q->down->col<p->col)q=q->down;p->down=q->down;q->down=p;deletecp;re

31、turn in;template<class Type> MatrixNode<Type>* LinkMatrix<Type>:Head(int i) MatrixNode<Type>*a;a=head->next;for(int j=1;j<i;j+)a=a->next; return a;template<class Type>void LinkMatrix<Type>:InsertInCol(MatrixNode<Type>*p)MatrixNode<Type>*pre,*c

32、h=Head(p->col);pre=ch;while(pre->down!=ch&&pre->down->row<p->row)pre=pre->down;p->down=pre->down;pre->down=p;template<class Type>void LinkMatrix<Type>:DeleteInCol(MatrixNode<Type>*p)MatrixNode<Type>*pre,*ch=Head(p->col);pre=ch;while(pr

33、e->down!=ch&&pre->down!=p)pre=pre->down;if(pre->down=p)pre->down=p->down;delete p;/else throw invalid_arguement("No such a Node to be deleted in DeleteInCol()");template<class Type> /重载符合赋值运算符+=LinkMatrix<Type>&LinkMatrix<Type>:operator +=(co

34、nst LinkMatrix<Type> &a)MatrixNode<Type> *pre,*pa,*h,*ah,*p,*tmp;if(head->col !=a.head->col|head->row !=a.head->row)/非同型矩阵不可相加cout<<"The two matrice aren't isomorphic!"/throw domain_error("The two matrice aren't isomorphic!");h=head->n

35、ext;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->col<pa->col) /若被加矩阵的列标更小，则比较下一个pre=p; p=p->right;else if(p=h|p->col>pa->col) /若加矩阵的列标更小，则插入tmp=ne

36、w MatrixNode<Type>(*pa) ;pre->right=tmp; /在行链表中插入pa复制结点tmptmp->right=p;InsertInCol(tmp); /在列表中插入tmppre=tmp; /当前指针p的前驱变为tmppa=pa->right;else /列标相同，则做加法p->data +=pa->data;if(!p->data) /和为0，则删除之 （行、列都要删除）tmp=p;p=p->right;pre->right=p;/在行链表中将tmp摘下DeleteInCol(tmp); /在列链表中将tm

37、p删除pre=p;p=p->right;pa=pa->right;h=h->next; ah=ah->next; /处理下一行return *this;template<class Type> /重载加法运算符+LinkMatrix<Type> operator +(const LinkMatrix<Type> &a,const LinkMatrix<Type> &b)LinkMatrix<Type> c(a); /复制构造函数得到被加矩阵A的一个副本放在矩阵C中c+=b;return c;te

38、mplate<class Type>ostream & operator<<(ostream & out ,LinkMatrix<Type>& a)for(int i=1;i<=a.head->row;i+)MatrixNode<Type>*b=a.Head(i);b=b->right;for(int j=1;j<=a.head->col;j+)if(b->row=i&&b->col=j)cout<<b->data<<' 'b=b->right;elsecout<<'0'<<' 'cout<<endl;return out; ；.