第5章 数组和广义表.ppt

1、第5章 数组和广义表,5.1 数组的定义和运算 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储 5.4 广义表,5.1 数组的定义和运算,图5.1 Amn的二维数组,数组是一组有固定个数的元素的集合。对于数组的操作一般只有两类： (1) 获得特定位置的元素值； (2) 修改特定位置的元素值。,ADT Array 数据对象： ji=0,bi-1,i=1,2,n, D=aj1j2jn| n(0)称为数组的维数，bi是数组第i 维的长度， ji是数组元素的第i维的下标， aj1j2jn ElemSet 数据关系： R=R1,R2,Rn Ri=| 0jk bk-1, 1 k n 且k i 0

2、 ji bi-2, aj1jijn , aj1ji+1jn D，i=2，n,基本操作： （1） InitArray(Array ,/构造一个空的3X4X5的三维数组 InitArray(A,3,3,4,5);,5.3 特殊矩阵的压缩存储,一般矩阵：,用二维数组保存,5.3 特殊矩阵的压缩存储,假若值相同的元素或者零元素在矩阵中的分布有一定规律，则此类矩阵被称为特殊矩阵；反之，称为稀疏矩阵。,5.3.1对称矩阵,对称矩阵的特点是：在一个n阶方阵中，有aij=aji ，其中1i , jn,只需存储上三角或下三角部分即可,A=,如何只存储下三角部分呢？,A=,问题：在下三角中共有多少个元素？,存储到

3、一维数组san(n+1)/2中,n(n+1)/2个,k与i、j的对应关系,设将矩阵元素aij存到sak中 其中（1i , jn且ji） （kn (n+1)/2）,对应关系为： k=i(i-1)/2+j-1 (kn (n+1)/2 ),问题：如何找到i,j和k的对应关系？,思考问题：如何存储对称矩阵的上三角？,5.3.2稀疏矩阵,假设在mXn的矩阵中，有t个元素不为零。t/(mXn) 称为矩阵的稀疏因子。通常认为稀疏因子 0.05时称为稀疏矩阵。,1. 稀疏矩阵的三元组表表示法,该非零元素的 行下标,该非零元素的列下标,该非零元素的值,矩阵M的三元组表,i,j,e,矩阵T的三元组表,i,j,e,

4、T76,三元组表的类型说明如下：,define MAXSIZE 12500 /*非零元素的个数最多为12500*/ typedef struct int i, j; /该非零元素的行下标和列下标 ElemType e；/该非零元素的值 Triple; typedef struct Triple dataMAXSIZE+1; /非零元素的三元组表，data0未用 int mu, nu, tu; /矩阵的行数、 列数和非零元素的个数 TSMatrix；,1) 用三元组表实现稀疏矩阵的转置运算,所谓的矩阵转置，是指变换元素的位置，把位于（i，j）位置上的元素换到（j，i）位置上，也就是说， 把元素的

5、行列互换。如前边所示的67矩阵M，它的转置矩阵就是76的矩阵T，并且M(i，j) = T(j，i)，其中，1i6 ，1j7。,T76,矩阵M的转置矩阵为T,void TransMatrix（ElemType Mmunu, ElemType Tnumu） /M和T分别为被转置的矩阵和转置以后的矩阵(用二维数组表示) int row, col; for(col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow=Mrowcol; ,采用矩阵的正常存储方式时， 实现矩阵转置的经典算法如下：, 矩阵M三元组表中元素的行、 列互换就可以得到矩阵T三元组表

6、中的元素， 如图所示。,(i, j, e) (j, i, e) M.data T.data, 为了保证转置后的矩阵的三元组表T.data也是以“行序为主序”进行存放，则需要对行、列互换后的三元组表T.data按行下标（即M.data的列下标）大小重新排序，,i,j,i,j,如何使T.data中的三元组是以T的行（M的列）为主序依次排列呢？,两种处理方法： （1）按照T.data中三元组的次序依次在M.data中找到相应的三元组进行转置。 （2）按照M.data中三元组的次序进行转置，并将转置后的三元组置入T.data中恰当的位置。,方法1,按照T.data中三元组的次序依次在M.data中找到

7、相应的三元组进行转置。 算法思路： M的行、列转化成T的列、行； 在M.data中依次找第一列的、第二列的、直到最后一列，并将找到的每个三元组的行、列交换后顺序存储到T.data中即可。,我们附设一个位置计数器q，用于指向当前转置后元素应放入三元组表T.data中的位置。 处理完一个元素后，q加1， q的初值为1。,Status TransposeTSMatrix(TSMatrix M, TSMatrix ,for(col=1; col=M.nu; +col) for(p=1; p=M.tu; +p) if(M.datap.j=col) T.dataq.i=M.datap.j T.dataq.

8、j=M.datap.i; T.dataq.e=M.datap.e; +q; return OK; /TransposeSMatrix,算法的时间耗费主要是在双重循环中，其时间复杂度为 O(M.nuM.tu), 最坏情况下，当M.tu和M.muM.nu同数量级时，时间复杂度为O(M.muM.nu2)。采用正常方式实现矩阵转置的算法时间复杂度为O(M.muM.nu)。可见，上述算法仅使用与tumu nu 的情况。,算法要从M的三元组表中寻找第一列、第二列、，要反复搜索M.data表，若能直接确定M中每一三元组在T中的位置，则对M的三元组表扫描一次即可。,上述算法效率低的原因是,方法2 按照M.da

9、ta中三元组的次序进行转置，并将转置后的三元组置入T中恰当的位置。这种转置算法称为快速转置算法。,为了能将待转置三元组表M.data中元素一次定位到三元组表T.data的正确位置上，需要预先计算以下数据： (1) 待转置矩阵M每一列中非零元素的个数（即转置后矩阵T每一行中非零元素的个数）。 (2) 待转置矩阵M每一列中第一个非零元素在三元组表T.data中的正确位置（即转置后矩阵T每一行中第一个非零元素在三元组T.data中的正确位置）。,为此， 需要设两个数组num和cpot，其中numcol表示矩阵M中第col列中非零元素个数，cpotcol指示M中第col列的第一个非零元素在T.data

10、中的正确位置。显然有 numcol的计算方法： 将三元组表M.data扫描一遍，对于其中列号为k的元素，给相应的numk加1。 cpotcol的计算方法： cpot1=1， cpotcol=cpotcol-1+numcol-1， 其中2colM.nu。,矩阵M的numcol和cpotcol的值,矩阵M的三元组表,i,j,e,具体算法如下：,Status FastTransposeSMatrix (TSMatrix M, TSMatrix if(T.tu) ,for(col=1; col=M.nu; +col) numcol=0; for(t=1; t=M.tu; +t) + numM.data

11、t.j; cpot1=1; for(col=2; colM.nu; +col) cpotcol=cpotcol-1+numcol-1; for(p=1; pM.tu; +p) col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e cpotcol+; /for /if return ok; /,快速转置算法效率,快速转置算法的时间主要耗费在四个并列的单循环上，这四个并列的单循环分别执行了M.nu和M.tu次，因而总的时间复杂度为O(M.nu+M.tu)。 当待转置矩阵M中非零

12、元素个数tu接近于munu 时，其时间复杂度接近于经典算法的时间复杂度O(munu)。 快速转置算法在空间耗费上除了三元组表所占用的空间外，还需要两个辅助向量空间，即num1.M.nu， cpot1.M.nu。可见，算法在时间上的节省，是以更多的存储空间为代价的。,2)行逻辑链接的顺序表,typedef struct Triple dataMAXSIZE+1; / 非零元素的三元组表 / int rposMAXRC+1; /各行第一个非零元的位置表 int mu, nu, tu; /矩阵的行数、 列数和非零元素的个数 RLSMatrix；,矩阵相乘,设矩阵M是m1n1矩阵，N是m2n2矩阵；

13、当n1=m2时可以相乘，得到结果矩阵Q=MN（一个m1n2的矩阵）。 数学中矩阵Q中的元素的计算方法如下：,其中： 1im1, 1jn2。,根据数学上矩阵相乘的原理， 我们可以得到矩阵相乘的经典算法： for(i=1; i=m1; i+) for(j=1; j=n2; j+) Qij=0; for(k=1; k=n1; k+) Qij=Qij+Mik*Nkj; ,下图给出了一个矩阵相乘的例子。当矩阵M、N是稀疏矩阵时，我们可以采用三元组表的表示形式来实现矩阵的相乘。,Q=MN,矩阵M、N、Q的三元组表,M.rpos,N.rpos,如何从M和N求得Q呢？,其中： 1im1, 1jn2。,（1）乘

14、积矩阵Q中元素,(2)稀疏矩阵相乘的基本操作是：对于M.datap(p=1,2,M.tu),找到N中所有满足条件M.datap.j=N.dataq.i的元素N.dataq，求得M.datap.e和N.dataq.e的乘积，又乘积矩阵Q中每个元素的值是个累计和，这个乘积M.datap.e N.dataq.e只是Qij的一部分。为便于操作，应对每个元素设一累计和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。,(3)两个稀疏矩阵相乘的乘积不一定是稀疏矩阵。反之， 中每个分量值M(i,k)xN(k,j)不为零，其累加值Qij也可能为零。因此乘积矩阵Q中的元素是否

15、为非零元，只有在求得其累加和后才能得知。由于Q中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对Q进行逐行处理，先求得累计求和的中间结果（Q的一行），然后再压缩存储到Q.data中去。,具体算法如下： Status MulSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix /Q初始化 if(M.tu*N.tu!=0) ,for(arow=1; arow=M.mu; arow+) /* 逐行处理M */ ctemp=0 ; /* 当前行各元素的累加器清零*/ Q.rposarow=Q.tu+1; if(arowM.mu) tp=M.

16、rposarow+1; else tp=M.tu+1; for(p=M.rposarow; ptp; p+)/对当前行中每一个非零元 brow=M.datap.j; /找到对应元在N中的行号 if(browN.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow; qt; q+) ,ccol=N.dataq.j; /* 乘积元素在Q中列号 */ ctempccol+=M.datap.e*N.dataq.e; /* for q */ /* 求得Q中第crow行的非零元素 */ for(ccol=1; ccolMAXSIZE) return ERR

17、OR; Q.dataQ.tu=(arow, ccol, ctempccol); /* if */ /* for arow */ /*if*/ returnOK; /MultSMatrix,算法的时间性能,上述算法的时间性能如下：（1）求ctemp时间复杂度为O(M.mu*N.nu)；（2）求Q的所有非零元素的时间复杂度为O(M.tu*N.tu/N.mu)；（3）压缩存储时间复杂度为O(M.mu*N.nu)；所以总的时间复杂度为O(M.mu*N.nu+M.tu*N.tu/N.mu)。,2. 稀疏矩阵的链式存储结构: 十字链表,三元组表可以看作稀疏矩阵顺序存储，但是在做一些操作（如加法）时，非零项

18、数目及非零元素的位置会发生变化，这时这种表示就十分不便。在这节中，我们介绍稀疏矩阵的一种链式存储结构十字链表。,如图是一个稀疏矩阵的十字链表,A.chead,A.rhead,A=,在十字链表中，矩阵的每一个非零元素用一个结点表示， 该结点除了（i，j，e）以外，还要有以下两个链域： right： 用于链接同一行中的下一个非零元素； down： 用于链接同一列中的下一个非零元素。,十字链表的结构类型说明如下：,typedef struct OLNode int i, j; /* 非零元素的行和列下标 */ ElemType e; struct OLNode * right, *down; /*

19、非零元素所在行表、列表的后继链域 */ OLNode; *OLink; typedef struct OLink * rhead, *chead; /* 行、 列链表的头指针向量 */ int mu, nu, tu; /* 稀疏矩阵的行数、 列数、 非零元素的个数 */ CrossList;,两个十字链表表示的稀疏矩阵的加法,A.chead,A.rhead,A=,B.chead,B.rhead,B=,执行A=A+B后,A.chead,A.rhead,A=,两个十字链表表示的稀疏矩阵的加法,已知两个稀疏矩阵A和B，分别采用十字链表存储，计算C=A+B，C也采用十字链表方式存储，并且在A的基础上形

20、成C。,分析：C中的非零元素cij只可能有种情况：或者是aij+bij，或者是aij(bij=0)，或者是bij(aij=0)，因此当B加到A上时，对A十字链表的当前结点来说，对应下列四种情况：或者改变结点的值（aij+bij），或者不变（bij），或者插入一个新结点（aij），还可能是删除一个结点（aij+bij）。整个运算从矩阵的第一行起逐行进行。对每一行都从行表的头结点出发，分别找到A和B在该行中的第一个非零元素结点后开始比较，然后按种不同情况分别处理。,算法思想,设pa和pb分别指向A和B的十字链表中行号相同的两个结点，种情况如下： (1) pa=NULL或pa-j pb-j，则需要在

21、矩阵A的十字链表中插入一个pb所指结点。此时，需改变同一行中前一结点的right域值以及同一列中前一结点的down域值。 (2) 若pa-j j，则只需要将pa指针向右推进一步，并继续进行比较。 (3) 若pa-j=pb-j且pa-e+pb-e0，则只要用aij+bij的值改写pa所指结点的值域即可。 (4) 若pa-j=pb-j且pa-e+pb-e=0，则需要在矩阵A的十字链表中删除pa所指结点，此时需改变该行链表中前趋结点的right域值，以及该列链表中前趋结点的down域值。,两个矩阵相加的算法描述,(1) 初始令pa和pb分别指向A和B的第一行的第一个非零元素的结点，即paA.rhea

22、d1; pbB.rhead1; pre = NULL;且令hl初始化 for (j=1; j=A.nu; +j) hljA.cheadj;(2) 重复本步骤，依次处理本行结点，直到B的本行中无非零元素的结点，即pb=NULL为止：, 若pa=NULL或pa-jpb-j（即A的这一行中非零元素已处理完），则需在A中插入一个pb所指结点的复制结点。假设新结点的地址为p，则A的行表中的指针作如下变化：if (pre = NULL) A.rheadp-i=p;else pre-rightp; p-rightpa; pre = p;A的列链表中的指针也要作相应的改变。首先需从hlp-j开始找到新结点在同

23、一列中的前驱结点，并让hlp-j指向它，然后在列链表中插入新结点：if (!A.cheadp-j |A.cheadp-j-ip-i) p-down=A.cheadp-j ; A.cheadp-j=p ; else p-downhlp-j-down; hlp-j-downp; hlp-j = p;, 若pa!=NULL且pa-jj，则令pa指向本行下一个非零元结点，即 prepa; papa-right; 若pa-j = pb-j，则将B中当前结点的值加到A中当前结点上，即pa-epb-e;此时若pa-e!=0，则指针不变，否则删除A中该结点，即行表中指针变为：if (pre = NULL) A

24、.rheadpa-i = pa-right;else pre-rightpa-right; p=pa; pa=pa-right; 同时，为了改变列表中的指针，需要先找到同一列中的前驱结点，且让hlpa-j指向该结点，然后如下修改相应指针：if(A.cheadp-j = p) A.cheadp-j = hlp-j = p-down; else hlp-j-downp-down; free (p);,(3) 若本行不是最后一行，则令pa和pb指向下一行的第一个非零元结点，转(2)；否则结束。,5.4 广 义 表,广义表，是线性表的一种推广。广义表被广泛地应用于人工智能等领域的表处理语言LISP语言

25、中。,5.4.1广义表的定义和基本运算,广义表的定义 例如，中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式： （俄罗斯，巴西，（国家，河北，四川），古巴，美国，（），日本）,广义表（Generalized Lists）是n（n0）个数据元素a1，a2，ai，an的有序序列，一般记作： LS（a1，a2，ai，an） 每个ai（1in）是LS的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表LS的原子和子表。当广义表LS非空时，称第一个元素a1为LS的表头（head），称其余元素组成的表（a2，ai，an）为LS的表尾（tail）。 显然，广义表的定义是递归的,广义表的

26、表示,下面是一些广义表的例子： A （）/空表，它的长度为零 B （e）/B只有一个原子e，B的长度为1 C （a，（b，c，d）/列表C的长度为2 D （A，B，C）/列表D的长度为3，3个元素都是列表。 E （a，E）/这是一个递归的表，它的长度为2。 F （） 非空表，长度为1,广义表的性质,从上述广义表的定义和例子可以得到广义表的下列重要性质： 广义表是一种多层次的数据结构。 广义表可以是递归的表。 广义表可以为其他表所共享。,广义表基本运算,A （） B （e） C （a，（b，c，d） D （A，B，C） E （a，E） F （） GetHead（B） e GetTail（B）（）

27、 GetHead（C） a GetTail（C）（b，c，d） GetHead（D） A GetTail（D）（B，C） GetHead（E） a GetTail（E）（E） GetHead（F）（） GetTail（F）（）,此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、求广义表深度、遍历等。 CreateGList(ls)：根据广义表的书写形式创建一个广义表ls。 GListEmpty(ls)：判定广义表ls是否为空。 GListLength(ls)：求广义表ls的长度。 GListDepth(ls)：求广义表ls的深度。 GetHead(ls)：返回广义表ls的头部。 GetTail(ls)：返回广义表的尾部。 参见教材P107,