Listenverarbeitung in C 

Listenverarbeitung

Reihungen  können zwar in alloziertem Speicher bei Bedarf auch eine erst zur Laufzeit bestimmte Größe haben, sie unterstützen das

• Einfügen oder
• Löschen von Komponenten (mit Verschieben der folgenden Komponenten und Veränderung der Länge der Reihung)

aber nicht direkt. Wenn solche Operationen direkt unterstützt werden, spricht man von einer Liste (von Werten).

Als Schnittstelle  („abstrakter Datentyp“, „API“) ist eine Liste durch eine bestimmte Menge von Operationen definiert:

• Veränderungen: Einfügen, Ändern oder Löschen einer Komponente an einer bestimmten Position
• Auswertungen: Durchlaufen aller Komponente der Liste (von der ersten bis zur letzten)
• (eventuelle weitere ergänzende Operationen)

Eine Implementation  ist die Umsetzung (Realisierung) dieser Operationen durch konkrete Funktionen.

Wiederverwendung

Die Wiederverwendung  von Programmen und Programmteilen soll helfen, Arbeit zu sparen und die Qualität zu erhöhen.

• Oft kostet es weniger Zeit, eine fertige Bibliothek (Sammlung von Entitäten) zu verwenden, als sie neu zu schreiben; auch wenn dabei Zeit zur Suche, Auswahl und Einarbeitung anfällt.
• Wenn eine ausgereifte Bibliothek verwendet wird, dann werden in ihr oft schon viele Fehler gefunden und beseitigt worden sein; möglicherweise enthält sie auch schon besonders effiziente Algorithmen.

Die Implementation einer Liste bietet sich besonders zur Wiederverwendung an, weil sie ein weitverbreitetes Standardproblem ist. Bei der Softwareentwicklung sollten für weitverbreitete Standardprobleme vorhandene Bibliotheken eingesetzt werden, damit der Programmierer sich auf die Lösung der spezifischen Probleme seines Projekts konzentrieren kann.

Die Bibliothek simclist  bietet beispielsweise eine Implementation von Listen für C -Programme unter der recht liberalen BSD -Lizenz. Sie ist schon recht ausgereift und stellt sicher, daß viele Aufgaben elegant und effizient erledigt werden könnten. Die Neuentwicklung einer entsprechenden Listenbibliothek würde entsprechend viel Zeit kosten.

Dokumentation

http://mij.oltrelinux.com/devel/simclist/simclist.h

Da mehr als sechs externe Bezeichner als signifikant vorausgesetzt werden und die Bibliothek das C99 -Schlüsselwort »restrict« verwendet, kann sie allerdings zunächst nur mit einem C99 -Compiler zusammen verwendet werden (notfalls könnte sie aber auch entsprechend umgeschrieben werden).

Es folgt ein Beispielprogramm zum Einlesen, Sortieren und Ausgeben einer Liste.

list0.c

#include <stdio.h>                   /* scanf, printf */
#include <stdlib.h>                  /* EXIT_SUCCESS  */

#include "simclist-1.4.3/simclist.h" /* list_...      */

int appendvalue( list_t * const list, int looping )
{ int value;
  scanf( "%d", &value );
  if( value >= 0 )list_append( list, &value );
  else looping = 0;
  return looping; }

void read( list_t * const list )
{ int looping = 1; while( looping )
  { looping = appendvalue( list, looping ); }}

void sort( list_t * const list )
{ list_attributes_comparator( list, list_comparator_int32_t );
  list_sort( list, -1 ); }

void print( list_t * const list )
{ list_iterator_start( list );
  while( list_iterator_hasnext( list ))
  { void * next = list_iterator_next( list );
    printf( "%d\n", *( int * )next ); }
  list_iterator_stop( list ); }

void main2( list_t * const list )
{ list_attributes_copy( list, list_meter_int32_t, 1 );
  read( list );
  sort( list );
  printf("Sorted values:\n");
  print( list ); }

void main1( list_t * const list )
{ list_init( list );
  main2( list );
  list_destroy( list ); }

int main( void )
{ list_t list;
  main1( &list );
  return EXIT_SUCCESS; }

Konsole

$ wget http://mij.oltrelinux.com/devel/simclist/simclist-1.4.3.tar.bz2

$ tar xvjf simclist-1.4.3.tar.bz2

$ gcc -Wno-implicit -std=c99 list0.c simclist-1.4.3/simclist.c

$ ./a.out
90
10
30
-1
Sorted values:
90
30
10

$ echo $?
0

Das voranstehende Programm war allerdings „optimistisch“ programmiert, also so, als ob alle Laufzeitversuche erfolgreich sein werden. Das folgende Programm enthält Fehlerbehandlungen, die sicherstellen sollen, daß ein korrekter Erfolgsstatus zurückgegeben wird und die normale Ausführung beim Scheitern eines Versuchs nicht fortgesetzt wird, wobei gleichzeitig noch sichergestellt wird, daß alle Ressourcen auch wieder zurückgegeben werden.

Dadurch ist der Quellcode komplizierter als bei „optimistischer Programmierung“. Der „normale“ Ablauf beim Erfolg aller Versuche ist unter dem Kode zur Behandlung von Fehlern verborgen und nicht mehr auf den ersten Blick erkennbar.

Die int-Funktionen des Programms ergeben 0, genau dann wenn kein  Laufzeitfehler auftrat.

list1.c

#include <stdio.h>                   /* scanf, printf */
#include <stdlib.h>                  /* EXIT_SUCCESS  */

#include "simclist-1.4.3/simclist.h" /* list_...      */

int appendvalue( list_t * const list, int *looping )
{ int value;
  if( 1 != scanf( "%d", &value ))return 1;
  if( value >= 0 )
  { if( list_append( list, &value )< 0 )return 2; }
  else *looping = 0; 
  return 0; }

int read( list_t * const list )
{ int looping = 1; while( looping )
  { if( appendvalue( list, &looping ))return 1; }
  return 0; }

int sort( list_t * const list )
{ if( list_attributes_comparator( list, list_comparator_int32_t ))return 1;
  else if( list_sort( list, -1 ))return 2;
  else return 0; }

int print( list_t * const list )
{ if( list_iterator_start( list )<= 0 )
  return 1;
  { while( list_iterator_hasnext( list ))
    { void * next = list_iterator_next( list );
      if( next )
      { if( printf( "%d\n", *( int * )next )< 0 )return 2; }
      else break; }
    if( !list_iterator_stop( list ))return 3; }
  return 0; }

int main2( list_t * const list )
{ if( !list_attributes_copy( list, list_meter_int32_t, 1 ))
  { if( read( list ))return 1;
    else if( sort( list ))return 2;
    { printf("Sorted values:\n");
      if( print( list ))return 3; }}}

int main1( list_t * const list )
{ if( list_init( list ))return 1;
  { if( main2( list ))return 2;
    list_destroy( list ); }
  return 0; }

int main( void )
{ list_t list;
  return main1( &list )? EXIT_FAILURE : EXIT_SUCCESS; }

In dem obigen Programmstück ergeben die Funktionen (außer »main«) 0 bei Erfolge und einen Fehlercode sonst. Eine Funktion kann aber die Fehlercodewerte der von ihr aufgerufenen Funktionen nicht direkt weitergeben, da zwei Funktionen denselben Codewerte zurückgeben könnten, dessen Bedeutung dann nicht mehr klar wäre. Daher gibt jede Funktion spezielle Fehlercodes zurück. Hierbei ersetzt der Quellcode die Dokumentation der Fehlercodes, was nicht immer richtig ist.

Da »appendvalue« jetzt auch einen Fehlercode zurückgibt, wird dieser Funktion nun nicht mehr der Wert, sondern die Adresse des Objekts »looping« übergeben, damit sie dieses Objekt verändern kann.

/    Übung

Das obige Programm enthält noch mindestens einen Fehler: Auch, bei fehlerfreien Ablauf gibt es oft einen Fehlerstatus zurück. Um den Fehler zu finden, soll die Rückgabe der Fehlerwerte verfolgt werden. Dazu werden die Rückgabeanweisungen mit einem vim -Kommando durch Makroaufrufe ersetzt:

%s/return \([0-9]\)/RAISE(\1)/g

Das Makro »RAISE« kann in C99 so definiert werden, daß es den Namen der aufrufenden Funktion ausgibt.

#define RAISE(i) do{ fprintf( stderr, "%s %d\n", __func__,( i )); return i; }while( 0 )

In C90 kann immerhin die Zeilennummer ausgegeben werden.

#define RAISE(i) do{ fprintf( stderr, "%d %d\n", __LINE__,( i )); return i; }while( 0 )

(Die do-Anweisung bewirkt, daß ein Makro-Aufruf wie »RAISE(1);« mit einem ihm direkt folgenden Semikolon zusammen eine einzige Anweisung bildet. Dies ist nötig, weil ja auch die ersetze return -Anweisung eine einzige Anweisung war.)

Wird das Programm dann ausgeführt, kann verfolgt werden, ab wann ein nichtverschwindender Fehlerwert zurückgegeben wird, so kann der Fehler dann lokalisiert werden.

Diese Übung zeigt auch, wie ein Programm mit Fehlerrückgabe, aber ohne Fehlerberichte, in ein Programm mit Fehlerberichten transformiert werden kann. Sollen nur Fehlerberichte, aber keine Erfolgsberichte ausgegeben werden, dann wäre folgendes ein passendes vim -Kommando.

%s/return \([1-9]\)/RAISE(\1)/g

Die Implementation einer Listenverarbeitung

Die Implementation  einer Listenverarbeitung kann als Lehrbeispiel nützlich sein. In der Praxis sollten jedoch zunächst erprobte Bibliotheken zur Listenverarbeitung geprüft werden, bevor eine Listenverarbeitung neu entwickelt wird. Die Verwendung einer ad hoc geschriebenen Listenverarbeitung wird hier also für den allgemeinen Fall nicht  empfohlen, obwohl sie unter speziellen Umständen geboten sein könnte. Neben der Verwendung einer Bibliothek zur Listenverarbeitung kann zur Datenhaltung auch die Verwendung einer externen oder internen Datenbank  geprüft werden.

Der Aufwand für Listen und Bäume lohnt sich erst, wenn die Anzahl beziehungsweise Struktur von Daten sich zur Laufzeit verändern können soll. Sonst sollten einfachere Arten der Datenhaltung bevorzugt werden.

Ein klassisches Werk über Listenverarbeitung, an Hand dessen der Autor dieses Textes selber die Listenverarbeitung kennenlernte, stammt von Foster, ist aber derzeit vielleicht nicht mehr neu erhältlich.

[Foster 1969]

J. M. Foster : List Processing. London: Macdonald, 1969.

[Foster 1970]

J. M. Foster : Listenverarbeitung. München: Carl Hanser, 1970.

Gepunktete Paare

Eine verbundene Liste L von Werten wird hier durch einen Zeiger »list« (oder anders benannt) auf ein gepunktetes Paar  (oder „Cons -Paar“ oder – wenn keine Mißverständnisse zu befürchten sind – kurz „Paar“) realisiert. Diese Bezeichnungen sind historisch bedingt und sind hier als willkürlich gewählt zu verstehen, sie haben also keine tiefere Bedeutung.

Wenn die Liste L leer ist, dann ist dieser Zeiger gleich 0. In der folgenden Abbildung wird ein Nullzeiger durch einen „geerdeten Pfeil“ dargestellt, dieser zeigt auf einen kurzen Abschlußstrich.

Die leere Liste ()

list ----->|

Sonst zeigt dieser Zeiger auf das erste Paar der Liste L. Dieses erste Paar enthält dann

1.) einen Wert (den ersten Wert der Liste L) und

2.) eine weitere Liste L', die den Rest der Liste L darstellt.

Diese beiden Komponenten eines Cons -Paares werden aus historischen Gründen manchmal auch „CAR“ und „CDR“ (moderner, aber schon nicht mehr ganz so allgemein: „first“ und „rest“ oder „head“ und „tail“ oder „Kopf“ und „Rest“) genannt. In diesem Text wird zunächst kein ganz allgemeines Cons -Paar behandelt, bei dem die erste Komponenten ebenfalls ein Zeiger sein könnte, sondern nur der Spezialfall, in dem die erste Komponente ein int -Wert ist.

Hier wird zur Vereinfachung zunächst ein Cons -Paar für int -Werte gezeigt, obwohl auch noch allgemeinere Cons -Paare möglich sind:

Rekursive Struktur eines Cons -Paares

struct pair
{ int           value;
  struct pair * next; };

Die Liste ( 3 )

            .-------.
list -----> | 3 | o----->|
            '-------'

Die Liste ( 3, 7 )

            .-------.     .-------.
list -----> | 3 | o-----> | 7 | o----->|
            '-------'     '-------'

Die rekursive Struktur  eines Cons -Paares führt dazu, daß zu seiner Verarbeitung zunächst rekursive Algorithmen natürlich sind, die in C  aber aus Gründen der Effizienz oft wieder durch nicht-rekursive Algorithmen ersetzt werden.

Die rekursive Struktur eines Cons -Paares könnte ohne die Verwendung von Zeigertypen nicht ausgedrückt werden, da eine Struktur sich nicht selber  enthalten kann, sondern nur einen Zeiger auf sich selbst. (Selbstbezüglichkeit von Texten erfordert immer einen Schritt der Interpretation  eines Bezugs.)

Das folgende Programmbeispiel zeigt das Einlesen und Ausgeben einer int-Liste, zur Vereinfachung ohne Behandlung von Laufzeitfehlern.

list1.c

#include <stdio.h>  /* printf       */
#include <stdlib.h> /* EXIT_SUCCESS */

struct pair
{ int           value;
  struct pair * next; };

int main( void )
{ struct pair * list = 0;
  struct pair * this = 0;
  int looping = 1; while( looping )
  { int value; scanf( "%d", &value );
    if( value < 0 )looping = 0; else
    { struct pair * const new = malloc( sizeof *new ); /* A */
      new->value = value; new->next  = 0;              /* B */
      if( list )this->next = new; else list = new;     /* C */
      this = new;                                      /* D */ }}
  for( this = list; this; this = this->next )
  printf( "%d\n", this->value );
  return EXIT_SUCCESS; }

A Falls eine Benutzer die Eingabe nicht  mit einem negativen Wert beendet hat, wird für einen eingegebenen Wert ein neues Paar alloziert

B Dieses Paar erhält eine Kopie des Wertes. Sein next -Zeiger ist 0, da es das (vorerst) letzte Paar der Liste ist.

C Normalerweise wird nun ein Zeiger auf das neue Paar »new« in die Variable für das bisher letzte Paar »this« geschrieben. Falls die Liste bisher jedoch leer war, geht das nicht, weil es noch kein bisher letztes Paar gibt. Dann wird der Zeiger statt dessen in die Variable »list« geschrieben, welche die Liste insgesamt repräsentiert. Dasselbe könnte etwas kompakter auch wie folgt geschrieben werden: »*( list ? &this->next : &list )= new;« (weil der Wert eines bedingten Ausdrucks nicht auf der linken Seite einer Zuweisung stehen darf, werden die Adressen der möglichen Zuweisungsziele angegeben, und dann wird der Sternchenoperator verwendet, dessen Wert auf der linken Seite einer Zuweisung stehen darf. An Stelle von »a = 1« kann man auch schreiben »*&a = 1«.)

D Nun wird das neue Paar »new« zum bisher letzten Paar »this« (für einen eventuell folgenden Schleifendurchlauf).

Bei der Eingabe der Zahlen »3« und »7« kann man sich die Situationen beispielsweise wie folgt vorstellen.

Situation vor den Eingaben

this ----->|

list ----->|

Situation nach Eingabe von 3

             this
              |
              |
              v
            .-------.
list -----> | 3 | o----->|
            '-------'

Situation nach Eingabe von 3 und 7

                           this
                            |
                            |
                            v
            .-------.     .-------.
list -----> | 3 | o-----> | 7 | o----->|
            '-------'     '-------'

/    Präsenzaufgabe Ausgabe

Erklären Sie den Programmteil zur Ausgabe der Liste.

/    Übungsaufgabe Umformatieren/Umschreiben

Wenn Ihnen etwas an dem obigen Programm als unübersichtlich erscheint (also beispielsweise die Formatierung oder die Namen von Variablen), ändern Sie das Programm so lange ab, bis es Ihnen als möglichst übersichtlich erscheint.

/    Übungsaufgabe Scheitern von Anforderungen

Welches Verhalten wäre sinnvoll, wenn der Aufruf von »malloc« in dem Programm scheitert, also 0 ergibt? Denken Sie sich ein Verhalten aus und setzen Sie dies durch eine Änderung des Programms um.

/    Übungsaufgabe Freigeben der Liste

Ergänzen Sie das Programm um einen Teil am Ende, der die Liste wieder freigibt, also alle bisher mit »malloc« erfolgreich angeforderten Paare mit »free« wieder freigibt. (Das ist in diesem Programm nicht nötig, wird aber manchmal in anderen Programmen benötigt.)

/    Übungsaufgabe (Neu um 2010-01-14) Rekursive und iterative Länge

Eine rekursive Funktion zum Ermitteln der Länge einer Liste ist »int length( struct pair const * const list ){ return list ? 1 + length( list->next ): 0; }«. Die Rekursion ist zwar elegant, da sie der Struktur der Datentypdefinition entspricht, aber sie leidet in C  potentiell unter dem Zeit- und Speicheraufwand für Funktionsaufrufe. Schreiben Sie eine Funktion, welche die Länge einer Liste ohne den Funktionsaufrufe ermittelt.

/    Präsenzaufgabe Invertieren der Liste (Variante 0)

Ändern Sie das Programm so ab, daß die jeweils eingegebene Zahl nicht an das Ende der Liste angefügt wird, sondern an den Anfang (also immer vor das bisher erste Paar der Liste). Das bedeutet, daß die Liste nach dem Einlesen in der umgekehrten Reihenfolge angeordnet ist als bisher.

/    Übungsaufgabe Invertieren der Liste (Variante 1) (schwierig)

Ändern Sie das Programm so ab, daß die Liste in umgekehrter Reihenfolge ausgegeben wird, wobei sie diesmal aber wieder – wie in dem obigen Programmbeispiel – in der normalen Reihenfolge eingelesen wird.

/    Übungsaufgabe Invertieren der Liste (Variante 2) (schwierig)

Ändern Sie das Programm so ab, daß die Liste nach dem Einlesen und vor dem Ausgegeben umgekehrt wird. Sie sollte dann also in umgekehrter Reihenfolge ausgegeben werden, obwohl die Programmteile zum Einlesen und Ausgeben die Liste in der normalen Reihenfolge einlesen und ausgeben (also wie in dem obigen Programmbeispiel). (Das Invertieren einer Liste wird nach einigen Quellen manchmal in Bewerbungsgesprächen von Programmierern diskutiert.)

/    Übungsaufgabe Invertieren der Liste (Variante 3) (schwierig) (Wiederholung)

Diese Übungsaufgabe wurde schon einmal gestellt, aber bisher noch nicht gelöst:

Schreiben Sie ein Programm, das eine Liste von Zahlen einliest und in umgekehrter Reihenfolge wieder ausgibt. Dabei soll die größtmögliche Anzahl dieser Zahlen nicht durch den Quelltext des Programms auf eine bestimmten Wert begrenzt sein. Außerdem soll kein allozierter Speicher (wie bei den anderen obenstehenden Übungsaufgaben) verwendet werden.

Die Lösung dieser Aufgabe ist ein verblüffend kurzes C -Programm, es ist nur nicht einfach, darauf zu kommen.

Abstrakte Objekte (zum Thema „Strukturierung großer Programme“)

Eine monolithische Struktur bei einem großen Programm bringt es meist mit sich, daß eine Änderung an einer Stelle Änderungen an anderen Stellen nötig macht. Dadurch kann eine Kaskade von Änderungen nötig werden, wodurch die Wartbarkeit und Änderbarkeit solch eines Programms leidet. Als Gegenmaßnahme sollen solche Programme in isolierte Abschnitte unterteilt werden, die nur über bestimmte Schnittstellen miteinander kommunizieren. Dies bringt auch noch den Vorteil mit sich, daß die so isolierten Programmteile nun in anderen Programmen (wieder)verwendet werden können.

Zur Trennung von Programmteilen haben sich abstrakte Datentypen (ADTs, Schnittstellen) als nützlich erwiesen. Ein abstrakter Datentyp ist eine Sammlung dokumentierter Funktionen. Bestenfalls haben diese einen „Kontrakt“, es geht also aus ihrer Dokumentation genau hervor unter welchen Voraussetzungen sie aufgerufen werden dürfen und welche Konsequenzen sie dann garantieren.

Eine Entität, die einen abstrakten Datentyp (als ihren Typ) hat, wird abstraktes Objekt  genannt.

Der Klient eines abstrakten Objektes greift auf dieses Objekt ausschließlich  über die Funktionen der Schnittstelle zu.

Das klassische Beispiel für ein abstraktes Objekt in C  ist ein FILE -Objekt.

ISO/IEC 9899:1999 (E) erklärt zu FILE, “[it ]is an object type capable of recording all the information needed to control a stream, including its file position indicator, a pointer to its associated buffer (if any), an error indicator that records whether a read/write error has occurred, and an end- of-file indicator that records whether the end of the file has been reached ” und “The address of the FILE object used to control a stream may be significant; a copy of a FILE object need not serve in place of the original.”. (Hinzu kommt die allgemeine akzeptierte, aber nicht wörtlich in der Norm enthaltene, Regel [“as-if rule”], daß eine C -Implementation die Festlegungen der Norm nicht wörtlich umsetzen muß, sondern es reicht, wenn sie sich so verhält, als ob  sie dies täte, wodurch sie auch die Möglichkeit von Realisierungen solcher FILE -Objekte hat, die noch weiter von den Angaben im Standard entfernt sind.)

Ein FILE -Objekt ist also nur abstrakt charakterisiert, jedoch ist nicht erklärt, wie von außen auf seine Datenkomponenten direkt zugegriffen werden kann. Der Zugriff ist nur über Zugriffsfunktionen möglich. So erlaubt die Funktion »ferror« (»int ferror(FILE *stream);«) beispielsweise den Lesezugriff auf den Fehlerindikator eines FILE -Objekts.

Ein weiteres Beispiel für eine ADT-Implementation ist die schon vorgestellte Bibliothek zur Listenverarbeitung von »mij.oltrelinux.com«.

Die Definition und Implementation eines ADTs verursacht natürlich auch Aufwand, weswegen von Fall zu Fall entschieden werden muß, wann sich dieser Aufwand lohnt.

Abstrakter Datentyp (ADT, Schnittstelle)

Eine Menge von Funktionen und einer Dokumentation (Angabe, Beschreibung) ihrer Semantik.

Semantik einer Funktion (Kontrakt)

Die Semantik (Bedeutung) einer Funktion ist gegeben durch die Angabe der Voraussetzung/Vorbedingungen (einschließlich der Argumentwerte) unter/mit denen sie aufgerufen werden kann und der Angabe der Folgen, die sie dann garantiert (Nachbedingungen, Wirkungen, einschließlich eines eventuellen Wertes des Aufrufs).

Abstraktes Objekt

Eine Entität, deren Typ ein ADT ist.

ADT-Implementation

Eine Implementation (Umsetzung, Verwirklichung) eines ADTs.

Klient

Ein Programmteil, der einen anderen Programmteil (beispielsweise eine ADT-Implementation) nutzt.

Kapselung

Jede Maßnahme, die sicherstellt, daß ein Klient nur über die Schnittstelle auf eine ADT-Implementation zugreift, aber nicht auf „interne Implementationsdetails“.

[Liskov 1974]

Barbara Liskov, Stephen Zilles : Programming with abstract data types. In: ACM SIGPLAN Notices. (1974), Volume 9, Issue 4:50-59.

http://www.cs.iastate.edu/courses/archive/f06/cs362/papers/p50-liskov.pdf

[Meyer 1974]

Bertrand Meyer : Applying "Design by Contract". In: Computer (IEEE). (1992), Volume 25, Issue 10:50-51.

http://www.cs.iastate.edu/courses/archive/f06/cs362/papers/meyer92.pdf

Objekte ohne Schnittstelle

Das folgende Programmbeispiel zeigt die Implementation einer ADTs für ein Konto mit den Operationen »deposit« (einzahlen) und »balance« (Saldo). Im Beispielklienten werden zweimal 10 Cent eingezahlt und dann wird der Saldo ausgegeben (erwartet werden hier 20 Cent für den Saldo). Zunächst ein Programm ohne Kapselung.

Ein Konto ohne eine klare Schnittstelle

#include <stdio.h>  /* printf       */
#include <stdlib.h> /* EXIT_SUCCESS */

int main( void )
{ int balance = 0;

  balance += 10;
  balance += 10;

  printf( "%d\n", balance );
  return EXIT_SUCCESS; }

stdout

20

Objekte mit Schnittstelle (einfache Implementation)

Ein Konto mit einer Schnittstelle

#include <stdio.h>  /* printf       */
#include <stdlib.h> /* EXIT_SUCCESS */

void initialize( int * const account )
{ *account = 0; }

void deposit( int * const account, int const value )
{ *account += value; }

int balance( int * const account )
{ return *account; }

int main( void )
{ int account;
  initialize( &account );
  deposit( &account, 10 );
  deposit( &account, 10 );
  return EXIT_SUCCESS; }

stdout

20

Die Schnittstelle wird in dem obigen Programm von den drei Funktionen »initialize«, »deposit« und »balance« gebildet.

Der Parameter von »balance« ist in dem obigen Programm nur aus Gründen der Einheitlichkeit auch ein Zeiger.

Man sieht, daß die Verwendung „sprechender“ Funktionsnamen auch die Verständlichkeit des Klientencodes erhöhen kann.

Strukturen zur Kapselung

Die Schnittstelle ist oben allerdings noch löchrig gekapselt (eine “leaky abstraction ”), da der Klient noch interne Details, wie den Datentyp des Kontos (»int«) sehen kann.

Dieser kann in einer Struktur versteckt werden.

Ein Konto als Struktur

#include <stdio.h>  /* printf       */
#include <stdlib.h> /* EXIT_SUCCESS */

struct account
{ int balance; };

void initialize( struct account * const account )
{ account->balance = 0; }

void deposit( struct account * const account, int const value )
{ account->balance += value; }

int balance( struct account * const account )
{ return account->balance; }

int main( void )
{ struct account account;
  initialize( &account );
  deposit( &account, 10 );
  deposit( &account, 10 );
  printf( "%d\n", balance( &account ));
  return EXIT_SUCCESS; }

stdout

20

Diese Vorgehensweise entspricht schon weitgehend dem Stand der Technik. Die weiteren Abschnitte zeigen mögliche Verbesserungen, die allerdings noch etwas komplizierter sind. Die Techniken der nächsten Abschnitte sollten daher nicht  eingesetzt werden, wenn sie für die an einem Projekt Beteiligten schwer durchschaubar sein sollten.

Unvollständige Strukturen zur verstärkten Kapselung

Hier könnte es nun immer noch bemängelt werden, daß der Klient ja auch unter Umgehung der Schnittstelle direkt  auf die Struktur zugreifen könnte  (wenn der Programmierer gerade nicht daran denkt, daß nur die Schnittstelle zu verwenden ist). Eine Verstärkung der Kapselung ist möglich, bedeutet aber auch mehr Aufwand, der nicht in jedem Fall angebracht sein muß.

Die einzelnen Programmabschnitten vorangestellten Dateinamen  zeigen, wie eine Datei benannt werden könnte, in die das ihnen folgende Programmstück ausgelagert werden könnte, wenn die folgende Quelldatei auf die übliche Weise in mehrere Quelldateien zerlegt werden sollte. Auf eine solche Zerlegung wurde hier nur verzichtet, weil eine einzelne Quelldatei zunächst einfacher au handhaben ist.

Ein Konto als gekapselte Struktur

#include <stdio.h>  /* printf                     */
#include <stdlib.h> /* EXIT_SUCCESS, EXIT_FAILURE */

/* account.h */
struct account;
struct account * account_create( void );
void account_dispose( struct account * account );
void account_deposit( struct account * account, int value );
int account_balance( struct account * account );

/* client.c */
/* Obige include-Zeilen mit "std" und #include "account.h" */
int main( void )
{ struct account * account;
  if( account = account_create() )
  { account_deposit( account, 10 );
    account_deposit( account, 10 );
    printf( "%d\n", account_balance( account ));
    account_dispose( account );
    return EXIT_SUCCESS; }
  else return EXIT_FAILURE; }

/* account.c */
/* #include "account.h" */
struct account { int balance; };

struct account * account_create( void )
{ struct account * account;
  if( account = malloc( sizeof *account ))
  { account->balance = 0; }
  return account; }

void account_dispose( struct account * account )
{ free( account ) ; }

void account_deposit( struct account * const account, int const value )
{ account->balance += value; }

int account_balance( struct account * const account )
{ return account->balance; }

stdout

20

Die Schnittstelle wird in dem obigen Programm von den drei Funktionen »account_dispose«, »account_deposit« und »account_balance« gebildet. (Die Funktion »account_create« gehört zwar auch zu einer Schnittstelle, aber genau genommen zu der eines anderen Typs, da sie kein Konto voraussetzt, sondern dieses erst erzeugt.)

unvollständige Struktur Das obige Programm macht sich die Möglichkeit der Definition einer „unvollständigen Struktur“ zunutze. Nach der Deklaration »struct account;« kann der Klient zwar Zeigern auf die Struktur weiterreichen, aber sie nicht dereferenzieren – die Zeiger sind „opak“. Einen ähnlichen Effekt könnte man zwar auch durch Verwendung von »void *« erzielen, so kann der Compiler aber außerdem weiterhin prüfen, daß beim Aufruf der Funktionen Zeiger des richtigen Typs verwendet werden (Typstrenge). Allerdings muß nun Speicher mit allozierter Lebensdauer verwendet werden, was das Programm etwas komplizierter macht.

Griffe

Ein opaker Zeiger wird hier auch ein Griff  (“handle ”) genannt. Der Klient erhält einen Griff von bestimmten Funktionen und reicht sie an andere Funktionen zur Identifizierung eines abstrakten Objekts weiter. Er soll aber nicht wissen, welche Daten sich hinter dem Griff verbergen.

Namenskonvention Hier wurde die an sich empfehlenswerte Namenskonvention verwendet, der zufolge alle Funktionsnamen einer Schnittstelle mit einem gleichen Teil (wie »account_«) beginnen. Allerdings sind in C90 nur die ersten sechs Zeichen  eines externen Bezeichners signifikant, so daß solch eine Benennung in C90  nicht maximal portabel ist. Sie ist aber in der Praxis trotzdem oft möglich, weil viele Implementationen mehr als sechs Zeichen als signifikant berücksichtigen. Es ist wohl eines der größten Probleme von C90, daß sich alle externen Funktionsnamen bei strenger Anwendung dieser Norm in den ersten sechs Zeichen unterscheiden müssen; wird aber wohl von den meisten Programmierern ignoriert.

Laufzeitprüfungen (aufwendig) *

Durch Verwendung von cast -Operatoren oder anderen Möglichkeiten ist es aber möglich, daß ein Klient die Typprüfungen unterläuft und zur Laufzeit einen Zeiger auf ein Objekt eines falschen Typs an eine Funktion einer Schnittstelle übergibt. Auch könnte ein Nullzeiger übergeben werden.

Die Richtlinien der C -Standardbibliothek erlauben es, in solchen Fällen undefiniertes Verhalten zu zeigen. Denn es gilt:

Es ist die Aufgabe eines Aufrufers sicherzustellen, daß Funktionen richtig aufgerufen werden. Es ist nicht die Aufgabe einer Funktion, sich auch bei falschem Aufruf sinnvoll zu verhalten (denn das ist im allgemeinen gar nicht möglich.)

Dennoch kann es zumindest während der Entwicklung richtig sein, wenn eine aufgerufene Funktion an den ihr übergebenen Informationen Integritätsprüfungen vornimmt.

In dem folgenden Programm wird die interne Struktur jedes abstrakten Objektes daher mit einer zusätzlichen Typkennung versehen. Bei jedem Aufruf, bei dem ein Griff übergeben wird, kann dann mit »assert« geprüft werden, daß dieser nicht 0 ist und, daß er tatsächlich auf eine Struktur mit der richtigen Typkennung zeigt. Jedoch sind die dabei eingesetzten Techniken schon etwas schwerer zu durchschauen, weswegen eine Programmierung in der hier gezeigten Art eher für fortgeschrittene Entwickler geeignet ist.

Im Ersatztext eines Makros bezeichnet »x##y« einen Namen, der aus der direkten Verbindung der beiden Angaben »x« und »y« entsteht. Wenn eine solche Angabe ein Parameter ist, dann steht sie für den Wert dieses Parameters, sonst steht sie für ihren eigenen Text. So ergibt »TYPEOF(alpha)« beispielsweise den Bezeichner »alphatype«.

Ein Konto als gekapselte Struktur mit Laufzeittypprüfung *

#include <stdio.h>  /* printf                     */
#include <stdlib.h> /* EXIT_SUCCESS, EXIT_FAILURE */
#include <assert.h> /* assert                     */

/* type.h */
#define TYPEOF(name) name##type
struct type { char const * name; };

/* account.h */
struct account;
struct account * account_create( void );
void account_dispose( struct account * account );
void account_deposit( struct account * account, int value );
int account_balance( struct account * account );

/* client.c             */
/* #include "account.h" */
int main( void )
{ struct account * account;
  if( account = account_create() )
  { account_deposit( account, 10 );
    account_deposit( account, 10 );
    printf( "%d\n", account_balance( account ));
    account_dispose( account );
    return EXIT_SUCCESS; }
  else return EXIT_FAILURE; }

/* account.c            */
/* #include "type.h"    */
/* #include "account.h" */
struct type TYPEOF(account)={ "account" };

struct account
{ struct type * type;
  int balance; };

struct account * account_create( void )
{ struct account * account;
  if( account = malloc( sizeof *account ))
  { account->type = &TYPEOF(account);
    account->balance = 0; }
  return account; }

void account_dispose( struct account * account )
{ assert( account&&( account->type == &TYPEOF(account) ));
  free( account ) ; }

void account_deposit( struct account * const account, int const value )
{ assert( account&&( account->type == &TYPEOF(account) ));
  account->balance += value; }

int account_balance( struct account * const account )
{ assert( account&&( account->type == &TYPEOF(account) ));
  return account->balance; }

stdout

20

Übungsaufgaben

Bei der Bearbeitung dieser Übungsaufgaben kann das unter der Überschrift „Strukturen zur Kapselung “ beschriebene Verfahren verwendet werden. Es ist nicht  nötig die Techniken aus den Abschnitten „Unvollständige Strukturen zur verstärkten Kapselung “ oder „Laufzeitprüfungen “ einzusetzen.

/    Übungsaufgabe Einfach verkettete Listen als abstraktes Objekt (wichtig zur Gliederung größerer Projekte)

Schreiben Sie eine Sammlung von Funktionen zum Arbeiten mit einer einfach verketteten Liste:

• Anlegen einer neuen (leeren) Liste, diese Funktion ergibt einen Zeiger auf eine Struktur, welche die Liste repräsentiert (Diese Struktur muß selber kein gepunktetes Paar sein, sondern kann eine weitere Struktur neben dem gepunkteten Paar sein)
• Vollständiges Auflösen (Löschen) einer beliebigen Liste mit Freigabe aller ihrer Ressourcen
• Anfügen einer Zahl an das Ende der Liste
• eine Funktion zum Ausgeben der Liste

Schreiben Sie das obige Programm dann als Klient Ihrer ADT-Implementation um.

/    Übungsaufgabe Doppelt verkettete Listen

Bei einer einfach verketteten Liste ist das Durchlaufen von vorne nach hinten  direkt möglich, während das Durchlaufen in die andere Richtung schwieriger ist. Implementieren Sie eine doppelt verkettete  Liste als ADT-Implementation. Bei einer doppelt verketteten Liste enthält jeder Eintrag auch einen Zeiger auf seinen Vorgänger.

Schreiben Sie dann einen Klienten, der unter Verwendung dieser ADT-Implementation eine Liste von Zahlen einliest und in umgekehrter Reihenfolge wieder ausgibt.

Speicherverwaltung

Wenn Listen zur Laufzeit aufgebaut und an andere Programmteile zur Verarbeitung weitergereicht werden, dann kann es schwierig werden, zu übersehen, wann welche allozierten Strukturen mit »free« wieder freigegeben werden können. Dies gilt insbesondere dann, wenn die Datenstrukturen noch komplizierter werden, wie etwa im nächsten Abschnitt angedeutet.

Die Verwaltung komplizierter dynamischer Datenstrukturen ist einer der schwierigsten Teile der C -Programmierung. Sie wird daher in einigen anderen Programmiersprache durch zusätzliche Unterstützung automatisiert und somit erleichtert: Dort sorgt ein sogenannter “garbage collector ” dafür, daß von einem Programm nicht mehr verwendeter Speicher automatisch wieder freigegeben wird, was das Programmieren in manchen Fällen ungemein erleichtert.

Auch für die Programmiersprache C  gibt es einen solchen “garbage collector ”, den „Boehm-Collector“.

http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Der Boehm-Collector gehört allerdings nicht zum Standard der Programmiersprache C.

How Microsoft Lost the API War

2004-06-13

Joel Spolsky

http://www.joelonsoftware.com/articles/APIWar.html

A lot of us thought in the 1990s that the big battle would be between procedural and object oriented programming, and we thought that object oriented programming would provide a big boost in programmer productivity. I thought that, too. Some people still think that. It turns out we were wrong. Object oriented programming is handy dandy, but it's not really the productivity booster that was promised. The real significant productivity advance we've had in programming has been from languages which manage memory for you automatically. It can be with reference counting or garbage collection; it can be Java, Lisp, Visual Basic (even 1.0), Smalltalk, or any of a number of scripting languages. If your programming language allows you to grab a chunk of memory without thinking about how it's going to be released when you're done with it, you're using a managed-memory language, and you are going to be much more efficient than someone using a language in which you have to explicitly manage memory. Whenever you hear someone bragging about how productive their language is, they're probably getting most of that productivity from the automated memory management, even if they misattribute it.

2010-01-03T21:20:14+01:00

Ausblick *

Wenn in den Paaren die erste int-Komponente durch eine Komponenten vom Typ »void *« ersetzt wird, so können beliebige Werte  als Inhalt der Liste vorkommen, etwa auch Zeiger auf weitere Listen. So wird eine Verschachtelung von Listen möglich. Eine Liste könnte dann also nicht nur Zahlen, sondern wiederum auch andere Listen enthalten (oder sogar Verweise auf sich selbst). Daher wird solch eine Liste hier auch „rekursive Liste“ genannt.

Die Liste (( A B ) C )

            .-------.    .-------.
list -----> | o | o----->| o | o----->|
            '-|-----'    '-|-----'
              |            |
              |            V
              |            C
              |
              V
            .-------.    .-------.
            | o | o----->| o | o----->|
            '-|-----'    '-|-----'
              |            |
              V            V
              A            B

Durch diese Verschachtelung von Listen kann eine Baumstruktur realisiert (dargestellt) werden.

Der Baum (( A B ) C )

                /\
               /  \
              /    \
             /\     C
            /  \
           A    B

Zur Interpretation solch einer verschachtelten Liste muß aber der Typ eines jeden Objektes zur Laufzeit  bekannt sein, was bei naiver Implementation zunächst nicht mehr gegeben ist.

Es kann aber vereinbart werden, daß eine jede Liste als Kopf zunächst eine Typangabe als Text enthält. Dann kann die bisherige Paarstruktur beibehalten werden. Der Baum »(( A B ) C )« würde dann als »( LIST (( ATOM A )( ATOM B ))( ATOM C ))« dargestellt werden, wobei mit »ATOM« Texte und mit »LIST« Listen gekennzeichnet werden.

Die weitere Beschäftigung mit Listenverarbeitung könnte Algorithmen auf solchen rekursiven Listen behandelt und auch die Implementation eines Interpretierers für eine vereinfachte Variante der Programmiersprache LISP.

Diese interessanten Themen solle hier aber nicht weiterverfolgt werden, da in diesem Intensivkurs C  nur eine beschränkte Zeit für die Beschäftigung mit Listen eingeplant wurde, damit auch noch Raum für andere vereinbarte Themen bleibt.