Atari Computer

Beispiel: doppelt verkettete Liste

Die folgenden Beispiele zeigen eine doppelt verkettete Liste.

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

dliste.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 *Prev;
   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(ListeKnoten));
   if (NewElement != NULL)
   {
      NewElement->Key = Daten;
      /* Listenelement einfuegen */
      if (*Wurzel == NULL)
      {
         /* Liste ist leer -> als erstes Element einfuegen */
         NewElement->Prev = NULL;
         NewElement->Next = NULL;
         *Wurzel = NewElement;
      }
      else
      {
         /* die einzufuegende Stelle suchen */
         if (NewElement->Key <= (*Wurzel)->Key)
         {
            /* als erstes Element einfuegen, da kleinster Schluessel */
            (*Wurzel)->Prev = NewElement;
            NewElement->Prev = NULL;
            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->Prev = NewElement;
                  NewElement->Prev = WorkPtr;
                  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->Prev = WorkPtr;
               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;
         (*Wurzel)->Prev = NULL;
         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;
               MerkPtr->Next->Prev = WorkPtr;
               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);
   }
}

dliste.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;
   ListeKnoten = ^ListeElement;
   ListeElement = record
      Key : ListeKeyType;
      Prev : ListeKnoten;
      Next : ListeKnoten;
   end;
   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^.Prev := nil;
      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 *)
         Wurzel^.Prev := NewElement;
         NewElement^.Prev := nil;
         NewElement^.Next := Wurzel;
         Wurzel := NewElement;
      end
     >els 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^.Prev := NewElement;
               NewElement^.Prev := WorkPtr;
               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^.Prev := WorkPtr;
            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;
         Wurzel^.Prev := nil;
         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;
               MerkPtr^.Next^.Prev := WorkPtr;
               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;

dliste.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;
      Prev : ListeKnoten;
      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^.Prev := NIL;
      NewElement^.Next := NIL;
      Wurzel := NewElement;
   ELSE
      (* die einzufuegende Stelle suchen *)
      IF (NewElement^.Key <= Wurzel^.Key) THEN
         (* als erstes Element einfuegen, da kleinster Schluessel *)
         Wurzel^.Prev := NewElement;
         NewElement^.Prev := NIL;
         NewElement^.Next := Wurzel;
         Wurzel := NewElement;
      ELSE
         (* List> du NewElement^.Key) THEN
               (* Der Nachfolger der aktuellen Position hat
                  einen groesseren Schluessel -> einfuegen *)
               NewElement^.Next := WorkPtr^.Next;
               WorkPtr^.Next^.Prev := NewElement;
               NewElement^.Prev := WorkPtr;
               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^.Prev := WorkPtr;
            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;
         Wurzel^.Prev := NIL;
         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;
               MerkPtr^.Next^.Prev := WorkPtr;
               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.