文档介绍：第6章数组与广义表
数组的定义及其基本操作
数组的顺序存储结构
矩阵的压缩存储
广义表的概念
广义表的存储结构表示
广义表的运算
数组的定义及其基本操作 数组的定义
数组(Array):由一组类型相同的数据元素构成的有限序列,且该有限序列存储在一块地址连续的内存单元中
一维数组:数组只有一个下标
二维数组:数组元素都含有两个下标,形如:
二维数组与一维数组的关系:
一个二维数组看成是每个数据元素都是相同类型的一维数组的一维数组
事例:m行n列的二维数组,可以看成是一个线形表 A=(a1,a2,…,ap) (p=m 或 n) 即:
数组的性质:
数组中的数据元素数目固定
数组中的数据元素具有相同的数据类型。
数组中的每个数据元素都和一组唯一的下标值对应。
数组是一种随机存储结构,可随机存取数组中的任意数据元素
随机存:给定一组下标,存一个数据元素到该组下标对应的内存单元中
随机取:从给定的一组下标所对应的内存单元中取出一个数据元素
数组的基本操作
数组的顺序存储结构
数组的顺序存储结构:将数组元素顺序地存放在一片连续的存储单元中
二维数组有两种存储方式:以列序为主序(column major order)的存储方式,如图6-2(a)所示和以行序为主序(row major order)的存储方式,如图6-2(b)所示
地址计算:以行序为主序的存储方式为例
推广到n维数组:
LOC[i,j]=LOC[0,0]+(b2i+j) L
A0 (1)
A1(1)
An-1 (1)
以列序为主序
以行序为主序
/*数组的顺序存储表示*/
typedef struct
{
ElemType *base; /*数组元素初始地址,由初始化操作实现*/
int dim; /*数组的维数*/
int *bounds; /*数组各维的长度,也由初始化操作实现*/
int *const ; /*数组的映象函数常量的初始地址,由初始化操作实现*/
} Array;
/*初始化数组A*/
Status InitialArray(Array &A, int Adim)
/*如果维数Adim和数组各维的长度bounds合法,构造相应的数组A,并返回OK值*/
{ /*如果维数Adim不合法,返回值为error */
if (Adim<1||Adim> MAXDIM)
return error ;
=Adim;
=(int* )malloc(Adim*sizeof(int));
if (!)
exit (overflow);
/*如果各维长度合法,,并求出A的元素总数totalnum*/
totalnum=1;
va_start(ap, Adim); /*ap为存放变长参数表信息的数组,其类型为va_list*/
for(i=0;i<Adim;++i)
{
[i]=va_arg(ap,int);
if([i]<0)
return (underflow);
totalnum* = [i];
}
va_end(ap);
=(ElemType*)malloc(dim*sizeof(ElemType));
if(!) exit(overflow);
/*求映象函数的常, [i-1],i=1,…,Adim*/
=(int*)malloc(dim*sizeof(int));
if(!) exit(overflow);
[Adim-1]=1; /*指针的增减以元素的大小为单位*/
for(i=Adim-2;i>=0,i--)
[i]=[i+1]* [i+1];
return OK;
}