Как реализовать функцию «содержит» для связанных списков в C

Question

В настоящее время я выполняю задание для uni, и мне нужно найти сумму графика.

Для этого я считаю, мне нужен связанный список, который я могу использовать, чтобы помнить, какие узлы были посещены. У меня есть связанный список, который работает правильно, но я не могу заставить функцию contains работать. Это код, который у меня есть:

struct listnode 
{ 
    struct N *val; 
    struct listnode *next; 
}; 


int contains(struct listnode *head,struct N* value) 
{ 
    struct listnode *current = head; 
    while (current) 
    { 
    if ((current -> val) == value) 
    { 
     return 1; 
    } 
    current = current -> next; 
    } 
    return 0; 
} 

примечание: N - это узел графика.

Может ли кто-нибудь увидеть проблемы с тем, что я делаю?

EDIT: содержит функция должна возвращать 1, если N * имеет значение в списке, 0 в противном случае

EDIT2:

У меня есть толчок функции:

void push(struct listnode *head,struct N *value) 
{ 
    if (head) 
    { 
    struct listnode *current = head; 
    while (current->next) 
    { 
     current = current -> next; 
    } 
    current->next = malloc(sizeof(struct listnode*)); 
    current->next->val = value; 
    current->next->next = NULL; 
    } 
    else 
    { 
    head = malloc(sizeof(struct listnode*)); 
    if (head) 
    { 
     head -> val = value; 
     head -> next = NULL; 
    } 
    else 
    { 
     printf("error"); 
     exit(0); 
    } 
    } 
} 

и я хочу следующее линия для возврата 1:

contains(push(visited,p),p); 

где p является указателем на структуру N и посещен m у глобального связанный список

EDIT3:

это моя последняя функция суммы, которую я считаю, должен работать, но оленья кожа из-за того, содержит.

long sum(struct N *p) 
{ 
    if (p) 
    { 
    if (contains(visited,p) == 0) //if p hasnt been visited 
    { 
     push(visited,p); //make it visited 
     return (p -> data) + sum(p -> x) + sum(p -> y) + sum(p -> z); 
    } 
    else 
    { 
     return 0; 
    } 
    } 
    else 
    { 
    return 0; 
    } 
} 

Answer 1

Ваша функция отображается в порядке. Проблема в том, что вы всегда передаете ему список NULL, который вызван неисправной функцией push. Вам нужно вернуться в push или передать указатель с еще одним уровнем косвенности, поэтому вы можете назначить head за пределами push.Еще одно возможное улучшение - заметить, что независимо от того, что вы проходите, malloc и инициализация нового узла на самом деле то же самое.

И, наконец, основная проблема, которая, скорее всего, вызовет segfault, заключается в том, что вы выделяете достаточно места для указателя на узел, а не для самого узла.

Вот пример:

#ifdef BY_INDIRECTION 
    #define RET_TYPE void 
    #define IN_TYPE struct listnode ** 
#else 
    #define RET_TYPE struct listnode * 
    #define IN_TYPE struct listnode * 
#endif 

RET_TYPE push(IN_TYPE head, struct N *value) 
{ 
    struct listnode *current, **next; 
    if(head) 
    { 
    for(current = head; current->next; current = current->next) ; 
    next = &(current->next); 
    } 
    else 
    { 
#ifdef BY_INDIRECTION 
    next = head; 
#else 
    next = &head; 
#endif 
    } 

    *next = malloc(sizeof(struct listnode)); 
    if(!*next) { 
     printf("error"); 
     exit(0); 
    } 
    (*next)->val = value; 
    (*next)->next = NULL; 

#ifndef BY_INDIRECTION 
    return head 
#endif 
} 

Я включил оба предложения здесь. Если вы хотите прочитать ту, где мы используем косвенность (переходим в listnode ** и получаем void), выберите путь, где определено значение BY_INDIRECTION. Если вы хотите вернуть head (и просто введите listnode *), прочитайте путь, где BY_INDIRECTION не определен.

Последний подход имеет возвращаемое значение, поэтому его можно использовать для написания сокращенной формы, например if(contains(push(head, value), value)) { ... }. Первый подход не делает, так что вы должны сделать

push(&head, value); 
if(contains(head, value)) { ... } 

Я бы рекомендовал использовать косвенный подход независимо, потому что есть очень мало случаев, которые вы хотели бы проверить на сдерживание после сдачи в стоимости.

Answer 2

Это сравнение:

if ((current -> val) == value) 

это сравнение указателей. Если вы называете функции таким образом ...

... 
struct N val_to_find; 
... 
result = contains (list, &val_to_find); 

Вы никогда не найдете значение, даже если содержание val_to_find такие же, как и содержимые любую структуру, указатель хранится в списке.

Если ваше намерение для , чтобы найти узлы, которые имеют одни и те же данные, а не только одни и те же указатели, я хотел бы предложить вам что-то вроде этого:

if (struct_n_comparing_function (current -> val, value) == EQUAL) ... 

Где struct_n_comparing_function должны иметь следующий прототип:

int struct_n_comparing_function (struct N *a, struct N *b); 

, которая сравнивает содержимое двух структур, указываемых a и b и возвращает EQUAL, если все поля на структуры указываемого a имеют то же значение, что и поля структуры, на которые указывает b.