数据结构 第5章课件.ppt

《数据结构 第5章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章数组和广义表5.1数组的定义数组定义ADTArray{数据对象：ji=0,...,bi-1,i=1,2,...,n,D={aj1j2...jn

2、n>0,aj1j2...jnElemSet}数据关系：R={R1,R2,...,Rn}Ri={

3、aj1..ji....jn,aj1...ji+1...jnD}基本操作：InitArray(&A,n,bound1,...boundn)DestroyArray(&A)Value(A,&e,index1,...indexn)Assign(&A,e,index

4、1,...indexn)}ADTArray二维数组可以将二维数组看成一个定长的线性表，它的每个数据元素也是一个定长线性表。A=(a0,a1,...,ap);ai=(a0j,a1j,...am-1j)typedefElemTypeArray2[m][n];typedefElemTypeArray1[n];typedefArray1Array2[m];(0,0)(m-1,n-1)二维数组，m行，n列元素个数：m*n每个元素由行、列两个关系约束5.2数组的顺序表示和实现数组的顺序存储结构以行为主序例：A[3][2]A00,A01,A10,A11,A20,A21LOC[i

5、][j]=LOC[0][0]+(n*i+j)*LL为每个元素占用的空间单元数数组的顺序存储结构以列为主序例A[3][2]A00,A10,A20,A01,A11,A21LOC[i][j]=LOC[0][0]+(m*j+i)*LL为每个元素占用的空间单元数假设：b1,b2,b3,...bn为每一维的元素个数LOC[j1,j2,...jn]=LOC[0,0,...,0]+(b2*b3...*bn*j1+b3*...*bn*j2,+...+bn*jn-1+jn)L=LOC[0,0,...,0]+()L=LOC[0,0,...,0]+其中:cn=L,ci-1=bi*ci1<

6、i<=n三维数组A[6][8][4]共6*8*4=192个元素假设：每个元素占据L=1个存储单元b1=6,b2=8,b3=4,L=1则：c3=L=1c2=c3*b3=c3*4=1*4=4c1=c2*b2=4*8=4*8=32A[3][4][2]=0+32*3+4*4+2=114#include//可变长参数#defineMAX_ARRAY_DIM8typedefstruct{ElemType*base;//数据元素基址intdim;//数组维数int*bounds;//每一维的元素个数int*constants;//映像函数常数}StatusI

7、nitArray(Array&A,intdim,...){if(dim<1

8、

9、dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=newint[dim];if(!A.bounds)exit(OVERFLOW);elemtotal=1;va_start(ap,dim);//初始化参数列表for(i=0;i

10、a_end(ap);//复位A.base=newElemType[elemtotal];if(!A.base)exit(OVERFLOW);A.constants=newint[dim];if(!A.constants)exit(OVERFLOW);A.constants[dim-1]=1;//计算Cifor(i=dim-2;i>=0;i--)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}StautsDestroyArray(Array&A){if(!A.base)returnERROR;delet

11、e[]A.base;A.base=NULL;if(!A.bounds)returnERROR;delete[]A.bounds;A.bounds=NULL;if(!contants)returnERROR;delete[]A.contants;A.contants=NULL;returnOK;}StatusLocate(ArrayA,va_listap,int&off){off=0;for(i=0;i

12、

13、ind>=A.bounds[i])returnOVERFLOW;off+=A.con

14、stant