Der ADT "Set" (Menge)

Der abstrakte Datentyp Set repräsentiert im mathematischen Sinne eine Menge. Eine Menge hat folgende Eigenschaften:

• Eine Menge kann beliebig viele Elemente enthalten.
• Jedes Element kann höchstens einmal vorhanden sein.
• Es kommt nicht auf die Reihenfolge der Elemente an.

Und folgende Methoden:

• Konstruktor Set() – erzeugt eine leere Menge
• einfuegen(wert: int) – fügt den Wert wert in die Menge ein, falls er noch nicht vorhanden ist
• entfernen(wert: int) – entfernt den Wert wert aus der Menge, falls er vorhanden ist; andernfalls wird die Menge nicht verändert.
• enthaelt(wert: int): boolean – gibt true zurück, wenn wert in der Menge enthalten ist, sonst false.
• anzahl(): int – gibt die Anzahl der Elemente in der Menge zurück
• istLeer(): boolean – gibt true zurück, wenn die Menge leer ist, sonst false.
• schnittmenge(s: Set): Set – ???
• vereinigungsmenge(s: Set): Set – ???
• differenz(s: Set): Set – ???
• untermenge(s: Set): boolean – gibt true zurück, wenn jedes Element dieser Menge in s enthalten ist
• gleich(s: Set): boolean – gibt true zurück, wenn diese Menge und s die gleichen Elemente enthält; sonst false.

Arbeite mit der Vorlage von https://codeberg.org/qg-info-unterricht/bluej-adt-set und bearbeite nachfolgende Aufgaben. Ganz unten findest du Tipps zu den einzelnen Aufgaben, falls du Hinweise benötigst.

In der Vorlage sind zwei verschiedene Varianten implementiert. Der Quellcode ist nicht einsehbar. Finde heraus, ob beide Versionen die gleiche Funktionalität aufweisen. Erstelle dazu Beispielobjekte. Verwende die Methode alsArray(), um dir die Elemente eines Sets anzuschauen.

Wähle nun eine der beiden Varianten aus der Vorlage aus und löse damit die folgenden Teilaufgaben. Verwende auch hier wieder die Methode alsArray(), um dir die Elemente eines Sets anzuschauen.

1. Erstelle ein Set M = {19, 23, 1, 11, 10, 33, 9, 42, 17} und ein Set N = {10, 7, 11, 19, 2, 23, 42, 37}. Finde heraus was die Methoden schnittmenge(s), vereinigungsmenge(s)und differenz(s) machen. Beschreibe die Funktionalität für das gegebene Beispiel sowie den allgemeinen Fall (schriftlich).
2. Ist die Reihenfolge der eingefügten Elemente relevant? Prüfe mithilfe passender Beispielmengen.
3. Die Operation untermenge(s) gibt true zurück, wenn jedes Element dieser Menge in s enthalten ist. Überprüfe diese Funktionalität, indem du die Operation mit verschiedenen Beispielmengen testest. Achte darauf, dass alle möglichen Fälle abgedeckt sind.
4. Vergleiche die Operationen des ADT Set mit denen anderer ADTs. Welche Gemeinsamkeiten und v.a. welche Unterschiede fallen dir auf?

• Erstelle je ein Set beider Varianten und inspiziere die erstellten Objekte.
• Dann schneide die beiden Sets miteinander und erstelle aus dem Schnitt ein neues Objekt (Methode anwenden → Hole → neues Objekt benennen).
• Betrachte dein Ergebnis mithilfe von alsArray() und indem du es inspzierst. Wie wird dein Ergebnis dargestellt? Beschreibe.
• Beschreibe auch, was passiert, wenn du die beiden Sets anders herum schneidest. In welcher Form wird dein Ergebnis nun dargestellt?
• Begründe deine Beobachtung mithilfe der bisher erlernten Konzepte.

Hier findest du Tipps zu den einzelnen Aufgaben, sofern du sie benötigst.

Tipp A2.1

Tipp A2.2

Tipp1 A2.3

Tipp2 A2.3

Tipp3 A2.3

Tipp A2.4

Tipp A3

• Die Set-Implementationen im Detail