C# Gedankliche Hilfestellung bei Verschachtelung

[Gateway_man]

Guten Morgen allerseits,

ich bin momentan an einem Problem, bei dem mir ein "akurrater" Lösungsweg nicht einfällt.

Zum Ausgangspunkt.

Ich erhalte eine generische Liste mit Feldern deren wichtigste Strukturelemente wie folgt aussehn:

Jedes element hat die Felder ID und ParentID (kann 0 sein) vom Typ int.

Jetzt will ich diese "Ordnen" das heißt ich habe eine Struktur geschrieben (nennen wir Sie mal Clients) die intern nochmal ein generisches Feld hat das ParentClients heißt.

So nun meine Frage, wie loope ich die urpsrungsliste (am effektivsten durch) um alle ParentClients zu den richtigen Clients zuzuordnen.

Wenn es nur eine ebene geben würde, wäre das nicht so schlimm. Nur kann auch jeder ParentClient weitere ParentClients besitzten und diese wiederrum weitere.

Wenn ich das mit Schleifen mache, schreibe ich mir einen Wolf und bekomm es (gedanklich) trotzdem nicht hin das ich alle ebenen erhalte.

Ich weiß es ist nicht ganz so super ausformuliert, ich hoffe jedoch das ihr es trotzdem verstanden habt.

Vielleich noch ein treffenderes Beispiel:

Nehmen wir an Ihr habt alle Daten + Ordnernamen eures Primären Laufwerkes in einer Generischen Liste. So nun möchtet ihr jedoch wieder die Baumstruktur herstellen, da diese in der bereitgestellten Liste nicht mehr existiert. Wie geht ihr also die Liste am besten durch um diese Struktur wiederherzustellen ohne am Ende zig hundert Zeilen Code geschrieben zu haben.

lg

Gateway

[SilentDemise]

Ich muss gestehen ich habe dein Problem nicht 100% verstanden, klingt für mich aber nach einem Fall, wo man mit LINQ sehr gut weiterkommen kann.

[HJST1979]

Ich kann dir eine Lösung schreiben, sie ist aber nicht die sauberste, also bitte mich nicht Zerlegen

1. Schritt Sortiere deine Listen nach ParentID (Wenn ParentID = 0 dann hast du die oberste Ebene)

Jetzt kannst du die Liste durchlaufen, ich geh mal davon aus, dass du ein TreeView hast

Code ist VB.NET

Dim tNode as Treenode

Dim htNodes as New Hashtable


For Each Element as ... in Liste

    tNode = New Treenode

    tNode.Text = Element.Wert1

    htNodes.Add(Element.ID) = tNode

    If Element.ParentID = 0 then

        Me.TreeView.Add(tNode)

    Else

        htNodes(Element.ParentID).Add(tNode)

    End IF

Next

Gruß Hans-Jörg

[Gateway_man]

Ich werde mal kurz per Code zeigen was ich meine:

public class Viewer{


  public List<Channel> GetChannelList() {

            List<Channel> result = new List<Channel>();

                foreach (ChannelListEntry item in m_sock.GetChannelList())

                {

                    Channel citem = new Channel();

                    if (item.ParentChannelId <= 0)

                    {

                        citem.ID = item.ChannelId;

                        citem.name = item.Name;

                        result.Add(citem);

                    }

                    else {

                        foreach (Channel xitem in result) {

                            if (xitem.ID == item.ParentChannelId) {

                                citem.ID = item.ChannelId;

                                citem.name = item.Name;

                                if (xitem.SubChannels == null)

                                    xitem.SubChannels = new List<Channel>();

                                xitem.SubChannels.Add(citem);

                            }

                        }

                    }

		// So wie es jetzt ist erhalte ich maximal die Zuordnung der ersten Subchannel. 

		//Da aber jeder Subchannel weitere Subchannel habe kann usw usw usw, geht das hier nicht so ganz auf.

                }


            return result;

        }




}

    internal class Channel {

        internal List<Channel> SubChannels = new List<Channel>();

        internal uint ID = 0;

        internal string name;    

    }

Ich hoffe ihr versteht mein Dilema.

Lg

Gateway

[NerdonRails]

Ich würde das ganze via Rekursion lösen:

var rootElements = acc.GetRootElements(allItems);

var result = acc.BuildTree(rootElements, allItems);

public class Item

{

	public Int32 Id

	{

		 get;

		 set;

	}


	public Int32? ParentId

	{

		 get;

		 set;

	}


	public List<Item> Children

	{

		 get;

		 set;

	}


	public Item(Int32 id, Int32? parentId = null)

	{

		 this.Id = id;

		 this.ParentId = parentId;

	}

}

public class TreeAccumulator

{



	public IEnumerable<Item> GetRootElements(IEnumerable<Item> allItems)

	{

		 var rootElements = from current in allItems

					  where current.ParentId == null

					  select current;

		 return rootElements;

	}


	public IEnumerable<Item> BuildTree(IEnumerable<Item> itemsToBeProcessed, IEnumerable<Item> allItems)

	{

		 foreach (var current in itemsToBeProcessed)

		 {

			  var children = from actual in allItems

					  where actual.ParentId == current.Id

					  select actual;

			  current.Children = children.ToList();

			  this.BuildTree(current.Children, allItems);

		 }

		 return itemsToBeProcessed;

	}

}

[Klotzkopp]

Benutz einen assoziativen Container, in dem du für jede ID den Channel-Verweis ablegst. So kannst du schnell den passenden Parent-Channel raussuchen, ohne deinen Baum durchsuchen zu müssen.

Ist überhaupt sichergestellt, dass die Liste, die m_sock.GetChannelList() zurückgibt, so aufgebaut ist, dass jeder Channel hinter seinem Parent-Channel steht? Ansonsten musst du dir noch etwas überlegen, wie du Einträge zurückstellst, deren Parent-Channel noch gar nicht in deinem Baum ist.

[Gateway_man]

Ist überhaupt sichergestellt, dass die Liste, die m_sock.GetChannelList() zurückgibt, so aufgebaut ist, dass jeder Channel hinter seinem Parent-Channel steht?

Eine hervorragende Frage . Es ist nicht zwangsläufig gewährleistet. Jedoch wird für jedes ChannelListEntry eine Order nummer mitgeliefert.

Vielen Dank an alle, für die ganzen Anregungen. Ich werde Sie mir mal zu gemüte führen und mich gegenfalls dann wieder melden.

lg

Gateway

[streffin]

ein kleiner Einwurf ...

mit so einer Struktur kannst du wunderbar endlosschleifen bauen ...

ID 0 ParemtID 2

ID 1 ParentID 0

ID 2 ParentID 1

würdest du das jetzt durch loopen um die Wurzel des Baums zu finden hättest du eine wunder schöne infinite loop.

Da solltest du ein Auge drauf haben, damit sowas nicht passieren kann.

Gruß

Sven

[lilith2k3]

Also ich habe einmal ein ähnliches Problem gehabt (Baumstruktur): Organisationseinheiten innerhalb einer Firma.

Mein Lösungsweg sah so aus:

1) Ermittele diejenige Organisationseinheit, die selbst kein Eltern-Element hat (bzw. "NULL" oder andere Kennung).

Das Element muss also der Root-Knoten des Baumes sein. Einfügen und aus der Liste streichen.

2) Durchlaufe die Liste der verbleibenden Organisationseinheiten zyklisch bis Liste Leer.

2.1) Prüfe, ob zu dem aktuellen Element ein Element im Baum existiert, dessen ID mit der ElternID des aktuellen Elements übereinstimmt

2.1.1) Wenn es eins gibt, füge das aktuelle Element unterhalb des Eltern-Elementes ein und streich es

2.1.2) Wenn es keins gibt, gehe zum nächsten Element

Die Suche nach einem passenden Element selbst, ist rekursiv aufgebaut.

Das Kriterium "Bis Liste leer" kann auch zu einer Endlosschleife führen. Das kannst Du insofern unterbinden, indem Du eine mathematische Obergrenze (n!) angibst (quasi hast Du n Positionen zu besetzen und spielst alle Möglichkeiten durch - spätestens nach n! Schritten solltest Du alle Elemente an ihrem Platz haben, wenn nicht, ist irgendetwas faul und es sollte mit einem Fehler abgebrochen werden).

P.S.: Bin auch jetzt noch offen für Verbesserungsvorschläge :]

[streffin]

Was ich das letzte mal gemacht habe, mit dem ich auch nicht ganz glücklich war / bin:

Ich hatte in jedem Element noch die Hierachieebene als Attribut. Beim Aufbau der Struktur konnte ich damit dann abfangen, dass ich keine "Sprünge" in der Hirarchie hatte, und damit die Endlosschleife ausgeschlossen.