《十字链表实现稀疏矩阵的加法》由会员分享，可在线阅读，更多相关《十字链表实现稀疏矩阵的加法（15页珍藏版）》请在装配图网上搜索。
1、实验二 十字链表
一、实验题目
以十字链表为储存结构，实现稀疏矩阵的求和运算。
二、问题描述
1、 功能要求：根据用户输入的矩阵，实现稀疏矩阵的求和运算，并输出结果。
2、 输入要求：矩阵的数据在程序运行的时候由用户提供，先由用户输入稀疏矩阵的行
数、列数和非零元个数。再根据非零元个数，输入这些非零元，还需要用户为这些非零元输入行、列和非零元的值。这样，一个稀疏矩阵就输入完成。
若输入
3 3 2
则表示这个稀疏矩阵有3行3列2个非零元
然后用户需要为这两个非零元输入行、列、非零元的值
如：
1 1
2、 2
2 2 1
表示第一个非零元行为1，列为1,，值为2；第二个非零元行为2，列为2，值为1。
此过程输入的稀疏矩阵为：
2 0 0
0 1 0
0 0 0
3、 输出要求：输出按矩阵输出，按行列依次输出，非零元则输出非零元的值，不是非
零元则输出“0”。各元素之间用空格隔开。最后输出完整的矩阵。
三、概要设计
1．稀疏矩阵的抽象数据类型定义如下：
ADT S
3、parseMatrix {
数据对象：
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);
//求稀疏矩阵
4、的转置矩阵
AddSMatrix(&M,&N);
//求稀疏矩阵M和N之和
MulSMatrix(&M,&N);
//求稀疏矩阵M和N之积
}ADT SparseMatrix
2、 存储结构选择
采用十字链表存储稀疏矩阵，它是稀疏矩阵链式表示的一种较好的表示方法。在十字链表中，每一个非零矩阵元素存储在一个结点内。每一个节点除了存储非零元素的三元组以外，还设置了right和down两个指针，分别指向同一行的下一个非零元素结点和同一列的下一个非零元结点。
3、 其他函数
1） 主函数main（）
2） 作为友元函数的加法运算。
四、 详细设计
用十字链表表示稀疏矩阵
5、，需要定义结点类和链表类两个类
1、 结点类MatrixNode
templateclass MatrixNode
{
friend class LinkMatrix;
friend istream&operator>>(istream&,LinkMatrix&);
friend ostream&operator<<(ostream&out, LinkMatrix&);
friend LinkMatrix operator +(const LinkMatrix &a,
6、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(MatrixNod
7、e*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,cons
8、t 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(Matri
9、xNode*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
10、=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<<"输入矩阵的行数、列数、
11、和非零元素个数"<>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
12、->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)"<;
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
13、;
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
ostream & operator<<(ostream & out ,LinkMatrix& a)
{
for(int i=1;i<=a.head->row;i++)
14、
{
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<
15、e> //重载符合赋值运算符+=
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<<"The two matrice aren't isomorphic!";
//throw domain_error("The two matrice aren't isomor
16、phic!");
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=ne
17、w 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); //在列链表
18、中将tmp删除
}
pre=p;p=p->right;pa=pa->right;
}
}
h=h->next; ah=ah->next; //处理下一行
}
return *this;
}
9、 重载+
template //重载加法运算符+
LinkMatrix operator +(const LinkMatrix &a,const LinkMatrix &b){
LinkMatrix c(a); //复制构造函数得到被加矩阵A的一个副本放在矩阵C中
c+=b;return c;
}
19、
五、 调试与测试
1、 编译环境
Visual C++ 6.0
2、 main函数
int main()
{
LinkMatrixa,b,c;
cin>>a;
cout<<"A矩阵为：\n"<>b;
cout<<"B矩阵为：\n"<
20、
表示这个矩阵行数为3，列数为3，非零元个数为3，接着提示“请输入一个非零元三元组”。
输入
1 1 1
表示第一个三元组的行为1，列为1，值为1
然后程序继续提示“输入一个非零元三元组”。
按要求再依次输入
2 2 2
3 1 5
则矩阵A输入完成，程序按矩阵格式输出矩阵A
程序继续提示“请输入行数、列数、非零元个数”
在按上述操作继续输入
3 3 4
1 1 2
2 1 1
3 1 1
21、3 3 3
为矩阵B输入，完成后程序输入矩阵B
程序同时输出A+B
3、 结果分析
程序提供输入和输出，根据输入的矩阵A和矩阵B，A+B计算结果准确无误。
六、 使用说明
使用本程序简单明了，只需根据提示为稀疏矩阵输入，就可以计算出稀疏矩阵的和。
附录2：
十字链表实现稀疏矩阵相加源程序
软件2班 201113040207
#include
using namespace std;
22、
templateclass MatrixNode;
templateclass LinkMatrix;
templateistream &operator>>(istream &,LinkMatrix&);
templateostream &operator<<(ostream &,LinkMatrix&);
templateLinkMatrix operator +(const LinkMatrix &a,con
23、st LinkMatrix &b);
templateclass MatrixNode
{
friend class LinkMatrix;
friend istream&operator>>(istream&,LinkMatrix&);
friend ostream&operator<<(ostream&out, LinkMatrix&);
friend LinkMatrix operator +(const LinkMatrix &a,const Lin
24、kMatrix &b);
private:
int row,col;
MatrixNode*right,*down;
union{
Type data;
MatrixNode*next;
};
};
templateclass LinkMatrix
{
private:
MatrixNode *head;
void InsertInCol(MatrixNode*p);
void DeleteInCol(MatrixNode*p);
pub
25、lic:
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
26、> &b);
};
int main()
{
LinkMatrixa,b,c;
cin>>a;
cout<<"A矩阵为：\n"<>b;
cout<<"B矩阵为：\n"<
istream&operator>>(istream&in,LinkMatrix&a)
{
int m,
27、n,terms,s;
MatrixNode**cp,*p,*q;
cout<<"输入矩阵的行数、列数、和非零元素个数"<>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++)
{
28、
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)"<;
in>>p->row>>p->col>>p->data;
q=cp[p->row];
while((q->right!=cp[p->r
29、ow]&&(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)
30、
{
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;
31、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 inv
32、alid_arguement("No such a Node to be deleted in DeleteInCol()");
}
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<
33、<"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 !=ah) { //处理当前行
if(p !=h&&(p->col
34、>col)){ //若被加矩阵的列标更小，则比较下一个
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;
35、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,c
36、onst 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<
十字链表实现稀疏矩阵的加法
