Menge (Datenstruktur)

Die Datenstruktur Menge, auch Set genannt, ist eine ungeordnete Sammlung von Elementen eines bestimmten Datentyps, von denen jeweils maximal ein Exemplar enthalten ist. Sie ist der endlichen Menge in der Mathematik nachempfunden. Es ist meist aus Effizienzgründen sinnvoll, konstante Mengen anders zu repräsentieren als dynamische Mengen.

Zu den verfügbaren Operationen zählen meist:

Erzeugen einer Menge aus den Elementen
Prüfung, ob ein Element bereits enthalten ist.
Prüfung, ob eine Menge Untermenge einer anderen ist.
Bildung von Schnittmenge, Vereinigung, Differenzmenge usw.
Aufzählen der Elemente der Menge in einer beliebigen Ordnung

Dynamische Mengen unterstützen zusätzlich folgende Funktion:

Hinzufügen und Entfernen einzelner Elemente.

Je nach Anwendung können jeweils mehr oder weniger der genannten Operationen implementiert werden.

Implementation

Dynamische Mengen werden üblicherweise mit Datenstrukturen wie Hashtabellen oder balancierten Suchbäumen implementiert.

Wenn ausschließlich Untermengen einer bekannten Menge behandelt werden (z.B. ein Intervall der natürlichen Zahlen), ist auch eine Darstellung als Feld von Bits möglich. Dabei stellt eine Eins an Stelle n dar, dass das Element n in der Menge enthalten ist. Die üblichen Mengenoperationen lassen sich dann gut als binäre Operationen implementieren. Inklusionstests lassen sich dann in konstanter Zeit durchführen.

Wenn eine binäre Kodierung für die Elemente einer Menge verfügbar ist, können Mengen auch als Binäres Entscheidungsdiagramm repräsentiert werden. Dabei wird die Menge als Boolesche Funktion repräsentiert, die für die Kodierung ihrer Elemente Eins, für alle anderen Kodierungen Null ergibt. Das kann für bestimmte sehr große, aber einfach strukturierte Mengen sinnvoll sein, wie sie etwa beim Model Checking auftreten können.

Einige Programmiersprachen, wie zum Beispiel Modula-2, Oberon oder Python, haben Mengen im Sprachumfang integriert, wobei dieser Datentyp dann typischerweise mit "SET" oder "BITSET" deklariert wird. Viele Programmiersprachen haben allerdings keinen elementaren Datentyp für Mengen im Definitionsumfang, und da in diesen Fällen oft Mengenoperationen mit ganzzahligen Datentypen zugelassen sind, ist die Zuweisungskompatibilität erheblich eingeschränkt, was leicht zu Programmfehlern führen kann. Daher ist es im Allgemeinen wesentlich besser und sicherer, Bibliotheksfunktionen für Mengenoperationen zu implementieren und zu benutzen.

Basierend auf einem Artikel in:

Wikipedia.de