3. list - zeiger auf list.begin()

list - zeiger auf list.begin()

  • N

    Tag auch, bin noch relativ neu in c++, wollte aber die, im unterricht gegebene, aufgabenstellung mit dieser Sprache zu lösen versuchen.
    Ersteinmal etwas zur Aufgabenstellung:
    Es soll eine art binärer Suchbaum erstellt werden.
    Jedes Element ist eine Struktur nach folgendem Muster:

    struct Node{
	int wert;
	Node* left;
	Node* right;
	Node* parent;

	Node(){
		wert  = null;
		left  = null;
		right = null;
		parent= null;
	}

};

    parent zeigt auf ein übergeordnetes Element, left auf ein element mit einem kleineren wert und right auf ein element mit einem größeren wert. für left und right ist das element das auf diese zeigt, das parent.

    In einer weiteren Klasse sollen nun Funktionen wie search, insert und delete erstellt werden. search ist ansich fertig, es fehlt nur ein insert um search auch testen zu können, aber genau beim insert komme ich nicht weiter.

    Die Klasse sieht so aus:

    class BinaryTree{
private:
	list<Node> nodes;
	Node* nodPos;

public:

	BinaryTree(){
		Node nodNull;
		nodPos = &nodNull;
	}

	bool insert(int newValue){

		if(nodes.size() == 0){
			Node nodRoot;
			nodRoot.wert = newValue;
			nodes.push_back(nodRoot);
			nodPos = nodes.begin();
		}
		else{

		}
		return true;
	}
};

    Mithilfe von List wollte ich eine Menge von Node-Objekten lagern.
    nodPos ist ein Zeiger der auf die Adresse des gerade benutzen Nodes zeigt sein.
    Das erste Node das erstellt wird, ist ein Root Node mit einem null-Node als Parent. Auf dieses Node sollte nodPos zu beginn zeigen, allerdings funktioniert das ganze nicht so recht wie ich es mir vorgestellt habe. nodes.beginn() liefert doch theoretisch einen Zeiger zum ersten Node, oder nicht? Jedenfalls wollte ich, das nodPos auf das eben erstellte Objekt in der Liste zeigt.
    Es geht zwar, dass ich einem Node Objekt *nodes.begin() zuweise, aber wenn ich dann einen Zeiger auf dieses neue Node Objekt setze, zeigt es auf eine anderes Element als auf das in der Liste, oder?

    Folgende Fehlermeldung wird für die Zeile nodPos = nodes.begin(); ausgegeben:

    error C2440: '=': 'std::list<_Ty>::_Iterator<_Secure_validation>' kann nicht in 'Node *' konvertiert werden

    Da ich noch etwas Probleme mit Zeigern habe habe ich auch versucht, ein * oder & vor nodes.begin() zu setzen, hat aber auch nicht geholfen.

    0
  • B

    Hallo Nudel

    Nodes.begin(); liefert keinen Zeiger, sondern einen Iterator.
    Den musst du erst dereferenzieren um dein Objekt zu erhalten.

    (*nodes.begin());

    nun hast du ein Node-Objekt.
    Willst du einen Zeiger darauf, musst du die Adresse übergeben mit &

    nodPos=&(*nodes.begin());

    Übrigens fügst du mit push_back() am Ende ⚠ ein, also bräuchtest du nodes.end()-1 für das zuletzt eingefügte Element.

    (Hoffe das stimmt so, bin selber noch nicht so bewandert)

    0
  • S

    Das Ganze ist ohnehin fürn Arsch 😉 .
    Es ist ganz bestimmt nicht Sinn und Zweck eines Binärbaumes die Knoten in ner Liste zu speichern. :p

    Gruss Spacelord

    0
  • N

    Danke dir, hat funktioniert. 🙂

    @Spacelord
    Kann sein, kenn mich mit Binärbäumen nicht nicht besonders gut aus. ^^
    Nur in was sollte ich sonst beliebig viele Node-Objekte speichern? Wenn ich das ganze als vector speichere bzw als Array, scheint die Aufgabenstellung nicht mehr besonders viel Sinn zu machen, da sich alles leicht über den index anstatt den Node Attributen ansprechen lässt.

    0
  • B

    Hmm
    Eigentlich brauchst du nur den Root zu speichern, und von da kannst du den Baum hoch klettern zu jedem einzelnen Node.
    Ich dachte das wär der Sinn von Bäumen? Spacelord was meinst du?

    [edit]typos[/edit]

    0
  • S

    Ein Baum ist eine rekursive Struktur.
    Also ist ein Baum vom Prinzip her erstmal nur der Kopfknoten.
    Dieser verweist dann wiederum auf seine Kinder(Teilbäume) und diese wieder auf ihre Kinder usw. usw.
    Das Ganze geht solange bis die Teilbäume nicht mehr auf weitere Knoten verweisen.Dann spricht man von einem Blatt.
    Also im Prinzip brauchst du ne Klasse/Struktur Node und ne Klasse Tree welche als Attribut für den Kopfknoten ein Exemplar der Klasse Node enthält.
    Darauf musst du alles aufbauen.
    Wenn du ne Liste zur Speicherung der Knoten benutzt(was sicherlich auch geht) dann kannst du nicht mehr die Laufzeiteigenschaften einhalten die einem Binärbaum im Allgemeinen zugesprochen werden.
    Die genaue Implementierung hängt von den wirklich gestellten Anforderungen ab.
    Brauchst du Iteratoren? Soll Node ne private innere Klasse von Tree sein usw.

    Schau mal hier:
    http://www.netzmafia.de/skripten/ad/ad10.html
    unter Baumstrukturen um erstmal hinter den generellen Gedanken zu kommen.
    Das Ganze ist in C,macht aber vom Prinzip her keinen Unterschied.
    Es geht anscheinend ja erstmal darum die Datenstruktur ansich und das rekursive Prinzip dahinter zu verstehen.

    Gruss Spacelord

    0
  • N

    Ich glaub ich hab verstanden, was ihr meint. Ich wollte alle Elemente die später im Baum existieren irgendwo abspeichern, hab nicht daran gedacht, dass man den Baum garnicht in einer liste speichern muss sondern einfach durch node.left/right oder parent = new Node(); erstellen kann.
    Die folgen kurzsichtigen drauflosprogrammierens. 😃

    EDIT:
    Danke für die zusätzlichen informationen zu Bäumen, spacelord.

    0
Anmelden zum Antworten