c - set_add 和 set_contains 错误

Question

我目前已经制作了一套ADT，它使用链表函数来实现给定的接口(interface)。

我们用于测试集 ADT 的测试实用程序在 set_add 和 set_contains 上给了我错误。

// Push function, pushes element on head of set
void Push(set_t **set, void *elem) {
        // Allocates memory for a newNode
        set_t *newNode = (set_t *) malloc(sizeof(set_t));
        // sets element to elem which is in input
        newNode->elem = elem;
        // Previous head to next
        newNode->next = *set;
        // Newnode as head
        *set = newNode;
}

void AppendNode(set_t **headRef, void *elem) {
        set_t *current = *headRef;
        set_t *newNode;

        newNode = malloc(sizeof(set_t));
        newNode->elem = elem;
        newNode->next = NULL;

        if (current == NULL) {
                *headRef = newNode;
        }
        else {
                while ( current->next != NULL) {
                        current = current->next;
                }
                current->next = newNode;
        }
}

/*
 * Adds the given element to the given set.
 */
void set_add(set_t *set, void *elem) {
        if (set_contains(set, elem) == 1) {
                return;
        }
        else {
                AppendNode(&set, elem);
        }
}

/*
 * Returns 1 if the given element is contained in
 * the given set, 0 otherwise.
 */
int set_contains(set_t *set, void *elem) {
        set_t *current = set;

        while (current != NULL) {
                if (current->elem == elem) {
                        return 1;
                }
                current = current->next;
        }

        return 0;
}

无论我用Push推头部还是用AppendNode添加尾部都没有关系。

这是我设置的结构:

struct set { 
   void *elem; 
   set_t *next; 
   cmpfunc_t cmpfunc; 
}

有人看到一些非常不对劲的东西吗？

Answer 1

您的 Push 和 AppendNode 函数看起来没问题。错误出在 set_add 上，您将本地 set 更新为 set_add。此更改不会反射(reflect)在调用 set_add 的函数中。

您应该将函数更改为:

void set_add(set_t **set, void *elem) {
    if (set_contains(*set, elem) == 0) {
        AppendNode(set, elem);
    }
}

函数set_contains不需要指针到指针参数，因为它只检查集合，但不会更改它。

编辑 该问题需要使用给定的函数原型(prototype)。在这种情况下，您应该使 set_t 成为包含头节点的链表的接口(interface)。所有函数都接收此接口(interface)作为指针。

示例实现可能如下所示:

接口(interface)，例如在 set.h 中定义，它将 set_t 声明为不透明类型:

typedef struct set set_t;

set_t *set_create(void);
void set_destroy(set_t *set);
void set_add(set_t *set, void *elem);
int set_contains(const set_t *set, void *elem);

set.c 中的实现定义了结构的内容。它还定义了节点的类型，该类型是 set.c 私有(private)的。当然，它还实现了以下功能:

#include <set.h>

typedef struct setnode setnode_t;

struct set {
    setnode_t *head;
};

struct setnode { 
   void *elem; 
   setnode_t *next; 
};

set_t *set_create(void)
{
    set_t *set = malloc(sizeof(*set));

    if (set) set->head = NULL;
    return set;
}

void set_destroy(set_t *set)
{
    setnode_t *curr = set->head;

    while (curr) {
        setnode_t *next = curr->next;
        free(curr);
        curr = next;
    }

    free(set);
}

int set_contains(const set_t *set, void *elem)
{
    setnode_t *curr = set->head;

    while (curr != NULL) {
        if (curr->elem == elem) return 1;
        curr = curr->next;
    }

    return 0;
}

void set_add(set_t *set, void *elem)
{
    if (set_contains(set, elem) == 0) {
        setnode_t *node = malloc(sizeof(*node));

        node->elem = elem;
        node->next = set->head;
        set->head = node;
    }
}

客户端代码可以像这样使用该集合:

#include <set.h>

int main()
{
    set_t *set = set_create();

    for (size_t i = 3; i < 17; i++, i++) {
        set_add(set, (void *) i);
    }

    for (size_t i = 0; i < 20; i++) {
        printf("%4zu %d\n", i, set_contains(set, (void *) i));
    }

    set_destroy(set);

    return 0;
}