稀疏矩阵相乘

1、 稀疏矩阵相乘1问题描述1.1稀疏矩阵的三元组及十字链表表示（1) 稀疏矩阵及其三元组表示行（row)列（col)值（value)00322106152111131517423-6535396403975228稀疏矩阵（2）稀疏矩阵的十字链表表示1.2基本要求（1） 以“带行逻辑链接信息”的三元组表示稀疏矩阵；（2） 输入矩阵用三元组顺序输入；（2）稀疏矩阵采用十字链表表示；（3）实现两个矩阵相乘的运算，而运算结果的矩阵则以通常的阵列形式列出。2设计思路2.1存储结构设计2.1.1三元组表示稀疏矩阵只存储矩阵中极少的非零元素，采用<row,col,value>来唯一地确定每一个非零

2、元素，其中row、col、value分别表示非零元素在矩阵中的的行下标、列下表和值。各数组元素的三元组按在原矩阵中的位置以行优先的顺序依次存放。struct triple /三元组结构定义 int row, col; /非零元素行号,列号 Float value; /非零元素的值 triple& operator=(triple &x) row=x.row;col=x.col;value=x.value;2.1.2十字链表表示稀疏矩阵struct element int row,col;float value;class Matrix;class node / 矩阵节点类的定义

3、friend class Matrix;public:node():head(true) right=down=this; /建立附加头结点node(element *t) / 建立非零元素结点triple.col=t->col;triple.row=t->row;triple.value=t->value;right=down=this;head=false;node*down,*right;/行列链表指针bool head;union element triple;node*next; /无名联合;class Matrix/稀疏矩阵的类定义friend istream&a

4、mp;operator>>(istream&,Matrix&); friend ostream&operator<<(ostream&,Matrix&);private:int Row,Col,Terms,temp; /矩阵的总行数，总列数，和非零元素个数和临时变量；node*headnode; /稀疏矩阵的总表头public:Matrix(int m,int n); /重载构造函数Matrix(); /对矩阵进行构造Matrix(Matrix& T); /复制构造函数Matrix()makeEmpty(); /析构函数v

5、oid Init(int m,int n); /初始化函数，又来初始化无参构造函数构造的矩阵void makeEmpty(); /清空矩阵void Insert(int m,int n,float p); /插入矩阵元素node *Locate(int i); /定位附加头结点Matrix Mul(Matrix b); /两个矩阵相乘Matrix &operator=(Matrix &T); /重载赋值号;在稀疏矩阵的十字链表表示中，矩阵的的每一行设置为一个带附加头结点的循环行链表，每一列也设置为一个带附加头结点的循环列链表。链表中的结点都属于类node的对象，这个类包含一个域

6、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的

7、一个对象，*headnode给出整个附加头结点链表的附加头结点的地址。headnextdownrightheadrowcoldownvalueright 非零元素结点 附加头结点 非零元素结点2.2主要算法基于三元组及十字链表的稀疏矩阵乘法Matrix Matrix:Mul( Matrix b) /矩阵乘法的实现 if(this->Col=b.Row) Matrix C(this->Row,b.Col); /以A矩阵的行和b矩阵的列为行列建立稀疏矩阵 float value; node *Row_head,*Col_head; /设两个指针，一个充当行头指针，一个为列指针 for(

8、int i=1;i<=temp;i+) /先确定行，再求出C矩阵在该行各列的元素 for(int j=1;j<=temp;j+) /通过确定列头指针来实现遍历相乘 value=0; Row_head=Locate(i); Col_head=b.Locate(j); while(Row_head->right!=Locate(i) /假如行中还有元素不为零就找与之匹配的元素相 Row_head=Row_head->right; Col_head=Col_head->down; while(Row_head->triple.col!=Col_head->t

9、riple.row &&Col_head->down!=b.Locate(j) /假如行列不相等而且对应列还有元素，就继续找匹配的元素否则判断再环 if(Row_head->triple.col>Col_head->triple.row) Col_head=Col_head->down; else if(Row_head->right=Locate(i) Col_head=Col_head->down;/假如b矩阵该列元素比a矩阵该行元素 else Row_head=Row_head->right; /则b中该列元素已经无法找到能

10、相乘元素则往下推直至跳出循环 if(Col_head->down!=b.Locate(j)|Col_head->triple.row=Row_head->triple.col) value+=Row_head->triple.value*Col_head->triple.value;if(value!=0) C.Insert(i,j,value) return C; else Matrix C; cerr<<"输入的两个矩阵不符规则，不能相乘！"<<endl; return C; 2.3测试用例3调试分析3.1调试过程（

11、1）编译时程序中没有语法错误，但是格式及语句的书写错误叫多，按照编译错误提示一次改正错误，直至编译正确。（2）运行程序。以三元组的形式，即输入矩阵的行数、列数、非零元素个数和各非零元素的行、列、值，输入两个稀疏矩阵，输出了两个矩阵及它们的乘积。（3）问题：输出的矩阵不符合要求，形成的阵列中只有非零元素，零元素都没有输出。说明友元输入函数有问题，将元函数改为下面的函数后能正确输出矩阵阵列。ostream &operator<<(ostream &out,Matrix &b) /输出函数 node *x; for(int i=1;i<=b.temp;i+)

12、 /先确定各行头结点的位置再遍历各行，以输出所有非零元 x=b.Locate(i); x=x->right; for(int j=1;j<=b.temp;j+) if(x->head=false&&(x->triple.col=j) cout.width(4); out<<x->triple.value; x=x->right; else if(x->head=true) for(j;j<=b.temp;j+)cout.width(4);cout<<"0"break; elsecout.

13、width(4);cout<<"0" cout<<endl; return out;3.2设计分析（1）此程序中乘法算法的时间复杂度为O（Rows*Cols)。（2）此程序没有将类做成模版，导致只能输入floate型的值。 改进方案：将所有的类做成模版，将其属下的floate类型的全改为模版类型参数<T>。（3） 此程序显的很繁锁，算法比较复杂（4） 此程序只有稀疏矩阵的乘法，可以加入其他的矩阵运算来完善运算，也可以再主程序中设计选择菜单，实现多种运算。（5） 改进算法：重新考虑算法，看是否可用数组加指针的方式实现，用数组可以简化找头指针

14、的繁琐过程，简化循环的过程提高程序运行效率！4经验与体会 我的题目是实现三元组，十字链表下乘法，运算。看到这个题目的时候，我一片茫然，因为我们数据结构这一部分并没有讲，我根本就不知道十字链表是什么。于是我赶紧看书，可是书上对十字链表的将就知识一笔带过，更不要指望在书上找到相关代码了。于是我先学习了三元组数组的乘法算法，在这个基础上，我在网上收集各种资料收集和算法。然后不断调试，不断改进程序，最终正确结果终于运行出来了。我觉得自己的数据结构学得不好，但是数据结构可以说是计算机里一门基础课程，对于以后的学习尤为重要。所以我们一定要把基础学扎实，这次的课内实践帮我重新巩固基础知识，也学了很多新知识，

15、提高了我的专业的动手实践能力，也提高了我的对数据结构的学习兴趣。此次课程设计过程中，我真正的体验到，拿到一个问题，应该先分析，将其的属性，功能分析清楚后，再进行细化，考虑其实现的具体的、有效的算法，有了整体的结构框架后再上机！以前只要拿到题就直接打开电脑，想到什么就写什么，没整体思考，对小程序可以，大程序就会彻底崩溃。编程实质就是问题的分析及其实现的算法，这两方面解决了上机编程才会得心应手，剩下的就是按算法些代码了！确定一个好算法很难，一个人往往陷入死循环，思路受局限，找人讨论很必要，编程时团队意识很重要，这不是一个人就能搞定的。在实践的过程中我每天完成一小部分。尽量减少操作的盲目性，提高我们

16、学习的效率。有个总体的大纲来逐步实现。我也曾经犯过这种错误。每个函数都做出来部分，结果都没做完。所以我们要养成有良好的时间规划的习惯，只有一步一步的进行，我们才能完成得更好。同时在实验中我们要培养自己独立的思考能力和解决问题的能力，不能太过依赖于同学和网络，我们应该要有自己的想法，培养自己的编程思维。实践能力对我们今后的发展也是至关重要的，我们只有拥有很好地实践能力，才有机会再编程这个领域有所发展。子啊编程的过程中，我们应该积极的朝着更好地一面发展不断的完善程序，不能马马虎虎随便应付一下。 就像古人云，纸上得来终觉浅，得知此事要躬行。为了以后的计算机道路，我们应该不断的提高自身的专业素养。5附

17、录5.1程序#include<iostream.h>#include<stdlib.h>struct element int row,col;float value;class Matrix;class node / 矩阵节点类的定义friend class Matrix;public:node():head(true) right=down=this; /建立附加头结点node(element *t) / 建立非零元素结点triple.col=t->col;triple.row=t->row;triple.value=t->value;right=d

18、own=this;head=false;node*down,*right;/行列链表指针bool head;union element triple;node*next; /无名联合;class Matrix/稀疏矩阵的类定义friend istream&operator>>(istream&,Matrix&); friend ostream&operator<<(ostream&,Matrix&);private:int Row,Col,Terms,temp; /矩阵的总行数，总列数，和非零元素个数和临时变量；node*

19、headnode; /稀疏矩阵的总表头public:Matrix(int m,int n); /重载构造函数Matrix(); /对矩阵进行构造Matrix(Matrix& T); /拷贝构造函数Matrix()makeEmpty(); /析构函数void Init(int m,int n); /初始化函数，又来初始化无参构造函数构造的矩阵void makeEmpty(); /清空矩阵void Insert(int m,int n,float p); /插入矩阵元素node *Locate(int i); /定位附加头结点Matrix Mul(Matrix b); /两个矩阵相乘Mat

20、rix &operator=(Matrix &T); /重载赋值号;Matrix:Matrix(int m,int n):Row(m),Col(n) /重载构造函数的实现element x;x.row=m;x.col=n;x.value=0;Terms=0;temp=m>=n?m:n;node *current;headnode=new node(&x);current=headnode->right=new node();for(int i=1;i<temp;i+)current->next=new node();current=current

21、->next;Matrix:Matrix():Row(0),Col(0),Terms(0) /构造函数的实现element x;x.row=Row;x.col=Col;x.value=0;Matrix:Matrix(Matrix&T) /复制构造函数的实现Init(T.Row,T.Col);node*current;for(int i=1;i<=temp;i+)current=T.Locate(i); /定位行while(current->right!=T.Locate(i) /通过行遍历逐个赋值current=current->right; Insert(cu

22、rrent->triple.row,current->triple.col,current->triple.value);void Matrix:Init(int m,int n) /矩阵初始化函数的实现Row=m;Col=n;Terms=0;element x;x.row=m;x.col=n;x.value=0;headnode=new node(&x);node *current; if(m>0&&n>0)temp=m>=n?m:n;current=new node();headnode->right=current; fo

23、r(int i=1;i<temp;i+)current->next=new node(); current=current->next;elsecout<<"矩阵初始化错误！"<<endl;node* Matrix:Locate(int i)/定位附加头结点实现node *current;current=headnode->right;for(int k=1;k<i;k+)current=current->next;return current;void Matrix:Insert(int m,int n,floa

24、t p)/插入函数的实现element x;x.row=m;x.col=n;x.value=p;if(m<=this->Row&&n<=this->Col)node *Newnode=new node(&x),*current,*head;head=Locate(m);/先定位行的位置再寻找列插入current=head->right;if(current=head)current->right=Newnode;Newnode->right=current;elsewhile(current->triple.col<

25、n&&current->right!=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;elsewhile(current->triple.row<m&&current-&

26、gt;down!=head)current=current->down;Newnode->down=current->down;current->down=Newnode;Terms+; /完成插入elsecout<<"输入的结点位置超出了范围，请重新输入！"<<endl;istream &operator>>(istream &in,Matrix &b) /输入函数重载的实现int M,N,m,n,T;float p;cout<<"请输入矩阵的行列和非零元素个数：&q

27、uot;<<endl;in>>M>>N>>T;b.Init(M,N);if(T>(M*N)cerr<<"输入的元素个数超过范围"<<endl;exit(1);elsecout<<"请输入各非零元素的行数列数和值"<<endl;cout<<"行数 列数 值"<<endl;for(int i=1;i<=T;i+) /输入元素结点并且插入矩阵cout<<""<<i&l

28、t;<":"in>>m>>n>>p;b.Insert(m,n,p); /插入结点return in;ostream &operator<<(ostream &out,Matrix &b) /输出函数重载node *x;for(int i=1;i<=b.Row;i+) /先确定各行头结点的位置再遍历各行，以输出所有非零元x=b.Locate(i);x=x->right;for(int j=1;j<=b.Col;j+) if(x->head=false&&(x-

29、>triple.col=j)cout.width(4);out<<x->triple.value;x=x->right;else if(x->head=true)for(j;j<=b.Col;j+)cout.width(4);cout<<"0"break;elsecout.width(4);cout<<"0"cout<<endl;return out;Matrix & Matrix:operator =(Matrix &T) /重载赋值号函数的实现this-&g

30、t;Row=T.Row;this->Col=T.Col;node *current;for(int i=1;i<=temp;i+)current=T.Locate(i);while(current->right!=current)current=current->right; /通过行遍历逐个赋值this->Insert(current->triple.row,current->triple.col,current->triple.value);return *this;void Matrix:makeEmpty() /清空矩阵的实现node*d

31、el,*current;for(int i=1;i<=temp;i+)current=Locate(i); /找到列的附加头结点while(current->down!=Locate(i)del=current->down; /通过列的附加头结点向下删除结点current->down=del->down;delete del;Matrix Matrix:Mul( Matrix b) /矩阵乘法的实现if(this->Col=b.Row)Matrix C(this->Row,b.Col); /以A矩阵的行和b矩阵的列为行列建立稀疏矩阵float value;node *Row_head,*Col_head; /设两个指针，一个充当行头指针，一个为列指针 for(int i=1;i<=temp;i+) /先确定行，再求出C矩阵在该行各列的元素for(int j=1;j<=temp;j+) /通过确定列头指针来实现遍历相乘value=0;Row_head=Locate(i); Col_head=b.Locate(j);while(Row_head->right!=Locate(i) /假如行中还有元素不为零就找与之匹配的元素相乘Row_head=Row_head->rig