C Implementierung einer verknüpften Liste Element entfernen Funktion

Question

Ich habe ein Lehrbuch gelesen und stieß auf die folgende Funktion, um ein Element aus einer verknüpften Liste zu entfernen. Der CELL Typ ist wie folgt definiert;

typedef struct CELL CELL; 
struct CELL { 
    int element; 
    CELL* next; 
}; 

void delete(int x, CELL** pL) { 
    if ((*pL) != NULL) { 
     if (x == (*pL)->element) 
      (*pL) = (*pL)->next; 
     else 
      delete(x, &((*pL)->next)); 
    } 
} 

Angenommen, ich habe eine verknüpfte Liste mit den folgenden Elementen beginnend bei 5;

5->10->3->21->15->7

Jetzt nehme ich löschen Element 10. Meine Frage ist, was mit dem CELL geschieht 10 enthält, wenn die delete Funktion kehrt nun, dass diese CELL unreferenced ist? Nimmt es nicht noch Speicherplatz in Erinnerung?

Answer 1

Da Sie keinen Speicher in Ihrem Code freigeben, sollte er immer noch da sein. Sie heben die Verknüpfung dieses Elements von der verknüpften Liste auf.

Je nachdem, wie Sie den Speicher für diese Elemente verwalten, ist dies möglicherweise kein Problem (Speicherleck). Wenn beispielsweise jedes Element unter Verwendung von malloc zugeordnet wird und die verknüpfte Liste den einzigen Zeiger auf dieses Element hat, liegt wahrscheinlich ein Speicherverlust vor (und die Verwendung von free ist erforderlich). Wenn die Knoten jedoch auf dem Stapel zugeordnet sind (z. B. unter Verwendung von alloca) oder in einem Speicherpool, der später freigegeben wird, ist möglicherweise kein Leck vorhanden. Es kommt also wirklich darauf an, wie Sie mit dem Speicher umgehen und wann Sie ihn freigeben.

Answer 2

was passiert mit dem CELL 10 enthält, wenn die Löschfunktion kehrt nun, dass diese CELL unreferenced ist? Nimmt es nicht noch Speicherplatz in Erinnerung?

Absolut! Sobald die Funktion zurückkehrt, wird die CELL, die 10 enthält, zu einem Speicherverlust, es sei denn, es gibt einen anderen Zeiger, der darauf verweist, oder die CELL ist nicht dynamisch zugewiesen.

Wenn andere Funktionen für die Liste zu manipulieren (Erstellen, Einfügen, etc.) sind so ausgebildet, dass sie die Liste auf das Eigentum ihrer Zellen übernehmen, fügen Sie einen Aufruf an free in der Branche, die wieder Punkte *pl-(*pL)->next. Erstellen Sie eine temporäre Variable, speichern Sie die Adresse *pl darin, führen Sie die Neuausrichtung durch, und rufen Sie free auf dem temporären.

Answer 3

Für den Anfang einige Bemerkungen über die Funktion selbst. Es wäre besser, die Funktion folgendermaßen zu deklarieren:

int delete(CELL **pL, int x); 

Tatsächlich macht die Funktion zwei Dinge. Es durchsucht einen Knoten mit dem Wert x. Und wenn ein solcher Knoten gefunden wird, wird die Verknüpfung aufgehoben.

Es ist also wünschenswert, dass die Funktion meldet, ob ein solcher Knoten gefunden wird.

Eine weitere Möglichkeit, die Funktion für den Fall zu erklären, wenn die Funktion nicht der entfernte Knoten frei von @IanAbbott in einem Kommentar darauf ist

CELL * delete(CELL **pL, int x); 

, dass die Funktion an den entfernten Knoten zurückgibt Zeiger ist oder NULL, wenn ein solcher Knoten mit dem Wert x nicht gefunden wird.

Zweitens ist es besser, den ersten Parameter als Referenz auf den Knoten und den zweiten Parameter als gesuchten Wert zu deklarieren. Das ist zuerst, was Sie zu tun haben und wie Sie mit der Liste umgehen.

Wie für Ihre Frage, dann die Funktion, wie ich schon sagte, die Verknüpfung eines Knotens. Der Knoten selbst wird nicht aus dem Speicher entfernt und nicht geändert. Wenn es dynamisch zugewiesen wurde, müssen Sie eine Kopie des Zeigers behalten, der auf den Knoten zeigt. Andernfalls tritt ein Speicherverlust auf, weil Sie ihn nicht ohne einen Zeiger auf den Knoten freigeben können.