Ошибки с 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; 
} 

Это не имеет значения, если я использую Нажмите, чтобы нажать на голове или использовать 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; 
}