多维数组和广义表课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,1,5.2,多维数组,5.3,矩阵,的,压缩存储,5.4,广义表,5.5,实例分析与实现,5.1,应用实例,2,应用实例：,魔方阵,魔方阵是一个古老的智力问题，它要求在一个,N,N,的方阵中填入,1,N,2,的数字（,N,要求为奇数），使得每一行、每一列、每条对角线的累加和都相等。,3,5.2,多维数组,定义,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,可看成是一种特殊的线性表，其特殊在,于表中的,数据元素本身也是一个线性表,。,数组是,一组有固定个数的元素的集合,。,4,类型特点,:,1,）不,考虑插入和删除操作；,2,）数组是多维的结构，而存,储空间是一个一维的结构。,5.2,多维数组,5,运算,获得特定位置的元素值；,修改特定位置的元素值。,主要操作是,数据元素的定位,，即给定元素,的下标，得到该元素在计算机中的存放位置。,其本质是,地址计算问题,。,有两种顺序映象的方式,:,以行序为主序；,以列序为主序。,5.2,多维数组,6,以行序为主序,例如：,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,5.2,多维数组,7,以列序为主序,例如：,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,5.2,多维数组,8,三维数组,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,数 据 结 构 与 算 法,5.2,多维数组,9,推广到一般情况，可得到,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,5.2,多维数组,10,例如：,设有二维数组,A1020,，其每个元素占,2,个字节，第一个元素,A,1,1,的存储地址为,100,，,则,按行优先,顺序存储时元素,A,5,6,的存储地址为,?,若,按列优先,顺序存储时元素,A,5,6,的存储地址为,?,A,5,6,=,100,+,(5-1)*20+(6-1),*2,=270,按行优先,按列优先,A,5,6,=,100,+,(6-1)*10+(5-1),*2,=208,5.2,多维数组,11,5.3,矩阵的压缩存储,特殊矩阵,三角矩阵,带状矩阵,稀疏矩阵,三元组顺序表,十字链表,12,第,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,数 据 结 构 与 算 法,5.3,矩阵的压缩存储,13,特殊矩阵：,三角矩阵,上三角矩阵,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,5.3,矩阵的压缩存储,14,第,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,数 据 结 构 与 算 法,5.3,矩阵的压缩存储,15,稀殊矩阵：,稀疏因子：,设在,m*n,的矩阵中，有,t,个非零元素，令,称,为矩阵的,稀疏因子,。通常认为,=0.3,时为稀疏矩阵。,n,m,t,=,d,数 据 结 构 与 算 法,5.3,矩阵的压缩存储,16,稀殊矩阵：,三元组顺序表,三元组也是采取按,行,进行存储！,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,数 据 结 构 与 算 法,5.3,矩阵的压缩存储,17,稀殊矩阵：,三元组顺序表,数据类型定义,#define MAXSIZE 1000,typedef struct,int row,col;,ElementType e ;,Triple;,typedef struct,Triple,dataMAXSIZE,+1,;,int m,n,len;,TSMatrix;,5.3,矩阵的压缩存储,18,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-len0),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(jA.len)break;,22,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.coldatai.row=A.datamin.col;,B-datai.col=A.datamin.row;,B-datai.e=A.datamin.e;,i+;,A.datamin.col=A.n+1;,23,稀殊矩阵：,三元组顺序表,的转置运算,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,一次定位快速转置,5.3,矩阵的压缩存储,24,稀殊矩阵：,三元组顺序表,的转置运算,-,-,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 2 -7,3 1 36,3 4 28,1 5 -5,i,j,v,i,j,v,2,1 14,2,2 -7,1,3 36,4,3 28,5,1 -5,5.3,矩阵的压缩存储,25,稀殊矩阵：,三元组顺序表,的转置运算,一次定位快速转置,算法步骤：,a.,扫描矩阵,A,的三元组表，统计出,A,的每一列的,非零元素的个数,，存放到数组,numcol,中,（,numcol,存放,M,第,col,列的非零元素个数）。,b.,计算转置矩阵,B,的每一行在三元组表中的开始,位置,，并存放到数组,positioncol,中，,（,positioncol,存放,T,第,col,行开始位置）。,c.,再次扫描矩阵,A,的三元组表，,根据非零元素的列号,col,，,确定它转置后的行号,，,查,position,表，按查到的位置直,接将该项存入转置三元组表,B,中,并,修改,positioncol,将,其,指向该行下一个元素的存储位置,(,positioncol +,),。,5.3,矩阵的压缩存储,26,稀殊矩阵：,三元组顺序表,的转置运算,一次定位快速转置,算法实现：,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,5.3,矩阵的压缩存储,27,稀殊矩阵：,三元组顺序表,的转置运算,一次定位快速转置,算法实现：,b.p,osition1=1;,for(col=2;col=A.n;col+),positioncol=positioncol-1+numcol-1;,col,1,2,3,4,5,numcol,0,0,0,0,0,1,1,2,1,1,positioncol,1,2,4,4,5,1 2 14,2 2 -7,3 1 36,3 4 28,1 5 -5,i,j,v,i,j,v,2,1 14,2,2 -7,1,3 36,4,3 28,5,1 -5,5.3,矩阵的压缩存储,28,稀殊矩阵：,三元组顺序表,的转置运算,一次定位快速转置,算法实现：,for(p=1;pdataq.row=A.datap.col;,B-dataq.col=A.datap.row;,B-dataq.e=A.datap.e;,positioncol+;,col,1,2,3,4,5,numcol,0,0,0,0,0,1,1,2,1,1,positioncol,1,2,4,4,5,1 2 14,2 2 -7,3 1 36,3 4 28,1 5 -5,i,j,v,i,j,v,2,1,14,3,5,1,-5,2,2,-7,4,1,3,36,2,4,3,28,6,5,完整,P100,5.3,矩阵的压缩存储,29,稀殊矩阵：,三元组顺序表,的转置运算,一次定位快速转置,算法实现：,该算法的总的循环次数为：,A.n+A.len+A.n-1+A.len,=2(A.n+A.len)-1,时间复杂度为,：,O(A.n+A.len),即使非零元个数,A.len,与,A.m*A.n,同数量级，其时间,复杂度为,O(A.m*A.n),，,与经典算法时间复杂度相同。,5.3,矩阵的压缩存储,30,稀殊矩阵：,十字链表,的存储表示,一个结点除了数据域,(i,j,elem),之外，还应该用,两,个方向的指针（,right,down),，分别指向行和列。