数据结构之数组与广义表课件.ppt

单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,5,章 数组与广义表,5.1,数组,5.1.1 数组的定义,数组是由n个相同类型的元素组成的有序序列，并存储在一个连续的空间中。,数组的特点：,元素类型必须相同；,可对每一个元素随机访问,数组中的元素个数是固定的。,数组分为,一维数组,和,多维数组,一维数组 如:A10 (1行,共10个元素),二维数组 如:B34(3行4列,共12个元素),5.1.2 数组的顺序存储,在计算机中，数组是按一定的规则存储在一个连续的地址空间中.,可以用下标随机的访问该数组的任意一个元素。,计算数组元素存储地址的公式称为,寻址公式,。,设数组为A，每个数组元素占k个存储单元，一旦定义了它的维数和各维的上、下界，就可以得到数组中任一元素的寻址公式。,1.,一维数组的寻址公式,对于一维数组，若其第一个元素的首地址为Loc(,a,0,)，下标为 i 的数组元素Ai的地址为Loc(,a,i,)，,则 Loc(,a,i,)=Loc(,a,0,)+k*i,(0in-1),2.,二维数组的寻址公式,二维数组分为,以行为主序存储,和,以行为主序存储.,在C语言中，采用以,行为主序,存储,在FORTRAN语言中，采用以,列为主序,存储,设二维数组Amn，m、n分别表示数组的行数和列数，用 Loc(aij)表示数组元素Aij的地址.设每个元素占用k个存储单元，则寻址公式为:,若,以行为主序，则,Loc(ai,j)=Loc(a00)+(i*n+j)*k,若,以列为主序,，则,Loc(ai,j)=Loc(a00)+(j*m+i)*k,注:假设数组从0开始编址.,对称矩阵有n*n个元素，但只存储n*(n+1)/2个元素即可.若以,行序,为主序，把下三角中的元素，存储在一个一维数组SAn*(n+1)/2 中，则 Ai,j 和SAk 的对应关系如下：,若,i=j,则Ai,j在下三角中，Ai,j之前共有1+2+i+j=i*(i+1)/2+j 个元素，因此有,k=i*(i+1)/2+j,注:假定矩阵的行和列从0开始,一维数组的编址从0开始.,若,i=j 时,k=i*(i+1)/2+j,当 ij 时,k=n*(n+1)/2,例:元素A3,2,对应的地址,k=3*4/2+2=8,3.稀疏矩阵的压缩存储,若一个m*n矩阵，有s个非0元素，,记 e=s/(m*n),e 称为,稀疏因子,。,当 e,0.05时，则称为稀疏矩阵。,例:,0 2 -1 0 0 0 0,0 0 0 0 0 0 0,-1 0 0 0 0 4 0,M=0 0 0 0 0 0 0,0 8 0 0 0 0 0,5 0 0 0 0 0 0,0 0 0 0 0 9 0,在稀疏矩阵中，非0元素的排列无规律，所以不能采用以前的压缩方法。,可用一个三元组（i,j,Ai,j）来存储非0元素。,其中 i：非0元素的行号,j：非0元素的列号,Ai,j：非0元素的值,如上例矩阵用三元组表示成：,(1,2,2),(1,3,-1),(3,1,-1),(3,6,4),(5,2,8),(6,1,5),(7,6,9),稀疏矩阵的三元组定义如下:,#define maxn,typedef struct,int row;/*行号*/,int col;/*列号*/,elementtype elements;/*元素的值*/,tritype;,typedef struct,int rn;/*矩阵的行数*/,int cn;/*矩阵的列数*/,int tn;/*矩阵的非0元素个数*/,tritype datamaxn;/*非0元素的三元组表*/,tmatrix;,把M压缩后，存储成：,行数 rn,列数 cn,非0数 tn,行号,列号 元素值,1,2,2,1,3,-1,3,1,-1,3,6,4,5,2,8,6,1,5,7,6,9,7,7,7,例:求M的转置矩阵.,s:t:,1,2,2,1,3,-1,3,1,-1,3,6,4,5,2,8,6,1,5,7,6,9,7,7,7,7,7,7,1,3,-1,1,6,5,2,1,2,2,5,8,3,1,-1,6,3,4,6,7,9,基本思想：,把S转置成T，就是把S中的每一个三元组的行号和列号（row 和col）交换，并存储在T中。但是，这样的结果是按列优先存储的稀疏矩阵T，所以，还必须重新排列三元组的顺序。,由于S的列是T的行，因此，应按S中列的顺序扫描,即先扫描第1列所有非0元素，然后第2列所有非0元素,，最后得到的结果就是按行优先顺序存储的。,算法如下：,Inttrmatrix(tmatrix s,t),int i,j,k;,t.rn=;/*列数变行数*/,=s.rn;/*行数变列数*/,t.tn=s.tn；/*非0元素个数赋值*/,if(t.tn!=0),j=0;/*三元组T（目的地）中的位置,for(i=1;i=;i+),/*为列数,for(k=0;khp):,取表尾算法:,Glist gettail(glist p),if(!p|!p-tag),printf(“空表或是一个原子”);,return(null);,Return(p-tp):,返回,求表的深度,Int depth(glist L),tmp=L;,If(tmp=null)Return(1);,If(tmp-tag=0)Return(0);,max=0;,While(tmp!=null),dep=depth(tmp-hp);,If(depmax)max=dep;,tmp=tmp-tp;,return(max+1),