数组的学习与应用（数据结构）
一、数组的定义
[indent]几乎所有的程序设计语言都把数组类型设定为固有类型。
以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。
数组的定义：
ADT Array{
数据对象:j[size=-2]i[/size]=0,...,b[size=-2]i[/size]-1,i=1,2,...,n;
[indent][indent]D={[size=+1]a[/size][size=-2]j1j2...jn[/size]|n(>0)称为数组的维数,b[size=-2]i[/size]是数组第i维的长度,j[size=-2]i[/size]是数组元素的第i维下标,[size=+1]a[/size][size=-2]j1j2...jn[/size] (-ElemSet}
[/indent][/indent]数据关系:R={R[size=-2]1[/size],R[size=-2]2[/size],...R[size=-2]n[/size]|
[indent][indent]Ri={<a[size=-2]j1...ji...jn[/size],a[size=-2]j1...ji+1 ...jn[/size]>|
[indent][indent]0<=j[size=-2]k[/size]<=b[size=-2]k-1[/size],1<=k<=n且k<>i,
0<=j[size=-2]i[/size]<=b[size=-2]i-2[/size],a[size=-2]j1...ji...jn[/size],
a[size=-2]j1...ji+1 ...jn[/size](-D,i=2,...n}
[/indent][/indent][/indent][/indent]基本操作:
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
列向量的一维数组:
[table=75%][tr][td=1,1,21%][size=+4]a[/size]00[/td][td=1,1,21%][size=+4]a[/size]01[/td][td=1,1,21%][size=+4]a[/size]02[/td][td=1,1,12%]...[/td][td=1,1,25%][size=+4]a[/size]0,n-1[/td][/tr][tr][td=1,1,21%][size=+4]a[/size]10[/td][td=1,1,21%][size=+4]a[/size]11[/td][td=1,1,21%][size=+4]a[/size]12[/td][td=1,1,12%]...[/td][td=1,1,25%][size=+4]a[/size]1,n-1[/td][/tr][tr][td=1,1,21%]...[/td][td=1,1,21%]...[/td][td=1,1,21%]...[/td][td=1,1,12%]...[/td][td=1,1,25%]...[/td][/tr][tr][td=1,1,21%][size=+4]a[/size]m-1,0[/td][td=1,1,21%][size=+4]a[/size]m-1,1[/td][td=1,1,21%][size=+4]a[/size]m-1,2[/td][td=1,1,12%]...[/td][td=1,1,25%][size=+4]a[/size]m-1,n-1[/td][/tr][/table]行向量的一维数组:
把二维数组中的每一行看成是一个数据元素,这些数据元素组成了一个一维数组A.
[table=81%][tr][td=1,1,18%][size=+4]A[/size]0[/td][td=1,4,82%][table=94%][tr=#ffcccc][td=1,1,21%][size=+4]a[/size]00[/td][td=1,1,21%][size=+4]a[/size]01[/td][td=1,1,21%][size=+4]a[/size]02[/td][td=1,1,11%]...[/td][td=1,1,26%][size=+4]a[/size]0,n-1[/td][/tr][tr][td=1,1,21%][size=+4]a[/size]10[/td][td=1,1,21%][size=+4]a[/size]11[/td][td=1,1,21%][size=+4]a[/size]12[/td][td=1,1,11%]...[/td][td=1,1,26%][size=+4]a[/size]1,n-1[/td][/tr][tr][td=1,1,21%]...[/td][td=1,1,21%]...[/td][td=1,1,21%]...[/td][td=1,1,11%]...[/td][td=1,1,26%]...[/td][/tr][tr=#ffcccc][td=1,1,21%][size=+4]a[/size]m-1,0[/td][td=1,1,21%][size=+4]a[/size]m-1,1[/td][td=1,1,21%][size=+4]a[/size]m-1,2[/td][td=1,1,11%]...[/td][td=1,1,26%][size=+4]a[/size]m-1,n-1[/td][/tr][/table][/td][/tr][tr][td=1,1,18%][size=+4]A[/size]1[/td][/tr][tr][td=1,1,18%]...[/td][/tr][tr][td=1,1,18%][size=+4]A[/size]m[/td][/tr][/table]
[/indent]二、数组的顺序表示和实现
[indent]以行序为主序的存储方式:
[table=93%][tr][td=1,1,4%][align=center]a[size=-2]00[/size][/align][/td][td=1,1,4%][align=center]a[size=-2]01[/size][/align][/td][td=1,1,4%][align=center]a[size=-2]02[/size][/align][/td][td=1,1,5%][align=center]...[/align][/td][td=1,1,9%][align=center]a[size=-2]0,n-1[/size][/align][/td][td=1,1,4%][align=center]a[size=-2]10[/size][/align][/td][td=1,1,4%][align=center]a[size=-2]11[/size][/align][/td][td=1,1,4%][align=center]a[size=-2]12[/size][/align][/td][td=1,1,6%][align=center]...[/align][/td][td=1,1,8%][align=center]a[size=-2]1,n-1[/size][/align][/td][td=1,1,6%][align=center]...[/align][/td][td=1,1,8%][align=center]a[size=-2]m-1,0[/size][/align][/td][td=1,1,8%][align=center]a[size=-2]m-1,1[/size][/align][/td][td=1,1,9%][align=center]a[size=-2]m-1,2[/size][/align][/td][td=1,1,6%][align=center]...[/align][/td][td=1,1,11%][align=center]a[size=-2]m-1,n-1[/size][/align][/td][/tr][/table]数组的顺序存储表示和实现:
#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){
[indent]A.bounds[i]=va_arg(ap,int);
if(A.bounds[i]<0) return UNDERFLOW;
elemtotal*=A.bounds[i];
[/indent]}
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)
[indent]A.constants[i]=A.bounds[i+1]*A.constants[i+1];
[/indent]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){
[indent]ind=va_arg(ap,int);
if(ind<0||ind>=A.bounds[i]) return OVERFLOW;
off+=A.constants[i]*ind;
[/indent]}
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;
}
[/indent]三、小结
[indent]数组的存储方式。
数组的基本操作种类。
[/indent]