Konstruktoren in C++

[ocsme]

Hallo zusammen,

ich habe mal wieder eine Frage diesmal bezüglich C++
Wollte mir eine Klasse schreiben die eine Liste repräsentiert.
Das ganze sieht bis jetzt wie folgt aus:

Liste.h

class Liste {
    class Node {
    public:
        int value;
        Node *next;
        Node *prev;
        Node(int value = 0, Node *next = nullptr, Node *prev = nullptr);
    };
    Node *start;
public:
    Liste();
    Liste(int value);
    Liste(const Liste &l);    //Kopier Konstruktor
    Liste(Liste &&l);        //Verschiebe Konstruktor
    ~Liste();
    Liste &operator=(const Liste &original);
    Liste &operator=(Liste &&l);
};

Nun scheitere ich am Kopier-Konstruktor in C++!!!
Finde das in C++ auch extrem SCHWER Gegensatz zu Java!
Vielleicht kann mir dabei ja jemand helfen?

Hier mal meine Liste.cpp:

#include <iostream>
#include "Liste.h"
using namespace std;

Liste::Node::Node(int value, Node* next, Node* prev) :
        value(value), next(next), prev(prev) {
}

void Liste::Node::setNext(Node* next) {
    this->next = next;
}

Liste::Node* Liste::Node::getNext() {
    return next;
}

int Liste::Node::getValue() {
    return value;
}

void Liste::Node::setValue(int value) {
    this->value = value;
}

void Liste::Node::printNode() {
    cout << value << endl;
}

Liste::Liste() :
        start(nullptr) {
}

Liste::Liste(int value) {
    Liste::Node *n = new Liste::Node;
    n->value = value;
    start = n;
}

//Kopier Konstruktor
Liste::Liste(const Liste &l) {
    Node *tmp = l.start;
    while (tmp != nullptr) {
        this->start = insert(tmp->value);
        tmp = tmp->next;
    }
}

//Verschiebe Konstruktor
Liste::Liste(Liste &&l) {

}

Liste::~Liste() {
  
}

Der Kopier- Konstruktor soll doch ein neues Objekt erschaffen das die selben Daten hat wie mein als Parameter übergebenes Objekt.
Ich verstehe nur gerade überhaupt nicht wie ich das so machen soll Start ist ein Pointer auf ein Object vom Typ Node. Wie bekomme ich diesen denn gefühlt?

Hab es wie oben mit einer insert Methode versucht die ich auch der Klasse zur Verfügung stelle. Doch so klappt es nicht da mekert schon der Compiler!

Hier die insert Methode:

void Liste::recInsert(Liste::Node *s, Liste::Node *n) {
    if (s->next == nullptr)
        s->next = n;
    else
        recInsert(s->next, n);
}

void Liste::insert(int value) {
    Liste::Node *n = new Liste::Node { value };
    if (start == nullptr)
        start = n;
    else
        Liste::recInsert(start, n);
}

 

[kneitzel]

Dein Problem dürfte sein:

this->start = insert(tmp->value);

Da überschreibst Du start immer mit dem aktuellen Node und das war es.

Aber Du willst doch nicht ständig start der Liste überschreiben. Die erste Lösung, die Du machen kannst (wenig optimiert) ist, dass Du einfach für jeden Node ein insert(value) aufrufst.

Wenig optimiert, da du für jedes Insert durch die Liste bis zum Ende laufen musst.

Ansonsten kannst Du auch einfach hingehen und dir den letzten eingefügten Node merken um da direkt einen neuen Node dran zu hängen. Dann sparst Du Dir dieses durchhangeln.

Und am Anfang hast Du halt ein paar Prüfungen?
- Übergebene Liste leer? -> entsprechend behanden.
- ersten Node erstellen (Hier wird dann start gesetzt)
- Schleife um restliche Nodes zu erstellen und einzuhängen.

 

[ocsme]

Aber Du willst doch nicht ständig start der Liste überschreiben. Die erste Lösung, die Du machen kannst (wenig optimiert) ist, dass Du einfach für jeden Node ein insert(value) aufrufst.

Das klappt doch nicht weil die übergebene Liste const ist. Somit kann ich durch diese Liste mit start = start->next nicht wandern. Ich stehe hier gerade mega auf dem Schlauch! Werde erst mal ein paar Minuten Pause machen.
Danke trotzdem für die schnelle Antwort!

LG

So zerstöre ich die Ausgabe wieso auch immer

Liste::Liste(const Liste &l) {
    Node *tmp = l.start;
    while(tmp != nullptr) {
            insert(tmp->value);
            tmp = tmp->next;
        }
}

 

[kneitzel]

Das klappt doch nicht weil die übergebene Liste const ist. Somit kann ich durch diese Liste mit start = start->next nicht wandern. Ich stehe hier gerade mega auf dem Schlauch! Werde erst mal ein paar Minuten Pause machen.
Danke trotzdem für die schnelle Antwort!

LG

Das ist doch überall das Gleiche. Auch in Java sollte man (meiner Meinung nach) Parameter final kennzeichnen. Und wenn man da mit einem Wert arbeiten will, dann macht man sich eine eigene Variable der man den Wert des kontanten Parts zuweist als Initialisierung. Die neue Variable ist dann änderbar.

Also bei Dir kannst Du eine

Liste::Node *current = start->next;

erstellen um dann bei der Abarbeitung immer weiter zu gehen:

current = current->next;

 

[ocsme]

@JustNobody Danke
Kann das sein das mein Einfügen schon FALSCH ist?

Hier jetzt mal das was ich gemacht habe:

Liste::Liste(const Liste &l) {
    if (l.start != nullptr) {
        Liste::Node *tmp = l.start;
        while (tmp != nullptr) {
            cout << "Test" << endl;
            insert(tmp->value);
            tmp = tmp->next;
        }
    }
}

Denn danach ist mal wieder die Liste weg.
Main.cpp

Liste l { 1 };
    l.insert(55);
    l.insert(42);
    l.insert(155);
    l.insert(142);
    l.insert(525);
    l.insert(242);
    l.print();
    printf("\n");
    Liste test {l};
    l.deleteNode(1);
    l.print();
    printf("\n");

    test.print();

Er gibt nur die erste Liste aus!

 

[kneitzel]

Also Dein insert habe ich noch nicht im Detail angesehen - das waren bisher nur ganz oberflächige Betrachtungen.

Bei dem Konstruktor: Da das Objekt erst erzeugt wird, dürfte da kein Copy-Konstruktor möglich sein. Den Fall musst Du also nicht wirklich betrachten meine ich.

Und ehe Du insert aufrufst musst Du natürlich start setzen. Ohne initialisierung ist das auf irgendwas und führt zu einem Speicherfehler. Also als erstes ein start = nullptr; in den Konstruktor und schon geht es (zumindest bei mir, aber ich musste mir ja auch viel selbst zusammen basteln )

 

[ocsme]

mhh... so klappt es!

Liste::Liste(const Liste &l) {
    start = nullptr;
    if (l.start != nullptr) {
        Liste::Node *tmp = l.start;
        while (tmp != nullptr) {
            insert(tmp->value);
            tmp = tmp->next;
        }
    }
}

man könnte auch start = new Node(); machen dann bekomme ich nur den ersten value = 0 noch mit rein
So und nun noch zu den sonderfällen!
Danach noch verschiebe Konstruktor, =operator und verschiebe zuweisung
Wenn das dann Fertig ist werde ich das ganze noch mit einem Baum versuchen! uff!!! Ich vermisse die JVM!!! Wieso gibt es so etwas ähnliches nicht für C/C++? Auf aktuellen Betriebssystem ist das zu viel Aufwand oder einfach nicht umsetzbar durch z. B. Index unterschreitung bei einem Array und der gleichen?

 

[ocsme]

Ich habe nun mein Destruktor und Kopierkonstruktor in verschiedene Methoden gelagert und damit dann den Zuweisungsoperator gemacht. Macht das Sinn oder ist das Falsch an der Stelle?

Liste& Liste::operator=(const Liste &original) {
    if (original.start != nullptr && &original != this) {
        loesche();
        erschaffe(original);
    }
    return *this;
}

void Liste::loesche() {
    Node* toDel = start;
    while (start) {
        start = start->next;
        delete toDel;
        toDel = start;
    }
}
void Liste::erschaffe(const Liste &l) {
    start = nullptr;
        if (l.start != nullptr) {
            Liste::Node *tmp = l.start;
            while (tmp != nullptr) {
                insert(tmp->value);
                tmp = tmp->next;
            }
        }
}

Liste::Liste(const Liste &l) {
    erschaffe(l);
}

Liste::~Liste() {
    loesche();
}

Wenn das so Korrekt wäre! dann würde ich noch den verschiebe Konstruktor und die Verschiebe Zuweisung versuchen und mich dann an den Baum wagen

 

[kneitzel]

Also auch für c++ gibt es extrem viel. Wenn Du z.B. einen Garbage Collector haben willst, dann könntest Du Dir selbst einen bauen. (Und es gibt da bestimmt auch Libs fertig zur Nutzung). Bezüglich des selbst bauen könnte man sich das Buch von Herbert Schild "The Art of C++" ansehen - da wird das in einem Kapitel behandelt.

Aber das ist eigentlich nicht der Weg, den man bei C++ gehen will. Aber das ist alles ein anderes Thema und muss nicht im Detail ausdiskutiert werden.

 

[ocsme]

Aber das ist eigentlich nicht der Weg, den man bei C++ gehen will. Aber das ist alles ein anderes Thema und muss nicht im Detail ausdiskutiert werden.

Danke für die Antwort. NEIN muss nicht ausdiskutiert werden! Hast mir ja auch schon eine Antwort gegeben Ja es gibt so etwas (Fertig!). Das reicht erst einmal. Kann man selber Bauen auch sehr cool! Aber wie man sieht scheitere ich an allen Ecken und Kanten noch an den Anfängen ähnlich wie bei Java!!!

LG

PS: Werde mal nach dem Buch schauen Herbert Schild "The Art of C++"

 

[kneitzel]

Ich hoffe, das mit dem nicht ausdiskutieren ist nicht missverstanden worden. Mir ging es da nur darum, dass ich den Thread nicht durch sowas aufblähen wollte und Dich auch nicht groß verwirren.

Generell solltest Du Dich erst einmal rein mit den Grundlagen beschäftigen. Das Buch von Herbert Schild fand ich gut und interessant, aber den Hinweis hätte ich mir evtl. sparen sollen, um Dich nicht damit abzulenken. Nach den Grundlagen würde ich mich lieber verstärkt auf die neuen C++ Standards stürzen.

 

[ocsme]

So hab den Baum versucht und denke bis jetzt läuft alles ganz gut.
Hatte nur 2 Stunden lang ein Problem. Meine Header Datei sah wie folgt aus:

#include "Node.h"

class Baum {
Node *root;
   
public:
    Baum();
    Baum(int value);
//    Baum(const Baum &b);
    Baum(Baum &&b);
    ~Baum();
//    Baum &operator=(const Baum &b);
//    Baum &operator=(Baum &&b);
    void insert(int value);
    void print();
private:
    void erase(); //Dekonstruktor benutzen
//    void create(const Baum &b); //Copy Konst benutzen
    Node *reInsert(Node *n, int value);
    void rePrint(Node *n);
    void reErase(Node *root);
};

Als ich dann in meiner Main.cpp folgendes versucht hatte, weil ich wieder mal keine Ausgabe bekommen habe:

Baum b (1);
    cout << b.root->value << endl;
    b.insert(22);
    b.print();

Bekomme ich direkt in der Zeile 2 eine Warnung:
Multiple markers at this line - ‘Node* Baum::root’ is private within this context - ‘int Node::value’ is private within this context
Naja wenn er nicht zugreifen kann kommt auch keine Ausgabe. Da ich 2 Stunden lang das Problem gesucht habe. Habe ich meine Node Klasse in eine neue Datei geschrieben, denn vorher war Sie auch in der Baum Klasse als Innere Klasse wie bei der Liste. Das hat das Problem nicht gelöst. Also habe ich wie in Java gelernt den Node *root Knoten in private geschrieben und einen GETTER UND SETTER eingebaut.

Die Header Datei sieht nun so aus:

#include "Node.h"

class Baum {

public:
    Baum();
    Baum(int value);
//    Baum(const Baum &b);
    Baum(Baum &&b);
    ~Baum();
//    Baum &operator=(const Baum &b);
//    Baum &operator=(Baum &&b);
    void insert(int value);
    void print();
    void setRoot(Node *root);
    Node *getRoot();
private:
    Node *root;
    void erase(); //Dekonstruktor benutzen
//    void create(const Baum &b); //Copy Konst benutzen
    Node *reInsert(Node *n, int value);
    void rePrint(Node *n);
    void reErase(Node *root);
};

WIESO KONNTE ER NICHT AUF DAS ROOT ELEMENT ZU GREIFEN? In der Liste klappt das doch auch soweit!
Was übersehe ich mal wieder bzw. wo ist der Fehler

 

[kneitzel]

In der Liste hast Du auf das Element start bestimmt nur aus der Liste selbst zugegriffen. Innerhalb der Klasse Liste kannst Du natürlich auf das Element start zugreifen.

In der Main.cpp bist Du außerhalb der Klasse Baum, daher kannst Du auf das Element root nicht zugreifen.

Die Lösung mit dem Getter ist aber nicht so gut. Du gibst ein Detail der Implementierung nach außen, das Du eigentlich kapseln möchtest.

Wenn Du (Log/Trace) Ausgaben der implementierungs-Details haben willst, dann bau diese beim Baum selbst ein.

 

[ocsme]

Die Lösung mit dem Getter ist aber nicht so gut. Du gibst ein Detail der Implementierung nach außen, das Du eigentlich kapseln möchtest.

So lernten wir das in Java. Gilt das dann auch für Java das so etwas nicht gut ist?

mhhh... Ich muss mir das ganze mal wieder genauer anschauen. Jetzt geht es aber immerhin schon mal Werde den Baum fertig machen und später das ganze wieder mit der Inneren Klasse Node versuchen

Ich schreibe ja eine Baum.h und eine Baum.cpp. Wenn ich die .h in der .cpp includeiert habe dann kann ich doch auf alles zugreifen! Verstehe einfach nicht wo da gestern der Fehler war. Weil ich jetzt alles so rum gestrickt habe schreibe ich den Baum später nochmal komplett neu und schau mir das ganze noch einmal an. Wenn nicht Poste ich den ganzen Baum hier mal dann wird es sicherlich klarer was ich mal wieder Falsch mache

 

[temi]

So lernten wir das in Java. Gilt das dann auch für Java das so etwas nicht gut ist?

Das gilt generell bei OO. Eine Klasse sollte so wenig Informationen nach außen geben wie möglich und nur soviel wie nötig.

 

[kneitzel]

Also wenn Du eine reine Entity (=Datenklasse) hast, dann ist es so, dass die Daten nach außen bekannt sind. Aber das ist dann auch kein wirklicher Objektorientierter Ansatz!

Bei einem objektorientierten Ansatz hast Du Objekte mit einem Verhalten und das Verhalten ist dann wichtig. Das Innenleben interessiert nicht!

Daher gibt es dann auch tatsächlich Tools, die den Code prüfen, und dann Warnungen auswerfen, wenn Du so komische Konstrukte hast wie someInstance.getSomething().getSomethingElse(). Wenn Du objektorientiert arbeitest, dann magst Du ein "someInstance" haben, aber dann arbeitest Du damit. Du holst dir nicht irgend was internes um darauf etwas zu machen....

Hier auch immer an die realen Objekte denken.
Du hast ein auto mit einem Verhalten und mit einer Außenschnittstelle, die Du bedienst. Du kannst beim Auto Gas geben.
Aber Du machst kein auto.getMotor().getSteuerung().setSomeValue(auto.getMotor().getSteuertung().getSomeValue() + 10);
wobei getSomeValue halt von mir aus die Benzinzufuhr war, die du erhöhen willst ....

Oder bei dem Computer: Du prüfst da doch nicht: myComputer.getMotherboard().getResistor(14).getTemperature() um zu prüfen, ob der Widerstand 14 evtl. warm geworden ist. Morgen baut jemand ein anderes Motherboard ein und der wichtige Wderstand ist nicht mehr Nr. 14 sondern Nr. 27.... Außerdem interessiert Dich doch der einzelne Widerstand nicht. Du willst wissen: Läuft das Motherboard noch in normalen Bereichen? Da ist dir egal, ob ein Widerstand oder ein IC zu heiß wird.
Und wie das Motherboard das prüft, ist dir auch egal. Ob da 100 Sensoren oder nur 3 verbaut wurden. Das ist ein Implementierungsdetail.

Was aber in der Praxis tatsächlich regelmäßig vorkommt: Man arbeitet mit Datenklassen. Das sind dann die Entities und da kommt wohl kaum eine Business Applikation drum herum. Da hat man dann halt Eigenschaften und jede Eigenschaft bekommt Getter und Setter. Equals prüft alle Eigenschaften, Hashcode bezieht alle Eigenschaft mit ein. Der Code, der da geschrieben wird, ist fast immer gleich! Und da kommt dann Lombok ins Spiel - da schreibst Du diesen ganzen Code nicht mehr. Da schreibst Du nur noch

public class MyEntity {
    private SomeType1 attribute1;
    private SomeType2 attribute2;
    private SomeType3 attribute3;
    ...
}

Und dann kommen da paar Annotations vor die Klasse wie z.B. @Data und dann wird alles von Lombok generiert. Getter, Setter, Konstruktoren (Mit Parametern, ohne Parametern), equals, hashCode, Builder so gewünscht, ....

Aber da hat man nicht wirklich einen objektorientierten Ansatz. Das ist dann auch vergleichbar mit einer Struct in C mit ein paar Funktionen drumherum...

 

[ocsme]

Danke erst einmal

So und jetzt läuft auch der Kopier- Konstruktor mit dem hatte ich gerade noch Probleme.
Kann man das ganze effizienter gestallten?

void Baum::reCreate(Node *n) {
    if (n != nullptr) {
        insert(n->getValue());
        reCreate(n->getLeft());
        reCreate(n->getRight());
    }
}

void Baum::create(const Baum& b) {
    root = nullptr;
    if(b.root != nullptr) {
        Node *neu = new Node {b.root->getValue()};
        root = neu;
        reCreate(b.root->getLeft());
        reCreate(b.root->getRight());
    }
}

 

[kneitzel]

So wie auch bei der Liste: Du fügst immer beim Baum selbst ein, so dass da der Baum durch gelaufen werden muss zum Einfügen. Aber bei der Rekursion kannst Du doch auch beim Baum mit weiter durch gehen. Dann hast Du es gleich um log(N) verbessert.

 

[ocsme]

Bei einem objektorientierten Ansatz hast Du Objekte mit einem Verhalten und das Verhalten ist dann wichtig. Das Innenleben interessiert nicht!

Also die Getter und Setter alle raus schmeißen und direkt mit den Datentypen arbeiten oder wie soll ich das verstehen?

Zu uns wurde gesagt zu jedem Dateityp in einer Klasse sollte man Getter und Setter erstellen um es so zu machen wie ich gepostet habe! Wie du schreibst der Praxis orientierte Ansatz.

Aber da hat man nicht wirklich einen objektorientierten Ansatz

Verstehe ich zwar dann überhaupt nicht doch ich frage mich gerade ob ich überhaupt verstehe was Objektorientierung heißt!
mhh... glaube ich werfe gerade wieder alles schön durcheinander

Aber bei der Rekursion kannst Du doch auch beim Baum mit weiter durch gehen.

Ja so füge ich bis jetzt jeden Knoten von vorne ein das meinst du doch sicherlich! Und ich soll dann in meinem derzeitigen Baum mit wandern? Das verstehe ich nicht ganz ich weiß ja nicht was der nächste Wert ist wo soll ich dann hin laufen Links oder Rechts

 

[ocsme]

Hallo,

wollte mal nachfragen ob mir das vielleicht nochmal jemand erklären kann.
Wie kann ich hier das Laubzeitverhalten verbessern?

Beispiel an meiner Liste:

void Liste::create(const Liste &l) {
    start = nullptr;
        if (l.start != nullptr) {
            Liste::Node *tmp = l.start;
            while (tmp != nullptr) {
                insert(tmp->value);
                tmp = tmp->next;
            }
        }
}

void Liste::recInsert(Liste::Node *s, Liste::Node *n) {
    if (s->next == nullptr)
        s->next = n;
    else
        recInsert(s->next, n);
}

void Liste::insert(int value) {
    Liste::Node *n = new Liste::Node { value };
    if (start == nullptr)
        start = n;
    else
        Liste::recInsert(start, n);
}

Mir ist bewusst das ich ja dann durch den Rekrusiven Aufbau und Abbau das X-mal mache Was Speicher und Zeit kostet.
Doch wenn ich es Rekursiv lasse weiß ich nicht wie ich es verbessern kann

Kann da jemand etwas helfen?

 

[mihe7]

Du fügst immer am Ende der Liste ein, so dass Du eine Laufzeit von O(n) hast. Wenn Du am Listenanfang einfügst, ist die Laufzeit konstant also O(1).

 

[kneitzel]

Also wenn es um das Kopieren geht, dann soll das Ergebnis ja gleich sein zur Eingabe. Daher läuft man halt entsprechend durch.

Wenn man das rekursiv machen möchte, dann ist das doch ganz trivial wie folgt (Rekursiv) zu machen:

Liste
=====
CopyNode Funktion
Parameter: Original Node
Rückgabe: Erstellter Node.
Rekursion-Abbruch: Wenn Orignal Node null, dann return null.
Aktion: Neuen Node erstellen; next = CopyNode(orgNode->next); value = ordNode->value;

Baum
====
CopyTree Funktion
Parameter: Original Tree Node
Rückgabe: Erstellter Tree Node.
Rekursions-Abbruch: OrgNode = null -> return null.
Aktionen:
Neuen Node erstellen.
value=orgNode->value
right=CopyTree(orgNode->right)
left=CopyTree(orgNode->left)

So rennst Du nicht mehrfach durch die Liste oder den Baum.

 

[ocsme]

Danke an euch zwei
Jetzt hätte ich so etwas doch komme schon nicht ganz mit der Ausgabe hin, eine zyklische Warteschlange.

Meine erste Frage dazu wäre:
muss ich die Ausgabe so umständlich machen mit der 2ten Abfrage?
(Hatte es erst Rekursiv versucht doofe Idee endlos schleife!)
Mir fällt leider nicht ein wie man das mit einer Abfrage abfangen könnte
Des weiteren verstehe ich nicht so ganz wieso ich nach meinem delete bei der Ausgabe immer noch eine Speicherzelle zurück bekomme.

void Warteschlange::output() {
    Node *hBottom = pBottom;
    Node *hTop = pTop;
    while(hBottom != hTop) {
        cout << hBottom->value << endl;
        hBottom = hBottom->next;
    }
    if(hBottom == hTop)
        cout << hTop->value << endl;
}

void Warteschlange::delete() {
    Node *end = pBottom;
    Node* toDel = end->next;
    end->next = nullptr;
    while (toDel) {
        Node *tmp = toDel->next;
        delete toDel;
        toDel = tmp;
    }
    //Warum auf nullptr setzen?
        pBottom = nullptr;
        pTop = nullptr;
}

Speichert man sich bei solchen Datenstrukturen dann eine size?
Das wäre sicherlich eleganter oder?

 

[mihe7]

eine zyklische Warteschlange.

Nur, damit wir vom gleichen reden:

   +------------------------+
   |                        |
   v next     next     next |
  e0 ----> e1 ----> e2 -----+
   ^                 ^
   bottom            top

Richtig?

muss ich die Ausgabe so umständlich machen mit der 2ten Abfrage?

Du brauchst in jedem Fall eine zweite Abfrage, aber man kann das auch umdrehen:

void Warteschlange::output() {
    if (isEmpty()) {
        return; 
    }

    Node *cur = pBottom;
    do {
        cout << cur->value << endl;
        cur = cur->next;
    } while (cur != pBottom);
}

 

[ocsme]

wieso vergesse ich so etwas immer und immer wieder

Genau das ist es Muss ich mir gleich mal noch dazu schreiben. DANKE
Ich habe jetzt auch einfach mal eine unsigned int size Variable eingeführt.
Dann sieht es bei mir wie folgt aus:

oid Warteschlange::output() {
    if (pBottom != nullptr) {
        Node *hBottom = pBottom;
        for (unsigned int i = 0; i < size; i++) {
            cout << hBottom->value << endl;
            hBottom = hBottom->next;
        }
    } else
        cerr << "Fehler Warteschlange ist leer!" << endl;
}

void Warteschlange::loesche() {
    recDelete(pBottom, size);
}

void Warteschlange::recDelete(Node *start , unsigned int count) {
    if(start != nullptr && count != 0) {
        recDelete(start->next, count--);
        delete start;
    }
}

Output könnte man dann auch noch so Rekursiv machen Wollte aber mal beides im Quellcode haben.


Eine Verständnis Frage zu diesem hier hätte ich aber noch.
Wieso wird wenn ich nach diesem delete mir bei der Ausgabe eine Speicherzelle ausgegeben? (Bei der rekursion oben nicht da ist alles schön weg!)

void Warteschlange::delete() {
    Node *end = pBottom;
    Node* toDel = end->next;
    end->next = nullptr;
    while (toDel) {
        Node *tmp = toDel->next;
        delete toDel;
        toDel = tmp;
    }
    //Warum auf nullptr setzen?
       // pBottom = nullptr;
        //pTop = nullptr;
}

 

[mihe7]

Mich wundert gerade vielmehr, warum das überhaupt funktionieren soll: delete gibt nur den Speicher frei, der Zeiger ist hinter undefiniert.

 

[ocsme]

der Zeiger ist hinter undefiniert.

muss man deswegen den Zeiger dann nochmal separat auf nullptr setzen? also pBottom und pTop.
Was ich mich nur frage wieso klappt es dann aber bei der Rekursion. Denn auch dort läuft er ganz nach hinten und gibt eins nach dem anderen den Speicher wieder frei. Wieso ist dann aber pBottom der Zeiger nicht mehr da? dann müsste ich dort doch auch noch den Zeiger auf nullptr setzen oder bin ich mal wieder so verwirrt heute?
----
Kann sein das mein Eclipse wieder spinnt also eine Fehlermeldung oder Warnung noch sonst etwas bekomme ich nicht mhh....

 

[mihe7]

muss man deswegen den Zeiger dann nochmal separat auf nullptr setzen?

Ja.

dann müsste ich dort doch auch noch den Zeiger auf nullptr setzen oder bin ich mal wieder so verwirrt heute?

Darum wundert es mich ja Ich sehe auch nicht, dass Du size korrigieren würdest.

 

[ocsme]

Ich kann leider meinen letzten Beitrag nicht bearbeiten.

@mihe7 du hattest recht.
So geht es aber nun:

void Warteschlange::delete() {
    recDelete(pBottom, size);
    size = 0;
    pBottom = pTop = nullptr;
}

void Warteschlange::recDelete(Node *start, unsigned int count) {
    if (start != nullptr && count != 0) {
        recDelete(start->next, --count);
        delete start;
    }
}

oder hab ich nun wieder etwas übersehen?

 

[mihe7]

Hm... wann/warum sollte start == nullptr gelten?

Mit dem Bild aus #24 durchgespielt:

recDelete(bottom, 3)
  start == e0: recDelete(start->next, 2)
    start == e1: recDelete(start -> next, 1)
      start == e2: recDelete(start -> next, 0)
        start == e0, aber count == 0: return
        delete e2
      delete e1
    delete e0
size = 0
bottom = top = nullptr

 

[ocsme]

Hm... wann/warum sollte start == nullptr gelten?

Dachte da an eine leere Liste. Ist aber eh Quatsch denn die Liste ist nie leer
Doch ich bin zu doof push und pop zu machen Ich verstehe die Aufgabenstellung einfach nicht.
Vielleicht habt Ihr Lust euch damit auseinander zu setzen wenn nicht muss ich morgen Fragen gehen

Aufgabenstellung:

Die Warteschlange soll basierend auf einer Zyklischen Liste arbeiten.
Ihre Zyklische Liste soll bei einem pop() den Speicher des freiwerdenden Listenelements nicht löschen.
Das Listenelement soll in der zyklischen Liste zur weiteren Nutzung verbleiben.
Dadurch werden Speicheroperationen nur nötig, wenn die Liste komplett gefüllt ist.

Die private Eigenschaft pTop speichert einen Zeiger auf das nächste freie ListElem.
Die private Eigenschaft pBottom speichert einen Zeiger auf das älteste belegte ListElem.
Einen Konstruktor, der optional die Größe der Warteschlange übergeben bekommt. Als minimaler Wert wird die Größe 1 akzeptiert. Wird keine Größe angegeben, wird eine Warteschlange mit 4 Elementen angelegt.
Eine private Methode extend(), die Ihre Warteschlange um ein weiteres ListenElem erweitert. An einfachsten nutzen Sie extend() so, dass immer mindestens ein freies Element existiert.
Die Methode push(), um einen Int-Wert in die Warteschlange einzufügen.
Die Methode pop(), um den ältesten gespeicherten Wert zurückzugeben.

Mal mein Anfang bis jetzt:

#include <iostream>
#include "Warteschlange.h"

using namespace std;

Warteschlange::Node::Node(int value, Node* next) {
    this->value = value;
    this->next = next;
}

void Warteschlange::Node::setValue(int value) {
    this->value = value;
}

void Warteschlange::Node::setNext(Node* next) {
    this->next = next;
}

int Warteschlange::Node::getValue() {
    return value;
}

Warteschlange::Node* Warteschlange::Node::getNext() {
    return next;
}

Warteschlange::Warteschlange(unsigned int value) {
    if (value == 0)
        value = 4;
    for (unsigned int i = 0; i < value; i++)
        extends();
}

void Warteschlange::push(int value) {

}

int Warteschlange::pop() {
    
    return 0;
}

void Warteschlange::extends() {
    Node *node = new Node;
    if (node == nullptr)
        return;
    if (pTop == nullptr) {
        pTop = pBottom = node;
        size++;
    } else {
        pTop->next = node;
        pTop = node;
        pTop->next = pBottom;
        size++;
    }
}

void Warteschlange::output() {
//  @mihe7
    if (isEmpty()) {
        cerr << "Fehler Warteschlange ist leer!" << endl;
        return;
    }
    Node *cur = pBottom;
    do {
        cout << cur->value << endl;
        cur = cur->next;
    } while (cur != pBottom);
}

void Warteschlange::loesche() {
    recDelete(pBottom, size);
    size = 0;
    pBottom = pTop = nullptr;
}

void Warteschlange::recDelete(Node *start, unsigned int count) {
    if (count != 0) {
        recDelete(start->next, --count);
        delete start;
    }
}

int Warteschlange::isEmpty() {
    return pBottom == nullptr ? 1 : 0;
}

Bei mir Zeigt pTop nicht auf das nächste Freie Element sondern auf das letzte freie Element.
Soll ich das ganze nun wirklich ändern? Dachte erst an eine 2te INT - Variable (added z. B.) um fest zu halten wie viele Elemente in der Warteschlange sind.
Dann dachte ich noch okay dann rufe ich den Konstruktor eben so auf:

Warteschlange::Warteschlange(unsigned int value) {
    if (value == 0)
        value = 4;
    for (unsigned int i = 0; i < value; i++)
        extends();
        // hier wurde etwas geändert
    pTop = pBottom->next;
}

Nun steht pTop auf dem ersten freien Element.
Doch ich bekomme weder pop() noch push() zufriedenstellend hin
Vor allem weiß ich auch nicht ob das Quatsch ist was ich da versuche
ufff...

 

[mihe7]

Vor allem weiß ich auch nicht ob das Quatsch ist was ich da versuche

OK, mit der Aufgabenschreibung ergeben sich neue Erkenntnisse...

Und wieder das Bild aus #24: das zeigt eine Warteschlange mit einer Kapazität von 3 Elementen, wovon 2 belegt sind.

bottom zeigt auf das älteste Element, d. h. e0 enthält einen Wert. Ebenso enthält e1 einen Wert und top zeigt auf e2, das nächste freie Element.

Was muss bei einem pop passieren?
1. wenn top == bottom gilt, dann ist die Liste leer, dann kann also nichts zurückgegeben werden.
2. ansonsten gilt die Invariante, dass top auf das nächste, leere Element zeigen muss. D. h. nach dem pop() muss top auf das Vorgängerelement zeigen, das dann leer ist und dessen ursprünglicher Wert zurückgegeben werden muss.

Im Bild würde also pop() dazu führen, dass der Wert von e1 zurückgegeben wird, top auf e1 zeigt.

Was muss bei einem push passieren?

1. das Element, auf das top zeigt, ist das nächste, freie Element. Dieses muss also den Wert aufnehmen.
2. wenn top->next == bottom gilt, kann top nicht einfach auf top->next vorrücken, dann muss vorher die Liste erweitert werden.
3. abschließend top = top->next

 

[ocsme]

Was ich immer noch nicht verstehe ist der Bottom.
Soll Bottom dann ein Initiallwert bekommen und eigentlich nie befüllt werden können?
Denn anders müsste man bei einem push(int a) ja noch den Bottom zu erst befüllen. Doch woher will ich denn wissen das Bottom befüllt wurde? Es steht ja schon ein int wert drin. Könnte ja auch sagen push(0).
Wenn Bottom nur der Anfangszeiger der Warteschlange ist nicht mehr oder weniger würde das meiner Sicht nach mehr Sinn ergeben. Dann könnte man den ersten Wert an Top speichern und Top eins wandern lassen. Sobald dann Top == Bottom ist beim Einfügen weiß ich jetzt muss ich die Schlange um eines erweitern.

Vielleicht Interpretiere ich hier auch einfach nur viel zu viel rein ? oder ich verstehe es nicht

 

[kneitzel]

Ich versuche es noch einmal etwas von Anfang an.

Du hast eine zyklische Warteschlange. Das bedeutet, dass alle Elemente zusammen einen Kreis bilden. Das Ende zeigt wieder auf den Anfang.

Also wie nehmen jetzt einfach eine Kette. Und Du hast Kettenglieder. Du hast ein Kettenglied als Anfang markiert. Wenn Du jetzt einmal durch alle Kettenglieder durch gehen willst, dann startest du beim Anfang und gehst so lange ein Kettenglied weiter, bis Du wieder am Anfang angekommen bist.

Nun ist es aber so umständlich, ständig Kettenglieder heraus zu nehmen. (Wir stellen uns einfach vor, dass der "Inhalt" da etwas drauf geschriebenes ist.) Da wir aber immer an einer Stelle die Glieder heraus nehmen würden, gehen wir jetzt einfach hin und markieren sozusagen den Anfang der leeren Kettenglieder ....

Also am Anfang ist es dann voll:
(*1)->(2)->(3)->(4)~ Dabei ist ~ jetzt sozusagen die Verbindung zum Anfang zurück also das soll jetzt die Kurzform für das sein:

+->(*1)->(2)->(3)->(4)-+
+-------------------------+

Und das Element mit dem * soll das Start Element sein.

Wenn nun die (1) geht, dann müsste ich das Kettenglied entfernen:
+->(*2)->(3)->(4)~
Das will ich aber nicht, um diese blöde Arbeit zu sparen.
Also lasse ich das Element einfach drinnen und dann habe ich:
+->(*2)->(3)->(4)->('1')~

Du erkennst: Das Element mit der 1 ist noch da - daher habe ich da die 1 in '1' gesetzt.
Aber wenn ich da nun durch gehe, dann sieht es so aus, als wäre die 1 noch in der Warteliste. Also braucht man nun noch einen Zweiten Zeiger, der den Start der leeren Element anzeigt. Das mache ich mal mit einem &:
+->(*2)->(3)->(4)->(&'1')~

Nun kann auch noch die 2 dran kommen:
+->(*3)->(4)->(&'1')->('2')~

Nun auch noch die 3 und 4:
+->(*&'1')->('2')->('3')->('4')->~

Was Du nun erkennst: * und & sind beim gleichen Element. Und die Liste ist leer. Das ist doch ein Zusammenhang

Nehmen wir noch einmal den Schritt, ehe die 3 und 4 dran gekommen sind:
+->(*3)->(4)->(&'1')->('2')~
Was, wenn die 5 jetzt noch kommen würde?
& zeigt ja auf das erste freie Feld. Also nutzen wir das doch und erhalten dann:
+->(*3)->(4)->(5)->(&'2')~
(& musste natürlich eins weiter rücken ... Soll ja auf das nächste freie Kettenglied zeigen ....)

 

[ocsme]

Bekomme es nicht hin.

void Warteschlange::push(int value) {
    pTop->value = value;
    if(pTop->next == pBottom)
        extends();
    pTop = pTop->next;
}

void Warteschlange::extends() {
    Node *node = new Node;
    if (node == nullptr) {
        cerr << "Fehler kein Speicherplatz" << endl;
        return;
    }
    if (pTop == nullptr) {
        pTop = pBottom = node;
        size++;
    } else {
        pTop->next = node;
        pTop = node;
        pTop->next = pBottom;
        size++;
    }
}

In Konstruktor setze ich mal pTop = pBottom damit ich auch an das erste Element komme!

Warteschlange::Warteschlange(unsigned int value) {
    if (value == 0)
        value = 4;
    for (unsigned int i = 0; i < value; i++) {
        extends();
    }
    pTop = pBottom;

}

Wenn ich das so versuche überschreibt er mir die Element immer nur!

 

[ocsme]

Aufgezeichnet und Fehler gefunden !!!

void Warteschlange::push(int value) {
    pTop->value = value;
    if(pTop->next == pBottom) {
        extends();    return;
    }

    pTop = pTop->next;
}

Bin immer 2x gewandert! mit return springe ich jetzt einfach raus

Bei pop() klämmt es aber immer noch. Soll ich da jetzt mit pBottom arbeiten? oder fasse ich den pBottom zeiger nie an? denn in meinem pBottom ist derzeit ein Tmp gespeichert, so zu sagen. Der hat den Wert 0 der aber gar nicht eingefügt wurde.
Dann müsste ich mit pBottom erst einmal eins weiter laufen diesen Wert zurück geben und was soll dan mit pTop passieren?
So gesehen würde Top dann wieder auf Bottom zeigen und später müsste Top wieder ganz nach hinten wandern! Ich zeichne es mir auf und verstehe gar nichts mehr

 

[ocsme]

Was muss bei einem pop passieren?
1. wenn top == bottom gilt, dann ist die Liste leer, dann kann also nichts zurückgegeben werden.
2. ansonsten gilt die Invariante, dass top auf das nächste, leere Element zeigen muss. D. h. nach dem pop() muss top auf das Vorgängerelement zeigen, das dann leer ist und dessen ursprünglicher Wert zurückgegeben werden muss.

Im Bild würde also pop() dazu führen, dass der Wert von e1 zurückgegeben wird, top auf e1 zeigt.

Was muss bei einem push passieren?

1. das Element, auf das top zeigt, ist das nächste, freie Element. Dieses muss also den Wert aufnehmen.
2. wenn top->next == bottom gilt, kann top nicht einfach auf top->next vorrücken, dann muss vorher die Liste erweitert werden.
3. abschließend top = top->next

Fehlen mir dafür nicht 2 Zeiger?
Ein Zeiger für den Start und einen für das Ende der Queue?

Egal wie ich es mir aufzeichne. Wenn push(x) Funktioniert, klappt pop() nicht und umgekehrt!

Wenn ich mit push 4 Elemente einfüge steht Top auf dem 5ten Element das derzeit Freie Element. Wenn ich nun 1x pop aufrufe würde Top zu Bottom->next wandern dann den Wert zurück geben und auf diesem Element stehen bleiben? <- Dann füge ich aber an der ersten Stelle ein, somit würde sich ein Kunde an der Kasse vor drängeln! Selbst wenn ich mir den Top speichere und wieder ans ende Setze darf der Bottom nicht wandern sonst bekomme ich später durch extends() speicher Probleme! Dann befinden sich noch Knoten im Programm die nicht referenziert werden.

Leider weiß ich auch nicht ob wir noch andere Zeiger einfügen dürfen in der Aufgabenstellung steht nur was von 2 Zeigern.
Damit bekomme ich das nicht hin.
Wo ist der Denkfehler?

 

[mihe7]

Wo ist der Denkfehler?

Zuerst mal bei mir: ich beschreibe die ganze Zeit einen Stack und keine Queue...

Beim push ändert sich dadurch nichts aber natürlich beim pop: hier muss das bottom in Richtung top wandern und nicht umgekehrt.

 

[ocsme]

Zuerst mal bei mir: ich beschreibe die ganze Zeit einen Stack und keine Queue...

Kein Problem. Wir sind alle NUR MENSCHEN und Menschen machen FEHLER

Beim push ändert sich dadurch nichts aber natürlich beim pop: hier muss das bottom in Richtung top wandern und nicht umgekehrt.

Moment dann habe ich aber immer noch ein Denkfehler!
Wenn das Bottom wandert verliere ich doch die Referenz auf das erste Element. Sobald man nun nach pop wieder push macht und die Liste vergrößert werden muss hängt dieses Element hinter Bottom und nicht mehr hinter dem Anfang. Somit hätte man doch Speicherprobleme.
Oder hab ich immer noch einen DENKFEHLER!

Werde es mir gleich nochmal auf ein Sauberes Papier aufmalen, erst mal etwas zu Essen holen vielleicht arbeitet dann das Hirn wieder besser

 

[mihe7]

Wenn das Bottom wandert verliere ich doch die Referenz auf das erste Element.

Eine Queue ist ja ein FIFO. Was als erstes reinkam, kommt auch als erstes wieder raus.

Wenn das erste Element rauskommt, ist das nächste Element das neue erste Und nachdem die Queue zirkulär ist, gehen auch keine Referenzen verloren.

 

[ocsme]

Egal wie ich es mache in meiner Konstruktion geht der Zeiger dann immer verloren bzw. die Elemente!
Ich bekomme es nicht hin ufff... !!!

Ich poste mal meinen Code nochmal vielleicht könnt ihr den mal überfliegen und mir erklären wo es hackt
Konstruktor:

Warteschlange::Warteschlange(unsigned int value) {
    if (value == 0)
        value = 4;
    for (unsigned int i = 0; i < value; i++) {
        extends();
    }
    pTop = pBottom->next;
}

extends:

void Warteschlange::extends() {
    Node *node = new Node {-1};
    if (node == nullptr) {
        cerr << "Fehler kein Speicherplatz" << endl;
        return;
    }
    if (pTop == nullptr) {
        pTop = pBottom = node;
        size++;
    } else {
        pTop->next = node;
        pTop = node;
        pTop->next = pBottom;
        size++;
    }
}

push:

void Warteschlange::push(int value) {
    if(pTop->next != pBottom) {
        pTop->value = value;
        pTop = pTop->next;
    }
    else {
        pTop->value = value;
        extends();
    }

pop:

int Warteschlange::pop() {
    if(pBottom != pTop) {
        pBottom = pBottom->next;
        return pBottom->value;
    }
    else {
        cerr << "Fehler pop() Warteschlange leer!" << endl;
        return -1;
    }
}

Ich könnte ja einfach zwei Zeiger noch nehmen Anfang und Ende! Dann sollte es einfacherer werden Und auch für mich möglich. Leider weiß ich aber nicht ob wir das dürfen.

 

[ocsme]

Sauber wenn ich die Liste mit einem Element initialisiere fällt das Programm bei so ziemlich allen Methoden auf eine nullptr Exception oder etwas anderes
Auch mit dem Anfang und Ende Zeiger bekomme ich es nicht hin!
Dabei belasse ich es jetzt erst einmal werd das ganze neu überdenken müssen und von vorne Anfangen.