数据结构第五章2016

1、问题： 寻找两个字符串中的最长公共子串假设 string1=“sgabacbadfgbacst”,string2=“gabadfgab”,则最长公共子串为“badfg”。 算法思想:?第五章第五章 数组和广义表数组和广义表 5.1 数组的定义数组的定义 5.2 数组的顺序表示和实现数组的顺序表示和实现 5.3 矩阵的压缩存储矩阵的压缩存储 5.3.1 特殊矩阵特殊矩阵 5.3.2 稀疏矩阵稀疏矩阵 5.4 广义表的定义广义表的定义 5.5 广义表的存储结构广义表的存储结构 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。 5.1 5.1 数组的定义数组的定义

2、数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组： a11 a12 a1n a21 a22 a2n am1 am2 amn 可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2mn; 等价于： typedef elemtype array1n; typedef

3、array1 array2m; 同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有通过给定的下标存取元素和修改元素值的操作。ADT Array 数据对象数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系：数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n 基本操作：基本操作： ADT Array 二维数组的定义二维数组的定义:数据对象数据对象

4、: : D = aij | 0ib1-1, 0 jb2-1数据关系数据关系:?:? R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2基本操作基本操作：P90 InitArray(&A, n, bound1, ., boundn) DestroyArray(&A) Value(A, &e, index1, ., indexn) Assign(&A, e, index1, ., indexn) Value(A, &e, index1, ., indexn) 初始条件：初始条件：A是n维数组

5、，e为元素变量， 随后是n 个下标值。 操作结果：操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。 Assign(&A, e, index1, ., indexn) 初始条件：初始条件：A是n维数组，e为元素变量， 随后是n 个下标值。 操作结果：操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。5.2 5.2 数组的顺序表示和实现数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作一般不做插入和删除

6、操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。有两种顺序存储方式有两种顺序存储方式：行优先顺序行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,am1,a12,a22,am2,an1,a

7、n2,anm在FORTRAN语言中，数组就是按列优先顺序存储的。 按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用L个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1) n个元素，第i行上aij前面又有j-1个元素，故它前面一共有

8、(i-1) n+j-1个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a11)+(i-1)*n+j-1*L同样，三维数组Amnp中,Aijk按“行优先顺序”存储即为按左(高)下标为主序(或称低下标优先)，其地址计算函数为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+(k-1)*L在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为：称为基地址基地址或基址。二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij) La0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a

9、0,2a1,0a1,1a1,2L推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系LOC(j1, j2, ., jn ) = LOC(0,0,.,0)+（b2 bn j1+ b3 bn j2+bn jn-1+jn)L = LOC(0,0,.,0)+(ji bk+jn)L=LOC(0,0,.,0) + ci ji *其中 cn = L，ci-1 = bi ci , 1 1时，元素aij=0。 上述的各种特殊矩阵，其非零元素的分布都是其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中存储到一个向量中

10、，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行仍能对矩阵的元素进行随机存取随机存取。 5.3.25.3.2随机稀疏矩阵的压缩存储方法随机稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、 十字链表十字链表 如何进行稀疏矩阵的压缩存储？ 在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（位置（i,j)i,j)。反之，一个三元组一个三元组(i,j,a

11、(i,j,aijij) )唯一确定了矩阵唯一确定了矩阵A A的一个非零元的一个非零元。因此，稀疏矩阵可由表示非零元的三元组三元组及其行列行列数唯一确定。一、三元组顺序表顺序表假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元组顺序表。 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型三元组类型typedef struct Triple dataMAXSIZE + 1; /非零元三元组表 int mu, nu, tu; /矩阵的行

12、数、列数和非零元素个数 TSMatrix; / 稀疏矩阵类型稀疏矩阵类型 设A为TSMatrix型的结构变量，P97图5.5中所示的稀疏矩阵的三元组的表示如下： i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 再加上(6,7)行、列值，矩阵就唯一确定。 下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。 一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。如何求转置矩阵如何求转置矩阵？028003600070500140005280000007

13、143600 将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容（见图5.5），那么得到的b.data将是一个按列优先顺序按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。 由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。按这种方法设计的算法，其基本思想是：对A中的每一列 col(0coln-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data

14、中，即可得到B的按行优先按行优先的压缩存储表示。 1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28Void TransposeSMatrix(TSMatrix M,TSMatrix &T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu) q=1; for(col=1;col=M.nu;+col) for(p=1;p=M.tu;+p) if( =col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +

15、q; return OK; M.datap.j分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=1;col=nu;+col) for(row=1;row=mu;+row) Tcolrow=Mrowcol; 其时间复杂度为O(nu*mu)。当非零元素的个数tu和mu*nu同数量级时，算法TransposeSMatrix的时间复杂度为O(mu*nu2)。 三元组顺序表虽然节省了存储空间节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度

16、。因此，此算法仅适用于tu=mu*nu的情况。下面给出另外一种称之为快速转置的算法快速转置的算法，1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩求得矩阵阵M M中的每一列中非零元素的个数中的每一列中非零元素的个数。因为：矩阵M中某列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个向量num和cpot numcol：统计M中每列非零元素的个数 numcol的值可以由A的各列求得。 cp

17、otcol：由递推关系得出M中的第col列第一个非零元素在B中的位置。 算法通过cpot数组建立位置对应关系： cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28 col12345Numpos12011Cpotcol124451 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28pqCol = M.datap.j;q =

18、cpotcol;pqCol = M.datap.j;q = cpotcol; /T中位置中位置T.dataq.i = M.datap.j;T.dataq.j = M.datap.i;T.dataq.e = M.datap.e;+cpotcolStatus FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat

19、.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) 转置矩阵元素 / if return OK; / FastTransposeSMatrix 分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为时间复杂度为: : O(M.nu+M.tu)当非零元素的个数tu和mu*nu同数量级时, 其时间复杂度为：O（mu*nu）。for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col

20、=2; col=M.nu; +col) for (p=1; p=M.tu; +p) 二、行逻辑联接的顺序表二、行逻辑联接的顺序表 三元组顺序表又称有序的双下标法有序的双下标法，它的特点是，非零元在表中按行序按行序有序存储，因此便于便于进行依行顺序处理的矩阵运算进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。 有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表行表来记录稀疏矩来记录稀疏矩阵中每行的非零元素在三元组表中的阵中每行的非零元素在三元组表中的起始位置。起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一

21、种顺序存储结构：带行表的三元组表带行表的三元组表。其类型描述如下：#define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; /各行第一个非零元的位置表 int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型行逻辑链接顺序表类型 例如：给定一组下标(r,k)，求矩阵的元素值 if (M.datap.i=r & M.datap.j=k) return M.datap.e; else return 0; / valueElemType value(RLSMatrix M, i

22、nt r, int k) p = M.rposr; while (M.datap.i=r & M.datap.j k) p+;矩阵乘法的精典算法矩阵乘法的精典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其时间复杂度为其时间复杂度为: O(m1n2n1)下面讨论两个稀疏矩阵相乘的例子，容易看出下面讨论两个稀疏矩阵相乘的例子，容易看出带行表的三元组表带行表的三元组表这种表示方法的优越性。这种表示方法的优越性。当M和N是稀疏矩阵并用三元组表存储结构时，就不

23、能套用上述算法。假设M和N分别为： 3 0 0 50 -1 0 02 0 0 0M= 0 2 1 0-2 4 0 0N=则Q=M*N为： 0 6-1 0 0 4Q= 它们的三元组分别为： 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 2 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data如何从M和N中求得Q？为求Q值，只需对于M.data和N.data中找到相应的各对元素（即M.data中的j值和N.dataN.data中的i i值相等相等的各对元素）相乘积； M.datap.e

24、* N.dataq.e; M.datap.j = N.dataq.i; 乘积矩阵Q中每个元素的值是个累加和，这个乘积只是其中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。 两个稀疏矩阵相乘的乘积不一定是稀疏矩阵，只有在求得其累加和后才能得知。 对Q进行逐行处理，先求得累计求和的中间结果（Q的一行），然后再压缩存储到Q.data中去 Q初始化； if （ Q是非零矩阵） / 逐行求积 for (arow=1; arow=M.mu; +arow) / 处理M的每一行 ctemp = 0

25、; / 累加器清零 计算Q中第arow行的积并存入ctemp 中； 将ctemp 中非零元压缩存储到Q.data； / for arow / if 稀疏矩阵相乘（QMN）的过程大致如下： Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; / Q初始化 if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理M的每

26、一行 / for arow / if return OK; / MultSMatrix ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; if (arow M.mu) tp = M.rposarow+1; else tp = M.tu + 1; for (p=M.rposarow; ptp;+p) /对当前行中每一个非零元对当前行中每一个非零元 brow=M.datap.j; / M中的列号=N中的行号 if (brow N.mu ) t = N.rposbrow+1; else t = N.tu+1 for (q=N.rposbrow; q t; +

27、q) ccol = N.dataq.j; / ccol：乘积元素在Q中列号 ctempccol += M.datap.e * N.dataq.e; / for q / for p求得求得Q中第中第brow( =arow)行的非零元行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if处理 的每一行M某行中非零元素的个数某行中非零元素的个数矩阵乘法算法的时间复杂度时间复杂度：累加器ctemp初始化：(M.muN.nu)，求Q的所有非零元： (M.tuN.tu/N.mu) =M.

28、mu*(M.tu/M.mu)*(N.tu/N.mu),进行压缩存储： (M.muN.nu)，总时间复杂度：(M.muN.nu+M.tuN.tu/N.mu)。若若M是是m行行n列的稀疏矩阵，列的稀疏矩阵，N是是n行行p列的稀疏矩阵列的稀疏矩阵，则则M中非零元个数：中非零元个数：M.tu = Mmn N中非零元个数：中非零元个数：N.tu = Nnp乘法的时间复杂度为：乘法的时间复杂度为： (mp(1+nMN) 如果如果 M0.05 和N0.05及 n right)&(q-right-jright)&(q-right-jright) ; q=q-right) for ( q=M.c

29、headj; for ( q=M.cheadj; (q-down)&(q-down-idown)&(q-down-idown ); q=q-down );寻查在列表中的插入位置，第寻查在列表中的插入位置，第i i行第行第j j列前？列前？总结 1、了解数组的两种存储表示方法（行、列），并掌握以行为主的存储结构中，地址的计算方法。 2、掌握对特殊矩阵进行压缩存储的下标变换公式。 3、了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法 。 5.4 5.4 广义表的定义广义表的定义 广义表（Lists，又称列表）是线性表的推广。 在第

30、2章中，我们把线性表定义为n=0个元素 a1,a2,a3,an的有限序列。线性表的元素仅 限于原子项; 原子是作为结构上不可分割的成分，它可以是一个数或一个结构; 若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。 广义表是n(n=0)个元素a1,a2,a3,an的有限序列，其中ai或者是原子项原子项，或者是一个广义表广义表。通常记作LS=（a1,a2,a3,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。当广义表非空时，称第一个元素第一个元素a1为LS的表头表头（Head），称其余元素组成的表表（ a2,a3,an）是LS的表尾表尾（T

31、ail）。 广义表的类型定义广义表的类型定义ADT Glist 数据对象数据对象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in 基本操作基本操作: ADT Glist 结构的创建和销毁结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);基本操作基本操作 状态函数状态函数 GListLength(L); GListDepth(L);

32、GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍历遍历 Traverse_GL(L, Visit();广义表广义表 LS = ( 1, 2, , n )的结构特点的结构特点:1. 广义表是一个多层次多层次的线性结构线性结构例如：例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( )d( )bce2、广义表中的数据元素有相对次序次序；3、广义表的长度长度定义为最外层包含元素个数；例：例

33、： A = ( ) 空表 ，长度为0 F = (d, (e) 长度为2 D = (a,(b,c), F) 长度为2 C = (A, D, F) 长度为3 B = (a, B) = (a, (a, (a, , ) ) ) 长度为2D=(E, F)4、广义表的深度深度定义为所含括弧的重数； 注意：“原子”如表表A、A=e的深度为 0 ；含原子的列表深度为 1 ；A=(e); “空表”的深度为 1 。A=( )5、广义表可以共享共享；6、广义表可以是一个递归递归的表。 广义表是递归递归定义的线性结构线性结构 递归表的深度是无穷值，长度是有限值递归表的深度是无穷值，长度是有限值。7、 任何一个非空广义

34、表非空广义表 LS = ( 1, 2, , n) 均可分解为 表头表头 Head(LS) = 1 和 表尾表尾 Tail(LS) = ( 2, , n) 两部分。例如例如: D = ( E, F ) = (a, (b, c)，F )Head( D ) = Tail( D ) =Head( E ) = Tail( E ) =Head( ( b, c) ) = Tail( ( b, c) ) =Head( ( b, c) ) = Tail( ( b, c) ) =Head( ( c ) ) = Tail( ( c ) ) =E( F )a( ( b, c) )( b, c)( )b( c )c(

35、)注意: （）和（）不同；前者为空表，后者为含空表的表； 表长=？ 表的深度=？ 后者表头、表尾都为例: 已知广义表LS=(a,b,c),(d,e,f),运用head和tail函数取出Ls中原子e;head(tail(head(tail(LS) n=0n=112（） 表头、表尾分析法：构造存储结构的分析方法:若表头为原子，则为空表 ls=NIL非空表 lstag=1 hp tp 指向表头的指针指向表尾的指针tag=0 atom5.5 广义表的存储结构 广义表的头尾链表存储表示广义表的头尾链表存储表示typedef enumATOM,LISTElemTag;typedef enumATOM,LI

36、STElemTag; / ATOM=0/ ATOM=0：原子：原子,LIST=1,LIST=1：子表：子表Typedef structTypedef struct GLNodeGLNode ElemTag tag;ElemTag tag;/公共部分，用于区分原子结点和表结点公共部分，用于区分原子结点和表结点UnionUnion /原子结点和表结点的联合部分原子结点和表结点的联合部分AtomType atom;AtomType atom;/atom/atom是原子结点的值域，是原子结点的值域，AtomTypeAtomType由用户由用户定义定义Structstruct GLNode Struct

37、struct GLNode * *hp,hp,* *tpptr;tpptr;/ ptr/ ptr是表结点的指针域，是表结点的指针域，ptr.hpptr.hp和和ptr.tpptr.tp分别指向表头和表尾分别指向表头和表尾; * *Glist;Glist;/广义表类型广义表类型enum 枚举名枚举名 联合变量定义 union (联合名联合名) 数据类型数据类型 成员名成员名; 数据类型数据类型 成员名成员名; . (联合变量名联合变量名);/( )中的可省略中的可省略 联合表示几个变量公用一个内存位置, 在不同的时间保存不同的数据类型 和不同长度的变量。 定义: union a_bc int i; char mm; ; union a_bc lgc; 联合既可以出现在结构内, 它的成员也可以是结构。 例如: struct int age; char *job; union int banji