数据结构第五章-数组和广义表.ppt

它们的三元组、和分别为：ijeijeije11312212614521121-132-131-2324312324M.dataN.dataQ.data如何从M和N求得Q呢？（1）乘积矩阵Q中的元素为了得到非0的乘积，只要对M.data中的每个元素（i,k,M(i,k)）(1≤i≤m1,1≤k≤n1)，找到N.data中所有相应的元素（k,j,N(k,j)）(1≤k≤m2,1≤j≤n2)相乘即可。矩阵N中第k行的所有非0元都在N.data中。在稀疏矩阵的行逻辑链接的顺序表中，N.rpos[row]指示矩阵N的第row行中第一个非0元在N.data中的序号，则rpos[row+1]-1指示矩阵N的第row行中最后一个非0元在N.data中的序号。（2）对每个元素设一累计和的变量，其初值为0，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。（3）两个稀疏矩阵相乘的乘积不一定是稀疏矩阵。见算法5.33、十字链表0050-1002000M=在十字链表中，每个非0元可用一个含5个域的结点表示。^311^^－122^^541^^213M.cheadM.rhead广义表（Lists，又称列表）是线性表的推广。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。5.4广义表的定义在第2章中，我们把线性表定义为n=0个元素a1,a2,a3,…,an的有限序列。广义表是n(n=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。通常记作LS=（a1,a2,a3,…,an)当广义表LS非空时，称第一个元素a1为LS的表头（head），称其余元素组成的表（a2，…，ai，…，an）为LS的表尾（tail）。为书写清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。下面是一些广义表的例子：A＝（）B＝（e）C＝（a，（b，c，d））D＝（A，B，C）E＝（a，E）F＝（（））从上述广义表的定义和例子可以得到广义表的下列重要性质：⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。⑵广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。⑶广义表可以为其他表所共享。例如，表A、表B、表C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。Head（B）＝eTail（B）＝（）Head（C）＝aTail（C）＝（（b，c，d））Head（D）＝ATail（D）＝（B，C）Head（E）＝aTail（E）＝（E）Head（F）＝（）Tail（F）＝（）由于广义表中的数据元素可以具有不同的结构，因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。在这种表示方式下，每个数据元素可用一个结点表示。5.5广义表的存储按结点形式的不同，广义表的链式存储结构又可以分为不同的两种存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。头尾表示法的结点形式tag=1hpt