eine einzeln verknüpfte Liste in C ++ durchqueren

StackOverflow https://stackoverflow.com/questions/1522828

Frage

Ich frage mich, ob es möglich ist, eine verknüpfte Liste wie folgt zu verfahren: 


currentNode = randomNode;//where randomNode may or may not = firstNode
prevNode = firstNode;
while(prevNode != currentNode && prevNode->link != currentNode)
{
    prevNode = prevNode->link;
}

Ist es möglich, dies in C ++ zu tun, wenn ich versuche, den Knoten vor currentNode in einer einfach verketteten Liste zu finden?

Ich versuche, so etwas wie dies in einer Konsolenanwendung für eine Schule Zuordnung zu implementieren, so davon ausgehen, dass ich nicht etwas Besonderes, wie das Boost-Bibliotheken / Liste / alles, was das Leben leichter macht verwenden kann usw. Also im Grunde habe ich nur recht primitive Datentypen und Bibliotheken zu meiner Verfügung.

War es hilfreich?

Lösung

Sie können sicherstellen möchten, dass prevNode-> Link nicht NULL-Verweis entweder ist, im Fall, dass currentNode eigentlich nicht verknüpft.

Andere Tipps

Das sollte gut funktionieren. Haben Sie versucht es noch?

Dieser Code wird einen Teil Ihrer Liste durchlaufen, aber welcher Teil hängt davon ab, welche Art und Weise Ihrer Liste verknüpft ist. Wenn es von Kopf- geht> Schwanz (sprich: Kopfknoten Verbindungen zu einem Knoten, die Links in Richtung Schwanz), dann würden Sie Ihre Liste aus dem zufälligen Ort an den Schwanz ausgehend durchqueren. Wenn die Links Kopf sind <-tail dann würden Sie von dem zufälligen Ort auf den Kopf durchqueren. In jedem Fall würden Sie nicht alle Knoten in der Liste berühren.

Alle oben genannten übernimmt einige Link-Liste als solche: 

[head]<->[0...N Nodes]<->[Tail]

Die Links können entweder so sein.

Auch könnten Sie den Kopf und Schwanz Knoten verbinden und eine kreisförmig verbundene Liste erstellen. In diesem Szenario ist es möglich, alle Knoten zu besuchen, indem Sie einfach durchlaufen, bis Sie zurück zu Ihrem ursprünglichen Knoten sind.

Achten Sie darauf, alle möglichen Grenzfälle betrachten:

  • Was passiert randomNode firstNode gleich? Was Sie zurück? Was sollte Sie zurückkommen?
  • Was passiert, wenn randomNode der letzte Knoten in der Liste ist?
  • Was passiert, wenn randomNode NULL ist?
  • Was passiert, wenn randomNode nicht in der Liste?

Nun, nicht alle diese Fälle anwendbar sein kann, je nachdem, ob Sie etwas über randomNode wissen, und einige von ihnen können trivial sein. Aber sie sind alle bedenkenswert.

Wenn Sie alle diese sehr sorgfältig zu prüfen, gibt es eine einfache und elegante Lösung, die Griffe alle.

Der Code sieht gut aus, aber ich würde eine geringfügige Änderung Ihrer while Bedingung

vorschlagen 
while(prevNode != currentNode && prevNode != NULL)

Aus zwei Gründen

  • Ihr Code, wie zur Zeit konnte angegeben, stoppen, wenn der Knoten wir suchen ist, auf den beiden prevNode oder prevNode->link (und deshalb werden wir keine Ahnung haben, was insbesondere einen der beiden Punkte zu currentNode - wenn wir wollten wissen, wir würden mit einem if Zustand überprüfen). Mit der Änderung oben wird der Zielknoten garantiert in prevNode gespeichert werden (wenn überhaupt - siehe nächsten Punkt).
  • Zur Sicherheit willen, wäre es gut, dass prevNode zu überprüfen, ist nicht NULL. Doch wie Pavel erwähnt, ist dieser Test nicht erforderlich, wenn currentNode gewährleistet ist in der Liste sein.

Bearbeiten in Reaktion auf Kommentar

Da müssen Sie nicht wissen, ob currentNode in prevNode oder prevNode->link ist, und da Sie stoppen wollen (wenn möglich) auf currentNode == prevNode->link, dann Ihrem ursprünglichen while ist in Ordnung. Allerdings ...

  

gibt es eine if-Anweisung höher in   der Code, dass verhindert   prevNode vom Wesen null   bereits

Es scheint, wie Sie fehlt den Punkt, warum Sie für NULL überprüfen sollten. Ja, das ist gut Sie es zu prüfen, bevor, aber der Grund, warum wir die NULL Prüfung in der Schleife haben, ist in dem Fall, in dem currentNode ist nicht in der Liste, so dass Sie schließlich den letzten Knoten zu erreichen. Vermutlich (wenn Sie dies tun, wie die meisten anderen verkettete Listen) den Wert von link für Ihre letzte Knoten ist NULL. Wenn ja, wird Ihre aktuelle Code schließlich am Ende NULL->link Aufruf was natürlich Ihr Programm abstürzen. Deshalb sollten Sie noch überprüfen sollten NULL 

while(prevNode != NULL && prevNode != currentNode && prevNode->link!=currentNode)

Wenn Sie absolut sicher , dass currentNode in der Liste sein werden, dann ich erraten , dass der Check ist auch nicht notwendig, aber es ist wirklich eine gute angewöhnen .

Sie können sogar haben: 

while (prevNode && prevNode != currentNode)
    prevNode = prevNode->link;

Aber was Sie sieht gut aus.

Eine kleine Sache, die ich mit dem Code als gebucht (abgesehen von der Möglichkeit, in anderen Antworten von Ablaufen des Endes der Liste diskutiert, wenn currentNode nicht auf der Liste oder andere Fehlerbehandlung ist) ändern würde, ist, dass, wenn die während Schleife wird Sie, wenn prevNode oder prevNode->link Punkte currentNode wissen nicht getan. Das ist kein großes Problem (da kann man es leicht Test), aber es scheint mir, dass es für diese spezielle Fall Situation vor der Suche nach Test am besten ist, so ist es klar, dass es ein besonderer Fall.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top