资源描述：
《稀疏矩阵相乘.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、武汉理工大学《数据结构》课程设计稀疏矩阵相乘1问题描述1.1稀疏矩阵的三元组及十字链表表示（1)稀疏矩阵及其三元组表示行（row)列（col)值（value)[0]0322[1]0615[2]1111[3]1517[4]23-6[5]3539[6]4039[7]5228稀疏矩阵（2）稀疏矩阵的十字链表表示1.2基本要求（1）以“带行逻辑链接信息”的三元组表示稀疏矩阵；（2）输入矩阵用三元组顺序输入；（2）稀疏矩阵采用十字链表表示；（3）实现两个矩阵相乘的运算，而运算结果的矩阵则以通常的阵列形式列出。15武汉理工大学《数据结构》课程设计2设计思路2.1存储结构设计2.1.1三元组表示稀疏矩阵只
2、存储矩阵中极少的非零元素，采用来唯一地确定每一个非零元素，其中row、col、value分别表示非零元素在矩阵中的的行下标、列下表和值。各数组元素的三元组按在原矩阵中的位置以行优先的顺序依次存放。structtriple{//三元组结构定义introw,col;//非零元素行号,列号Floatvalue;//非零元素的值triple&operator=(triple&x){row=x.row;col=x.col;value=x.value;}};2.1.2十字链表表示稀疏矩阵structelement{introw,col;floatvalue;};classM
3、atrix;classnode{//矩阵节点类的定义friendclassMatrix;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;15武汉理工大学《数据结构》课程设计}node*down,*right;//行列链表指针boolhead;union{elementtriple;node*next;};//无名联合};
4、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();}//析构函数voidIn
5、it(intm,intn);//初始化函数，又来初始化无参构造函数构造的矩阵voidmakeEmpty();//清空矩阵voidInsert(intm,intn,floatp);//插入矩阵元素node*Locate(inti);//定位附加头结点MatrixMul(Matrixb);//两个矩阵相乘Matrix&operator=(Matrix&T);//重载赋值号};在稀疏矩阵的十字链表表示中，矩阵的的每一行设置为一个带附加头结点的循环行链表，每一列也设置为一个带附加头结点的循环列链表。链表中的结点都属于类node的对象，这个类包含一个域head,它用于区分改结点是附加头结点还是链表中的
6、非零元素结点；head=true,表示该结点是附加头结点；head=false,表示该结点是矩阵中的非零元素结点。每一个附加头结点还有三个域：down、right、next。第i个行链表和第i15武汉理工大学《数据结构》课程设计个列链表共用一个附加头结点，在它的right域存放第i行链表最前端的第一个结点的地址，在它的down域存放第i列链表的最前端第一个结点的地址，通过next域链接到第i+1个附加头结点。每一个非零元素结点包含六个域：head,row,col,down,right，value。Down存放列链表指针，right存放行链表指针。整个稀疏矩阵定义为类Matrix的一个对象，*
7、headnode给出整个附加头结点链表的附加头结点的地址。headnextdownrightheadrowcoldownvalueright非零元素结点附加头结点非零元素结点2.2主要算法基于三元组及十字链表的稀疏矩阵乘法MatrixMatrix::Mul(Matrixb)//矩阵乘法的实现{if(this->Col==b.Row){MatrixC(this->Row,b.Col);//以A矩阵的行和b矩阵的
