Menge (Datenstruktur)

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 Funktionen:

  • 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. [1]

Einige Programmiersprachen wie zum Beispiel Modula-2 oder Oberon haben Mengen im Sprachumfang integriert, wo dieser Datentyp 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 (siehe zum Beispiel in Java die Klasse "Bitset").

Einzelnachweise

  1. G. Hachtel, F. Somenzi: Logic Synthesis and Verification Algorithms, 1996, S. 219.

Literatur


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Menge — (von mittelhochdeutsch manic „viel“, vgl. mannigfach) bezeichnet: eine bestimmte Anzahl Menge (Mathematik), eine Zusammenfassung unterscheidbarer Objekte zu einer Gesamtheit Menge (Datenstruktur), in der Informatik eine von der mathematischen… …   Deutsch Wikipedia

  • Heap (Datenstruktur) — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung… …   Deutsch Wikipedia

  • Schlange (Datenstruktur) — In der Informatik bezeichnet eine Warteschlange (engl. Queue [kju]) eine häufig eingesetzte spezielle Datenstruktur. Inhaltsverzeichnis 1 Funktionsprinzip 2 Illustration 3 Anwendung 4 Imp …   Deutsch Wikipedia

  • Liste (Datenstruktur) — Die Verkettete Liste ist eine dynamische Datenstruktur, die eine Speicherung von einer im Vorhinein nicht bestimmten Anzahl von miteinander in Beziehung stehenden Objekten erlaubt. Sie wird durch Zeiger auf die jeweils folgende(n) Knoten oder… …   Deutsch Wikipedia

  • Warteschlange (Datenstruktur) — In der Informatik bezeichnet eine Warteschlange (engl. Queue [kju]) eine häufig eingesetzte Datenstruktur. Inhaltsverzeichnis 1 Funktionsprinzip 2 Illustration 3 Anwendung …   Deutsch Wikipedia

  • Größte stabile Menge — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Maximale stabile Menge — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Stabile Menge — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Unabhängige Menge — Knotenüberdeckungen, Cliquen und stabile Mengen sind Begriffe der Graphentheorie und bezeichnen spezielle Teilmengen von Knoten in Graphen. Das Finden von minimalen Knotenüberdeckungen und größten Cliquen bzw. stabilen Mengen gilt als… …   Deutsch Wikipedia

  • Dynamische Datenstruktur — Dynamische Datenstrukturen bezeichnen in der Informatik Datenstrukturen, die eine flexible Menge an Arbeitsspeicher reservieren. Grundsätzlich unterscheidet man zwei Arten: Bei der ersten wird schon während der Initialisierung ein… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”