set_add 和 set_contains 错误

Question

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

我们用于测试集合 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。此更改不会反映在调用 set_add.

的函数中

您应该将函数更改为：

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

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

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

示例实现可能如下所示：

接口，例如在 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 是私有的。当然，它实现了以下功能：

#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;
}

set_add 和 set_contains 错误

Errors with set_add and set_contains

c

struct

pointers

linked-list