第十八课
本课主题:数组的顺序表示与实现
教学目的:掌握数组的定义,数组的顺序表示方法
教学重点:数组的定义,数组的顺序表示方法
教学难点:数组的顺序表示方法
授课内容:
一、数组的定义
几乎所有的程序设计语言都把数组类型设定为固有类型。
以抽象数据类型的形式讨论数组的定义和实现,可以让我们加深对数
组类型的理解。
数组的定义:
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;
}
三、小结
数组的存储方式。
数组的基本操作种类。
回目录上一课下一课
第十九课
本课主题:实验四 串的实现实验
教学目的:掌握PASCAL
串类型的实现方法
教学重点:串的操作
教学难点:串的联接操作
授课内容:
一、PASCAL串类型的存储表示:
#define MAXSTRLEN 255
typedef char
SString[MAXSTRLEN+1];
二、串的操作:
1、串的联接
mystrcat(SString
s1,SString
s2,SString t);
2、求子串
mysubstr(SString t,int
pos,int
len,SString sub);
3、子串定位
mystrindex(SString
t,SString
sub,int *index);
回目录上一课下一课