Reverse-doppelt-link-Liste in C++
Habe ich versucht herauszufinden, wie, um in umgekehrter Reihenfolge durch eine doppelt verknüpfte Liste, aber für einige Grund, in meiner Funktion void reverse()
while-Schleife läuft einmal durch und dann stürzt aus irgendeinem Grund. Ein paar Fragen vorneweg, ich bin selbst Lehre mich, mit meinen Brüdern zu helfen. Dies ist nicht der gesamte code, aber ich habe eine display()
Funktion druckt alle Knoten chronologisch von start_ptr
und einen Schalter, aktiviert bestimmte Funktionen wie
case 1 : add_end(); break;
case 2 : add_begin(); break;
case 3 : add_index(); break;
case 4 : del_end(); break;
case 5 : del_begin(); break;
case 6 : reverse(); break;
Dies ist der geist von meinem code:
#include <iostream>
using namespace std;
struct node
{
char name[20];
char profession[20];
int age;
node *nxt;
node *prv;
};
node *start_ptr = NULL;
void pswap (node *pa, node *pb)
{
node temp = *pa;
*pa = *pb;
*pb = temp;
return;
}
void reverse()
{
if(start_ptr==NULL)
{
cout << "Can't do anything" << endl;
}
else if(start_ptr->nxt==NULL)
{
return;
}
else
{
node *current = start_ptr;
node *nextone = start_ptr;
nextone=nextone->nxt->nxt;
current=current->nxt;
start_ptr->prv=start_ptr->nxt;
start_ptr->nxt=NULL;
//nextone=nextone->nxt;
while(nextone->nxt!= NULL)
{
pswap(current->nxt, current->prv);
current=nextone;
nextone=nextone->nxt;
}
start_ptr=nextone;
}
}
Sie vertauschen die Inhalte der Knoten, anstatt nur die Knoten Zeiger. Sind Sie sicher, dass Sie das tun wollen?
Auf ein zugehöriger Hinweis, man betrachtet die Dinge aus einer anderen Sicht. Anstatt reverse-die Inhalte der doppelt verknüpften Liste selbst, Sie könnten stattdessen auf die Iteration über den Inhalt der Liste in umgekehrter, das sollte unkompliziert sein, da die Liste ist in zweifacher Hinsicht verbunden. Zum Beispiel, implementieren STL-Stil bidirektionale Iteratoren für Ihre Liste. Sie können verwendet werden, mit der
Auf ein zugehöriger Hinweis, man betrachtet die Dinge aus einer anderen Sicht. Anstatt reverse-die Inhalte der doppelt verknüpften Liste selbst, Sie könnten stattdessen auf die Iteration über den Inhalt der Liste in umgekehrter, das sollte unkompliziert sein, da die Liste ist in zweifacher Hinsicht verbunden. Zum Beispiel, implementieren STL-Stil bidirektionale Iteratoren für Ihre Liste. Sie können verwendet werden, mit der
std::reverse_iterator<>
- adapter (für rbegin()
und rend()
). Sobald die Methoden implementiert, es werden einfach zu nutzen, die STL-algorithmen, einschließlich std::reverse()
. Es ist eine nette übung, IMO.
InformationsquelleAutor Dan | 2010-07-07
Du musst angemeldet sein, um einen Kommentar abzugeben.
Versuchen Sie dies:
Wow, vielen Dank, Mann, ich fixe dein code oben ein bisschen und es sieht so viel besser aus als alle meine anderen versuche. Alles, was Sie tun musste, war fügen Sie eine Qualifikation, wenn
start_ptr==NULL || start_ptr->nxt==NULL
und machen Sie Ihren Teil des Codes, der sonst Ende. Innerhalb von, ich sorgte dafür, dass am Ende code, derend_ptr->nxt=NULL;
Thanks a bunchIch bin mir nicht wirklich sicher, warum Sie müssen diese Prüfungen - ich denke, der code, den ich gab, wird auch ohne diese funktionieren. Und am Ende, end_ptr->nxt wird NULL, weil am Anfang, start_ptr->prv NULL war. Aber du bist willkommen, auf jeden Fall.
können wir nicht einfach zuweisen
head
Zeiger auf den letzten Knoten undNULL
zuprv
von der Startknoten?InformationsquelleAutor Borealid
EDIT: Meine erste Umsetzung, die korrekt war, aber nicht perfekt.
Ihre Umsetzung ist ziemlich kompliziert. Können Sie versuchen Sie dies:
Hier ist meine aktuelle Lösung:
Die Logik war richtig. Aber das Problem war, dass ich war der Annahme in der Eingabe argument start_ptr. Das bedeutet, dass ich die Rücksendung der lokalen Kopie. Nun sollte es funktionieren.
Ich kann einfach nicht herausfinden, wie ich tun könnte. Kann das jemand bestätigen, wenn dieser Implementierung wird ein Runder verlinkten Liste? Danke...
Ich habe es versucht und es wiederholt. (z.B. 2., 1., 2., 1., etc.)
Hi Danutenshu, ich habe aktualisiert mein Lösung. Ich kenne deine Probleme schon gelöst, aber ich würde viel besser fühlen, wenn Sie können, bitte lassen Sie mich wissen, wenn ich was geändert haben ist das so richtig?
InformationsquelleAutor bits
Können Sie vereinfachen Ihre
reverse()
ganz ein bisschen. Ich würde so etwas tun:Erklärung: Die Grundidee ist einfach, besuchen Sie jede
Node
und tauschen die links zuprevious
undnext
. Wenn wir uns bewegencurr
zum nächstenNode
wir müssen zum speichern des nächsten Knoten, so haben wir noch einen Zeiger darauf, wenn wir unscurr.next
zuprev
.In der Tat, und ich war off-by-one an den start. Sollte nun besser werden.
InformationsquelleAutor Justin Ardini
Einfache Lösung. kehrt in weniger als der halben Anzahl der gesamten Iterationen über die Liste
InformationsquelleAutor Hussain Pithawala
Schlage ich vor, Aufrechterhaltung einer Verbindung zum letzten Knoten.
Wenn nicht, finden Sie den letzten Knoten.
Durchlaufen der Liste verwenden Sie die "zurück" - links (bzw. in deinem Fall
prv
).Gibt es keine Notwendigkeit, tatsächlich ändern Sie den links um. Die Traversierung mit der
prv
Zeiger wird automatisch besuchen die Knoten in umgekehrter Reihenfolge.InformationsquelleAutor Thomas Matthews
Blick auf
Hier
nextone->nxt
null sein kann.Davon abgesehen, versuchen Sie, verwenden Sie Zeiger auf Zeiger in der swap-Funktion.
InformationsquelleAutor Diego Pereyra
Ihre pswap Funktion falsch ist
Ihr sollte ein vertauschen der Zeiger nicht versuchen, zu erstellen temporäre Objekte und tauschen Sie.
Sollte so sein, dass (möglicherweise gibt es noch weitere Fehler später)
Sie sind absolut richtig, ich schaue nicht auf die Signatur-Funktion. Nur Feste das temporäre Objekt-Erstellung Fehler
InformationsquelleAutor mb14
Sehr einfach und in O(n) Lösung mit zwei Zeigern:
start = Kopf der doppelt LL
InformationsquelleAutor Jyo the Whiff
Mein code für die Umkehrung doppelt verkettete Liste,
InformationsquelleAutor Ashish