严蔚敏数据结构教材讲义精选.ppt

当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设M和N分别为： 0 0 5 0 -1 0 0 2 0 0 0 M= 0 2 1 0 -2 4 0 0 N= 则Q=M*N为： 0 6 -1 0 0 4 Q= * 它们的三元组、和分别为： i j v i j v i j v 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data * 稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。 * void multsmatrix( rtripletable a, rtripletable b, rtripletable c){ if(a.n!=b.m){ printf(“error\n”); exit(0); } c.m=a.m; c.n=b.n; c.t=0; if(a.t*b.t!=0){ for(arow=1;arow=a.m;++arow){ ctemp[arow]=0; * c.rpos[arow]=c.t+1; for(p=a.rops[arow];pa.rpos[arow+1];++p){ brow=a.data[p].j; if(browb.t) t=b.rpos[brow+1] else t=b.t+1; for(q=b.rpos[brow]; qt;++q){ ccol=n.data[q].j; ctemp[ccol]+=a.data[p].v*b.data[q].v; } } * for(ccol=1;ccol=c.n;++ccol) if(ctemp[ccol]){ if(++c.tmaxsize) exit(0); c.data[c.t]={arow,ccol,ctemp[ccol]}; } } } } * 5.4 广义表的定义 广义表（Lists，又称列表）是线性表的推广。在第2章中，我们把线性表定义为n=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。 广义表是n(n=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。 * 第六章 树和二叉树 6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 * 通常用圆括号将广义表括起来，用逗号分隔其中的 元素。为了区别原子和广义表，书写时用大写字母 表示广义表，用小写字母表示原子。若广义