Question

main.c 会编译成功，但在连接和执行之前，我们必须实现其中的抽象数据类型和内存管理。如果一个对象不存储信息，且每个对象最多属于一个结合，我们可以把每个对象和集合当成，小的，独立的，正整数的值。可在 heap[] 中通过数组下标来索引到。如果一个对象（这里的对象为数组元素的地址）是一个集合的成员，则数组元素的值代表这个集合。对象指向包含它的集合。

首先的解决方案是非常简单的，即我们把其他模块与 Set.c 相结合。集合对象集有相似的呈现方式。因此，对于 new() 无需关注类型描述。它仅仅从数据 heap[] 中返回非零元素。

void * new (const void * type, ...)
{
  int *p ;  /*&heap[1...]*/
  for(p=heap+1;p<heap+MANY;++p){
    if(!*p){/*若 heap 中的某个元素为 0，则返回这个指针，并把值设为 MANY*/
      break;
    }
  }
  assert(p<heap+MANY);
  *p=MANY;   
  return p;
}

我们是用 0 来标记 heap[] 中有效的元素；因此不能返回 heap[0] 的引用 - 如果它是一个集合，而集合的元素可以是索引值为 0 的对象。

在一个对象被添加到集合当中之前， 我们让它包含无效的索引 MANY ，以便于 new() 不会再次返回它，请不能误解 MANY 是集合的一个成员。

new() 能够使用完内存。这是很多“致命性错误”的其中一个。我们可以简单的使用标准化Ｃ语言宏的宏 assert() 来标记这些错误。一个更理想的实现方式是至少会打印合理的错误信息或使用用户可重写的错误处理机制的通用功能。这也是我们的目的中，编码技术完整性的一部分。在第 13 章，我们会介绍一种通用异常处理的技术。

delete() 必须得严加防范空指针的传入。通过设置其元素的值为 0 来进行 heap[] 中元素的回收。

void delete (void * _item)
{
  int* item=_item;
  if(item){
    assert(item>heap && item,heap+MANY);
    *item=0;
  }
}

我们需要统一的处理通用指针；因此，给每个通用指针的变量的前面加上下划线前缀，然后仅仅使用它初始化指定类型的局部变量。

一个集合被它的对象所表示。集合中的每个元素指向它的集合。如果元素包含 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() 在这里稍微显得逊色：我们只关注在 heap[] 内的指针和集合不属于其他部分的集合，等等，数组元素的值应该为 MANY 。

其他的功能都是很简单的。 find() 只查找元素的值为集合索引的元素。若找到，返回元素，否则返回 NULL 。

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() 把 find() 的结果转换为真值：

int contains(const void* _set,const void* _element)
{
  return find(_set,_element)!=0;
}

drop() 依赖于 find() 的结果，若在集合中查找到，则把此元素的值标记为 MANY ，并返回此元素：

void* drop(void * _set,const void * _element)
{
  int* element=find(_set,_element);
  if(element){
    *element=MANY;
  }
  return element;
}

如果我们深入挖掘，一定会坚持被删除的元素要不包含于其他集合中。在这种情况下，毫无疑问会在 drop() 中复制更多 find() 的代码。

我们的实现是很非传统的。在实现一个集合时似乎不需要 differ() 。我们仍然提供它，因为我们的程序要使用这个函数。

int differ (const void * a, const void * b)
{
  return a!=b;
}

当数组中对象的索引不同时，这个对象必然是不同的，也就是索引值就能区分它们的不同，但一个简单的指针比较已经足够了。

我们已经做完了 - 对于这个问题的解决我们还没有使用描述符 Set 和 Object ，但是不得不定义它以使我们的编译器能通过。

const void * Set;
const void * Object;

我们在 main() 函数中使用上述指针来创建集合和对象。