教学目的： 掌握数组的定义,数组的顺序表示方法 教学重点： 数组的定义,数组的顺序表示方法 教学难点： 数组的顺序表示方法 授课内容： 一、数组的定义 几乎所有的程序设计语言都把数组类型设定为固有类型。 以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。 数组的定义： 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, aj1...ji+1 ...jn(-D,i=2,...n}
基本操作: InitArray(&A,n,bound1,...,boundn) 若维数和各维长度合法,则构造相应的数组A,并返回OK. DestroyArray(&A) 操作结果:销毁数组A. Value(A,&e,index1,...,indexn) 初始条件:A是n维数组,e为元素变量,随后是n个下标值. 操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK. Assign(&A,e,index1,...,indexn) 初始条件:A是n维数组,e为元素变量,随后是n个下标值. 操作结果:若下标不超界,则将e的值赋给 所指定的A的元素,并返回OK. }ADT Array 列向量的一维数组: | a00 | a01 | a02 | ... | a0,n-1 | | a10 | a11 | a12 | ... | a1,n-1 | | ... | ... | ... | ... | ... | | am-1,0 | am-1,1 | am-1,2 | ... | am-1,n-1 |
行向量的一维数组: 把二维数组中的每一行看成是一个数据元素,这些数据元素组成了一个一维数组A. | A0 | | a00 | a01 | a02 | ... | a0,n-1 | | a10 | a11 | a12 | ... | a1,n-1 | | ... | ... | ... | ... | ... | | am-1,0 | am-1,1 | am-1,2 | ... | am-1,n-1 |
| | A1 | | ... | | Am |
二、数组的顺序表示和实现 以行序为主序的存储方式: 数组的顺序存储表示和实现: #include<stdarg.h> #define MAX_ARRAY_DIM 8 typedef struct { ElemType *base; int dim; int *bounds; int *constants; }Array; Status InitArray(Array &A,int dim,...); Status DestroyArray(Array &A); Status Value(Array A,ElemType &e,...); Status Assign(Array &A,ElemType e,...); 基本操作的算法描述: Status InitArray(Array &A,int dim,...){ if(dim<1||dim>MAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim *sizeof(int)); if(!A.bounds) exit(OVERFLOW); elemtotal=1; va_start(ap,dim); for(i=1;i<dim;++i){ A.bounds[i]=va_arg(ap,int); if(A.bounds[i]<0) return UNDERFLOW; 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; for(i=dim-2;i>=0;--i) A.constants[i]=A.bounds[i+1]*A.constants[i+1];
return OK; } Status DestoyArray(Array &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.constatns) return ERROR; free(A.constants); A.constants=NULL; return OK; } Status Locate(Array A,va_list ap,int &off){ off=0; for(i=0;i<A.dim;++i){ ind=va_arg(ap,int); if(ind<0||ind>=A.bounds[i]) return OVERFLOW; off+=A.constants[i]*ind;
} return OK; } Status Value(Array A,ElemType &e,...){ va_start(ap,e); if((result=Locate(A,ap,off))<=0 return result; e=*(A.base+off); return OK; } Status Assign(Array &A,ElemType e,...){ va_start(ap,e); if((result=Locate(A,ap,off))<=0) return result; *(A.base+off)=e; return OK; }
三、小结 数组的存储方式。 数组的基本操作种类。
|