数组是大家很熟悉的一种数据类型，而且在我们的程序设计中也应用非常广泛。这里以抽象数据类型的形式讨论数组的定义和实现。
一、数组的定义 假设n维数组中含有第i维的长度为b(i)，则数组的总长度为b(0) *b(1)*...*b(n-1)，每个元素都受着n个关系的约束。在每个关系中元素a(j1,j2,...,jn) (0<=jn<=b(i)-2)都有一个直接后继元素。因此，就单个关系而言，这n个关系仍然是线性关系。和线性表一样，所有的数据元素都属于同一数据类型。数组的每个数据元素都对应于一组下标(j1,j2,......,jn).特殊地，当n=1，n维数组就退化为定长的线性表；反之，n维数组可以看成是线性表的推广。数组一旦被定义，它的维数和维界就不再改变。因此除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。 二、数组的顺序表示和实现 1.存在的主序问题 由于我们的内存时一维的线性结构，而数组是个多维的结构，则用一组连续存储单元存放数组元素时就有个次序约定问题。因为我们是用C语言实现，所以我们默认都是使用行主序（pascal语言使用列主序）。 2.存储位置计算 对于数组，一旦规定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标就可求出相应数组元素的存储位置。下面以行序为主序的存储结构进行说明。假设每个数据元素占L个存储单元，则二维数组A任一元素a(i, j)的存储位置可由下式确定： LOC(i, j) = LOC(0, 0)+(b2*i+j) *L其中LOC(0, 0)是元素a(0, 0)的存储位置，即二维数组A的起始存储位置，也称为基地址。现将二维数组推广到一般情况，得到n维数组的数据元素存储位置的计算公式： 上式称为n维数组的映像函数。容易看出，数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，c(i)就是常数。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。 3.补充知识 后面要进行代码实现，在此之前先要了解可变参数的使用方法。VA_LIST 是在C语言中解决变参问题的一组宏。它有以下几个成员：(1).va_list型变量： #ifdef _M_ALPHA typedef struct { char *a0; /* pointer to first homed integer argument */ int offset; /* byte offset of next parameter */ } va_list; #else typedef char * va_list; #endif(2)._INTSIZEOF宏，获取类型占用的空间长度，最小占用长度为int的整数倍： #define _INTSIZEOF(n) ( (sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )(3).VA_START 宏，获取可变参数列表的第一个参数的地址（ap是类型为va_list的指针，v是可变参数最左边的参数）： #define va_start(ap,v) ( ap=(va_list)&v + _INTSIZEOF(v))(4).VA_ARG宏，获取可变参数的当前参数，返回指定类型并将指针指向下一参数（t参数描述了当前参数的类型）：#define va_arg(ap,t) ( (t )((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )
(5).VA_END宏，清空va_list可变参数列表： #define va_end(ap) ( ap = (va_list)0 )VA_LIST的用法： （1）首先在函数里定义一具VA_LIST型的变量，这个变量是指向参数的指针； （2）然后用VA_START宏初始化变量刚定义的VA_LIST变量； （3）然后用VA_ARG返回可变的参数，VA_ARG的第二个参数是你要返回的参数的类型（如果函数有多个可变参数的，依次调用VA_ARG获取各个参数）； （4）最后用VA_END宏结束可变参数的获取。 4.代码实现 下面给出数组的顺序存储和实现： #include <stdio.h>#include <stdlib.h>#include <stdarg.h> //标准头文件，提供宏va_start、va_arg和va_end用于存取变长参数表#define MAX_ARRAY_DIM 8 //假设数组维数最大值为8typedef struct{ int *base; //数组元素基址 int dim; //数组维数 int *bound; //数组维界基址,即用于存储每一维的长度 int *constants;//数组映像函数的各个常量系数}Array;//初始化数组，初始化维度，每一维的长度，和给数组分配内存void InitArray(Array *A, int dim, ...){ if (dim < 1 || dim > MAX_ARRAY_DIM) return; A->dim = dim; //初始化数组的维数 A->bound = (int*)malloc(dim * sizeof(int)); int elemtotal = 1; va_list ap; va_start(ap, dim); for (int i = 0; i < dim; ++i) //存放数组每一维的长度 { A->bound[i] = va_arg(ap, int); elemtotal *= A->bound[i]; //统计数组的元素个数 } va_end(ap); A->base = (int*)malloc(sizeof(int) * elemtotal); A->constants = (int*)malloc(dim * sizeof(int)); A->constants[dim - 1] = 1; //最后的一维是一维数组，其参数固定为1 for (int i = dim - 2; i >= 0; --i) { A->constants[i] = A->bound[i + 1] * A->constants[i + 1]; }}//释放数组动态分配的内存空间，以免发生内存泄露void DestroyArray(Array *A){ if (!A->base) return; free(A->base); A->base = NULL; if (!A->bound) { return; } free(A->bound); A->bound = NULL; if (!A->constants) { return; } free(A->constants); A->constants = NULL;}//ap参数中存放着要存取的元素的下标,off为数组映像函数的常量参数bool Locate(Array *A, va_list ap, int *off){ *off = 0; for (int i = 0; i < A->dim; ++i) { int ind = va_arg(ap, int); //依次取出每一维的下标 if (ind < 0 || ind > A->bound[i]) return false; (*off) += A->constants[i] * ind;//计算待存取的元素和数组基址的距离 } return true;}//A是n维数组，e是元素变量，随后是n个下标值//若下标不越界，则将e赋值为所指定的A的元素void Value(Array *A, int *e, ...){ va_list ap; va_start(ap, e); int off; if (!Locate(A, ap, &off)) { return; } *e = *(A->base + off);}//A是n维数组，e是元素变量，随后是n个下标值//若下标不越界，则将e赋给指定的A的元素void Assign(Array *A, int e, ...){ va_list ap; va_start(ap, e); int off; if (!Locate(A, ap, &off)) { return; } *(A->base + off) = e;}int main(void){ Array arr; InitArray(&arr, 3, 3, 4, 5); for (int i = 0; i < 3; ++i) { for (int j = 0; j < 4; ++j) { for (int k = 0; k < 5; ++k) { Assign(&arr, i + j + k, i, j, k); } } } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 4; ++j) { for (int k = 0; k < 5; ++k) { int tmp = 1; Value(&arr, &tmp, i, j, k); printf("%5d", tmp); } printf("n"); } printf("n"); } printf("n"); return 0;} 参考资料： 《数据结构》xhdsb版http://justsee.iteye.com/blog/1637173