Implementierung verketteter Listen
Verkettete Listen gehören zu den bekanntesten Datenstrukturen und werden in fast jedem Lehrbuch beschrieben. Doch gibt es bei der üblichen Implementierung noch einige Verbesserungsmöglichkeiten, von denen hier zwei vorgestellt werden. Erstens wird das Einfügen in eine Liste besser handhabbar gemacht, und zweitens wird das Durchsuchen einer Liste beschleunigt. Dazu kann man dieselben Typdefinitionen benutzen wie üblich, wenn man sie nur etwas geschickter gebraucht.
Zunächst will ich die Definitionen in LISTE.H erläutern. Als erstes sehen Sie die Definition des Strukturtyps TNode, mit dem die Knoten einer Liste dargestellt werden sollen. Wie üblich gibt es als Strukturelement einen Zeiger next, der auf den Nachfolgerknoten zeigt, und ein zweites Element, pval, zur Aufnahme der Daten (für das zweite Element wird häufig ein spezieller Datentyp benutzt; wenn Sie es jedoch wie hier als void-Zeiger deklarieren, können Sie die Listen zur Aufnahme beliebiger Daten verwenden).
Der Typ TList ist einfach nur ein anderer Name für TNode. Den Sinn dieser Definition werde ich weiter unten erläutern.
Der Typ TCmpF beschreibt einen Zeiger auf eine Funktion vom Typ int mit zwei void-Zeigern als Parameter. Er wird für Vergleichsfunktionen benutzt. Solche Vergleichsfunktionen werden zum Durchsuchen einer Liste und zum sortierten Einfügen benötigt. Für die Rückgabewerte gilt die Konvention: Wert < 0, falls e1 < e2; Wert > 0, falls e2 > e1; Wert = 0, falls e1 = e2. So verhalten sich auch Standardfunktionen wie strcmp.
Der Typ Tv_pv beschreibt einen Zeiger auf eine void-Funktion mit einem void-Zeiger als Parameter. Ein solcher Funktionszeiger wird in ls_ForAll benutzt, um auf alle Elemente einer Liste eine Funktion anzu wenden.
Einfügen
Um mit einer Liste zu arbeiten, benutzt man normalerweise einen Zeiger (den Anker) auf den ersten Knoten der Liste. Bei der Realisierung der Einfügefunktion ergibt sich hieraus aber ein Problem: Das Einfügen eines neuen Eintrags an den Anfang der Liste unterscheidet sich vom Einfügen als Nachfolger eines Knotens. Siebrauchen also zwei Einfügefunktionen oder eine Funktion mit Fallunterscheidung. Eine weitere Fallunterscheidung ist für die leere Liste nötig, da diese durch einen NULL-Zeiger dargestellt wird.
Das Häßliche dabei ist, daß man beim Einfügen am Anfang der Liste den Anker verändern muß, da ja nun die Liste mit einem anderen Knoten beginnt (das gleiche gilt natürlich für das Entfernen eines Eintrags aus der Liste). Ein solches Verhalten ist eigentlich nicht tragbar, schließlich kann sich ja auch die Adresse eines Arrays nicht ändern, wenn man darin etwas einträgt. Überdies kann es leicht eine Ursache von Fehlern sein, denn wenn man z.B. mit mehreren Zeigern auf dieselbe Liste arbeitet, müßte man sicherstellen, daß diese ggf. alle neu gesetzt werden.
Wenn Sie bereit sind, pro Liste einige wenige Bytes mehr zu opfern, können Sie dieses Problem sehr leicht umgehen und ganz nebenbei noch das Durchsuchen einer Liste beschleunigen. Dazu werden für jede Liste zwei Dummy-Knoten benutzt. Der erste steht immer am Anfang der Liste, also vor dem ersten Eintrag, und dient als Anker. Der zweite steht immer am Ende der Liste, also nach dem letzten Eintrag. Zusätzlich wird noch die Adresse des End-Dummy-Knotens in den pval-Zeiger des Ankers geschrieben. In Bild 1 (oben) ist dargestellt, wie eine Liste mit diesen zusätzlichen Dummy-Knoten aussieht. Auch die leere Liste besitzt diese Dummy-Knoten [Bild 1 (unten)].
Die Funktion ls_Create in LISTE.C dient dazu, eine neue leere Liste anzulegen. Sie stellt die beiden Dummy-Knoten in der beschriebenen Weise zur Verfügung und gibt einen Zeiger auf den Ankerknoten zurück.
Was ist damit nun gewonnen? Schauen Sie sich die Funktion ls_Insert an. Sie fügt einen neuen Eintrag e als Nachfolger eines Knotens n in die Liste ein. Wenn wir nun für n den Ankerknoten übergeben, wird e also als Nachfolger des Ankers eingetragen. Damit ist e der erste Eintrag der Liste, denn der Nachfolger des Ankers ist das erste Element der Liste. ls_Insert kann also innerhalb der Liste, am Anfang der Liste und in die leere Liste Elemente einfügen und benötigt dazu keine Fallunterscheidungen. Vor allem aber kann sich nun durch das Einfügen am Anfang der Liste der Anker nicht mehr ändern. Entsprechend funktioniert auch das Entfernen von Einträgen aus der Liste (ls_RmNext) ohne Probleme.
Nun können Sie auch den Sinn des Typs TList verstehen. Mit diesem Typ kann man Programme besser lesbar machen: Ein Zeiger, der als Anker dienen soll, sollte stets als TList* deklariert werden, denn der Anker repräsentiert ja die Liste als Ganzes. Außerdem sollte man einen TList-Zeiger außer beim Anlegen einer neuen Liste nicht verändern, und wie Sie gesehen haben, braucht man das ja auch nicht. Als TNode* deklariert man dagegen Zeiger, die auf irgend einen Knoten einer Liste zeigen können.
Beschleunigte Suche mit Wächtern
Wozu dient nun der Dummy-Knoten am Listenende? Man kann ihn benutzen, um mittels der Wächter-(oder Sentinel-)Technik das Durchsuchen einer Liste zu beschleunigen. Normalerweise wird eine Liste durchsucht, indem für jeden Knoten geprüft wird, ob er den gesuchten Eintrag enthält oder ob das Listenende erreicht ist. Der zweite Vergleich, der auf das Listenende, ist jedoch überflüssig, wenn man dafür sorgt, daß das gesuchte Element immer gefunden wird.
Betrachten Sie die Funktion ls_Search. Diese Funktion dient dazu, in der Liste nach einem Element zu suchen. Sie erwartet als Parameter einen void-Zeiger p, das ist ein Zeiger auf das gesuchte Element, einen Zeiger a auf den Ankerknoten und einen Funktionszeiger cmp vom Typ TCmpF, also eine Vergleichsfunktion. Zunächst wird end ein Zeiger auf den Dummy-Endknoten zugewiesen. Den bekommt man über den pval-Zeiger des Ankers. Nun kann man den Wächter einsetzten, d.h. man schreibt p in den pval-Zeiger des Dummy-Endknotens. Anschließend wird in einer while-Schleife die Liste durchlaufen, bis ein Element gefunden ist, das gleich p ist. Durch den Wächter ist sichergestellt, daß diese Schleife immer ordnungsgemäß beendet wird. Nach dem Ende der Schleife zeigt n auf einen Knoten, der ein Element gleich p enthält. Zunächst wird der Wächter wieder entfernt, dann wird geprüft, ob n gleich end ist. Ist das der Fall, so kann die Liste das gesuchte Element nicht enthalten, da die Suche in diesem Fall ja erst beim Wächter abgebrochen wurde. Somit wird NULL zurückgegeben. Ist dagegen n verschieden von end, dann enthält die Liste p, und es wird n zurückgegeben.
Die gleiche Methode wird in ls_SInsert angewandt. Diese Funktion dient zum sortierenden Einfügen, d.h., wird eine Liste mit ls_SInsert aufgebaut, so ist sie gemäß der Vergleichsfunktion cmp sortiert.
Weitere Funktionen
LISTE.C enthält noch drei nützliche Funktionen. ls_ForAll führt die übergebene Funktion func für alle Einträge einer Liste aus, ls_Free gibt alle Knoten einer Liste frei, ls_VFree gibt zusätzlich noch den Speicher unter pval frei, wofür die Funktion ff benutzt wird.
Das Demoprogramm
In LISTDEMO.C werden einige der angesprochenen Funktionen benutzt. Das compilierte Programm ist ein TTP-Programm, das den Namen einer ASCII-Datei (wie z.B. INPUT.TXT) als Argument erwartet. Es wird dann eine Liste von Strings aufgebaut, und zwar in der Reihenfolge, wie sie in der Datei stehen. Schließlich wird noch der String „Listenanfang“ am Anfang eingefügt und das ganze mittels ls_ForAll ausgegeben. Danach wird noch die Suchfunktion ls_Search demonstriert, und zum Schluß die ganze Liste samt der allozierten Strings mittels ls_VFree freigegeben.
Doppelt verkettete Listen
Manchmal ist es nötig, sich in einer Liste in beide Richtungen bewegen zu können. Dazu benutzt man dann bekanntlich doppelt verkettete Listen. Die Dummy-Knoten und die Wächtertechnik kann man natürlich bei doppelt verketteten Listen ganz genauso einsetzen wie bei einfach verketteten. Daher will ich auch nur noch eine Besonderheit ansprechen.
In Bild 2 ist eine doppelt verkettete Liste dargestellt. Dabei fällt auf, daß der prev-Zeiger des Ankerknotens nicht, wie vielleicht erwartet, auf NULL gesetzt ist, sondern auf den Anker selbst zeigt.
Einfügen
Neben einer Funktion dl_InsNext (DLISTE.C) zum Einfügen als Nachfolger eines Knotens möchte man auch eine Funktion dl_InsPrev, um vor einem Knoten einfügen zu können. Diese Funktion sollte auch mit dl_InsNext (bzw. ls_Insert) konsistent sein, d.h., sie sollte auch den Anker als Parameter akzeptieren und in diesem Fall am Anfang der Liste einfügen.
Eine solche Funktion braucht man nicht eigens zu implementieren, sondern man kann dl_lnsNext benutzen. Dazu braucht man sich nur zu überlegen, daß die Operation „füge e als Vorgänger von n ein“ genau dasselbe leistet wie „füge e als Nachfolger des Vorgängers von n ein“. Man realisiert dl_InsPrev also als Makro, und zwar so, daß aus dem Aufruf dl_InsPrev(n, p) der Aufruf dl_InsNext(n->prev,p) wird (DLISTE.H). Was geschieht nun, wenn man dl_InsPrev mit einem Zeiger a auf den Ankerknoten aufruft? Weil wir schlauerweise den prev-Zeiger von a auf a selbst gesetzt haben, wird dl_InsNext mit einem Zeiger auf den Anker aufgerufen und fügt es somit als erstes Element der Liste ein.
Auf ein Demoprogramm für doppelt verkettete Listen habe ich verzichtet, Sie können LISTDEMO.C leicht selbst entsprechend ändern.
#ifndef __LIST__
#define __LIST__
/*
* ---------------------- Typdefinitionen ---------
*/
typedef struct TNode{
struct TNode *next;
void *pval;
} TNode;
typedef TNode TList;
typedef int ( *TCmpF) ( void *e1, void *e2);
typedef void ( *Tv_pv) ( void *p);
/*
* -------------------- Prototypen -------------
*/
TList *ls_Create() void);
TNode *ls_Insert( TNode *n, void *e);
TNode *ls_SInsert( TList *a, void *e, TCmpF cmp);
TNode *ls_RmNext( TNode *n);
void ls_ForAll( TList *a, Tv_pv func);
TNode *ls_Search( void *p, TList *a, TCmpF cmp);
void ls_Free( TList *a);
void ls_VFree( TList *a, Tv_pv ff);
#endif /* __LIST__ */
/*
* Dieses Modul stellt einfach verkettete Listen
* und dazugehörige Funktionen zur Verfügung.
* Entwickelt mit Pure C von K. Rindfrey.
* (c) MAXON Computer 1993
*/
#include <stdlib.h>
#include <stdio.h>
#include "list.h"
#define N_ALLOC() malloc( sizeof( TNode))
/*
* N_ALLOC reserviert Speicher für ein
* Element vom Typ TNode.
*/
TList *ls_Create()
/*
* Legt eine neue Liste an.
* Rückgabe: Zeiger auf eine leere Liste
*/
{
register TNode *a, /* Anker. */
*e; /* Ende der Liste */
if( ( a = N_ALLOC()) == NULL ||
( e = N_ALLOC()) == NULL) return( NULL);
a->pval = a->next = e;
e->pval = e->next = NULL;
return( ( TList *) a);
}
TNode *ls_Insert( TNode *a, void *e)
/*
* Fügt e als Nachfolger von n ein.
* Rückgabe : Zeiger auf Nachfolgerknoten von n.
*/
{
register TNode *neu;
if( ( neu = N_ALLOC()) == NULL)
return( NULL);
neu->pval = e;
neu->next = n->next;
n->next = neu;
return( neu);
}
TNode *ls_SInsert( TList *a, void *e, TCmpF cmp)
/*
* Fügt e in die Liste a ein. Das Einfügen
* erfolgt sortiert mit cmp als
* Vergleichsfunktion.
*/
{
TNode *n, *nold, *end;
n = a->next;
nold = a;
end = ( TNode *)a->pval;
end->pval = e; /* Wächter setzen */
while( ( *cmp)( e, n->pval) > 0){
nold = n;
n = n->next;
}
end->pval = NULL; /* Wächter entfernen */
return( ls_Insert( nold, e));
}
TNode *ls_RmNext ( TNode *a)
/*
* Entferne Nachfolgerknoten von n.
* Rückgabe: Zeiger auf den entfernten Knoten.
*/
{
register TNode *d;
d = n->next;
if( d->next == NULL) return( NULL);
n->next = d->next;
return( d);
}
TNode *ls_Search( void *p, TList *a, TCmpF cmp)
/*
* Suche Eintrag p in Liste a mit der
* Vergleichsfunktion cmp.
* Rückgabe : Zeiger auf den Knoten mit
* Eintrag p; NULL falls p nicht gefunden
*/
{
TNode *n, *end;
end = ( TNode *)a->pval;
end->pval = p; /* Wächter setzen */
n = a->next;
while( ( *cmp)(p, n->pval) != 0)
n = n->next;
end->pval = NULL; /* Wächter entfernen */
return( n == end ? NULL : n);
}
void ls_ForAll( TList *a, Tv_pv func)
/*
* Wendet die Funktion func auf
* alle Einträge der Liste a an.
*/
{
TNode *n;
n = a->next;
while( n->next != NULL){
( *func) ( n->pval);
n = n->next;
}
}
void ls_Free( TList *a)
/*
* Gibt die Knoten der Liste frei
*/
{
TNode *n, *nold;
nold = a;
n = a->next;
while( n->next != NULL){
free( nold);
nold = n;
n = n->next;
}
free( nold);
}
void ls_VFree( TList *a, Tv_pv ff)
/*
* Gibt die Knoten der Liste und den
* Inhalt frei.
* ff ist eine Funktion zur Freigabe der Daten
* unter pval.
*/
{
TNode *n, *nold;
nold = n = a->next;
free( a) ;
while( n->next != NULL){
( *ff)( nold->pval);
free( nold);
nold = n; n = n->next;
}
free( nold);
}
listdemo.ttp
=
PCXSTART.O
listdemo.c (list.h)
list.c (list.h)
PCSTDLIB.LIB
/*
* Demo für einfach verkettete Listen.
* Aufruf: listdemo <textfile>
* (c) MAXON Computer 1993
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include “list.h"
static const char such_str[] = "Heinrich";
/* Suchstring zur Demonstration von ls_Search */
/*
* ------------------ main --------------------
*/
int main( int argc, const char *argv[])
{
FILE *fp;
TList *lst;
TNode *n;
char str[ 80];
if( argc != 2){
puts( "Argumentliste falsch!");
exit( 1);
}
if( ( fp = fopen( argv[ 1], "r")) == NULL){
puts( "Kann Datei nicht öffnen");
exit( 1);
}
/* Liste anlegen */
lst = n = ls_Create();
/* Strings einlesen und gemallocte Kopien
* in die Liste eintragen */
while( !feof( fp)){
if( fscanf( fp, "%s", str) > 0)
n = ls_Insert( n, strdup( str));
}
fclose( fp);
/* "Listenanfang!" an den Listenanfang */
ls_Insert( lst, strdup( "Listenanfang!"));
/* Alles mit puts ausgeben */
ls_ForAll( lst, (Tv_pv)puts);
/* Suche nach such_str */
if( ls_Search( such_str, lst, (TCmpF) strcmp) != NULL)
puts( "\nSuchstring gefunden!");
else
puts( "\nSuchstring nicht gefunden!");
/* Knoten und Strings freigeben */
ls_VFree( lst, free);
return( 0);
}
#ifndef __DLIST__
#define __DLIST__
/*
* --------------------- Typdefinitionen --------
*/
typedef struct TDNode{
struct TDNode *next;
struct TDNode *prev;
void *pval;
} TDNode ;
typedef TDNode TDList;
typedef int ( *TCmpF) ( void *e1, void *e2);
typedef void ( *Tv_pv) ( void *p);
/*
* ---------------------- Defines ----------------
*/
#define dl_InsPrev(n,e) dl_InsNext((n)->prev,e)
/*
* Fügt e als Vorgänger von n ein.
* Rückgabe : Zeiger auf Vorgängerknoten von n.
*/
/*
*---------------------- Prototypen ---------------
*/
TDList *dl_Create( void) ;
TDNode *dl_InsNext( TDNode *np, void *ep);
TDNode *dl_Remove( TDNode *n);
TDNode *dl_Search( void *p, TDList *a, TCmpF cmp);
TDNode *dl_RevSearch( void *p, TDList *a, TCmpF cmp);
void dl_ForAll( TDList *a, Tv_pv func);
#endif /* __DLIST__ */
/*
* Dieses Modul stellt doppelt verkettete Listen
* und dazugehörige Funktionen zur Verfügung.
* Entwickelt mit Pure C von K. Rindfrey.
* (c) MAXON Computer 1993
*/
#include <stdlib.h>
#include <stdio.h>
#include “dlist.h"
#define DN_ALLOC() malloc( sizeof( TDNode))
/*
* ND_ALLOC reserviert Speicher für ein
* Element vom Typ TDNode.
*/
TDList *dl_Create()
/*
* Legt eine doppelt verkettete Liste an.
* Rückgabe: Zeiger auf eine leere Liste
*/
{
register TDNode *a, /* Anker */
*e; /* Ende der Liste */
if( (a = DN_ALLOC()) == NULL ||
(e = DN_ALLOC()) == NULL) return( NULL);
a->pval = a->next = e;
a->prev = a;
e~>pval = e->next = NULL;
e->prev = a;
return( ( TDList *) a);
}
TDNode *dl_InsNext( TDNode *n, void *e)
/*
* Füge e als Nachfolger von n ein.
* Rückgabe : Zeiger auf Nachfolgerknoten von n.
*/
{
register TDNode *neu;
if( ( neu = DN_ALLOC()) == NULL)
return( NULL);
neu->pval = e;
neu->next = n->next;
neu->prev = n;
neu->next->prev = neu;
n->next = neu;
return( neu);
}
TDNode *dl_Remove( TDNode *n)
/*
* Entferne Knoten *n
* Rückgabe n bzw. NULL
*/
{
register TDNode *next, *prev;
if( ( prev = n->prev) == n)
return( NULL); /* Anker nicht entfernen */
next = n->next;
prev->next = next;
next->prev = prev;
return( n);
}
TDNode *dl_Search( void *p, TDList *a, TCmpF cmp)
/*
* Suche Eintrag p in Liste a mit der
* Vergleichsfunktion cmp.
* Rückgabe : Zeiger auf den Knoten mit
* Eintrag p; NULL falls p nicht gefunden
*/
{
TDNode *n, *end;
end = ( TDNode *)a->pval;
end->pval = p; /* Wächter setzen */
n = a->next;
while( ( *cmp)(p, n->pval) != 0)
n = n->next;
end->pval = NULL; /* Wächter entfernen */
return( n == end ? NULL : n);
}
TDNode *dl_RevSearch( void *p, TDList *a, TCmpF cmp)
/*
* Durchsucht die Liste a wie dl_Search,
* jedoch in umgekehrter Richtung,
* beginnend mit dem Endknoten.
*/
{
TDNode *n, *end;
end = ( TDNode *)a->pval;
a->pval = p; /* Wächter setzen */
n = end->prev;
while( ( *cmp)(p, n->pval) != 0)
n = n->prev;
a->pval = end; /* Zeiger restaurieren */
return( n == a ? NULL ; n);
}
void dl_ForAll( TDList *a, Tv_pv func)
/*
* Wendet die Funktion func auf
* alle Einträge der Liste a an.
*/
{
TDNode *n;
n = a->next;
while( n->next != NULL){
( *func)( n->pval);
n = n->next;
}
}
Klaus Rindfrey