C - 如何遍历 ADT 结构？

Question

我正在为一项学校作业制作一套 ADT，而且我已经快要完成了。但是，对于如何迭代结构中的各个项目，我遇到了一些困难:集合结构的“元素”成员必须是空指针，如果它是 int 类型，我可以set->element[i]。对替代品有什么建议吗？

struct set
{
    void *element;
    int size;
    cmpfunc_t cmpfunc;
    set_t *start;
    set_t *next;
};

int set_contains(set_t *set, void *elem)
{
    for(int i = 0;i<set->size;++i)
      if(set->element[i] == elem)
        return 1;

    return 0;
}

Answer 1

您的 ADT 结构并没有多大意义；看起来您已经尝试过混合不同的设计模式，即使用数组来保存集合元素，以及使用链表来保存集合。

我会冒昧地修改结构，使其更符合任一模式。首先，typedef 的隐藏信息 -> 尽可能避免它们。

第一种模式:使用元素数组

struct set {
  void **elements;              /* array of elements    */
  int nElem;                    /* array count          */
  size_t elemSize;              /* size of element type */
  int(*cmpFunc)(void*, void*);  /* equality comparison  */
};

elemSize 字段用于在不知道数据类型的情况下分配和复制新元素。这对于两种模式和一般的通用 ADT 都是常见的。要迭代此集合，请使用:

int set_contains(struct set *pSet, void *elem) {
  for (int i = 0; i < pSet->nElem; ++i) {
    if (pSet->cmpFunc(pSet->elements[i], elem))
      return 1;
  }
  return 0;
}

第二种模式:使用链表表示集合

struct node {
  void *data;         /* element data      */
  struct node *next;  /* next node in list */
};

struct set{
  struct node *head;            /* first element       */
  size_t elemSize;              /* size of data type   */
  int(*cmpFunc)(void*, void*);  /* equality comparison */
};

元素大小和比较函数是给定集合的属性，而不是该集合中包含的数据，因此它们定义在 set 结构上，而不是 node 结构，它只定义了数据和关联的链接。要迭代此集合，请使用:

int set_contains(struct set *pSet, void *elem) {
  struct node *head = pSet->head;
  while(head) {
    if (pSet->cmpFunc(head->data, elem))
      return 1;
    head = head->next;
  }
  return 0;
}