Einfach verkettete Liste mit Listenendezeiger
-
Hallo Programmierer,
Ich habe hier ein kleines Problem das schon des Öfteren besprochen worden ist, aber dennoch komme ich nicht auf die Lösung.
Ich habe hier eine einfach verkettete Liste bei der ich zurzeit noch den Listenanfang bzw. auch Listenkopf genannt übergebe. Meine Aufgabe ist es allerdings nicht mehr den Listenanfang zu übergeben sondern das Listenende dies muss auch wieder an die main Funktion zurückgegeben werden. Jedes weitere "einfügen" bekommt auch das "listenende" sowie die "ausgabe" und das "löschen" der Liste.(Vollständiger Quellcode im Anhang)
Hat wer eine Idee dazu?
#include <iostream> using namespace std; //Die Struktur für die Listenelemente struct listenelement { string daten; listenelement *next; }; //Eine Funktion zu Anhängen von Elementen an die Liste void anhaengen (string datenneu, listenelement *listenanfang) { //ein lokaler Hilfszeiger, um in der Liste wandern zu können listenelement *hilfszeiger; //den hilfszeiger an den Anfang der Liste setzen hilfszeiger = listenanfang; //Durch die Liste gehen, bis das letzte Element erreicht ist while (hilfszeiger->next != nullptr) { hilfszeiger = hilfszeiger->next; } //Ein neues Element am ende der Liste anhängen hilfszeiger->next = new(listenelement); //den Hilfszeiger auf das neue Element setzen hilfszeiger = hilfszeiger->next; //die Daten in das neue Element eintragen hilfszeiger->daten = datenneu; //es gibt keinen Nachfolger, daher wird next auf nullptr gesetzt hilfszeiger->next = nullptr; } //Eine Funktion zum ausgeben aller Elemente void ausgabe(listenelement *listenanfang) { //Ein lokaler Hilfszeiger, um in deer Liste wandern zu können listenelement *hilfszeiger; //den Hilfszeiger auf den Anfang der Liste setzen hilfszeiger = listenanfang; //das erste Element ausgeben cout << hilfszeiger->daten << '\n'; //Solange das Ende der Liste noch nicht erreicht ist: while (hilfszeiger->next != nullptr) { //den Hilfszeiger hilfszeiger auf das nächste Element setzen hilfszeiger = hilfszeiger->next; //Daten ausgeben cout << hilfszeiger->daten << '\n'; } } //die Liste leeren und Speicher freigeben void ende(listenelement *listenanfang) { //Ein lokaler Hilfszeiger, um in der Liste wandern zu können listenelement *hilfszeiger; //Solange noch Elemente in der Lsite sind while (listenanfang != nullptr) { //den Hilfszeiger auf das erste Element der Liste setzen hilfszeiger = listenanfang; //den Zeiger für den Listenanfang auf das nächste Element setzen listenanfang = listenanfang->next; //den Speicher für das herausgenommene Element freigeben delete(hilfszeiger); } } int main() { //ein Zeiger auf den Anfang der Liste setzen listenelement *listenanfang; //das erste Element erzeugen listenanfang = new(listenelement); //Daten in das erste Element schreiben listenanfang->next = nullptr; listenanfang->daten = "Daten in Liste 1"; //und jetzt weitere Elemente erzeugen anhaengen("Daten in Liste 2", listenanfang); anhaengen("Daten in Liste 3", listenanfang); //die Liste ausgeben ausgabe(listenanfang); //die Liste wieder abbauen ende(listenanfang); return 0; }
-
Ich hab dir mal Tags spendiert.
Dein Code ist uebrigens C mit
new
/delete
. Ich weiss nicht, ob du schon bei Konstruktoren und Destruktoren angelangt bist, aber wenn nicht, solltest du dir mal RAII ud das C++ Objektmodell anschauen. Edit: Achso, du hast ja noch gar keine Listenklasse im eigentlichen Sinn. Macht aber eigentlich keinen Unterschied: Man kann ein Element sein Datum und seinen Nachfolger killen lassen, und das Ursprungselement legst du auf dem Stack an. Ist zwar nicht endrekursiv, aber eine schoenere Loesung verlangt eben eine verwaltende Klasse (-> Liste).Was dein Problem angeht: Ist der Code im OP von dir, bin ich zuversichtlich, dass du auch den Rest schaffst. Hoert sich aber nach einer Hausaufgabe an, und daher waere etwas Eigeninitiative angebracht.
-
theprofile schrieb:
Hat wer eine Idee dazu?
Bitte gib mal den genauen Aufgabentext wieder, nicht diene Interpretation davon.
Arcoth schrieb:
Dein Code ist uebrigens C mit
new
/delete
.Da tust du C unrecht. Das Datenmodell hier ist in jeder Sprache schlecht. Es kann ja nicht einmal eine leere Liste existieren. Selbst wenn man auf OOP verzichtet, sollte das nicht so sein. Schlechter Lehrer?
-
SeppJ schrieb:
Arcoth schrieb:
Dein Code ist uebrigens C mit
new
/delete
.Da tust du C unrecht. Das Datenmodell hier ist in jeder Sprache schlecht. Es kann ja nicht einmal eine leere Liste existieren.
Nullzeiger auf listenelement?
-
theprofile schrieb:
Ich habe hier eine einfach verkettete Liste bei der ich zurzeit noch den Listenanfang bzw. auch Listenkopf genannt übergebe. Meine Aufgabe ist es allerdings nicht mehr den Listenanfang zu übergeben sondern das Listenende dies muss auch wieder an die main Funktion zurückgegeben werden. Jedes weitere "einfügen" bekommt auch das "listenende" sowie die "ausgabe" und das "löschen" der Liste.
Es klingt erstmal völlig abwegig, bei einer einfach verketteten Liste das Listenende zu übergeben. Was bedeutet es, wenn ein weiteres "einfügen" die "ausgabe" bekommt? (vermutlich meinst du mit deinem Satz irgendwas anderes)
Ich verstehe die Aufgabe nicht. Formuliere sie bitte deutlich. Ein genaues Verständnis der Aufgabe ist der erste Schritt zur Lösung. Wenn du dir genau überlegt hast, was du eigentlich warum machen willst, kommst du auch vielleicht selbst auf die Lösung.
PS: habe deinen Quellcode nur optisch angeguckt (ohne zu lesen) und finde, dass deutlich zu viele Kommentare drin sind. Kommentiere besser die Funktionen inkl. Anforderungen deutlich. Das betrifft insbesondere sowas wie:
//die Liste ausgeben ausgabe(listenanfang);
-
Arcoth schrieb:
SeppJ schrieb:
Arcoth schrieb:
Dein Code ist uebrigens C mit
new
/delete
.Da tust du C unrecht. Das Datenmodell hier ist in jeder Sprache schlecht. Es kann ja nicht einmal eine leere Liste existieren.
Nullzeiger auf listenelement?
Ist hier aber nicht so gemacht.
-
wob schrieb:
Es klingt erstmal völlig abwegig, bei einer einfach verketteten Liste das Listenende zu übergeben. Was bedeutet es, wenn ein weiteres "einfügen" die "ausgabe" bekommt?
Beim einfachen Anhängen ist es doch sinnvoll direkt das Listenende zu übergeben? Einfach weil dann nicht erst rekursiv das letzte Element geholt werden muss sondern direkt angefügt werden kann.
Bedeuted ja eigentlich nur, dass die Funktion "anhaengen" nicht mehr den Anfang sondern das Ende erhält und wenn ich der Aufgabenstellung folge, das neue Element zurück liefert.
Vereinfacht die Anwendung ja auch ungemein:
listenelement *anhaengen (string datenneu, listenelement *listenende) { listenende->next = new(listenelement); listenende = listenende->next; listenende->daten = datenneu; listenende->next = nullptr; return listenende; }
-
Gut, mag sein. Allerdings: was ist das Ende? Ist das der letzte next-Zeiger (der wäre nullptr, das geht also nicht) oder das letzte existierende Element (was ist dann mit leeren Listen?)?
Und wenn man die Aufgabe
Meine Aufgabe ist es allerdings nicht mehr den Listenanfang zu übergeben sondern das Listenende dies muss auch wieder an die main Funktion zurückgegeben werden. Jedes weitere "einfügen" bekommt auch das "listenende" sowie die "ausgabe" und das "löschen" der Liste.
so liest, dass "löschen" nun auch als Parameter das Ende bekommen soll, ist das gänzlich wertlos - denn wie soll man korrekt löschen können, ohne den Anfang zu kennen? Irgendwas stimmt hier doch nicht.
-
Ja, da hast du recht. Ich denke dass der Teil mit dem Ausgeben und Löschen aus dem Zusammenhang geraten ist. Funktioniert bei einer einfach verketteten Liste ja auch nicht über das letzte Element.
-
Also erstmal Danke für die vielen und schnellen Antworten.
Anbei nochmal die Fragestellung etwas genauer.
Es geht hier darum in der Funktion -anhaengen- das Listenende zu übergeben bzw. zu ermitteln, dieses aber auch wieder an die -main- Funktion zurückzugeben um damit weiter "arbeiten" (als Argument beim Anhängen übergeben) zu können.
Es soll damit bezweckt werden dass nicht immer erst vom ersten bis zum letzten Element "gewandert" werden muss, sondern gleich das letzte Element bekannt ist.*Die Funktion -ausgabe- und -löschen- bekommen weiterhin den Listenanfang!
Es muss allerdings dafür gesorgt werden das dass -Listenende- nach jedem anhängen neu ermittelt wird. Ich habe schon etliche Wege probiert wie z.Bsp. zwei weitere Zeiger (Pointer) - *begin und *last - in der Struktur (struct) einzufügen und mit denen zu arbeiten allerdings kann ich diese nicht an die -main- Funktion zurückgeben.
Falls ihr meine Lösungsverusche sehen wollt, kann ich diese natürlich auflisten.
Meine Frage wäre ob denn wer einen Weg kennt den Quellcode nicht Großartig zu ändern sondern rein die Funktion -aendern- zu ändern. Ich bin hier nicht auf Lösungen aus sondern rein auf Ansatzwege.
Danke im Voraus.
-
Du hast es in 6 Stunden nicht geschafft meinen Beitrag anzusehen und auszuprobieren?
-
inflames2k schrieb:
Du hast es in 6 Stunden nicht geschafft meinen Beitrag anzusehen und auszuprobieren?
Nein hatte ich leider noch nicht bis jetzt.
Hier meine Version davon, allerdings wird mir nur immer das letzte Element ausgegeben. Liegt das daran weil ich den Zeiger immer wieder überschreibe oder?
#include <iostream> using namespace std; //Die Struktur für die Listenelemente struct listenelement { string daten; listenelement *next; }; //Eine Funktion zu Anhängen von Elementen an die Liste listenelement *anhaengen (string datenneu, listenelement *listenende) { //Ein lokaler Hilfszeiger, um in deer Liste wandern zu können listenelement *hilfszeiger; //den Hilfszeiger auf das letzte Element setzen hilfszeiger = listenende; while (hilfszeiger->next != nullptr) { hilfszeiger = hilfszeiger->next; } hilfszeiger->next = new(listenelement); listenende = hilfszeiger->next; hilfszeiger->daten = datenneu; hilfszeiger->next = nullptr; return listenende; } //Eine Funktion zum ausgeben aller Elemente void ausgabe(listenelement *listenanfang) { //Ein lokaler Hilfszeiger, um in deer Liste wandern zu können listenelement *hilfszeiger; //den Hilfszeiger auf den Anfang der Liste setzen hilfszeiger = listenanfang; cout << hilfszeiger->daten << '\n'; while (hilfszeiger->next != nullptr) { hilfszeiger = hilfszeiger->next; //Daten ausgeben cout << hilfszeiger->daten << '\n'; } } //die Liste leeren und Speicher freigeben void ende(listenelement *listenanfang) { //Ein lokaler Hilfszeiger, um in der Liste wandern zu können listenelement *hilfszeiger; //Solange noch Elemente in der Liste sind while (listenanfang != nullptr) { hilfszeiger = listenanfang; listenanfang = listenanfang->next; //den Speicher für das herausgenommene Element freigeben delete(hilfszeiger); } } int main() { //ein Zeiger auf den Anfang der Liste setzen listenelement *listenanfang, *listenende; //das erste Element erzeugen listenanfang = new(listenelement); //Daten in das erste Element schreiben listenanfang->next = nullptr; listenanfang->daten = "Daten in Liste 1"; listenende = listenanfang; //und jetzt weitere Elemente erzeugen anhaengen("Daten in Liste 2", listenende); anhaengen("Daten in Liste 3", listenende); anhaengen("Daten in Liste 4", listenende); anhaengen("Daten in Liste 5", listenende); //die Liste ausgeben ausgabe(listenanfang); //die Liste wieder abbauen ende(listenanfang); return 0; }
-
Hauptsächlich liegt es an fehlerhaftem Code.
Der Hilfszeiger in anhaengen ist unnötigt, nur die letzten 5 Codezeilen sind relevant. Alles andere kann raus.
//Eine Funktion zu Anhängen von Elementen an die Liste listenelement *anhaengen (string datenneu, listenelement *listenende) { //Ein lokaler Hilfszeiger, um in deer Liste wandern zu können listenelement *hilfszeiger; //den Hilfszeiger auf das letzte Element setzen hilfszeiger = listenende; while (hilfszeiger->next != nullptr) { hilfszeiger = hilfszeiger->next; } hilfszeiger->next = new(listenelement); listenende = hilfszeiger->next; hilfszeiger->daten = datenneu; hilfszeiger->next = nullptr; return listenende; }
In deiner Main musst du auch listenende mit dem Rückgabewert überschreiben.
listenende = anhaengen("Daten in Liste 2", listenende);
Andernfalls hängst du immer wieder an das Startelement Daten an und setzt danach den Null-Pointer.
-
Ja genau so funktioniert es prima!
das verwende ich jetzt auch.
Aber gibt es noch eine andere Möglichkeit außer über die return Funktion diese Aufgabe umzusetzen. Wahrscheinlich über Klassen und listen?!
-
Ist nicht unbedingt die sauberste Variante, aber mit einer einfachen Klasse: IDE One
-
theprofile schrieb:
Aber gibt es noch eine andere Möglichkeit außer über die return Funktion diese Aufgabe umzusetzen. Wahrscheinlich über Klassen und listen?!
Ja.
Du kannst der Funktion
anhaengen
z.B. einen Zeiger auf einen Zeiger auflistenelement
übergeben. Dann kann die Funktion direkt denlistenelement
-Zeiger immain
ändern.Das selbe kannst du in C++ auch erreichen indem du eine Referenz auf einen Zeiger auf
listenelement
übergiebst. Dabei ändert sich in diesem Fall lediglich die Syntax leicht.=> Google dich zum Thema "Zeiger auf Zeiger" und "Referenzen" schlau.
Die Frage ist dann bloss noch ob das so gewünscht ist. Wäre leicht möglich dass euer Lehrer/Vortragender die
listenende = anhaengen("Daten in Liste 2", listenende);
Variante haben möchte. Oder auch ganz 'was anderes. z.B. wäre auchanhaengen("Daten in Liste 2", listenende); listenende = finde_ende(listenende);
denkbar, oder einfachanhaengen("Daten in Liste 2", listenende); listenende = listenende->next;
.
-
Okay super, Danke.
Werd mich mal schlau machen.