Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:adt:set:implementationen:start [14.11.2021 19:03] – [Zahlen hinzufügen] sbel
+++ faecher:informatik:oberstufe:adt:set:implementationen:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== Die Set-Implementationen im Detail ======
-===== Variante 1: ArrayList =====
-Die einfachste Lösung ist, wenn der ADT Set als interne Datenstruktur eine ''ArrayList'' verwendet.
-Beim Einfügen muss immer getestet werden, ob der Wert bereits in der ''ArrayList'' vorkommt. Dazu muss unter Umständen jedes Element der ''ArrayList'' untersucht werden.
-=== Vorteile: ===
-  * Einfache Implementation
-  * Speicherbedarf relativ gering (etwa proportional zur Anzahl der Werte)
-=== Nachteile: ===
-  * Suche nach einem Element bei großen Mengen aufwendig (proportional zur Anzahl der Werte)
-===== Variante 2: Bitvektor =====
-Man kann eine Menge von Integer-Zahlen auch in eine einzelne Integer-Zahl verpackt darstellen, indem man die entsprechenden Bits in ihrer Binärdarstellung setzt. Man spricht dann von einem **Bitvektor**.
-**Beispiel:** Die Menge ''{0,3,4}'' soll gespeichert werden. Dazu setzt man die Bits an den Stellen 0,3 und 4 auf ''1'' und alle anderen auf ''0'' und bestimmt anschließend die Dezimaldarstellung der Binärzahl. Das Resultat ist die Zahl 25:
-{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_090.png |}}
-Da eine Integer-Zahl in Java 32 Bit lang ist, kann man mit einer Integer-Zahl also für die Zahlen von 0 bis 31 darstellen, ob sie in einer Menge enthalten sind oder nicht.
-==== Ist eine Zahl in der Menge enthalten? ====
-Um herauszufinden, ob eine Zahl enthalten ist, kann man mit dem binären UND-Operator prüfen, ob das entsprechende Bit gesetzt ist:
-<code java>
-int vier_gesetzt = 25 & 16;  // Ergebnis: 16
-int eins_gesetzt = 25 & 2;   // Ergebnis: 0
-</code>
-{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_091.png |}}
-Der binäre UND-Operator verknüpft zwei ''int''-Zahlen (nach Umwandlung in die Binärdarstellung) und setzt im Ergebnis ein Bit auf 1, wenn die entsprechenden Bits in beiden Operanden auf 1 gesetzt sind.
-Eine Zahl ist in der Menge enthalten, wenn bei der UND-Verknüpfung ein Wert herauskommt, der nicht 0 ist.
-==== Zahlen hinzufügen ====
-Um einen Wert zu einem Bitvektor hinzufügen, verwendet man die binäre ODER-Verknüpfung.
-**Beispiel:** Zur Menge ''{0,3,4}'' soll die ''6'' hinzugefügt werden. Man setzt also den Bitvektor auf
-<code java>
- bitvektor = bitvektor | 64; // neuer Wert 89
-</code>
-{{ :faecher:informatik:oberstufe:adt:set:implementationen:auswahl_092.png |}}
-Der binäre ODER-Operator verknüpft zwei ''int''-Zahlen und setzt im Ergebnis ein Bit auf 1, wenn mindestens eines der entsprechenden Bits in den beiden Operanden auf 1 gesetzt ist.
-Beim Setzen eines Bits muss nicht geprüft werden, ob es bereits gesetzt ist – der ODER-Operator verändert in diesem Fall den Bitvektor nicht.
-==== Bitmasken ====
-Zum lesen und setzen von Elementen benötigt man die entsprechenden Zahlen, letztlich in Binärdarstellung. Diese Zahlen, die man zum Auslesen oder Setzen von Bits verwendet werden als ''Bitmaske'' bezeichnet.
-Eine Maske, bei der als niederwertigstes Bit nur das n-te Bit von rechts gesetzt ist, entspricht der Zahl 2^n. Schnell und effizient erhält man diese Zahl, indem man die Zahl 1 um n Stellen nach links „verschiebt“.