Benutzer-Werkzeuge

Webseiten-Werkzeuge


datenstruktur_menge

== Aufgabe == GK Informatik, Hessen 2007 Beim aus der Mathematik bekannten Konzept der Menge werden einzelne Elemente zu einer Menge zusammengefasst. Eine Menge kann leer sein, niemals aber mehrere Exemplare eines Elements enthalten. Die Reihenfolge der Elemente spielt keine Rolle. Um in der Informatik mit Mengen arbeiten zu können, benötigt man eine geeignete Datenstruktur. Wir verwenden dafür ein Feld, in dem die Elemente gespeichert werden. 1. In der Tabelle ist dargestellt, wie die Menge M = {rot, purpur, gelb, lila, hellblau} mit Hilfe eines Feldes dargestellt werden kann, wobei die maximale Kapazität des Feldes zehn Elemente beträgt. [[Beschreiben]] Sie diese Darstellung. |1 |2 |3 |4|5|6 |7|8|9 |10| |gelb|purpur|rot| | |hellblau| | |lila | | 2. Fügen Sie das neue Element ''grün'' mit dem folgenden Algorithmus in das Feld aus 1. ein und [[erläutern]] Sie diesen Algorithmus. <code pascal> procedure Einfuegen(Element: string); var i: integer; gefunden: boolean; begin gefunden:= false; for i:= 1 to Kapazitaet do if Menge[i] = Element then gefunden:= true; if not gefunden then begin i:= 1; while (i <= Kapazitaet) and (Menge[i] <> '') do i:= i + 1; if i <= Kapazitaet then Menge[i]:= Element end; end; </code> 3. [[Implementieren]] Sie jeweils einen Algorithmus 3.1 der ein Element entfernt, 3.2 der prüft, ob ein Element in der Menge enthalten ist, 3.3 der die Anzahl der Elemente der Menge liefert. 4. Analysieren und [[erläutern]] Sie die folgende Prozedur, die mit FeldNachMenge(1) aufgerufen wird. [[Implementieren]] Sie dann eine iterative Variante. <code pascal> procedure FeldNachMenge(Ab: integer); var i: integer; Element: string; begin if Ab < Kapazitaet then begin Element:= Menge[Ab]; for i:= Ab + 1 to Kapazitaet do if Menge[i] = Element then Menge[i]:= <nowiki></nowiki>; FeldNachMenge(Ab + 1); end; end; </code> 5. Bei der in 1. benutzen Modellierung M1 einer Menge können beim Löschen von Elementen der Menge Lücken in der Datenstruktur entstehen. Man kann die Modellierung so ändern, dass man nach jeder Löschoperation eine entstandene Lücke durch ein anderes Element schließt. [[Vergleichen]] Sie die geänderte Modellierung M2 mit der ursprünglichen Modellierung M1. == Lösung == 1. Bei einem Feld erfolgt der Zugriff auf ein Feldelement über einen Index. An den Indexpositionen 1, 2, 3, 6 und 8 sind die Elemente der Menge M gespeichert. Im Feld können an den Indexpositionen 4, 5, 7, 9 und 10 noch maximal fünf weitere Elemente gespeichert werden. 2. Zunächst wird geprüft, ob das einzufügende Element schon im Feld gespeichert ist. Wenn es schon gespeichert ist, passiert nichts, d. h. ein Element kann nicht mehrfach in eine Menge eingefügt werden. Ist das Element noch nicht in der Menge, wird nach einem leeren Platz gesucht. Ist ein solcher vorhanden, so wird das Element an der betreffenden Stelle in das Feld eingefügt. Das Element ''grün'' wird nach diesem Algorithmus an der Position 4 gespeichert. 3. <code pascal> procedure Entfernen(Element: string); var i: integer; begin for i:= 1 to Kapazitaet do if Menge[i] = Element then Menge[i]:= <nowiki></nowiki>; end; </code> <code pascal> function istEnthalten(Element: string): boolean; var i: integer; begin Result:= false; for i:= 1 to Kapazitaet do if Menge[i] = Element then Result:= true; end; </code> <code pascal> function gibAnzahl: integer; var i, Anzahl: integer; begin Anzahl:= 0; for i:= 1 to Kapazitaet do if Menge[i] <> <nowiki></nowiki> then Anzahl:= Anzahl + 1; Result:= Anzahl; end; </code> 4. Dieser Algorithmus wandelt ein Feld in eine Menge um. Dazu werden mehrfach im Feld vorkommende Elemente entfernt. Beim Aufruf von FeldNachMenge(1) wird das erste Element im Feld bestimmt. Anschließend wird im Rest des Feldes geprüft, ob dieses Element noch einmal vorkommt und gegebenenfalls gelöscht. Zum Schluss erfolgt ein rekursiver Aufruf, so dass das Verfahren mit dem nächsten Element fortgesetzt wird. Dies wiederholt sich solange, bis alle Positionen geprüft sind. <code pascal> procedure FeldNachMengeIt; var i, k: integer; Element: string; begin for k:= 1 to Kapazitaet - 1 do begin Element:= Menge[k]; for i:= k + 1 to Kapazitaet do if Menge[i] = Element then Menge[i]:= <nowiki></nowiki> end; end; </code> 5. Die benutzte Modellierung ist einfacher, weil man sich das Verschieben von Elementen erspart. Ist die Kapazität des Feldes allerdings deutlich größer als die Anzahl n der Elemente, so wäre die Variante mit Verschieben der Elemente effizienter. Jede in den Algorithmen vorkommende Schleife müsste nur noch bis zur Anzahl n laufen und nicht bis zur Kapazität des Feldes. Beim Einfügen könnte man direkt am Ende des belegten Feldes das neue Element speichern. Das Suchen einer freien Position würde entfallen. Das Löschen wäre natürlich aufwändiger, weil immer die Lücke durch Verschieben von Elementen geschlossen werden muss.

datenstruktur_menge.txt · Zuletzt geändert: 2014/09/01 13:25 von admin