webentwicklung-frage-antwort-db.com.de

Löschen eines Knotens aus einer einzelnen verknüpften Liste, wenn nur ein Zeiger auf diesen Knoten angegeben ist

Dies ist eine Frage, die mir in einem Interview gestellt wurde.

"Eine einzelne verknüpfte Liste befindet sich im Speicher. Sie müssen einen Knoten löschen. Sie müssen eine Funktion zum Löschen dieses Knotens schreiben, die nur die Adresse des zu löschenden Knotens als Eingabe und nichts anderes (einschließlich Kopf) verwendet."

Ich habe die Antwort ähnlich der im folgenden Beitrag beantworteten gegeben - Kopieren des Inhalts des nächsten Knotens in den zu löschenden Knoten und Löschen des nächsten Knotens.

Löschen eines mittleren Knotens aus einer einzelnen verknüpften Liste, wenn der Zeiger auf den vorherigen Knoten nicht verfügbar ist

Aber der Interviewer fragte mich noch einmal, was passiert, wenn ich die Adresse des letzten Knotens übergebe. Ich sagte ihm, da die nächste NULL sein wird, kopiere diese NULL zusammen mit der Adresse zum nächsten Knoten, der ebenfalls NULL ist, in das Datenfeld. Dann sagte er mir, dass es ein Problem mit baumelnden Zeigern geben würde ... das ich nicht ein bisschen verstand. Kann jemand bitte Licht in dieses Problem werfen? Gibt es eine generische Lösung dafür?

Update (zwei Tage später): Ein bisschen mehr. Berücksichtigt man, dass am Ende der Liste kein spezieller Knoten steht. Und der letzte Knoten zeigt auf NULL, und wenn dieser Knoten als Eingabe angegeben wird, wie der vorletzte Knoten auf NULL gesetzt wird. Oder ist es unmöglich?

Einfach ausgedrückt: Wenn ein Knoten als Eingabe für eine Funktion angegeben wird, zeigt der Zeiger, der auf ihn verweist, auf NULL

11
King

Schlenkerzeiger:

(http://en.wikipedia.org/wiki/Dangling_reference)

Dangling Pointer und Wild Pointer in der Computerprogrammierung sind Zeiger, die nicht auf ein gültiges Objekt des entsprechenden Typs verweisen. Dies sind spezielle Fälle von Verstößen gegen die Speichersicherheit.

Baumelnde Zeiger entstehen, wenn ein Objekt gelöscht oder freigegeben wird, ohne den Wert des Zeigers zu ändern, so dass der Zeiger weiterhin auf den Speicherort des freigegebenen Speichers zeigt. Da das System möglicherweise den zuvor freigegebenen Speicher einem anderen Prozess zuweist, kann es zu unvorhersehbarem Verhalten kommen, wenn das ursprüngliche Programm den (jetzt) ​​baumelnden Zeiger dereferenziert, da der Speicher jetzt möglicherweise völlig andere Daten enthält.

Um den angegebenen Knoten zu löschen, löschen Sie in Ihrer Antwort den next -Knoten, auf den möglicherweise ein Zeiger verweist. So entsteht das Problem des baumelnden Zeigers.

(1) Es gibt keine externen Verweise auf die Liste, wie Sie in einem Hinweis erläutern. (2) Ein baumelndes Zeigerproblem kann auftreten, wie der Interviewer sagte.

Sowohl (1) als auch (2) können nicht gleichzeitig korrekt sein. Was bedeutet, dass es irgendwo ein Missverständnis gibt.

Informationen zum Löschen des letzten Knotens:

Aber der Interviewer fragte mich noch einmal, was passiert, wenn ich die Adresse des letzten Knotens übergebe. Ich sagte ihm, da die nächste NULL sein wird, kopiere diese NULL zusammen mit der Adresse zum nächsten Knoten, der ebenfalls NULL ist, in das Datenfeld.

Ich denke, Sie verwechseln diese beiden Dinge: (1) Ein Zeiger p, der auf NULL zeigt, (2) Ein verknüpfter Listenknoten, dessen Datenfeld NULL enthält.

Angenommen, die Datenstruktur lautet a -> b -> c -> d. Das Schreiben von NULL in das Datenfeld von d bewirkt nicht, dass c einen NULL-Zeiger in seinem Feld next hat.

Sie können den letzten Knoten löschen wenn die verknüpfte Liste immer einen speziellen letzten Knoten hat der niemals gelöscht wird. Beispiel: a -> b -> c -> d -> LAST, wobei LAST in seinem Datenfeld einen speziellen Wert hat, der angibt, dass es sich wirklich um das letzte Element handelt. Um nun d zu löschen, können Sie LAST löschen und den speziellen Wert in das Datenfeld von d schreiben.

Vielleicht haben Sie genau das versucht, während des Interviews zu erzählen. In diesem Fall muss ein Missverständnis zwischen Ihnen und dem Interviewer aufgetreten sein.

9
Ali Ferhat

Schritte:

  1. Daten vom Knoten (i + 1) zum Knoten (i) kopieren
  2. Kopieren Sie das NÄCHSTE des zweiten Knotens (i + 1) in eine temporäre Variable.
  3. Löschen Sie nun den zweiten Knoten (i + 1) // es wird kein Zeiger auf den vorherigen Knoten benötigt.

Funktion:

void delete_node(node* node)
{
    node->Data = node->Next->Data;
    node* temp = node->Next->Next;
    delete(node->Next);
    node->Next = temp;
}
13
Saket Vatsa

dann sollte im Programm überprüft werden, ob der angegebene Knoten der letzte Knoten ist oder nicht.

void delete_node(node* node1)
{
    node* search=head;
    if(node1==head)
    {
        head=head->next;
        search->next=NULL;
        node1->next=NULL;
    }
    while(search->next != node1)
        search=search->next;
    if(node1->next==NULL)
    {
       search->next=NULL;
    }
    else
    {
       search->next=node1->next;
       node1->next=NULL;
    }
    delete node1;
}
3

Wenn andere Elemente auf den nächsten Knoten verweisen, der auf den aktuellen Knoten kopiert und anschließend gelöscht wird, führt diese Operation zu einem Fehler. In Ihrer Antwort hätten Sie also betonen müssen, dass Ihre Lösung nur funktioniert, wenn es keine externen Verweise auf die Liste gibt.

Ihre Lösung funktioniert nur mit dem letzten Knoten, wenn die Datenstruktur um ein bestimmtes "letzter Knoten" -Element erweitert ist. (Wenn Sie Smalltalk verwenden, können Sie self become: nil schreiben. Keine andere Sprache hat etwas Ähnliches.)

Nein, es gibt keine generische Lösung, wenn Verweise von außen auf die Liste vorhanden sind. Ich glaube, der Interviewer wollte sehen, ob Sie sich wirklich mit dem Thema auskennen oder nur eine auswendig gelernte Antwort wiederholen.

2
Ali Ferhat

Wahrscheinlich muss bei der Überquerung der Linkliste davon ausgegangen werden, dass jeder Knoten, der auf null zeigt, ein null-Knoten ist, unabhängig vom Wert ...

a->b->c->d->NULL

d ist also null node und der node sollte nicht als node betrachtet werden. Auf diese Weise können Sie die Verwendung von Sonderwerten einsparen, da diese im allgemeinen Sinne nicht korrekt sind. Ansonsten gibt es für den vorherigen Knoten keine andere Möglichkeit, auf null zu verweisen.

1
nitsi
 public void removeNode(Node node){

        /* if no node return null */
        if(node==null) return;

        /* if only 1 node then delete node */
        if(node.getNext()==null) {
            node = null;
            return ;
        }

        /* copy next node data to this node */
        node.data = node.getNext().data();

        /* store the next next node */
        Node second = node.getNext().getNext();

        /* remove next node */
        removeNode(node.getNext());

        /* set the copied node as next */
        node.setNext(second);
     }
0
sreeprasad