Suchen in Vector von eigener Struktur richtig?



  • Moin,

    ich befasse mich seit laengerer Zeit zum ersten Mal wieder mit CPP, was ich das letzte Mal vor zwei Jahren im Studium gelernt habe. Bitte seht mir also "Anfaenger-Fragen" nach 😉

    Meine Idee ist, meinen Wissenstand aufzufrischen und zu erweitern, indem ich mir ein Projekt suche und einfach mal drauflos programmiere. Irgendwann ist das Ziel des aktuellen Projektes, das Brettspiel Scotland Yard zu "digitalisieren" und letzendlich auch einen Computergesteuerten Gegenspieler zu implementieren. Das dauert aber noch eine Weile, ich habe heute erst mit den Grundstrukturen angefangen.

    Das Spielfeld moechte ich als eine Art Graph modellieren, also als eine Menge von Knoten und Kanten. In jedem Knoten soll eine Nummer gespeichert werden und eine Liste (da habe ich mich fuer die Vector Struktur entschieden, weil schon bekannt, bin aber gerne offen fuer neues) mit erreichbaren Knoten. Nun moechte ich eine Suchfunktion implementieren, die entscheidet, ob ein Knoten mit einem anderen verbunden ist. Leider scheint entweder diese nicht zu funktionieren, oder meine add-Funktion im nun folgenden Beispiel:

    class Knoten 
    {
    	private:
    		int nummer;
    		vector<Knoten> verbunden;
            //Block mit public Funktionen. Einige Ausschnitte:
            public:
                    Knoten(int num, vector<Knoten> knot) //Konstruktor
    		{
    			nummer = num;
    			verbunden = knot;
    		}
    		int add(Knoten k) { //fuegt k zu verbunden hinzu
    			verbunden.push_back(k);
    			return 0;
    		}
    
    }
    bool contains(vector<Knoten> l, Knoten k) { // Hilfe fuer ist_verbunden
    	auto f = find(l.begin(), l.end(), k);
    	if (f != l.end()) {
    		return true;
    	}
    	else {
    		return false;
    	}
    }
    
    bool Knoten::ist_verbunden(Knoten k) { 
    	if (contains(verbunden,k)) {
    		return true;
    	}
    	else
    		return false;
    }
    int main()
    {
    	vector<Knoten> v;
    	Knoten K = Knoten(1, v);
    	Knoten K2 = Knoten(2, v); 
    	K.add(K2);
    	K2.add(K);
    	if (K.ist_verbunden(K2)) {
    		cout << "jo"<< endl;
    	}
    	else {
    		cout << "nope" << endl; 
    	}
    	
    	return 0;
    }
    
    

    Es wird "nope" ausgegeben, ich muss also einen Fehler gemacht haben.

    Ich hoffe ich habe mich einigermassen an die Post-Richtlinien gehalten, falls nicht bitte entschuldigt, ich bessere das gerne nach.

    Ansonsten schonmal danke im Vorraus 🙂

    VG,
    Teedeekay



  • Das größte Problem bei dir dürfte sein, dass jeder Knoten einen Menge von Knoten enthält. Das ist nicht in deinem Sinne. Stattdessen sollte jeder Knoten eine Menge von Verweisen auf andere Knoten enthalten. Ansonsten wirst du keine Verbindungen bauen können.

    Du hast ja eine Menge von Knotenverbindungen - da bietet sich auch ein std::set an.

    Außerdem ist dies hier fragwürdig:

            vector<Knoten> v;
    	Knoten K = Knoten(1, v);
    	Knoten K2 = Knoten(2, v); 
    

    Deine Knoten kopieren jeweils den vector v. Der Knotenkonstruktor sollte keinen vector an Knoten übergeben bekommen - by default ist ein Knoten dann nicht verbunden. Du musst die Verbindugen eh später setzen, weil die Knoten ja nacheinander erzeugt werden und die Verbindung erst möglich ist, wenn die Knoten fertig sind. Außer du benennst sie mit einer ID und speicherst in jedem Knoten nur die IDs der verbundenen Knoten. Wäre vielleicht die bessere Lösung. Dann nimmst du einen vector<Knoten>, wo alle Knoten drin sind und z.B. K1(1, {{2, TransportMode::Taxi}, {3, TransportMode::Bus}}) usw. Andererseits hast du ja einen ungerichteten Graphen. D.h. wenn du erst alle Knoten erzeugst, dann kannst du in der make_connection-Funktion gleich automatisch den Rückweg erzeugen.

    (Bein nächsten Post bitte darauf achten, dass der gepostete Code auch compiliert)



  • @wob sagte in Suchen in Vector von eigener Struktur richtig?:

    Das größte Problem bei dir dürfte sein, dass jeder Knoten einen Menge von Knoten enthält. Das ist nicht in deinem Sinne. Stattdessen sollte jeder Knoten eine Menge von Verweisen auf andere Knoten enthalten. Ansonsten wirst du keine Verbindungen bauen können.

    Und noch etwas genauer die Erklärung, warum 'find' nichts findet:

    K.add(K2);   // K2 hat leeren Knoten-vector und wird nach K kopiert
    K2.add(K);  // K2 kriegt jetzt einen Knoten; der in K bleibt leer (weil Kopie)
    

    Das 'find' ist dann später false, wegen derunterschiedlichen vectors.



  • Die C++ Container speichern Kopien von Objekten. D.h. bei K.add(K2) wird eine Kopie von K2 in K gespeichert. Danach modifizierst du K2 mit K2.add(K). Die Kopie in K bleibt aber so wie sie ist. D.h. die K2 und die Kopie von K2 in D sind nicht mehr gleich.
    (Wobei du uns einen wichtigen Teil unterschlagen hast, nämlich den operator == von Knoten - ich gehe einfach mal davon aus dass dieser auch die beiden verbunden Member vergleicht.)

    ps: Hab die beiden Antworten vor meiner nicht gesehen. Entweder nicht richtig geguckt oder Verbindungsproblem zum Server oder ... keine Ahnung.



  • Erstmal vielen Dank an alle, die antworteten 🙂

    @wob sagte in Suchen in Vector von eigener Struktur richtig?:

    Das größte Problem bei dir dürfte sein, dass jeder Knoten einen Menge von Knoten enthält. Das ist nicht in deinem Sinne. Stattdessen sollte jeder Knoten eine Menge von Verweisen auf andere Knoten enthalten. Ansonsten wirst du keine Verbindungen bauen können.

    Ich muesste also einen set/vector von Verweisen bauen. Dazu direkt eine Frage: Sind Verweise Referenzen oder Zeiger? Rein logisch wuerde ich sagen, ich muesste Referenzen nutzen, oder? Implementiert sieht das dann so (bzw. anders mit set) aus?

    vector<Knoten&> verbunden;
    

    Scheint noch nicht zu stimmen, mein Programm kompiliert nicht mehr.

    @wob sagte in Suchen in Vector von eigener Struktur richtig?:

    Deine Knoten kopieren jeweils den vector v. Der Knotenkonstruktor sollte keinen vector an Knoten übergeben bekommen - by default ist ein Knoten dann nicht verbunden. Du musst die Verbindugen eh später setzen, weil die Knoten ja nacheinander erzeugt werden und die Verbindung erst möglich ist, wenn die Knoten fertig sind.

    Dann aendere ich also den Konstruktor folgendermassen ab:

    Knoten(int num) //Konstruktor
    		{
    			nummer = num;
    			vector<Knoten&> knot;
    			verbunden = knot;
    		}
    

    @wob sagte in Suchen in Vector von eigener Struktur richtig?:

    Außer du benennst sie mit einer ID und speicherst in jedem Knoten nur die IDs der verbundenen Knoten. Wäre vielleicht die bessere Lösung. Dann nimmst du einen vector<Knoten>, wo alle Knoten drin sind und z.B. K1(1, {{2, TransportMode::Taxi}, {3, TransportMode::Bus}}) usw.

    Ich verstehe den Ansatz, aber nicht genau dein Beispiel. Der Konstruktor kriegt dann also den Index und eine Liste von Tupeln aus Index und Verkehrsmodus der adjazenten Knoten?
    Beide Varianten sind aber vermutlich gleich gut, oder? Ich kann ja zuerst die Knoten mit einer Schleife erzeugen und dann die Verbindungen machen.

    @wob sagte in Suchen in Vector von eigener Struktur richtig?:

    (Bein nächsten Post bitte darauf achten, dass der gepostete Code auch compiliert)

    Bitte entschuldige, das lag vermutlich an den fehlenden includes und usings oder?

    @hustbaer sagte in Suchen in Vector von eigener Struktur richtig?:

    (Wobei du uns einen wichtigen Teil unterschlagen hast, nämlich den operator == von Knoten - ich gehe einfach mal davon aus dass dieser auch die beiden verbunden Member vergleicht.)

    Ja, hast Recht:

    bool operator == (Knoten k, Knoten k2) {  //Vergleichsoperator
    	if (k.get_nummer() != k2.get_nummer() ) {
    		return false;
    	}
    	if (k.get_verbunden() != k2.get_verbunden() ) {
    		return false;
    	}
    	return true;
    }
    

    Wenn ich bei dem die verbunden abfrage weglasse, mache ich dann was kaputt?

    EDIT: Grammatik einer Frage angepasst



  • @teedeekay

    bool operator == (Knoten k, Knoten k2)

    macht gleich hier zwei Kopien.



  • @manni66 sagte in Suchen in Vector von eigener Struktur richtig?:

    @teedeekay

    bool operator == (Knoten k, Knoten k2)

    macht gleich hier zwei Kopien.

    Also so?

    bool operator == (Knoten& k, Knoten& k2) 
    


  • @teedeekay

    da du nichts verändern willst, const.

    einfach mal drauflos programmiere

    Da scheint bei dir nicht mehr genug hängengeblieben zu sein um mit der Methode Erfolg zu haben.



  • @manni66 sagte in Suchen in Vector von eigener Struktur richtig?:

    da du nichts verändern willst, const.

    Hatte ich auch erst, aber dann mag er nicht den this zeiger als const knoten in knoten& konvertieren.



  • @teedeekay sagte in Suchen in Vector von eigener Struktur richtig?:

    @manni66 sagte in Suchen in Vector von eigener Struktur richtig?:

    da du nichts verändern willst, const.

    Hatte ich auch erst, aber dann mag er nicht den this zeiger als const knoten in knoten& konvertieren.

    Weil contains und ist_verbunden nicht const sind, wie sie es sein sollten.



  • Super, danke 🙂

    Dann habe ich jetzt nur noch ganz viele Zeiger auf Verweis ungueltig Fehler 😉


Anmelden zum Antworten