数据结构数组 和广 义表.ppt

《数据结构数组 和广 义表.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,...in

4、dexn)Assign(&A,e,index1,...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数组的顺序表示和实现数组的顺序存储

5、结构以行为主序例：A[3][2]A00,A01,A10,A11,A20,A21LOC[i][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,+...+b

6、n*jn-1+jn)L=LOC[0,0,...,0]+()L=LOC[0,0,...,0]+其中:cn=L,ci-1=bi*ci1//可变长参数#defineMAX_ARRAY_DIM8typedefstruc

7、t{ElemType*base;//数据元素基址intdim;//数组维数int*bounds;//每一维的元素个数int*constants;//映像函数常数}StatusInitArray(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、

11、or(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;delete[]A.base;A.base=NULL;if(!A.bounds)returnERROR;delete[]A.bounds;A.bounds=NULL;if(!contants)returnERROR;delete[]A.contants;A.contant

12、s=NULL;returnOK;}StatusLocate(ArrayA,va_listap,int&off){off=0;for(i=0;i

13、

14、ind>=A.bounds[i])returnOVERFLOW;off+=A.constant