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

第五章数组和广义表,5.1数组的类型定义,5.3稀疏矩阵的压缩存储,5.2数组的顺序表示和实现,5.4广义表的类型定义,5.5广义表的表示方法,5.6广义表操作的递归函数,5.1数组的类型定义,ADTArray数据对象：Daj1,j2,.,ji,jn|ji=0,.,bi-1,i=1,2,.,n数据关系：RR1,R2,.,RnRi|0jkbk-1,1kn且ki,0jibi-2,i=2,.,nADTArray,基本操作:,二维数组的定义:,数据对象:D=aij|0ib1-1,0jb2-1数据关系:R=ROW,COLROW=|0ib1-2,0jb2-1COL=|0ib1-1,0jb2-2,基本操作:,基本操作：,InitArray(2)数组是多维的结构，而存储空间是一个一维的结构。,有两种顺序映象的方式:1)以行序为主序(低下标优先);2)以列序为主序(高下标优先);,例如：,称为基地址或基址。,以“行序为主序”的存储映象,二维数组A中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(b2ij),a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,a0,1,a0,0,a0,2,a1,0,a1,1,a1,2,L,L,推广到一般情况，可得到n维数组数据元素存储位置的映象关系,称为n维数组的映象函数。数组元素的存储位置是其下标的线性函数,LOC(j1,j2,.,jn)=LOC(0,0,.,0)+b2bnj1+b3bnj2+bnjn-1+jn)L,假设m行n列的矩阵含t个非零元素，则称为稀疏因子通常认为0.05的矩阵为稀疏矩阵,5.3稀疏矩阵的压缩存储,何谓稀疏矩阵？,以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:,1)零值元素占了很大空间;,2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零;,1)尽可能少存或不存零值元素;,解决问题的原则:,2)尽可能减少没有实际意义的运算;,3)操作方便;即:能尽可能快地找到与下标值(i,j)对应的元素;能尽可能快地找到同一行或同一列的非零值元;,1)特殊矩阵非零元在矩阵中的分布有一定规则例如:三角矩阵对角矩阵,2)随机稀疏矩阵非零元在矩阵中随机出现,有两类稀疏矩阵：,特殊矩阵的压缩存储,特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩阵三对角矩阵,对称矩阵的压缩存储,设有一个nn的对称矩阵A。,在矩阵中，aij=aji,为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。数组B共有n+(n-1)+1=n*(n+1)/2个元素。,上三角矩阵,下三角矩阵,下三角矩阵,Ba00a10a11a20a21a22a30a31a32an-1n-1,012345678n(n+1)/2-1,若ij,数组元素Aij在数组B中的存放位置为1+2+i+j=(i+1)*i/2+j,前i行元素总数第i行第j个元素前元素个数,若ij，数组元素Aij在矩阵的下三角部分，在数组B中没有存放。因此，找它的对称元素Aji。Aji在数组B的第(2*n-j-1)*j/2+i的位置中找到。,三对角矩阵的压缩存储,Ba00a01a10a11a12a21a22a23an-1n-2an-1n-1,012345678910,三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中，且a00存放于B0。在三条对角线上的元素aij满足0in-1,i-1ji+1在一维数组B中Aij在第i行，它前面有3*i-1个非零元素,在本行中第j列前面有j-i+1个，所以元素Aij在B中位置为k=2*i+j。,随机稀疏矩阵的压缩存储方法:,一、三元组顺序表,二、行逻辑联接的顺序表,三、十字链表,#defineMAXSIZE12500typedefstructinti,j;/该非零元的行下标和列下标ElemTypee;/该非零元的值Triple;/三元组类型,一、三元组顺序表,typedefstructTripledataMAXSIZE+1;intmu,nu,tu;TSMatrix;/稀疏矩阵类型,如何求转置矩阵？,用常规的二维数组表示时的算法,其时间复杂度为:O(munu),for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;,用“三元组”表示时如何实现？,1214,15-5,22-7,3136,3428,2114,51-5,22-7,1336,4328,首先应该确定转置矩阵中,每一行的第一个非零元在三元组中的位置。,cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;,StatusFastTransposeSMatrix(TSMatrixM,TSMatrix/FastTransposeSMatrix,转置矩阵元素,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,分析算法FastTransposeSMatrix的时间复杂度：,时间复杂度为:O(M.nu+M.tu),for(col=1;col=M.nu;+col)for(t=1;t=M.tu;+t)for(col=2;col=M.nu;+col)for(p=1;p=M.tu;+p),三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。,二、行逻辑联接的顺序表,#defineMAXMN500typedefstructTripledataMAXSIZE+1;intrposMAXMN+1;intmu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型,修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos,其值在稀疏矩阵的初始化函数中确定。,例如：给定一组下标，求矩阵的元素值,ElemTypevalue(RLSMatrixM,intr,intc)p=M.rposr;while(M.datap.i=r/value,矩阵乘法的精典算法: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),Q初始化;ifQ是非零矩阵/逐行求积for(arow=1;arow=M.mu;+arow)/处理M的每一行ctemp=0;/累加器清零计算Q中第arow行的积并存入ctemp中；将ctemp中非零元压缩存储到Q.data；/forarow/if,两个稀疏矩阵相乘（QMN）的过程可大致描述如下：,StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix/MultSMatrix,ctemp=0;/当前行各元素累加器清零Q.rposarow=Q.tu+1;for(p=M.rposarow;pMAXSIZE)returnERROR;Q.dataQ.tu=arow,ccol,ctempccol;/if,处理的每一行,M,分析上述算法的时间复杂度,累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.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和Nptr.hp);if(depmax)max=dep;returnmax+1;/GlistDepth,if(!L)return1;if(L-tag=ATOM)return0;,for(max=0,pp=L;pp;pp=pp-ptr.tp)dep=GlistDepth(pp-ptr.hp);if(depmax)max=dep;,例如:,pp,pp-ptr.hp,pp,pp,pp-ptr.hp,pp-ptr.hp,1,1,1,L,例二复制广义表,新的广义表由新的表头和表尾构成。,可以直接求解的两种简单情况为:空表复制求得的新表自然也是空表;原子结点可以直接复制求得。,将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾，,若ls=NIL则newls=NIL否则构造结点newls,由表头ls-ptr.hp复制得newhp由表尾ls-ptr.tp复制得newtp并使newls-ptr.hp=newhp,newls-ptr.tp=newtp,复制求广义表的算法描述如下:,StatusCopyGList(Glist/CopyGList,分别复制表头和表尾,CopyGList(T-ptr.hp,L-ptr.hp);/复制求得表头T-ptr.hp的一个副本L-ptr.hpCopyGList(T-ptr.tp,L-ptr.tp);/复制求得表尾T-ptr.tp的一个副本L-ptr.tp,语句CopyGList(T-ptr.hp,L-ptr.hp);等价于CopyGList(newhp,L-ptr.tp);T-ptr.hp=newhp;,例三创建广义表的存储结构,对应广义表的不同定义方法相应地有不同的创建存储结构的算法。,假设以字符串S=(1,2,n)的形式定义广义表L，建立相应的存储结构。,由于S中的每个子串i定义L的一个子表，从而产生n个子问题，即分别由这n个子串(递归)建立n个子表，再组合成一个广义表。,可以直接求解的两种简单情况为:由串()建立的广义表是空表;由单字符建立的子表只是一个原子结点。,如何由子表组合成一个广义表？,首先分析广义表和子表在存储结构中的关系。,先看第一个子表和广义表的关系:,1,L,指向广义表的头指针,指向第一个子表的头指针,再看相邻两个子表之间的关系:,1,1,指向第i+1个子表的头指针,指向第i个子表的头指针,可见，两者之间通过表结点相链接。,若S=()则L=NIL,否则构造第一个表结点*L,并从串S中分解出第一个子串1,对应创建第一个子广义表L-ptr.hp;,若剩余串非空，则构造第二个表结点L-ptr.tp,并从串S中分解出第二个子串2,对应建第二个子广义表;,依次类推，直至剩余串为空串止。,voidCreateGList(Glist/脱去串S的外层括弧/else,由sub中所含n个子串建立n个子表;,dosever(sub,hsub);/分离出子表串hsub=iif(!StrEmpty(sub)p-ptr.tp=new(sizeof(GLNode);/建下一个子表的表结点*(p-ptr.tp)p=p-ptr.tp;while(!StrEmpty(sub);p-ptr.tp=NULL;/表尾为空表,创建由串hsub定义的广义表p-ptr.hp;,if(StrLength(hsub)=1)p-ptr.hp=(GList)malloc(sizeof(GLNode);p-ptr.hp-tag=ATOM;p-ptr.hp-atom=hsub;/创建单原子结点elseCreateGList(p-ptr.hp,hsub);/递归建广义表,5.1设有上三角矩阵（aij）nn，将其上三角元素逐行存于数组中Bm，（m充分大），使得Bk=aij且k=f1(i)+f2(j)+c。试推导出函数f1,f2和常数c（要求f1和f2中不含常数项）。,课后作业及习题,5.2求下列广义表操作的结果：,(1)GetHead(p,h,w);(2)GetTail(b,k,p,h)(3)GetHead(a,b),(c,d);(4)GetTail(a,b),(c,d);(5)GetHeadGetTail(a,b),(c,d);(6)GetTailGetHead(a,