Удалить узел - связанный список - C

Question

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

Я видел этот вопрос удаление узла в середине связанного списка , и я не 'Не знаю, чем моя функция удаления узла отличается от ответа.

Вот мой код:

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

typedef unsigned char u8;
typedef struct Node node;
void addfirstnode( u8 );
void addnode( u8 );
void print( void );
void deletenode( u8 key );
void deleteonlynode();
void deletefirstnode();

struct Node
{
    u8 x;
    node *next;
};
node *head;
u8 length = 0;


void main( void )
{
    u8 x;
    printf( "\nTo add node enter 0\nTo print linked list enter 1\nTo exit press 2\nTo delete node press 3\nYour Choice:" );
    scanf( "%d", &x );
    if ( x == 2 )
    {
        printf( "\nThank You\nGood Bye" );
    }
    while ( x != 2 )
    {
        switch ( x )
        {
            u8 n;
            u8 key;
            case 0:            //Add node
                printf( "\nPlease enter first value:" );
                scanf( "%d", &n );
                if ( length == 0 )
                {
                    addfirstnode( n );
                    //printf("%d",head->x);
                }
                else
                {
                    addnode( n );
                }
                printf( "\nNode added , Thank you\n" );
                break;

            case 1:            //Print
                print();
                break;

            case 3:            //DeleteNode
                printf( "\nPlease enter value to be deleted:" );
                scanf( "%d", &key );
                deletenode( key );
                //deletefirstnode();
                break;

            default:
                printf( "\nInvalid Choice please try again\n" );
        }
        printf( "\nTo add node enter 0\nTo print linked list enter 1\nTo exit press 2\nTo delete node press 3\nYour Choice:" );
        scanf( "%d", &x );
        if ( x == 2 )
        {
            printf( "\nThank You\nGood Bye" );
        }
    }
    //where do I use free();
}

void addfirstnode( u8 n )
{
    head = ( node * ) malloc( sizeof( node ) );
    head->next = NULL;
    head->x = n;
    length++;
}

void addnode( u8 n )
{
    node *last = head;
    while ( ( last->next ) != NULL )
    {
        last = last->next;
    }
    last->next = ( node * ) malloc( sizeof( node ) );
    ( last->next )->next = NULL;
    ( last->next )->x = n;
    length++;
}

void print( void )
{
    node *last = head;
    u8 count = 1;
    printf( "\n---------------------" );
    if ( last == NULL )
    {
        printf( "\nList is empty" );
    }
    while ( last != NULL )
    {
        printf( "\nNode Number %d = %d", count, last->x );
        last = last->next;
        count++;
    }
    printf( "\n---------------------" );
    printf( "\n" );
}

void deletenode( u8 key )
{
    node *last = head;
    //node*postlast = NULL;
    if ( ( last->x == key ) && ( last->next == NULL ) )
    {
        deleteonlynode();
    }
    else
    {
        while ( last != NULL )
        {
            if ( ( last->x ) == key )
            {
                printf( "value to be deleted is found" );
                node *temp = last->next;
                last->next = last->next->next;
                free( temp );
                length--;
            }
            last = last->next;
        }
    }
}

void deleteonlynode()
{
    printf( "\n Deleting the only node" );
    free( head );
    head = NULL;
    length--;
}

void deletefirstnode()
{
    printf( "\n Deleting the first node" );
    node *temp = head;
    head = head->next;
    free( temp );
    length--;
}

Answer 1

Ваш код, кажется, удаляет last->next, тогда как last должен быть узлом, который соответствует ключу.Я предполагаю, что следующий код может быть короче и выполнять удаление

node* head;

/* returns the node* the previous_node->next should be after the deletion */
node* delete_node(node* current, u8 key) {
    if (current == NULL) return NULL;  // deletion comes to end
    if (head->x == key) {
        node* temp = current->next;
        free(current);
        return delete_node(temp, key);
    }
    current->next = delete_node(current->next, key);
    return current;
}


int main() {
    // build the linked list
    // ...
    head = delete_node(head, key);
    return 0;
}

Однако эта реализация (которая использует рекурсию вместо цикла) может вызвать StackOverFlow, если список слишком длинный.Я не проверял, оптимизирует ли gcc рекурсию.

Answer 2

Код удаляет неправильный элемент из связанного списка:

См .:

        if ( ( last->x ) == key )
        {
            printf( "value to be deleted is found" );
            node *temp = last->next;     // last->next? No, just last.
            last->next = last->next->next;
            free( temp );
            length--;
        }

last указывает на удаляемый элемент.Но затем код назначает temp для указания на last->next (НЕ last), а затем вырезает это из списка.

Итак, глядя на node->next, а не на текущий узел, можнообрезать его, так как вы начинаете с указателя, прежде чем удалить.В основном ваш код уже был почти там.

void deletenode( u8 key )
{
    node *ptr = head;

    if ( ( ptr->x == key ) )
    {
        // Delete the first/head element
        node *temp = ptr;
        head = head->next;
        free( temp );
        length--;
    }
    else
    {
        while ( ptr->next != NULL )
        {
            if ( ( ptr->next->x ) == key )
            {
                printf( "value to be deleted is found" );
                node *temp = ptr->next;
                ptr->next = ptr->next->next;
                free( temp );
                length--;
            }
            ptr = ptr->next;
        }
    }
}

Кроме того, я позволил себе переименовать last в ptr, потому что это меня смущало.

РЕДАКТИРОВАТЬ: Обновлено, чтобы удалить головучисто тоже.