图9-1 交叉引用列表的数据结构
集合 （set）是不同 成员的无序 汇集。对集合的基本操作包括检验成员资格、添加成员和删除成员。其他操作包括集合的并、交、差和对称差。给定两个集合s和t，并集s+t是包含s和t中所有成员的一个集合，交集s*t包含所有既出现在s中、也出现在t中成员，差集s-t包含所有仅出现在s中、而不出现在t中的成员，对称差集通常记作s/t，包含了所有仅出现在s或t其中之一的成员。
描述集合时，通常会用到全集 （universe），即所有可能成员的集合。例如，字符的集合通常关联到由256个八位字符码构成的全集。当确定了全集U时，可以定义集合s的补集，即U-s。
由Set接口提供的集合不依赖全集。该接口导出了操作集合成员的函数，但从不直接查看集合成员。在这方面，Set接口的设计类似于Table接口，都由客户程序提供函数来查看特定集合中成员的属性。
应用程序使用集合的方式，与使用表的方式非常相似。实际上，Set接口定义的集合与表类似：集合成员是键，而与键关联的值被忽略了。
〈set.h 〉≡ #ifndef SET_INCLUDED #define SET_INCLUDED #define T Set_T typedef struct T *T; 〈exported functions 100〉 #undef T #endif
Set接口导出的函数分为四组：分配和释放、基本集合操作、集合遍历和接受集合操作数并返回新集合的操作，如集合并操作。前三组中的函数与Table接口中的函数类似。
Set_T实例由下列函数分配和释放：
〈exported functions
100〉≡
extern T Set_new (int hint,
int cmp(const void *x, const void *y),
unsigned hash(const void *x));
extern void Set_free(T *set);
Set_new分配、初始化并返回一新的T实例。hint是对集合预期会包含的成员数目的一个估计，准确的hint值可能会提高性能，但任何非负值都是可接受的。cmp用来比较两个成员，hash用来将成员映射到无符号整数。给定两个成员x和y，cmp(x,y)针对x小于y、x等于y或x大于y的情形，必须分别返回小于零、等于零或大于零的整数。如果cmp(x,y)返回0，那么x和y中只有一个会出现在集合中，而且hash(x)必定等于hash(y)。Set_new可能引发Mem_Failed异常。
如果cmp为NULL函数指针，那么假定集合的成员为原子，如果x=y，那么两个成员x和y就是相等的。类似地，如果hash是NULL函数指针，Set_new会自行提供一个适合于原子的哈希函数。
Set_free释放*set并将其赋值为NULL指针。Set_free并不释放集合的成员，该工作可使用Set_map完成。如果传递给Set_free的set或*set为NULL指针，则是已检查的运行时错误。
基本的集合操作由下列函数提供：
〈exported functions
100〉+≡
extern int Set_length(T set);
extern int Set_member(T set, const void *member);
extern void Set_put (T set, const void *member);
extern void *Set_remove(T set, const void *member);
Set_length返回集合的势 （cardinality），或其所包含成员的数目。如果member在set中，Set_member返回1，否则返回0。Set_put将member添加到set（如果member尚不在set中），Set_put可能引发Mem_Failed异常。Set_remove将member从set删除（如果set包含了member），并返回删除的成员（可能是一个不同于member的指针）。否则（即member不在set中），Set_remove什么都不做并返回NULL。传递给上述例程的set或member为NULL，则是已检查的运行时错误。
下列函数遍历一个集合中的所有成员。
〈exported functions
100〉+≡
extern void Set_map (T set,
void apply(const void *member, void *cl), void *cl);
extern void **Set_toArray(T set, void *end);
Set_map对集合的每个成员都调用apply。它会将成员本身和客户程序相关的指针cl传递给apply。它并不查看cl。请注意，不同于Table_map，apply不能改变集合的成员。如果传递给Set_map的apply或set为NULL，或apply调用Set_put或Set_remove来改变set的内容，则构成已检查的运行时错误。
Set_toArray返回一个指针，指向一个N+1个元素的数组，其中以任意顺序包含了集合的N个元素。end的值（通常是NULL指针）赋值给数组的第N+1个元素。Set_toArray可能引发Mem_Failed异常。客户程序必须释放返回的数组。传递给Set_toArray的set为NULL，则是已检查的运行时错误。
下列各函数
〈exported functions
100〉+≡
extern T Set_union(T s, T t);
extern T Set_inter(T s, T t);
extern T Set_minus(T s, T t);
extern T Set_diff (T s, T t);
执行本章开头描述的4个集合操作。Set_union返回s+t，Set_inter返回s*t，Set_minus返回s-t，Set_diff返回s/t。所有这4个函数都会创建并返回新的T实例并可能引发Mem_Failed异常。这些函数将为NULL的s或t解释为空集，但总是返回一个新的、非NULL的T实例。因而，Set_union(s,NULL)返回s的一个副本。对于上述各个函数，如果s和t都是NULL，或s和t都不是NULL，但二者的比较函数和哈希函数不同时，则构成已检查的运行时错误。即，此前调用Set_new创建s和t时，必须指定了相同的比较函数和哈希函数。
xref输出其各个输入文件中标识符的交叉引用列表，这是很有用的，例如，可用于找到程序源文件中对特定标识符的所有引用。例如，
% xref xref.c getword.c
...
FILE getword.c: 6
xref.c: 18 43 72
...
c getword.c: 7 8 9 10 11 16 19 22 27 34 35
xref.c: 141 142 144 147 148
...
输出表明，FILE用于getword.c的第6行和xref.c的第18行、第43行和第72行。类似地，c出现在getword.c中11个代码行，以及xref.c中的5个代码行。一个行号只列出一次，即使该标识符在这一行出现了多次。输出按排序次序列出了文件和行号。
如果程序没有参数，xref将输出标准输入中的标识符的交叉引用列表，并省略上述的样例输出中的文件名：
% cat xref.c getword.c | xref
...
FILE 18 43 72 157
...
c 141 142 144 147 148 158 159 160 161 162 167 170 173 178
185 186 ...
xref的实现说明了如何协同使用集合和表。它建立了一个表，由标识符索引，而每个相关联的值则是另一个表，由文件名索引。表中的值是集合，包含了若干整数指针，指向标识符出现的行号。图9-1描述了这个结构，并给出了上述第一次输出后与标识符FILE相关的细节。在单一的顶层表中与FILE（在下文的代码中，即为标识符的值）相关联的值，是一个处于第二层的表Table_T，包含了两个键：表示getword.c和xref.c的原子。与这些键关联的值是Set_T实例，集合中保存的是整数指针，指向FILE出现的行号。在顶层表中，对于每个标识符，都有一个二级表；在每一个二级表中，每个键—值对中的值都是一个集合。
图9-1 交叉引用列表的数据结构
〈xref.c 〉≡ 〈xref includes 103〉 〈xref prototypes 104〉 〈xref data 105〉 〈xref functions 102〉
xref的main函数与wf的非常相似：它创建标识符表，然后处理文件名参数。它会分别打开每个文件，并用FILE指针、文件名和标识符表作为参数，来调用xref函数。如果没有参数，则调用xref时，传递的参数是NULL文件名指针、对应于标准输入的FILE指针和标识符表：
〈xref functions 102〉≡ int main(int argc, char *argv[]) { int i; Table_T identifiers = Table_new(0, NULL, NULL); for (i = 1; i < argc; i++) { FILE *fp = fopen(argv[i], "r"); if (fp == NULL) { fprintf(stderr, "%s: can't open '%s' (%s)\n", argv[0], argv[i], strerror(errno)); return EXIT_FAILURE; } else { xref(argv[i], fp, identifiers); fclose(fp); } } if (argc == 1) xref(NULL, stdin, identifiers); 〈print the identifiers 103〉 return EXIT_SUCCESS; } 〈xref includes 103〉≡ #include <stdio.h> #include <stdlib.h> #include <errno.h> #include "table.h"
xref会建立一个复杂的数据结构，如果首先考察如何输出该数据结构的内容（通过遍历其各个组成部分），那么就更容易理解如何建立该数据结构。编写独立的代码块或函数来分别处理数据结构的各个组成部分，有助于读者理解遍历过程的细节。
第一步建立标识符及其值（二级表）的数组，并按标识符对数组排序，然后遍历数组调用另一个函数print来处理各个二级表。这个步骤与wf的代码块<print the words 103>很相似。
〈print the identifiers
103〉≡
{
int i;
void **array = Table_toArray(identifiers, NULL);
qsort(array, Table_length(identifiers),
2*sizeof (*array), compare);
for (i = 0; array[i]; i += 2) {
printf("%s", (char *)array[i]);
print(array[i+1]);
}
FREE(array);
}
identifiers中的各个键是原子，因此传递给标准库函数qsort的比较函数compare，与wf中使用的compare是相同的，都使用strcmp来比较一对标识符（8.2节解释了qsort的参数）：
〈xref functions 102〉+≡ int compare(const void *x, const void *y) { return strcmp(*(char **)x, *(char **)y); } 〈xref includes 103〉+≡ #include <string.h> 〈xref prototypes 104〉≡ int compare(const void *x, const void *y);
identifiers中的每个值都是另一个表，将传递给print函数。这个表中的键是表示文件名的原子，因此可以使用与上文类似的代码，将键和值导出到一个数组中排序并遍历。
〈xref functions 102〉+≡ void print(Table_T files) { int i; void **array = Table_toArray(files, NULL); qsort(array, Table_length(files), 2*sizeof (*array), compare); for (i = 0; array[i]; i += 2) { if (*(char *)array[i] != '\0') printf("\t%s:", (char *)array[i]); 〈print the line numbers in the set array[i+1] 104〉 printf("\n"); } FREE(array); } 〈xref prototypes 104〉+≡ void print(Table_T);
print可以使用compare，因为相关的键只是字符串。如果没有文件名参数，那么传递给print的每个表都只有一个项，其键是一个零长度的原子。print使用该约定，来避免在输出行号列表之前输出文件名。
传递给print的表中，每个值都是一个行号的集合。因为Set实现了指针的集合，xref用指向整数的指针来表示行号，并将这些指针添加到集合中。为输出它们，程序调用Set_toArray构建并返回一个整数指针的数组，以NULL指针结尾，然后排序该数组并输出整数行号：
〈print the line numbers in the set
array[i+1] 104〉≡
{
int j;
void **lines = Set_toArray(array[i+1], NULL);
qsort(lines, Set_length(array[i+1]), sizeof (*lines),
cmpint);
for (j = 0; lines[j]; j++)
printf(" %d", *(int *)lines[j]);
FREE(lines);
}
cmpint与compare类似，但其参数为两个指向整数的双重指针，通过比较整数值来返回结果：
〈xref functions 102〉+≡ int cmpint(const void *x, const void *y) { if (**(int **)x < **(int **)y) return -1; else if (**(int **)x > **(int **)y) return +1; else return 0; } 〈xref prototypes 104〉+≡ int cmpint(const void *x, const void *y);
xref建立上述代码输出的数据结构时，使用的是此前讨论过的代码。它使用getword从输入读取标识符。对于每个标识符，程序从数据结构中找到对应的集合，并将当前行号添加到集合中：
〈xref functions 102〉+≡ void xref(const char *name, FILE *fp, Table_T identifiers){ char buf[128]; if (name == NULL) name = ""; name = Atom_string(name); linenum = 1; while (getword(fp, buf, sizeof buf, first, rest)) { Set_T set; Table_T files; const char *id = Atom_string(buf); 〈files ← file table in identifiers associated with id 106〉 〈set ← set in files associated with name 106〉 〈add linenum to set, if necessary 107〉 } } 〈xref includes 103〉+≡ #include "atom.h" #include "set.h" #include "mem.h" #include "getword.h" 〈xref prototypes 104〉+≡ void xref(const char *, FILE *, Table_T);
linenum是一个全局变量，每次first遇到一个换行符时，都将linenum加1，first是传递给getword的函数指针参数，用于识别标识符的首字母：
〈xref data 105〉≡ int linenum; 〈xref functions 102〉+≡ int first(int c) { if (c == '\n') linenum++; return isalpha(c) || c == '_'; } int rest(int c) { return isalpha(c) || c == '_' || isdigit(c); } 〈xref includes 103〉+≡ #include <ctype.h>
getword以及传递给它的first和rest函数，已经在8.2节描述过。
〈xref prototypes
104〉+≡
int first(int c);
int rest (int c);
穿过两层表以找到适当集合的代码，必须处理数据结构中某些部分缺失的问题。例如，在第一次遇到某个标识符时，identifiers表中没有对应的项，因此代码需要创建文件表（下面代码中的files表），并将“标识符—文件表”对（下面代码中的id和files）即时添加到identifiers表：
〈files ← file table in identifiers associated with id 106〉≡ files = Table_get(identifiers, id); if (files == NULL) { files = Table_new(0, NULL, NULL); Table_put(identifiers, id, files); }
类似地，在一个新文件中第一次遇到某个标识符时，行号的集合尚不存在，因此需要创建一个新集合并将其添加到files表：
〈set ← set in files associated with name 106〉≡ set = Table_get(files, name); if (set == NULL) { set = Set_new(0, intcmp, inthash); Table_put(files, name, set); }
这些集合的成员是指向整数的指针，intcmp和inthash比较并散列整数值。intcmp类似上文的cmpint，但其参数是集合中的指针，因此它可以调用cmpint。可以直接用整数本身作为其哈希码：
〈xref functions 102〉+≡ int intcmp(const void *x, const void *y) { return cmpint(&x, &y); } unsigned inthash(const void *x) { return *(int *)x; } 〈xref prototypes 104〉+≡ int intcmp (const void *x, const void *y); unsigned inthash(const void *x);
在控制到达代码块<add linenum to set, if necessary 107>时，set就是应该插入当前行号的目标集合。插入操作由下述代码完成：
int *p; NEW(p); *p = linenum; Set_put(set, p);
但如果set已经包含linenum，该代码将产生内存泄漏，因为指向新分配内存空间的指针不会添加集合中 [1] 。仅当linenum不在set中时才分配内存空间，即可避免内存泄漏。
〈add linenum to set, if necessary 107〉≡ { int *p = &linenum; if (!Set_member(set, p)) { NEW(p); *p = linenum; Set_put(set, p); } }
Set接口的实现与Table的实现非常相似。它用哈希表表示集合，并使用比较函数和哈希函数在表中定位成员。章后的习题，针对下述实现和Table接口的实现，探讨了一些可行的备选方案。
〈set.c 〉≡ #include <limits.h> #include <stddef.h> #include "mem.h" #include "assert.h" #include "arith.h" #include "set.h" #define T Set_T 〈types 108〉 〈static functions 108〉 〈functions 108〉
Set_T是一个哈希表，其中通过链表来保存集合的成员：
〈types
108〉≡
struct T {
int length;
unsigned timestamp;
int (*cmp)(const void *x, const void *y);
unsigned (*hash)(const void *x);
int size;
struct member {
struct member *link;
const void *member;
} **buckets;
};
length是集合中成员的数目，timestamp用于实现Set_map中的已检查的运行时错误，即禁止apply修改集合，cmp和hash分别指向比较函数和哈希函数。
类似Table_new，Set_new会为buckets数组计算一个适当的容量，并将容量值记录在size字段中，并分配struct T实例和buckets数组所需的空间：
〈functions
108〉≡
T Set_new(int hint,
int cmp(const void *x, const void *y),
unsigned hash(const void *x)) {
T set;
int i;
static int primes[] = { 509, 509, 1021, 2053, 4093,
8191, 16381, 32771, 65521, INT_MAX };
assert(hint >= 0);
for (i = 1; primes[i] < hint; i++)
;
set = ALLOC(sizeof (*set) +
primes[i-1]*sizeof (set->buckets[0]));
set->size = primes[i-1];
set->cmp = cmp ? cmp : cmpatom;
set->hash = hash ? hash : hashatom;
set->buckets = (struct member **)(set + 1);
for (i = 0; i < set->size; i++)
set->buckets[i] = NULL;
set->length = 0;
set->timestamp = 0;
return set;
}
Set_new使用hint选择primes中的一个值，作为buckets数组的容量（参见8.3节）。如果成员是原子（cmp或者hash是NULL函数指针，即表明这一点），Set_new将使用下列比较和哈希函数，这与Table_new使用的函数是相同的。
〈static functions
108〉≡
static int cmpatom(const void *x, const void *y) {
return x != y;
}
static unsigned hashatom(const void *x) {
return (unsigned long)x>>2;
}
检验成员资格类似在表中查找键：散列所检验的成员，并搜索buckets中与散列值对应的链表
〈functions 108〉+≡ int Set_member(T set, const void *member) { int i; struct member *p; assert(set); assert(member); 〈search set for member 109〉 return p != NULL; } 〈search set for member 109〉≡ i = (*set->hash)(member)%set->size; for (p = set->buckets[i]; p; p = p->link) if ((*set->cmp)(member, p->member) == 0) break;
如果搜索取得成功，那么p不是NULL，否则为NULL，因此检验p即可确定Set_member的结果。
添加一个新成员的过程类似：搜索集合查找该成员，如果搜索失败则添加它。
〈functions 108〉+≡ void Set_put(T set, const void *member) { int i; struct member *p; assert(set); assert(member); 〈search set for member 109〉 if (p == NULL) { 〈add member t o set 109〉 } else p->member = member; set->timestamp++; } 〈add member to set 109〉≡ NEW(p); p->member = member; p->link = set->buckets[i]; set->buckets[i] = p; set->length++;
timestamp用于Set_map中，以强制实施已检查的运行时错误。
Set_remove会删除一个成员，该函数使用一个指向member结构的双重指针pp遍历适当的哈希链，直至*pp为NULL或(*pp)->member即为我们感兴趣的成员，后一种情况下，下述代码中的赋值操作*pp=(*pp)->link即可从哈希链中删除该成员。
〈functions
108〉+≡
void *Set_remove(T set, const void *member) {
int i;
struct member **pp;
assert(set);
assert(member);
set->timestamp++;
i = (*set->hash)(member)%set->size;
for (pp = &set->buckets[i]; *pp; pp = &(*pp)->link)
if ((*set->cmp)(member, (*pp)->member) == 0) {
struct member *p = *pp;
*pp = p->link;
member = p->member;
FREE(p);
set->length--;
return (void *)member;
}
return NULL;
}
使用pp遍历哈希链，这使用了与Table_remove相同的惯用法，请参见8.3节。
Set_remove和Set_put通过将集合的length字段减1和加1来跟踪集合中成员的数目，Set_length函数会返回该字段：
〈functions
108〉+≡
int Set_length(T set) {
assert(set);
return set->length;
}
如果集合是非空的，Set_free首先必须遍历各个哈希链，释放其中的member结构实例，然后才能释放集合本身并将*set清零。
〈functions
108〉+≡
void Set_free(T *set) {
assert(set && *set);
if ((*set)->length > 0) {
int i;
struct member *p, *q;
for (i = 0; i < (*set)->size; i++)
for (p = (*set)->buckets[i]; p; p = q) {
q = p->link;
FREE(p);
}
}
FREE(*set);
}
Set_map与Table_map几乎相同：它会遍历各个哈希链，并对每个成员调用apply。
〈functions
108〉+≡
void Set_map(T set,
void apply(const void *member, void *cl), void *cl) {
int i;
unsigned stamp;
struct member *p;
assert(set);
assert(apply);
stamp = set->timestamp;
for (i = 0; i < set->size; i++)
for (p = set->buckets[i]; p; p = p->link) {
apply(p->member, cl);
assert(set->timestamp == stamp);
}
}
一个差别是，Set_map将每个成员（而不是指向每个成员的指针）传递给apply，因此apply不能改变集合中的指针。但它仍然可以通过转换，来修改这些成员所指向的值，这会破坏集合的语义。
Set_toArray比Table_toArray简单，类似List_toArray，它只需分配一个数组并将集合的成员复制到数组中：
〈functions
108〉+≡
void **Set_toArray(T set, void *end) {
int i, j = 0;
void **array;
struct member *p;
assert(set);
array = ALLOC((set->length + 1)*sizeof (*array));
for (i = 0; i < set->size; i++)
for (p = set->buckets[i]; p; p = p->link)
array[j++] = (void *)p->member;
array[j] = end;
return array;
}
p->member必须从const void*转换为void*，因为数组并未声明为常量。
所有4个集合操作的实现都是类似的。例如，s + t通过将s和t的每个成员都添加到一个新的集合来实现，实现时可以首先建立s的一个副本，而后将t的各个成员都添加到副本中（如果尚未包含在该集合中的话）：
〈functions 108〉+≡ T Set_union(T s, T t) { if (s == NULL) { assert(t); return copy(t, t->size); } else if (t == NULL) return copy(s, s->size); else { T set = copy(s, Arith_max(s->size, t->size)); assert(s->cmp == t->cmp && s->hash == t->hash); {〈for each member q in t 112〉 Set_put(set, q->member); } return set; } } 〈for each member q in t 112〉≡ int i; struct member *q; for (i = 0; i < t->size; i++) for (q = t->buckets[i]; q; q = q->link)
内部函数copy返回其参数的一个副本，参数必须不能为NULL。
〈static functions 108〉+≡ static T copy(T t, int hint) { T set; assert(t); set = Set_new(hint, t->cmp, t->hash); {〈for each member q in t 112〉 〈add q->member to set 112〉 } return set; } 〈add q->member to set 112〉≡ { struct member *p; const void *member = q->member; int i = (*set->hash)(member)%set->size; 〈add member to set 109〉 }
Set_union和copy都可以访问特许信息：它们都知道集合的表示，因而可以通过向Set_new传递适当的hint值，来为新的集合指定哈希表的大小。Set_union在建立s的副本时需要提供hint，它使用s或t中较大的哈希表的容量，因为结果集合包含的成员数目，至少等于Set_union中最大的参数集合的成员数。copy可以调用Set_put将每个成员添加到副本集合中，但它使用<add q->member to set 155>代码块，这使得添加操作更为直接，避免了Set_put中不必要的搜索步骤。
交集操作s*t，将利用s或t中较小的哈希表创建一个新的集合，仅当某个成员同时出现在s和t中时，才将其添加到新的集合：
〈functions 108〉+≡ T Set_inter(T s, T t) { if (s == NULL) { assert(t); return Set_new(t->size, t->cmp, t->hash); } else if (t == NULL) return Set_new(s->size, s->cmp, s->hash); else if (s->length < t->length) return Set_inter(t, s); else { T set = Set_new(Arith_min(s->size, t->size), s->cmp, s->hash); assert(s->cmp == t->cmp && s->hash == t->hash); {〈for each member q in t 112〉 if (Set_member(s, q->member)) 〈add q->member to set 112〉 } return set; } }
如果s成员数比t少，那么Set_inter将在调换s和t之后，递归调用自身 [2] 。这使得最后一个else子句中的for循环将遍历较小的集合。
差集操作s-t将创建一个新集合，并将s中那些不属于t的成员添加到新集合中。下述代码调换 了参数的名称，以便使用代码块<for each member q in t 112>来遍历s：
〈functions 108〉+≡ T Set_minus(T t, T s) { if (t == NULL){ assert(s); return Set_new(s->size, s->cmp, s->hash); } else if (s == NULL) return copy(t, t->size); else { T set = Set_new(Arith_min(s->size, t->size), s->cmp, s->hash); assert(s->cmp == t->cmp && s->hash == t->hash); {〈for each member q in t 112〉 if (!Set_member(s, q->member)) 〈add q->member to set 112〉 } return set; } }
对称差操作s/t创建的集合中，其成员只出现在s或t其中一个集合中，而不会同时出现在s和t中。如果s或t是空集，那么s/t等于t或s。否则，s/t等于(s-t)+(t-s)，即首先遍历s，将不在t中的各个成员添加到新集合中，而后遍历t，将不在s中的各个成员添加到新集合。代码块<for each member q in t 112>可以用于这两次遍历，只需要在两次遍历之间切换s和t的值即可：
〈functions 108〉+≡ T Set_diff(T s, T t) { if (s == NULL) { assert(t); return copy(t, t->size); } else if (t == NULL) return copy(s, s->size); else { T set = Set_new(Arith_min(s->size, t->size), s->cmp, s->hash); assert(s->cmp == t->cmp && s->hash == t->hash); {〈for each member q in t 112〉 if (!Set_member(s, q->member)) 〈add q->member to set 112〉 } { T u = t; t = s; s = u; } {〈for each member q in t 112〉 if (!Set_member(s, q->member)) 〈add q->member to set 112〉 } return set; } }
这4个操作的更高效实现是可能的，习题探讨了其中一些方案。一个特例是当s和t中的哈希表容量相同时，这对一些应用程序可能是比较重要的，参见习题9.7。
Set接口导出的集合模仿了Icon[Griswold and Griswold，1990]中的集合，其实现也类似于Icon[Griswold and Griswold，1986]中的实现。对于固定的、较小的全集来说，通常使用位向量来表示集合，第13章描述了使用该方法的一个接口。
Icon是将集合作为内建数据类型的少数语言之一。集合是SETL中的中心数据类型，其大部分运算符和控制结构都用来操作集合。
9.1 使用Table接口实现Set接口。
9.2 使用Set接口实现Table接口。
9.3 Set和Table接口的实现有许多共同之处。设计并实现另一个接口，提炼出二者的共同特性。该接口的目的是，支持类似集合和表的ADT的实现。使用你的新接口，重新使用Set和Table接口。
9.4 为包 （bag）设计一个接口。包类似集合，但其成员可以出现多次。例如，{1 2 3}是一个整数集合，而{1 1 2 2 3}是一个整数包。使用前一道习题中设计的支持接口，来实现本接口。
9.5 copy在创建其参数集合的副本时，每次复制一个成员。因为它知道副本中成员的数目，因此可以一次性地分配所有的member结构实例，然后在填充副本集合时将这些member实例添加到适当的哈希链。实现该方案并测量其好处。
9.6 通过在member结构中存储哈希码，可能使一些集合操作更高效，这样对每个成员只需调用一次hash，仅当哈希码相等时才需要调用比较函数。分析此项改进预期会节省的时间，如果看起来值得，那么实现该改进并测量改进后的结果。
9.7 当s和t中哈希桶数目相同时，s+t相当于位于相同哈希链上的各个子集的并集。即s+t中的每个哈希链，是s和t中对应哈希链上的成员的并集。这种情况经常发生，因为许多应用程序在调用Set_new时指定了相同的hint。改变s + t、s * t、s - t和s / t的实现，以检测这种情况，并对其使用更简单、更高效的实现。
9.8 如果一个标识符出现在几个连续行中，xref将输出每一个行号。例如：
c getword.c: 7 8 9 10 11 16 19 22 27 34 35
修改xref.c，使之将多个连续行号替换为一个行范围：
c getword.c: 7-11 16 19 22 27 34-35
9.9 xref分配大量内存，但仅释放Table_toArray创建的数组。修改xref，使之最终释放它分配的所有东西（当然，原子除外）。在数据结构输出时，很容易增量式地完成释放工作。使用习题5.5的答案，来确认是否释放了所有分配的东西。
9.10 解释cmpint和intcmp为何使用显式比较来比较整数，而不是返回二者相减的结果。即cmpint的下述版本看起来简单得多，它有什么问题呢？
int cmpint(const void *x, const void *y) {
return **(int **)x - **(int **)y;
}
[1] 应当是集合，不是表。——译者注
[2] 其实可以直接调换s和t，不必要递归。——译者注