数据结构(c语言版)严尉敏编第5章.ppt

5.1 数组的类型定义;5.1 数组的类型定义;typedef Elemtype array2[m][n]; 等价于： typedef Elemtype array1[n]; typedef array1 array2[m]; ;ADT Array { 数据对象： D＝{aj1,j2, ...,,ji,jn| ji =0,...,bi -1, i=1,2,..,n } 数据关系： 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, i=2,...,n } 基本操作: } ADT Array ;InitArray(A, n, bound1, ..., boundn) 操作结果：若维数 n 和各维长度合法，构造相应的数组A，并返回OK。;Assign(A, e, index1, ..., indexn) 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。 操作结果：若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。;二维数组的抽象定义:;5.2 数组的顺序表示和实现;??按行序为主序存放;二维数组A中任一元素aij 的存储位置 LOC(i,j) = LOC(0,0) + (b2×i＋j)× L; 推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系：; 容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，ci 是常数。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。;下面是数组顺序存储表示和实现;Status InitArray(Array A, int dim,…) { //若维数 dim 和各维长度合法，构造相应的数组A，并返回OK if(dim1||dim MAX_ARRAY_DIM ) return ERROR; A.dim=dim; A.bounds=(int*)malloc(dim*sizeof(int)); if(! A.bounds) exit(OVERFLOW); //若各维长度合法,则存入A.bounds,并求出元素总数elemtotal elemtotal=1; va_start(ap,dim);//ap为va_list类型,存放变长参数表信息的数组 for(i=0;idim;i++) { A.bounds[i]=va_arg(ap,int);; if(A.bounds[i]0) return OVERFLOWER; elemtotal*= A.bounds[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; //L=1,指针的增减以元素大小为单位 for(i=dim-2;i=0;i--) {A.constants[i]= A.bounds[i+1] *A.constants[i+1]; return OK; }// InitArray;Status DestroyArray(Array A) { //销毁数组A if(!A.base) return ERROR; free(A.base); A.base=NULL; if(!A.bounds) return ERROR; free(A.bounds); A.bounds=NULL; if(!A.constants) return ERROR; free(A.constants); A.constants=NULL; return OK; }// DestroyArray ;Status Locate(Array A , va_list ap , int off ) { //若ap所指下标合法,则求出元素在数组中的相对位置off // 最终off带回在存储该元素时已经存储的元素个数;Status Value(Array A, ElemType e ,…)