attraversando una lista concatenata semplice in C ++

Question

Mi chiedevo se è possibile attraversare una lista collegata in questo modo:

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

E 'possibile fare questo in C ++ quando sto cercando di trovare il nodo prima nodoCorrente in una lista concatenata?

I cercando di implementare qualcosa di simile in una console app per un compito scolastico in modo da presumo che non posso usare qualcosa di fantasia come il librerie Boost / list / tutto ciò che rende la vita più facile, ecc Quindi, fondamentalmente, ho solo abbastanza tipi di dati primitivi e le librerie a mia disposizione.

Answer 1

Si potrebbe desiderare di fare in modo che prevNode- link> non è un riferimento null o, nel caso in cui nodoCorrente non è in realtà legata.

Answer 2

Questo dovrebbe funzionare bene. Hai provato ancora?

Answer 3

Che il codice attraverserà una parte della vostra lista, ma che parte dipende da quale modo la vostra lista è collegata. Se si passa da testa-> coda (leggi: i collegamenti nodo principale a un nodo che collega verso la coda) allora si sarebbe attraversare la vostra lista a partire dalla posizione casuale alla coda. Se i collegamenti sono testa <-tail allora si sarebbe attraversare dalla posizione casuale alla testa. In entrambi i casi, non sarebbe toccare tutti i nodi della lista.

Tutto quanto sopra assume qualche lista collegamento come ad esempio:

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

I collegamenti potrebbero essere in entrambi i modi.

Inoltre, è possibile collegare i nodi testa e di coda e creare un elenco circolarmente collegati. In questo scenario, è possibile visitare tutti i nodi, semplicemente attraversando finché non si è di nuovo al vostro nodo originale.

Answer 4

Assicurati di considerare tutte le possibili casi limite:

• Che cosa succede randomNode uguale firstNode? Cosa si torna? Ciò che dovrebbe si tornare?
• Cosa succede quando randomNode è l'ultimo nodo della lista?
• Cosa succede quando randomNode è NULL?
• Cosa succede quando randomNode non è nella lista?

Ora, non tutti questi casi possono essere applicabili, a seconda se si sa nulla di randomNode, e alcuni di questi potrebbe essere banale. Ma sono tutti la pena di pensare.

Se si considerano tutti questi con molta attenzione, c'è una soluzione semplice ed elegante che li gestisce.

Answer 5

Il codice guarda bene, ma vorrei suggerire una piccola modifica alla vostra condizione while

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

Per due motivi

• Il codice, come attualmente previsto, potrebbe fermare se il nodo che stiamo cercando è puntato da uno o prevNode prevNode->link (e quindi avremo idea di quale particolare uno dei due punti di currentNode - se volessimo conoscere, avremmo dovuto controllare con una condizione if). Con il cambiamento sopra, il nodo di destinazione è garantito da memorizzare in prevNode (se non del tutto - vedi punto successivo).
• Per motivi di sicurezza, sarebbe bene verificare che prevNode non è NULL. Tuttavia, come ricorda Pavel, questo test non è necessaria se currentNode è garantito per essere nella lista.

---

Modifica in risposta al commento

Dato che non c'è bisogno di sapere se currentNode è in prevNode o prevNode->link, e dal momento che si vuole fermare (se possibile) il currentNode == prevNode->link, allora il vostro while originale va bene. Tuttavia ...

  

c'è un'istruzione if più in alto   il codice che impedisce   prevNode dall'essere nullo   già

Sembra che vi state perdendo il punto di cui si dovrebbe verificare la presenza di NULL. Sì, va bene di controllare prima, ma il motivo per cui abbiamo il controllo NULL nel circuito è nel caso in cui currentNode è non nella lista, quindi alla fine si raggiunge l'ultimo nodo. Presumibilmente (se si fa questo come la maggior parte altre liste collegate) il valore del link per il vostro ultimo nodo è NULL. In tal caso, il codice corrente finirà per finire col chiamare NULL->link che ovviamente in crash il programma. È per questo che si deve ancora verificare la presenza di NULL

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

Se sei assolutamente sicuri che currentNode sarà nella lista, poi I indovinare che il check è anche inutile, ma è davvero una buona abitudine di entrare in .

Answer 6

È anche possibile avere:

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

Ma che cosa avete sembra a posto.

Answer 7

Una piccola cosa che vorrei cambiare con il codice come pubblicato (a parte la possibilità discusso in altre risposte di scappare alla fine della lista, se nodoCorrente non è sulla lista o altro la gestione degli errori) è che quando il tempo ciclo è fatto non si sa se prevNode o prevNode->link punti per currentNode. Questo non è un problema enorme (dal momento che si può facilmente verificare), ma mi sembra che è meglio per verificare questa situazione particolare caso prima della ricerca, quindi è chiaro che si tratta di un caso speciale.