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

89 阅读 0 评论 59 点赞

我是靠谱客的博主时尚鲜花，最近开发中收集的这篇文章主要介绍5.1数组的定义&5.2数组的顺序表示和实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

5.1数组的定义：

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

5.2数组的顺序表示和实现

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

代码如下：

#include <stdarg.h>	//提供宏va_start、va_arg、va_end
					//用于存取可变长参数表
#define MAX_ARRAY_DIM 8//假设数组最大值为8

typedef 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]*jn
bounds[]中存储的每一维的多少

懂了吧。

下面是基本操作的函数原型说明：

首先来看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;
}