用三元组表示稀疏矩阵的乘法

用三元组表示稀疏矩阵的乘法第1页，课件共26页，创作于2023年2月两个矩阵相乘也是矩阵的一种常用的运算。设矩阵M是m1×n1矩阵，N是m2×n2矩阵；若可以相乘，则必须满足矩阵M的列数n1与矩阵N的行数m2相等，才能得到结果矩阵Q=M×N（一个m1×n2的矩阵）。数学中矩阵Q中的元素的计算方法如下：其中：1≤i≤m1,1≤j≤n2。第2页，课件共26页，创作于2023年2月根据数学上矩阵相乘的原理，我们可以得到矩阵相乘的经典算法：for(i=1;i<=m1;i++)for(j=1;j<=n2;j++){Q［i］［j］=0;for(k=1;k<=n1;k++)Q［i］［j］=Q［i］［j］+M［i］［k］*N［k］[j］;}第3页，课件共26页，创作于2023年2月图5.17Q=M×N图5.17给出了一个矩阵相乘的例子。当矩阵M、N是稀疏矩阵时，我们可以采用三元组表的表示形式来实现矩阵的相乘。第4页，课件共26页，创作于2023年2月图5.18矩阵M、N、Q的三元组表第5页，课件共26页，创作于2023年2月经典算法中，不论M［i］［k］、N［k］［j］是否为零，都要进行一次乘法运算，而实际上，这是没有必要的。采用三元组表的方法来实现时，因为三元组只对矩阵的非零元素做存储所以可以采用固定三元组表a中的元素（i，k，Mik）（1≤i≤m1，1≤k≤n1），在三元组表b中找所有行号为k的的对应元素（k，j，Nkj）（1≤k≤m2，1≤j≤n2）进行相乘、累加，从而得到Q［i］［j］，即以三元组表a中的元素为基准，依次求出其与三元组表b的有效乘积。第6页，课件共26页，创作于2023年2月算法中附设两个向量num［］、first［］，其中num［row］表示三元组表b中第row行非零元素个数（1≤row≤m2），first［row］表示三元组表b中第row行第一个非零元素所在的位置。显然，first［row+1］-1指向三元组表b中第row行最后一个非零元素的位置。first［1］=1；first［row］=first［row-1］+num［row-1］，2≤row≤m2+1。这里，first［m2+1］-1表示最后一行最后一个非零元素的存储位置。当三元组表a中第i行非零元素的列号等于三元组表b中非零元素的行号时，则元素相乘并将结果累加。第7页，课件共26页，创作于2023年2月图5.19Q=M×N第8页，课件共26页，创作于2023年2月图5.20图5.19中矩阵N对应的向量num［row］,first［row］Row1234(5)Num[row]2111First[row]13456第9页，课件共26页，创作于2023年2月＃defineMAXSIZE1000/*非零元素的个数最多为1000*/＃defineMAXROW1000/*矩阵最大行数为1000*/typedefstruct{introw,col;/*该非零元素的行下标和列下标*/ElementTypee；/*该非零元素的值*/}Triple;typedefstruct{Tripledata［MAXSIZE+1］;/*非零元素的三元组表，data［0］未用*/intfirst［MAXROW+1］;/*三元组表中各行第一个非零元素所在的位置*/intm,n,len;/*矩阵的行数、列数和非零元素的个数*/}TriSparMatrix；第10页，课件共26页，创作于2023年2月具体算法如下：该算法的时间主要耗费在乘法运算及累加上，其时间复杂度为O（A.len×B.n）。当A.len接近于A.m×A.n时，该算法时间复杂度接近于经典算法的时间复杂度O（A.m×A.n×B.n）。

第11页，课件共26页，创作于2023年2月稀疏矩阵的链式存储结构:十字链表与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵不仅节约了空间，而且使得矩阵某些运算的运算时间比经典算法还少。但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如A=A+B，将矩阵B加到矩阵A上，此时若还用三元组表表示法，势必会为了保持三元组表“以行序为主序”而大量移动元素。第12页，课件共26页，创作于2023年2月在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row，col，value）以外，还要有以下两个链域：right：用于链接同一行中的下一个非零元素；down：用于链接同一列中的下一个非零元素。rowcolValueDownright第13页，课件共26页，创作于2023年2月图5.23十字链表的结构第14页，课件共26页，创作于2023年2月十字链表的结构类型说明如下：typedefstructOLNode{introw,col;/*非零元素的行和列下标*/ElementTypevalue;structOLNode*right,*down;/*非零元素所在行表、列表的后继链域*/}OLNode;*OLink;typedefstruct{OLink*row_head,*col_head;/*行、列链表的头指针向量*/intm,n,len;/*稀疏矩阵的行数、列数、非零元素的个数*/}CrossList;第15页，课件共26页，创作于2023年2月CreateCrossList(CrossList*M){/*采用十字链表存储结构，创建稀疏矩阵M*/scanf(&m,&n,&t);/*输入M的行数,列数和非零元素的个数*/M->m=m;M->n=n;M->len=t;If(!(M->row_head=(OLink*)malloc((m+1)sizeof(OLink))))exit(OVERFLOW);If(!(M->col_head=(OLink*)malloc((n+1)sizeof(OLink))))exit(OVERFLOW);M->row_head［］=M->col_head［］=NULL;/*初始化行、列头指针向量，各行、列链表为空的链表*/for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;/*生成结点*/if(M->row_head［i］==NULL)M->row_head［i］=p;第16页，课件共26页，创作于2023年2月else{/*寻找行表中的插入位置*/for(q=M->row_head［i］;q->right&&q->right->col<j;q=q->right)p->right=q->right;q->right=p;/*完成插入*/}if(M->col_head［j］==NULL)M->col_head［j］=p;else{/*寻找列表中的插入位置*/for(q=M->col-head［j］;q->down&&q->down->row<i;q=q->down)p->down=q->down;q->down=p;/*完成插入*/}}}第17页，课件共26页，创作于2023年2月广义表广义表，顾名思义，也是线性表的一种推广。广义表被广泛地应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP语言的程序也表示为一系列的广义表。第18页，课件共26页，创作于2023年2月在第2章中，线性表被定义为一个有限的序列（a1，a2，a3，…，an）,其中ai被限定为是单个数据元素。广义表也是n个数据元素（d1，d2，d3，…，dn）的有限序列，但不同的是，广义表中的di既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，…，dn）。GL是广义表的名字，通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表，则称di是广义表GL的子表。在广义表GL中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。由此可见广义表的定义是递归定义的，因为在定义广义表时又使用了广义表的概念。第19页，课件共26页，创作于2023年2月·D=（）空表；其长度为零。·A=（a，（b，c））表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表（b，c）。·B=（A，A，D）长度为3的广义表，其前两个元素为表A，第三个元素为空表D。·C=（a，C）长度为2递归定义的广义表，C相当于无穷表C=（a，（a,（a，（…））））。#其中，A、B、C、D是广义表的名字。下面以广义表A为例，说明求表头、表尾的操作：head（A）=a表A的表头是a。tail（A）=（（b，c））表A的表尾是（（b，c））。广义表的表尾一定是一个表。第20页，课件共26页，创作于2023年2月从上面的例子可以看出：（1）广义表的元素可以是子表，而子表还可以是子表……由此可见，广义表是一个多层的结构。（2）广义表可以被其它广义表共享，如广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。（3）广义表具有递归性，如广义表C。第21页，课件共26页，创作于2023年2月由于广义表GL=（d1，d2，d3，…，dn）中的数据元素既可以是单个元素，也可以是子表，因此对于广义表来说，我们难以用顺序存储结构来表示它，通常我们用链式存储结构来表示。表中的每个元素可用一个结点来表示。广义表中有两类结点：一类是单个元素结点；另一类是子表结点。任何一个非空的广义表都可以分解成表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。由此，一个表结点可由三个域构成：标志域、指向表头的指针域和指向表尾的指针域。而元素结点只需要两个域：标志域和值域。第22页，课件共26页，创作于2023年2月typedefenum{ATOM,LIST}ElemTag;/*ATOM＝0，表示原子；LIST＝1，表示子表*/typedefstructGLNode{ElemTagtag;/*标志位tag用来区别原子结点和表结点*/union{AtomTypeatom;/*原子结点的值域atom*/struct{structGLNode*hp,*tp;}