稀疏矩阵相乘.docx
- 文档编号:7225161
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:19
- 大小:95.10KB
稀疏矩阵相乘.docx
《稀疏矩阵相乘.docx》由会员分享,可在线阅读,更多相关《稀疏矩阵相乘.docx(19页珍藏版)》请在冰点文库上搜索。
稀疏矩阵相乘
稀疏矩阵相乘
1问题描述
稀疏矩阵的三元组及十字链表表示
(1)稀疏矩阵及其三元组表示
行(row)
列(col)
值(value)
[0]
0
3
22
[1]
0
6
15
[2]
1
1
11
[3]
1
5
17
[4]
2
3
-6
[5]
3
5
39
[6]
4
0
39
[7]
5
2
28
稀疏矩阵
(2)稀疏矩阵的十字链表表示
基本要求
(1)以“带行逻辑链接信息”的三元组表示稀疏矩阵;
(2)输入矩阵用三元组顺序输入;
(2)稀疏矩阵采用十字链表表示;
(3)实现两个矩阵相乘的运算,而运算结果的矩阵则以通常的阵列形式列出。
2设计思路
存储结构设计
三元组表示稀疏矩阵
只存储矩阵中极少的非零元素,采用
各数组元素的三元组按在原矩阵中的位置以行优先的顺序依次存放。
structtriple
{//三元组结构定义
introw,col;//非零元素行号,列号
Floatvalue;//非零元素的值
triple&operator=(triple&x)
{row=;col=;value=;}
};
十字链表表示稀疏矩阵
structelement{introw,col;floatvalue;};
classMatrix;
classnode
{//矩阵节点类的定义
friendclassMatrix;
public:
node():
head(true){right=down=this;}//建立附加头结点
node(element*t)//建立非零元素结点
{
=t->col;
=t->row;
=t->value;
right=down=this;
head=false;
}
node*down,*right;//行列链表指针
boolhead;
union{elementtriple;node*next;};//无名联合
};
classMatrix
{//稀疏矩阵的类定义
friendistream&operator>>(istream&,Matrix&);
friendostream&operator<<(ostream&,Matrix&);
private:
intRow,Col,Terms,temp;//矩阵的总行数,总列数,和非零元素个数和临时变量;
node*headnode;//稀疏矩阵的总表头
public:
Matrix(intm,intn);//重载构造函数
Matrix();//对矩阵进行构造
Matrix(Matrix&T);//复制构造函数
~Matrix(){makeEmpty();}//析构函数
voidInit(intm,intn);//初始化函数,又来初始化无参构造函数构造的矩阵
voidmakeEmpty();//清空矩阵
voidInsert(intm,intn,floatp);//插入矩阵元素
node*Locate(inti);//定位附加头结点
MatrixMul(Matrixb);//两个矩阵相乘
Matrix&operator=(Matrix&T);//重载赋值号
};
在稀疏矩阵的十字链表表示中,矩阵的的每一行设置为一个带附加头结点的循环行链表,每一列也设置为一个带附加头结点的循环列链表。
链表中的结点都属于类node的对象,这个类包含一个域head,它用于区分改结点是附加头结点还是链表中的非零元素结点;head=true,表示该结点是附加头结点;head=false,表示该结点是矩阵中的非零元素结点。
每一个附加头结点还有三个域:
down、right、next。
第i个行链表和第i个列链表共用一个附加头结点,在它的right域存放第i行链表最前端的第一个结点的地址,在它的down域存放第i列链表的最前端第一个结点的地址,通过next域链接到第i+1个附加头结点。
每一个非零元素结点包含六个域:
head,row,col,down,right,value。
Down存放列链表指针,right存放行链表指针。
整个稀疏矩阵定义为类Matrix的一个对象,*headnode给出整个附加头结点链表的附加头结点的地址。
head
next
down
right
head
row
col
down
value
right
非零元素结点
附加头结点非零元素结点
主要算法
基于三元组及十字链表的稀疏矩阵乘法
MatrixMatrix:
:
Mul(Matrixb)//矩阵乘法的实现
{
if(this->Col==
{
MatrixC(this->Row,;//以A矩阵的行和b矩阵的列为行列建立稀疏矩阵
floatvalue;
node*Row_head,*Col_head;//设两个指针,一个充当行头指针,一个为列指针for(inti=1;i<=temp;i++)//先确定行,再求出C矩阵在该行各列的元素
{
for(intj=1;j<=temp;j++)//通过确定列头指针来实现遍历相乘
{value=0;
Row_head=Locate(i);
Col_head=(j);
while(Row_head->right!
=Locate(i))
{//假如行中还有元素不为零就找与之匹配的元素相Row_head=Row_head->right;
Col_head=Col_head->down;
while(Row_head->!
=Col_head->
&&Col_head->down!
=(j))
{//假如行列不相等而且对应列还有元素,就继续找匹配的元素否则判断再环
if(Row_head->>Col_head->
Col_head=Col_head->down;
else{
if(Row_head->right==Locate(i))
Col_head=Col_head->down;//假如b矩阵该列元素比a矩阵该行元素elseRow_head=Row_head->right;
//则b中该列元素已经无法找到能相乘元素则往下推直至跳出循环
}
}
if(Col_head->down!
=(j)||Col_head->==Row_head->
{value+=Row_head->*Col_head->;}
}
if(value!
=0){(i,j,value)}
}
}
returnC;
}
else{MatrixC;
cerr<<"输入的两个矩阵不符规则,不能相乘!
"< returnC; } } 测试用例 3调试分析 调试过程 (1)编译时程序中没有语法错误,但是格式及语句的书写错误叫多,按照编译错误提示一次改正错误,直至编译正确。 (2)运行程序。 以三元组的形式,即输入矩阵的行数、列数、非零元素个数和各非零元素的行、列、值,输入两个稀疏矩阵,输出了两个矩阵及它们的乘积。 (3)问题: 输出的矩阵不符合要求,形成的阵列中只有非零元素,零元素都没有输出。 说明友元输入函数有问题,将元函数改为下面的函数后能正确输出矩阵阵列。 ostream&operator<<(ostream&out,Matrix&b)//输出函数 {node*x; for(inti=1;i<=;i++)//先确定各行头结点的位置再遍历各行,以输出所有非零元 { x=(i); x=x->right; for(intj=1;j<=;j++) {if(x->head==false&&(x->==j) { (4); out< x=x->right; } elseif(x->head==true) {for(j;j<=;j++){(4);cout<<"0";}break;} else{(4);cout<<"0";} } cout< } returnout; } 设计分析 (1)此程序中乘法算法的时间复杂度为O(Rows*Cols)。 (2)此程序没有将类做成模版,导致只能输入floate型的值。 改进方案: 将所有的类做成模版,将其属下的floate类型的全改为模版类型参数 (3)此程序显的很繁锁,算法比较复杂 (4)此程序只有稀疏矩阵的乘法,可以加入其他的矩阵运算来完善运算,也可以再主程序中设计选择菜单,实现多种运算。 (5)改进算法: 重新考虑算法,看是否可用数组加指针的方式实现,用数组可以简化找头指针的繁琐过程,简化循环的过程提高程序运行效率! 4经验与体会 我的题目是实现三元组,十字链表下乘法,运算。 看到这个题目的时候,我一片茫然,因为我们数据结构这一部分并没有讲,我根本就不知道十字链表是什么。 于是我赶紧看书,可是书上对十字链表的将就知识一笔带过,更不要指望在书上找到相关代码了。 于是我先学习了三元组数组的乘法算法,在这个基础上,我在网上收集各种资料收集和算法。 然后不断调试,不断改进程序,最终正确结果终于运行出来了。 我觉得自己的数据结构学得不好,但是数据结构可以说是计算机里一门基础课程,对于以后的学习尤为重要。 所以我们一定要把基础学扎实,这次的课内实践帮我重新巩固基础知识,也学了很多新知识,提高了我的专业的动手实践能力,也提高了我的对数据结构的学习兴趣。 此次课程设计过程中,我真正的体验到,拿到一个问题,应该先分析,将其的属性,功能分析清楚后,再进行细化,考虑其实现的具体的、有效的算法,有了整体的结构框架后再上机! 以前只要拿到题就直接打开电脑,想到什么就写什么,没整体思考,对小程序可以,大程序就会彻底崩溃。 编程实质就是问题的分析及其实现的算法,这两方面解决了上机编程才会得心应手,剩下的就是按算法些代码了! 确定一个好算法很难,一个人往往陷入死循环,思路受局限,找人讨论很必要,编程时团队意识很重要,这不是一个人就能搞定的。 在实践的过程中我每天完成一小部分。 尽量减少操作的盲目性,提高我们学习的效率。 有个总体的大纲来逐步实现。 我也曾经犯过这种错误。 每个函数都做出来部分,结果都没做完。 所以我们要养成有良好的时间规划的习惯,只有一步一步的进行,我们才能完成得更好。 同时在实验中我们要培养自己独立的思考能力和解决问题的能力,不能太过依赖于同学和网络,我们应该要有自己的想法,培养自己的编程思维。 实践能力对我们今后的发展也是至关重要的,我们只有拥有很好地实践能力,才有机会再编程这个领域有所发展。 子啊编程的过程中,我们应该积极的朝着更好地一面发展不断的完善程序,不能马马虎虎随便应付一下。 就像古人云,纸上得来终觉浅,得知此事要躬行。 为了以后的计算机道路,我们应该不断的提高自身的专业素养。 5附录 程序 #include<> #include<> structelement{introw,col;floatvalue;}; classMatrix; classnode {//矩阵节点类的定义 friendclassMatrix; public: node(): head(true){right=down=this;}//建立附加头结点 node(element*t)//建立非零元素结点 { =t->col; =t->row; =t->value; right=down=this; head=false; } node*down,*right;//行列链表指针 boolhead; union{elementtriple;node*next;};//无名联合 }; classMatrix {//稀疏矩阵的类定义 friendistream&operator>>(istream&,Matrix&); friendostream&operator<<(ostream&,Matrix&); private: intRow,Col,Terms,temp;//矩阵的总行数,总列数,和非零元素个数和临时变量; node*headnode;//稀疏矩阵的总表头 public: Matrix(intm,intn);//重载构造函数 Matrix();//对矩阵进行构造 Matrix(Matrix&T);//拷贝构造函数 ~Matrix(){makeEmpty();}//析构函数 voidInit(intm,intn);//初始化函数,又来初始化无参构造函数构造的矩阵 voidmakeEmpty();//清空矩阵 voidInsert(intm,intn,floatp);//插入矩阵元素 node*Locate(inti);//定位附加头结点 MatrixMul(Matrixb);//两个矩阵相乘 Matrix&operator=(Matrix&T);//重载赋值号 }; Matrix: : Matrix(intm,intn): Row(m),Col(n)//重载构造函数的实现 { elementx; =m; =n; =0; Terms=0; temp=m>=nm: n; node*current; headnode=newnode(&x); current=headnode->right=newnode(); for(inti=1;i { current->next=newnode(); current=current->next; } } Matrix: : Matrix(): Row(0),Col(0),Terms(0) {//构造函数的实现 elementx; =Row; =Col; =0; } Matrix: : Matrix(Matrix&T)//复制构造函数的实现 { Init,; node*current; for(inti=1;i<=temp;i++) { current=(i);//定位行 while(current->right! =(i)) {//通过行遍历逐个赋值 current=current->right; Insert(current->,current->,current->; } } } voidMatrix: : Init(intm,intn)//矩阵初始化函数的实现 { Row=m;Col=n;Terms=0; elementx; =m;=n;=0; headnode=newnode(&x); node*current; if(m>0&&n>0) { temp=m>=nm: n; current=newnode(); headnode->right=current; for(inti=1;i { current->next=newnode(); current=current->next; } } else{cout<<"矩阵初始化错误! "< } node*Matrix: : Locate(inti)//定位附加头结点实现 { node*current; current=headnode->right; for(intk=1;k { current=current->next; } returncurrent; } voidMatrix: : Insert(intm,intn,floatp)//插入函数的实现 { elementx; =m;=n;=p; if(m<=this->Row&&n<=this->Col) { node*Newnode=newnode(&x),*current,*head; head=Locate(m);//先定位行的位置再寻找列插入 current=head->right; if(current==head) { current->right=Newnode; Newnode->right=current; } else { while(current-> =head) { current=current->right; } Newnode->right=current->right; current->right=Newnode; }//完成插入 head=Locate(n);//先定位列再寻找行插入 current=head->down; if(current==head) { current->down=Newnode; Newnode->down=current; } else { while(current-> =head) { current=current->down; } Newnode->down=current->down; current->down=Newnode; } Terms++; }//完成插入 else { cout<<"输入的结点位置超出了范围,请重新输入! "< } } istream&operator>>(istream&in,Matrix&b)//输入函数重载的实现 { intM,N,m,n,T;floatp; cout<<"请输入矩阵的行列和非零元素个数: "< in>>M>>N>>T; (M,N); if(T>(M*N)) { cerr<<"输入的元素个数超过范围"< exit (1); } else { cout<<"请输入各非零元素的行数列数和值"< cout<<"行数列数值"< for(inti=1;i<=T;i++)//输入元素结点并且插入矩阵 { cout<<"["< "; in>>m>>n>>p; (m,n,p);//插入结点 } returnin; } } ostream&operator<<(ostream&out,Matrix&b)//输出函数重载 { node*x; for(inti=1;i<=;i++)//先确定各行头结点的位置再遍历各行,以输出所有非零元 { x=(i); x=x->right; for(intj=1;j<=;j++) { if(x->head==false&&(x->==j)) { (4); out< x=x->right; } elseif(x->head==true) { for(j;j<=;j++){(4);cout<<"0";} break; } else{(4);cout<<"0";} } cout< } returnout; } Matrix&Matrix: : operator=(Matrix&T)//重载赋值号函数的实现 { this->Row=; this->Col=; node*current; for(inti=1;i<=temp;i++) { current=(i); while(current->right! =current) { current=current->right;//通过行遍历逐个赋值 this->Insert(current->,current->,current->; } } return*this; } voidMatrix: : makeEmpty()//清空矩阵的实现 { node*del,*current; for(inti=1;i<=temp;i++) { current=Locate(i);//找到列的附加头结点 while(current->down! =Locate(i)) { del=current->down;//通过列的附加头结点向下删除结点 current->down=del->down; deletedel; } } } MatrixMatrix: : Mul(Matrixb)//矩阵乘法的实现 { if(this->Col== { MatrixC(this->Row,;//以A矩阵的行和b矩阵的列为行列建立稀疏矩阵 floatvalue; node*Row_head,*Col_head;//设两个指针,一个充当行头指针,一个为列指针 for(inti=1;i<=temp;i++)//先确定行,再求出C矩阵在该行各列的元素 { for(intj=1;j<=temp;j++)//通过确定列头指针来实现遍历相乘 { value=0; Row_head=Locate(i); Col_head=(j); while(Row_head->right! =Locate(i)) {//假如行中还有元素不为零就找与之匹配的元素相乘 Row_head=Row_head->right; Col_head=Col_head->down; while(Row_head->! =Col_head->&&Col_head->down! =(j)) {//假如行列不相等而且对应列还有元素,就继续找匹配的元素否则判断再循环 if(Row_head->>Col_head-> Col_head=Col_head->down; else { if(Row_head->right==Locate(i)) Col_head=Col_head->down; //假如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 稀疏 矩阵 相乘