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?
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.
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."
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:
das wird wie folgt dargestellt (klicken zum vergrößern):
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:
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.
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.
Wir müssen den *p-Zeiger so korrigieren, dass **p auf das Element after*del-Element zeigte, das wir löschen möchten:
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:
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/
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.
@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
Hier ist ein komplettes Codebeispiel, bei dem mit einem Funktionsaufruf übereinstimmende Elemente entfernt werden:
rem()entfernt übereinstimmende Elemente mit prevrem2()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:
- gcc https://wandbox.org/permlink/LxgMddqCZWyj7lMI
- clang https://wandbox.org/permlink/5aEkxh24sGfAecwF
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.