|
Hauptseite - Welches System? - Hardware - Software - Emulatoren - |
Internet MausNet Programmieren Verweise Über |
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 |
/* 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); } }
(* 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;
(* 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. |