verkettete - zirkuläre liste c




Verwenden von Zeigern zum Entfernen von Elementen aus einer einfach verknüpften Liste (5)

In einem kürzlich erschienenen Slashdot-Interview gab Linus Torvalds ein Beispiel, wie manche Leute Zeiger verwenden, die darauf hindeuten, dass sie nicht wirklich verstehen, wie man sie richtig benutzt.

Leider, da ich einer der Leute bin, von denen er spricht, habe ich auch sein Beispiel 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 und so etwas tun

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

und wenn ich Code wie diesen sehe, gehe ich einfach "Diese Person versteht keine Zeiger". Und es ist leider ziemlich üblich. Leute, die Zeiger verstehen, benutzen einfach einen "Zeiger auf den Eintragszeiger" und initialisieren das mit der Adresse des list_head. Und dann, während sie die Liste durchqueren, können sie den Eintrag entfernen, ohne irgendwelche Bedingungen zu verwenden, indem sie einfach tun

*pp = entry->next

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


Erklärung per Video

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

Erklärung mit Beispiel

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

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

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

Code

Hier ist der einfache Code, der das 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:

56 70 8 1 28 
56 70 1 28

Erklärung des Codes

Lassen Sie uns einen * **p 'doppelten' Zeiger auf *head Kopfzeiger erstellen:

Lassen Sie uns nun analysieren, wie void remove_from_list(int val, node_t **head) funktioniert. Es iteriert über die von head Liste solange *p && (**p).value != val .

In diesem Beispiel enthält eine Liste den value , den wir löschen möchten ( 8 ). Nach der zweiten Iteration der while (*p && (**p).value != val) Schleife (**p).value wird 8 , also hören wir auf zu iterieren.

Beachten Sie, dass *p auf die Variable node_t *next innerhalb von node_t verweist, die vor dem node_t , das wir löschen möchten (was **p ). Dies ist entscheidend, da wir damit den *next Zeiger des node_t , der vor dem zu node_t , node_t und ihn damit effektiv aus der Liste entfernen können.

del->value == 8 wir nun die Adresse des Elements, das wir entfernen wollen ( del->value == 8 ), dem *del Zeiger zu.

Wir müssen den *p Zeiger so korrigieren, dass **p auf das eine Element nach *del Element zeigt, das wir löschen werden:

Im obigen Code nennen wir free(del) , daher ist es nicht notwendig, del->next NULL , aber wenn wir den Zeiger auf das Element "detached" von der Liste del->next möchten anstatt ihn komplett zu entfernen, wir würde del->next = NULL :


@glglgl:

Ich habe folgendes einfaches Beispiel geschrieben. Hoffe du kannst mal schauen warum es funktioniert.
In der Funktion void delete_node(LinkedList *list, void *data) ich *pp = (*pp)->next; und es funktioniert. Um ehrlich zu sein, 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

Bei der ersten Vorgehensweise löschen Sie einen Knoten, indem Sie ihn von der Liste trennen .

Im zweiten Ansatz ersetzen Sie den zu löschenden Knoten durch den nächsten Knoten.

Offensichtlich vereinfacht der zweite Ansatz den Code in eleganter Weise. Auf jeden Fall erfordert der zweite Ansatz ein besseres Verständnis der verknüpften Liste und des zugrundeliegenden Berechnungsmodells.

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


Das erneute Verbinden der Liste, sobald ein Knoten entfernt werden soll, ist interessanter. Betrachten wir mindestens 3 Fälle:

1. Einen Knoten von Anfang an entfernen.

2. Einen Knoten von der Mitte entfernen.

3.Entfernen eines Knotens vom Ende.

Von Anfang an entfernen

Wenn der Knoten am Anfang der Liste entfernt wird, wird kein erneutes Verknüpfen von Knoten durchgeführt, da der erste Knoten keinen vorhergehenden Knoten hat. Zum Beispiel, Knoten mit einem entfernen:

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

Allerdings müssen wir den Zeiger auf den Anfang der Liste fixieren:

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

Entfernen von der Mitte

Das Entfernen eines Knotens von der Mitte erfordert, dass der vorhergehende Knoten über den zu entfernenden Knoten überspringt. ZB Entfernen des Knotens mit b:

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

Das bedeutet, dass wir einen Weg brauchen, um auf den Knoten vor dem zu verweisen, den wir entfernen wollen.

Vom Ende entfernen

Das Entfernen eines Knotens vom Ende erfordert, dass der vorhergehende Knoten das neue Ende der Liste wird (dh nach diesem Punkt auf nichts zeigt). ZB Entfernen des Knotens 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 vorausgeht, auf den Punkt verweisen muss, der entfernt werden soll."


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

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

und dann durchqueren Sie den zu löschenden Knoten (toDel = curr> next)

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

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







linked-list