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

本文格式为Word版，下载可任意编辑——数据结构课程设计报告（十字链表实现稀疏矩阵的加法）

一、问题描述

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

1、功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。

2、输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。若输入

432

则表示这个稀疏矩阵有4行3列2个非零元

然后用户需要为这两个非零元输入行、列、非零元的值如：

122411

表示第一个非零元行为1，列为2,，值为2；其次个非零元行为4，列为1，值为1。此过程输入的稀疏矩阵为：

020000000100

3、输出要求：输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非零元则输出“0〞。各元素之间用空格隔开。最终输出完整的矩阵。

二、概要设计

1．稀疏矩阵的抽象数据类型定义如下：??ADTSparseMatrix{??

数据对象：??D={aij|i=1,2,3??m,j=1,2,3??n;aij属于ElemSet,m和n分别是稀疏矩阵的行数和列数}数据关系：??R={Row,Col}Row={|1classMatrixNode{

friendclassLinkMatrix;friendistreamfriendostream

friendLinkMatrixoperator+(constLinkMatrixprivate:introw,col;MatrixNode*right,*down;union{Typedata;MatrixNode*next;};};

2、链表类

templateclassLinkMatrix{private:MatrixNode*head;voidInsertInCol(MatrixNode*p);voidDeleteInCol(MatrixNode*p);public:

friendistreamfriendostreamMatrixNode*Head(inti);LinkMatrixfriendLinkMatrixoperator+(constLinkMatrix};

3、求头结点函数

templateMatrixNode*LinkMatrix::Head(inti){

MatrixNode*a;a=head->next;for(intj=1;jnext;}returna;}

4、将结点p插入p->col列中

templatevoidLinkMatrix::InsertInCol(MatrixNode*p){MatrixNode*pre,*ch=Head(p->col);pre=ch;while(pre->down!=chp->down=pre->down;pre->down=p;}

5、在p->col列中删除结点p，并释放空间

templatevoidLinkMatrix::DeleteInCol(MatrixNode*p){MatrixNode*pre,*ch=Head(p->col);pre=ch;while(pre->down!=chif(pre->down==p){pre->down=p->down;deletep;}}

6、重载>>函数

templateistreamMatrixNode**cp,*p,*q;cout>m>>n>>terms;if(n>m)s=n;elses=m;a.head=newMatrixNode;a.head->row=m;a.head->col=n;a.head->right=a.head->down=NULL;cp=newMatrixNode*[s+1];cp[0]=a.head;inti;for(i=1;i;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;in>>p->row>>p->col>>p->data;q=cp[p->row];while((q->right!=cp[p->row]p->right=q->right;q->right=p;q=cp[p->col];while((q->down!=cp[p->row]p->down=q->down;q->down=p;}delete[]cp;returnin;}

7、重载

ostreamirow;i++){MatrixNode*b=a.Head(i);b=b->right;for(intj=1;jcol;j++){if(b->row==ib=b->right;}else{cout//重载符合赋值运算符+=

LinkMatrix

if(head->col!=a.head->col||head->row!=a.head->row)//非同型矩阵不可相加coutnext;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!=hp=p->right;}

elseif(p==h||p->col>pa->col){tmp=newMatrixNode(*pa);

pre->right=tmp;//在行链表中插入pa复制结点tmp

tmp->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);//在列链表中将tmp删除}

pre=p;p=p->right;pa=pa->right;}}

h=h->next;ah=ah->next;//处理下一行}

return*this;}

9、重载+

template//重载加法运算符+

LinkMatrixoperator+(constLinkMatrix//复制构造函数得到被加矩阵A的一个副本放在矩阵C中c+=b;returnc;}

五、测试与探讨1、编译环境VisualC++6.02、main函数intmain(){LinkMatrixa,b,c;cin>>a;cout>b;cout〞。

输入

111

表示第一个三元组的行为1，列为1，值为1

然后程序继续提醒“输入一个非零元三元组〞。

按要求再依次输入222315

则矩阵A输入完成，程序按矩阵格式输出矩阵A

程序继续提醒“请输入行数、列数、非零元个数〞在按上述操作继续输入334112211311333

为矩阵B输入，完成后程序输入矩阵B程序同时输出A+B

3、结果分析

程序提供输入和输出，根据输入的矩阵A和矩阵B，A+B计算结果确凿无误。

六、用户手册

使用本程序简单明白，只需根据提醒为稀疏矩阵输入，就可以计算出稀疏矩阵的和。

附录：源代码

(只含pro1.cpp)：

//pro1.cpp

#includeusingnamespacestd;

templateclassMatrixNode;templateclassLinkMatrix;

templateistreamtemplateostream

templateLinkMatrixoperator+(constLinkMatrix

templateclassMatrixNode{

friendclassLinkMatrix;friendistreamfriendostream

friendLinkMatrixoperator+(constLinkMatrixprivate:introw,col;MatrixNode*right,*down;union{Typedata;MatrixNode*next;};};

templateclassLinkMatrix{private:MatrixNode*head;voidInsertInCol(MatrixNode*p);voidDeleteInCol(MatrixNode*p);public:friendistreamfriendostreamMatrixNode*Head(inti);LinkMatrix

friendLinkMatrixoperator+(constLinkMatrix};

templateistreamMatrixNode**cp,*p,*q;cout>m>>n>>terms;if(n>m)s=n;elses=m;a.head=newMatrixNode;a.head->row=m;a.head->col=n;a.head->right=a.head->down=NULL;cp=newMatrixNode*[s+1];cp[0]=a.head;inti;for(i=1;i;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;in>>p->row>>p->col>>p->data;q=cp[p->row];while((q->right!=cp[p->row]p->right=q->right;q->right=p;q=cp[p->col];while((q->down!=cp[p->row]p->down=q->down;q->down=p;}delete[]cp;returnin;

}

templateMatrixNode*LinkMatrix::Head(inti){

MatrixNode*a;a=head->next;for(intj=1;jnext;}returna;}

templatevoidLinkMatrix::InsertInCol(MatrixNode*p){MatrixNode*pre,*ch=Head(p->col);pre=ch;while(pre->down!=chp->down=pre->down;pre->down=p;}

templatevoidLinkMatrix::DeleteInCol(MatrixNode*p){MatrixNode*pre,*ch=Head(p->col);pre=ch;while(pre->down!=chif(pre->down==p){pre->down=p->down;deletep;}//elsethrowinvalid_arguement(\}

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

LinkMatrixif(head->col!=a.head->col||head->row!=a.head->row)//非同型矩阵不可相加coutnext;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!=hp=p->right;}elseif(p==h||p->col>pa->col){//若加矩阵的列标更小，则插入tmp=newMatrixNode(*pa);pre->right=tmp;//在行链表中插入pa复制结点tm