Verwenden von Zeigern zum Entfernen von Elementen aus einfach verknüpften Listen
Lesezeit: 11 Minuten
Codebox
In einer kürzlichen Slashdot-Interview Linus Torvalds gab ein Beispiel dafür, wie einige Leute Zeiger auf eine Weise verwenden, die darauf hindeutet, dass sie nicht wirklich verstehen, wie man sie richtig verwendet.
Da ich einer der Leute bin, von denen er spricht, habe ich leider auch sein Beispiel nicht verstanden:
Ich habe zu viele Leute gesehen, die einen einfach verknüpften Listeneintrag löschen, indem sie den “vorherigen” Eintrag verfolgen und dann den Eintrag löschen, indem sie so etwas tun
if (prev)
prev->next = entry->next;
else
list_head = entry->next;
und immer wenn ich solchen Code sehe, gehe ich einfach “Diese Person versteht keine Zeiger”. Und es ist leider ziemlich häufig. Leute, die Zeiger verstehen, verwenden einfach einen “Zeiger auf den Eintragszeiger” und initialisieren diesen mit der Adresse von list_head. Und wenn sie dann die Liste durchlaufen, können sie den Eintrag ohne Bedingung entfernen, indem sie es einfach tun
*pp = entry->next
Kann jemand etwas mehr erklären, warum dieser Ansatz besser ist und wie er ohne eine bedingte Anweisung funktionieren kann?
Es scheint, dass “Diese Person versteht keine Zeiger” für Linus “Diese Person schreibt keinen Code wie ich” bedeutet …
– Andrey Vihrov
16. Oktober 2012 um 14:32 Uhr
glglgl
Am Anfang schon
pp = &list_head;
und während Sie die Liste durchlaufen, rücken Sie diesen “Cursor” mit vor
pp = &(*pp)->next;
So behalten Sie immer den Überblick, wo „Sie herkommen“ und können den dort lebenden Pointer verändern.
Wenn Sie also den zu löschenden Eintrag finden, können Sie dies einfach tun
*pp = entry->next
Auf diese Weise kümmern Sie sich um alle 3 Fälle Afaq Erwähnungen in einer anderen Antwort, wodurch die effektiv beseitigt werden NULL prüfen Auf prev.
Wird das &* hier wirklich benötigt? wirkt etwas überflüssig.
– fuz
16. Oktober 2012 um 14:05 Uhr
@FUZxxl Es wird benötigt, als pp ist ein Zeiger auf einen Knotenzeiger. Also müssen wir es zuerst dereferenzieren und dann auf die zugreifen next auf die übliche Weise, und nehmen Sie dann seine Adresse erneut.
– glglgl
16. Oktober 2012 um 14:42 Uhr
Falls Sie den Endknoten der Liste entfernen und die verfolgen müssen tail wie Sie es mit diesem tun werden pp?
– hasnobrains
15. Oktober 2015 um 8:16 Uhr
@glglgl, ist das nicht (* pp)-> als nächstes genug, um die Adresse zu erhalten, die in pp gespeichert werden soll, warum &?
– Amit Singh Tomar
26. Mai 2016 um 7:19 Uhr
@ZianLai Nein. Du willst pp irgendwo anders zeigen, nicht die Daten wo ändern pp verweist auf.
– glglgl
22. August 2017 um 12:07 Uhr
patryk.beza
Wenn Sie gerne anhand von Beispielen lernen, habe ich eines vorbereitet. Nehmen wir an, wir haben die folgende einfach verkettete Liste:
das wird wie folgt dargestellt (zum Vergrößern anklicken):
Wir wollen den Knoten mit dem löschen value = 8.
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 = 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
Erläuterung des Codes
Lassen Sie uns erstellen **p ‘doppelter’ Zeiger auf *head Zeiger:
Lassen Sie uns nun analysieren, wie void remove_from_list(int val, node_t **head) funktioniert. Es iteriert über die Liste, auf die gezeigt wird head so lange wie *p && (**p).value != val.
In diesem Beispiel enthält die angegebene Liste value die wir löschen wollen (also 8). Nach der zweiten Iteration der while (*p && (**p).value != val) Schleife (**p).value wird 8also hören wir auf zu iterieren.
Beachten Sie, dass *p zeigt auf die Variable node_t *next innerhalb node_t das ist Vor das node_t die wir löschen wollen (also **p). Dies ist entscheidend, weil es uns erlaubt, das zu ändern *next Zeiger der node_t das steht davor node_t das wir löschen möchten, wodurch es effektiv aus der Liste entfernt wird.
Lassen Sie uns nun die Adresse des Elements zuweisen, das wir entfernen möchten (del->value == 8) zum *del Zeiger.
Wir müssen das reparieren *p Zeiger damit **p zeigte auf das eine Element nach*del Element, das wir löschen werden:
Im obigen Code rufen wir auf free(del)daher ist eine Einstellung nicht erforderlich del->next zu NULLaber wenn wir den Zeiger auf das Element ‘getrennt’ aus der Liste zurückgeben möchten, anstatt es vollständig zu entfernen, würden wir setzen del->next = NULL:
Interessanter ist es, 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 muss keine Neuverknüpfung von Knoten durchgeführt werden, da der erste Knoten keinen vorangehenden Knoten hat. Entfernen Sie beispielsweise einen Knoten mit einem:
link
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
Allerdings müssen wir den Zeiger auf den Anfang der Liste fixieren:
link
|
+-------------+
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
Aus der Mitte entfernen
Das Entfernen eines Knotens aus der Mitte erfordert, dass der vorhergehende Knoten den zu entfernenden Knoten überspringt. Entfernen Sie beispielsweise den Knoten mit b:
link
|
v
--------- --------- ---------
| a | --+--+ | b | --+---> | c | 0 |
--------- | --------- ---------
| ^
+----------------+
Das bedeutet, dass wir eine Möglichkeit brauchen, 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 vorhergehende Knoten das neue Ende der Liste wird (dh auf nichts danach zeigt). 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 das sagen “Der Knoten, der dem zu entfernenden vorangeht, muss dorthin zeigen, wo der zu entfernende ist.”
ZillGate
Im ersten Ansatz löscht man einen Knoten per Verknüpfung aufheben es aus der Liste.
Im zweiten Ansatz, Sie ersetzen den zu löschenden Knoten mit dem nächsten Knoten.
Anscheinend vereinfacht der zweite Ansatz den Code auf elegante Weise. Der zweite Ansatz erfordert definitiv ein besseres Verständnis der verknüpften Liste und des zugrunde liegenden Berechnungsmodells.
Auf diese Weise müssen Sie nicht prüfen, ob es sich um das erste Element handelt, da das erste Element immer Dummy ist und niemals gelöscht wird.
Ist curr->next-next ein Tippfehler?
– Max Heiber
29. November 2016 um 4:58 Uhr
@MaxHeiber Es scheint so. Ich habe den Tippfehler korrigiert.
– Pavan Manjunath
11. Oktober 2020 um 18:49 Uhr
mg979
Hier ist meine Meinung, ich fand es auf diese Weise einfacher zu verstehen.
Beispiel für das Löschen eines Knotens in einer verknüpften Liste unter Verwendung von Zeigern auf Zeiger.
struct node {
int value;
struct node *next;
};
void delete_from_list(struct node **list, int n)
{
struct node *entry = *list;
while (entry && entry->value != n) {
// store the address of current->next value (1)
list = &entry->next;
// list now stores the address of previous->next value
entry = entry->next;
}
if (entry) {
// here we change the previous->next value
*list = entry->next;
free(entry);
}
}
Angenommen, wir erstellen eine Liste mit diesen Werten:
*node value next
----------------------------------------
a 1 null
b 2 a
c 3 b
d 4 c
e 5 d
Wenn wir den Knoten mit dem Wert 3 löschen wollen:
entry = e
while (entry && entry->value != 3) iterations:
e->value != 3
list = &e->next
entry = d
d->value != 3
list = &d->next
entry = c
c->value == 3
STOP
if (entry)
d->next = b (what was 'list' is dereferenced)
free(entry)
Nach if (entry) wir haben:
d->next = b
Die Liste wird also:
*node value next
----------------------------------------
a 1 null
b 2 a
c 3 b
d 4 b
e 5 d
Und schlussendlich:
free(entry)
Und die Liste wird:
*node value next
----------------------------------------
a 1 null
b 2 a
d 4 b
e 5 d
Wenn wir den ersten Knoten löschen wollen, wird es trotzdem funktionieren, denn initial
*list == entry
daher mit:
*list = entry->next;
*list zeigt auf das zweite Element.
(1) Beachten Sie das Sprichwort:
list = &entry->next;
Ist dasselbe wie zu sagen:
list = &(entry->next);
Ist curr->next-next ein Tippfehler?
– Max Heiber
29. November 2016 um 4:58 Uhr
@MaxHeiber Es scheint so. Ich habe den Tippfehler korrigiert.
– Pavan Manjunath
11. Oktober 2020 um 18:49 Uhr
Sigisaft
Hier ist ein vollständiges Codebeispiel, das einen Funktionsaufruf verwendet, um übereinstimmende Elemente zu entfernen:
rem() Entfernt übereinstimmende Elemente unter Verwendung von 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 = 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;
}
Beim Kompilieren und Verwenden von valgrind (ein Speicherleckprüfer) wie folgt: gcc -std=c11 -Wall -Wextra -Werror -o go code.c && valgrind ./go
Wir sehen, dass alles gut ist.
Perfekte Umsetzung von void rem2(list_entry **pp, int match_val) es spricht Linus Torvalds Bedenken an, dass viele Entwickler Zeiger nicht gut verstehen, insbesondere die Feinheiten von Zeigern auf Zeiger. Er verwendet es als Beispiel dafür, dass viele nicht wissen, wie mehrere Elemente einer Verknüpfung mit nur einer Bedingung mit zwei Verzweigungen gelöscht werden, da dies die Verwendung eines Zeigers auf einen Zeiger erfordert.
– Abetancort
25. September 2020 um 12:17 Uhr
14145000cookie-checkVerwenden von Zeigern zum Entfernen von Elementen aus einfach verknüpften Listenyes
Es scheint, dass “Diese Person versteht keine Zeiger” für Linus “Diese Person schreibt keinen Code wie ich” bedeutet …
– Andrey Vihrov
16. Oktober 2012 um 14:32 Uhr