图10-1 Array_New(100, sizeof int)创建的Array_T实例
数组是由相同类型值组成的一个序列，序列中的元素以一对一的方式关联到某个连续范围内的索引值。在几乎所有编程语言中，都把某些形式的数组作为内建的数据类型。在某些语言（如C语言）中，所有数组索引值有共同的下界，而在其他的语言中（如Modula-3），每个数组都可以有自身的索引值边界。在C语言中，所有数组的索引都从0开始。
数组的大小可以在编译时或运行时指定。静态 数组的大小在编译时就是已知的。例如，在C语言中声明数组时，数组的大小必须在编译时就是已知的，即在声明int a[n]中，n必须是常量表达式。静态数组可以在运行时分配，例如，作为局部变量的数组，就是在运行时调用其所在函数时分配的，但其大小是编译时就是已知的。
像Table_toArray这样的函数返回的数组是动态 数组，因为其内存空间是通过调用malloc或等效的分配函数分配的。因此，他们的大小可以在运行时确定。一些语言（如Modula-3），在语言层面支持动态数组。但在C语言中，动态数组必须显式构造，如Table_toArray函数所示。
各种toArray函数都说明了动态数组是多么有用，本章描述的Array ADT提供了一种类似但更为通用的设施。它导出的函数可以分配并释放动态数组，可以访问动态数组并进行边界检查，可以扩展或收缩动态数组以容纳更多或更少的元素。
本章还描述了ArrayRep接口。对少数需要更高效地访问数组元素的客户程序，该接口披露了动态数组的表示细节。Array和ArrayRep共同说明了一个二级接口 或分层的接口 。Array规定了数组ADT的高层视图，ArrayRep规定了该ADT在较低层次上的另一个更详细的视图。这种组织方式的好处在于，如果有客户程序导入了ArrayRep接口，那么很显然，它们将依赖于动态数组的表示。对表示的修改将只影响此类客户程序，而不会影响到只导入Array接口的那些客户程序（比前一类多得多）。
如下的Array ADT
〈array.h 〉≡ #ifndef ARRAY_INCLUDED #define ARRAY_INCLUDED #define T Array_T typedef struct T *T; 〈exported functions 117〉 #undef T #endif
导出了一些函数，可以操作包含N个元素的数组，通过索引值0到N-1访问。特定数组中的每个元素都是定长的，但不同数组的元素可以有不同的大小。Array_T实例通过下列函数分配和释放：
〈exported functions
117〉≡
extern T Array_new (int length, int size);
extern void Array_free(T *array);
Array_new分配、初始化并返回一个新的数组，包含length个元素，可以用索引值0到length-1访问，在length为0时，数组不包含任何元素。每个元素占size字节。每个元素中的各个字节都初始化为0。size必须包含对齐所需的填充字节，这样，在length为正值时，直接分配length * size个字节即可创建数组。如果length为负值或size不是正值，则造成已检查的运行时错误，Array_new可能引发Mem_Failed异常。
Array_free释放*array并将其清零。如果array或*array是NULL，则是已检查的运行时错误。
不同于本书中大部分其他ADT在void指针基础上建立结构的方式，Array接口对元素的值不作任何限制，每个元素只是一个字节序列，包含size个字节。这种设计的基本原理是，Array_T通常用于构建其他ADT：第11章描述的序列就是一个例子。
下列各函数
〈exported functions
117〉+≡
extern int Array_length(T array);
extern int Array_size (T array);
返回array中元素的数目及元素的大小。数组元素通过下列函数访问：
〈exported functions
117〉+≡
extern void *Array_get(T array, int i);
extern void *Array_put(T array, int i, void *elem);
Array_get返回指向编号为i的元素的指针，类比而言，假定a声明为C语言数组，那么该函数的语义类似于&a[i]。客户程序通过反引用Array_get返回的指针，即可访问元素的值。Array_put用elem指向的新元素，覆盖元素i的值。不同于Table_put，Array_put返回elem。它不能返回元素i先前的值，因为元素未必是指针，而且元素也可能是任意字节长。
如果i大于或等于array的长度，或elem是NULL，则是已检查的运行时错误。首先调用Array_get，而后在反引用Array_get返回的指针之前，通过Array_resize改变array的大小，则造成未检查的运行时错误。如果elem指向的内存空间，以任何方式与array的第i个元素的内存空间重叠，都是未检查的运行时错误。
〈exported functions
117〉+≡
extern void Array_resize(T array, int length);
extern T Array_copy (T array, int length);
Array_resize改变array的大小，使之能够容纳length个元素，会根据需要扩展或收缩数组。如果length超过数组的当前长度，则增加的新元素被初始化为0。调用Array_resize，将使此前调用Array_get返回的值都变为无效。Array_copy的语义类似，但将返回array的一个副本，包含array的前length个元素。如果length超过array中元素的数目，副本中过多的那些元素将被初始化为0。Array_resize和Array_copy可能引发Mem_Failed异常。
Array没有类似Table_map和Table_toArray的函数，因为Array_get提供了执行等效操作的必要手段。
向该接口中任何函数传递的T值为NULL，都是已检查的运行时错误。
ArrayRep接口揭示了Array_T是由指向描述符 的指针表示的，描述符结构的各个字段给出了数组中元素的数目、元素的大小和指向数组内存空间的指针。
〈arrayrep.h
〉≡
#ifndef ARRAYREP_INCLUDED
#define ARRAYREP_INCLUDED
#define T Array_T
struct T {
int length;
int size;
char *array;
};
extern void ArrayRep_init(T array, int length,
int size, void *ary);
#undef T
#endif
图10-1给出Array_new(100, sizeof int)返回的包含100个整数的数组的描述符，所运行的机器上整数为4字节。如果数组没有元素，array字段为NULL。数组描述符有时也称为信息矢量 （dope vector）。
图10-1 Array_New(100, sizeof int)创建的Array_T实例
ArrayRep的客户程序可以读取描述符的各字段，但不能写这些字段，否则会造成未检查的运行时错误。ArrayRep保证，如果array是一个T实例，而i是非负整数且小于array->length，那么
array->array + i*array->size
是元素i的地址。
ArrayRep还导出了ArrayRep_init，该函数初始化array指向的Array_T结构实例的各字段，将其分别设置为参数length、size和ary的值。提供该函数后，客户程序可以初始化Array_T实例，将其嵌入到其他结构中。如果array是NULL，或size不是正值，或length为正值且ary为NULL，或length为零且ary不是NULL，均会造成已检查的运行时错误 [1] 。用调用ArrayRep_init之外的手段初始化T结构，则是未检查的运行时错误。
我们用一个实现导出Array和ArrayRep两个接口：
〈array.c 〉≡ #include <stdlib.h> #include <string.h> #include "assert.h" #include "array.h" #include "arrayrep.h" #include "mem.h" #define T Array_T 〈functions 120〉
Array_new为一个描述符及数组本身（如果length为正值）分配空间，并调用ArrayRep_init初始化描述符的各字段：
〈functions
120〉≡
T Array_new(int length, int size) {
T array;
NEW(array);
if (length > 0)
ArrayRep_init(array, length, size,
CALLOC(length, size));
else
ArrayRep_init(array, length, size, NULL);
return array;
}
ArrayRep_init是初始化描述符的各字段唯一的有效方法，用其他方式分配描述符的客户程序必须调用ArrayRep_init来初始化描述符。
〈functions
120〉+≡
void ArrayRep_init(T array, int length, int size,
void *ary) {
assert(array);
assert(ary && length>0 || length==0 && ary==NULL);
assert(size > 0);
array->length = length;
array->size = size;
if (length > 0)
array->array = ary;
else
array->array = NULL;
}
调用ArrayRep_init来初始化一个T结构实例，有助于减少耦合：这些调用清楚地标识出了自行分配描述符的那些客户程序（因而依赖于数组的表示）。只要ArrayRep_init不改变，那么向描述符添加字段不会影响这些客户程序。例如，如果向T结构添加一个用于标识序列号的字段，且该字段由ArrayRep_init自动初始化，那么就会发生上述场景。
Array_free释放数组本身和T结构实例，并将其参数清零 [2] ：
〈functions
120〉+≡
void Array_free(T *array) {
assert(array && *array);
FREE((*array)->array);
FREE(*array);
}
Array_free无需检查(*array)->array是否为NULL，因为FREE可以处理NULL指针。
Array_get从Array_T实例获取数组元素，Array_put向Array_T实例存储数组元素：
〈functions
120〉+≡
void *Array_get(T array, int i) {
assert(array);
assert(i >= 0 && i < array->length);
return array->array + i*array->size;
}
void *Array_put(T array, int i, void *elem) {
assert(array);
assert(i >= 0 && i < array->length);
assert(elem);
memcpy(array->array + i*array->size, elem,
array->size);
return elem;
}
请注意，Array_put将返回其第三个参数，而不是目标数组元素的地址。
Array_length和Array_size分别返回描述符中名称类似的字段：
〈functions
120〉+≡
int Array_length(T array) {
assert(array);
return array->length;
}
int Array_size(T array) {
assert(array);
return array->size;
}
ArrayRep的客户程序可以从描述符直接访问这些字段。
Array_resize调用Mem接口的RESIZE来改变数组中的元素的数目，并相应地改变数组的length字段。
〈functions
120〉+≡
void Array_resize(T array, int length) {
assert(array);
assert(length >= 0);
if (length == 0)
FREE(array->array);
else if (array->length == 0)
array->array = ALLOC(length*array->size);
else
RESIZE(array->array, length*array->size);
array->length = length;
}
不同于Mem接口的RESIZE，在这里，新的长度为0是合法的，而在这种情况下数组将被释放，此后描述符实际上描述了一个空的动态数组。
Array_copy与Array_resize非常相似，只是它会复制array的描述符以及数组的部分或全部内容：
〈functions
120〉+≡
T Array_copy(T array, int length) {
T copy;
assert(array);
assert(length >= 0);
copy = Array_new(length, array->size);
if (copy->length >= array->length
&& array->length > 0)
memcpy(copy->array, array->array,
array->length*array->size);
else if (array->length > copy->length
&& copy->length > 0)
memcpy(copy->array, array->array,
copy->length*array->size);
return copy;
}
一些语言支持动态数组的变体。例如，Modula-3[Nelson，1991]容许在执行期间创建具有任意边界的数组，但这种数组不能扩展或收缩。Icon[Griswold and Griswold，1990]中的列表与动态数组类似，可以在两端添加或删除元素，从而进行扩展或收缩，这与下一章描述的序列非常相似。Icon还支持从列表获取子列表，或将子列表替换为一个不同长度的列表。
10.1 设计并实现一个ADT，提供指针的动态数组。它应该通过函数提供对这些数组元素的“安全”访问，这些函数本质上与Table接口提供的函数类似。在你的实现中使用Array或Array_Rep。
10.2 为动态矩阵（即二维数组）设计一个ADT，并使用Array实现它。你可以将设计推广到N维数组吗？
10.3 为稀疏 动态数组（其中大部分元素是零的数组）设计并实现一个ADT。你的设计应该接受一个特定于数组的值作为零，实现应该只存储那些不等于零的元素。
10.4 将下述函数
extern void Array_reshape(T array, int length,
int size);
添加到Array接口及其实现中。Array_reshape会将array中元素的数目和每个元素的大小分别改为length和size。类似Array_resize，重整后的数组保留了原数组的前length个元素，如果length超过原来的长度，超出的那部分元素将设置为0。array中的第i个元素，将变为重整后的数组中的第i个元素。如果size小于原本每个元素的大小，则截断原来的各个元素，如果size大于原来各个元素的大小，超出的那部分字节设置为0。
[1] 原文对length和ary的限定有点错误，根据下文的代码改正。——译者注
[2] 指将*array清零，由FREE宏自动完成。——译者注