Функция поиска по списку со связанными списками

Question

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h> 

/*Define custom functions */ 
void insertElement(); 
bool elementExists(); 
int getNumElements(); 


/*Create linked list */ 
struct node { 
    int number; 
    int occurence; 
    struct node *next; 
}; 

/*Call our linked list freqTable */ 
struct node *freqTable = NULL; 

unsigned int numElements = 0; 

int main(){ 
    int readNumElements = 0; 
    int i = 0; 
    int newNum, status; 

    status = scanf("%d", &readNumElements); 
    if(status == -1){ 
     fprintf(stderr, "%d is not a number\n", readNumElements); 
     exit(-1); 
    } 


    for (i = 0; i < readNumElements;i++) { 
     status = scanf("%d", &newNum); 
     if(status == -1){ 
      fprintf(stderr, "%d is not a number\n", newNum); 
      exit(-1); 
     } 
     if(elementExists(newNum)){ 
      printf("%d exists\n", newNum); 
     }else{ 
      insertElement(&freqTable, newNum); 
     } 

    } 

return 0; 
} 

void insertElement(struct node **list, int n){ 
    struct node *new_input; 

    new_input = malloc(sizeof(struct node)); 

    if(new_input == NULL){ 
     fprintf(stderr,"Error: Failed to create memory for new node\n"); 
     exit(EXIT_FAILURE); 
    } 

    new_input->number = n; 
    new_input->occurence = 1; 
    new_input->next = *list; 
    numElements++; 

    *list = new_input; 
} 

bool elementExists(int n){ 
    printf("%d\n", freqTable->number); 
return false; 
} 

int getNumElements(){ 
    return numElements; 
} 

Ой, что у меня есть. Это должно скомпилировать.

Проблема приходит на

if(elementExists(newNum)){ 
     printf("%d exists\n", newNum); 
    }else{ 
     insertElement(&freqTable, newNum); 
    } 

Я получаю ошибку сегментации, и я не знаю, почему.

Answer 1

В функции elementExists вам необходимо убедиться, что freqTable не NULL:

bool elementExists(int n){ 
if(freqTable) { // add this check 
    printf("%d\n", freqTable->number); 
} 
} 

Также ваш elementExists не делать то, что его должен делать (проверка на наличие узла со значением n), вы должны сделать что-то вроде:

bool elementExists(int n) { 

if(!freqTale) { // table does not exist..return false. 
    return false; 
} 
// table exists..iterate node by node and check. 
struct node *tmp = freqTable; 
while(tmp) { // loop till tmp becomes NULL 
    if(*tmp == n) { // it node contains n..return false. 
    return true; 
    } 
    tmp = tmp->next; // move on 
} 
return false; // n does not exist in the list..return false. 
} 

Answer 2

Как указано в комментариях, вы разыгрываете freqTable в elementExists перед тем, как распределяются любые узлы. Таким образом, freqTable всегда имеет значение NULL, поэтому вы вызываете неопределенное поведение. Вы могли бы просто добавить чек для NULL в elementExists и вернуть false в этом случае.

Answer 3

Там проблема с вызовом elementExists:

if(elementExists(&freqTable, newNum)){ 

Вы передаете адрес freqTable (т. указатель на то, где хранится указатель на первый элемент списка) вместо его значения. Тем не менее, в elementExists вы разыменовать аргумент, как если бы это был указатель на элемент списка:

printf("Compare with: %d\n", list->number); 

и

else list = list->next; 

Удалите & от вызова elementExists. И не обращайтесь к глобальному freqTable внутри elementExists, если вы передаете список в качестве аргумента.