《稀疏矩阵与广义表》由会员分享，可在线阅读，更多相关《稀疏矩阵与广义表（47页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构一、数据结构：（1）定义：数据之间的关系（2）逻辑结构：数据之间的形式上的关系（3）物理结构：数据的存储结构数据采用不同的存储结构，将引起不同的处理方法，即算法也不相同。二、数据结构的描述：1、描述方法：用二元组表示，B=( K, R )其含义是：B是一种数据结构，K表示K个数据元素， R表示元素之间的关系。这里R可以是多个关系，我们主要研究 R1 的关系2、例如：一种数据结构表示如下：LLL（K , R）K= 01, 02 , 03, 04, 05 , 06 ,07 , 08 , 09 ,10 R= r r = , , , , , , 例题2、一种数据结构tree=( K ,
2、R )K= 01, 02 , 03, 04, 05 , 06 ,07 , 08 , 09 ,10 R= r r = , , , , , , , 三、算法的时间复杂性和空间复杂性1、时间复杂性 ：取决于循环次数和循环嵌套层数O(log2n) nil) and ( rr.col then s:=r.next ; q.next:=r ; r.next:=p ;q:=r; r:=s end ;(4) if p=nil then p.next:= r ;End; 矩阵乘法：矩阵乘法 ：A M，N* BN，T = CM，T例如：一般矩阵乘法的运算方法：（1）A、B两矩阵必须满足如下条件：A矩阵的列数与B矩
3、阵的行数相同，即：A K，T， BT，X得到新的矩阵：CK，X（2）乘法方法：将A矩阵的一行的每个元素，对应乘以B 矩阵的每一列的元素，其代数和为当前新矩阵的一个元素 值。（3）程序实现的方法： 建立三个数组 ，其行列个数，根据需要设定 输入两个矩阵，并输出 利用三重循环语句完成矩阵乘法运算。稀疏矩阵的乘法运算：用三元组存储方法，计算两个矩 阵相乘广义表一、广义表1、定义：线性表的推广。广义表是指一个表或者是空表 或是一个非空元素组成的表。其元素可以是某个确定类型 的元素，也可以是子表组成。（a1, a2, a3, B4, a5 , a6 , B7 an) 其中B4、B7分别为一个子表。B4=
4、（b1, b2, b3,bi) , B7=( d1,d2,dj)例如：A=（ ），B=（e）， C=( a, ( b, c, d ) ) D=(A ,B , C )=( ( ), (e), ( a,( b, c, d ) ) )E=(a, (a ,b),(a,b),c ) )注意：广义表通常用圆括号括起来，用逗号分隔其中的元素。 为了区分原子和子表，书写时用大写字母表示广义表的子表，用小写字母表示原子。 若广义表 L 非空(n1)，则al是L的表头，其余元素组成的表(a1，a2，an)称为L的表尾。广义表是递归定义的 2、 广义表常用表示 E=( )E是一个空表，其长度为0。 L=(a，b)L
5、是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表 A=(x，L)=(x，(a，b)A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。 B=(A，y)=(x，(a，b)，y)B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。 C=(A，B)=(x，(a，b)，(x，(a，b)，y)C的长度为2，两个元素都是子表。 D=(a，D)=(a，(a，(a，()D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。 3、 广义表的深度一个表的“深度“是指表展开后所含括号的层数。【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为。
6、4、广义表的结构图：A=（ ），B=（e）， C=( a, ( b, c, d ) ) D=(A ,B , C )=( ( ), (e), ( a,( b, c, d ) ) )树 形 结 构5、广义表的运算： （ p. 80)(1) 计算广义表的长度(2) 广义表的输入和输出(3) 建立广义表6、广义表的应用：(1) 建立广义表(2) 输入广义表，输出广义表二、广义表的存储结构由于广义表中元素及子表中的元素多少不固定，所以一般用动态 链接结构。结点表示 ：A= NIL ， BCTag(0,1) da(或link)Next 0e0a10b0cd0练习：画出下列广义表的链接存储结构A=（a,b,
7、c ) ; B=(a,(b,(c) ; C=(a,b),(c,d) ; D=(a ,(b,(c,d),(e) ； E=(a,(b,( ) ,c),(d) ,e)。三、 广义表类型定义方法及操作：1. 定义：type node=recordtag : 01; 0： 表示元素，1 ：表示子表 next :node;case tag of 0: da:integer ; char 1: link: node ;end;2. 广义表的操作： (1)建立广义表、 输出广义表(2) 求广义表的表头和表尾(3) 计算广义表的深度:所有子表中最大深度加 1例题1：建立广义表的算法元素之间用“，”分开，表元素的
8、开始结束符号用“（）”，空表用（ ）表示。设用“；”号作为表的结束符号。（加一个表头结点）E=(a,( b, ( ) , c), ( d ) , e) ；Procedure creat ( var po: node) ;begin(1) read(ch);(2) case ch of : po = nil ;(: new(po) ;po.tag:=1; creat(po.link); az: new(po); po.tag:=0; po.da:=ch; end ;(3) read(ch);(4) if po nil then write(,);print(p.next) end ; 例题3 求
9、广义表的表头和表尾。表头： head ( ) , 表尾 :tail( )表头是指表中的第一个元素 ，表尾是指除表头以外的元素。任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。例如 ： (1) HEAD(TAIL(HEAD(a,b),(c,d)(2) TAIL(HEAD(TAIL(a,b),(c,d)(3) . 广义表( (A , B, E, F , G)的表尾是( )。A.(B, E , F, G) B.( ) C.（A，B， E，F，G) D. 不存在 (4) . 广义表（ ( ( ) ，( ) ) , (a , b, c) , (e , d)）的表
10、头是( )， 表尾是( )。 A.(e , d ) B.( ( ) ) C.( ( ) , ( ) ) D.（(a , b , c ）, ( e , d) )(5) 对广义表( (a),(b) )进行下面的操作head(head(a),(b) 后的结果是( )。A.a B.(a) C.( ) D.不确定(6) 广义表(A,B,E,F,G)的表尾是( )。 A.(B, E , F, G) B.( ) C.（A，B， E，F，G) D. （G）(7) 利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：(1) L1(apple, pear, ban
11、ana, orange)(2) L2(apple, pear), (banana, orange)(3) L3(apple), (pear), (banana), (orange)(4) L4(apple), (pear), (banana), orange)(5) L5(apple), pear), banana), orange)(6) L6(apple, (pear, (banana), orange) 例题3 计算广义表的深度 。分析：（1）建立广义表，并输出广义表 （2）广义表的深度递归定义：所有子表中表的最大深 度加 1 ，整个表为深度 1 ，其形式如下：depth = max+1
12、 设p 是指针类型，开始时指向一个广义表的第一个结点，则求其深度的算法用递归方法是：function depth ( _p ):integer ;begin (1) max:=0 ;(2) while p max then max := dep ; p:=p.next ; end;(3) depth:= max+1 ;end ;设一个广义表为： T=( ( ), a ,( (b,c) ,d ) )它的存储结构如图 ： （为了说明递归过程，加数字，表明执行过程。 参考P.81 递归过程图。四、练习：（1）p82第六、第七（2）、第十一、第十二（2）输入两个矩阵（稀疏），将它们相加（3）输入两个矩阵（稀疏、一般），求两个矩阵的积。C=AB（4）编写一个函数计算一个广义表的原子结点个数。例如 一个广义表为(a,(b,c),(e),其原子结点个数为4。（5）已知广义表A=(a,b,c),(d,e,f),从中取出原子e的运算是 _.A tail(head(A) B head(tail(A)C head(tail(tail(head(A) D head(head(tail(tail(A) 1.四、练习：2.（1）p82第六、第七、第八、第十、第十一
