第05章数组和广义表1.ppt

5.1 数组的定义 数组的定义 从逻辑结构上，数组可以看成是一般线性表的扩充。 一维数组即为线性表。 二维数组：其数据元素是一维数组（线性表）的线性表。 ADT Array{ 数据对象：ji=0,…,bi-1,i=1,2,…,n D={aj1j2…jn|n(0)称为数组的维 数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1j2…jn∈ElemSet} 数据关系：R={R1,R2,…,Rn} Ri={aj1…ji…jn,aj1…ji+1…jn| 0≤jk≤bk-1,1≤k≤n 且k≠i,0≤ji≤bi-2, aj1…ji…jn,aji…ji+1…jn∈D,i=2,…,n} 数组的顺序存储表示和实现 1.数组的顺序存储表示 #include stdarg.h #define MAX_ARRAR_DIM 8 typedef struct{ ElemType *base; int dim; int *bounds; int *constants; }Array 2.数组基本运算的实现 1）数组初始化：InitArray(Array A,int dim,…) 数组初始化是指对于给定合法的数组维数及各维长度，分配数组空间，建立对应数组的信息。因为数组维数和各维长度可以在合法的范围内任意确定，所以实现函数的参数表中需要引用变长参数表符号“…”。实际调用时，根据数组维数dim的值，确定参数“…”处有几个实参。 例如当dim=3时，表示“…”处有3个参数，分别表示各维的长度。 [算法设计] 首先设置变量elemtotal存放数组元素的总数；设置一个va_list类型的变量ap指示有效变长参数表信息。然后需要完成以下功能： （1）若数组维数合法，则分配维界数组空间A.bounds；若各维长度合法，则依次存入该数组，并求出A数组的元素总数存入变量elemtotal。 （2）根据elemtotal的值分配数组元素空间A.base。 （3）分配数组映像函数常量数组空间A.constants,计算各常量值ci，并存入该数组。 [算法描述] int InitArray(Array A,int dim,…) {int i,elemtotal=1; va_list ap; if(dim1||dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim*sizeof(int)); if(!A.bounds) exit (OVERFLOW); va_start(ap,dim); for(i=0;idim;++i) {A.bounds[i]=va_arg(ap,int); if(A.bound[i]0) return ERROR; elemtotal*=A.bound[i]; } va_end(ap); A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType)); if(!A.base) exit (OVERFLOW); A.constants=(int *)malloc(dim *sizeof(int)); if(!A.constants) exit(overflow); A.constants[dim-1]=1; for(i=dim-2;i=0;--i) A.constants[i]=A.bound[i+1]*A.constants[i+1 ] return OK; } 例如：初始化数组A[3][4][2] 2)销毁数组 销毁数组即回收已分配的数组空间、维数数组空间及常量ci数组空间，并设相应指针变量为NULL。 [算法描述] int Destroy Array(Array A) {if(A.base) {free(A.base);A.base=NULL;} else return ERROR; if(A.bounds) {free(A.bounds);A.bounds=NULL;} else return ERROR; if(A.constants) {free(A.constants);A.constants=NULL;} else return ERROR; return OK; } 3)求数组元素的相对地址 利用已给的求地址公式求指定元素在数组中的相对地址。va_list数组中存放的数组A中所有元素各维下标的值，ap为va_list类型的变量，用于遍历va_list表中的参数。 [算法描述] int Locata(Array A