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

  1. 1、本文档共240页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
严蔚敏数据结构教材讲义精选

当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 森林与二叉树的转换 * 通常用圆括号将广义表括起来,用逗号分隔其中的 元素。为了区别原子和广义表,书写时用大写字母 表示广义表,用小写字母表示原子。若广义

文档评论(0)

beoes + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档