Atari Computer

Beispiel: einfach verkettete Liste

Die folgenden Beispiele zeigen eine sortierte Liste. Da der Datentyp erst bei einer konkreten Anwendung feststeht, sind die Listen hier nur als Beispiel implementiert.

Wenn in der Programmiersprache ein typloser und damit universeller Zeiger und Funktionspointer zur Verfügung stehen, kann die Listenverwaltung universell implementiert werden. Ein Beispiel in C könnte dann etwa so aussehen. Der Schlüssel und die Daten werden von der Liste als typloser Zeiger verwaltet. Die nötige Vergleichsfunktion wird der Liste als Funktionspointer bei der Initialsierung übergeben.

Sprache	C	Pascal	Modula
Beispiel	liste.c	liste.pas	liste.mod

liste.c

/* Da der Datentyp der Liste erst bei einer konkreten Anwendung  */
/* feststeht, ist die Liste nur als Beispiel und nicht als Modul */
/* programmiert.                                                 */

#include 
#include 

typedef long ListeKeyType;
typedef struct liste_element {
   ListeKeyType Key;
   struct liste_element *Next;
} ListeElement, *ListeKnoten;
typedef ListeKnoten Liste;

void ListeCreate(Liste *Wurzel)
{
   *Wurzel=NULL;
}

int ListeInsert(Liste *Wurzel, ListeKeyType Daten)
{  ListeKnoten WorkPtr, NewElement;
   int fertig;

   /* neues Listenelement erzeugen */
   NewElement = malloc(sizeof(ListeElement));
   if (NewElement != NULL)
   {
      NewElement->Key = Daten;
      /* Listenelement einfuegen */
      if (*Wurzel == NULL)
      {
         /* Liste ist leer -> als erstes Element einfuegen */
         NewElement->Next = NULL;
         *Wurzel = NewElement;
      }
      else
      {
         /* die einzufuegende Stelle suchen */
         if (NewElement->Key <= (*Wurzel)->Key)
         {
            /* als erstes Element einfuegen, da kleinster Schluessel */
            NewElement->Next = *Wurzel;
            *Wurzel = NewElement;
         }
         else 
         {
            /* Liste durchlaufen */
            WorkPtr = *Wurzel;
            fertig = 0;
            while ((WorkPtr->Next != NULL) && !fertig)
            {
               if (WorkPtr->Next->Key > NewElement->Key)
               {
                  /* Der Nachfolger der aktuellen Position hat
                     einen groesseren Schluessel -> einfuegen */
                  NewElement->Next = WorkPtr->Next;
                  WorkPtr->Next = NewElement;
                  fertig = 1;
               }
               else
                  /* noch nicht gefunden -> Liste weiter durchsuchen */
                  WorkPtr = WorkPtr->Next;
            }
            if (!fertig)
            {
               /* Es wurde in der Liste keine Stelle zum Einfuegen
                  gefunden -> am Ende anhaengen */
               NewElement->Next = NULL;
               WorkPtr->Next = NewElement;
            }
         }
      }
      return(1);
   }
   else
      return(0);
}

int ListeDelete(Liste *Wurzel, ListeKeyType Daten)
{  ListeKnoten WorkPtr, MerkPtr;
   int gefunden;

   gefunden = 0;
   if (*Wurzel != NULL)
   {
      /* Die Liste enthaelt Elemente */
      if ((*Wurzel)->Key == Daten)
      {
         /* das erste Element ist das gesuchte */
         WorkPtr = *Wurzel;
         *Wurzel = (*Wurzel)->Next;
         free(WorkPtr);
         gefunden = 1;
      }
      else
      {
         /* Liste durchsuchen */
         WorkPtr = *Wurzel;
         while ((WorkPtr->Next != NULL) && !gefunden)
         {
            /* solange kein Listenende und nicht gefunden */
            if (WorkPtr->Next->Key == Daten)
            {
               /* Nachfolger des aktuellen Elements ist das gesuchte */
               MerkPtr = WorkPtr->Next;
               WorkPtr->Next = MerkPtr->Next;
               free(MerkPtr);
               gefunden = 1;
            }
            else
               /* noch nicht gefunden -> weitersuchen */
               WorkPtr = WorkPtr->Next;
         }
      }
   }
   return(gefunden);
}

ListeKnoten ListeFinde(Liste Wurzel, ListeKeyType Key)
{  ListeKnoten WorkPtr;
   int gefunden;

   if (Wurzel == NULL)
      /* die Liste ist leer */
      return(NULL);
   else
   {
      gefunden = 0;
      WorkPtr = Wurzel;
      while ((WorkPtr != NULL) && !gefunden)
      {
         /* solange kein Listenende und nicht gefunden */
         if (WorkPtr->Key == Key)
            /* gefunden */
            gefunden = 1;
         else
            /* noch nicht gefunden -> weitersuchen */
            WorkPtr = WorkPtr->Next;
      }
      return(WorkPtr);
   }
}

liste.pas

(* Da der Datentyp der Liste erst bei einer konkreten Anwendung  *)
(* feststeht, ist die Liste nur als Beispiel und nicht als Modul *)
(* programmiert.                                                 *)

type
   ListeKeyType = long_integer;
   ListeElement = record
      Key : ListeKeyType;
      Next : ^ListeElement;
   end;
   ListeKnoten = ^ListeElement;
   Liste = ListeKnoten;

procedure ListeCreate(var Wurzel : Liste);
begin
   Wurzel := nil;
end;

procedure ListeInsert(var Wurzel:Liste; Daten : ListeKeyType);
var
   WorkPtr, NewElement : ListeKnoten;
   fertig : boolean;
begin
   (* neues Listenelement erzeugen *)
   new(NewElement);
   NewElement^.Key := Daten;
   (* Listenelement einfuegen *)
   if (Wurzel = nil) then
   begin
      (* Liste ist leer -> als erstes Element einfuegen *)
      NewElement^.Next := nil;
      Wurzel := NewElement;
   end
   else
   begin
      (* die einzufuegende Stelle suchen *)
      if (NewElement^.Key <= Wurzel^.Key) then
      begin
         (* als erstes Element einfuegen, da kleinster Schluessel *)
         NewElement^.Next := Wurzel;
         Wurzel := NewElement;
      end
      else 
      begin
         (* Liste durchlaufen *)
         WorkPtr :=>Wur nil) and not fertig) do
         begin
            if (WorkPtr^.Next^.Key > NewElement^.Key) then
            begin
               (* Der Nachfolger der aktuellen Position hat
                  einen groesseren Schluessel -> einfuegen *)
               NewElement^.Next := WorkPtr^.Next;
               WorkPtr^.Next := NewElement;
               fertig := true;
            end
            else
               (* noch nicht gefunden -> Liste weiter durchsuchen *)
               WorkPtr := WorkPtr^.Next;
         end;
         if (not fertig) then
         begin
            (* Es wurde in der Liste keine Stelle zum Einfuegen
               gefunden -> am Ende anhaengen *)
            NewElement^.Next := nil;
            WorkPtr^.Next := NewElement;
         end;
      end;
   end;
end;

procedure ListeDelete(var Wurzel:Liste; Daten:ListeKeyType);
var
   WorkPtr, MerkPtr : ListeKnoten;
   gefunden : boolean;
begin
   if (Wurzel <> nil) then
   begin
      (* Die Liste enthaelt Elemente *)
      if (Wurzel^.Key = Daten) then
      begin
         (* das erste Element ist das gesuchte *)
         WorkPtr := Wurzel;
         Wurzel := Wurzel^.Next;
         dispose(WorkPtr);
      end
      else
      begin
         (* Liste durchsuchen *)
         gefunden := false;
         WorkPtr := Wurzel;
         while ((WorkPtr^.Next <> nil) and not gefunden) do
         begin
            (* solange kein Listenende und nicht gefunden *)
            if (WorkPtr^.Next^.Key = Daten) then
            begin
               (* Nachfolger des aktuellen Elements ist das gesuchte *)
               MerkPtr := WorkPtr^.Next;
               WorkPtr^.Next := MerkPtr^.Next;
               dispose(MerkPtr);
               gefunden := true;
            end
            else
               (* noch nicht gefunden -> weitersuchen *)
               WorkPtr := WorkPtr^.Next;
         end;
      end;
   end;
end;

function ListeFinde(Wurzel:Liste; Key:ListeKeyType):ListeKnoten;
var
   WorkPtr : ListeKnoten;
   gefunden : boolean;
begin
   if (Wurzel = nil) then
      (* die Liste ist leer *)
      ListeFinde := nil
   else
   begin
      gefunden := false;
      WorkPtr := Wurzel;
      while ((WorkPtr <> nil) and not gefunden) do
      begin
         (* solange kein Listenende und nicht gefunden *)
         if (WorkPtr^.Key = Key) then
            (* gefunden *)
            gefunden := true
         else
            (* noch nicht gefunden -> weitersuchen *)
            WorkPtr := WorkPtr^.Next;
      end;
      ListeFinde := WorkPtr;
   end;
end;

liste.mod

(* Da der Datentyp der Liste erst bei einer konkreten Anwendung  *)
(* feststeht, ist die Liste nur als Beispiel und nicht als Modul *)
(* programmiert.                                                 *)

FROM Heap IMPORT Allocate, Deallocate;
FROM SYSTEM IMPORT TSIZE;

TYPE
   ListeKeyType = LONGINT;
   ListeKnoten = POINTER TO ListeElement;
   ListeElement = RECORD
      Key : ListeKeyType;
      Next : ListeKnoten;
   END;
   Liste = ListeKnoten;

PROCEDURE ListeCreate(VAR Wurzel : Liste);
BEGIN
   Wurzel := NIL;
END ListeCreate;

PROCEDURE ListeInsert(VAR Wurzel:Liste; Daten : ListeKeyType);
VAR
   WorkPtr, NewElement : ListeKnoten;
   fertig : BOOLEAN;
BEGIN
   (* neues Listenelement erzeugen *)
   Allocate(NewElement,TSIZE(ListeElement));
   NewElement^.Key := Daten;
   (* Listenelement einfuegen *)
   IF (Wurzel = NIL) THEN
      (* Liste ist leer -> als erstes Element einfuegen *)
      NewElement^.Next := NIL;
      Wurzel := NewElement;
   ELSE
      (* die einzufuegende Stelle suchen *)
      IF (NewElement^.Key <= Wurzel^.Key) THEN
         (* als erstes Element einfuegen, da kleinster Schluessel *)
         NewElement^.Next := Wurzel^.Next;
         Wurzel := NewElement;
      ELSE
         (* Liste durchlaufen *)
         WorkPtr := Wurzel;
         fertig := F>LSE NewElement^.Key) THEN
               (* Der Nachfolger der aktuellen Position hat
                  einen groesseren Schluessel -> einfuegen *)
               NewElement^.Next := WorkPtr^.Next;
               WorkPtr^.Next := NewElement;
               fertig := TRUE;
            ELSE
               (* noch nicht gefunden -> Liste weiter durchsuchen *)
               WorkPtr := WorkPtr^.Next;
            END;
         END;
         IF (NOT fertig) THEN
            (* Es wurde in der Liste keine Stelle zum Einfuegen
               gefunden -> am Ende anhaengen *)
            NewElement^.Next := NIL;
            WorkPtr^.Next := NewElement;
         END;
      END;
   END;
END ListeInsert;

PROCEDURE ListeDelete(VAR Wurzel:Liste; Daten:ListeKeyType);
VAR
   WorkPtr, MerkPtr : ListeKnoten;
   gefunden : BOOLEAN;
BEGIN
   IF (Wurzel # NIL) THEN
      (* Die Liste enthaelt Elemente *)
      IF (Wurzel^.Key = Daten) THEN
         (* das erste Element ist das gesuchte *)
         WorkPtr := Wurzel;
         Wurzel := Wurzel^.Next;
         Deallocate(WorkPtr,TSIZE(ListeElement));
      ELSE
         (* Liste durchsuchen *)
         gefunden := FALSE;
         WorkPtr := Wurzel;
         WHILE ((WorkPtr^.Next # NIL) AND NOT gefunden) DO
            (* solange kein Listenende und nicht gefunden *)
            IF (WorkPtr^.Next^.Key = Daten) THEN
               (* Nachfolger des aktuellen Elements ist das gesuchte *)
               MerkPtr := WorkPtr^.Next;
               WorkPtr^.Next := MerkPtr^.Next;
               Deallocate(MerkPtr,TSIZE(ListeElement));
               gefunden := TRUE;
            ELSE
               (* noch nicht gefunden -> weitersuchen *)
               WorkPtr := WorkPtr^.Next;
            END;
         END;
      END;
   END;
END ListeDelete;

PROCEDURE ListeFinde(Wurzel:Liste; Key:ListeKeyType):ListeKnoten;
VAR
   WorkPtr : ListeKnoten;
   gefunden : BOOLEAN;
BEGIN
   IF (Wurzel = NIL) THEN
      (* die Liste ist leer *)
      RETURN NIL;
   ELSE
      gefunden := FALSE;
      WorkPtr := Wurzel;
      WHILE ((WorkPtr # NIL) AND NOT gefunden) DO
         (* solange kein Listenende und nicht gefunden *)
         IF (WorkPtr^.Key = Key) THEN
            (* gefunden *)
            gefunden := TRUE;
         ELSE
            (* noch nicht gefunden -> weitersuchen *)
            WorkPtr := WorkPtr^.Next;
         END;
      END;
      RETURN WorkPtr;
   END;
END ListeFinde;

English version not yet available.