webentwicklung-frage-antwort-db.com.de

Verwenden von Zeigern, um ein Element aus der einzeln verknüpften Liste zu entfernen

In einem aktuellen Slashdot-Interview gab Linus Torvalds ein Beispiel, wie manche Leute Zeiger verwenden, die darauf schließen lassen, dass sie nicht wirklich verstehen, wie man sie richtig verwendet. 

Da ich einer der Leute bin, über die er spricht, habe ich sein Beispiel leider nicht verstanden:

Ich habe zu viele Leute gesehen, die einen einfach verknüpften Listeneintrag löschen, indem Sie den Eintrag "prev" verfolgen und dann den Eintrag löschen, indem Sie so etwas wie

if (prev)
    prev->next = entry->next;
else
    list_head = entry->next;

und immer wenn ich so Code sehe, gehe ich einfach "Diese Person versteht nicht Zeiger verstehen". Und das ist leider ziemlich üblich. Leute die Für Zeiger verwenden Sie einfach einen "Zeiger auf den Eingabezeiger" und initialisieren Sie das mit der Adresse des list_head. Und dann wie sie Wenn Sie die Liste durchlaufen, können Sie den Eintrag entfernen, ohne ein beliebiges .__ zu verwenden. Bedingungen, indem Sie einfach

*pp = entry->next

Kann jemand etwas mehr erklären, warum dieser Ansatz besser ist und wie er ohne bedingte Anweisung funktionieren kann?

44
codebox

Am Anfang machst du das

pp = &list_head;

und, während Sie die Liste durchlaufen, bewegen Sie diesen "Cursor" mit

pp = &(*pp)->next;

Auf diese Weise behalten Sie immer den Punkt im Auge, von dem "Sie kommen" und können den dort lebenden Zeiger ändern.

Wenn Sie also herausfinden, dass der Eintrag gelöscht werden soll, können Sie dies einfach tun

*pp = entry->next

Auf diese Weise erledigen Sie alle 3 Fälle Afaq in einer anderen Antwort und eliminieren so effektiv die NULL-Prüfung auf prev.

32
glglgl

Es ist interessanter, die Liste erneut zu verbinden, sobald ein Knoten entfernt werden soll. Betrachten wir mindestens 3 Fälle:

1.Entfernen eines Knotens von Anfang an.

2.Entfernen eines Knotens aus der Mitte.

3.Entfernen eines Knotens vom Ende. 

Entfernen von Anfang an

Beim Entfernen des Knotens am Anfang der Liste müssen keine Knoten neu verknüpft werden, da der erste Knoten keinen vorhergehenden Knoten hat. Beispiel: Entfernen des Knotens mit einem:

link
 |
 v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------

Wir müssen jedoch den Zeiger an den Anfang der Liste setzen:

link
 |
 +-------------+
               |
               v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------

Entfernen aus der Mitte

Um einen Knoten aus der Mitte zu entfernen, muss der vorherige Knoten den zu entfernenden Knoten überspringen. Zum Beispiel den Knoten mit b entfernen:

link
 |
 v
---------     ---------     ---------
| a | --+--+  | b | --+---> | c | 0 |
---------  |  ---------     ---------
           |                ^
           +----------------+

Dies bedeutet, dass wir einen Weg benötigen, um auf den Knoten vor dem Knoten zu verweisen, den wir entfernen möchten.

Entfernen vom Ende

Das Entfernen eines Knotens vom Ende erfordert, dass der vorherige Knoten das neue Ende der Liste wird (d. H. Auf nichts danach zeigt). So entfernen Sie beispielsweise den Knoten mit c:

link
 |
 v
---------     ---------     ---------
| a | --+---> | b | 0 |     | c | 0 |
---------     ---------     ---------

Beachten Sie, dass die letzten beiden Fälle (Mitte und Ende) kombiniert werden können, indem Sie sagen, dass "der Knoten, der dem zu entfernenden Knoten vorangeht, zeigen muss, wohin der zu entfernende Fall geht." 

11
Afaq

Erklärung per Video

Dieses Problem wurde von Philip Buuck in diesem YouTube-Video diskutiert. Ich empfehle Ihnen, dies zu beachten, wenn Sie eine ausführlichere Erklärung benötigen.


Erklärung von Beispiel

Wenn Sie gerne von Beispielen lernen, habe ich eines vorbereitet. Nehmen wir an, wir haben die folgende einfach verknüpfte Liste:

 Singly-linked list example

das wird wie folgt dargestellt (klicken zum vergrößern):

 Singly-linked list representation

Wir möchten den Knoten mit dem value = 8 löschen.

Code

Hier ist der einfache Code, der dies tut:

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

struct node_t {
    int value;
    node_t *next;
};

node_t* create_list() {
    int test_values[] = { 28, 1, 8, 70, 56 };
    node_t *new_node, *head = NULL;
    int i;

    for (i = 0; i < 5; i++) {
        new_node = (node_t*)malloc(sizeof(struct node_t));
        assert(new_node);
        new_node->value = test_values[i];
        new_node->next = head;
        head = new_node;
    }

    return head;
}

void print_list(const node_t *head) {
    for (; head; head = head->next)
        printf("%d ", head->value);
    printf("\n");
}

void destroy_list(node_t **head) {
    node_t *next;

    while (*head) {
        next = (*head)->next;
        free(*head);
        *head = next;
    }
}

void remove_from_list(int val, node_t **head) {
    node_t *del, **p = head;

    while (*p && (**p).value != val)
        p = &(*p)->next;  // alternatively: p = &(**p).next

    if (p) {  // non-empty list and value was found
        del = *p;
        *p = del->next;
        del->next = NULL;  // not necessary in this case
        free(del);
    }
}

int main(int argc, char **argv) {
    node_t *head;

    head = create_list();
    print_list(head);

    remove_from_list(8, &head);
    print_list(head);

    destroy_list(&head);
    assert (head == NULL);

    return EXIT_SUCCESS;
}

Wenn Sie diesen Code kompilieren und ausführen, erhalten Sie Folgendes:

56 70 8 1 28 
56 70 1 28

Erklärung des Codes

Erstellen wir **p 'double' auf *head:

 Singly-linked list example #2

Lassen Sie uns nun analysieren, wie void remove_from_list(int val, node_t **head) funktioniert. Es durchläuft die Liste, auf die head zeigt, solange *p && (**p).value != val.

 Singly-linked list example #3

 Singly-linked list example #4

In diesem Beispiel enthält die Liste value, die gelöscht werden soll (8). Nach der zweiten Iteration der while (*p && (**p).value != val)-Schleife (**p).value wird 8, und wir hören auf zu iterieren.

Beachten Sie, dass *p auf die Variable node_t *next in node_t zeigt, die vor dem node_t ist, den Sie löschen möchten (was **p ist). Dies ist wichtig, da wir damit den *next-Zeiger des node_t vor dem node_t ändern können, den wir löschen möchten, und ihn effektiv aus der Liste entfernen.

Nun weisen wir die Adresse des Elements, das wir entfernen möchten (del->value == 8), dem *del-Zeiger zu.

 Singly-linked list example #5

Wir müssen den *p-Zeiger so korrigieren, dass **p auf das Element after*del-Element zeigte, das wir löschen möchten:

 Singly-linked list example #6

Im obigen Code rufen wir free(del) auf. Daher ist es nicht notwendig, del->next auf NULL zu setzen. Wenn wir jedoch den Zeiger auf das Element 'detached' aus der Liste zurückgeben möchten, anstatt ihn vollständig zu entfernen, würden wir del->next = NULL setzen:

 Singly-linked list example #7

8
patryk.beza

Im ersten Ansatz löschen Sie einen Knoten, indem Sie Verknüpfung aufheben ihn aus der Liste entfernen.

Im zweiten Ansatz Ersetzen wird der zu löschende Knoten durch den nächsten Knoten ersetzt.

Offensichtlich vereinfacht der zweite Ansatz den Code auf elegante Weise. Auf jeden Fall erfordert der zweite Ansatz ein besseres Verständnis der verknüpften Liste und des zugrunde liegenden Berechnungsmodells.

Hinweis: Hier ist eine sehr relevante, aber etwas andere Kodierungsfrage. Gut zum Testen des eigenen Verständnisses: https://leetcode.com/problems/delete-node-in-a-linked-list/

5
ZillGate

Ich bevorzuge den Dummy-Knoten-Ansatz, ein Beispiellayout:

|Dummy|->|node1|->|node2|->|node3|->|node4|->|node5|->NULL
                     ^        ^
                     |        |
                    curr   curr->next // << toDel

und dann fahren Sie zu dem Knoten, den Sie löschen möchten (toDel = curr> next)

tmp = curr->next;
curr->next = curr->next-next;
free(tmp);

Auf diese Weise müssen Sie nicht prüfen, ob es das erste Element ist, da das erste Element immer Dummy ist und niemals gelöscht wird.

2
Xee

@glglgl:

Ich schrieb folgendes einfaches Beispiel. Ich hoffe, Sie können sehen, warum es funktioniert.
In Funktion void delete_node(LinkedList *list, void *data) verwende ich *pp = (*pp)->next; und es funktioniert. Ehrlich gesagt verstehe ich nicht, warum es funktioniert. Ich zeichne sogar das Zeigerdiagramm, verstehe es aber immer noch nicht. Hoffe du kannst es klären.

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

typedef struct _employee {
    char name[32];
    unsigned char age;
} Employee;

int compare_employee(Employee *e1, Employee *e2)
{
    return strcmp(e1->name, e2->name);
}
typedef int (*COMPARE)(void *, void *);

void display_employee(Employee *e)
{
    printf("%s\t%d\n", e->name, e->age);
}
typedef void (*DISPLAY)(void *);

typedef struct _node {
    void *data;
    struct _node *next;
} NODE;

typedef struct _linkedlist {
    NODE *head;
    NODE *tail;
    NODE *current;
} LinkedList;

void init_list(LinkedList *list)
{
    list->head = NULL;
    list->tail = NULL;
    list->current = NULL;
}

void add_head(LinkedList *list, void *data)
{
    NODE *node = (NODE *) malloc(sizeof(NODE));
    node->data = data;
    if (list->head == NULL) {
        list->tail = node;
        node->next = NULL;
    } else {
        node->next = list->head;
    }
    list->head = node;
}

void add_tail(LinkedList *list, void *data)
{
    NODE *node = (NODE *) malloc(sizeof(NODE));
    node->data = data;
    node->next = NULL;
    if (list->head == NULL) {
        list->head = node;
    } else {
        list->tail->next = node;
    }
    list->tail = node;
}

NODE *get_node(LinkedList *list, COMPARE compare, void *data)
{
    NODE *n = list->head;
    while (n != NULL) {
        if (compare(n->data, data) == 0) {
            return n;
        }
        n = n->next;
    }
    return NULL;
}

void display_list(LinkedList *list, DISPLAY display)
{
    printf("Linked List\n");
    NODE *current = list->head;
    while (current != NULL) {
        display(current->data);
        current = current->next;
    }
}

void delete_node(LinkedList *list, void *data)
{
    /* Linus says who use this block of code doesn't understand pointer.    
    NODE *prev = NULL;
    NODE *walk = list->head;

    while (((Employee *)walk->data)->age != ((Employee *)data)->age) {
        prev = walk;
        walk = walk->next;
    }

    if (!prev)
        list->head = walk->next;
    else
        prev->next = walk->next; */

    NODE **pp = &list->head;

    while (((Employee *)(*pp)->data)->age != ((Employee *)data)->age) {
        pp = &(*pp)->next;
    }

    *pp = (*pp)->next;
}

int main () 
{
    LinkedList list;

    init_list(&list);

    Employee *samuel = (Employee *) malloc(sizeof(Employee));
    strcpy(samuel->name, "Samuel");
    samuel->age = 23;

    Employee *sally = (Employee *) malloc(sizeof(Employee));
    strcpy(sally->name, "Sally");
    sally->age = 19;

    Employee *susan = (Employee *) malloc(sizeof(Employee));
    strcpy(susan->name, "Susan");
    susan->age = 14;

    Employee *jessie = (Employee *) malloc(sizeof(Employee));
    strcpy(jessie->name, "Jessie");
    jessie->age = 18;

    add_head(&list, samuel);
    add_head(&list, sally);
    add_head(&list, susan);

    add_tail(&list, jessie);

    display_list(&list, (DISPLAY) display_employee);

    NODE *n = get_node(&list, (COMPARE) compare_employee, sally);
    printf("name is %s, age is %d.\n",
            ((Employee *)n->data)->name, ((Employee *)n->data)->age);
    printf("\n");

    delete_node(&list, samuel);
    display_list(&list, (DISPLAY) display_employee);

    return 0;
}

ausgabe:

Linked List
Susan   14
Sally   19
Samuel  23
Jessie  18
name is Sally, age is 19.

Linked List
Susan   14
Sally   19
Jessie  18
1
Lion Lai

Hier ist ein komplettes Codebeispiel, bei dem mit einem Funktionsaufruf übereinstimmende Elemente entfernt werden:

  • rem() entfernt übereinstimmende Elemente mit prev

  • rem2() entfernt übereinstimmende Elemente mit Zeiger-zu-Zeiger

// code.c

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


typedef struct list_entry {
    int val;
    struct list_entry *next;
} list_entry;


list_entry *new_node(list_entry *curr, int val)
{
    list_entry *new_n = (list_entry *) malloc(sizeof(list_entry));
    if (new_n == NULL) {
        fputs("Error in malloc\n", stderr);
        exit(1);
    }
    new_n->val  = val;
    new_n->next = NULL;

    if (curr) {
        curr->next = new_n;
    }
    return new_n;
}


#define ARR_LEN(arr) (sizeof(arr)/sizeof((arr)[0]))

#define     CREATE_LIST(arr) create_list((arr), ARR_LEN(arr))

list_entry *create_list(const int arr[], size_t len)
{
    if (len == 0) {
        return NULL;
    }

    list_entry *node = NULL;
    list_entry *head = node = new_node(node, arr[0]);
    for (size_t i = 1; i < len; ++i) {
        node = new_node(node, arr[i]);
    }
    return head;
}


void rem(list_entry **head_p, int match_val)
// remove and free all entries with match_val
{
    list_entry *prev = NULL;
    for (list_entry *entry = *head_p; entry; ) {
        if (entry->val == match_val) {
            list_entry *del_entry = entry;
            entry = entry->next;
            if (prev) {
                prev->next = entry;
            } else {
                *head_p    = entry;
            }
            free(del_entry);
        } else {
            prev = entry;
            entry = entry->next;
        }
    }
}


void rem2(list_entry **pp, int match_val)
// remove and free all entries with match_val
{
    list_entry *entry;
    while ((entry = *pp)) { // assignment, not equality
        if (entry->val == match_val) {
            *pp =   entry->next;
            free(entry);
        } else {
            pp  =  &entry->next;
        }
    }
}


void print_and_free_list(list_entry *entry)
{
    list_entry *node;
    // iterate through, printing entries, and then freeing them
    for (;     entry != NULL;      node = entry, /* lag behind to free */
                                   entry = entry->next,
                                   free(node))           {
        printf("%d ", entry->val);
    }
    putchar('\n');
}


#define CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val) createList_removeMatchElems_print((arr), ARR_LEN(arr), (match_val))

void    createList_removeMatchElems_print(const int arr[], size_t len, int match_val)
{
    list_entry *head = create_list(arr, len);
    rem2(&head, match_val);
    print_and_free_list(head);
}


int main()
{
    const int match_val = 2; // the value to remove
    {
        const int arr[] = {0, 1, 2, 3};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {0, 2, 2, 3};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {2, 7, 8, 2};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {2, 2, 3, 3};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {0, 0, 2, 2};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {2, 2, 2, 2};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }

    return 0;
}

Sehen Sie den Code hier in Aktion:

Wenn Sie valgrind (einen Speicherleck-Checker) wie folgt kompilieren und verwenden:
gcc -std=c11 -Wall -Wextra -Werror -o go code.c && valgrind ./go
Wir sehen, dass alles gut ist.

0
ajneu