Einfache Verkettung - Zeiger ans Ende stellen

cpts · 13. August 2022

Hallo!

Ihr habt mir bereits zu meiner Lagerverwaltung einen guten Tip gegeben und nun verzweifle ich am nächsten Thema.
Da ihr mir im alten Thread großzügigerweise weitere Hilfe angeboten hast, dachte ich, ich schreibe einfach mal.

Ich habe hier folgenden Code zu einer einfach verketteten Liste:

Code:

#include <iostream>
using namespace std;


struct listenelement{
string daten;
listenelement* next;
};


//----------


void anhaengen(string datenneu, listenelement* listenanfang){
listenelement* hilfszeiger1 = listenanfang;






while(hilfszeiger1->next != nullptr)
hilfszeiger1 = hilfszeiger1->next;


hilfszeiger1->next = new(listenelement);
hilfszeiger1 = hilfszeiger1->next;
hilfszeiger1->daten = datenneu;


hilfszeiger1->next = nullptr;
}


void ausgeben(listenelement* listenanfang){
listenelement* hilfszeiger1;
hilfszeiger1 = listenanfang;
cout << hilfszeiger1->daten << endl;


while(hilfszeiger1->next != nullptr){
hilfszeiger1 = hilfszeiger1->next;
cout << hilfszeiger1->daten << endl;
}
}


void ende(listenelement* listenanfang){
listenelement* hilfszeiger1;


while(listenanfang != nullptr){
hilfszeiger1 = listenanfang;
listenanfang = listenanfang->next;
delete(hilfszeiger1);
}
}




int main(){


listenelement* listenanfang;
listenanfang = new(listenelement);
listenanfang->next = nullptr;
listenanfang->daten = "Element 1";


listenelement* listenende;


anhaengen("Element 2", listenanfang);
anhaengen("Element 3", listenanfang);
anhaengen("Element 4", listenanfang);


ausgeben(listenanfang);
ende(listenanfang);


return 0;
}

______________________________________________________________________________________________________________

Mein Ziel ist es, einen Hilfszeiger zu erschaffen, der permanent auf das Ende der Liste zeigt, so dass ich beim Anfügen von neuen Elementen nicht mehr die ganze Liste durcharbeiten muss bis zum nullptr, sondern direkt weiß, wo das Ende ist (so, wie ich auch genau weiß, wo der Anfang ist).

Meine Internet-Recherche auf Youtube oder in anderen Forenbeiträgen hat mich ehrlich gesagt nur noch mehr verwirrt, dabei ist es eigentlich ganz einfach - glaube ich.
Wo stehe ich denn auf dem Holzweg? Könnt ihr mir einen Tip geben?

mfg

Zvoni · 15. August 2022

Du brauchst entweder ein weiteres Feld "LetztesElement" in ListenElement
Nachteil: Immer wenn du ein weiteres Element anhängst musst du wieder durch alle Elemente rennen, und den Zeiger auf das letztes Element biegen

Oder:
Erzeuge eine "Super"-Struct

C:

struct listenelement{
    string daten;
    listenelement* next;
};

struct SuperStruktur {
    listenelement* LetztesElement;
    listenelement* liste;
}

So speicherst du nur einmal den Zeiger auf das letzte Element, und über "liste" kannst du dann wie gewohnt arbeiten

EDIT: Erinnert mich doch stark an einen Stack....

EDIT2: Mir ist doch noch ne dritte Variante eingefallen: Dreh die Liste um.
Anstelle von "das neu erzeugte Listenelement" an "next" der Liste zu hängen, hänge die Liste an das "next" des neuen Listenelements.
Heisst: Du hängst nicht hinten an, du fügst vor dem ersten ein.

Technipion · 15. August 2022

Ich habe auf diesen Post absichtlich nicht geantwortet, weil
1. im Originalpost der Code völlig unleserlich nicht in Codetags gepasst wurde und
2. die Frage viel zu unspezifisch gestellt ist.

cpts hat gesagt.:
Mein Ziel ist es, einen Hilfszeiger zu erschaffen, der permanent auf das Ende der Liste zeigt, so dass ich beim Anfügen von neuen Elementen nicht mehr die ganze Liste durcharbeiten muss bis zum nullptr, sondern direkt weiß, wo das Ende ist (so, wie ich auch genau weiß, wo der Anfang ist).

Was genau soll das heißen?
Ich tippe ja darauf, dass damit die "SuperStruktur" von @Zvoni gemeint ist. Es könnte aber z.B. auch sein, dass von jedem Listenelement aus das Ende erreichbar sein soll.

Zvoni hat gesagt.:
Nachteil: Immer wenn du ein weiteres Element anhängst musst du wieder durch alle Elemente rennen, und den Zeiger auf das letztes Element biegen

Jopp, außer natürlich du speicherst einen Zeiger auf einen Zeiger. Die Listenelemente referenzieren dann sozusagen den Ort, wo der Zeiger auf das letzte Listenelement zu finden ist.

Aber ich sehe es halt auch nicht ein hier viel meiner Zeit reinzustecken, wenn der Fragesteller das nicht wenigstens auch tut.

Gruß Technipion

Zvoni · 15. August 2022

Die prinzipielle Frage ist: Wofür braucht er die Liste?
eine einfach verkettete Liste ist meist ein Hinweis auf einen Stack.
Bei einer einfach verketteten Liste "arbeitet" man eigentlich immer nur mit dem ersten/vordersten Element (weil eben dieses einen Zeiger auf das nächste hat)
Richtig aufgebaut, kann das erste Element das zuletzt hinzugefügte sein (Siehe mein Edit2)

cpts · 15. August 2022

Erstmal: Danke, dass ihr überhaupt antwortet!

Dann: Sorry, dass das so unformatiert ist, ich hab den Button gesucht, wo ich das als Code einfügen kann, aber irgendwie nicht gefunden .. (?) EDIT: Aha, jetzt aber...

Ich mache gerade ein Fernstudium über die ILS für C++ und da wird in einem Heft das Thema einfach verkettete Listen behandelt. Die Einsendeaufgabe am Ende ist unter anderem das Ändern der einfach verketteten Liste so, dass der Zeiger nicht auf den Listenanfang zeigt, sondern auf das Listenende. Das soll verhindern, dass das Programm beim Anhängen eines neuen Elements erstmal durch die gesamte Bestandsliste durchklöppelt bist der nullptr erreicht ist, sondern direkt aufs Ende springt.

Also wenn ich jetzt ein Element neu anhänge, dann wandert ja das Programm vom Listenanfang (auf den der permanente Zeiger zeigt) von Element zu Element zu Element usw. , bis das Element erreicht ist, das als next-Zeiger den NULL hat . Das soll gem. Aufgabenstellung verhindert werden, indem ein permanenter Zeiger erschaffen wird (so wie der Listenanfangs-Zeiger), der auf das Ende zeigt und jedes mal, wenn ich ein neues Element anhänge, der Zeiger wieder aufs Ende zeigt.

Ich finde die Aufgabe total bescheuert, aber ich hänge da jetzt seit knapp 2 Wochen am grübeln in kriegs nicht hin.

Zvoni · 15. August 2022

Dann meine SuperStruktur oder das in Edit2

Technipion · 17. August 2022

cpts hat gesagt.:
Dann: Sorry, dass das so unformatiert ist, ich hab den Button gesucht, wo ich das als Code einfügen kann, aber irgendwie nicht gefunden .. (?) EDIT: Aha, jetzt aber...

Ahhh, super! Weißt du, die Sache ist die: Niemand reißt dir den Kopf ab, wenn du hier eine Frage schlecht stellst. Letztenendes sind wir alle ja hier, weil wir dir helfen wollen. Wir ziehen alle am gleichen Strang. Aber wenn du natürlich mehr Zeit in die Frage investierst, dir mehr Gedanken machst, und sie dann klarer und präziser formulierst, dann gibst du uns viel mehr Orientierung bei der Beantwortung, und demensprechend werden die Antworten eine viel höhere Qualität haben und dir besser weiterhelfen.
Also in Zukunft weißt du: Je mehr Info du uns gibst, desto besser werden die Antworten.

Kommen wir also zu deinem Problem:

Zvoni hat gesagt.:
Dann meine SuperStruktur oder das in Edit2

Ja im Prinzip isses das. Allerdings willst du ja C++ lernen (und auch wie man als C++-Programmierer denkt). Hier würde es sich anbieten, denn Typ von anhaengen zu ändern, und zwar auf einen Zeiger auf listenelement. Die Idee dahinter: Jedes Mal wenn du ein Element anhängst, bekommt die Liste ja ein neues Ende. Den Zeiger auf eben dieses neue Ende geben wir dann einfach als Rückgabewert zurück. Damit wird aus
anhaengen("Element 2", listenanfang);
im Grunde einfach das hier:
listenende = anhaengen("Element 2", listenanfang);

Jetzt haben wir in der main() immer einen aktuellen Zeiger auf das Ende der Liste (listenende).

Aber halt! Wofür machen wir nochmal das alles? Ah genau, weil es uns beim Anhängen viel Zeit spart, wenn wir das letzte Element schon kennen, und uns nicht erst durch die ganze Liste arbeiten müssen. Für die 1+ mit Stern schreiben wir also die Funktion anhaengen nochmal um, sodass sie statt eines Zeigers auf den Listenanfang einen Zeiger auf das Listenende benutzt. Das Anhängen an die Liste wird damit zu einer Operation mit O(1), also mit konstanter Laufzeit. Eine Verbesserung von O(n) zu O(1) - nicht schlecht!

Hier der Code, falls du etwas nachlesen willst:

C++:

#include <iostream>

using namespace std; // Das macht man heute eigentlich nicht mehr
                     // Stichwort: namespace poisoning / namespace pollution


struct listenelement {
    string daten;
    listenelement* next;
};


listenelement* anhaengen(string datenneu, listenelement* listenanfang) {
    listenelement* hilfszeiger1 = listenanfang;

    while(hilfszeiger1->next != nullptr)
        hilfszeiger1 = hilfszeiger1->next;

    hilfszeiger1->next = new(listenelement);
    hilfszeiger1 = hilfszeiger1->next; // Laufe ein Element vorwärts
    hilfszeiger1->daten = datenneu;

    hilfszeiger1->next = nullptr;

    // hilfsteiger1 zeigt jetzt auf das letzte Element
    return hilfszeiger1;
}


listenelement* anhaengen_schnell(string datenneu, listenelement* listenende) {
    listenelement* hilfszeiger1 = listenende; // Wir sind schon da
    // Deshalb sparen wir uns hier den Durchlauf in der while-Schleife

    hilfszeiger1->next = new(listenelement);
    hilfszeiger1 = hilfszeiger1->next; // Laufe ein Element vorwärts
    hilfszeiger1->daten = datenneu;

    hilfszeiger1->next = nullptr;

    // hilfsteiger1 zeigt jetzt auf das letzte Element
    return hilfszeiger1;
}


void ausgeben(listenelement* listenanfang) {
    listenelement* hilfszeiger1;
    hilfszeiger1 = listenanfang;
    cout << hilfszeiger1->daten << endl;

    // Wäre hier eine do-while Schleife nicht besser geeignet?
    while(hilfszeiger1->next != nullptr) {
        hilfszeiger1 = hilfszeiger1->next;
        cout << hilfszeiger1->daten << endl;
    }
}


// Wofür ist diese Funktion da?
void ende(listenelement* listenanfang) {
    listenelement* hilfszeiger1;

    while(listenanfang != nullptr) {
        hilfszeiger1 = listenanfang;
        listenanfang = listenanfang->next;
        delete(hilfszeiger1);
    }
}


int main() {
    listenelement* listenanfang;
    listenanfang = new(listenelement);
    listenanfang->next = nullptr;
    listenanfang->daten = "Element 1";

    listenelement* listenende;

    listenende = anhaengen("Element 2", listenanfang);
    listenende = anhaengen("Element 3", listenanfang);
    listenende = anhaengen("Element 4", listenanfang);

    ausgeben(listenanfang);

    cout << "Das geht nur, weil wir das Listenende kennen:" << endl;

    listenende = anhaengen_schnell("Element 5", listenende);
    listenende = anhaengen_schnell("Element 6", listenende);
    listenende = anhaengen_schnell("Element 7", listenende);

    ausgeben(listenanfang);

    // Was soll dieser Aufruf hier bezwecken?
    //ende(listenanfang);


    return 0;
}

Gruß Technipion

cpts · 17. August 2022

ZITAT ANFANG

Ja im Prinzip isses das. Allerdings willst du ja C++ lernen (und auch wie man als C++-Programmierer denkt). Ja unbedingt ... !
Hier würde es sich anbieten, denn Typ von anhaengen zu ändern, und zwar auf einen Zeiger auf listenelement. Die Idee dahinter: Jedes Mal wenn du ein Element anhängst, bekommt die Liste ja ein neues Ende. Den Zeiger auf eben dieses neue Ende geben wir dann einfach als Rückgabewert zurück. Damit wird aus
anhaengen("Element 2", listenanfang);
im Grunde einfach das hier:
listenende = anhaengen("Element 2", listenanfang);

Jetzt haben wir in der main() immer einen aktuellen Zeiger auf das Ende der Liste (listenende).
Auf sowas wäre ich nicht gekommen ... schon, dass ich den Zeiger aufs Listenende als Rückgabewert an die Main() liefern muss, aber nicht wie. Sehr frustrierend ...

Aber halt! Wofür machen wir nochmal das alles? Ah genau, weil es uns beim Anhängen viel Zeit spart, wenn wir das letzte Element schon kennen, und uns nicht erst durch die ganze Liste arbeiten müssen. Richtig! Genau das war meine Intention! Für die 1+ mit Stern schreiben wir also die Funktion anhaengen nochmal um, sodass sie statt eines Zeigers auf den Listenanfang einen Zeiger auf das Listenende benutzt. Das Anhängen an die Liste wird damit zu einer Operation mit O(1), also mit konstanter Laufzeit. Eine Verbesserung von O zu O(1) - nicht schlecht!

Hier der Code, falls du etwas nachlesen willst:
Spoiler: Code - aber versuch ruhig erst mal es selbst hinzubekommen
C++:

C++:

#include <iostream>

using namespace std; // Das macht man heute eigentlich nicht mehr
// Stichwort: namespace poisoning / namespace pollution
[HR][/HR]
/*Wow, ok ... hab den Kurs ganz aktuell bei der ILS gebucht, dort wird es als Lernmethode beigebracht. Habe aber anderswo auch schon gelesen, dass die ILS - zumindest in diesem Kurs - gar nicht sooo hervorragend sein soll :( */
[HR][/HR]

struct listenelement {
string daten;
listenelement* next;
};


listenelement* anhaengen(string datenneu, listenelement* listenanfang) {
listenelement* hilfszeiger1 = listenanfang;

while(hilfszeiger1->next != nullptr)
hilfszeiger1 = hilfszeiger1->next;

hilfszeiger1->next = new(listenelement);
hilfszeiger1 = hilfszeiger1->next; // Laufe ein Element vorwärts
hilfszeiger1->daten = datenneu;

hilfszeiger1->next = nullptr;

// hilfsteiger1 zeigt jetzt auf das letzte Element
return hilfszeiger1;
}

/* Verstehe ich das richtig, dass ich die Funktion anhaengen() überhaupt ein erstes Mal durchlaufen lassen muss, damit ich überhaupt ans Ende gelange und erst nach dem einmaligen "Komplettdurchlauf" weiß, wo mein Zeiger fürs Ende ist und somit danach dann die Funktion anhaengen_schnell nutzen kann um mir den Weg durch die komplette Liste zu sparen? */

listenelement* anhaengen_schnell(string datenneu, listenelement* listenende) {
listenelement* hilfszeiger1 = listenende; // Wir sind schon da
// Deshalb sparen wir uns hier den Durchlauf in der while-Schleife

hilfszeiger1->next = new(listenelement);
hilfszeiger1 = hilfszeiger1->next; // Laufe ein Element vorwärts
hilfszeiger1->daten = datenneu;

hilfszeiger1->next = nullptr;

// hilfsteiger1 zeigt jetzt auf das letzte Element
return hilfszeiger1;
}


void ausgeben(listenelement* listenanfang) {
listenelement* hilfszeiger1;
hilfszeiger1 = listenanfang;
cout << hilfszeiger1->daten << endl;

// Wäre hier eine do-while Schleife nicht besser geeignet?
/* Besteht da ein gravierender Unterschied? Habe mir über die Wahl der Schleife keine großen Gedanken gemacht - noch nicht. */

while(hilfszeiger1->next != nullptr) {
hilfszeiger1 = hilfszeiger1->next;
cout << hilfszeiger1->daten << endl;
}
}


// Wofür ist diese Funktion da?
/*Diese Funktion soll am Ende des Programmes die Liste Stück für Stück löschen und den Speicher wieder freigeben.*/

void ende(listenelement* listenanfang) {
listenelement* hilfszeiger1;

while(listenanfang != nullptr) {
hilfszeiger1 = listenanfang;
listenanfang = listenanfang->next;
delete(hilfszeiger1);
}
}


int main() {
listenelement* listenanfang;
listenanfang = new(listenelement);
listenanfang->next = nullptr;
listenanfang->daten = "Element 1";

listenelement* listenende;

listenende = anhaengen("Element 2", listenanfang);
listenende = anhaengen("Element 3", listenanfang);
listenende = anhaengen("Element 4", listenanfang);

ausgeben(listenanfang);

cout << "Das geht nur, weil wir das Listenende kennen:" << endl;

listenende = anhaengen_schnell("Element 5", listenende);
listenende = anhaengen_schnell("Element 6", listenende);
listenende = anhaengen_schnell("Element 7", listenende);

ausgeben(listenanfang);

// Was soll dieser Aufruf hier bezwecken? s.o.
//ende(listenanfang);


return 0;
}

ZITAT ENDE

Vielen Dank für diese ausführliche Antwort!
Habe dich anfangs auch nicht falsch verstanden oder forsch aufgefasst, alles gut!

Ich sehe, ich habe noch einiges zu lernen :/
mfG
cpts

EDIT1: Wie bekomme ich es hin, dass mein Code im Forum nicht nur als Code angezeigt wird, sondern als C++-Code, so wie bei dir?

Zvoni · 18. August 2022

EDIT1: Wie bekomme ich es hin, dass mein Code im Forum nicht nur als Code angezeigt wird, sondern als C++-Code, so wie bei dir?

(Ich musste hier ein Leerzeichen zwischen E und = einfügen, sonst wird der BB-Code umgewandelt)
[CODE =cpp]
//Hier c++-Code
[/CODE]
... oder auf die drei senkrechten Punkte über dem Textfeld hier, und dort dann den </>-Button auswählen

cpts · 18. August 2022

Danke!

Und danke für eure ausführlichen Erklärungen und Hilfestellungen !

Habe das Gefühl, dieses Forum und so manch ein Youtube-Kanal sind lehrreicher, als der ILS-Kurs ...

EDIT:

Ich bekomme beim letzten Anhängen (Zeile 88 bei Technipion) die Fehlermeldung, bzw. den Hinweis
"Value stored to 'listenende' is never read [clang-analyzer-deadcode.DeadStores]"

Was genau heißt das? Bzw., ist das jetzt irgendwie schlimm? Weil beim Ausführen des Codes, scheint alles zu klappen.

Einfache Verkettung - Zeiger ans Ende stellen

cpts

Grünschnabel

Technipion

Zvoni

Erfahrenes Mitglied

Technipion

Erfahrenes Mitglied

Zvoni

Erfahrenes Mitglied

cpts

Grünschnabel

Zvoni

Erfahrenes Mitglied

Technipion

Erfahrenes Mitglied

cpts

Grünschnabel

Zvoni

Erfahrenes Mitglied

cpts

Grünschnabel

Neue Beiträge