首页 / 软件开发 / 数据结构与算法 / 数据结构教程 第十八课 数组的顺序表示与实现

数据结构教程 第十八课 数组的顺序表示与实现2007-05-17教学目的： 掌握数组的定义,数组的顺序表示方法

教学重点： 数组的定义,数组的顺序表示方法

教学难点： 数组的顺序表示方法

授课内容：

一、数组的定义

几乎所有的程序设计语言都把数组类型设定为固有类型。

以抽象数据类型的形式讨论数组的定义和实现，可以让我们加深对数组类型的理解。

数组的定义：

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

二、数组的顺序表示和实现

以行序为主序的存储方式:

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

数组的顺序存储表示和实现:

#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;

}

三、小结

数组的存储方式。

数组的基本操作种类。