mehrfach-verzweigte Liste

[Wasserfallkarzinom (Gast)]

Frage zu Datenpanken, die Abbildung sei eine Eisenbahn mit zwei Kreisen 
und Weichen:


                       W  W           
              *           #     #               *
                      W      W            
                                               
                                                
                                                
                                         
                                                
                                     


Hi,

ich habe folgendes Problem. Das obige Sternen-W-Bild sei eine 
Eisenbahnstrecke. Jedes Sternchen * sei eine Schiene, W eine Weiche. Der 
Hasenkasten # soll einfach nur den Übergang zwischen zwei Weichen 
symbolisieren. Ich möchte gerne die Schinenstränge verarbeiten/verwalten 
können. Dazu habe ich mir im groben folgendes überlegt

class Schine ()
{
 int Nummer;
 int Vorgänger;
 int Nachfolger;

 Rest...
};

class Weiche ()
{
 int Nummer;
 int Vorgänger;
 int Nachfolger_1;
 int Nachfolger_2;

 Rest...
};

Jede Schine/Weiche habe eine individuelle Nummer. In Vorgänger wird die 
Schinennummer eingetragen, die davor ist, in Nachfolger die danach 
kommende Schine.

Bei der Weiche wird es etwas komplizierter. Das einfachste Beispiel sei 
eine 2fache Weiche. Dort gibt es ja dann zwei Nachfolger und einen 
Vorgänger.

Jetzt sollen für jede Schine/Weiche individuelle Eigenschaften noch 
vorhanden sein, z.B. die Farbe, ob sich ein Zug darauf befindet. Diese 
Eigenschaften sind mit Rest... in der Klasse symbolisiert.

Ich hab ja so nun eine Vielzahl von Schinen, ich schreib jetzt einfach 
immer nur mal Schinen, aber die Weichen sind auch damit gemeint, Weiche 
ist ja eine Kindklasse von Schiene. In gewissen definierten 
Zeitabständen muss ich ja den ganzen Datensatz von Schinen einmal 
durcharbeiten, ob sich irgendwelche Eigenschaften geändert haben oder 
geändert werden müssen etc. Dazu muss ich ja den ganzen Datensatz einmal 
abarbeiten.

Hätte ich jetzt einfach nur einen Kreis, so könnte ich eine einfache 
lineare Liste nehmen. Ich würde eine Schine als Start definieren mir den 
Start merken, da ich ja eine Ringstruktur habe und irgendwie ungern an 
der Startschiene Vorgänger auf NULL setzen, vielleicht muss ich das 
doch, ich weis es grad noch nicht. Und dann könnte ich die ganze Liste 
von der ersten Schine bis zur letzten durcharbeiten.

Jetzt kommt aber der Knackpunkt Weiche. Dort habe ich ja dann in der 
Liste zwei Möglichkeiten weiterzugehen, einmal rechts, einmal gerade 
aus. Zunächst könnte man ja denken - ist ja ein einfacher binärer Baum. 
Aber Pustekuchen, ist es leider doch nicht, denn es kann vorkommen, dass 
durch die Schinenvernetzungen auch manchmal ein Nachfolger auf ein 
voriges Element zeigt, weil ich ja im obigen Beispiel schon zwei Weichen 
habe. Bei einer Weiche wäre das nicht so der Fall, aber bei zwei Weichen 
schon. Also sind die einzelnen Datensätze auch untereinander noch 
verkettet.

Damit scheidet eine rekursive Abarbeitung der Liste aus, weil ich ja 
irgendwann mich im Kreis drehen würde und ich bekäme eine Art 
Endlosschleife. Alternativ ist mir noch eingefallen, dass man bei jedem 
nächsten Bearbeitungsschritt immer eine zweite kleine Datenbank 
mitschleppt, wo immer eingetragen wird, welche Schinennummern bereits 
schon bearbeitet wurden. So muss aber dann bei jedem Rekursionsschritt 
immer überprüfen, ob die jeweilige Schiene bereits bearbeitet wurde. Das 
mag bei kleinen Datenbanken vielleicht noch gehen, aber bei jedem 
Schritt vergrößert sich dann ja auch dieser zusätzliche Datensatz. Und 
klappen könnte dies wahrscheinlich auch, aber ich wäre mit dieser 
Variante unzufrieden.

Ich bin leider mit Datenbanken und Listen etc. nicht so ganz gut 
vertraut. Wie binäre Bäume und die einfache linerare Liste funktioniert, 
dass hab ich kapiert, aber diese beiden Varianten lassen sich für mein 
Problem nicht benutzen. Ich hatte als Gedankenexperiment auch mal 
zunächst gedacht, setz doch den Nachfolger bei der letzten Schine im 
jeweiligen Kreis auf NULL, dann wäre ja theoretisch ein Abbruchkriterium 
vorhanden und man könnte theoretisch einen binären Baum benutzen (ginge 
dann aber auch nur bei einer zweifach-Weiche), aber dann geht ein 
Schinenstrang zwischen zwei Weichen verloren, dass wären dann z.B. die 
beiden   zwischen den beiden Weichen im inneren Schinenkreis, die dann 
garnicht abgearbeitet würden.

Also, ich muss mich irgendwie mit Datenbanken und so wohl auseinander 
setzen, aber ich hab da momentan nicht so die Idee, wonach ich genau 
suchen müsste oder wie ich damit anfange. Ich habe mal das Stichwort 
mehrfachverzweigte Netze und so in google ausprobiert, aber dann kommen 
z.B. irgendwelche Hinweise zu Fettsäuren aus der Chemie und lauter so 
ein Kram.

Ich habe in der vorschau festgestellt, dass mein schönes kleines Bild 
aus Sternchen, W´s und Hasenkästen irgendwie kaputt gemacht wird, darum 
hab ich es als Screenshot mit angefuegt.

[sebastians (Gast)]

Versuchs mal mit dem Stichwort "gerichteter Graph" (engl. "directed 
graph").

Begriffe:
Knoten (engl. vertices): Deine Schienen
Kanten (engl. edges): Die Verweise auf die Nachfolger - Schienen.

Wenn du ein Paar aus Vorgänger+Nachfolger-Verweis als eine Kante 
betrachtest, dann kannst du es auch als ungerichteten Graphen nehmen.

Und zum Besuchen aller Knoten kannst du z.B. Tiefensuche (engl. depth 
first search, DFS) oder Breitensuche nehmen.

Tiefensuche funktioniert mit einem Stack (oder Rekursion) und indem du 
die besuchten Knoten markierst.
Breitensuche ähnlich, nur mit FIFO statt Stack.

Wenn du die Vorgänger/Nachfolger als Nummern speicherst: Weisst du 
schon, wie du das dazugehörende Schienen/Weichen-Objekt findest? 
Verwendest du std::map<int, Schiene*> oder std::vector<Schiene*> (mit 
der Nummer als Index)? Oder, Stichwort Datenbanken, arbeitest du mit 
einer relationalen Datenbank?

Markieren kannst du, indem du deinen Knoten ein extra Attribut (Typ 
bool) gibst. Oder du machst ein Markierungs-Array und benutzt die 
Knoten-Nummer als Index.
------------------------------
Oder machs viel einfacher: Steck die Schienen in eine Datenstruktur, die 
du von vorn nach hinten durchlaufen kannst und geh einfach durch die 
ganze Datenstruktur, ohne den Verweisen zu folgen. Kommt drauf an was du 
damit bezwecken willst... willst du nur jede Schiene einmal besuchen 
oder brauchst du eine besondere Reihenfolge oder willst nur die 
besuchen, die zusammenhängen?

Ich nehme an, du programmierst in C++ (auch wenn die Klammern () hinter 
dem Klassennamen da nicht stimmen).
Da kommen die Datenstrukturen der STL (std::vector, std::list, ...) in 
Frage.

Oder ganz einfache Arrays (da musst du allerdings die Größe schon beim 
Anlegen kennen).

Wenn "Weiche" eine Unterklasse von "Schiene" ist ("Eine Weiche IST EINE 
Schiene"), dann versuch nicht, sie direkt in eine Schienen-Datenstruktur 
zu legen. Leg Zeiger in die Datenstruktur, z.B. std::vector<Schiene*>.

Warum schreibst du von Datenbanken? Willst du die Schienen persistent 
(dauerhaft, auf der Festplatte) speichern? Das ist nochmal ganz 
anderst...

So, ich hoffe, ich hab jetzt genug Fachwörter eingeworfen, nach denen du 
im Internet suchen kannst :-)

[sebastians (Gast)]

noch was: vielleicht solltest du es erstmal mit einer einfacheren 
Programmiersprache versuchen. C zum Beispiel.

http://yosefk.com/c++fqa/
Was da steht ist (großteils) nicht übertrieben!

[Wasserfallkarzinom (Gast)]

Hi Sebastians,

vielen Dank, dass Du Dir die Mühe gemacht hast, mir so ausführlich auf 
meine Fragestellung zu antworten. Die beiden von Dir vorgeschlagenen 
Varianten

- das Setzen eines Markierungsbits, ob bereits ein Durchgang durch 
Schiene erfolgte
- sowie das sequenzielle Abarbeiten der einzelnen Schinenelemente

scheinen recht praktisch zu sein, das letzte wird in jedem Fall 
funktionieren und die Variante mit dem boolschen Markierungsbit hat 
schon mal auf dem Papier funktioniert.

Die beiden Integer Vorgaenger/Nachfolger sind die Schinennummern, nicht 
die Zeiger für die Speicherstellen von Vorgaenger/Nachfolger, die müssen 
noch ergänzt werden. Ich musste ja erstmal anfangen zu ueberlegen, 
welche Eigenschaften braucht denn so ne Schine und so und da kann man ja 
immer weiter was dranbasteln und die Speicherstellen werden ja beim 
Erzeugen der Schinenfolge erzeugt, aber da ich jeder einzelnen Schine 
eine individuelle Nummer geben will, brauch ich ja auch noch dafür eine 
Variable, die hab ich eben Nummer genannt und Vorgäner/Nachfolger sind 
eben einfach erstmal die Nummern für mich, wie die Schlüssel bei einer 
relationalen Datenbank.

Datenbank, passt nicht so der Begriff, ne relationale Datenbank will ich 
natürlich nicht, aber ich will natürlich meine Schinenkreise schon 
abspeichern in einer Datei, aber die wird ja einmal bei Programmstart 
geöffnet und eingelesen, da jetzt von Datenbank zu sprechen ist glaub 
ich ein bißchen übertrieben :-)

[Wasserfallkarzinom (Gast)]

Hi,

folgendes verstehe ich nicht:


sebastians schrieb:
> Wenn "Weiche" eine Unterklasse von "Schiene" ist ("Eine Weiche IST EINE
> Schiene"), dann versuch nicht, sie direkt in eine Schienen-Datenstruktur
> zu legen. Leg Zeiger in die Datenstruktur, z.B. std::vector<Schiene*>.

Was ist damit gemeint? Warum soll ich Weiche nicht als Unterklasse von 
Schiene verwenden, also die Schiene um die Weichenfunktionen erweitern, 
sondern diese Sache mit dem Zeiger in die Datenstruktur zu machen?

[sebastians (Gast)]

"Warum soll ich Weiche nicht als Unterklasse von
Schiene verwenden" --> Darfst du gern machen. Aber in einer 
Datenstruktur, die Weichen und Schienen enthalten soll, kannst du dann 
halt nur einen Zeiger auf Schienen speichern (der auch auf Weichen 
zeigen kann, weils ja eine Unterklasse ist) und nicht die Schienen 
selbst.

Also:

class Schiene...
class Weiche: public Schiene...

vector<Schiene> schienen;
vector<Schiene*> schienenZeiger;

schienen[i] = Weiche(...); // geht nicht
schienenZeiger[i] = new Weiche(...); // geht

[Wasserfallkarzinom (Gast)]

Hi sebastians,

vielen Dank für Deine Infos. Aber ich muss Dir ehrlich gestehen, dass 
ich immer noch nicht so genau kapiere, was Du mir damit eigentlich sagen 
möchtest.


Dass was Du schreibst

sebastians schrieb:
> schienen[i] = Weiche(...); // geht nicht

kann doch auch schon deshalb nicht gehen, weil Schiene und Weiche doch 
zwei unterschiedliche Datentypen sind und ich würde die Klasse Schiene 
doch eigentlich auch an gar keiner Stelle mehr im Programm dierekt 
verwenden, sondern ich würde immer Objekte vom jeweiligen Typ erzeugen, 
also eben z.B. Weiche, gerade Schiene, Kurve (alles Kinder von Schiene 
mit jeweils unterschiedlichen Eigenschaften, wo eben ein "Rumpf" gleich 
ist). Und die jeweiligen Stelle in der Liste, wo die Stellen auf 
Nachfolger oder Vorgänger oder so weisen, verweisen doch dann auf 
Speicherstellenadressen und somit kann ich doch auch unterschiedliche 
Listenelemente miteinander verknüpfen. Ich muss halt immer nur bei der 
Auswertung der Liste oder wie auch immer man die Daten miteinander dann 
verknüpft eine unterschiedliche Bearbeitung für die verschiedenartigen 
Datentypen (eben Weiche, gerade Schiene ...) machen, da ja 
unterschiedliche Eigenschaften in jeder Klasse sind.

[Karl H. (kbuchegg)]

Wasserfallkarzinom schrieb:

> sebastians schrieb:
>> schienen[i] = Weiche(...); // geht nicht
>
> kann doch auch schon deshalb nicht gehen, weil Schiene und Weiche doch
> zwei unterschiedliche Datentypen sind

Genau darum gehts.
Bei dir ist das so.
Bei Sebastian aber nicht. Eine Weiche IST EINE Schiene weil die Klasse 
Weiche von der Klasse Schiene abgeleitet wurde!. Daher kann der 2.te 
Vektor sowohl Zeiger auf Schienen als auch Zeiger auf Weichen speichern.

Was du als allererstes ganz dringend brauchst, ist Literatur! Kauf dir 
einen Stroustroup und arbeite ihn durch. Das was du machst, hat zur Zeit 
keinen Sinn. Du versuchst gleichzeitig Progammiersprache, typische 
Alogorithmen, typische Datenstrukturen und objektorientierte 
Programmierung in einem Rutsch zu erlernen. Und das ganze auch noch ohne 
sinnvoll aufgebaute Lernunterlagen sondern frei Schnauze. Du kannst 
damit nur auf die Nase fallen. Das ist so sicher wie das Amen im Gebet!


Und: nein. Das Ganze hat erst mal nichts mit Datenbanken oder linearen 
Listen oder dergleichen zu tun, sondern ganz einfach damit, wie 
Polymorphismus in C++ funktioniert.