数据结构讲义PPT学习教案

1、会计学1数据结构讲义数据结构讲义5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构*5.6 m元多项式的表示元多项式的表示*5.7 广义表的递归算法广义表的递归算法目录目录第第 五五 章章 数组和广义表数组和广义表第1页/共66页5.1数组的定义数组的定义 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的。 几乎所有的程序设计语言都把数组类型设定为固有类型。 数组也是我们最熟悉的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上

2、界和下界，因此，数组的处理比其它复杂的结构更为简单。第2页/共66页 以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。ADT Array 数据对象:ji=0,.,bi-1,i=1,2,.,n; D=aj1j2.jn|n(0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2.jn (- ElemSet 数据关系:R=R1, R2,. Rn Ri =| 0=jk=bk-1,1=k=n且ki, 0=ji=bi-2,aj1.ji.jn, aj1.ji+1 jn (- D,i=2,.n第3页/共66页基本操作: InitArray(&A,n,bou

3、nd1,.,boundn) 若维数和各维长度合法,则构造相应的数组A,并返回OK. DestroyArray(&A) 操作结果:销毁数组A. Value(A,&e,index1,.,indexn) 初始条件:A是n维数组,e为元素变量,随后是n个下标值. 操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK. Assign(&A,e,index1,.,indexn) 初始条件:A是n维数组,e为元素变量,随后是n个下标值. 操作结果:若下标不超界,则将e的值赋给 所指定的A的元素,并返回OK.ADT Array第4页/共66页多维数组是一维数组的推广。例如，二维数组： a11 a

4、12 a1n A1 a21 a22 a2n A2 am1 am2 amn AnAmn=见书见书P91页图页图5.1第5页/共66页 所以数组可以看成是由行向量组成的线性表，也可以看成是个列向量组成的线性表。 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2mn; 等价于： typedef elemtype array1n; typedef array1 array2m; 同理，一个N维数组类型可以定义为其数据元素为N-1维数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初

5、始化和销毁之外，数组只有存取元素和修改元素值的操作。第6页/共66页5.2数组的顺序表示和实现数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式：通常有两种顺序存储方式：行优先顺序行优先顺序将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a11,a12,a1n

6、,a21,a22,a2n,am1,am2,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序列优先顺序将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,am1,a12,a22,am2,an1,an2,anm在FORTRAN语言中，数组就是按列优先顺序存储的。第7页/共66页 以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。 按上述两种方式顺序存储的序组，因此，数组中的任一元素可以在相同的时间内存

7、取，即顺序存储的数组是一个随机存取结构。例如例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1) n个元素，第i行上aij前面又有j-1个元素，故它前面一共有(i-1) n+j-1个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a11)+(i-1)*n+j-1*d同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+(k-1)*d第

8、8页/共66页 将上述的式子推广到一般情况，可得到n维数组的数据元素存储位置的计算公式： LOC(j1,j2,jn)=LOC(0,0,0) +( b2 bn j1+b3 bn j2+bn jn-1+jn)L=LOC(0,0,0)+=LOC(0,0,0)+ 上式就称为n维数组的映象函数。容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度,Ci就是常数。 Ljbjninnikki111)(niiijc1第9页/共66页数组的顺序存储表示和实现:#include #define MAX_ARRAY_DIM 8typedef struct ElemType *base; /数组

9、元素基址，由InitArray分配 int dim; /数组维数 int *bounds; /数组维界基址，由InitArray分配 int *constants; /数组映象函数常量基址，由InitArray分配Array;Status InitArray(Array &A,int dim,.);Status DestroyArray(Array &A);Status Value(Array A,ElemType &e,.);Status Assign(Array &A,ElemType e,.);第10页/共66页基本操作的算法描述:Status InitArray(Array &A,in

10、t dim,.) if(dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim *sizeof(int); if(!A.bounds) exit(OVERFLOW); elemtotal=1; va_start(ap,dim); for(i=1;idim;+i) A.boundsi=va_arg(ap,int); if(A.boundsi=0;-i) A.constantsi=A.boundsi+1*A.constantsi+1; return OK;第12页/共66页Status DestoyArray(Ar

11、ray &A) if(!A.base) return ERROR; free(A.base); A.base=NULL; if !(A.bounds) return ERROR; free(A.bounds); A.bounds=NULL; if!(A.constatns) return ERROR; free(A.constants); A.constants=NULL; return OK;第13页/共66页Status Locate(Array A,va_list ap,int &off) off=0; for(i=0;iA.dim;+i) ind=va_arg(ap,int); if(

12、ind=A.boundsi) return OVERFLOW; off+=A.constantsi*ind; return OK;第14页/共66页Status Value(Array A,ElemType &e,.) va_start(ap,e); if(result=Locate(A,ap,off)=0 return result; e=*(A.base+off); return OK;第15页/共66页Status Assign(Array &A,ElemType e,.) va_start(ap,e); if(result=Locate(A,ap,off)=jk= 当i1时，元素aij

13、=0。 由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2 ，则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。 在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其余元素都是零。 对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都要是3个，因此，需存储的元素个数为3n-2。 3(n-2) + 2 + 2 = 3n-2第23页/共66页a n-1 n-1a n-1

14、n-2a21 a12a11a10a01 a00 K=0 1 2 3 4 5 3n-2 3n-1 数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d=LOC(0,0)+(2i+j)*d 上例中，a34对应着sa10。 k=2*i+j=2*3+4=10 a21对应着sa5 k=2*2+1=5由此，我们称sa0.3*n-2是阶三对角带状矩阵A的压缩存储表示。第24页/共66页 上述的各种特殊矩阵，其非零元

15、素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。第25页/共66页 什么是？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。 精确点，设在的矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为。第26页/共66页 矩阵运算的种类很多，在下列抽象数据类型稀疏矩阵的定义中，只列举了几种常见的运算：ADT SparseMatrix 数据对象：D=aij | i=1,2,m;j=1,2,n; aij

16、ElemSet,m和n分别称为矩阵的行数和列数。 数据关系：R=Row,Col Row= | 1=i=m, 1=j=n-1 Col= | 1=i=m-1, 1=j=n 基本操作： CreateSMatrix( & M); 操作结果：创建稀疏矩阵M。 DestroySMatrix( & M); 初始条件：稀疏矩阵M存在。 操作结果：销毁稀疏矩阵M。第27页/共66页 PrintSMatrix(M); 初始条件：稀疏矩阵M存在。 操作结果：输出稀疏矩阵M。 CopySMatrix(M,&T); 初始条件：稀疏矩阵M存在。 操作结果：由稀疏矩阵M复制得到T。 AddSMatrix(M,N,&Q);

17、初始条件：稀疏矩阵M与N的行数和列数对应相等。 操作结果：求稀疏矩阵的和Q=M+N。 SubtMatrix(M,N,&Q); 初始条件：稀疏矩阵M与N的行数和列数对应相等。 操作结果：求稀疏矩阵的差Q=M-N。 MultSMatrix(M,N,&Q); 初始条件：稀疏矩阵M的列数等于N的行数。 操作结果：求稀疏矩阵的积Q=M*N。 TransposeSMatrix(M,&T); 初始条件：稀疏矩阵M存在。 操作结果：求稀疏矩阵M的转置矩阵T。ADT SparseMatrix第28页/共66页 在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。如何进行稀疏矩阵的压缩存储呢？ 按照

18、压缩存储的概念，只存储稀疏矩阵的非零元。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。 反之，用一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，。第29页/共66页例如，下列三元组表(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)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0

19、0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 图5.4 稀疏矩阵M和TM=T=第30页/共66页1.1.三元组顺序表三元组顺序表 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法。 #define maxsize 12500 /假设非零元个数的最大值为12500 typedef struct int i,j; /该非零元的行下标和列下

20、标 ElemType e; Triple; typedef struct triple datamaxsize+1; /非零元三元组表 int m,n,t; /矩阵的行数、行数和非零无个数 TSMatrix;第31页/共66页设A为TSMatrix型的结构变量，图5.4中所示的稀疏矩阵的三元组的表示如下： i j e 1 2 12 data1 1 3 9 data2 3 1 -3 data3 3 6 14 data4 4 3 24 data5 5 2 18 data6 6 1 15 data7 6 4 -7 data8 A.mu = 6 A.nu = 7 A.tu = 8 在此，data域中表

21、示非零元的三元组是以行序为主序顺序排列行序为主序顺序排列的。第32页/共66页 下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。 一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。 将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。 由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.

22、data必定是按行优先存放的。第33页/共66页 按这种方法设计的算法，其是：对A中的每一列 col(0coln-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。1 3 -3 data11 6 15 data22 1 12 data32 5 18 data43 1 9 data53 4 24 data64 6 -7 data76 3 14 data8 1 2 12 data1 1 3 9 data2 3 1 -3 data33 6 14 data4 4 3 24 data5 5 2

23、 18 data6 6 1 15 data7 6 4 -7 data8A.mu = 6 A.nu = 7 A.tu = 8A.mu = 6 A.nu = 7 A.tu = 8B.mu = 7 B.nu = 6 A.tu = 8B.mu = 7 B.nu = 6 A.tu = 8第34页/共66页Status TransposeSMatrix(TSMatrix A, TSMatrix &B) /采用三元组表存储表示，求稀疏矩阵采用三元组表存储表示，求稀疏矩阵A的转置矩阵的转置矩阵B。 B.mu = A.nu; B.nu = A.mu; B.tu = A.tu; if ( B.tu) q=1; f

24、or(col=1;col=A.nu;+col) for(p=1;p=A.tu;+p) if(A.datap.j = = col) B.dataq.i = A.datap.j; B.dataq.j = A.datap.i; B.dataq.e = A.datap.e; +q; return OK; P书书99页算法页算法5.1看演示看演示!第35页/共66页 分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;col=n-1;+col) for(row=0;row

25、=m;+row) tcolrow=mrowcol; 其时间复杂度为O(n*m)。当非零元素的个数tu和m*n同数量级时，算法transmatrix的时间复杂度为O(nu*n2)。 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于tu=m*n的情况。 第36页/共66页 下面给出另外一种称之为，其算法思想为：按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中的位置。 如果能预先确定矩阵A中每一列（即B中每一行）的第一个非零元在B.data中应有的位置，那么在对a.data中的三元组依次作转置时，便可直接放

26、到b.data中恰当的位置上去。 为了确定这些位置，在转置前，应先求得A的每一列中非零元的个数，进而求得每一列的第一个非零元在b.data中应有的位置。 为此，需要设置两个一维数组num0.n和cpot0.nnum0.n：统计矩阵A中每列非零元素的个数.cpot0.n：由递推关系得出M中的每列第一个非零元素在B中的位置。第37页/共66页 算法通过cpot数组建立位置对应关系： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=col=a.nu例如：图5.4中的矩阵M和相应的三元组A可以求得numcol和 cpotcol的值如下： col 1 2 3 4 5 6 7 n

27、umcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9 1 2 12 data1 1 3 9 data2 3 1 -3 data33 6 14 data4 4 3 24 data5 5 2 18 data6 6 1 15 data7 6 4 -7 data8第38页/共66页快速转置算法如下：快速转置算法如下：Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) /采用三元组顺序表存储表示，求稀疏矩阵采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵的转置矩阵B。 T.mu = M.nu; T.nu = M.mu;

28、T.tu = M.tu; if( T.tu) for ( col =1; col=M.nu; +col) O(nu) numcol = 0; for( t=1; t=M.tu; +t) O(tu) +num M.datat.j ; /求求M中每一列含非零元个数中每一列含非零元个数 cpot1 = 1; 第39页/共66页 /求第求第col列中第一个非零元在列中第一个非零元在b.data中的序号中的序号 for( col =2; col=M.nu; +col) O(nu) cpotcol = cpotcol - 1 + num col-1; for( p=1; p=M.tu; +p) O(tu)

29、 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 O(nu+tu) 如果如果tu=mu*muretrun Ok; O(mu*mu)/FastTransposeSMatrix第40页/共66页 三元组顺序表又称有序的，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需按行号存取某一行的非零元，则需从头开始进行查找。 1 2 12 data1 1 3 9 data2 3 1 -3

30、 data33 6 14 data4 4 3 24 data5 5 2 18 data6 6 1 15 data7 6 4 -7 data8第41页/共66页2. 2. 行逻辑链接的顺序表行逻辑链接的顺序表 为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可将上节快速转置矩阵的算法中创建的，指示“行”信息的辅助数据cpot固定在稀疏矩阵的存储结构中。 我们就得到了稀疏矩阵的另一种顺序存储结构：带行链接的三元组表。其类型描述如下： #define maxrow 100 typedef struct Triple datamaxsize+1; /非零元三元组

31、表 int rposmaxro + 1;/各行第一个非零元的位置表 int n,m,t; /矩阵的行数、列数和非零元个数 RLSMatrix; 下面讨论两个稀疏矩阵相乘两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。第42页/共66页 两个矩阵相乘的经典算法也是大家所熟悉的。若设Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。当n1=m2时有： for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0； for(k=1;k=n1;+k) qij+=mik*nkj; 此算法的复杂度为O(m1*n1*n2)。 第43页/共66页当M和N是稀疏矩阵并用三元组表存

32、储结构时，就不能套用上述算法。假设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=第44页/共66页 它们的三元组M.data、N.data和Q.data分别为： 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第45页/共66页（1）乘积矩阵Q中元素11),(*),(),(nkjkNkiMjiQ 在经典算法中，不论M(i,k)和N(k

33、,j)的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积亦为零。因此，在对稀疏矩阵进行运算时，应免去这种无效操作，换句话说，为求Q的值，。 例如：P101页书上M，N矩阵上来。第46页/共66页 由此可见，为了得到非零的乘积，只要对M.data1.M.tu中的每个元素(1=i=m1,1=k=n1) ,找到N.data中所有相应的元素(1=k=m2,1=j=n2)相乘即可。 为此需在N.data中寻找矩阵N中第k行的所有非零元。在稀疏矩阵的行逻辑链接的顺序表中，N.rpos为我们提供了有关信息。 表：矩阵表：矩阵N的的rpos的值的值row 1 2 3 4rposrow

34、1 2 3 5并且，由于rposrow指示矩阵N的第row行中第一个非零元在N.data中的序号，则 rposrow+1-1指示矩阵N的第row行中最后一个非零元在N.data中的序号。第47页/共66页（2）稀疏矩阵相乘的是：对于M中每个元素M.datap(p=1,2,M.tu)，找到N 中所有满足条件M.datap.j=N.dataq.i的元素N.dataq，求得M.datap.v和N.dataq.v的乘积，而前面公式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积M.datap.v*N.dataq.v只是Q(i,j)中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然

35、后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。（3）两个稀疏矩阵相乘的乘积不一定是稀疏矩阵。反之，即使前面公式中每个分量值M(i,k)*N(k,j)不为零，其累加值Qi,j也可能为零。因此乘积矩阵Q中的元素是否为非零元，只有在求得其累加和后才能得知。由于Q中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对Q进行逐行处理，先求得累计求和的中间结果（Q的一行），然后再压缩存储到Q.data中去。（见P102页书算法大致描述）第48页/共66页Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &

36、Q)/求矩阵乘积求矩阵乘积Q=M*N，采用行逻辑链接存储表示，采用行逻辑链接存储表示 if(M.nu != N.mu) return ERROR; Q.nu = M.mu; Q.nu = N.nu; Q.tu =0; /Q初始化初始化 if( M.tu * N.tu != 0 ) for( arow =1; arow=M.mu; +arow) /处理处理M的每一行的每一行 ctemp =0; /当前行各元素累加器清零当前行各元素累加器清零 Q.rposarow = Q.tu +1; for ( p=M.rposarow; pM.rposarow+1; +p) /对当前行中每一个非零元找到对应元

37、在对当前行中每一个非零元找到对应元在N中的行号中的行号 brow = M.datap.j; if( brow N.tu +1) t=N.rposbrow+1; else t= N.tu +1; 第49页/共66页 for ( q=N.rposbrow; qt; +q) ccol =N.dataq.j; ctempccol += M.datap.e * N.dataq.e; /for q /求得求得Q中第中第crow(=arow)行的非零元行的非零元 for(ccol=1; ccolMAXSIZE) return ERROR; Q.dataQ.tu =arow, ccol,ctempccol;

38、/if /for arow /if return OK;/MultSMAtrix第50页/共66页3.3.十字链表十字链表 当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。例如，在作“将矩阵B加到矩阵A上”的操作时，由于非零元的插入或删除将会引起A.data中元素的移动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。 在链表中，每个非零元可用一个含五个域五个域的结点表示，其中i,j和e三个域分别表示该非零元所在的行、列和非零元的值，同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，

39、每个非零元既是某个行链表的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。第51页/共66页3 0 0 50 -1 0 02 0 0 0M=3*4 M.chead列1 1 31 4 52 2 -13 1 2M.rhead行 第52页/共66页稀疏矩阵的十字链表表示：typedef struct OLNode int i,j; /该非零元的行和列下标 ElemType e; struct OLNode *right,*

40、down; /该非零元所在行表和列表的后继链域OLNode,*OLink;typedef struct Olink *rhead,*chead; /行和列链表头指针向量基址由CreateSMatrix分配 int mu,nu,tu;/稀疏矩阵的行数、列数和非零元个数CrossList;第53页/共66页 CreateSMatrix_OL函数用来创建稀疏矩阵M。采用十字链表存储表示。 P书104页CrossList M;MM.mu 稀疏矩阵的行数M.nu 稀疏矩阵的列数M.tu 稀疏矩阵的非零元素的个数 M.rhead1-iM.rhead M.rhead1-j M.rhead1-e M.rhea

41、d1-right M.rhead1-downM.chead 第54页/共66页5.4广义表的定义广义表的定义 广义表（广义表（ListsLists，又称列表），又称列表）是线性表的推广。在第2章中，我们把线性表定义为n=0个元素a1,a2,a3,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。 广义表是n(n=0)个元素a1,a2,a3,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,an)。LS是广义表的名字，n为它的长度。

42、若ai是广义表，则称它为LS的子表。第55页/共66页抽象数据类型广义表的定义如下：ADT Glist 数据对象： D=ei | i=1,2,.,n;n=0 ; eiAtomSet 或ei Glist, AtomSet为某个数据对象 数据关系：R1= | ei-1 , ei D,2=i=1)非空，则a1是LS的表头，其余元素组成的表(a2,an)称为LS的表尾。 显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：（1）A=（）A是一个空表，其长度为零。（2）B=（e）表B只有一个原子e，B的长度为1。（3）C=（a,(b,c,d)表C的长度为2，两个元素分别 为原子a和子表(b,c,d)。（4）D=（A，B，C