数据结构chapter5数组和广义表

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,数 据 结 构,5.1,数组的定义和运算,第,5,章 数组和广义表,5.2,数组的顺序存储和实现,5.3,特殊矩阵的压缩存储,5.4,广义表,1,数 据 结 构,5.1,数组的定义和运算,定义,第,5,章 数组和广义表,mn,m,m,n,n,n,m,A,a,.,a,a,.,.,.,.,a,.,a,a,a,.,a,a,2,1,2,22,21,1,12,11,=,n,m,也可以看成是,m,个行向量,可以看成是 个列向量,n,可看成是一种特殊的线性表，其特殊在,于表中的,数据元素本身也是一个线性表,。,数组是,一组有固定个数的元素的集合,。,2,数 据 结 构,5.1,数组的定义和运算,抽象数据类型定义,第,5,章 数组和广义表,ADT Array,ADT Array,数据对象：,D=a,j1j2,jn,|n,0,称为数组的维数，,j,i,是数组的,第,i,维下标，,1j,i,b,i,b,i,为数组第,i,维的长度，,a,j1j2,jn,ElementSet,数据关系：,R=R,1,R,2,R,n,Ri,=|1j,k,b,k,1kn,且,ki,1j,i,b,i-1,a,j1,ji,jn,a,j1ji+1,jn,D,i=1,n,基本操作：,1.InitArray(A,n,bond1,bondn,)2.Destroy(A),3.GetValue(A,e,index1,indexn,),4.SetValue(A,e,index1,indexn,),3,数 据 结 构,5.2,数组的顺序存储和实现,类型特点,:,第,5,章 数组和广义表,1,）不,考虑插入和删除操作；,2,）数组是多维的结构，而存,储空间是一个一维的结构。,4,数 据 结 构,5.1,数组的定义和运算,运算,第,5,章 数组和广义表,获得特定位置的元素值；,修改特定位置的元素值。,主要操作是,数据元素的定位,，即给定元素,的下标，得到该元素在计算机中的存放位置。,其本质是,地址计算问题,。,有两种顺序映象的方式,:,以行序为主序；,以列序为主序。,5,数 据 结 构,5.2,数组的顺序存储和实现,以行序为主序,第,5,章 数组和广义表,例如：,a,1,2,a,1,1,a,1,3,a,2,1,a,2,2,a,2,3,a,1,2,a,1,1,a,1,3,a,2,1,a,2,2,a,2,3,L,二维数组,A,mxn,中任一元素,a,i,j,的存储位置,LOC(i,j)=LOC(1,1)+(n(i-1),(j-1),称为,基地址,或基址。,L,6,数 据 结 构,5.2,数组的顺序存储和实现,以列序为主序,第,5,章 数组和广义表,例如：,L,二维数组,A,mxn,中任一元素,a,i,j,的存储位置,LOC(i,j)=LOC(1,1)+(m(j-1),(i-1),称为,基地址,或基址。,L,a,1,2,a,1,1,a,1,3,a,2,1,a,2,2,a,2,3,a,2,1,a,1,1,a,1,2,a,2,2,a,1,3,a,2,3,7,数 据 结 构,5.2,数组的顺序存储和实现,第,5,章 数组和广义表,三维数组,A,r mn,中任一元素,a,i,j,k,的存储位置,LOC(i,j,k)=LOC(1,1,1)+(i-1)mn(j-1)n+(k-1)L,j,1,j,2,j,3,代替数组下标,i,j,k,，,并且,j,1,j,2,j,3,的下限分别为,c,1,c,2,c,3,，,上,限为,d,1,d,2,d,3,每个元素占,size,个存储单元。则,a,j1,j2,j3,的,存储位置,LOC(,j,1,j,2,j,3,)=LOC(,c,1,c,2,c,3,)+(j,1,-c,1,)(d,2,-c,2,+1)(d,3,-c,3,+1),(j,2,-c,2,)(d,3,-c,3,+1)+(j,3,-c,3,)size,8,数 据 结 构,5.2,数组的顺序存储和实现,第,5,章 数组和广义表,推广到一般情况，可得到,n,维数,组数据元素存储位置的映象关系：,Loc(Aj,1,j,2,j,n,=Loc(Ac,1,c,2,c,n,)+,i,(,j,i,-c,i,),1,i,n,n,i=1,其中：,i,=size,(d,k,-c,k,+1),1,i,n),n,k=i+1,9,数 据 结 构,5.2,数组的顺序存储和实现,第,5,章 数组和广义表,例如：,设有二维数组,A1020,，,其每个元素占,2,个字节，第一个元素,A,1,1,的存储地址为,100,，,则,按行优先,顺序存储时元素,A,6,6,的存储地址为,?,若,按列优先,顺序存储时元素,A,6,6,的存储地址为,?,A,6,6,=,100,+,(6-1)*20+(6-1),*2,=310,按行优先,按列优先,A,6,6,=,100,+,(6-1)*10+(6-1),*2,=210,10,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,特殊矩阵,三角矩阵,带状矩阵,稀疏矩阵,三元组顺序表,十字链表,11,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,特殊矩阵：,三角矩阵,下三角矩阵,nn,n,n,n,c,c,c,c,c,c,c,c,c,a,a,a,a,a,a,a,a,a,a,3,2,1,33,32,31,22,21,11,LOC(i,j)=,LOC(1,1),+,前,i-1,行非零元素个数,第,i,行中,a,ij,前非零元素的个数,=LOC(1,1),+,i(i-1)/2,+j-1,12,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,特殊矩阵：,三角矩阵,上三角矩阵,LOC(i,j)=,LOC(1,1),+,前,i-1,行非零元素个数,第,i,行中,a,ij,前非零元素的个数,=LOC(1,1)+,(i-1)(2n-i+2)/2,+j-i,nn,n,n,c,c,c,c,c,0,a,a,a,a,a,a,a,a,a,a,.,.,.,.,.,.,.,.,.,3,33,2,23,22,1,13,12,11,n,13,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,特殊矩阵：,带状矩阵,LOC(i,j)=LOC(1,1),+,3(i-1)-1,+j-i+1,=LOC(1,1)+2(i-1)+j-1,n,n,.,.,.,.,.,.,45,44,43,34,33,32,23,22,21,12,11,a,a,a,a,a,a,a,a,a,a,a,14,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,稀殊矩阵：,稀疏因子：,设在,m*n,的矩阵中，有,t,个非零元素，令,称,为矩阵的,稀疏因子,。通常认为,=0.3,时为稀疏矩阵。,n,m,t,=,d,15,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,稀殊矩阵：,三元组顺序表,三元组也是采取按,行,进行存储！,3 0 0 0 0,0 0 0 0 0,0 4 0 0 5,2 0 0 0 0,0 0 0 6 0,1 0 0 0 7,j,v,i,1,1,3,3,2,-4,3,5,5,4,1,2,5,4,6,6,1,1,6,5,7,16,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,稀殊矩阵：,三元组顺序表,数据类型定义,#define MAXSIZE 1000,typedef,struct,int,row,col,;,ElementType,e ;,Triple;,typedef,struct,Triple,dataMAXSIZE,+1,;,int,m,n,len,;,TSMatrix,;,17,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,稀殊矩阵：,三元组顺序表,的转置运算,-,-,0,28,0,0,36,0,0,0,7,0,5,0,0,14,0,-,-,0,0,5,28,0,0,0,0,0,0,7,14,36,0,0,for(row=1;row=m;+row),for(,col,=1;,col,m=A.n;,B-n=A.m;,B-,len,=,A.len,;,if(B-,len,0),j=1;,for(k=1;k=A.n;k+),for(i,=1;idataj.row=,A.datai.col,;,B-,dataj.col,=A.datai.row;,B-dataj.e=A.datai.e;,j+;,if(j,A.len,)break;,21,数 据 结 构,void,TransposeTSMatrix(TSMatrix,A,TSMatrix,*B),int,i,j,min,;,B-m=A.n;,B-n=A.m;,B-,len,=,A.len,;,i=1;,while(i,=,A.len,),min=1;,for(j,=2;j=,A.len;j,+),if(A.dataj.col,datai.row,=,A.datamin.col,;,B-,datai.col,=,A.datamin.row,;,B-,datai.e,=,A.datamin.e,;,i+;,A.datamin.col,=A.n+1;,22,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,稀殊矩阵：,三元组顺序表,的转置运算,M,第,j,列在转置后，形成转置矩阵,T,的第,j,行。,设,M,的第,j,列有,k,个非零元素，如图所示,r,1,j,v,1,r,2,j,v,2,r,k,j,v,k,M,j,r,1,v,1,j,r,2,v,2,j,r,k,v,k,T,一次定位快速转置,23,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,稀殊矩阵：,三元组顺序表,的转置运算,-,-,0,28,0,0,36,0,0,0,7,0,5,0,0,14,0,-,-,0,0,5,28,0,0,0,0,0,0,7,14,36,0,0,1 2 14,2 1 -7,3 1 36,3 3 28,1 5 -5,i,j,v,i,j,v,1,3 36,2,1 14,1,2 -7,3,3 28,5,1 -5,24,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,稀殊矩阵：,三元组顺序表,的转置运算,一次定位快速转置,算法步骤：,a.,扫描矩阵,A,的三元组表，统计出,A,的每一列的,非零元素的个数,，存放到数组,numcol,中,（,numcol,存放,M,第,col,列的非零元素个数）。,b.,计算转置矩阵,B,的每一行在三元组表中的开始,位置,，并存放到数组,positioncol,中，,（,positioncol,存放,T,第,col,行开始位置）。,c.,再次扫描矩阵,A,的三元组表,，,根据非零元素的列号,col,，,确定它转置后的行号,，,查,position,表，按查到的位置直,接将该项存入转置三元组表,B,中,并,修改,positioncol,将,其,指向该行下一个元素的存储位置,(,positioncol,+,),。,25,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,稀殊矩阵：,三元组顺序表,的转置运算,一次定位快速转置,算法实现：,a.,for(col,=1;col=,A.n;col,+),numcol,=0;,for(t=1;t=,A.len;t,+),numA.datat.col,+;,1 2 14,2 2 -7,3 1 36,3 4 28,1 5 -5,i,j,v,col,1,2,3,4,5,numcol,0,0,0,0,0,1,1,2,1,1,26,数 据 结 构,5.3,特殊矩阵的压缩存储,第,5,章 数组和广义表,稀殊矩阵：,三元组顺序表,的转置运算,一次定位快速转置,算法实现：,b.p,osition1=1;,for(col,=2;col=,A.n;col,+