Datenstruktur Menge

Aus Operatoren

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.

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]:= '';
    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]:= '';
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] <> '' 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]:= ''
  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.