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

会计学1用三元组表示稀疏矩阵的乘法用三元组表示稀疏矩阵的乘法 两个矩阵相乘也是矩阵的一种常用的运算。设矩阵M是m1n1矩阵，N是m2n2矩阵；若可以相乘，则必须满足矩阵M的列数n1与矩阵N的行数m2相等，才能得到结果矩阵Q=MN（一个m1n2的矩阵）。数学中矩阵Q中的元素的计算方法如下：其中：1im1,1jn2。第1页/共27页 根据数学上矩阵相乘的原理，我们可以得到矩阵相乘的经典算法：for(i=1;i=m1;i+)for(j=1;j=n2;j+)Qij=0;for(k=1;km=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_headi=NULL)M-row_headi=p;第15页/共27页else /*寻找行表中的插入位置*/for(q=M-row_headi;q-right&q-right-colright)p-right=q-right;q-right=p;/*完成插入*/if(M-col_headj=NULL)M-col_headj=p;else /*寻找列表中的插入位置*/for(q=M-col-headj;q-down&q-down-rowdown)p-down=q-down;q-down=p;/*完成插入*/第16页/共27页广广 义义 表表 广义表，顾名思义，也是线性表的一种推广。广义表被广泛地应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。第17页/共27页 在第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）称为广义表的表尾。由此可见广义表的定义是递归定义的，因为在定义广义表时又使用了广义表的概念。第18页/共27页 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）。广义表的表尾一定是一个表。第19页/共27页 从上面的例子可以看出：（1）广义表的元素可以是子表，而子表还可以是子表由此可见，广义表是一个多层的结构。（2）广义表可以被其它广义表共享，如广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。（3）广义表具有递归性，如广义表C。第20页/共27页 由于广义表GL=（d1，d2，d3，dn）中的数据元素既可以是单个元素，也可以是子表，因此对于广义表来说，我们难以用顺序存储结构来表示它，通常我们用链式存储结构来表示。表中的每个元素可用一个结点来表示。广义表中有两类结点：一类是单个元素结点；另一类是子表结点。任何一个非空的广义表都可以分解成表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。由此，一个表结点可由三个域构成：标志域、指向表头的指针域和指向表尾的指针域。而元素结点只需要两个域：标志域和值域。第21页/共27页typedef enum ATOM,LIST ElemTag;/*ATOM0，表示原子；LIST1，表示子表*/typedef struct GLNode ElemTag tag;/*标志位tag用来区别原子结点和表结点*/union AtomType atom;/*原子结点的值域atom*/struct struct GLNode *hp,*tp;htp;/*表结点的指针域htp，包括表头指针域hp和表尾指针域tp*/atom_htp;/*atom_htp 是原子结点的值域atom和表结点的指针域htp的联合体域*/*GList；第22页/共27页第23页/共27页图5.25 广义表的另一种结点结构 Tag=1hptpTag=0atomtp表结点 原子结点 第24页/共27页第25页/共27页typedef enum ATOM,LIST ElemTag;/*ATOM0，表示原子；LIST1，表示子表*/typedef struct GLNode ElemTag tag;union AtomType atom;struct GLNode *hp;atom_hp;/*atom-hp 是原子结点的值域atom和表结点的表头指针域hp的联合体域*/struct GLNode *tp;*GList;第26页/共27页