5.1数组的定义&5.2数组的顺序表示和实现

5.1数组的定义：

数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。

5.2数组的顺序表示和实现

下面我们先来看下数组顺序存储的表示：

代码如下：

#include <stdarg.h>	//提供宏va_start、va_arg、va_end					//用于存取可变长参数表#define MAX_ARRAY_DIM 8//假设数组最大值为8typedef struct{	ElemType* base;	//数组元素基址，由InitArray分配	int dim;	//数组维数	int* bounds;	//数组维界基址，由InitArray分配	int* constants;	//数组映像函数常量基址，由InitArray分配}Array;
我们先分析下：
这个va_start,va_arg,va_end我们遇到相关代码再说。
这个*base是数组元素基址，所谓的元素基址，我们知道一维数组，二维数组，三维数组在逻辑上我们可以把他形象化，比如一维数组是线，二维是平面，三维是空间，但在内存中，他还是处于线性排列的，所以得有那么一个数组的元素基址，才能确定元素的位置。
这个dim,指的是数组的维度，比如刚刚所说的一维，二维，三维。
这个*bounds是存储了每个维度所在的地址。
这个*constants这个是数组映像函数常量基址，可能有人会问，什么是映像函数。所谓的映像函数就是用以根据数组下标快速计算其存储位置，有人说听不懂！那举个例子。假定每个元素之占用1个存储单元.其实这就是:(b2*...*bn)*j1+(b3*...*bn)*j2+(b4*...*bn)*j3+...+[b(n-1)*bn]*j(n-2)+bn*j(n-1)+1*jn上面式子的变体.constants[0]*j1+constants[1]*j2+...+constants[n-2]*j(n-1)+constants[n-1]*jnbounds[]中存储的每一维的多少
懂了吧。
下面是基本操作的函数原型说明：
首先来看InitArray函数：
代码如下：
Status InitArray(Array& A, int dim, ...){	//若维度dim和各维度长度合法，则构造相应的数组A，并返回OK	if (dim<1 || dim>MAX_ARRAY_DIM)		return ERROR;	A.dim = dim;	A.bounds = (int *)malloc(dim*sizeof(int));	if (!A.bounds)		exit(OVERFLOW);	//若各维长度合法，则存入A.bounds,并求出A的元素总数elemtotl	int elemtotal = 1;	// elemtotal是数组元素总数，初值为1(累乘器)	va_list ap;	va_start(ap, dim);	//读取可变参数的过程其实就是在堆栈中，使用指针,遍历堆栈段中的参数列表,从低地址到高地址一个一个地把参数内容读出来的过程	for (int i = 0; i < dim; i++)	{		A.bounds[i] = va_arg(ap, int);		if (A.bounds[i] < 0)			return UNDERFLOW;	// 在math.h中定义为4		elemtotal *= A.bounds[i];	}	va_end(ap);	A.base = (ElemType*)malloc(elemtotal*sizeof(ElemType));	if (!A.base)		exit(OVERFLOW);	//求映像函数的常数Ci，并存入A.constant[i-1],i=1,...,dim	A.constants = (int*)malloc(dim*sizeof(int));	if (!A.constants)		exit(OVERFLOW);	A.constants[dim - 1] = 1;	//L=1,指针的增减以元素的大小为单位	for (int i = dim - 2; i >= 0; --i)		A.constants[i] = A.bounds[i + 1] * A.constants[i + 1];	return Ok;}下面来分析下：
这个MAX_ARRAY_DIM，是刚刚定义的宏，也就是最大只有8维。
这里的参数里面有"..."这个可能有人问。在此说明下。大家都懂PRintf这个也就是这样，可变参数。那么如何读取到底有多少个可变参数。那就是va_start,va_list,va_end，va_arg的事，下面来讲解下va_start,va_list,va_end,va_arg。
va_list 是一个字符指针，可以理解为指向当前参数的一个指针，取参必须通过这个指针进行。<Step 1> 在调用参数表之前，定义一个 va_list 类型的变量，(假设va_list 类型变量被定义为ap)；<Step 2> 然后应该对ap 进行初始化，让它指向可变参数表里面的第一个参数，这是通过 va_start 来实现的，第一个参数是 ap 本身，第二个参数是在变参表前面紧挨着的一个变量,即“...”之前的那个参数；<Step 3> 然后是获取参数，调用va_arg，它的第一个参数是ap，第二个参数是要获取的参数的指定类型，然后返回这个指定类型的值，并且把 ap 的位置指向变参表的下一个变量位置；<Step 4> 获取所有的参数之后，我们有必要将这个 ap 指针关掉，以免发生危险，方法是调用 va_end，他是输入的参数 ap 置为 NULL，应该养成获取完参数表之后关闭指针的习惯。说白了，就是让我们的程序具有健壮性。通常va_start和va_end是成对出现。
这里面没有用到va_arg,在下面的程序里面会用到。
函数都讲解完了，下面讲解下这程序的思路。
这个程序的思路是先把有多少维度的Array初始了，这个可变参数里面放的是根据dim的数来判断的，比如dim为2，那么就是二维的，那么还要两个可变参数，一个是第一维的元素个数，一个是第二维的元素个数。
这里elemotal*=A.bounds[i],就把维度里面的所有元素都读取了出来
然后A.base就是第一个元素的地址。
开辟了A.base的空间后，现在弄映像函数。
下面是销毁数组A
代码如下：
Status DestroyArray(Array& A){	//销毁数组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.constants)		return ERROR;	free(A.constants);	A.constants = NULL;	return Ok;}分析：
这个就是当那个指针地址不为空就free，然后把指针指向安全的地带，也就是NULL。
下面是求元素在A中的相对位置。
代码如下：
Status Locate(Array A, va_list ap, int& off){	//若ap指示的各下标值合法，则求出该元素在A中相对地址off	int ind;	off = 0;	for (int 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;}
分析:
这个函数是要结合下面这个函数看的。调用va_arg，它的第一个参数是ap，第二个参数是要获取的参数的指定类型，然后返回这个指定类型的值，并且把 ap 的位置指向变参表的下一个变量位置。这个ap是下面这个Value函数的可变参数。
下面两个函数代码为：
Status Value(Array A, ElemType& e, ...){	//A是n维数组，e为元素变量，随后是n个下标值。	//若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。	va_list ap;	int result;	int off;	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, ...){	//A是n维数组，e为元素变量，随后是n个下标值。	//若下标不越界，则将e的值赋值给所指定的A的元素，并返回OK	va_list ap;	va_start(ap, e);	int off;	int result;	//这里的Statues被定义为int型	if (result = Locate(A, ap, off) <= 0)		return result;	*(A.base + off) = e;	return Ok;}