Verkette Liste

guenne

Aso ist das. Was heist leaken ? Und was würde mir hier jetzt aus der misere helfen ? Wie erstell ich den persistente Objekte? Eine Möglichkeit wäre ja die Allocation in die Methode selbst zu verlegen, aber ich muss doch auch irgendwie auch so, dynamisch Objekte erzeugen können die auch nach verlassen eines Blocks noch persistent sind.

€dit: Aso, oder müsste ich einfach den Zeiger an Add übergeben, anstelle der
Refrenz der lokalen Variable. Hatte mich schon gefragt, wo der unterschied ist
zwischen einer Referenz oder einem Zeiger als Parameter.

€dit: Ah nu klappts, nachdem ich mit dem Zeiger arbeite in der Methode add. Komme von der Java-Sparte da sind ja alles Referenzen, von daher die kleine Verwirrung meinerseite Eine Frage bleibt dennoch, was meintest du mit leaken.

MFK

guenne schrieb:

Aso, oder müsste ich einfach den Zeiger an Add übergeben, anstelle der
Refrenz der lokalen Variable. Hatte mich schon gefragt, wo der unterschied ist
zwischen einer Referenz oder einem Zeiger als Parameter.

Nein, das ist nicht das Problem.

Mit

Liste::Node n

erzeugst du nicht nur einen Objektverweis wie in Java, sondern ein komplettes Objekt. Dieses Objekt ist eine Kopie des Objekts, das du gleich darüber mit new erzeugt hast. Du hast zu diesem Zeitpunkt also bereits 2 Nodes. Und du speicherst die Adresse des zweiten, lokalen Objekts. Ob du das jetzt als Referenz oder Zeiger übergibst, ist egal. Entscheidend ist, welches Objekt du übergibst.

guenne schrieb:

Eine Frage bleibt dennoch, was meintest du mit leaken.

Das heißt, du erstellst ein Objekt, zerstörst es aber nicht wieder. Im Gegensatz zu Java hat C++ keine Garbage Collector, der nicht mehr benötigte Objekte automatisch wieder löscht.

Zumindest in der ursprünglichen Version hättest du auch keine Möglichkeit gehabt, die mit new erzeugten Objekte wieder zu löschen, weil die Zeiger darauf unwiederbringlich weg waren.

guenne

Danke für deine Hilfe du machst mir gerade grundlegende Sachen wieder klar.
Nur mal zur vervollständigung.
Unten stehender Code wäre so richtig und mal abgesehn davon das die lokale Varibale n nun völlig überflüssig ist, würde n nun aber nicht mehr geleakt werden, sondern ordnungsgemäs gelöscht. Korrigier mich wenn ich falsch liege.
Ich müsste dann auch noch einen Destruktor schreiben der alle Knoten eigenständig löscht, nicht wahr?

for(int i = 0; i<5; i++)
    {
        Liste::Node * pnode = new Liste::Node(i);
        Liste::Node n = *pnode;
        l.add(*pnode,l);
        delete n;
    }

MFK

guenne schrieb:

Unten stehender Code wäre so richtig und mal abgesehn davon das die lokale Varibale n nun völlig überflüssig ist, würde n nun aber nicht mehr geleakt werden, sondern ordnungsgemäs gelöscht.

Nein, das lässt sich nicht kompilieren. Du kannst delete nicht mit n aufrufen, n ist kein Zeiger, und auch &n wäre falsch, weil dieses Objekt nicht mit new angelegt wurde. Du könntest delete für pnode aufrufen. Aber dann hättest du wieder das Problem, dass du ungültige Zeiger in deiner Liste hast.

guenne schrieb:

Ich müsste dann auch noch einen Destruktor schreiben der alle Knoten eigenständig löscht, nicht wahr?

Du solltest dir zunächst einmal darüber klar werden, ob deine Liste die Objekte besitzen soll, oder nicht. Davon hängt ab, wer für's Löschen zuständig ist.

volkard

Du hat ein paar ungewöhnliche Tricks benutzt. In der Annahme, daß der mit &(l.head) Dir recht wichtig ist, habe ich ihn gelassen und fortgeführt, bis es funktioniert. Außerdem hast Du dadurch einen Zeiger auf Zeiger, das ist doch genau das, was Du trainieren wolltest?
Denk dran, daß Du nie l.add(n,l); nebst { l.foo } brauchst, denn l. macht schon, daß &l übergeben wird als this, also l.add(n); nebst { this->foo } reicht.

#include <iostream>
using namespace std;

class Liste
{
public:
    struct Node
    {
        int dat;
        Node * next;
        Node(int x)
                :dat(x)
                ,next(0)
        {
        }
    };

    Node * head;
//    Node * tail;
    Liste()
            :head(0)
    {
    }

    void add(Node* n)
    {
        if (head == 0)
        {
            head = n;
            return;
        }
        Node ** tmp = &(head->next);
        while (*tmp != 0)
            tmp = &((*tmp)->next);
        (*tmp)=n;
    }
    void show()
    {
        Node * tmp = head;
        while ( tmp != 0 )
        {
            cout << tmp->dat;
            tmp = tmp->next;
        }
    }
};

int main()
{
    Liste l;
    for (int i = 0; i<5; i++)
    {
        Liste::Node * pnode = new Liste::Node(i);
        l.add(pnode);
    }

    l.show();
    cout << "DA WILL ER NICHT TERMINIEREN !?! GIBTS DOCH NICHT";
    int a;
    cin >> a;

    return (0);
}

guenne

Ah okay. Das mit der dynamischen Objekterzeugung und wie ich den dafür reservierten Speicher verwalte muss ich mir wohl mal durchlesen. Danke für deine Hilfe nochmal und deine Geduld

€dit: @ Volkard: Das dass übergebn der Liste unnötig ist, ist mir nachdem ich das Grundgerüst implementiert hatte auch aufgefallen, aber war mir dann nicht so wichtig, als das ich es unbedingt geädnert hätte ; )

"ungewöhnliche Tricks", hehe, ich muss mich wie erstmal wieder in einigen C++ Code einlesen

volkard

Hier ein minimalistisches Besipiel:

#include <iostream>
using namespace std;

template<typename T>
class Liste{
private:
	struct Knoten{
		T daten;
		Knoten* next;
                Knoten(T& t)
                :daten(t)
                {
                }
	};
	Knoten* anfang;
public:
	Liste(){
		anfang=0;
	}
	~Liste(){
		while(!istLeer())
			loescheOberstesElement();
	}
	bool istLeer(){
		return anfang==0;
	}
	void vorneEinfuegen(T& neuerWert){
		//neuen Knoten erzeugen und Adresse merken in lokaler
		//Variable namens nk
		Knoten* nk;
		nk=new Knoten(neuerWert);
		//Adresse vom ersten Element in das Next-Feld vom neuen
		//Knoten schreiben
		nk->next=anfang;
		//Listenanfang setzen auf die Adresse des neuen Knotens
		anfang=nk;
	}
	T const& gibOberstesElement(){
		return anfang->daten;
	}
	void loescheOberstesElement(){
		//Die Adresse des zweiten Elements merken in lokaler Variablen
		//namens hugo
		Knoten* hugo;
		hugo=anfang->next;
		//Löschen des ersten Elements
		delete anfang;
		//Hugo nehmen und in anfang reinschreiben
		anfang=hugo;
	}
};

int main()
{
    Liste<int> l;
    for (int i = 0; i<5; i++)
    {
        l.vorneEinfuegen(i);
    }

    while(!l.istLeer())
    {
    	cout<<l.gibOberstesElement()<<'\n';
    	l.loescheOberstesElement();
    }

    int a;
    cin >> a;

    return (0);
}

guenne

Danke für die Mühe Volkard. War gut nochmal ein Beispiel von jemanden zu sehn, der weis wie man C++ codet. Ausserdem fand ich den Hugo amüsant ; )

€dit: Wo ich schonmal dabei bin. Was ist den der unterschied ob ich nu eine Referenz oder einen Zeiger an eine Funktion übergebe?

Bei beiden kann ich auf das Objekt zugreifen und auf die Adresse. Naja mal abgesehn von Funktionszeigern ist das doch stets das gleiche.
Oder wann verwendet man stets Zeiger?

volkard

guenne schrieb:

€dit: Wo ich schonmal dabei bin. Was ist den der unterschied ob ich nu eine Referenz oder einen Zeiger an eine Funktion übergebe?

Bei beiden kann ich auf das Objekt zugreifen und auf die Adresse. Naja mal abgesehn von Funktionszeigern ist das doch stets das gleiche.

Ja, ist gleich.
AAAber

Liste::Node * pnode = new Liste::Node(i); 
        Liste::Node n = *pnode; //Patsch
        l.add(n,l);

Du hast in der Patsch-Zeile eine Kopie angelegt!
Richtig wäre

Liste::Node * pnode = new Liste::Node(i); 
        Liste::Node & n = *pnode; //Patsch
        l.add(n,l);

guenne schrieb:

Oder wann verwendet man stets Zeiger?

Wenn auch NULL drin stehen kann.
Also

struct Knoten{
        T daten;
        Knoten& next;

kann nicht gehen, weil next wenigstens beim letzen Knoten NULL sein muß. NULL kann in einer Referenz per Definition nicht drinstehen.

Ich halte es darüberhinaus so, daß ich Referenzen vorwiegend nur da benutze, wo es auch eine Kopie machen würde, nur daß die Übergabe per Referenz einen Tick schneller ist.

guenne

Danke schön.