数据结构讲义精.ppt

数据结构讲义数据结构讲义第1页，本讲稿共67页第2页，本讲稿共67页5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义5.5 广义表的存储结构广义表的存储结构*5.6 m元多项式的表示元多项式的表示*5.7 广义表的递归算法广义表的递归算法目录目录第第 五五 章章 数组和广义表数组和广义表第3页，本讲稿共67页5.1数组的定义数组的定义 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素数据元素数据元素数据元素本身也是一种线性表本身也是一种线性表本身也是一种线性表本身也是一种线性表。数组的定义数组的定义数组的定义数组的定义 几乎所有的程序设计语言都把数组类型设定为固有类型。数组也是我们最熟悉的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。第4页，本讲稿共67页 以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。数组的抽象数据类型定义：数组的抽象数据类型定义：数组的抽象数据类型定义：数组的抽象数据类型定义：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第5页，本讲稿共67页基本操作:InitArray(&A,n,bound1,.,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第6页，本讲稿共67页多维数组是一维数组的推广。例如，二维数组：a11 a12 a1n A1 a21 a22 a2n A2 am1 am2 amn AnAmn=见书见书P91页图页图5.1第7页，本讲稿共67页 所以数组可以看成是由行向量组成的线性表，也可以看成是个列向量组成的线性表。在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedef elemtype array2mn;等价于：typedef elemtype array1n;typedef array1 array2m;同理，一个N维数组类型可以定义为其数据元素为N-1维数组类型的一维序组类型。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。第8页，本讲稿共67页5.2数组的顺序表示和实现数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式：通常有两种顺序存储方式：行优先顺序行优先顺序将数组元素按行排列，第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,an2,anm在FORTRAN语言中，数组就是按列优先顺序存储的。第9页，本讲稿共67页 以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。按上述两种方式顺序存储的序组，只要知道开始结点的存放地址只要知道开始结点的存放地址只要知道开始结点的存放地址只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的元数，就可以将数组元素的存放地址表示为其下标的元数，就可以将数组元素的存放地址表示为其下标的元数，就可以将数组元素的存放地址表示为其下标的线性函数线性函数线性函数线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。例如例如，二维数组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第10页，本讲稿共67页 将上述的式子推广到一般情况，可得到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就是常数。第11页，本讲稿共67页数组的顺序存储表示和实现:#include#define MAX_ARRAY_DIM 8typedef struct ElemType*base;/数组元素基址，由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,.);第12页，本讲稿共67页基本操作的算法描述:Status InitArray(Array&A,int 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;第14页，本讲稿共67页Status DestoyArray(Array&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;第15页，本讲稿共67页Status Locate(Array A,va_list ap,int&off)off=0;for(i=0;iA.dim;+i)ind=va_arg(ap,int);if(ind=A.boundsi)return OVERFLOW;off+=A.constantsi*ind;return OK;第16页，本讲稿共67页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;第17页，本讲稿共67页Status Assign(Array&A,ElemType e,.)va_start(ap,e);if(result=Locate(A,ap,off)=jk=当i=j i1时，元素aij=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第25页，本讲稿共67页a n-1 n-1a n-1 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的压缩存储表示。第26页，本讲稿共67页 上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。第27页，本讲稿共67页稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵 什么是稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。精确点，设在的矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵。第28页，本讲稿共67页 矩阵运算的种类很多，在下列抽象数据类型稀疏矩阵的定义中，只列举了几种常见的运算：ADT SparseMatrix 数据对象：D=aij|i=1,2,m;j=1,2,n;aij 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。第29页，本讲稿共67页 PrintSMatrix(M);初始条件：稀疏矩阵M存在。操作结果：输出稀疏矩阵M。CopySMatrix(M,&T);初始条件：稀疏矩阵M存在。操作结果：由稀疏矩阵M复制得到T。AddSMatrix(M,N,&Q);初始条件：稀疏矩阵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第30页，本讲稿共67页 在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。如何进行稀疏矩阵的压缩存储呢？按照压缩存储的概念，只存储稀疏矩阵的非零元。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，用一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定稀疏矩阵可由表示非零元的三元组及其行列数唯一确定稀疏矩阵可由表示非零元的三元组及其行列数唯一确定稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。第31页，本讲稿共67页例如，下列三元组表(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的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 7 7 7 7 0 12 9 0 0 0 0 0 0-3 0 0 15 0 0 0 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=1 12 23 34 45 56 6第32页，本讲稿共67页1.1.三元组顺序表三元组顺序表 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表三元顺序表三元顺序表三元顺序表。#define maxsize 12500/假设非零元个数的最大值为12500 typedef struct int i,j;/该非零元的行下标和列下标 ElemType e;Triple;typedef struct triple datamaxsize+1;/非零元三元组表 int m,n,t;/矩阵的行数、行数和非零无个数 TSMatrix;第33页，本讲稿共67页设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域中表示非零元的三元组是以行序为主序顺序排列行序为主序顺序排列的。第34页，本讲稿共67页 下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。一个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.data必定是按行优先存放的。第35页，本讲稿共67页 按这种方法设计的算法，其基本思想基本思想基本思想基本思想是：对A中的每一列 col(0coln-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。i j ei j ei j ei j e1 3 -3 data11 6 15 data22 1 12 data32 5 18 data43 1 9 data53 4 24 data64 6 -7 data76 3 14 data8i j ei j ei j ei j e 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 data8A AB BA.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第36页，本讲稿共67页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;for(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看演示看演示!第37页，本讲稿共67页 分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：for(col=0;col=n-1;+col)for(row=0;row=m;+row)tcolrow=mrowcol;其时间复杂度为O(n*m)。当非零元素的个数tu和m*n同数量级时，算法transmatrix的时间复杂度为O(nu*n2)。三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于tu=m*n的情况。第38页，本讲稿共67页 下面给出另外一种称之为快速转置的算法快速转置的算法快速转置的算法快速转置的算法，其算法思想为：按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当恰当恰当恰当的位置。如果能预先确定矩阵A中每一列（即B中每一行）的第一个非零元在B.data中应有的位置，那么在对a.data中的三元组依次作转置时，便可直接放到b.data中恰当的位置上去。为了确定这些位置，在转置前，应先求得A的每一列中非零元的个数（因为：矩阵（因为：矩阵（因为：矩阵（因为：矩阵A A A A中每一列的第一个非中每一列的第一个非中每一列的第一个非中每一列的第一个非零元素在数组零元素在数组零元素在数组零元素在数组B B B B中应有的位置等于前一列第一个非零元素的位置加上中应有的位置等于前一列第一个非零元素的位置加上中应有的位置等于前一列第一个非零元素的位置加上中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。前列非零元素的个数。前列非零元素的个数。前列非零元素的个数。），进而求得每一列的第一个非零元在b.data中应有的位置。为此，需要设置两个一维数组num0.n和cpot0.nnum0.n：统计矩阵A中每列非零元素的个数.cpot0.n：由递推关系得出M中的每列第一个非零元素在B中的位置。第39页，本讲稿共67页 算法通过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 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9i j ei j e 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 data8A A A.mu=6 A.nu=7 A.tu=8 A.mu=6 A.nu=7 A.tu=8 A.mu=6 A.nu=7 A.tu=8 A.mu=6 A.nu=7 A.tu=8见演示见演示!第40页，本讲稿共67页快速转置算法如下：快速转置算法如下：Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)/采用三元组顺序表存储表示，求稀疏矩阵采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵的转置矩阵B。T.mu=M.nu;T.nu=M.mu;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;第41页，本讲稿共67页 /求第求第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)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第42页，本讲稿共67页 三元组顺序表又称有序的双下标法双下标法双下标法双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需按行号存取某一行的非零元，则需从头开始进行查找。i j ei j e 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第43页，本讲稿共67页2.2.行逻辑链接的顺序表行逻辑链接的顺序表 为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此，可将上节快速转置矩阵的算法中创建的，指示“行”信息的辅助数据cpot固定在稀疏矩阵的存储结构中。称这种称这种称这种称这种“带带带带行链接信息行链接信息行链接信息行链接信息”的三元组表为行逻辑链接的顺序表。的三元组表为行逻辑链接的顺序表。的三元组表为行逻辑链接的顺序表。的三元组表为行逻辑链接的顺序表。我们就得到了稀疏矩阵的另一种顺序存储结构：带行链接的三元组表。其类型描述如下：#define maxrow 100 typedef struct Triple datamaxsize+1;/非零元三元组表 int rposmaxro+1;/各行第一个非零元的位置表 int n,m,t;/矩阵的行数、列数和非零元个数 RLSMatrix;下面讨论两个稀疏矩阵相乘两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。第44页，本讲稿共67页 两个矩阵相乘的经典算法也是大家所熟悉的。若设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)。第45页，本讲稿共67页当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设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=第46页，本讲稿共67页 它们的三元组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那么如何从那么如何从那么如何从那么如何从MM和和和和N N求得求得求得求得QQ呢？呢？呢？呢？第47页，本讲稿共67页（1）乘积矩阵Q中元素 在经典算法中，不论M(i,k)和N(k,j)的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积亦为零。因此，在对稀疏矩阵进行运算时，应免去这种无效操作，换句话说，为求Q的值，只只只只需在需在需在需在M.dataM.data和和和和N.dataN.data中找到相应的各对元素（即中找到相应的各对元素（即中找到相应的各对元素（即中找到相应的各对元素（即M.dataM.data中中中中j j值和值和值和值和N.dataN.data中中中中的的的的i i值相等的各对元素）相乘即可值相等的各对元素）相乘即可值相等的各对元素）相乘即可值相等的各对元素）相乘即可。例如：P101页书上M，N矩阵上来。第48页，本讲稿共67页 由此可见，为了得到非零的乘积，只要对M.data1.M.tu中的每个元素（i,k,M(i,k)i,k,M(i,k)）(1=i=m1,1=k=n1),找到N.data中所有相应的元素(k,j,N(k,j)(k,j,N(k,j)(1=k=m2,1=j=n2)相乘即可。为此需在N.data中寻找矩阵N中第k行的所有非零元。在稀疏矩阵的行逻辑链接的顺序表中，N.rpos为我们提供了有关信息。表：矩阵表：矩阵N的的rpos的值的值row 1 2 3 4rposrow 1 2 3 5并且，由于rposrow指示矩阵N的第row行中第一个非零元在N.data中的序号，则 rposrow+1-1指示矩阵N的第row行中最后一个非零元在N.data中的序号。第49页，本讲稿共67页（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)中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。（3）两个稀疏矩阵相乘的乘积不一定是稀疏矩阵。反之，即使前面公式中每个分量值M(i,k)*N(k,j)不为零，其累加值Qi,j也可能为零。因此乘积矩阵Q中的元素是否为非零元，只有在求得其累加和后才能得知。由于Q中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对Q进行逐行处理，先求得累计求和的中间结果（Q的一行），然后再压缩存储到Q.data中去。（见P102页书算法大致描述）看演示！看演示！看演示！看演示！第50页，本讲稿共67页Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix&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)/对当前行中每一个非零元找到对应元在对当前行中每一个非零元找到对应元在N中的行号中的行号 brow=M.datap.j;if(brow N.tu+1)t=N.rposbrow+1;else t=N.tu+1;第51页，本讲稿共67页 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;/if /for arow/if return OK;/MultSMAtrix第52页，本讲稿共67页3.3.十字链表十字链表 当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。例如，在作“将矩阵B加到矩阵A上”的操作时，由于非零元的插入或删除将会引起A.data中元素的移动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。在链表中，每个非零元可用一个含五个域五个域的结点表示，其中i,j和e三个域分别表示该非零元所在的行、列和非零元的值，向右域向右域rightright用以链接用以链接同一行中下一个非零元同一行中下一个非零元，向下域向下域downdown用以链接同一列中下一个非零元。用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，每个非零元既是某个行链表的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。第53页，本讲稿共67页3 0 0 50 -1 0 02 0 0 0M=3*4 M.chead列1 1 31 4 52 2 -13 1 2M.rhead行 稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵MM的十字链表的十字链表的十字链表的十字链表第54页，本讲稿共67页稀疏矩阵的十字链表表示：typedef struct OLNode int i,j;/该非零元的行和列下标 ElemType e;struct OLNode*right,*down;/该非零元所在行表和列表的后继链域OLNode,*OLink;typedef struct Olink*rhead,*chead;/行和列链表头指针向量基址由CreateSMatrix分配 int mu,nu,tu;/稀疏矩阵的行数、列数和非零元个数CrossList;第55页，本讲稿共67页 CreateSMatrix_OL函数用来创建稀疏矩阵M。采用十字链表存储表示。P书104页CrossList M;MM.mu 稀疏矩阵的行数M.nu 稀疏矩阵的列数M.tu 稀疏矩阵的非零元素的个数 M.rhead1-iM.rhead M.rhead1-j M.rhead1-e M.rhead1-right M.rhead1-downM.chead 第56页，本讲稿共67页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为它的长度。若ai是广义表，则称它为LS的子表。第57页，本讲稿共67页抽象数据类型广义表的定义如下：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）表D的长度为3，三个元素 都是广义表。显然，将子表的值代入后，则有D=(),(e),(a,(b,c,d)。（5）E=（E）这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,).第61页，本讲稿共67页从上述定义和例子可推出广义表的三个重要结论：（1）广义表的元素可以是子表，而子表的元素还可以是子表，。由此，广义表是一个多层次的结构，可以用图形象地表示。P108（2）广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。（3）广义表的递归性。综上所述，广义表不仅是线性表的推广，也是树的推广。第62页，本讲稿共67页 由表头、表尾的定义可知：任何一个非空广义表其表头可能是原子，也可能是列表，而其表尾必定是列表。gethead(B)=e gettail(B)=()gethead(D)=A gettail(D)=(B,C)由于（B，C）为非空广义表，则可继续分解得到：gethead(B,C)=B gettail(B,C)=(C)注意广义表（）和()不同。前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（）。第63页，本讲稿共67页 由于广义表(a1,a2,a3,an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构采用链式存储结构，每个数据元素可用一个结点表示。由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。若列表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可唯一确定列表。由此，一个表结点可由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域。5.5广义表的存储结构广义表的存储结构第64页，本讲稿共67页1 1、表结点由三个域组成：、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。表结点 原子结点 tp hp tag=1 atom tag=0第65页，本讲稿共67页其类型定义如下：typedef enumATOM,LISTelemtag;typedeg struct glnode elemtag