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 456 789 10
gelbpurpurrot 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.

 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;

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.

 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;

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.

 procedure Entfernen(Element: string);
   var i: integer;
 begin
   for i:= 1 to Kapazitaet do
     if Menge[i] = Element then
       Menge[i]:= <nowiki></nowiki>;
 end;
 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;
 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;

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.

 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;

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