数组与广义表相关知识

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 数组和广义表,5.1,数组的类型定义,5.3,矩阵的压缩存储,5.2,数组的顺序表示和实现,5.4,广义表的类型定义,5.5,广义表的存储结构,学习提要：,1.,了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。,2.,掌握对特殊矩阵进行压缩存储时的下标变换公式。,3.,了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。,4.,掌握广义表的结构特点及其存储表示方法。,ADT Array ,数据对象,：,D,a,j,1,j,2, .,j,i,j,n,| j,i,=0,.,b,i,-1, i=1,2,.,n ,数据关系,：,R,R1, R2, ., Rn,Ri, | 0,j,k,b,k,-1,1,k,n,且,k,i, 0,j,i,b,i,-2, i=2,.,n , ADT,Array,基本操作,:,5.1,数组的类型定义,基本操作,：,InitArray(&A, n, bound1, ., boundn),DestroyArray(&A),Value(A, &e, index1, ., indexn),Assign(&A, e, index1, ., indexn),InitArray(&A, n, bound1, ., boundn),操作结果：,若维数,n,和各维长度合法，,则构造相应的数组,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,。,二维数组的定义,:,数据对象,:,D = a,ij,|,0,ib,1,-1, 0 jb,2,-1,数据关系,:,R = ROW, COL ,ROW,= ,|,0,ib,1,-2, 0jb,2,-1,COL,= ,|,0ib,1,-1, 0 jb,2,-2,二维数组的定义,:,5.2,数组的顺序表示和实现,类型特点,:,（,1,）,只有引用型操作，没有加工型操作；,（,2,） 数组是多维的结构，而存储空间是,一个一维的结构。,有两种顺序映象的方式,:,（,1,）,以行序为主序,（,2,）,以列序为主序,a,00,a,01, a,0n-1,a,10,a,11, a,1n-1,a,m-10,a,m-11, a,m-1n-1,.,按行序为主序存放,a,m-1n-1,.,a,m-11,a,m-10,.,a,1n -1,.,a,11,a,10,a,0n-1,.,a,01,a,00,0,1,n-1,m*n-1,n,LOC(i,j) = LOC(0,0) + (ni,j)L,按列序为主序存放,0,1,m-1,m*n-1,m,a,m-1n-1,.,a,1n-1,a,0n-1,.,a,m-11,.,a,11,a,01,a,m-10,.,a,10,a,00,a,00,a,01,.,a,0n-1,a,10,a,11,.,a,1n-1,a,m-10,a,m-11,a,m-1n-1,.,LOC(i,j) = LOC(0,0) + (mj,i)L,称为,基地址,或基址,以“行序为主序”的存储映象,:,二维数组,A,中任一元素,a,i,j,的存储位置,LOC(i,j) = LOC(0,0) + (ni,j),L,以“列序为主序”的存储映象,:,二维数组,A,中任一元素,a,i,j,的存储位置,LOC(i,j) = LOC(0,0) + (mj,i),L,例,5.1:,若,L=2, LOC1,1 = 1000,LOC3,4 = LOC1,1 + (5*(3-1)+4-1)*L,= 1000 + 13 * 2,= 1026,一般地，若,LOC0,0,为基地址,:,LOCi,j = LOC0,0 + (n*i+j)*L,(0=im, 0=jn,每个数据元素占,L,个存储单元,),LOCi,j,k = LOC0,0,0 + (n*h*i+ h*j + k)*L,(0=im, 0=jn, 0=kh,每个数据元素占,L,个存储单元,),a,11,a,12,a,13,a,14,a,15,A,4x5,= a,21,a,22,a,23,a,24,a,25,a,31,a,32,a,33,a,34,a,35,a,41,a,42,a,43,a,44,a,45,推广到一般情况,n,维数组的行序为主序存储地址计算公式,b,1,b,2,.,b,n,是,n,维的维界,数组元素,A(j,1,j,2,.,j,n,),的存储位置为,LOCj,1,j,2,.j,n,= LOC0,0,.,0 + (b,2,*b,3*,*b,n*,j,1,+ b,3*,*b,n*,j,2,+ .,+ b,n*,j,n,-1,+ j,n )*,L,n-1 n,= LOC0,0,.,0 + (, j,i, b,k +,j,n,)*,L,i=1 k=i+1,例,:,在,C,语言中,设 数组,A5678,的首地址为,2000,每个元素占,2,个字节,;,求元素,A3454,的地址,.,LOC3,4,5,4 = 2000 + (6*7*8*3 + 7*8*4 + 8*5 + 4)*2,= 2000 + ( 336*3 + 56*4 + 8*5 + 1*4)*2,= 2000 + (1008 + 224 + 40 + 4)*2 = 4552,推广到一般情况，可得到,n,维数组数据元素存储位置的映象关系,称为,n,维数组的,映象函数,。数组元素的存储位置是其下标的线性函数。,其中,c,n,= L,，,c,i-1,= b,i,c,i, 1 i,n,。,LOC(j,1, j,2, ., j,n,) = LOC(0,0,.,0) + c,i,j,i,i,=1,n,列序为主序,: (FORTRAN),A,mxn,=,(a,11,a,21,a,31,.a,m1,),(a,12,a,22,a,32,.a,m 2,),.(a,1n,a,2n,a,3n,.a,mn,),LOC1,1,为基地址,:,LOCi,j = LOC1,1 + (m*(j-1)+i-1)*L,(1=i=m, 1=j=n,每个数据元素占,L,个存储单元,),例,5.2:,若,L=2, LOC1,1 = 1000,LOC3,4 = LOC1,1 + (4*(4-1)+3-1)*L,= 1000 + 14 * 2 = 1028,LOC0,0,为基地址,:,LOCi,j = LOC0,0 + (m*j+i)*L,(0=i=m, 0=j=n,每个数据元素占,L,个存储单元,),LOCi,j,k = LOC0,0,0 + (m*(n*k)+j)+i) *L,a,11,a,12,a,13,a,14,a,15,a,21,a,22,a,23,a,24,a,25,a,31,a,32,a,33,a,34,a,35,a,41,a,42,a,43,a,44,a,45,数组顺序存储的表示和实现,InitArray(Array ,/,若维数,dim,和随后的各维长度数合法,构造相应的数组,并返回,OK,DestroyArray (Array /,销毁数组,A,Value(Array A, ElemType ,若各下标不超界,则,e,赋值为所指定的,A,的元素值,并返回,OK,Assign(Array &A, ElemType e, .),若各下标不超界,则将,e,的值赋给所指定的,A,的元素,并返回,OK,base,dim,bounds,constants,a0,a1,ai,at,.,.,.,0 1 . dim-1,.,#include ,#define MAX_ARRAY_DIM 8/,维数最大值,typedef struct ,ElemType *base;/,数组元素基址,int dim;/,维数,int *bounds; /,维界基址,int *constants;/,映像函数常量基址，除,dim,外，均由,InitArray,分配,Array;,练习,假设有二维数组,A,6,8,，每个元素用相邻的,6,个字节存储，存储器按字节编址。已知,A,的起始存储位置（基地址）为,1000,，计算：,（,1,）数组,A,的体积（即存储量）；,（,2,）数组,A,的最后一个元素,a,57,的第一个字节的地址；,（,3,）按行存储时，元素,a,14,的第一个字节的地址；,（,4,）按列存储时，元素,a,47,的第一个字节的地址。,5.3.1,特殊矩阵,5.3,矩阵的压缩存储,5.3.2,稀疏矩阵,以常规方法，即以二维数组表示,高阶的稀疏矩阵时产生的,问题,:,(1),零值元素占了很大空间,;,(2),计算中进行了很多和零值的运算。,(1),尽可能少存或不存零值元素；,解决问题的原则,:,(2),尽可能减少没有实际意义的运算；,(3),操作方便。 即：,能尽可能快地找到与下标值,(i,，,j),对应的元素，,能尽可能快地找到同一行或同一列的非零值元。,5.3.1,特殊矩阵,特殊矩阵是指非零元素或零元素在矩阵中的分布有一定规律的矩阵。,对称矩阵,元素满足条件,a,ij,=a,ji,1=i , j=n,的,n,阶矩阵。,按行序为主序：,a,11,a,12,., .,a,1n,a,21,a,22,. .,a,2n,a,n1,a,n2,.,a,nn,.,a11 a21 a22 a31 a32 an1 ann,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,例,5.2,对称矩阵,n = 5, 1+2+3+4+5 = 5*(5+1)/2 = 15,一维数组,SA1.15,作为数组,A,的存储结构,:,SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5),如,: a5,3 = a3,5 = 7,k = 5(5-1)/2 + 3-1= 12,故,:sa12 = 7,4 5 3 2 1,5 2 1 5 6,3 1 3 2 7,2 5 2 8 9,1 6 7 9 5,A =,4,5 2,0,3 1 3,2 5 2 8,1 6 7 9 5,A,=,三角矩阵,按行序为主序：,Loc( a,ij,)=Loc(a,11,)+,i*(i-1)/2,+(j-1)*L,a,11,0 0,.,0,a,21,a,22,0,.,0,a,n1,a,n2,a,n3,.,a,nn,.,0,a11 a21 a22 a31 a32 an1 ann,.,.,k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1,例,5.3,下三角矩阵,4 0 0 0 0,5 2 0 0 0,A,= 3 1 3 0 0,2 5 2 8 0,1 6 7 9 5,如,: a5,3 = 7,k = 5(5-1)/2 + 3-1 = 12,故,:sa12 = 7,但,a3,5 = 0,对角矩阵,a,11,a,12,0, .,0,a,21,a,22,a,23,0,0,0,0,a,n-1,n-2,a,n-1,n-1,a,n-1,n,0,0, ,a,n,n-1,a,nn,0,a,32,a,33,a,34,0,0,Loc(a,ij,)=Loc(a,11,)+2(i-1)+(j-1)*L,按行序为主序：,a11 a12 a21 a22 a23 ann-1 ann,.,.,k=0 1 2 3 4 3*n-3,sak,和,ai,j,的一一对应关系,:,sak, k = 3*(i-1) + j-i,ai, j =,当,|i - j|1,a,11,a,12,0 0 . 0,a,21,a,22,a,23,0 . 0,Anxn = 0 a,32,a,33,a,34,. 0,.,0 0 0 . a,nn-1,a,nn,例,5.4,对角矩阵,4 3 0 0 0,5 2 2 0 0,A = 0 1 0 4 0,0 0 2 8 7,0 0 0 9 5,一维数组,SA0.3*5-3,作为数组,A,的存储结构,: SA=(4 3 5 2 2 1 0 4 2 8 7 9 5),如,: a5,4 = 9,k = 3*(5-1) + 4-5= 11,故,:sa11 = 9,5.3.2,稀疏矩阵,假设,m,行,n,列,的矩阵含,t,个非零元素,，则称,为,稀疏因子,。,通常认为,0.05,的矩阵为稀疏矩阵。,稀疏矩阵的压缩存储方法,:,一、三元组顺序表,二、行逻辑链接的顺序表,三、 十字链表,#define,MAXSIZE 12500,typedef struct ,int,i, j;,/,该非零元的行下标和列下标,ElemType e;,/,该非零元的值,Triple; /,三元组类型,一、三元组顺序表,typedef struct ,Triple dataMAXSIZE + 1;,int,mu, nu, tu;,TSMatrix; /,稀疏矩阵类型,6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,i j e,0 1 2 3 4 5 6 7 8,T,如何求转置矩阵？,用常规的二维数组表示时的算法,其时间复杂度为,: O(mu,nu),for,(col=1; col=nu; +col),for,(row=1; row=mu; +row),Tcolrow = Mrowcol;,6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,i j e,0 1 2 3 4 5 6 7 8,i j e,7,6,8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,0 1 2 3 4 5 6 7 8,?,M.data,T.data,解决思路：,只要做到,将矩阵行、列值互换；,将每个三元组中的,i,和,j,相互调换；,重排三元组次序，使,T.data,中元素以,N,的行(,M,的列)为主序,方法一：按,M,的列序转置,按,T.data,中三元组次序依次在,M.data,中找到相应的三元组进行转置，即按照矩阵,M的列序,来进行置换。,为找到,M,中每一列所有非零元素，需对其三元组表,M.data,从第一行起扫描一遍。由于,M.data,中以,M,行序为主序，所以由此得到的恰是,T.data,中应有的顺序,。,6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,i j e,0 1 2 3 4 5 6 7 8,M.data,7,6,8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,i j e,0 1 2 3 4 5 6 7 8,T.data,q,p,p,p,p,p,p,p,p,q,q,q,q,p,p,p,p,p,p,p,p,col=1,col=2,Status TransposeSMatix(TSMatrix M,TSMatrix &T),/,采用三元组表存储表示，求稀疏矩阵,M,的转置矩阵,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 (M.datap.j = col),T.dataq.i = M.datap.j;,T.dataq.j = M.datap.i;,T.dataq.e = M.datap.e;,+q; ,return OK;,/TransposeSMatrix,T(n)=O(nu*tu),方法二：快速转置,按,M.data,中三元组次序转置，转置结果放入,T.data,中恰当位置。,此法关键是要预先确定,M,中每一列第一个非零元在,T.data,中位置，为确定这些位置，转置前应先求得,M,的每一列中非零元个数。,实现：,设两个数组,numcol,：表示矩阵,M,中第,col,列中非零元个数,cpotcol,：,指示,M,中第,col,列第一个非零元在,T.data,中位置,显然有：,cpot1=1;,cpotcol=cpotcol-1+numcol-1; (2,col M.nu),6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,i j e,0 1 2 3 4 5 6 7 8,M.data,i j e,0 1 2 3 4 5 6 7 8,T.data,col,numcol,cpotcol,1,1,2,2,3,2,3,5,2,4,7,1,5,8,0,6,8,1,7,9,0,7,6,8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,p,p,p,p,p,p,p,p,4,6,2,9,7,5,3,6,7,8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,i j e,0 1 2 3 4 5 6 7 8,for,(col=1; col=M.nu; +col),numcol = 0;,for,(t=1; t=M.tu; +t),+numM.datat.j;,cpot1 = 1;,for,(col=2; col=M.nu; +col),cpotcol = cpotcol-1,+ numcol-1;,Col,1 2 3 4 5 6 7,Numcol,cpotcol,t,1,t,1,t,1,t,1,t,2,t,2,t,2,t,1,0 0,1,3,5,7,8,8,9,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.datat.j;,cpot1 = 1;,for,(col=2; col=M.nu; +col),cpotcol = cpotcol-1 + numcol-1;,for,(p=1; p=M.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;, / FastTransposeSMatrix,T(n)=O(nu+tu),T(n)=O(mu*nu),三元组顺序表又称,有序的双下标法,，它的特点是，非零元在表中按行序有序存储，因此,便于进行依行顺序处理的矩阵运算,。然而，若需,随机,存取某一行中的非零元，则需从头开始进行查找。,#define,MAXMN 500,typedef struct ,Triple dataMAXSIZE + 1;,/,非零元三元组表,int rposMAXMN + 1;,/,各行第一个非零元的位置表,int,mu, nu, tu;,RLSMatrix;,/,行逻辑链接顺序表类型,二、行逻辑链接的顺序表,M=,N=,Q=,Q = M, N,1 1 3,1 4 5,i j e,1 2 3 4,3 1 2,2 2 -1,M.data,1 2 2,2 1 1,i j e,1 2 3 4,3 2 4,3 1 -2,N.data,2 1 -1,i j e,1 2 3 4,Q.data,p,arow 1 2 3,rposarow,1 3 4,brow 1 2 3 4,rposbrow,1 2 3 5,ccol 1 2,ctemp,t,1,tp,q,6,p,1 2 6,tp,p,2,t,q,-1,tp,=5,p,1,t,q,4,3 2 4,三、 十字链表,3 0 0 5,0 -1 0 0,2 0 0 0,1,1,3,1,4,5,2,2,-1,3,1,2,Type struct OLNode int i,j; int e; struct OLNode *right,*down; OLNode; *OLink;Type struct OLink *rhead,*chead; int mu,nu,tu; CrossList;,5.4,广义表的类型定义,ADT Glist ,数据对象,：,D,e,i,| i=1,2,.,n; n0;,e,i,AtomSet,或,e,i,GList,AtomSet,为某个数据对象,数据关系：,LR,| e,i-1,e,i,D, 2in, ADT,Glist,基本操作:,广义表是,递归,定义的,线性结构,，,LS = (,1,2,n,),其中：,i,或为原子 或为广义表,例如,:,A = ( ),F = (d, (e),D = (a,(b,c), F),C = (A, D, F),B = (a, B) = (a, (a, (a, ) ) ),广义表是一个,多层次,的,线性结构,例如：,D=(,E,F,),其中:,E=(,a,(,b,c,),),F=(,d,(,e,),),D,E,F,a,( ),d,( ),b,c,e,广义表,LS = (,1,2, ,n,),的,结构特点,:,1),广义表中的数据元素有相对,次序,；,2),广义表的,长度,定义为最外层包含元素个数；,3),广义表的,深度,定义为所含括弧的重数；,注意：“原子”的深度为,0,“空表”的深度为,1,4),广义表可以,共享,；,5),广义表可以是一个,递归,的表。,递归表的深度是无穷值，长度是有限值,。,6),任何一个非空广义表,LS = (,1,2, ,n),均可分解为,表头,GetHead(LS) =,1,和,表尾,GetTail(LS) = (,2, ,n),两部分。,例如,:,D = ( E, F ) = (a, (b, c),，,F ),GetHead(,D,) =,E,GetTail(,D,) =,( F ),GetHead(,E,) =,a,GetTail(,E,) =,( ( b, c) ),GetHead(,( b, c),) =,( b, c),Get Tail(,( b, c),) =,( ),GetHead(,( b, c),) =,b,GetTail(,( b, c),) =,( c ),GetHead(,( c ),) =,c,GetTail(,( c ),) =,( ),练习,求下列广义表操作的结果：,（,1,）,GetHead(,(p, h, w),);,（,2,）,GetTail(,(a ,b) ,(c ,d),);,（,3,）,GetHead ( GetTail ( (a,b),(c,d) ) ),。,结构的创建和销毁,InitGList(,&,L); DestroyGList(,&,L);,CreateGList(,&,L, S); CopyGList(,&,T, L);,基本操作,状态函数,GListLength(L); GListDepth(L);,GListEmpty(L); GetHead(L); GetTail(L);,插入和删除操作,InsertFirst_GL(,&,L, e);,DeleteFirst_GL(,&,L,&,e);,遍历,Traverse_GL(L, Visit();,5.5,广义表的表示方法,通常采用头、尾指针的链表结构,表结点,:,原子结点：,tag=1 hp tp,tag=0 data,链表存储表示,Typedef enumATOM,LISTElemTag;/ATOM=0:,原子，,LIST=1,：子表,Typedef struct GLNode,ElemTag tag;/,区分原子或子表的公共标记,union/,原子,/,表结点的联合部分,AtomType atom;/,原子结点值域,structstruct GLNode *hp,*tp;ptr;/,表结点指针域,;,*Glist;,（,1,） 表头、表尾分析法：,构造存储结构的两种分析方法,:,若表头为原子，则为,空表,ls=NIL,非空表,ls,tag=1,指向表头的指针,指向表尾的指针,tag=0 data,否则，依次类推。,L = ( a, ( x, y ), ( ( x ) ) ),a,( x, y ),(,),1,L,L = ( ),0 a,1,1,1,1,1,0 x,( ),x,练习,按教科书,5.5,节中图,5.8,所示结点结构，画出下列广义表的存储结构图，并求它的深度。,（,1,）,( ( ( ) ) , a , ( ( b , c ) , ( ) , d ) , ( ( ( e ) ) ) ),（,2 ( ( ( ( a ) , b ) ) , ( ( ( ) , d ) , ( e , f ) ) ),（,2,） 子表分析法：,若子表为原子，则为,空表,ls=NIL,非空表,指向子表,1,的指针,tag=0 atom,否则，依次类推。,指向子表,2,的指针,指向子表,n,的指针,1,1,1,ls,1,tag=1 hp tp,例如,:,LS=( a, (x,y), (x) ),0,a,1,1,ls,1,0,x,0 y,1,0,x,练习：,画,出下列广义表两种存储结构图,LS=(),A,(B,(C,D),(E,F),【,南京航空航天大学 （,10,分）,】,1.,了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。,2.,掌握对特殊矩阵进行压缩存储时的下标变换公式。,3.,了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。,本章学习要点,4.,掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为,n,个子表。,Thats all for this chapter! Thank you for listening!,