OOC:Abstract Data Types — Information Hiding
来自 ChinaUnix Wiki
目录 |
Abstract Data Types — Information Hiding
抽象数据类型 — 信息隐藏
Data Types
数据类型
Data types are an integral part of every programming language. ANSI-C has int, double and char to name just a few. Programmers are rarely content with what’s available and a programming language normally provides facilities to build new data types from those that are predefined. A simple approach is to form aggregates such as arrays, structures, or unions. Pointers, according to C. A. R. Hoare ‘‘a step from which we may never recover,’’ permit us to represent and manipulate data of essentially unlimited complexity.
数据类型是每种编程语言不可分割的一部分。ANSI-C就有int，double和char这几种。程序员们极少满足于现成可用的类型，而编程语言通常提供了从预定义的类型构建新的数据类型的机制。其中一种简单的方法是构造集合体，例如数组（array），结构体（structure）和联合体（union）。被C. A. R. Hoare称为“我们永远无法收回的一步”的指针，允许我们表示和操作具有本质上无限复杂性的数据。
What exactly is a data type? We can take several points of view. A data type is a set of values — char typically has 256 distinct values, int has many more; both are evenly spaced and behave more or less like the natural numbers or integers of mathematics. double once again has many more values, but they certainly do not behave like mathematics’ real numbers.
到底什么是数据类型？我们可以从不同的角度来看这个问题。一种数据类型是一个值（value）的集合——char就有256种不同的值，int就更多了；两者都是间隔均匀的，或多或少表现得像是数学里的自然数或整数。double类型的值就更多了，但是它们表现得却不像数学里的实数。
Alternatively, we can define a data type as a set of values plus operations to work with them. Typically, the values are what a computer can represent, and the operations more or less reflect the available hardware instructions. int in ANSI-C does not do too well in this respect: the set of values may vary between machines, and operations like arithmetic right shift may behave differently.
一种替代的方式是，我们可以定义一种数据类型，它包含了一组值的集合以及作用于该集合之上的一组操作。典型地来说，这些值是计算机能够表示的，而这些操作多少反映了可用的硬件指令。在这方面ANSI-C中的int就做得不太好：值的集合会随着机器的不同而变化，并且有些操作比如说算数右移也会表现得有所不同。
More complicated examples do not fare much better. Typically we would define an element of a linear list as a structure
更加复杂的例子也没有太大的意义。做为例子我们可以用结构体来定义线性表的的一个元素。
typedef struct node {
struct node * next;
... information ...
} node;
and for the operations we specify function headers like
至于这些操作我们指定像这样的函数头部：
node * head (node * elt, const node * tail);
This approach, however, is quite sloppy. Good programming principles dictate that we conceal the representation of a data item and declare only the possible manipulations.
但是，这种办法显得非常松散。好的编程原则要求我们封装数据项的表示并且只声明合适的操作。
Abstract Data Types
抽象数据类型 We call a data type abstract, if we do not reveal its representation to the user. At a theoretical level this requires us to specify the properties of the data type by mathematical axioms involving the possible operations. For example, we can remove an element from a queue only as often as we have added one previously, and we retrieve the elements in the same order in which they were added.
如果我们不把一种数据类型的具体表示展现给用户，那么我们称它是“抽象的”。在理论的层面这要求我们通过数学公理和适当的操作来指定这种数据类型的属性。例如，向队列中加入元素后才能删除，从队列中取出的元素的顺序和放入时的顺序相同。
Abstract data types offer great flexibility to the programmer. Since the representation is not part of the definition, we are free to choose whatever is easiest or most efficient to implement. If we manage to distribute the necessary information correctly, use of the data type and our choice of implementation are totally independent.
抽象数据类型给了程序员巨大的灵活性。由于表示不是定义的一部分，我们可以自由选择最容易的或者是效率最高的表示方法来实现定义。如果我们能正确的发布必要的信息，那么如何使用该数据类型和如何实现它就是完全独立的了。
Abstract data types satisfy the good programming principles of information hiding and divide and conquer. Information such as the representation of data items is given only to the one with a need to know: to the implementer and not to the user. With an abstract data type we cleanly separate the programming tasks of implementation and usage: we are well on our way to decompose a large system into smaller modules.
抽象数据类型满足了良好的编程原则对于信息隐藏以及“分而治之”方式的需求。信息（例如数据项的表示）只给予需要知道的人：实现者而不是使用者。通过抽象数据类型我们干净地把实现和使用两种编程任务分开：我们在把一个大系统分成小模块的道路上顺利前行。
An Example — Set
So how do we implement an abstract data type? As an example we consider a set of elements with the operations add, find, and drop.* They all apply to a set and an element and return the element added to, found in, or removed from a set. find can be used to implement a condition contains which tells us whether an element is already contained in a set.
一个例子 -- Set 那么我们如何实现一种抽象数据类型呢？比如，我们考虑一个元素的集合。该集合上可以进行add，find和drop操作。它们作用于一个集合和一个元素上，并返回一个元素，刚加入集合的（add），从集合中找到的（find）或者从集合中删除掉的（drop）元素。find可以用来实现一个条件判断contains，它可以告诉我们集合中是否已经包含某元素。
Viewed this way, set is an abstract data type. To declare what we can do with a set, we start a header file Set.h:
从这个角度来看，集合是一个抽象数据类型。为了声明我们能对一个集合做什么，我们创建了一个头文件Set.h：
#ifndef SET_H
#define SET_H
extern const void * Set;
void * add (void * set, const void * element);
void * find (const void * set, const void * element);
void * drop (void * set, const void * element);
int contains (const void * set, const void * element);
#endif
The preprocessor statements protect the declarations: no matter how many times we include Set.h, the C compiler only sees the declarations once. This technique of protecting header files is so standard, that the GNU C preprocessor recognizes it and does not even access such a file when its protecting symbol is defined.
其中的预处理语句是为了保护下面的声明：无论我们多少次包含Set.h，C编译器只会看到一次声明。这种保护头文件的技术非常的标准，GNU C预处理器能够识别它，并且当保护符号已经定义的时候不会访问这个文件。
Set.h is complete, but is it useful? We can hardly reveal or assume less: Set will have to somehow represent the fact, that we are working with sets; add() takes an element, adds it to a set, and returns whatever was added or already present in the set; find() looks for an element in a set and returns whatever is present in the set or a null pointer; drop() locates an element, removes it from a set, and returns whatever was removed; contains() converts the result of find() into a truth value.
Set.h是完整的，但它有用吗？我们几乎不能透露或者呈现更少的内容了：Set头文件必须在某种程度上表示出我们正在进行操作的是集合这个事实。 add()接收一个元素，把它加到集合中，并且返回该元素——无论它是新加入的或者已经存在于集合中；find()在集合中查找一个元素，返回该元素中或者空指针；drop()定位元素，把它从集合中删除，并且返回被删除的内容；contains()把find()的结果转换成一个真值。
- Unfortunately, remove is an ANSI-C library function to remove a file. If we used this name for a set function, we could no longer include stdio.h.
- 不幸的是，remove是一个ANSI-C库函数，用来删除一个文件。如果我们用remove来命名一个set的函数，我们就不能再包含stdio.h这个文件了。
The generic pointer void * is used throughout. On the one hand it makes it impossible to discover what a set looks like, but on the other hand it permits us to pass virtually anything to add() and the other functions. Not everything will behave like a set or an element — we are sacrificing type security in the interest of information hiding. However, we will see in chapter 8 that this approach can be made completely secure.
我们自始至终的使用了泛型指针void *。一方面它使得了解集合到底是什么变得不可能，但另一方面，它允许我们向add()和其他几个函数传递任何东西。并不是任何东西会表现得像一个集合或者一个元素一样——为了信息隐藏我们牺牲了类型安全。然而，在第8章中我们将会看到这种方法可以安全的实现。
Memory Management
We may have overlooked something: how does one obtain a set? Set is a pointer, not a type defined by typedef; therefore, we cannot define local or global variables of type Set. Instead, we are only going to use pointers to refer to sets and elements, and we declare source and sink of all data items in new.h:
内存管理
我们可能忽略了一些事情：如何获取一个集合？Set是一个指针，而不是一个用typedef定义的类型，所以我们不能够定义一个类型是Set的局部或者全局变量。作为替代，我们用指针来引用集合和元素，并且在new.h中声明所有数据项的产生和删除方法：
void * new (const void * type, ...);
void delete (void * item);
Just like Set.h this file is protected by a preprocessor symbol NEW_H. The text only shows the interesting parts of each new file, the source diskette contains the complete code of all examples.
就像Set.h一样，这个文件受到了预处理符号NEW_H的保护。本书只是展示了每个新的文件中有意思的部分，示例的完整代码包含在源代码磁盘中。
new() accepts a descriptor like Set and possibly more arguments for initialization and returns a pointer to a new data item with a representation conforming to the descriptor. delete() accepts a pointer originally produced by new() and recycles the associated resources.
new()接收像Set这样的描述符以及更多可能的初始化参数，并且返回一个指针，该指针指向新产生的符合描述参数的数据项。delete()接收一个由new()产生的指针，回收其相关的资源。
new() and delete() presumably are a frontend to the ANSI-C functions calloc() and free(). If they are, the descriptor has to indicate at least how much memory is required.
new()和delete()大致上是ANSI-C函数calloc()和free()的一个前端。如果它们是的话，描述符至少需要指明内存大小。
Object
If we want to collect anything interesting in a set, we need another abstract data type Object described by the header file Object.h:
对象
如果我们需要了解集合中的任何情况，就需要头文件Object.h中描述的另一个抽象数据类型Object：
extern const void * Object; /* new(Object); */
int differ (const void * a, const void * b);
differ() can compare objects: it returns true if they are not equal and false if they are. This description leaves room for the functionality of strcmp(): for some pairs of objects we might choose to return a negative or positive value to specify an ordering.
differ()能够比较对象：如果它们不相等就返回true，否则返回false。这样的描述为strcmp()的应用留下了空间：对于某些对象的配对（pair），我们也许会选择返回负值或正值来指明两者的次序。
Real life objects need more functionality to do something useful. For the moment, we restrict ourselves to the bare necessities for membership in a set. If we built a bigger class library, we would see that a set — and in fact everything else — is an object, too. At this point, a lot of functionality results more or less for free.
真实生活中的对象需要有更多的功能来完成一些有实际意义的事。现在，我们把自己局限于单纯的成为集合的成员的需求。如果我们构建一个更大的类库，就会发现一个集合——或是别的东西——也是一个对象。在这一点上，大量的功能性函数多多少少给了我们自由。
An Application
With the header files, i.e., the definitions of the abstract data types, in place we can write an application main.c:
一个应用实例
有了这些头文件，也就是这些抽象数据类型的定义，我们就可以写一个程序main.c：
#include <stdio.h>
#include "new.h"
#include "Object.h"
#include "Set.h"
int main ()
{ void * s = new(Set);
void * a = add(s, new(Object));
void * b = add(s, new(Object));
void * c = new(Object);
if (contains(s, a) && contains(s, b))
puts("ok");
if (contains(s, c))
puts("contains?");
if (differ(a, add(s, a)))
puts("differ?");
if (contains(s, drop(s, a)))
puts("drop?");
delete(drop(s, b));
delete(drop(s, c));
return 0;
}
We create a set and add two new objects to it. If all is well, we find the objects in the set and we should not find another new object. The program should simply print ok.
我们建立了一个集合并且加入了两个新的对象。如果一切正常，我们能在集合中找到这两个对象，而且不会存在任何新的对象了。所以这个程序只是简单的打印出ok。
The call to differ() illustrates a semantic point: a mathematical set can only contain one copy of the object a; an attempt to add it again must return the original object and differ() ought to be false. Similarly, once we remove the object, it should no longer be in the set.
对于differ()的调用展示了一个语义：一个数学集合只能包含一份a对象的拷贝；如果想要再加入一个a对象的话就会返回原始的对象并且differ()应该返回false。与此类似，一旦我们删除了一个对象，它就不应该还在这个set中了。
Removing an element not in a set will result in a null pointer being passed to delete(). For now, we stick with the semantics of free() and require this to be acceptable.
删除一个不在集合中的元素会导致一个空指针被传递给delete()。目前来说，我们坚持free()的语义并且要求它是可以被接受的。
An Implementation — Set
一个实现——集合
main.c will compile successfully, but before we can link and execute the program, we must implement the abstract data types and the memory manager. If an object stores no information and if every object belongs to at most one set, we can represent each object and each set as small, unique, positive integer values used as index into an array heap[]. If an object is a member of a set, its array element contains the integer value representing the set. Objects, therefore, point to the set containing them.
main.c可以正确的编译，但是在我们链接并且执行该程序之前，我们必须实现该抽象数据结构并完成存储管理的部分。假定对象里不存放任何信息并且每个对象至多属于一个集合，则可以把每个对象和集合看作heap[]数组的索引——都是一个个不重复的小正数。如果某对象是集合的元素，那么该对象的数组元素中存储着表示其所在的集合的整数索引值。因此，对象指向包含它的集合。
This first solution is so simple that we combine all modules into a single file Set.c. Sets and objects have the same representation, so new() pays no attention to the type description. It only returns an element in heap[] with value zero:
#if ! defined MANY || MANY < 1
#define MANY 10
#endif
static int heap [MANY];
void * new (const void * type, ...)
{ int * p; /* & heap[1..] */
for (p = heap + 1; p < heap + MANY; ++ p)
if (! * p)
break;
assert(p < heap + MANY);
* p = MANY;
return p;
}
方案一是如此的简单，我们可以把所有的模块集成到一个文件：Set.c中。集合和对象的表示是一样的，所以new()不再考虑参数所给的类型描述。new()返回heap[]数组中值为0的一个索引作为新元素：
We use zero to mark available elements of heap[]; therefore, we cannot return a reference to heap[0] — if it were a set, its elements would contain the index value zero.
我们用0值来标识heap[]数组中可用的成员；所以不能返回heap[0]的引用——因为如果它是一个集合，那么它所包含的元素可能包括索引值0。
Before an object is added to a set, we let it contain the impossible index value MANY so that new() cannot find it again and we still cannot mistake it as a member of any set.
在向集合中增加对象之前，将一个不可能取到的索引值MANY赋给该元素对应的数组成员，这样new()就不可能再次将其分配为新元素，我们也不会将其误认为某个集合的元素。
new() can run out of memory. This is the first of many errors, that ‘‘cannot happen’’. We will simply use the ANSI-C macro assert() to mark these points. A more realistic implementation should at least print a reasonable error message or use a general function for error handling which the user may overwrite. For our purpose of developing a coding technique, however, we prefer to keep the code uncluttered. In chapter 13 we will look at a general technique for handling exceptions.
new()会用完内存。这是很多“不会发生”的错误的第一个。我们简单的使用标准C的assert()宏来标记这个错误。更为可行的方法应该至少打印出适当的错误信息或者使用用户可以重写的通用错误处理函数。然而，就增进编程技术而言，我们更倾向于保持代码的干净整洁。十三章中我们会介绍普适的方法来处理异常。
delete() has to be careful about null pointers. An element of heap[] is recycled by setting it to zero:
void delete (void * _item)
{ int * item = _item;
if (item)
{ assert(item > heap && item < heap + MANY);
* item = 0;
}
}
delete()必须小心处理空指针。当heap[]数组中的成员被设为0时即完成了对其的回收。
We need a uniform way to deal with generic pointers; therefore, we prefix their names with an underscore and only use them to initialize local variables with the desired types and with the appropriate names.
我们需要一个统一的方式来处理这些通用指针，故我们用名字前面加下划线的方法来表示这些通用指针，并且只用他们来初始化需要的特定类型和名称的局部变量。
A set is represented in its objects: each element points to the set. If an element contains MANY, it can be added to the set, otherwise, it should already be in the set because we do not permit an object to belong to more than one set.
集合是由其对象表示出来的：每个集合中的元素都指向集合。如果一个元素对应的数组成员值为MANY，那么该元素就可以被加入到集合中，不然的话它一定已经在集合中了，因为我们不允许一个对象属于多个集合。
void * add (void * _set, const void * _element)
{ int * set = _set;
const int * element = _element;
assert(set > heap && set < heap + MANY);
assert(* set == MANY);
assert(element > heap && element < heap + MANY);
if (* element == MANY)
* (int *) element = set — heap;
else
assert(* element == set — heap);
return (void *) element;
}
assert() takes out a bit of insurance: we would only like to deal with pointers into heap[] and the set should not belong to some other set, i.e., its array element value ought to be MANY.
assert()宏保证了我们不会处理指向heap[]数组之外的元素，并保证集合不能再属于别的集合，也就是集合对应的数组成员的值应为MANY。
The other functions are just as simple. find() only looks if its element contains the proper index for the set:
其余的函数也很简单。find()用来检验其element参数对应的heap[]中的数组成员值是不是等于集合对应的数组序号值。
void * find (const void * _set, const void * _element)
{ const int * set = _set;
const int * element = _element;
assert(set > heap && set < heap + MANY);
assert(* set == MANY);
assert(element > heap && element < heap + MANY);
assert(* element);
return * element == set — heap ? (void *) element : 0;
}
contains() converts the result of find() into a truth value:
contains()函数将find()的结果转化为布尔值：
int contains (const void * _set, const void * _element)
{
return find(_set, _element) != 0;
}
drop() can rely on find() to check if the element to be dropped actually belongs to the set. If so, we return it to object status by marking it with MANY:
drop()利用find()函数来检查要被drop的元素是否真的属于该集合。如果是，我们恢复它的状态，标记为MANY，并返回它。
void * drop (void * _set, const void * _element)
{ int * element = find(_set, _element);
if (element)
* element = MANY;
return element;
}
If we were pickier, we could insist that the element to be dropped not belong to another set. In this case, however, we would replicate most of the code of find() in drop().
如果我们挑剔一点，我们还得保证要被除去的元素也不能属于别的集合。如果这样我们拷贝一些find()中的代码来实现drop()。
Our implementation is quite unconventional. It turns out that we do not need differ() to implement a set. We still need to provide it, because our application uses this function.
我们的实现方法很不寻常。事实上在集合操作中我们甚至不需要differ()函数。但是我们依旧要写出它，因为我们应用程序的需要。
int differ (const void * a, const void * b)
{
return a != b;
}
Objects differ exactly when the array index representing them differ, i.e., a simple pointer comparison is sufficient.
元素对象不同也就是他们在数组中对应的序号不同，也就是仅仅比较元素对应的指针就足够了。
We are done — for this solution we have not used the descriptors Set and Object but we have to define them to keep our C compiler happy:
const void * Set;
const void * Object;
We did use these pointers in main() to create new sets and objects.
对于这个方案来说，我们已经完成所有的工作了。至于Set和Object描述符其实并不需要，我们这里加上只是使C编译器高兴：
const void * Set;
const void * Object;
在main.c中我们就用这两个指针来创造新的集合和元素。
Another Implementation — Bag
另一个实现——包
Without changing the visible interface in Set.h we can change the implementation. This time we use dynamic memory and represent sets and objects as structures:
struct Set { unsigned count; };
struct Object { unsigned count; struct Set * in; };
不需要修改Set.h中提供的接口我们便可以更改其实现方法。这里我们用动态内存的方法，并且把集合和元素看作结构体：
struct Set { unsigned count; };
struct Object { unsigned count; struct Set * in; };
count keeps track of the number of elements in a set. For an element, count records how many times this element has been added to the set. If we decrement count each time the element is passed to drop() and only remove the element once count is zero, we have a Bag, i.e., a set where elements have a reference count.
count用来记录集合中元素的个数，而对于每个元素来说，count记录该元素已经被加入某集合多少次了。如果用drop()函数从集合中删除该元素的时候我们仅仅对count减一，直到count值为0时才真正删除该元素，此时的数据结构就叫做包（Bag），也就是有引用次数记录的元素的集合。
Since we will use dynamic memory to represent sets and objects, we need to initialize the descriptors Set and Object so that new() can find out how much memory to reserve:
因为我们要用动态存储的方法来表示集合和元素，就需要初始化描述符Set和Object，这样new()才知道需要预留多少内存。
static const size_t _Set = sizeof(struct Set);
static const size_t _Object = sizeof(struct Object);
const void * Set = & _Set;
const void * Object = & _Object;
new() is now much simpler: new()函数变得简单多了：
void * new (const void * type, ...)
{ const size_t size = * (const size_t *) type;
void * p = calloc(1, size);
assert(p);
return p;
}
delete() can pass its argument directly to free() — in ANSI-C a null pointer may be passed to free().
delete()函数也可以将其参数直接传给free()函数——在ANSI-C中空指针也可以传给free()函数。
add() has to more or less believe its pointer arguments. It increments the element’s reference counter and the number of elements in the set:
add()必须更多的信任其指针参数了。其将元素引用计数器与集合元素数都加一。
void * add (void * _set, const void * _element)
{ struct Set * set = _set;
struct Object * element = (void *) _element;
assert(set);
assert(element);
if (! element —> in)
element —> in = set;
else
assert(element —> in == set);
++ element —> count, ++ set —> count;
return element;
}
find() still checks, if the element points to the appropriate set:
find()函数依旧要检查要查找的元素是不是指向着合适的集合：
void * find (const void * _set, const void * _element)
{ const struct Object * element = _element;
assert(_set);
assert(element);
return element —> in == _set ? (void *) element : 0;
}
contains() is based on find() and remains unchanged. contains()函数基于find()所以没有任何变化。
If drop() finds its element in the set, it decrements the element’s reference count and the number of elements in the set. If the reference count reaches zero, the element is removed from the set:
如果drop()函数在集合中发现了其参数所指向的元素，便将该元素的引用计数器和集合元素数减一。如果该元素的引用计数器变为0，则从集合中删除该元素。
void * drop (void * _set, const void * _element)
{ struct Set * set = _set;
struct Object * element = find(set, _element);
if (element)
{ if (—— element —> count == 0)
element —> in = 0;
—— set —> count;
}
return element;
}
We can now provide a new function count() which returns the number of elements in a set:
现在又新加入一个函数count()，用来计算集合中元素的个数：
unsigned count (const void * _set)
{ const struct Set * set = _set;
assert(set);
return set —> count;
}
Of course, it would be simpler to let the application read the component .count directly, but we insist on not revealing the representation of sets. The overhead of a function call is insignificant compared to the danger of an application being able to overwrite a critical value.
当然了，如果直接让程序去读取结构体的count成员会简单很多，但是我们坚持不应泄漏集合的表示方法。与让程序能够直接修改程序关键数值的危险相比，多调用几次函数的代价真不算什么。
Bags behave differently from sets: an element can be added several times; it will only disappear from the set, once it is dropped as many times as it was added. Our application in section 1.6 added the object a twice to the set. After it is dropped from the set once, contains() will still find it in the bag. The test program now has the output
ok
drop?
包和集合不同：在包中，任何一个元素可以被多次加入；只有被扔掉的次数和放入包中的次数想同时，它才会从包中消失。在1.6的程序中，我们将一个元素两次加入集合，在将其从包中删除一次后，contains()依旧能够从包中找到该元素。程序会有如下输出：
ok
drop?
Summary
总结
For an abstract data type we completely hide all implementation details, such as the representation of data items, from the application code.
对于一个抽象数据结构来说，我们完全隐藏了其所有的实现细节，比如数据项的表示方法等等。
The application code can only access a header file where a descriptor pointer represents the data type and where operations on the data type are declared as functions accepting and returning generic pointers.
程序代码只能访问头文件，该文件仅仅声明数据类型的描述符指针以及作用于该数据类型的操作。
The descriptor pointer is passed to a general function new() to obtain a pointer to a data item, and this pointer is passed to a general function delete() to recycle the associated resources.
描述符指针传给通用函数new()来获得一个指向数据项的指针。这个指针传给另一个通用函数delete()来回收其相关的资源。
Normally, each abstract data type is implemented in a single source file. Ideally, it has no access to the representation of other data types. The descriptor pointer normally points at least to a constant size_t value indicating the space requirements of a data item.
一般来说，每个抽象数据类型都在一个单独的代码文件中实现。理想情况下，它也不能看到别的数据类型的具体实现。描述符指针应该至少指向一个常数值size_t用来指明数据项需要的空间。
Exercises
练习
If an object can belong to several sets simultaneously, we need a different representation for sets. If we continue to represent objects as small unique integer values, and if we put a ceiling on the number of objects available, we can represent a set as a bitmap stored in a long character string, where a bit selected by the object value is set or cleared depending on the presence of the object in the set.
如果一个元素可以同时属于多个集合，集合的实现就必须改变了。如果我们继续用一些惟一的小整数来表示元素，并且限定了可用元素的上限，那么就可以把一个集合表示成一个位图，并以一个长字符串的形式存储。其中某一位如果是选中的就表示其对应的元素在该集合中，否则则不在。
A more general and more conventional solution represents a set as a linear list of nodes storing the addresses of objects in the set. This imposes no restriction on objects and permits a set to be implemented without knowing the representation of an object.
更通用更常见的方法是用线性链表的节点存放集合中元素的地址。这种方法对元素没有任何限制，并且允许在不了解元素的实现方法的情况下实现集合。
For debugging it is very helpful to be able to look at individual objects. A reasonably general solution are two functions
能查看单个元素对于调试是很有帮助的。一个合理的通用解决方法是定义两个函数：
int store (const void * object, FILE * fp);
int storev (const void * object, va_list ap);
store() writes a description of the object to the file pointer. storev() uses va_arg() to retrieve the file pointer from the argument list pointed to by ap. Both functions return the number of characters written. storev() is practical if we implement the following function for sets:
store() 向文件指针fp所指文件内写入对元素的描述。storev()则使用va_arg()取得ap所指之参数表中的文件指针，然后向该文件指针写入对元素的描述。两个函数都返回写入的字符数。在下列的集合函数中storev()更实用一些：
int apply ( const void * set,
int (* action) (void * object, va_list ap), ...);
apply() calls action() for each element in set and passes the rest of the argument list. action() must not change set but it may return zero to terminate apply() early. apply() returns true if all elements were processed.
apply() 对集合中的每一个元素调用 action()，并将参数表中其余的参数传递给action()。action() 不可以改变集合，但可以通过返回0而提早终止apply()。若所有元素都得到处理则apply()返回true。
