Когда я пытаюсь стереть элемент из связанного списка, возникает ошибка сегментации

Question

Я начинающий и пытаюсь изучить структуры данных. Я написал код, который удаляет элемент из связанного списка. Если элемент уже существует в списке, никаких проблем не возникает во время компиляции и запуска. Но когда я пытаюсь стереть элемент, которого нет в списке, происходит ошибка сегментации, даже если я уже закодировал этот случай. Не могли бы вы взглянуть и помочь мне?

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int x;
    struct node *next;
}node;

void addElement(node *r, int x)
{
    for(; r->next!=NULL; r=r->next);
    r->next=(node*)malloc(sizeof(node));
    r->next->x=x;
    r->next->next=NULL;

}
node* add_Element_inorder(node *r, int x)
{
    if(r==NULL)
    {
        r=(node*)malloc(sizeof(node));
        r->next=NULL;
        r->x=x;
        return r;
    }
    if(r->x>x)
    {
        node*tmp=(node*)malloc(sizeof(node));
        tmp -> x = x;
        tmp->next=r;
        return tmp;
    }
    node *iter=r;

    while(iter->next!=NULL && iter->next->x < x)
    {

        iter=iter->next;
    }

    node*tmp=(node*)malloc(sizeof(node));
    tmp->next = iter->next;
    iter->next=tmp;
    tmp->x=x;
    return r;

}
void print_Linked_L(node *r)
{
    node* iter = r;
    printf("%d ", iter->x);
    iter=iter->next;
    while(iter != NULL)
    {
        printf("%d ", iter->x);
        iter=iter->next;
    }

}
node* erase_Element(node *r, int x)
{
   node*iter=r;
   if(iter->x == x)
   {
       r=r->next;
       free(iter);
       return r;
   }

   while(iter->next->x != x && iter->next!=NULL)
   {
       iter=iter->next;

   }

    if(iter->next==NULL)
    {
        printf("Number does not exist.");
        return r;
    }

   node *temp=iter->next;
   iter->next=iter->next->next;
   free(temp);
   return r;
}

int main()
{

    node *root = (node*)malloc(sizeof(node));
    root=NULL;
    root= add_Element_inorder(root, 400);
    root= add_Element_inorder(root, 40);
    root= add_Element_inorder(root, 4);
    root= add_Element_inorder(root, 450);
    root= add_Element_inorder(root, 50);
    node *iter=root;
    print_Linked_L(root);
    root =erase_Element(root,45);
    printf("\n");
    print_Linked_L(root);







return 0;
}

Answer 1

while(iter->next->x != x && iter->next!=NULL)

В этом коде сначала запустите iter-> next-> x, а затем iter-> next! = NULL Вы разыменовываете null. Решение:

while(iter->next!=NULL && iter->next->x != x )

Answer 2

На самом деле все функции неверны.

Например, в этой функции

void addElement(node *r, int x)
{
    for(; r->next!=NULL; r=r->next);
    r->next=(node*)malloc(sizeof(node));
    r->next->x=x;
    r->next->next=NULL;

}

нет проверки, равен ли т значению NULL. Функция должна быть определена, по крайней мере, как

node * addElement( node *head, int x )
{
    node *new_node = malloc( sizeof( node ) );
    new_node->x = x;

    if ( head == NULL )
    {
        new_node->next = head;
        head = new_node;
    }
    else
    {
        node *current = head;

        while ( current->next != NULL ) current = current->next;

        new_node->next = NULL;
        current->next = new_node;
    }

    return head;
}    

. В функции add_Element_inorder есть два многократно повторяющихся кода. Функцию можно определить проще.

node * add_Element_inorder( node *head, int x)
{
    node *new_node = malloc( sizeof( node ) );
    new_node->x = x;

    if ( head == NULL || x < head->x )
    {
        new_node->next = head;
        head = new_node;
    }
    else
    {
        node *current = head;

        while ( current->next != NULL && !( x < current->next->x ) )
        {
            current = current->next;
        }

        new_node->next = current->next;
        current->next = new_node;
    }

    return head;
}

Функция print_Linked_L может вызывать неопределенное поведение для пустого списка, когда указатель на головной узел равен NULL.

void print_Linked_L(node *r)
{
    node* iter = r;
    printf("%d ", iter->x);
    //...

Функция может быть определена как

void print_Linked_L( const node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->x );
    }

    puts( "null" );
}

Функция erase_Element снова может вызывать неопределенное поведение, когда нет узла с целевым значением из-за неправильного порядка условия в операторе while

while(iter->next->x != x && iter->next!=NULL)

То есть сначала нужно проверить, является ли iter->next != NULL, и только после этого проверить, не равно ли его значение x.

Функция может быть определена следующим образом

node * erase_Element( node *head, int x )
{
    if ( head != NULL )
    {
        if ( head->x == x )
        {
            node *tmp = head;
            head = head->next;
            free( tmp );
        }
        else
        {
            node *current = head;

            while ( current->next != NULL && current->next->x != x )
            {
                current = current->next;
            }

            if ( current->next != NULL )
            {
                node *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                printf( "Number %d does not exist in the list.\n", x );
            }   
        }
    }

    return head;
}

Функция main запускается с утечки памяти

int main()
{
    node *root = (node*)malloc(sizeof(node));
    root=NULL;

Сначала выделяется память, а затем сразу же возвращается потерянный адрес из-за перезаписи указателя root.

Вот примерный программа, которая показывает обновленные определения функций.

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

typedef struct node
{
    int x;
    struct node *next;
} node;

node * addElement( node *head, int x)
{
    node *new_node = malloc( sizeof( node ) );
    new_node->x = x;

    if ( head == NULL )
    {
        new_node->next = head;
        head = new_node;
    }
    else
    {
        node *current = head;

        while ( current->next != NULL ) current = current->next;

        new_node->next = NULL;
        current->next = new_node;
    }

    return head;
}    

node * add_Element_inorder( node *head, int x)
{
    node *new_node = malloc( sizeof( node ) );
    new_node->x = x;

    if ( head == NULL || x < head->x )
    {
        new_node->next = head;
        head = new_node;
    }
    else
    {
        node *current = head;

        while ( current->next != NULL && !( x < current->next->x ) )
        {
            current = current->next;
        }

        new_node->next = current->next;
        current->next = new_node;
    }

    return head;
}

void print_Linked_L( const node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->x );
    }

    puts( "null" );
}

node * erase_Element( node *head, int x )
{
    if ( head != NULL )
    {
        if ( head->x == x )
        {
            node *tmp = head;
            head = head->next;
            free( tmp );
        }
        else
        {
            node *current = head;

            while ( current->next != NULL && current->next->x != x )
            {
                current = current->next;
            }

            if ( current->next != NULL )
            {
                node *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                printf( "Number %d does not exist in the list.\n", x );
            }   
        }
    }

    return head;
}

int main(void) 
{
    node *root = NULL;

    root = add_Element_inorder( root, 400 );
    root = add_Element_inorder( root, 40 );
    root = add_Element_inorder( root, 4 );
    root = add_Element_inorder( root, 450 );
    root = add_Element_inorder( root, 50 );

    print_Linked_L( root );

    root = erase_Element( root, 45 );
    print_Linked_L(root);   
    root = erase_Element( root, 400 );
    print_Linked_L(root);   
    root = erase_Element( root, 40 );
    print_Linked_L(root);   
    root = erase_Element( root, 4 );
    print_Linked_L(root);   
    root = erase_Element( root, 450 );
    print_Linked_L(root);   
    root = erase_Element( root, 50 );
    print_Linked_L(root);   

    return 0;
}

Выход программы:

4 -> 40 -> 50 -> 400 -> 450 -> null
Number 45 does not exist in the list.
4 -> 40 -> 50 -> 400 -> 450 -> null
4 -> 40 -> 50 -> 450 -> null
4 -> 50 -> 450 -> null
50 -> 450 -> null
50 -> null
null