第 5 章 数组和广义表（数组的顺序存储结构实现）

1. 背景说明

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

2. 示例代码

1) status.h

/* DataStructure 预定义常量和类型头文件 */
#include 
 
#ifndef STATUS_H
#define STATUS_H
 
#define NONE ""
 
#define FILE_NAME(X) strrchr(X, '\\') ? strrchr(X,'\\') + 1 : X
 
#define DEBUG
 
#ifdef DEBUG
#define CHECK_NULL(pointer) if (!(pointer)) { \
		printf("\nFileName: %-25s FuncName: %-20s Line: %-10d ErrorCode: %-3d\n", FILE_NAME(__FILE__), __func__, __LINE__, ERR_NULL_PTR); \
		return NULL; \
	}
#else
#define CHECK_NULL(pointer)
#endif
 
#ifdef DEBUG
#define CHECK_VALUE(value, ERR_CODE) if (!(value)) { \
		printf("\nFileName: %-25s FuncName: %-20s Line: %-10d ErrorCode: %-3d\n", FILE_NAME(__FILE__), __func__, __LINE__, ERR_CODE); \
		return FALSE; \
	}
#else
#define CHECK_VALUE(value, ERR_CODE)
#endif
 
#ifdef DEBUG
#define CHECK_RET(ret, FORMAT, ...) if (ret != RET_OK) { \
		printf("\nFileName: %-25s FuncName: %-20s Line: %-10d ErrorCode: %-3d" FORMAT "\n", FILE_NAME(__FILE__), __func__, __LINE__, ret, ##__VA_ARGS__); \
		return ret; \
	}
#else
#define CHECK_RET(ret, FORMAT, ...)
#endif
 
#ifdef DEBUG
#define CHECK_CONDITION(condition, ERR_CODE, FORMAT, ...) if (condition) { \
		printf("\nFileName: %-25s FuncName: %-20s Line: %-10d ErrorCode: %-3d" FORMAT "\n", FILE_NAME(__FILE__), __func__, __LINE__, ERR_CODE, ##__VA_ARGS__); \
		return ERR_CODE; \
	}
#else
#define CHECK_CONDITION(condition, ERR_CODE, FORMAT, ...)
#endif
 
/* 函数结果状态码 */
#define TRUE 					1			/* 返回值为真 */
#define FALSE 					0			/* 返回值为假 */
#define RET_OK 					0			/* 返回值正确 */
#define ERR_NULL_PTR   			2			/* 空指针错误 */
#define ERR_MEMORY_ACCESS		3			/* 访问内存错 */
#define ERR_MEMORY_ALLOCATE		4			/* 内存分配错 */
#define ERR_NULL_STACK			5			/* 栈元素为空 */
#define ERR_PARA				6			/* 函数参数错 */
#define ERR_OPEN_FILE			7			/* 打开文件错 */
#define ERR_NULL_QUEUE			8			/* 队列为空错 */
#define ERR_FULL_QUEUE			9			/* 队列为满错 */
#define ERR_NOT_FOUND			10			/* 表项不存在 */
typedef int Status;							/* Status 是函数的类型,其值是函数结果状态代码，如 RET_OK 等 */
typedef int Bollean;						/* Boolean 是布尔类型,其值是 TRUE 或 FALSE */
 
#endif // !STATUS_H

2) sqArray.h

/* 数组的顺序存储表示头文件 */
 
#ifndef SQ_ARRAY_H
#define SQ_ARRAY_H
 
#include "status.h"
 
#define MAX_ARRAY_DIM 10
 
typedef int ElemType;
 
typedef struct {
	ElemType *base;
	int dim;
	int *bounds;
	int *constants;
} Array;
 
Status InitArray(int dim, Array *array, ...);
Status DestroyArray(Array *array);
Status Locate(va_list ap, const Array *array, int *off);
Status GetArrayValue(const Array *array, ElemType *e, ...);
Status AssignArray(ElemType e, Array *array, ...);
 
#endif // !SQ_ARRAY_H

3) sqArray.c

/* 数组的顺序存储实现源文件 */
 
#include "sqArray.h"
#include 
#include 
#include 
 
/*
	前置条件：维数 dim 和各维长度合法
	操作结果：构造相应的数组 *array，并返回 RET_OK
*/
Status InitArray(int dim, Array *array, ...)
{
	CHECK_CONDITION(!array, ERR_NULL_PTR, NONE);
	CHECK_CONDITION((dim < 1) || (dim > MAX_ARRAY_DIM), ERR_PARA, "dim = %d", dim);
	array->dim = dim;
	array->bounds = (int *)malloc(sizeof(int) * dim);
	CHECK_CONDITION(!(array->bounds), ERR_MEMORY_ALLOCATE, NONE);
	va_list ap;
	va_start(ap, array);
	int elemTotal = 1;
	for (int i = 0; i < dim; ++i) {
		array->bounds[i] = va_arg(ap, int);
		CHECK_CONDITION(array->bounds[i] < 0, ERR_PARA, "array->bounds[%d] = %d", i, array->bounds[i]);
		elemTotal *= array->bounds[i];
	}
 
	va_end(ap);
	array->base = (ElemType *)malloc(sizeof(ElemType) * elemTotal);
	CHECK_CONDITION(!(array->base), ERR_MEMORY_ALLOCATE, NONE);
	array->constants = (int *)malloc(sizeof(int) * dim);
	CHECK_CONDITION(!(array->constants), ERR_MEMORY_ALLOCATE, NONE);
	array->constants[dim - 1] = 1;
	for (int i = dim - 2; i >= 0; --i) {
		array->constants[i] = array->bounds[i + 1] * array->constants[i + 1];
	}
 
	return RET_OK;
}
 
/*
	前置条件：数组 *array 已存在
	操作结果：销毁数组 *array
*/
Status DestroyArray(Array *array)
{
	CHECK_CONDITION(!array, ERR_NULL_PTR, NONE);
	free(array->base);
	free(array->bounds);
	free(array->constants);
	array->base = array->bounds = array->constants = NULL;
	array->dim = 0;
 
	return RET_OK;
}
 
/*
	前置条件：数组 *array 已存在，ap 指示的各下标值合法
	操作结果：求出该元素在 *array 中的相对地址 *off
*/
Status Locate(va_list ap, const Array *array, int *off)
{
	CHECK_CONDITION(!array || !off, ERR_NULL_PTR, "array = %p, off = %p", array, off);
	int ind;
	*off = 0;
	for (int i = 0; i < array->dim; ++i) {
		ind = va_arg(ap, int);
		CHECK_CONDITION((ind < 0) || (ind >= array->bounds[i]), ERR_PARA, "ind = %d, array->bounds[%d] = %d",
			ind, i, array->bounds[i]);
		*off += (array->constants[i]) * ind;
	}
 
	return RET_OK;
}
 
/*
	前置条件：数组 *array 已存在，各维度的数组的下标值合法
	操作结果：将数组相应元素值赋值给 *e
*/
Status GetArrayValue(const Array *array, ElemType *e, ...)
{
	CHECK_CONDITION(!array || !e, ERR_NULL_PTR, "array = %p, e = %p", array, e);
	va_list ap;
	va_start(ap, e);
	int off;
	Status ret = Locate(ap, array, &off);
	CHECK_RET(ret, NONE);
	*e = *(array->base + off);
 
	return RET_OK;
}
 
/*
	前置条件：数组 *array 已存在，各维度的数组的下标值合法
	操作结果：将元素值 e 赋值给数组相应元素
*/
Status AssignArray(ElemType e, Array *array, ...)
{
	CHECK_CONDITION(!array, ERR_NULL_PTR, NONE);
	va_list ap;
	va_start(ap, array);
	int off;
	Status ret = Locate(ap, array, &off);
	CHECK_RET(ret, NONE);
	*(array->base + off) = e;
 
	return RET_OK;
}

4) main.c

#include "sqArray.h"
#include 
 
int main(void)
{
	/* 数组 array[3][4][2] */
	Array array;
	int dim = 3, bound1 = 3, bound2 = 4, bound3 = 2;
	Status ret = InitArray(dim, &array, bound1, bound2, bound3);
	CHECK_RET(ret, NONE);
	int *p = array.bounds;
	for (int i = 0; i < dim; ++i) {
		printf("array.bound[%d] = %d ", i, *(p + i));
	}
 
	printf("\n");
	p = array.constants;
	for (int i = 0; i < dim; ++i) {
		printf("array.constants[%d] = %d ", i, *(p + i));
	}
 
	printf("\n\n%d pages %d row %d col element: \n", bound1, bound2, bound3);
	ElemType e;
	for (int i = 0; i < bound1; ++i) {
		for (int j = 0; j < bound2; ++j) {
			for (int k = 0; k < bound3; ++k) {
				ret = AssignArray(i * 100 + j * 10 + k, &array, i, j, k);
				ret |= GetArrayValue(&array, &e, i, j, k);
				CHECK_RET(ret, "i = %d, j = %d, k = %d", i, j, k);
				printf("  array[%d][%d][%d] = %3d", i, j, k, e);
			}
 
			printf("\n");
		}
 
		printf("\n");
	}
 
	ElemType *p1 = array.base;
	printf("array.base = \n");
	for (int i = 0; i < bound1 * bound2 * bound3; ++i) {
		printf("%22d", *(p1 + i));
		if (i % 2 == 1) {
			printf("\n");
		}
	}
 
	ret = DestroyArray(&array);
	CHECK_RET(ret, NONE);
 
	return 0;
}

3. 输出示例