Linked List Search not working (SIGBUS error and memory leak)-CodePudding

i made a C program implementing linked lists but it won't work... everything i implemented was taken from websites or stackoverflow and it seems to be working for everyone, still does not work for me. Everytime i run the program (which has an input of a series of word in STDIN, one for row) it gives me Process finished with exit code 138 (interrupted by signal 10: SIGBUS) and debugging it it seems to be stuck at if (strcmp(var->word, searched) == 0) line in the Search function... where am i wrong? I suppose there's something related to pointers but i do not understand what. The programs starts working and prints something, then breaks and the temp value gets no word as it says read memory from 0x6c62430000600000 failed (0 of 1 bytes read).

Here is the code:

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


struct node{
    char* word;
    struct node* next;
};

int search(struct node** head, char* searched);
void Print(struct node* head);
void Free_All(struct node* head);
void Insert(struct node** head, char* word);
void Delete(struct node* head, char* to_delete);
int Count(struct node* head);


int main() {
    static struct node *head = NULL;

    int temp;
    char word[20];

    for (;;) {
        temp = scanf("%s", word);

        if (strcmp(word, "Print") == 0) {
            Print(head);
        }
        else if (strcmp(word, "Stop") == 0) {
            break;
        } 
        else if (temp == EOF) {
            Free_All(head);
            return 0;
        } 
        else {
            Insert(&head, word);
        }
    }

    scanf("%s", word);
    int found = search(&head, word);

    if (found == 0) {
        printf("!! ERROR !!");
        return 1;
    }

    else {
        char to_delete[15];
        scanf("%s", to_delete);
        Delete(head,to_delete);

        // DO OTHER STUFF
    }

    int count = Count(head);
    printf("Remaining nodes: %d",count);
    Free_All(head);
}




int search(struct node** head, char* searched) {
    struct node* var = *head;

    while (var != NULL) {
        if (strcmp(var->word, searched) == 0)
            return 1;
        var = var->next;
    }
    return 0;
}

void Print(struct node* head){
    struct node* temp = head;
    while (temp) {
        printf("%s \n", temp->word);
        temp = temp->next;
    }
}

void Free_All(struct node* head){
    struct node* temp;
    temp = head;

    while( temp != NULL ){
        head= head->next;
        free(temp);
        temp = head;
    }
}


void Insert(struct node** head, char* word)
{
    // Create new node
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
    new_node->word = malloc(strlen(word) 1);
    new_node->word = strcpy(new_node->word,word);
    new_node->next = NULL;

    if (*head== NULL || strcmp((*head)->word, new_node->word) >= 0) {
        new_node->next = *head;
        *head= new_node;
    }
    else {
        struct node* temp = *head;
        temp = *head;
        while (temp->next != NULL && strcmp(temp->next->word, new_node->word) < 0) {
            temp = temp->next;
        }
        new_node->next = temp->next;
        temp->next = new_node;
    }
}

void Delete(struct node* head, char* to_delete) {
    struct node *temp = head;
    struct node *prev = NULL;
    while(temp != NULL){
        if(strcmp(temp->word, to_delete) == 0)
        {
            if(prev == NULL){
                head = head->next;
                free(temp);
                return;
            }
            else{
                prev->next = temp->next;
                free(temp);
                return;
            }
        }
        prev = temp;
        temp = temp->next;
    }
}

int Count(struct node* head){
    int counter = 0;
    struct node* var = head;
    while (var != NULL)
    {
        counter  ;
        var = var->next;
    }
    return counter;
}

EDIT: Solved typo in main

CodePudding user response：

The function Delete accepts the pointer to the head node by value

void Delete(struct node* head, char* to_delete);

So the function deals with a copy of the value of the pointer head declared in main

static struct node *head = NULL;

Changing the copy of the value of the pointer head declared in main leaves the value of the original pointer unchanged.

You need to pass the pointer by reference through a pointer to it.

For example the function can be declared and defined the following way.

int Delete( struct node **head, const char *to_delete ) 
{
    while ( *head != NULL && strcmp( ( *head )->word, to_delete ) != 0 )
    {
        head = &( *head )->next;
    }

    int success = *head != NULL;

    if ( success )
    {
        struct node *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }

    return success;
}

Pay attention to that this for loop

for (;;) {
    temp = scanf("%s", word);

    if (strcmp(word, "Print") == 0) {
        Print(head);
    }

    if (strcmp(word, "Stop") == 0) {
        break;
    } else if (temp == EOF) {
        Free_All(head);
        return 0;
    } else {
        Insert(&head, word);
    }
}

has a wrong logic. For example if the user will enter the string "Print" then apart from calling the function Print there will be called the function

Insert(&head, word);

And the function Free_All actually does not free all. It does not free character arrays pointed to by the data member word.

void Free_All(struct node* head){
    struct node* temp;
    temp = head;

    while( temp != NULL ){
        head= head->next;
        free(temp);
        temp = head;
    }
}

The function also shall accept the pointer to the head node by reference. It can look the following way

void Free_All( struct node **head )
{
    while ( *head != NULL )
    {
        free( ( *head )->word );
        struct node *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }
}

CodePudding user response：

I don't have the time or patience to go through line-by-line what's wrong with your code. Right now, Delete of first item on the list does NOT affect the 'head' pointer in 'main()', so using that pointer to Count() or FreeAll() is undefined behaviour.

Here's a bit of code. Use pencil & paper to keep track of the very few variables in use, and where pointers are pointing.

void Print( struct node *p ) {
    for( ; p; p = p->next )
        printf( "%s ", p->word );
    putchar( '\n' );
}

void Insert( struct node **head, char *word ) {
    // assemble new node
    struct node *nn = (struct node*)malloc( sizeof node );
    nn->word = (char*)malloc( strlen( word )   1 );
    nn->word = strcpy( nn->word, word );
    nn->next = NULL;

    // find insertion point
    struct node *pPrev = NULL;
    struct node *pThis = *head;
    while( pThis && strcmp( word, pThis->word ) >= 0 )
        pPrev = pThis, pThis = pThis->next;

    // insert into (possibly empty) list
    if( pThis ) nn->next = pThis;
    if( pPrev ) pPrev->next = nn;
    if( pThis == *head ) *head = nn; // new head?
}

void Delete( struct node **head, char *word ) {
    struct node *pPrev = NULL;

    for( struct node *pThis = *head; pThis; pPrev = pThis, pThis = pThis->next ) {
        int res = strcmp( pThis->word, word );

        if( res < 0 ) // not found yet
            continue;
        if( res > 0 ) // gone beyond, so not present
            break;

        // Found!
        if( pPrev ) pPrev->next = pThis->next; // excise from list
        if( pThis == *head ) *head = pThis->next; // change head??
        free( pThis->word ); // release memory
        free( pThis ); // release memory
        break;
    }
}

int main() {
    struct node *head = NULL;

    char word[20];

    printf( "Entry phase:\n" );
    for( ;; ) {
        Print( head );

        scanf( "%s", word );

        if( strcmp( word, "Stop" ) == 0 )
            break;

        Insert( &head, word );
    }

    printf( "Delete phase:\n" );
    while( head ) {
        Print( head );

        scanf( "%s", word );

        if( strcmp( word, "Stop" ) == 0 )
            break;

        Delete( &head, word );
    }

    return 0;
}

Output:

Entry phase:

baker
baker
delta
baker delta
able
able baker delta
epsilon
able baker delta epsilon
charlie
able baker charlie delta epsilon
Stop
Delete phase:
able baker charlie delta epsilon
able
baker charlie delta epsilon
epsilon
baker charlie delta
charlie
baker delta
baker
delta
delta
{ program halts }