Programmieren in C


von Prof. Jürgen Plate

8 Ausgewählte Algorithmen (Teil 1)

8.1 Verarbeitung von Zeichenketten (Strings)

Einfache Stringoperationen

Bibliothek zum Test von Zeichen: <ctype.h>

Diese Bilbliothek wurde bereits kurz vorgestellt, hier folgen Beispiele zur Anwendung. Zur Erinnerung:
Das Argument der folgenden Funktionen ist jeweils ein int dessen Wert entweder durch EOF oder als unsigned char darstellbar sein muß. Der Rückgabewert ist ein int, wobei dieser gleich Null ist, wenn das Argument c die Bedingung nicht erfüllt, ansonsten ist er ungleich Null. Wenn sie Probleme mit char-Variablen haben, kann das in seltenen Fällen am zugrundeliegenden System liegen. Ersetzen sie dann char durch unsigned char.
Achtung: Die deutschen Umlaute und das "ß" sind keine Buchstaben im Sinne der C-Funktionen!!

islower(c) Kleinbuchstabe
isupper(c) Großbuchstabe
isalpha(c) Klein- oder Großbuchstabe
isdigit(c) Dezimalzahl
isalnum(c) Klein- oder Großbuchstabe oder Dezimalzahl
iscntrl(c) Control-Zeichen
isgraph(c) druckbares Zeichen außer space
isprint(c) druckbares Zeichen mit space
ispunct(c) druckbares Zeichen außer space, Buchstabe und Ziffern
isspace(c) space, formfeed, newline, carriage return, tab, vertical tab
isxdigit(c) Hexadezimalzahl
tolower(int c) konvertiert c zu Kleinbuchstaben
toupper(int c) konvertiert c zu Großbuchstaben

#include <stdio.h>
#include <ctype.h>

void main (void)
  {
  char c;

  c = getchar();
  if (isalpha(c)) printf ( "%c ist ein Buchstabe\n",c);
  if (isalnum(c)) printf ( "%c ist ein Buchstabe oder eine Ziffer\n",c);
  if (isupper(c)) printf ( "%c ist ein Großbuchstabe\n",c);
  if (islower(c)) printf ( "%c ist ein Kleinbuchstabe\n",c);
  if (isdigit(c)) printf ( "%c ist eine Ziffer\n",c);
  if (isspace(c)) printf ( "%c ist ein Leerzeichen\n",c);
  }
Das folgende Beispiel zeigt die Anwendung der Konvertierfunktionen:
#include <stdio.h>
#include <ctype.h>

void main (void)
{
  char c, d;

  c = getchar();
  if (! isalpha(c)) 
    {
    printf ("%c ist kein Buchstabe!\n",c);
    }
  else
    {
    if (islower(c))
      {
      d = toupper (c);
      printf ( "%c wurde umgwandelt in %c\n",c,d );
      }
    if (isupper(c)) 
      {
      d = tolower (c);
      printf ( "%c wird umgwandelt in %c\n",c,d );
      }
    }
  }

Ausdrucken einer einfachen ASCII-Tabelle:

#include <stdio.h>
#include <ctype.h>

void main(void)
  {
  int i, j;
  for (i=0; i < 4; i++) printf("|dec hex Char ");
  printf("|\n");
  for (i=0; i < 128/4; i++)
    {
    printf("\n| ");
    for (j=0; j < 128; j+=128/4)
      {
      printf("%3d %2X ", i+j, i+j);
      if (isgraph(j)) printf("  %c  | ", i+j);
      else printf("  .  | ");
      }
    }
  }

Länge einer konstanten Zeichenkette ermitteln:

#include <stdio.h>

int stringlaenge(char *s);

int main(void)
  { 
  char kette[] = "Elvis is alive!";
  printf("DDer String hat %d Zeichen.\n", stringlaenge(kette));
  } 

int stringlaenge(char s[])
  { 
  int i = 0;
  for(i=0; kette[i] != '\0'; i++);
  return (i)
  }

Stringfunktionen

Neben den einfachen Zuweisungen und Abfragen gibt es eine Reihe von komplexen Befehlen für Zeichenketten. DIe Prototypen befinden sich in der Standardbibliothek <string.h>. In den Beispielen gelten folgende Variablenvereinbarungen:
char a[100];
char b[100];
char c;
int n;
int m;

strcat ( char *a , char *b )

Es wird an a die Zeichenfolge von b angehängt.
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[100] = "Algorithmen & "; 
  char b[100] = "Datenstrukturen"; 

  printf ("a = %s\nb = %s\n",a,b); 
  strcat ( a, b ); 
  printf("\na = %s\n",a);
  }

strncat ( char *a , char *b , int n )

Es wird wie bei strcat b an a angehängt. Jedoch nur maximal n Zeichen von b werden angehängt.
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[100] = "Algorithmen & "; 
  char b[100] = "Datenstrukturen"; 
  int n = 5; 
  printf ("\na = %s\nb = %s\n",a,b); 
  strncat ( a, b ); 
  printf("\na = %s\n",a);
  }

strcpy ( char *a , char *b )

Der Inhalt von b wird nach a kopiert. Das Beispielprogramm dazu:
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[100] = "Alter Text"; 
  char b[100] = "Neuer Text";

  printf ("a = %s",a);
  printf ("b = %s\n\n",b);
  strcpy (a,b); 
  printf ("a = %s\n",a);
  }
strcpy könnte so implementiert werden:
void strcpy(char *a, char *b)
  { 
  int i = 0;
  while ((a[i] = b[i]) != '\0')
     i++;
  }

strncpy ( char *a , char *b , int n )

Der Inhalt von b wird nach a kopiert. Dabei werden höchstens n Zeichen von b nach a kopiert. Der Rest des Strings bleibt erhalten.
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[100] = "Alter Text"; 
  char b[100] = "Neuer Text";
  int n = 2;

  printf ("a = %s",a);
  printf ("b = %s\n\n",b);
  strcpy (a,b); 
  printf ("a = %s\n",a);
  strncpy (b,a,n); 
  printf ("a = %s\n",a);
  }

int n = strlen ( char *a )

Es wird die Länge der Zeichenkette ( ohne das abschließende '/0') zurückgegeben.
#include <stdio.h>
#include <string.h>

void main (void)
  {
  int n; 
  char a[100] ="Na, wie lang bin ich denn?"; 

  n = strlen (a); 
  printf (",,aïï ist %d Zeichen lang\n",n);
  }

Zeichenposition und Teilstring suchen im String

char *b = strchr ( char *a , char c )

Es wird String a nach dem Buchstaben c durchsucht und ein Zeiger auf die Stelle in a zurückgegeben, an der sich der Buchstabe c zuerst befindet. Existiert kein Buchstabe, so wird NULL zurückgegeben. Im Beispiel ist dies das 'i' von 'ist'.
#include <stdio.h>
#include <string.h>

void main (void)
  {
  int n; 
  char a[100] ="Na, wo ist denn das Zeichen?"; 

  printf ("%s" , strchr (a , 'i') );
  }

char *b = strrchr ( char *a , char c )

Es wird String a nach dem Buchstaben c durchsucht und ein Zeiger auf die Stelle in a zurückgegeben, an der sich der Buchstabe c zuletzt befindet. Existiert kein Buchstabe, so wird NULL zurückgegeben. Im Beispiel ist dies das 'i' von 'Zeichen'.
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[100] ="Na, wo ist denn das Zeichen?"; 
  printf ("%s" , strrchr (a , 'i') );
  }

int m = strcmp ( char *a , char *b )

Die beiden Zeichenketten werden miteinander verglichen. Der Rückgabewert hängt vom Vergleichsergebnis ab:
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[100] = "Vergleichswort 1"; 
  char b[100] = "Vergleichswort 2"; 

  printf ("a = %s",a);
  printf ("b = %s\n\n",b);
  printf ("strcmp (a,b) = %d\n", strcmp (a,b) ); 
  printf ("strcmp (a,a) = %d\n", strcmp (a,a) ); 
  printf ("strcmp (b,a) = %d\n", strcmp (b,a) ); 
  }

Die Vergleichsfunktion kann man sich auch selbst schreiben:

strcmp(char s1[], char s2[]) 
  {	
  int i=0;
  while (s1[i] == s2[i])
    {
    if (s1[i] == 0) 
      return(0);
    else
      i++;
    }
  return (s1[i] - s2[i]);
}

int m = strncmp ( char *a , char *b , int n )

Die Funktion arbeitet wie strcmp mit dem Unterschied, das nur die ersten n Zeichen verglichen werden. Alle nachfolgenden Zeichen werden ignoriert.Der Rückgabewert hängt vom Vergleichsergebnis ab:
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[100] = "Vergleichswort 1"; 
  char b[100] = "Vergleichswort 2"; 

  printf ("a = %s",a);
  printf ("b = %s\n\n",b);
  printf ("strncmp (a,b,3) = %d\n", strncmp (a,b,3) ); 
  printf ("strncmp (a,a,3) = %d\n", strncmp (a,a,3) ); 
  printf ("strncmp (b,a,3) = %d\n", strncmp (b,a,3) ); 
  }

size_t strlen( char *string)

liefert Länge von string ohne das Nullbyte am Schluß
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[100] = "Irgend ein String"; 

  int len = strlen(a);
  printf (",,%sïï hat %d Zeichen", a, len);
  }

void delete(char str[], int pos, int anz)

Die folgende Funktion löscht n Zeichen ab einer vorgegebenen Position aus einem String:
void delete(char str[],int pos, int anz)
  /* anz Zeichen aus str ab pos l”schen */
  {
  int i = pos + anz;
  while ((str[pos++] = str[i++]) != '\0');
  }

char *strupper(char *string)

Die folgende Funktion wandelt alle Kleinbuchstaben in Großbuchstaben um:
char *strupper(char *string)
  {
  char *s;
  if (string != NULL)
    for (s = string; *s; ++s)
      *s = toupper(*s);
  return string;
  } 

char *strlower(char *string)

Die folgende Funktion wandelt alle Großbuchstaben in Kleinbuchstaben um:
char *strlower(char *string)
  {
  char *s;
  if (string != NULL)
    for (s = string; *s; ++s)
      *s = tolower(*s);
  return string;
  }

Suchen und Ersetzen von Strings

char *strstr( char *such, char *vergleich )

liefert einen Zeiger auf das erste Auftreten des Strings such im String vergleich.

Das folgende Beispiel zeigt, wie man das 'Enthaltensein' eines Strings im anderen ermitteln kann. Zur Veranschaulichung ohne Bibliotheksfunktionen und ohne Pointer

int sstr( char such[], char vergleich[] )
  /* Feststellen, ob such in vergleich enthalten ist */
  {
  int i, j;			/* Laufvariablen */

  int lsuch = strlen(such);
  int lvergl = strlen(vergleich);

  for (i = 0; i < (lvergl - lsuch); i++)
    {
    j = 0;
    while (vergleich[i+j] == such[j++])
      if (j == lsuch) return (i);
    }
    return -1;
  }

Variante in der Programmierung:

int sstr( char such[], char vergleich[] )
  /* Feststellen, ob such in vergleich enthalten ist */
  {
  int i, j, k;			/* Laufvariablen */
  for (i = 0; vergleich[i] != '\0'; i++)
    {
    for (j = i, k = 0; such[k] != '\0' && such[k] == vergleich[j]; j++, k++)
      /* tu nix */;
    if (such[k] == '\0') return (i);
    }
  return -1;
  }
Die gleiche Funktion, nur daß diesman die Groß-/Kleinschreibung ignoriert wird:
int isstr( char such[], char vergleich[] )
  /* Feststellen, ob such in vergleich enthalten ist, 
     Gross-/Kleinschreibung ignorieren */
  {
  int i, j;			/* Laufvariablen */

  int lsuch = strlen(such);
  int lvergl = strlen(vergleich);

  for (i = 0; i < (lvergl - lsuch); i++)
    {
    j = 0;
    while (tolower(vergleich[i+j]) == tolower(such[j++])) 
      if (j == lsuch) return (i);
    }
    return -1;
  }

int index (char s[],char t[])

Suchen und die Position zurückliefern:
# include <stdio.h>
# define MAXLINE 1000

int index (char s[],char t[])    /* Position von t in s liefern,
                                    -1 falls nicht da */
  { 
  int i, j, k;
  for (i=0; s[i] != '\0'; i++) 
    {
    for (j=i,k=0; t[k]!='\0' && s[j]==t[k]; j++,k++)
      ;
    if (t[k] == '\0')
      return(i);
    }
  return(-1);
  } 

void replace( char such[], char ersatz[], char original[] )

Die folgende Funktion ersetzt such durch ersatz im String original. Falls such nicht im String enthalten ist, passiert nichts.
void replace( char such[], char ersatz[], char original[] )
  {
  int pos, i, j;			/* Laufvariablen */

  pos = sstr(such, original);
  if (pos >= 0)
    {
    /* Suchstring entfernen */
    i = pos + strlen(such);
    while ((original[pos++] = original[i++]) != '\0');
    /* Platz machen fuer ersatz */
    len = strlen(ersatz), j = pos;
    while ((original[j+len] = original[j]) != '\0')
      j++;
    /* ersatz einbauen */
    for (j = 0; ersatz[j] != '\0'; j++)
      original[pos+j] = ersatz[j];
    }
  }

Leerzeichen entfernen

Die folgende Funktion trim entfernt Leerzeichen aus einer Zeichenkette:
#include <ctype.h>

char *trim (char *str)
  {
  char *ibuf, *obuf;
  if (str)
    {
    for (ibuf = obuf = str; *ibuf; )
      {
      while (*ibuf && (isspace (*ibuf)))
         ibuf++;
      if (*ibuf && (obuf != str))
        *(obuf++) = ' ';
      while (*ibuf && (!isspace (*ibuf)))
        *(obuf++) = *(ibuf++);
      }
    *obuf = NUL;
    }
  return (str);
  }

Umlaute konvertieren

Die folgende Funktion konvertiert Umlaute und Szett in die Ersatzdarstellung (ae, oe, ue, Ae, Oe, Ue, ss):

char* uml(char* eingabe)
  {
  int i = 0, j = 0;
  char *tmp1 = NULL;
  char *tmp2 = NULL;

  /* Wir sparen uns das Ermitteln der Laenge des     */
  /* Eingabestrings und nehmen mal den worst case an */
  tmp1= malloc(2*strlen(eingabe) + 1);
  if(tmp1 == NULL) return(NULL);

  /*Kopieren und Ersetzen */
  while(eingabe[i] != '\0')
    {
    switch (eingabe[i])
      {
      case '&aluml;': tmp1[j++] = 'a'; tmp1[j++]='e'; break;
      case '&oluml;': tmp1[j++] = 'o'; tmp1[j++]='e'; break;
      case '&uluml;': tmp1[j++] = 'u'; tmp1[j++]='e'; break;
      case '&Aluml;': tmp1[j++] = 'A'; tmp1[j++]='e'; break;
      case '&Oluml;': tmp1[j++] = 'O'; tmp1[j++]='e'; break;
      case '&Uluml;': tmp1[j++] = 'U'; tmp1[j++]='e'; break;
      case 'ß': tmp1[j++] = 's'; tmp1[j++]='s'; break;
      default: tmp1[j++] = eingabe[i];
      }
     i++;
    }
  tmp1[j] = '\0';
  /* Nun den String genau passend zurueckgeben */
  tmp2 = malloc(strlen(tmp1) + 1);
  if(tmp2 == NULL) return(NULL);
  strcpy(tmp2,tmp1);
  free(tmp1);
  return(tmp2);
  }

Anwendung von atoi, atof,...

Die folgenden Funktionen wandeln eine Zeichenkette in eine Zahl um. Dabei werden führende Zwischenräume ignoriert. Die Umwandlung erfolgt, bis im String ein ungültiges Zeichen angetroffen wird. Bei über- oder Unterlauf wird errno = ERANGE und ein spezieller Wert zurückgegeben.

double atof(const char *s)

wandelt Zeichenkette in double float um.
#include <stdio.h>
#include <string.h>
#include <math.h>     /* wegen atof */

void main (void)
  {
  char a[80] = "123456.7899999"; 
  double z;

  printf ("a = %s\n",a);
  z = atof(a);
  printf ("z = %lf\n",z);
  }

int atoi(const char *s)

wandelt Zeichenkette in int um.
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[80] = "123"; 
  int i;

  printf ("a = %s\n",a);
  i = atoi(a);
  printf ("i = %d\n",i);
  }

int atol(const char *s)

wandelt Zeichenkette in long int um
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char a[80] = "123"; 
  long int ii;

  printf ("a = %s\n",a);
  ii = atol(a);
  printf ("ii = %lu\n",ii);
  }

Anwendung von sprintf

int sprintf(char *string, const char *format, ...)

Der Formatstring der Funktion hat den gleichen Aufbau wie bei printf(), die Ausgabe wird jedoch in string abgelegt. Daher eignet sich diese Funktion, um Zahlen in Zeichenketten umzuwandeln.
Warnung:Der Rückgabewert von sprintf() ist implementierungsabhängig. Es sollte die Zahl der Zeichen im String zurückgegeben werden. Manche Systeme liefern aber einen Zeiger auf den String.
#include <stdio.h>
#include <string.h>

void main (void)
  {
  char s[] = "*****";
  int i = 123;
  float x = 3.1415;
  char string[50];

  /* Resultat interessiert nicht */
  (void) sprintf (string, "Zeichenkette: %s Int: %d Float: %f", s, i, x);
  }

Römische Zahlen

Das folgende Programm zeigt, wie man eine positive ganze Zahl in römischen Ziffern darstellt. Das Schema ist identisch für Einer-, Zehner- und Hunderterstelle. Der Unterschied besteht nur in den Auszugebenden Zeichen: Ab Tausend aufwärts wird für jeden Tausender ein "M" gedruckt. Die Funktion behandelt weiterhin die Besonderheit der Schreibweise für 9 und 4 (z. B. IV, IX, CM).

#include <stdio.h>
#include <string.h>

void RZiffer(int x, char e, char f, char z)
  /* druckt x als roemische Zahl */
  {
  int i;
  switch (x)
    {
    case 9: printf("%c%c",e,z); break;
    case 8: printf("%c%c%c%c",v,e,e,e); break;
    case 7: printf("%c%c%c",v,e,e); break;
    case 6: printf("%c%c",v,e); break;
    case 5: printf("%c",v); break;
    case 4: printf("%c%c",e,v); break;
    case 3: printf("%c%c%c",e,e,e); break;
    case 2: printf("%c%c",e,e); break;
    case 1: printf("%e",e); break;
    default: break;
    }
  }
  
void main (void)
  {
  int x = 1999;

  while (x > 999)
    {
    printf("M");
    x = x - 1000;
    }
  RZiffer(x/100,'C','D','M');
  x = x%100;
  RZiffer(x/10,'X','L','C');
  RZiffer(x%10,'I','V','X');
  printf("\n");
  }

E/A-Funktionen für Zeichenketten

Die Funktion get_line liest eine Textzeile in ein Zeichenfeld ein und ergaenzt das '\0' Zeichen. Das Ergebnis der Funktion ist die Laenge des gelesenen Strings oder EOF bei Dateiende.

#include <stdio.h>
#define MAXLAENGE 80

int getline(char line[]); 

int main(void)
  { 
  char zeile[MAXLAENGE];
  int laenge, i;
  while ((laenge = getline(zeile)) > 0)
     { 
     printf("%d Zeichen gelesen\n",laenge)
     for(i=0; i<laenge; i++)
       printf("%c",zeile[i]); 
     printf("\n");
     }
  }

int getline(char line[])
  { 
  int c;
  int i = 0;
  while ((c = getchar()) != '\n' && c != EOF)
    if( i < MAXLAENGE-1)
      line[i++] = c;
  line[i++] = '\0';
  if( c == EOF)
    return (EOF);
  else
    return (i);
  }

In der Standardbibliothek sind neben printf und scanf zwei nützliche Routinen zum Einlesen bzw. Drucken von Strings vorhanden:

Beispiel: Einlesen und Ausgeben eines Strings mit Hilfe von Bibliotheksroutinen:

#include <stdio.h>
#define MAXLAENGE 80

void main(void)
  { 
  int i, laenge = 0;
  char zeile[MAXLAENGE];
  char *zeilenzeiger;

  zeilenzeiger = zeile;
  gets(zeilenzeiger);
  puts(zeile);
  }

Das folgende Beispiel zeigt, wie man mit printf Tabellen ausgeben kann. Der Trick ist darin verborgen, daß man bei jeder Druckzeile die Anzahl der Leerstellen ermittelt, die zwischen zwei Feldern liegen sollen. Durch einen * in der Formatangabe (z. B. "%-*s") kann die Ausgabebreite variabel gestaltet werden. Alles weitere zeigt das folgende Beispiel:


#include <stdio.h>
#include <string.h>

int main(void)
  {
  char *firstname[] = { "Sepp",      "Jan",   "Dennis",  NULL };
  char *lastname[]  = { "Langnamer", "Kurz",  "Ritchie", NULL };
  int   note[]      = {   4,           2,        1,       0   };
  int   i, tabwidth;

  printf("%15sStudentenname%30s\n\n", "", "Note");
     
  for (i = 0; NULL != lastname[i]; ++i)
    {
    tabwidth = 36                             /* Leerzeichen insgesamt */
               -2                             /* fuer  ", " */
               -strlen(lastname[i]);          /* laenge lastname */
    
    printf("%s, %-*s%3d\n",
            lastname[i], tabwidth, firstname[i], note[i]);
    }

  return 0;
  }

Das Ergebnis sieht dann etwa so aus:

Studentenname                    Note

Langnamer, Sepp                    4
Kurz, Jan                          2
Ritchie, Dennis                    1

BASIC-Stringfunktionen

Wer die Programmiersprache BASIC kennt, vermisst manchmal komfortable Funktionen zur Bearbeitung von Zeichenketten. Die folgenden Funktionen realisieren einige aus BASIC bekannte und vertraute Funktionen. Mit dabei ist auch eine einfache Speicherverwaltung.
/*
**  public domain by Bob Stout
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <limits.h>
#include <assert.h>

#define NUL '\0'
#define LAST_CHAR(s) (((char *)s)[strlen(s) - 1])


char *stralloc(size_t length);
     /* Belegen von Speicher fuer einen String */

void  str_free(char *string);
     /* Freigabe des mit stralloc belegten Platzes */

char *left(char *string, size_t N);
     /* liefert die linken N Zeichen des Strings */

char *right(char *string, size_t N);
     /* liefert die rechten N Zeichen des Strings */

char *mid(char *string, size_t M, size_t N);
     /* liefert einen Teilstring, N Zeichen lang, 
        beginnend ab Position M */

char *string_add(char *string, ...);
     /* konkateniert mehrere Strings zu einem */

char *string(int ch, size_t N);
     /* liefert eine N Zeichen langen String, der
        aus den durch ch vorgegebenen Zeichen besteht */

unsigned int instr(const unsigned int start_pos,
                   const char        *string,
                   const char        *findstr);
      /* liefert die Position von findstr (beginnend ab 1) in
         string. Die Suche beginnt bei Zeichenposition start_pos
         (beginnend bei 1). */


static int stralloc_ptr;
static char *strings[8];
static int str_tag[8];

/*
**  stralloc() is the key function in this package, maintaining a pool of
**  reusable strings.
*/

char *stralloc(size_t length)
{
      register int i;

      if (UINT_MAX == length)       /* Assume size_t == unsigned int    */
            return NULL;

      i = stralloc_ptr++;
      ++length;                     /* Allow for terminating NUL        */

      if ((!strings[i]) || (length > strlen(strings[i])))
      {
            strings[i] = (char *)realloc(strings[i], length);
            assert(NULL != strings[i]);
            str_tag[i] = -1;
      }
      else  str_tag[i] = 0;
      stralloc_ptr &= 7;
      return (strings[i]);
      /* Maintains 8 strings in a circular buffer */
}

/*
**  free the string pool.
*/

void str_free(char *string)
{
      register int i;

      for (i = 0; i < 8; ++i)
      {
            if (strings[i] == string)
            {
                  if (str_tag[i])
                        free(strings[i]);
                  return;
            }
      }
}

/*
**  return the leftmost N characters from a string, equivalent to LEFT$
*/

char *left(char *string, size_t N)
{
      char *buf;
      size_t strlength = strlen(string);

      if (N > strlength)
            N = strlength;
      buf = stralloc(N);
      memcpy(buf, string, N);
      buf[N] = NUL;
      return buf;
}

/*
**  return the rightmost N characters from a string, equivalent to RIGHT$
*/

char *right(char *string, size_t N)
{
      char *buf;
      size_t strlength = strlen(string);

      if (N > strlength)
            N = strlength;
      buf = stralloc(N);
      strcpy(buf, &string[strlength-N]);
      return buf;
}

/*
**  return a substring, N characters long beginning at position M,
**  equivalent to MID$
*/

char *mid(char *string, size_t M, size_t N)
{
      char *buf;
      size_t strlength = strlen(string);

      if (M > strlength)
            return NULL;
      if (N > (strlength - M))
            N = strlength - M;
      buf = stralloc(N);
      memcpy(buf, &string[M-1], N);
      buf[N] = NUL;
      return buf;
}

/*
**  string concatenation function, equivalent to A$=B$+C$+...
*/

char *string_add(char *string, ...)
{
      va_list arg_ptr;
      char *temp1, *temp2, *buf;

      va_start(arg_ptr, string);
      temp1 = string;
      do
      {
            if(NULL == (temp2 = va_arg(arg_ptr, char *)))
                  break;
            buf = stralloc(strlen(temp1) + strlen(temp2));
            temp1 = strcat(strcpy(buf, temp1), temp2);
      } while (NULL != temp2);
      return temp1;
}

/*
**  create a string of repeated characters, equivalent to STRING$()
*/

char *string(int ch, size_t N)
{
      char *buf;

      if (N)
      {
            buf = stralloc(N);
            memset(buf, ch, N);
      }
      buf[N] = NUL;
      return buf;
                  
}

/*
**  BASIC INSTR$() work alike - returns position (1-based) of findstr in
**  string, starting search at position start_pos (also 1-based).
**
**  Function suggested by Tika Carr
*/

unsigned int instr(const unsigned int start_pos,
                   const char        *string,
                   const char        *findstr)
{
      char *p;
      unsigned int pos;

      if (start_pos > strlen(string))
            return 0;
      else  pos = start_pos - 1;    /* BASIC offsets are one-based, not
                                       zero-based as in C               */

      if (NULL != (p = strstr(string + pos, findstr)))
            return (int)(p - (char *)string) + 1; /* Position 0 = position 1 */
      else  return 0;
}

8.2 Uhrzeit- und Datumsarithmetik

Datums- und Zeitfunktionen der Standard-Bibliothek

In C bezieht sich der Begriff Zeit auf Datum und Uhrzeit. Die Funktionsprototypen und die Definition der Struktur tm, die von vielen Zeitfunktionen verwendet werden, stehen in der Header-Datei time.h.

Die Zeitfunktionen von C stellen Zeitangaben auf zwei verschiedene Weisen dar.

Um die aktuelle Zeit der internen Uhr Ihres Systems abzufragen, verwenden Sie die Funktion time():
time_t time(time_t *ptr);
Die Funktion liefert die Anzahl der Sekunden zurück, die seit Mitternacht des 1. Januar 1970 verstrichen sind. Wenn der Funktion ein Nicht-NULL-Zeiger übergeben wird, speichert time() diesen Wert in der Variablen vom Typ time_t, auf die der Zeiger ptr zeigt. Die beiden folgenden Anweisunge speichern die aktuelle Zeit in der Variablen jetzt:
time_t jetzt;
jetzt = time(NULL);
Oder Sie verwenden die Rückgabe über das Argument:
time_t jetzt;
time(&jetzt);
Mit der Funktion localtime() wandeln Sie einen time_t-Wert in eine tm-Struktur um.
struct tm *localtime(time_t *ptr);
Diese Funktion liefert einen Zeiger auf eine statische Variable vom Typ tm zurück, so dass Sie keine Variable vom Typ tm deklarieren müssen, sondern nur einen Zeiger auf den Typ tm. Die statische Variable wird bei jedem Aufruf von localtime() wieder verwendet und überschrieben. Wenn Sie den zurückgegebenen Wert sichern wollen, muß das Programm eine separate Variable vom Typ tm deklarieren und in diese die Werte der statischen Variablen kopieren.

Die umgekehrte Konvertierung - von einer Variablen vom Typ tm in einen Wert vom Typ time_t - erfolgt mit Hilfe der Funktion mktime(). Der Prototyp lautet:

time_t mktime(struct tm *ntime);
Diese Funktion liefert die Anzahl der Sekunden, die zwischen Mitternacht des 1. Januar 1970 und der Zeit verstrichen sind, die durch die Variable vom Typ tm, auf die ntime zeigt, dargestellt wird.

Um Zeitangaben in formatierte Strings zu konvertieren, die ausgegeben werden können, gibt es die Funktionen ctime() und asctime(). Beide Funktionen liefern die Zeit als einen String in einem vordefinierten Format zurück. ctime() wird die Zeit als ein Wert vom Typ time_t übergeben wird, während asctime() die Zeit als eine Strukturvariable vom Typ tm entgegennimmt:

char *asctime(struct tm *ptr);
char *ctime(time_t *ptr);
Beide Funktionen liefern einen Zeiger auf einen statischen, nullterminierten 26-Zeichen-String zurück, der die Zeit des Funktionsarguments im folgenden 24-Stunden-Format angibt:
Thu Apr 30 11:22:15 2003
Beide Funktionen verwenden einen statischen String, der bei jedem Aufruf der Funktion überschrieben wird.

Wenn Sie das Format der Zeit ändern wollen, steht Ihnen dazu die Funktion strftime() zur Verfügung. Dieser Funktion wird die zu formatierende Zeitangabe als Strukturvariable vom Typ tm übergeben. Die Formatierung erfolgt anhand eines Formatstrings. Der Prototyp der Funktion lautet:

size_t strftime(char *s, size_t max, char *fmt, struct tm *ptr);
Die Funktion nimmt die zu formatierende Zeitangabe über die tm-Strukturvariable entgegen, auf die der Zeiger ptr weist, formatiert sie nach Vorgabe des Formatstrings fmt und schreibt das Ergebnis als nullterminierten String an die Speicherposition, auf die s zeigt. Das Argument max sollte die Größe des Speicherbereichs angeben, der für s reserviert wurde. Wenn der resultierende String (einschließlich des abschließenden Nullzeichens) mehr als max Zeichen enthält, liefert die Funktion 0 zurück, und der String s ist ungültig. Im anderen Fall liefert die Funktion die Anzahl der geschriebenen Zeichen zurück. Der Formatstring besteht aus einem oder mehreren der folgenden Konvertierungsspezifizierer:

Spezifiziererwird ersetzt durch:
%aAbgekürzter Wochentagsname
%AVoller Wochentagsname
%bAbgekürzter Monatsname
%BVoller Monatsname
%cDatums- und Zeitdarstellung (zum Beispiel, Tue Apr 18 10:41:50 2000)
%dTag des Monats als Dezimalzahl von 01 bis 31
%HDie Stunde als Dezimalzahl von 00 bis 23
%IDie Stunde als Dezimalzahl von 00 bis 11
%jDer Tag des Jahres als Dezimalzahl von 001 bis 366
%mDer Monat als Dezimalzahl von 01 bis 12
%MDie Minute als Dezimalzahl von 00 bis 59
%pAM oder PM
%SDie Sekunde als Dezimalzahl von 00 bis 59
%UDie Woche des Jahres als Dezimalzahl von 00 bis 53. Der Sonntag wird als erster Tag der Woche betrachtet
%wDer Wochentag als Dezimalzahl von 0 bis 6 (Sonntag = 0)
%WDie Woche des Jahres als Dezimalzahl von 00 bis 53. Der Montag wird als erster Tag der Woche betrachtet
%xDatumsdarstellung (zum Beispiel, 30-Jun-91)
%XZeitdarstellung (zum Beispiel, 10:41:50)
%yDas Jahr, ohne Jahrhundert, als Dezimalzahl von 00 bis 99
%YDas Jahr, mit Jahrhundert, als Dezimalzahl
%ZDer Name der Zeitzone, wenn die Information verfügbar ist, oder leer, wenn er nicht bekannt ist
%%Ein einfaches Prozentzeichen %

Sie können den Zeitunterschied zwischen zwei Zeitangaben mit dem Makro difftime() in Sekunden berechnen. Dieses Makro subtrahiert zwei time_t-Werte und liefert die Differenz zurück. Der Prototyp lautet:

double difftime(time_t zeit1, time_t zeit0);
Diese Funktion subtrahiert zeit0 von zeit1 und liefert die Differenz, das heißt die Anzahl der Sekunden zwischen den beiden Zeiten, zurück. Häufig wird difftime() dazu verwendet, die verstrichene Zeit zu berechnen.

Die Funktion clock() gibt an, wie viel Millionstelsekunde seit Beginn der Programmausführung verstrichen sind. Der Prototyp der Funktion lautet:

clock_t clock(void);
Um herauszufinden, wie viel Zeit für die Ausführung eines bestimmten Programmabschnitts benötigt wird, müssen Sie clock() zweimal aufrufen - vor und nach dem betreffenden Codeblock - und dann die beiden Rückgabewerte voneinander subtrahieren.
/* Beispiele fr die Verwendung der Zeitfunktionen. */

#include <stdio.h>
#include <time.h>

int main(void)
  {
  time_t beginn, ende, jetzt;
  struct tm *zgr;
  char *c, string[80];
  double dauer;

  /* Die Zeit des Programmstarts festhalten. */
  beginn = time(0);

  /* Die aktuelle Zeit festhalten. */
  time(&jetzt);

  /* Konvertiert den time_t-Wert in eine Struktur vom Typ tm. */
  zgr = localtime(&jetzt);

  /* Erzeugt einen formatierten String mit der aktuellen */
  c = asctime(zgr);
  puts(c);

  /* Verwendet die strftime()-Funktion, um verschiedene */
  /* formatierte Versionen der Zeit zu erzeugen. */

  strftime(string,80,"Dies ist %U. Woche des Jahres %Y",zgr);
  puts(string);
  
  strftime(string, 80, "Heute ist %A, %m/%d/%Y", zgr);
  puts(string);
  
  strftime(string, 80, "Es ist %M Minuten nach %I.", zgr);
  getc(stdin);

  /* Liest die aktuelle Zeit ein u. berechnet die Programmdauer. */

  ende = time(0);
  dauer = difftime(ende, beginn);
  printf("Ausfhrungszeit mit time() = %f Sekunden.\n", dauer);

  /* Gibt die Programmdauer mit clock() in Mikrosekunden an */
  printf("Ausfhrungszeit mit clock() = %ld .\n", clock());
      
  return(0);
  }

Datumsarithmetik

Die meisten dieser Algorithmen sind in der Literatur seit langem festgelegt. Es handelt sich um relativ einfache Berechnungen, weshalb keine Struktogramme beigefügt sind. Meine Informationen stammen aus einer Artikelserie von Heinz Zemanek in "Elektronische Rechenanlagen" 6/78, 4/79 und 6/79 und aus Jean Meeus: Astronomische Algorithmen, Barth, 1992, ISBN 3-335-00318-7.

Julianischer Tag

Es gäbe kein Jahr-2000-Problem, wenn alle Programmierer und Computerhersteller die Julianische Tageszahl für das Datum verwendet hätten. Stattdessen wurde das Jahr als Zeichenkette (TTMMJJ) gespeichert und das führte dazu, daß nach 99 das Jahr 00 kommt. Grund für die zweistellige Speicherung der Jahreszahl war der Zwang zum Speichersparen. Auch hier liegt die Julianische Tageszahl vorne, sie hätte noch weniger Speicher gebraucht.
Die Julianische Tageszahl - oder einfacher der Julianische Tag - ist eine fortlaufende Zählung der Tage, beginnend mit dem Tag 0, der am 1. Januar 4713 v. Chr. (im proleptischen Julianischen Kalender) um 12 Uhr Mittags begann. Dementsprechend beginnt ein neuer Julianischer Tag auch immer um 12 Uhr Mittags, was ursprünglich für die europäische Astronomie den Vorteil besaß, daß alle Beobachtungen einer Nacht an einem einzigen Julianischen Tag stattfanden.
Die Julianische Tageszählung läßt sich durch Anhängen des seit 12 Uhr Mittags verflossenen Tagesbruchteils leicht zu einer genauen Zeitangabe erweitern. So bezeichnet JD 2'451'605 den Tag, der am 1. März 2000 um 12 Uhr beginnt, während JD 2'451'605.25 den Zeitpunkt um 18 Uhr desselben Tages bestimmt. Diese Erweiterung wird in vielen Quellen als Julianisches Datum bezeichnet.
Julianische Tage wurden früher in der Regel (sofern nichts anderes spezifiziert wurde) nach mittlerer Sonnenzeit gezählt, heute nach UT. Die Weltzeit oder Universal Time (UT) wurde 1926 als Ersatz für die Greenwich Mean Time (GMT) eingeführt. Zur dieser Zeit waren mehrere, zum Teil deutlich unterschiedliche Bedeutungen von GMT im Gebrauch. UT ist für meisten praktische Belange gleichzusetzen mit der mittleren Sonnenzeit bezogen auf den Nullmeridian von Greenwich. Alternativ wurden Angaben auch in Ephemeridenzeit gemacht, was durch die Bezeichnung JED oder JDE gekennzeichnet wurde. Auch heute ist gelegentlich sinnvoll, Julianische Tage in einer anderen als der UT-Skala anzugeben. Die verwendete Zeitskala ist dann an die Zeitangabe anzuhängen, z.B. als JD 2 451 545.0 TDT für den 1.Januar 2000, 12 Uhr Mittags nach TDT-Zeit.
Häufig finden sich auch Zeitangaben in einem Modifizierten Julianischen Datumsformat (MJD). Die gebräuchlichste Definition eines MJD folgt aus MJD = JD - 2400000.5 der Nullpunkt liegt daher beim 17. November 1858 um 0 Uhr (!) Weltzeit. Andere Definitionen existieren allerdings auch, so daß bei der Verwendung von Daten in MJD Vorsicht geboten ist. Aus diesem Grunde wird MJD auch von der Internationalen Astronomischen Union nicht anerkannt.
Die Bedeutung der Julianischen Tagesangabe in der heutigen Astronomie liegt zum einen in der Möglichkeit einer kompakten, eindeutigen Zeitangabe, zum anderen in der einfachen Angabe und Berechnung von Zeitdifferenzen, Perioden usw.
Die Julianische Tageszählung wurde 1581 von dem französischen Gelehrten Joseph Justus Scaliger (in seinem Werk 'Opus novum de emendatione temporum') eingeführt, um eine eindeutige Zeitzählung ohne negative Jahreszahlen zu erhalten. Dazu mußte der Anfang der Zeitzählung genügend weit in der Vergangenheit in vorhistorischen Zeiten liegen. Scaliger konstruierte zunächst eine 7980 Jahre währende Julianische Periode, indem er folgende Zyklen kombinierte: Das letzte Jahr, in dem alle drei Zyklen gemeinsam einen neuen Durchlauf begannen, war 4713 v. Chr. Den 1. Januar dieses Jahres legte Scaliger als Beginn seiner Zeitrechnung fest. Für die meisten Menschen der damaligen Epoche war dieses Datum allerdings fiktiv, da nach ihrem Glauben die Welt erst wesentlich später erschaffen wurde. Scaliger selbst datierte die Erschaffung der Erde auf das Jahr 3267 v.Chr.

Der Algorithmus stellt sich dann folgendermaßen dar:
Y = Jahr, M = Monat (Januar = 1, Februar = 2, etc.),
D = Tag (eventuell mit Tagesbruchteilen)

Ist M > 2 lasse Y und M unverändert. 
Ist M = 1 oder M = 2 dann ist
   Y = Y - 1 
   M = M + 13 

Im Gregorianischen Kalender rechnet man weiter:
   A = INT (Y/100) 
   B = 2 - A + INT (A/4) 
Im Julianischen Kalender ist B = 0! 

Das gesuchte JD ist dann:
   JD = INT (365.25 * (Y + 4716)) 
   + INT (30.6001 * (M + 1)) + D 
   + B - 1524.5 
Das Programm zum Berechnen des Julianischen Datums stellt sich dann folgendermaßen dar. Beachten Sie, daß wegen der Besonderheit des Julianischen Datums der Tag nicht als Integer, sondern als Gleitpunktzahl dargestellt wird. Im Programm ist noch ein zweites Unterprogramm enthalten, das den JD wieder in unser gewohntes Datumsformat, das Gregorianische Datum, umrechnet:
#include <stdio.h>
#include <stdlib.h>

struct datum 
          {
          double tag;
          int monat;
          int jahr;
          };

double julian_day(double day, int month, int year);
struct datum gregorian_date(double jday);

int main(void)
  {
  int tag, monat, jahr;
  double jd;
  struct datum dat;

  printf("Tag, Monat und Jahr eingeben: ");
  scanf("%d %d %d",&tag, &monat, &jahr);
  jd = julian_day(1.0*tag, monat, jahr);
  printf("\nJulianischer Tag fuer den %d.%d.%d = %1.2f\n", 
         tag, monat, jahr, jd);
  dat = gregorian_date(jd);
  printf("\nZurueckgerechnet: %1.0f.%d.%d\n", dat.tag, dat.monat, dat.jahr);
  return 0;
  }


/* Julianischer Tag (>=1):
 * Gegeben: tag, monat, jahr
 *
 * Die gregorianische Kalenderreform wird beruecksichtigt (der Tag, der
 * auf den 4. Oktober 1582 folgt ist der 15. October 1582
 * Tage nach dem 15. Oktober 1582 werden als "Gregorianischer Kalender"
 * bezeichnet. Der Julianische Tag beginnt um 12 Uhr GMT (Mittag).
 * Um beliebige Uhrzeiten beruecksichtigen zu koennen, werden die Tage
 * nicht als Integer- sondern als Gleitpunktzahlen angegeben.
 */
double julian_day(double day, int month, int year)
  {
  int atmp, btmp, monthp, yearp;
  double ctmp;
  if (month > 2) 
    {
    monthp = month + 1;
    yearp = year;
    }
  else
    {
    monthp = month + 13;
    yearp = year - 1;
    }
  if ((year > 1582) || (year == 1582 && month >= 10)
     || (year == 1582 && month ==10 && day >= 15))
    {
    atmp = year / 100;
    btmp = 2 - atmp + (atmp / 4);
    }
  else
    btmp = 0;
  atmp = 365.25 * yearp;
  ctmp = atmp;
  atmp = 30.6001 * monthp;
  ctmp =  ctmp + atmp;
  return (ctmp + day + 1720994.5 + btmp);
  }

/* gregorian_date: Umrechnung Julianischer Tag 
   in (Tag, Monat, Jahr) */
struct datum gregorian_date(double jday)
  {
  int atmp, btmp, ctmp, dtmp, etmp, gtmp, ztmp;
  double ftmp;
  struct datum dd;

  ztmp = jday + 0.5;
  ftmp = (jday + 0.5) - ztmp;
  if (ztmp >= 2299161) 
    {
    gtmp = (ztmp - 1867216.25) / 36524.25;
    ctmp = gtmp / 4;
    atmp = ztmp + 1 + gtmp - ctmp;
    }
  else
    atmp = ztmp;
  btmp = atmp + 1524;
  ctmp = (btmp - 122.1) / 365.25;
  dtmp = 365.25 * ctmp;
  etmp = ((btmp - dtmp) / 30.6001);
  ztmp = 30.6001 * etmp;
  dd.tag = btmp - dtmp - ztmp + ftmp;
  if (etmp > 13.5)
    dd.monat = etmp - 13;
  else
    dd.monat = etmp - 1;
  if (dd.monat > 2.5)
    dd.jahr = ctmp - 4716;
  else
    dd.jahr = ctmp - 4715;
  return(dd);
  }

Datumsrechnung

Mit Hilfe des Julianischen Tages wir die Datumsrechnung relativ einfach. Zuerst die wichtigste Funktion, die Schaltjahresberechnung:

Schaltjahr

#include <stdio.h>
#include <stdlib.h>

int schaltjahr(int YY);

int main(void)
  {
  int jahr;
  printf("Jahr eingeben: ");
  scanf("%d", &jahr);
  if (schaltjahr(jahr))
    printf("\n%d ist Schaltjahr\n", jahr);
  else
    printf("\n%d ist KEIN Schaltjahr\n", jahr);
  return 0;
  }

int schaltjahr(int yy)
  /* 1, falls Schaltjahr, sonst 0 */
  {
  int sj;
  if      ((yy%400) == 0) sj = 1;
  else if ((yy%100) == 0) sj = 0;
  else if ((yy%4) == 0) sj = 1;
  else    sj = 0;
  return(sj);
  }

Die Funktion liefert einen Integerwert und man kann dann beispielsweise auch die Anzahl der Tage eines Jahres berechnen:
tage_im_jahr = 365 + schaltjahr(jahr);

Wochentagsberechnung

Die Wochentagsberechnung ist absolut einfach, wenn man den Julianischen Tag hat. Ergebnis: Wochentag 0=So, 1=Mo, 2=Di, 3=Mi, 4=Do, 5=Fr, 6=Sa:
wochentag = (Julianischer Tag + 1.5) % 7
Fur Daten nach dem 15.10.1582 gibt es noch einen andere Berechnungsweise:
/* Wochentagsberechnung aus Tag, Monat, Jahr (4-stellig) */
/* Ergebnis: Wochentag 0=So, 1=Mo, 2=Di, 3=Mi, 4=Do, 5=Fr, 6=Sa */
#include <stdio.h>
#include <stdlib.h>

int wota(int tt, int mm, int yy);

int main(void)
  {
  int tag, monat, jahr;
  printf("Tag, Monat und Jahr eingeben: ");
  scanf("%d %d %d",&tag, &monat, &jahr);

  printf("\nDer Wochentag ist %d\n", wota(tag, monat, jahr));

  return 0;
  }

int wota(int tt, int mm, int yy)
  {
  int wt, y, c;

  if (mm < 3)
    {
    mm = mm + 12;
    yy = yy - 1;
    }
  y = yy%100;
  c = yy/100;
  wt = (tt + (mm+1)*13/5 + y + y/4 + c/4 -2*c)%7;
  if (wt < 0) wt = wt + 7;
  return(wt);
  }

Jahrestag

Der Jahrestag reduziert sich auf eine effektive Zeile:
int day_of_year(double day, int month, int year)
  {
  return ((int) julian_day(day, month, year)
          - (int) julian_day(0.0, 1, year));
  }

Ebenso kann man auch ausrechen, wieviele Tage das Jahr noch hat:
days_remaining_in_year(double day, int month, int year)
  {
  return (365 + schaltjahr(year) - day_of_year(day, month, year));
  }

Der n-te Wochentag im Monat

Oft richten sich bestimmte Termine nicht nach einem Datum, sondern nach einem bestimmten Wochentag in der Nähe eines Datums, z. B. der erste Montag im Monat oder für Gehaltszahlung der letzte Donnerstag des Monats. Die Berechnung dafür liefert folgendes Unterprogramm. Gegeben wird der Wochentag (0 = Sonntag, 1 = Montag, usw.), der wievielte Wochentag es sein soll (1 - 5), Monat und Jahr (ab 1583).
int nth_day_of_week(int n, int day_of_week, int month, int year)
  {
  int atmp, btmp, ctmp, dtmp, etmp, ftmp, tmonth, tyear;

  if (month > 2) 
    {
    tmonth = month + 1;
    tyear = year;
	}
  else
    {
    tmonth = month + 13;
    tyear = year - 1;
    }
  atmp = 2.6 * tmonth;
  btmp = 1.25 * tyear;
  ctmp = (tyear / 100) - 7;
  dtmp = 0.75 * ctmp;
  etmp = (day_of_week - atmp - btmp + dtmp) % 7;
  if (etmp == 0)
    { 
    ftmp = 7; 
    n--; 
    }
  else
    ftmp = etmp;
  return (ftmp + (n * 7));
  }

Osterdatum (und bewegl. Feste)

Das christliche Osterfest ist aus dem jüdischen Passahfest abgeleitet, das am ersten Frühlingsvollmond beginnt. Dieser Tag kann offensichtlich auf einen beliebigen Wochentag fallen, Ostern beginnt dagegen definitionsgemäß am einem Sonntag. Ursprünglich war die Festlegung des Ostertermins sehr uneinheitlich geregelt in den verschiedenen christlichen Gemeinden. Erst im 1. Konzil von Nicäa im Jahre 325 n. Chr. einigte man sich auf die Formel, daß Ostern auf den ersten Sonntag nach dem Frühlingsvollmond nach der Frühjahrs-Tagundnachtgleiche fällt. Der erste Frühlingsvollmond ist dabei der erste Vollmond, der am Tag der Frühjahrs-Tagundnachtgleiche oder danach stattfindet.
Mit dem Beschluß von Nicäa waren aber die Schwierigkeiten nicht endgültig beseitigt, weil die genaue Festlegung des ersten Frühlingsvollmonds eigene Probleme mit sich brachte. Schließlich setzte der römische Abt Dionysius Exiguus auf Veranlassung von Papst Johannes I im Jahre 525 n. Chr. die in Alexandria übliche Rechnung durch. Danach wird
  1. der Frühlingsbeginn auf den 21. März 0 Uhr festgesetzt und
  2. von einem gleichmäßig auf einer Kreisbahn umlaufenden Mond ausgegangen.
Beide Annahmen sind Vereinfachungen, die zu Abweichungen von den wahren astronomischen Gegebenheiten führen. So findet der wahre Frühlingsbeginn etwa zwischen dem 19. März 8 Uhr und dem 21. März 20 Uhr UT statt. Berücksichtigung der wahren Mondbahn liefert Differenzen von bis zu +/- 0.7 Tagen gegenüber einer kreisförmigen Bahn. Ferner sind seit der Gregorianischen Kalenderreform zusätzliche Datumsbeschränkungen zu berücksichtigen, denen zufolge Ostern zwischen dem 22. März und dem 25. April (jeweils einschließlich) liegen muß. Aus diesen Gründen kommt es zu Verschiebungen des faktischen Osterdatums gegenüber dem astronomisch korrekt berechneten Datum, die als 'Osterparadoxien' bezeichnet werden. Die letzte Paradoxie fand im Jahre 1974 statt (Ostern war am 14. April statt am 7. April), die nächste findet im Jahr 2000 statt (23. April statt 26. März).
Durchgeführt wird die Osterrechnung heute durch die kirchlichen Ostertafeln (Tabellenwerke, die zu diesem Zwecke angelegt wurden) oder durch die Osterformel von Carl Friedrich Gauß. Beide Verfahren gelten für alle Jahre ab 532 n.Chr. Hier das Unterprogramm zu Berechnung des Osterdatums und ein Testprogramm dazu.
/* Berechnung des Osterdatums nach C. F. Gauss */
#include <stdio.h>
#include <stdlib.h>

struct datum 
          {
          int tag;
          int monat;
          int jahr;
          };
  
struct datum ostern(int yy);

int main(void)
  {
  int jahr;
  struct datum dat;
  printf("Jahr eingeben: ");
  scanf("%d", &jahr);
  dat = ostern(jahr);
  printf("\nOstern faellt %d auf den %d.%d.\n",dat.jahr, dat.tag, dat.monat);
  return 0;
  }

struct datum ostern(int year)
 /* Osterdatum */
  {
  int atmp, btmp, ctmp, dtmp, etmp, ftmp,
      gtmp, htmp, itmp, ktmp, ltmp, mtmp;
  struct datum dd;

  atmp = year % 19;
  btmp = year / 100;
  ctmp = year % 100;
  dtmp = btmp / 4;
  etmp = btmp % 4;
  ftmp = (btmp + 8) / 25;
  gtmp = (btmp - ftmp + 1) / 3;
  htmp = ((19 * atmp) + btmp - dtmp - gtmp + 15) % 30;
  itmp = ctmp / 4;
  ktmp = ctmp % 4;
  ltmp = (32 + (2 * etmp) + (2 * itmp) - htmp - ktmp) % 7;
  mtmp = (atmp + (11 * htmp) + (22 * ltmp)) / 451;
  dd.monat = (htmp + ltmp - (7 * mtmp) + 114) / 31;
  dd.tag = ((htmp + ltmp - (7 * mtmp) + 114) % 31) + 1;
  dd.jahr = year;
  return(dd);
  }

Die anderen beweglichen Feste lassen sich aus dem Osterdatum ableiten: Das Vorgehen ist ganz einfach. Man rechnet das Osterdatum in den Julianischen Tag um, addiert die o. a. Verschiebung und rechnet das Ergebnis wieder ins Gregorianische Datum um.

Datums- und Zeitfunktionen

Die ANSI-C-Standard-Bibliothek stellt Funktionen zur Verfügung, die einen Zugriff zur Systemuhr ermöglichen: Es werden drei verschiedenen Zeitdarstellungen verwendet: Die entsprechenden Funktionsdefinitionen befinden sich in der Standard-Header-Datei <time.h>. Diese ist daher bei Verwendung der Funktionen mittels #include <time.h> einzubinden. In <time.h> sind außerdem definiert:

Konstante CLK_TCK Anzahl der Perioden (ticks) der Systemzeit pro Sekunde

Typ clock_t

Arithmetischer Datentyp zur Darstellung der Zeit

Typ time_t

Arithmetischer Datentyp zur Darstellung der Zeit
Typ tm Structure-Typ zur Darstellung der Kalenderzeit

Der Typ tm muß wenigstens die folgenden Komponenten enthalten :

   int tm_sec;   /* Sekunden nach der Minute  [0 .. 59] */
   int tm_min;   /* Minuten nach der Stunde   [0 .. 59] */
   int tm_hour;  /* Stunden seit Mitternacht  [0 .. 23] */
   int tm_mday;  /* Tag des Monats            [0 .. 31] */
   int tm_mon;   /* Monate seit Januar        [0 .. 11] */
   int tm_year;  /* Jahre seit 1900                     */
   int tm_wday;  /* Tage seit Sonntag         [0 ..  6] */
   int tm_yday;  /* Tage seit 1.Januar        [0 ..365] */
   int tm_isdst; /* Sommerzeit-Flag                     */

Für den Wert des Sommerzeit-Flags tm_isdst gilt:

Funktionen zur Ermittlung von Zeiten und Zeitdifferenzen

clock_t clock(void); Ermittlung der Prozessorzeit, die seit Programmstart vergangen ist, in Systemzeit-Perioden (ticks).
clock()/CLK_TCK ist die Zeit in Sekunden.
Funktionswert = (clock_t)-1, wenn die Prozessorzeit nicht verfügbar ist.
time_t time(time_t *timer); Ermittlung der Kalenderzeit in einer implementierungsspezifischen Darstellung.
Falls timer!=NULL wird der Funktionswert auch *timer zugewiesen.
Funktionswert = (time_t)-1, wenn Kalenderzeit nicht verfügbar ist.
double difftime(time_t t2, time_t t1); Bildung der Zeitdifferenz t2 - t1 ausgedrückt in Sekunden (t2 und t1 enthalten Zeiten in implementierungsspezifischer Darstellung!)

Funktionen zur Umwandlung von Zeitdarstellungen

struct tm *gmtime(const time_t *tp); Umwandlung der in implementierungsspezifischer Darstellung vorliegenden Kalenderzeit *tp in eine strukturierte Darstellung der Coordinated Universal Time (UTC).
Falls die UTC nicht ermittelt werden kann, ist der Funktionswert = NULL
struct tm *localtime(const time_t *tp); Umwandlung der in implementierungsspezifischer Darstellung vorliegenden Kalenderzeit *tp in eine strukturierte Darstellung der Ortszeit.
time_t mktime(struct tm *tptr); Umwandlung der in strukturierter Darstellung vorliegenden Ortszeit *tptr in die implementierungsspezifische Darstellung der Kalenderzeit.
Die Werte der einzelnen Strukturkomponenten müssen nicht normiert sein. Die Funktion führt zusätzlich ihre Normierung durch und berechnet die Werte für die Komponenten tm_wday und tm_yday.
Falls keine darstellbare Kalenderzeit ermittelt werden kann, erzeugt die Funktion den Wert (time_t)-1.

Funktionen zur Darstellung von Zeiten als Strings

char *asctime(const struct tm *tptr); Umwandlung der in strukturierter Darstellung vorliegenden Ortszeit *tptr in einen String der folgenden Form:
"Sun Apr 14 11:23:22 1991\n\0"
Der Funktionswert ist Pointer auf diesen String.
char *ctime(const time_t *tp); Umwandlung der in implementierungsspezifischer Darstellung vorliegenden Kalenderzeit *tp in einen String der folgenden Form:
"Sun Apr 14 11:23:22 1991\n\0"
Der Funktionswert ist Pointer auf diesen String. ctime(tp) ist äquivalent zu asctime(localtime(tp)).
size_t strftime( char *s, size_t smax, const char *fmt, const struct tm *tptr); Ablage von in *tptr enthaltenen Zeit- und Datumsinformationen in den String s gemäß den im String fmt enthaltenen Formatspezifikationen.
Jeder sonstiger Text in fmt wird nach s übernommen. Der String s darf maximal smax Zeichen lang werden.
Funktionswert:
  • Anzahl der in s abgelegten Zeichen ohne abschließendes '\0'), wenn diese <=smax ist.
  • 0, wenn s länger als smax Zeichen werden würde. Der Inhalt von s ist in diesem Fall undefiniert.

Format-Spezifier für strftime():
%a    abgekürzter Name des Wochentags
%A    ausgeschriebener Name des Wochentags
%b    abgekürzter Name des Monats
%B    ausgeschriebener Name des Monats
%c    geeignete Darstellung der lokalen Zeit (Datum und Zeit)
%d    Tag des Monats als Dezimalzahl (01 .. 31)
%H    Stunde als Dezimalzahl (24-Std-Uhr) (00 .. 23)
%I    Stunde als Dezimalzahl (12-Std-Uhr) (01 .. 12)
%j    Tag des Jahres als Dezimalzahl (001 .. 386)
%m    Monat als Dezimalzahl (01 .. 12)
%M    Minute als Dezimalzahl (00 .. 59)
%p    PM oder AM (oder landesspezifisches Žquivalent)
%S    Sekunde als Dezimalzahl (00 .. 59)
%U    Woche des Jahres dezimal (Sonntag ist 1. Tag der Woche) (00 .. 53)
%w    Wochentag als Dezimalzahl (Sonntag = 0) (0 .. 6)
%W    Woche des Jahres dezimal(Montag ist 1. Tag der Woche) (00 .. 53)
%x    geeignete Darstellung des lokalen Datums
%X    geeignete Darstellung der lokalen Zeit
%y    (Jahr - Jahrhundert) als Dezimalzahl (00 .. 99)
%Y    Jahr als Dezimalzahl (einschließlich Jahrhundert)
%Z    Name der Zeitzone, falls ein Name existiert
%%    Das Zeichen %

8.3 Numerik

Primzahlen

Zerlegung in Primfaktoren oder die Aussage, ob eine Zahl Primzahl ist, wird bei verschiedenen Algorithmen genötigt, z. B. bei Kryptoverfahren. Um festzustellen, ob es sich um eine Primzahl handelt, kann man die Zahl X durch alle Zahlen teilen, die kleiner oder gleich X/2 sind; also durch 1, 2, 3, 4, 5, 6, 7, usw. Ist die Zahl durch keine der Zahlen teilbar, muß sie prim sein. Der Algorithmus kann dahingehnd verbessert werden, daß nur die ungeraden Faktoren und die 2 geprüft werden. im folgenden Programm liefert die Funktion is_prim() nur die Information darüber, ob eine Zahl prim ist, die Funktion primfaktoren() druckt die Primfaktoren einer Zahl.
#include <stdio.h>
#include <ctype.h>
#define TRUE 1
#define FALSE 0

long int getlong();
int is_prim(long int i);  
void primfaktoren(long int i);  

void main(void) 
  {	
  long int n, von, bis;
  printf("Berechnung der Primzahlen des Zahlenintervalls\n");

  printf("\nGeben Sie die untere Intervallgrenze ein:");
  von = getlong();
  
  printf("\nGeben Sie die obere Intervallgrenze ein:");
  bis = getlong();
  
  n = von;
  while(n <= bis) 
    {
    if (is_prim(n))
      printf(" %ld\n", n);
    n++;
    }
  }

int is_prim(long int i)  
  /* liefert TRUE, falls i eine Primzahl ist */
  {
  long int i;
  long int j;
  if (i < 2) return(FALSE);
  j = 2;
  while (j*j <= i) 
    {
    if (i % j == 0) 
      return (FALSE);
    else if (j == 2)
      j = 3;
    else 
      j = j + 2;
	}
	return (TRUE);
  }

void primfaktoren(long int i)  
  /* Druckt Primfaktoren einer Zahl */
  {
  long int i;
  long int j = 2;
  while (j*j <= i) 
    {
    while ((i%j) != 0)
      {
      if (j == 2)
        j = 3;
      else 
        j = j + 2;
      }
    i = i/j;
    printf(" %ld", j);
	}
  if (i > 1)
    printf(" %ld", i);
  printf("\n");
  }

long int getlong () 
  /* Ziffernfolge lesen und in long konvertieren */
  {
  long int i = 0;
  int c;
  c = getchar();
  while (isdigit(c)) 
    {
    i = 10*i + c - '0';
    c = getchar();
    }
  return(i);
  }

Auflösen arithmetischer Ausdrücke

U. a. ist die Aufgabe von Compilern das Aufbrechen von Formeln in eine für die lineare Maschinensprache geeignete klammerlose Form (Postfix-Notation). Auch die direkte Interpretation einer Formeleingabe ist eine häfig gestellte aufgabe, z.B. bei Kalkulationsprogrammen oder Formelinterpretern. Wie ein Arithmetischer Ausdruck aufgebaut ist, kann mit dem Schon bekannten Syntaxdiagrammen dargestellt werden - oder man verwendet die Textvariante, die Backus-Naur-Darstellung. Beim vorgesehenen Formelinterpreter sollen die vier Grundrechenarten sowie Klammerung realisiert werden. Natürlich gilt auch hier "Punkt vor Strich". Eine Formel kann dann folgendermaßen definiert werden:
     Ausdruck ::= Term { + Term | - Term }
     Term     ::= Faktor { * Faktor | / Faktor }
     Faktor   ::= Zahl | ( Ausdruck )
     Zahl     ::= [-] Ziffer {Ziffer} [. {Ziffer}]
     Ziffer   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Dabei bedeutet: Die Ziffern sowie die Zeichen '(', ')', '+', '-', '*', '/' sind Terminalsymbole.

Zur Programmierung: Die folgenden Funktionen geben genau die Definition wieder ­ für Ausdruck, Term und Faktor müssen jeweils die Prozeduren definiert werden, die sich dann gegenseitig rekursiv aufrufen.
Es muß immer nur das nächste Eingabezeichen betrachtet werden, um die Aufgabe zu lösen ­ daher reicht getchar() aus. Das gelesene Zeichen c ist global definiert. Die folgenden Ansätze sind in einer Art "Pseudocode" skizziert, und ohne Deklarationen.

Ausdruck:
  {
  wert = term;
  solange (c in ['+','-'])
    {
    falls (c = '+') wert = wert + term;
    falls (c = '-') Wert = wert ­ term;
    }
  Ausdruck = wert;
  }

Term:
  {
  wert = faktor;
  solange (c in ['*','/'])
    {
    falls (c = '*') wert = wert * faktor;
    falls (c = '/') Wert = wert / faktor;
    }
  Term = wert;
  }
  
Faktor:
  {
  Lies ein Zeichen c von der Eingabe;
  wenn (c in ['0'..'9']) wert = Zahl;
  wenn (c = '(') 
    { 
    wert = Ausdruck; 
    Lies schlieîende Klammer;
    }
  Faktor = Wert;
  }
 
Zahl:
  { 
  Lies eine Zahl mit Vorzeichen zeichenweise ein;
  }

Damit das Bearbeiten eines Ausdrucks nicht nur von der Eingabe, sondern auch z. B. aus einem String heraus leicht möglich ist, definieren wir noch eine Funktion int lies() die dem Einlesen eines Zeichens dient.

#include <stdio.h>
#define FALSE 0
#define TRUE 1

int   c;            /* eingelesenes Zeichen */
float wert;         /* Ergebniswert */

/* Funktionen-Vorwaertsdeklaration */
float ausdruck(); 
float term();     
float faktor(); 
float zahl();   
int   lies(); 

main()
  {
  do
    {                                  
    printf("Eingabe : ");               /* Eingabeaufforderung */
    wert = ausdruck();                  /* Einlesen und Berechnen */
    printf("Ergebnis: %0.5f\n\n",wert); /* 5 Nachkommastellen */
    }
  while (c != EOF);                    /* Ende mit Ctrl-D oder Ctrl-Z */
  }


int lies()
  /* Einlesen eines Zeichens, Leerzeichen übergehen */
  {
  while((c = getchar()) == ' ');
  return(c);
  }

float ausdruck()
  /* Ausdruck ::= Term { +Term || -Term } */
  {  
  float wert;
  wert = term();                
  while (c == '+' || c == '-')  
    {
    if (c == '+') wert = wert + term();
    if (c == '-') wert = wert - term();
    }
  return(wert);
  } 

float term()
  /* Term ::= Faktor { *Faktor || /Faktor } */
  {  
  float wert;
  wert = faktor();
  while (c == '*' || c == '/')
    {
    if (c == '*') wert = wert * faktor();
    if (c == '/') wert = wert / faktor();
    }
  return(wert);
  }

float faktor()
  /* Faktor :== Zahl || ( Ausdruck ) */
  {  
  float wert;
  c = lies();                          /* erst hier wird gelesen */
  if (('0' <= c && c <= '9') || (c == '-'))
    wert = zahl();
  if (c == '(')                        /* rekursiver Aufruf! */
    {
    wert = ausdruck();
    c = lies();                        /* ')' wird ueberlesen */
    }
  return(wert);
  }

float zahl()
  /* Zahl ::= [-] Ziffer {Ziffer} [.{Ziffer}] */
  {  
  float wert, teiler;
  int negativ = FALSE;                /* Merker fr neg. Vorzeichen */
  int bruch   = FALSE;                /* Merker fr Dezimalpunkt */
  wert = 0.0; teiler = 1.0;
 if (c == '-')                        /* Vorzeichen merken */
    {
    negativ = TRUE;
    c = lies();
    }
  while (('0' <= c && c <= '9') || (c == '.'))
    {                                  /* Zahl konvertieren */
    if (c == '.')                      /* Dezimalpunkt */
      bruch = TRUE;
    else
      {
      wert = wert * 10.0 + (c - '0');  /* weitere Stelle dazu */
      if (bruch) teiler = teiler*10.0; /* fr Nachkommastellen */
      }
    c = lies();                        /* n„chstes Zeichen */
    }
  if (negativ) wert = -wert;
  if (bruch)                           /* nur dann ist teiler != 0 */
    return(wert/teiler);               /* Dezimalpunkt beachten */
  else
    return(wert);
  }

Nullstellenberechnung

Die Nullstelle einer Funktion f(x) soll näherungsweise bestimmt werden. Das Aufsuchen der Nullstelle einer Funktion f(x) entspricht der Lösung der Gleichung f(x) = O. Ist das Intervall [a, b] bekannt, in dem sich die Nullstelle befindet, so kann dieses halbiert werden und aufgrund des Funktionswertes an der Halbierungsstelle überprüft werden, ob sich die Nullstelle im linken oder im rechten Teilintervall befindet. Dieses Intervall wird nach dem gleichen Verfahren wieder halbiert. Dieses als Bisektion bezeichnete Verfahren wird solange wiederholt, bis das Intervall genügend klein ist.

Zur Programmierung dieses Verfahrens ist es günstig, eine Funktion zu vereinbaren, die als Ergebnis den Näherungswert der Nullstelle einer Funktion float f() liefert:

float nullstelle(float a, float b)
  {
  float X;
  do
    {
    X = (a + b )/2.0;
    if (f(a)*f(b) > 0)
      a = X;
    else
      b = X;
    }
  while ((b - a) > EPS);
  return(X);

Die Parameter a und b werden hier als lokale Hilfsvariable verwendet. Mit EPS wird dabei die Genauigkeit bezeichnet, ein Wert, der nahe beim kleinsten darstellbaren Wert für float liegt. Definition beispielsweise über #define EPS 1.0-10.

Anstatt das Intervall in jedem Iterationsschritt zu halbieren, kann es auch im Verhältnis der Funktionswerte an den Intervallgrenzen geteilt werden. Dieses als Regula Falsi bezeichnete Verfahren führt im allgemeinen rascher zum Ziel. In der obigen Funktion muß zu diesem Zweck die Anweisung

X = (a + b)/2.0;
durch
X = a - f(a)*(b-a)/(f(b)-f(a))
ersetzt werden. Um die wiederholte Berechnung der Funktionswerte f(a) und f(b) zu vermeiden, wurden im nachfolgenden Programmbeispiel Hilfsvariable fa, fb und fx verwendet.
float nullstelle(float a, float b)
  {
  float X, fa, fb, fx;
  fa = f(a);
  fb = f(b);
  do
    {
    X = a - fa*(b - a)/(fb - fa);
    fx = f(X);
    if (fa*fx > 0)
      a = X; fa = fx;
    else
      b = X; fb = fx;
    }
  while ((b - a) > EPS);
  return(X);

Das Verfahren von NEWTON erlaubt die näherungsweise Bestimmung der Nullstelle einer Funktion, deren Ableitung bekannt ist. Von einem Näherungswert X0 ausgehend, wird eine verbesserte Näherung X1 bestimmt, indem die Tangente an die Funktion an der Stelle f(X0) mit der X-Achse geschitten wird:

Die verbesserte Näherung X1 berechnet sich zu

X1 = X0 - f(X0)/f'X0

Die Vorschrift wird solange wiederholt, bis sich keine nennenswerte Verbesserung mehr ergibt. Man kann die Ableitung der Funktion annähern, indem man den Differenzenquotienten verwendet (df = (f(X+dH) - f(X))/dH;). Bei Funktionen, deren Ableitungsfunktion bekannt ist, kann man bei der Zuweisung an Fs auch der Funktionswert der Ableitungsfunktion berechnet werden.

double Newton (double X0, double Eps, int ItMax)
  /* X0: Startwert der Nullstellenbestimmung    */    
  /* Eps: Genauigkeit der Nullstellenbestimmung */    
  /* ItMax: Maximale Anzahl der Iterationen     */    
  {
  double Xi, Fi, Fs;
  double dH = 1.e-6;
  int    it = 0; 

  Xi = X0;                    /* Startwert */
  Fi = f(X0);                 /* Funktionswert bei X0 */
  Fs = (f(X0+dH) - f(X0))/dH; /* numerische Ableitung f'(X0) */
  do
    {
    /* verschwindende Ableitung abfangen */
    if (fabs(Fs) < Eps)
      return Xi;
    /* Genauigkeit ueberpruefen */
    if (fabs(Fi) < Eps)
      return Xi;
    /* Berechnung des neuen Funktionswerts */
    Fi = f(Xi);
    Fs = (f(Xi+dH) - f(Xi))/dH; /* numerische Ableitung */
    Xi = Xi - Fi/Fs;
    it++;
    }
  while ((it < ItMax));
  return Xi;
  }

Numerische Integration

Zur numerischen Integration einer Funktion kann diese in kleine Intervalle unterteilt werden. Innerhalb der Intervalle wird der Funktionsgraph durch Geraden angenähert.

Der Wert des Integrals wird durch die Summe der Tapezflächen angenähert:

Zur Programmierung dieses Näherungsverfahrens wird eine Funktion verwendet, bei der die Intervallgrenzen sowie die Anzahl der Teilintervalle vorgegeben werden. Die zu integrierende Funktion wird definiert als Funktion float f().

float integral(float a, float b, int anz)
  {
  float sum, h;
  int i;
  
  h = (b - a)/anz;
  sum = (f(a) + f(b))/2.0;
  for(i = 1; i < anz; i++)
    sum = sum + f(a + float(i)*h);
  return(h * sum);
  }

Genauere Resultate erzielt man, wenn beim Integrieren nicht Geraden, sondern Parabelstücke verwendet werden. Die von SIMPSON gefundene Näherungsformel lautet dann

Die folgende Programmvariante verwendet die Simpson-Formel:

float integral(float a, float b, int anz)
  {
  float sum, h;
  int i, k;
  
  h = (b - a)/anz;
  k = 2;
  sum = f(a) + f(b);
  for(i = 1; i < anz; i++)
    {
    k = 6 - k;   /* 4, 2, 4, 2, ... */
    sum = sum + float(k)*f(a + float(i)*h);
    }
  return(h/3.0 * sum);
  }

Gausselimination (lin. Gleichungen)

Eine der ältesten direkten Methoden zur Lösung von linearen Gleichungssystemen ist die Gauss-Elimination. Gegeben ist ein Gleichungssystem

Ax = b

Wird die k-te Gleichung nach der Unbekannten xk aufgelöst, gilt für akk ungleich 0:

Bei der Gaußschen Eliminationsmethode werden die Ausgangsgleichungen so manipuliert, daß die Koeffizientenmatrix in ihrer Hauptdiagonalen den Wert 1 und unterhalb der Hauptdiagonalen nur Nullen enthält. Zwei Grundtypen von Matrixoperationen werden in der Gaußsehen Eliminationsmethode benutzt: skalare Multiplikation und Addition. Jede Gleichung kann mit einer Konstanten multipliziert werden, ohne das Ergebnis zu verändern. Dies ist äquivalent mit der Multiplikation einer Zeile der Koeffizientenmatrix und des zugehörigen Elementes im Konstantenvektor mit demselben Wert. Jede Gleichung kann auch durch die Summe zweier Gleichungen ersetzt werden.
Die folgenden Schritte werden die Benutzung der Gaußschen Ellmination anhand der folgenden Gleichungen erläutert:

  
        Koeffizienten-  Lösungs-
          Matrix A        Vektor b

        13   -8   -3        20
        -8   10   -1        -5
        -3   -1   11         0
Ziel der Elimination ist es, aus Ax = b eine äquivalentes System Cx = d mit C als obere Dreiecksmatix zu erzeugen:

Dieses System kann dann durch Rückwärtseinseten gelöst werden:

Rechnen wir das Beispiel einmal durch. Die erste Variable wird von allen außer der ersten Gleichung eliminiert. Ziel dieser Manipulation ist es, den Wert 1 als oberstes Element der ersten Spalte zu erzeugen. Die übrigen Positionen der Spalte werden 0. Dazu wird die gesamte erste Zeile durch das erste Element in der Zeile (das Pivot-Element) dividiert. Dies erzeugt den Wert 1 in der ersten Position der Diagonalen. Die erste Gleichung erhält dann folgendes Aussehen:

    [ 1  -0.61  -0.23] [1.5]
Die erste Unbekannte wird von der zweiten Zeile eliminiert, indem die neue erste Zeile mit dem ersten Element in der zweiten Zelle multipliziert und dann von der zweiten Zeile subtrahiert wird. Als neue zweite Zeile ergibt sich dann:
 Zeile 2:                 [ -8.00 10.00 -1.00 ]  [- 5]
 Minus Zeile 1 mal -8:    [ -8.00  4.88  1.84 ]  [ 12]
                         -----------------------------
 Ergibt:                  [  0.00  5.12  0.84 ]  [  7]
In ähnlicher Weise eliminiert man die erste Variable aus der dritten Gleichung. Die drei Gleichungen haben nun folgendes Aussehen:
   [ 1.00  -0.61  -0.23 ]  [1.5]
   [ 0      5.12   2.84 ]  [  7]
   [ 0      2.83  10.31 ]  [4.6]
Im nächsten Schritt wird der Wert 1 in der zweiten Position der zweiten Zeile (dem neuen Pivot-Element) erzeugt. Die zweite Zeile wird dazu durch das zweite Element dividiert. Die zweite Variable wird von der dritten Gleichung eliminiert, indem eine Null in der zweiten Position direkt unter dem Pivot-Element erzeugt wird. Die drei Gleichungen sehen dann so aus:
   [ 1.00  -0.61  -0.23 ]  [1.5]
   [ 0      1.00  -0.56 ]  [1.4]
   [ 0      0      8.7  ]  [8.7]
Der letzte Schritt dieser Phase besteht darin, den Wert 1 in der dritten Pivot-Position zu erhalten. Dies erreicht man durch Division der dritten Gleichung durch den Pivot-Wert. Insgesamt erhält man dann:
   [ 1.00  -0.61  -0.23 ]  [1.5]
   [ 0      1.00  -0.56 ]  [1.4]
   [ 0      0      1.00 ]  [1.0]
Das Ergebnis entspricht den drei Gleichungen:
    x - 0.6ly - 0.23z = 1.5
            y - 0.56z = 1.4
                    z = 1
Die dritte Gleichung kann direkt gelöst werden, da sie nur eine Unbekannte hat. Das Ergebnis lautet:
    z = 1
Die zweite Gleichung kann folgendermaßen umgeformt werden:
    y = 1.4 + 0.56z
Durch Einsetzung des Wertes von z ergibt sich für y der Wert 2. Die Einsetzung von y und z in die erste Gleichung liefert für x den Wert 3. Diese Phase der Berechnung Wird als "Rücksubstitution bezeichnet. Das Programm stellt sich dann so dar:

#include <stdio.h>

#define N 3                             /* Spalten/Zeilen der Matrix */
                                        /* = Anzahl der Gleichungen */
int main(void)
  { 
  int i, j, k;                          /* Schleifenzaehler */ 
  double f;                             /* Hilfsvariable */
  double a[N][N];                       /* Koeffizientenmatrix */
  double b[N];                          /* rechte Seite */
  double x[N];                          /* Loesung */

  /* Einlesen */
  for(i = 1; i <= N; i++)           
    { 
    for(j = 1; j <= N; j++) 
      scanf("%lg", &a[i-1][j-1]);
    scanf("%lg", &b[i-1]);
    }

  /* Elimination */
  for(i = 1; i <= (N-1); i++)                  
    { 
    for(k = i+1; k <= N; k++)
      { 
      f = a[k-1][i-1] / a[i-1][i-1];
      for(j = i+1; j <= N; j++) 
        a[k-1][j-1] -= f*a[i-1][j-1];
      b[k-1] -= f*b[i-1];
      }
    }

  /* Ruecksubstitution */
  for(i = N; i >= 1; i--)
    { 
    for(j = i+1; j <= N; j++) 
      b[i-1] -= a[i-1][j-1] * x[j-1];
    x[i-1] = b[i-1] / a[i-1][i-1];
    }

  /* Ausgabe */
  for(i = 1; i <= N; i++) 
    printf("x%d = %g\n", i, x[i-1]);

  return 0;
  }

Ein Problem ergibt sich, wenn die Pivot-Elemente relativ klein sind, weil dann - bedingt durch die begrenzte Rechengenauigkeit - sich die Rundungsfehler relativ stark auf das Endergebnis auswirken. Die Genauigkeit der Gaußschen Eliminationsmethode kann dadurch verbessert werden, daß man zwei Zeilen derart vertauscht, daß das Element mit dem größten absoluten Wert das Pivot-Element wird. Nehmen wir z. B. an, daß die vorhergehenden drei Gleichungen ursprünglich in einer anderen Reihenfolge geschrieben worden wären:

  
   [ -3   -1   11 ]  [  0 ]
   [ 13   -8   -3 ]  [ 20 ]
   [ -8   10   -1 ]  [ -5 ]
Die oberste Gleichung könnte dann durch -3 dividiert werden, um den Wert 1 in die Plvot-Position zu bringen. Das Ergebnis wird jedoch genauer, wenn wir zuerstst die erste und zweite Zeile vertauschen. Dies bringt den größeren Wert 13 in die Plvot-Position. Nach Elimination der ersten Variablen aus der zweiten und dritten Gleichung lautet das Ergebnis:
   [ 1 -0.6  -0.2 ]  [1.5]
   [ 0 -2.8  10.3 ]  [4.6]
   [ 0  5.1  -2.8 ]  [7.3]
Nun sollte man die zweite und dritte Gleichung vertauschen, um das größere Element 5.1 in die zweite Pivot-Position zu bringen. Es gibt einen weiteren Grund, warum Zeilen vertauscht werden müssen. Erscheint nämlich ein Null-Element (oder ein Wert nahe Null) in der Hauptdiagonalen, dann ist es nicht möglich, die Zeile durch dieses Pivot-Element zu dividieren ohne große Rundungsfehler zu erhalten. Der Austausch dieser Zeile mit einer darunterliegenden entfernt die Null aus der Pivot-Position.

Das Programm kann mit relativ wenig Aufwand erweitert werden:


#include <stdio.h>

#define N 3                             /* Spalten/Zeilen der Matrix */
                                        /* = Anzahl der Gleichungen */
int main(void)
  { 
  int i, j, k;                          /* Schleifenzaehler */ 
  int merk;                             /* Merker fuer Zeilentausch */
  double f;                             /* Hilfsvariable */
  double a[N][N];                       /* Koeffizientenmatrix */
  double b[N];                          /* rechte Seite */
  double x[N];                          /* Loesung */

  /* Einlesen */
  for(i = 1; i <= N; i++)
    { 
    for(j = 1; j <= N; j++) 
      scanf("%lg", &a[i-1][j-1]);
    scanf("%lg", &b[i-1]);
    }

  /* Elimination */
  for(i = 1; i <= (N-1); i++)
    { 
    merk = i;
    for(k = i+1; k <= N; k++)
      if (abs(a[k-1][i-1]) > abs(a[merk-1][i-1]))
        merk = k;
    if (merk != i) /* vertauschen */
      {
      for (j = i+1; j <= N; j++)
        {
        f = a[i-1][j-1]; 
        a[i-1][j-1] = a[merk-1][j-1];
        a[merk-1][j-1] = f;
        }
      f = b[i-1]; 
      b[i-1] = b[merk-1];
      b[merk-1] = f;
      }
    for(k = i+1; k <= N; k++)
      { 
      f = a[k-1][i-1] / a[i-1][i-1];
      for(j = i+1; j <= N; j++) 
        a[k-1][j-1] -= f*a[i-1][j-1];
      b[k-1] -= f*b[i-1];
      }
    }

  /* Ruecksubstitution */
  for(i = N; i >= 1; i--)
    { 
    for(j = i+1; j <= N; j++) 
      b[i-1] -= a[i-1][j-1] * x[j-1];
    x[i-1] = b[i-1] / a[i-1][i-1];
    }

  /* Ausgabe */
  for(i = 1; i <= N; i++) 
    printf("x%d = %g\n", i, x[i-1]);
 
 return 0;
 }

Um alle Fährnissen standzuhalten, sollte bei der Suche nach dem größten Pivot-Element auch gleich noch geprüft werden, ob die Matrix nicht singulär wird, d. h. ob es betragsmäßig größer als eine vorgegebene untere Schranke ist.

8.4 Statistische Maßzahlen

Beschreibende Statistik

Bei der Statistik handelt es sich um Verfahren, nach denen empirische Zahlen gewonnen, dargestellt, verarbeitet, analysiert und für Schlußfolgerungen, Prognosen und Entscheidungen verwendet werden. Mit Statistik lassen sich keine Beweise führen, nur Hypothesen bekräftigen. Mit der mathematischen Statistik analysiert man Massenerscheinungen. Dabei zeigt sich oft, daß die Massenerscheinungen gewisse Gesetzmäßigkeiten aufweisen, die sich für Einzelerscheinungen nicht formulieren lassen, da sie dort nur als zufällige Unregelmäßigkeit auftreten. Werden z. B. 100 Werkstücke einzeln vermessen, so streuen die einzelnen Werte zufällig und sind somit nicht vorhersagbar. Die mittleren Maße und die Streuung der Werte jedoch sind auch nach dem Auszählen einer zweiten Stichprobe nahezu identisch. Diese charakteristischen Werte erlauben somit eine Aussage über die Grundgesamtheit aller Werkstücke.
In der Wahrscheinlichkeitsrechnung wird der Mittelwert als Erwartungswert interpretiert. In der Bundesrepublik sterben jährlich 100 Personen aufgrund eines technischen Defekts an einem elektrischen Haushaltsgerät. Glaubhaft, da ein eng definiertes, singuläres Schadensereignis. Auf der Welt sterben jährlich über zwei Millionen Menschen an den Folgen ihres Nikotinkonsums. Dies wird nicht geglaubt, da es sich um ein Multikomponenten-Ereignis handelt von dem jeder eine Ausnahme kennt.

Tabellarische und graphische Darstellung

Üblicherweise werden die n Beobachtungsereignisse der Reihe nach aufgelistet (Urliste). Aus dieser Stichprobe vom Umfang n kann man Schlüsse auf die zugehörige Grundgesamtheit N ziehen. Wären gleichzeitig mehrere Merkmale gemessen worden, z. B. Masse und Größe, so hätte man eine Stichprobe erhalten, die aus n Zahlenpaaren besteht.

Häufigkeitsverteilung einer Gaußschen Normalverteilung.
links: Stabdiagramm, Häufigkeitspolygon, rechts: Balkendiagramm

Bei kleinen Stichproben hilft es schon, wenn man die Werte der Größe nach ordnet, um einen Überblick zu bekommen. Besser ist es, zahlenmäßig gleiche Werte zusammenzufassen und sie graphisch darzustellen. Dabei wird die Anzahl ai über dem Meßwert xi aufgetragen. Die Anzahl ai heißt die absolute Häufigkeit des betreffenden Wertes in der Stichprobe. Dividiert man die absolute Häufigkeit durch den Stichprobenumfang n, so erhält man die relative Häufigkeit. Die relative Häufigkeit ist somit immer eine Zahl zwischen 0 und 1. Die Auftragung kann als Punkt-, Stab- oder Balkendiagramm erfolgen. Eine direkte Verbindung der Punkte untereinander ergibt ein Häufigkeitspolygon. Diese Graphiken stellen Häufigkeitsverteilungen oder Histogramme der Stichprobe dar.

Die folgende Funktion druckt ein Histogramm für bis zu 25 Häufigkeiten, die im Array h gespeichert sind (int werte[25]). Dabei werden die Balken auf maximal 20 Zeilen normiert. Der erste Parameter der Funktion übergibt eine Überschrift, der zweite Parameter ist das oben erwähne Wertearray und der dritte Parameter gibt an, wieviele Balken auszugeben sind.

void make_histo(char *headline, int werte[],  int n)
  {
  int h[25];
  int i, j, max = 0;

  for (i = 0; i <= n; i++)          /* Maximum finden */
    if (werte[i] > max) max = werte[i];
  for (i = 0; i <= n; i++)          /* Normieren */
    h[i] = werte[i]*20/max;
  printf("\n%s\n",headline);
  printf("  |");
  for (i = 0; i <= n; i++)          /* oberste Zeile */
    if (h[i] >= 20) printf("%2d ",h[i]);
    else printf("   ");
  printf("\n  ");
  for(j = 19; j >= 1; j--)          /* y-Achse */
    {
    printf("|");
    for (i = 0; i <= n; i++)        /* x- Werte */
      if (h[i]>=j) printf(" * ");
      else printf("   ");
    printf("\n  ");
    }
  for (i = 0; i <= n; i++)          /* x-Achse zeichnen */
    printf("%s","--+");
  printf("\n  ");
  for (i = 0; i <= n; i++)          /* x-Achse beschriften */
    printf("%3d",i);
  printf("\n");
  }

Für die statistische Auswertung eines Feldes mit Urdaten müssen zuerst die Häufigkeiten ermittelt werden. Dazu dient die folgende Funktion. Die Häufigkeiten werden in einem Feld "hauf" gespeichert, dessen Komponenten den Datenwert und seine Häufigkeit speichern. Deshalb sind die Feldkomponenten ein Verbund:

struct Counter { double value; int count; };
Das Datenfeld muß aufsteigend sortiert vorliegen. Dazu wird die Bibliotheksfunktion qsort verwendet, die ihrerseits eine Vergleichsfunktion benötigt. Ein Aufrufbeispiel finden Sie weiter unten.
int dblvgl(const double *v1, const double *v2)
/* Vergleich zweier double-Werte (fuer Sortierung) */
  {
  if (*v1 > *v2) return(1);
  if (*v1 < *v2) return(-1);
  return (0);
  }

void frequencies(double data[], int n, struct Counter hauf[], int *toph)
/* Zaehlt die Haeufigkeiten der Werte in data     */
/* 'n' gibt die Anzahl der uebergebenen Werte an  */
/* Rueckgabe: hauf: (Werte und zugeh. Haeufigk.), */
/*    toph: letzter verwendeter Index von hauf    */
/* Seiteneffekt: Sortieren des Datenfeldes        */
/* struct Counter { double value; int count; };   */
  {
  int i, k;
  k = 0;
  qsort(data, n, sizeof(data[0]), dblvgl);
  hauf[0].count = 1;
  hauf[0].value = data[0];
  for (i = 1; i < n; i++)
    {
    if (data[i] == data[i-1])
      hauf[k].count++;
    else
      {
      k++;
      hauf[k].count = 1;
      hauf[k].value = data[i];
      }
    }
  *toph = k;
  }
Um die nun ermittelten Häfigkeiten auszugeben, kann man ein waagrecht liegendes Histogramm drucken. Dies leistet die folgende Funktion.
void printfrequencies(struct Counter hauf[], int n)
/* Ausgabe Histogramm der Haeufigkeiten in hauf  */
/* 'n' gibt die Anzahl der uebergebenen Werte an */
/* struct Counter { double value; int count; };  */
  {
  int i, k, max;
  max = 0;
  /* maximum der Haeufigkeiten ermitteln */
  for (i = 0; i <= n; i++)
    if (hauf[i].count > max) max = hauf[i].count;
  /* Ausgabe */
  for (i = 0; i <= n; i++)
    {
    printf("%12lf: ", hauf[i].value);
    for (k = 0; k < hauf[i].count*50/max; k++)
      putchar('#');
    printf(" (%5d)\n",hauf[i].count);
    }
  }

Mittelwert, Varianz, Standardabweichung, Standardfehler

Neben der Häufigkeitsfunktion kann man eine Grundgesamtheit oder eine Stichprobe auch durch Maßzahlen charakterisieren. Die beiden in der Praxis wichtigsten Maßzahlen sind der Mittelwert, der die durchschnittliche Größe der Grundgesamtheit N oder der Stichprobe n kennzeichnet, und eine Angabe über die Streuung der Werte. Im weiteren wird von der Annahme ausgegangen, daß die Meßwerte eine Normalverteilung nach Gauß ergeben. Eine genügend große Stichprobe wird vorausgesetzt. Der arithmetische Mittelwert ist definiert als:

µ = Mittelwert der Grundgesamtheit, = Mittelwert der Stichprobe

Die folgende Funktion berechnet den Mittelwert eines double-Arrays. Als Parameter werden dieses Array und die Anzahl der relevanten Elemente im Array übergeben (der Index läuft dnn von 0 bis n-1).

double mittel(double data[], int n)
/* Mittelwert des Arrays 'data' */
/* 'n' gibt die Anzahl der uebergebenen Werte an */
  {
  int i;
  double sum;

  sum = 0.0;
  for (i = 0; i < n; i++)
    sum += data[i];
  return(sum/(double)n);
  }

Dieser allein reicht jedoch nicht aus, um z. B. eine Stichprobe zu beschreiben, wie folgendes Beispiel zeigt:

Stichprobe 1: 1.5, 3.0, 3.5, 4.0 -> = 3
Stichprobe 2: 2.8, 2.9, 3.1, 3.2 -> = 3

Beide Stichproben haben zwar den Mittelwert = 3, unterscheiden sich aber voneinander, denn die Werte der ersten Stichprobe liegen viel weiter auseinander (und auch weiter vom Mittelwert entfernt) als die Werte der zweiten Stichprobe. Um diesen Unterschied zu erfassen, braucht man noch eine weitere Maßzahl, welche die Abweichung der Stichprobenwerte vom Mittelwert mißt. Man bildet die Quadrate der Einzelabweichungen (kleinste Gaußsche Fehlerquadrate, engl. least square) und summiert diese. Man erhält die Varianz oder Streuung (engl. variance). Sie berechnet sich zu

Die unterschiedliche Berechnung der Varianz für Grundgesamtheit und Stichprobe läßt sich aus der Wahrscheinlichkeitstheorie ableiten.

Die positive Quadratwurzel der Varianz heißt Standardabweichung (engl. standard deviation, S.D.). Sie gehört neben der Varianz zu den gebräuchlichsten Maßen zur Kennzeichnung der Variabilität einer Verteilung.


Für die obigen Beispiele ergeben sich somit:

Stichprobe 1: = 3, s2 = 1.17, s = 1,08
Stichprobe 2: = 3, s2 = 0,03, s = 0,18

Die Streuung der zweiten Stichprobe ist also wesentlich kleiner. Durch Angabe von Mittelwert und Varianz bzw. Standardabweichung sind Stichproben meist ausreichend beschrieben.
Bei einer unimodalen, symmetrischen und dazu glockenförmigen Verteilung liegen zwei Drittel aller Fälle in einem Bereich von einer Standardabweichung entfernt vom Mittelwert, was etwa 68 Prozent aller Fälle entspricht. In einer Entfernung von zwei Standardabweichungen liegen etwa 95 Prozent aller Fälle. Dieser Zusammenhang ist auch ein Grund dafür, daß Ausreißer in einer Verteilung, also Werte, die mehr als zwei Standardabweichungen vom Mittelwert entfernt liegen, oft durch diese Grenzwerte ersetzt werden.

Die Berechnung der Standardabweichung (bzw. Varianz) nach den obigen Definitionsformeln ist jedoch numerisch ungünstig. Durch die Differenzbildung (xi - ) entstehen sehr kleine Differenzen, die dann auch noch quadriert werden müssen. Durch Rundungsfehler entstehen Genauigkeitsverluste. Es gibt deshalb für die Praxis güstigere Berechnungsformeln. Bei ihnen werden die Differenzbildungen vermieden. Für die Standardabweichung einer Stichprobe ergibt sich somit

Die Funktion varianz hat die gleichen Parameter, wie die Mittelwert-Funktion. Es werden in der Schleife gleichzeitig Summe und Quadratsumme berechnet und anschließend die Varianz.

double varianz(double data[], int n)
/* Varianz des Arrays 'data' */
/* 'n' gibt die Anzahl der uebergebenen Werte an */
  {
  int i;
  double sum, sumsq;

  sum = 0.0;
  sumsq = 0.0;
  for (i = 0; i < n; i++)
    {
    sum += data[i];               /* Summe */
    sumsq += (data[i] * data[i]); /* Summer der Quadrate */
    }
  return((sumsq - sum*sum/(double)n)/(double)(n - 1));
  }

Bei der Bestimmung von Stichproben möchte man auch gerne wissen, mit welcher Wahrscheinlichkeit von den bei einer Stichprobe gefundenen Größen auf die Grundgesamtheit geschlossen werden kann. Die für eine Stichprobe ermittelten Werte (Mittelwert, Varianz, Standardabweichung) sind also nur Schätzwerte für die Grundgesamtheit. Man möchte z. B. wissen, wie weit der Stichprobenmittelwert vom Mittelwert der Grundgesamtheit µ abweicht. Diese Abweichung bezeichnet man als Standardfehler (= Fehler des Mittelwertes = Standardabweichung des Mittelwertes; engl. standard error of the mean, S.E.). Wenn keine extremen Abweichungen der Stichprobenwerte xi von der Normalverteilung um den Stichprobenmittelwert vorliegen, darf man annehmen, sich daß auch die Mittelwerte annähernd gleich großer Stichproben gleichmäßig um den Grundgesamtheitsmittelwert µ verteilen. Die unbekannte wirkliche Abweichung s kann durch den Standardfehler s abgeschätzt werden. Er berechnet sich aus der Standardabweichung s.

Das zusätzliche "n" in der Formel für den Standardfehler s (im Gegensatz zu Varianz und Standardabweichung) liefert eine Angabe über die Größe der Stichprobe. Je größer eine Stichprobe ist, desto genauer wird die Schätzung für die Grundgesamtheit. Der Standardfehler verkleinert sich dabei (n steht im Nenner), geht somit gegen µ.

Die C-Funktion dazu ist trivial - sie berechnet lediglich die Quadratwurzel der oben gezeigten Varianz-Funktion:

double streuung(double data[], int n)
/* Streuung des Arrays 'data' */
/* 'n' gibt die Anzahl der uebergebenen Werte an */
  {
  return(sqrt(varianz(data,n)));
  }

Der Standardfehler wird oft zusammen mit dem Stichprobenmittelwert zur Charakterisierung einer Stichprobe bezüglich der Grundgesamtheit angegeben:

± s (z. B. 25 cm ± 0,1 cm)

Minimum, Maximum, Median, Modalwert

Minimum ist der kleinste, Maximum der größte im Array vorkommende Wert.
Der Zentralwert oder Medianwert stellt ebenfalls einen charakteristischen Wert einer Häufigkeitsverteilung dar. Er wird für bestimmte statistische Verfahren benötigt. Er teilt die Häufigkeitsverteilung flächengleich auf, so daß sich links und rechts vom Zentralwert genau gleich viele Ereignisse befinden.
Der häufigste Wert oder Modalwert stellt, wie sein Name schon sagt, den Wert mit der größten Häufigkeit dar. Er ist also der Gipfel ("Peak") in einer Häufigkeitsverteilung. In einer Normalverteilung sind infolge der Symmetrie der Verteilung arithmetischer Mittelwert, Medianwert und Modalwert identisch. Er kann mit Hilfe der weiter oben vorgestellten Funktion frequencies ermittelt werden.

Die Funktion zum Berechnen der anderen Werte muß das Datenfeld sortieren (speziell für den Median). Dazu wird die Bibliotheksfunktion qsort verwendet, die ihrerseits eine Vergleichsfunktion benötigt. Die statistischen Werte gibt die Funktion als Referenzparameter zurück. Ein Aufrufbeispiel finden Sie weiter unten.

int dblvgl(const double *v1, const double *v2)
/* Vergleich zweier double-Werte (fuer Sortierung) */
  {
  if (*v1 > *v2) return(1);
  if (*v1 < *v2) return(-1);
  return (0);
  }

void minimax(double data[], int n,
              double *min, double *max, double *median)
/* Minimum, Maximum und Median des Arrays 'data'  */
/* 'n' gibt die Anzahl der uebergebenen Werte an  */
/* Rueckgabe: min, max, median                    */
/* (data ist anschliessend sortiert)              */
  {
  qsort(data, n, sizeof(data[0]), dblvgl);
  *min = data[0];
  *max = data[n-1];
  if ((n % 2) == 0) /* n gerade */
    *median = (data[(n-1)/2] + data[(n-1)/2+1])/2;
  else
    *median = data[(n-1)/2+1];
  }

Aufrufbeispiele

Das folgende Hauptprogramm zeigt, wie man die oben aufgeführten Funktionen aufruft. Der Einfachheit halber wurde das Datenfeld statisch vorbelegt, bei einer realen Anwendung wird man die Daten sicher von einer Datei einlesen.
int main(void)
  {
  double Data[MAXDATA] = {1.5, 2.0, 1.5, 3.0, 2.5, 1.5, 2.0, 2.5, 3.5, 3.0};
  struct Counter Hauf[MAXDATA];
  double min, max, median;
  int toph;

  printf("Mittel: %lf Varianz: %lf Streuung: %lf\n",
          mittel(Data,10), varianz(Data,10), streuung(Data,10));

  minimax(Data,10, &min, &max, &median);
  printf("Minimum: %lf Maximum: %lf Median: %lf Spanne: %lf\n",
          min, max, median,max-min);

  frequencies(Data,10,Hauf,&toph);
  printfrequencies(Hauf,toph);
  return(0);
  }
Die Ausgabe des Programms sieht folgendermaßen aus:
Mittel: 2.300000 Varianz: 0.511111 Streuung: 0.714920
Minimum: 1.500000 Maximum: 3.500000 Median: 2.250000 Spanne: 2.000000
    1.500000: ################################################## (    3)
    2.000000: ################################# (    2)
    2.500000: ################################# (    2)
    3.000000: ################################# (    2)
    3.500000: ################ (    1)

Lineare Regression

Bei der Erfassung von Meßgrößen besteht oft der Wunsch, Werte zwischen den einzelnen Stützpunkten zu ermitteln. Hier helfen Interpolation und Regression.

Bei der linearen Interpolation wird die Näherung eines Funktionswerts f(x) mit x1 < x < x2 aus den bekannten Funktionswerten f(x1) und f(x2) gewonnen.

Sind von einer Funktion nur die Werte an den Stützstellen x1, x2, ..., xn bekannt, so läßt sich durch Interpolation eine stückweise lineare Funktion definieren.

Bei der linearen Regression wird eine Gerade ax + b gesucht. Diese Gerade wird in einer bestmöglichen Näherung in eine Auftragung von n Datenpunkten (x1, f(x1)), (x2, f(x2)), ... ,(xn, f(xn)) gelegt.

Die bestmögliche Anpassung ist gegeben, wenn die Summe der Abweichungsquadrate

minimal wird. Die Werte von a und b errechnen sich aus den Gleichungen

Im folgenden Programm wird a in die Formel für b eingesetzt - daher sieht es etwas anders aus. Zudem werden nicht nur die Parameter a und b errechnet, sondern auch zwei statistische Maßzahlen, welche es erlauben, die "Güte" der Regressionsgeraden zu beurteilen. es sind dies die mittlere quadratische Abweichung der Geraden von allen Stützpunkten und die Standardabweichung für a und b.

Im Testprogramm wurden die Funktionswerte von y = 2a + 2 leicht verändert.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int linreg (double x[], double y[], int anz,
            double *a, double *b,
            double *r, double *sa, double *sb)
/* Lineare Regression fuer 'anz' Stuetzpunkte (x[i], y[i]):
*   Rueckgabeparameter (alles Referentparameter):
*   a, b: Koeffizienten der Regressionsgerade y = ax + b
*   r: mittlere quadratische Abweichung
*   sa, sb: Standardabweichungen fuer a und b
*   Die Funktion liefert im Erfolgsfall 0, wenn die
*   Koeffizienten nicht berechnet werden koennen, 1.
*   Aufruf: linreg(x,y,anzahl,&a,&b,&r,&sa,&sb);
*/
  {
  double summexy = 0.0, summex = 0.0;
  double summey = 0.0, summex2 = 0.0;
  double sum = 0.0;
  double divisor = 0.0;
  double n = (double) anz;
  int i;

  for(i = 0; i < anz; i++)
    {
    summex += x[i];
    summey += y[i];
    summexy += (x[i] * y[i]);
    summex2 += (x[i] * x[i]);
    }
  divisor = (n*summex2 - summex*summex);

  if (divisor < 1.0E-30) return (1); /* Division durch 0! */

  /* a und b fuer y = ax + b berechnen */
  *a = (n*summexy - summex*summey)/divisor;
  *b = (summex2*summey - summex*summexy)/divisor;

  /* mittlere quadratische Abweichung */
  for(i = 0; i < anz; i++)
    sum += pow(*a*x[i] + *b - y[i],2);
  *r = sqrt(sum/(n - 2.0));

  /* Standardabweichung von a und b */
  *sa = *r*sqrt(n/divisor);
  *sb = *r*sqrt(summex2/divisor);

  return (0);
  }

int main(void)
  {
  double x[] = {1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0};
  double y[] = {4.1,6.1,7.9,9.9,12.1,13.8,16.0,18.2,19.9,22.1};
  int anz = 10;
  double a, b, r, sa, sb;

  if(linreg(x,y,anz,&a,&b,&r,&sa,&sb) != 0)
    printf("Nicht berechenbar!\n");
  else
    {
    printf("Regressionsgerade: y = %lf * x + %lf\n",a,b);
    printf("Mitt. quad. Abweichung: %lf\n",r);
    printf("Standardabweichung a:   %lf\n",sa);
    printf("Standardabweichung b:   %lf\n",sb);
    }

  return 0;
  }

8.5 Suchen und Sortieren

Das Suchen in Datenbeständen ist ein häufig vorkommendes Programmierproblem. Eng damit zusammen hängt das Sortieren, denn normalerweise sortiert man ja Datensätze, um ein späteres Suchen zu erleichtern - entweder dem Programm oder dem Benutzer. In der praktischen Anw}ung werden die unterschiedlichsten Datensätze sortiert. Das können einfach Strings sein, aber auch komplexe Strukturen. In diesem Fall muß man sich natürlich darüber im Klaren sein, welches Feld als Such- und Sortierschlüssel dienen soll.

In den folgenden Beispielen soll der jeweilige Algorithmus verdeutlicht werden. Daher werden nur Zahlen sortiert; eine Anpassung an andere Situationen ist leicht. In den Beispielen werden folg}e globale Deklarationen, soweit nicht anders angegeben, vorausgesetzt:

#define TableSize 20;
int Table [TableSize];

Suchen in Tabellen

Dies ist der Standardfall. Wie in der Einleitung beschrieben, handelt es sich bei den Datensätzen, die durchsucht werden sollen, um Zahlen. Ein Array könnte beispielsweise so aussehen:
  12 07 56 32 44 44 18
Wenn man jetzt nach dem Schlüssel 56 sucht, muß die Suchfunktion als Index 2 zurückgeben. Suchet man nach 44, könnte sie entweder 4 oder 5 zurückgeben. Manchmal ist es wichtig, das erste Vorkommen eines Schlüssel zu finden (also 4). Außerdem kann es vorkommen, daß ein Schlüssel gar nicht gefunden wird. Die vorgestellten Funktionen signalisieren dies, indem sie den Index -1 zurückgeben.

Lineare Suche

Wenn man nichts über die Anordnung der Komponenten im Array weiß, bleibt einem nichts anderes übrig, als sie beginnend bei der ersten Komponente linear zu durchsuchen, bis man entweder die gesuchte Komponente gefunden hat, oder bis das Ende des Arrays erreicht wurde. Im statistischen Mittel werden bei N Tabelleineinträgen N/2 Suchschritte benötigt, im günstigsten Fall nur einer und im schlechtsten Fall N Schritte.
Um nicht jedesmal prüfen zu müssen, ob das Ende des Arrays schon erreicht ist, wenden wir einen kleinen Trick an: Am Ende des Arrays fügen wir noch ein Element an, das genau dem gesuchten Wert entspricht - auf diese Weise wird dann jedesmal ein Wert gefunden. Natürlich muß anschließend geprüft werden, ob der gefundene Wert nun ein "echter" Treffer oder die eigene Endemarke war. Diese Endemarke wird "Sentinel" genannt. Die Konstante Tablesize muß entsprechend großzügig gewählt werden.
Die Funktion LinSearch hat als Parameter den Suchschlüssel und gibt den gefundenen Index zurück:
int LinSearch(int Key, int Table[])
  {
  int Index;
  Table[TableSize] := Key;
  Index := 0;
  while (Table[Index] != Key)
    Index++;
  if (Index = TableSize)
    Index := -1;
  return(Index);
  }
Wie man sieht, wird im ersten Schritt der Sentinel gesetzt, dann wird der Index auf 0 initialisiert und dann so lange erhöht, bis der Key gefunden wurde. Zum Schluß wird noch geprüft, ob der Index außerhalb des gültigen Bereichs liegt. In diesem Fall wird der Index auf -1 korrigiert, denn das ist der Wert für "nicht gefunden". Daß der Algorithmus stets das erste Vorkommen des Keys findet, ist offensichtlich.

Binäre Suche

Um die Suche zu beschleunigen, müssen die Elemente in der Tabelle sortiert vorliegen. Dies kann man entweder durch eines der später beschriebenen Sortierverfahren erreichen, oder indem man neue Elemente gleich an der richtigen Stelle einfügt. Beides benötigt zusätzlichen Aufwand, spart aber Zeit beim Suchen. Wie nutzt man nun die Ordnung in der Tabelle aus?

Man sucht das mittlere Element der Tabelle und prüft, ob es größer oder kleiner als dder Key ist. Ist es größer oder gleich, braucht man nur noch in der unteren Hälfte der Tabelle zu suchen, ist es kleiner, sucht man nur noch in der oberen Hälfte. Irgendwann ist die Größe des Suchintervalls auf 1 geschrumpft, und dann hat man das gesuchte Element gefunden, oder es ist nicht vorhanden. Die Zahl der Suchschritte reduziert sich bei N Tabelleneinträgen auf ln(N) (ln: Logarithmus zur Basis 2).

Der folg}e Algorithmus benutzt die Variablen L(inks) und R(echts), um den Suchbereich zu definieren, sowie Middle, um die Mitte zu markieren. Soll oberhalb der Mitte weitergesucht werden, wird L zu Middle + 1, wird im unteren Teil weitergesucht, so ergibt sich R = Middle.

int BinSearch (int Key, int Table[])
  {
  int L, R, Middle;

  L := 1;
  R := TableSize + 1;
  while (L < R)
    {
    Middle := (L + R) / 2;
    if (Table[Middle] < Key) L := Middle + 1;
    else                        R := Middle;
    }
  if (Table[R] == Key) return(R);
  else                 return(-1);
  }
Wenn die Funktion das gesuchte Element früher als erwartet findet (z. B. wenn es genau in der Mitte liegt), könnte sie eigentlich abbrechen. Es ist dann nicht mehr garantiert, daß man das erste Vorkommen von Key findet.

Sortieren von Tabellen

Das Sortieren ist eines der wichtigsten Gebiete der Datenverarbeitung. Etwa 25% aller Rechenzeit im kommerziellen Bereich wird auf das Sortieren von Daten verwendent. An Beispielen zum Sortieren mangelt es nicht: Die Problemstellung: Gegeben ist ein Array mit Komponenten, die nach ihrem Schlüssel sortiert werden können, über deren momentane Anordnung jedoch nichts bekannt ist (das heißt auch, daß sie theoretisch schon sortiert sein oder in der umgekehrten Reihenfolge vorliegen könnten). Der Sortieralgorithmus soll die Elemente in die richtige Reihenfolge bringen.

Definition:

"Unter Sortieren versteht man allgemein den Prozess des Anordnens einer gegebenen Menge von Objekten in einer bestimmten Ordnung."

Das Sortieren ist ebenfalls einer der Grundalgorithmen in der Informatik insbesondere für die effiziente Speicherung von Informationen hinsichtlich der Auswertung bzw. Suche. Bei den Sortierverfahren unterscheidet man die

Bubblesort

Bubblesort ist einer der einfachsten Sortieralgorithmen. Im ersten Durchgang wird das Array vom Ende bis zum Anfang bearbeitet und bei jedem Schritt die aktuelle Komponente mit der nächsten verglichen. Ist die untere Komponente kleiner als die obere, werden die beiden vertauscht. Die größere Komponente behält also ihren Platz und die jeweils kleinere wandert weiter nach oben.
Im nächsten Durchlauf wird dann die zweitkleinste Komponente gesucht und nach oben durchgereicht. Logischerweise muß dieser Durchlauf nicht ganz bis zum Anfang gehen, sondern nur bis Index 1. der dritte Durchlauf läuft nur noch bis Index 2, usw. - bis das Verfahren abgeschlossen ist. Der Name "Bubblesort" kommt daher, daß die kleineren Komponente aufsteigen wie Blasen in einer Flüssigkeit.
void Bubblesort (int Table[])
  {
  int x;
  int Run, Index;
  for (Run = 1;  Run < TableSize; Run++)
    {
    for (Index = TableSize; Index >= Run; Index--)
      {
	  if (Table[Index] < Table[Index - 1])
	    {
	    x := Table[Index];
	    Table[Index] := Table[Index - 1];
	    Table[Index - 1] := x;
	    }
	  }
	}
  }
Deutlich zu erkennen ist der Vertauschungsvorgang, bei dem die "untere" Komponente zunächst in der Variablen x zwischengespeichert wird, dann den Wert der "oberen" zugewiesen bekommt und anschließend x im "oberen" Index gespeichert wird.

Bubblesort genießt keinen besonders guten Ruf, weil es sehr langsam ist. Trotzdem ist es häufig anzutreffen, nicht zuletzt wegen seines hohen Bekanntheitsgrades.

Sortieren durch Auswählen

Selectionsort ist ebenfalls ein sehr einfacher Algorithmus. Das Prinzip dahinter besteht darin, daß das Array von vorn nach hinten durchlaufen wird, und für jeden Platz die passende Komponente herausgesucht wird.

Man beginnt mit Table[0] und durchläft dann das Array.Dabei merkt sich die Funktion das kleinste Element. Dieses vertauscht sie dann mit der ersten Komponente, so daß nun die kleinste Komponente ganz vorne steht. Im nächsten Durchgang beginnt man bei Table[1] und durchsucht wieder das Array nach der kleinsten Komponente, wobei natürlich Table[0] unberücksichtigt bleibt. Im dritten Durchgang bleiben dann die ersten beiden Tabellenelemente unberührt usw.

void SelectionSort (int Table[])
  {
  int Komponente, Smallest;
  int Index, Smallidx;

  for (Komponente = 0; Komponente < TableSize; Komponente++)
    {
    Smallidx := Komponente;
    Smallest := Table[Smallidx];
    for (Index = Komponente + 1; Index <= TableSize; Index++)
      {
	  if (Table[Index] < Smallest)
	    {
	    Smallest := Table[Index];
	    Smallidx := Index;
	    }
      }
    if (Smallidx != Komponente)
      {
	  Table[Smallidx] := Table[Komponente];
	  Table[Komponente] := Smallest;
      }
    }
  }
In der Variablen Smallest merkt sich der Algorithmus den Wert die bislang kleinste Komponente, in Smallidx ihre Position. Beide werden zunächst auf die Komponente initialisiert, deren Position besetzt werden soll. Dann wird das übrige Array durchsucht, und beim Auftauchen einer kleineren Komponente entsprechend aktualisiert. Die Vertauschungsvorgang wird nur ausgeführt, wenn tatsächlich eine neue Position gefunden wurde. Selectionsort ist schneller als Bubblesort (ca. Faktor 2).

Sortieren durch Einfügen

Es wird angenommen, daß ein Teil am Anfang des Arrays schon sortiert ist (zu Beginn ist dieser Teil natürlich 0 Komponenten groß!). Nun wird die erste Komponente aus dem unsortierten Teil genommen und an der richtigen Stelle in den sortierten Teil eingefügt. Der sortierte Teil wächst dabei natürlich um eine Komponente, bleibt aber sortiert, wohingegen der unsortierte Teil um eine Komponente schrumpft.

Der Algorithmus durchläft die Arraykomponenten von Anfang bis Ende. Für jede Komponente geschieht nun folgendes: Von seiner Position aus bewegt er sich im sortierten Teil in Richtung Tabellenanfang, solange die Komponenten noch größer oder gleich der in Frage stehenden Komponente sind.

Dabei wird jede Komponente, die "überquert" wird, nach hinten verschoben. So entsteht an der jeweils aktuellen Position eine freie Array-Komponente. Diese "Lücke" wird dann an der richtigen Position mit dem einzufügenden Wert gefüllt. Auf diese Weise verbindet der Algorithmus die Suche nach der richtigen Position mit dem Verschieben der darüberliegenden Komponenten.

void InsertionSort (int Table[])
  {
   int x;
   int Komponente, Index;

   for (Komponente = 1; Komponente <= TableSize; Komponente++)
     {
     x := Table[Komponente];
     Index := Komponente;
     while ((Index > 0) && (Table[Index - 1] >= x))
       {
	   Table[Index] := Table[Index - 1];
	   Index--;
       }
     Table[Index] := x;
     }
  }
Wie man sieht, wird die aktuelle Komponente in x gespeichert. Dann beginnt das Verschieben, bis entweder eine Komponente gefunden wird, die kleiner als x ist, oder bis man bei Index 0 angelangt ist. Im letzteren Fall hat man offenbar keine kleinere Komponente im sortierten Teil und plaziert die Komponente an Position 0.

Shellsort

Shellsort ist ein Kompromiß aus Einfachheit und Geschwindigkeit. Das Array wird zunächst in mehrere Gruppen aufgeteilt, zwischen deren Mitgliedern der gleiche Abstand besteht. Angenommen, man verwendet den Abstand 3, dann gehören die Komponenten 1, 4, 7, ... in eine Gruppe, genauso 2, 5, 8, ..., 3, 6, 9, ... usw. Diese Gruppen werden nun einzeln sortiert, dann wird der Abstand verringert und die Vorgehensweise wiederholt. Das macht man so lange, bis der Abstand 1 ist, so daß im letzten Schritt gar keine Unterteilung mehr stattfindet.

Zum Sortieren der Gruppen wird ein Bubblesort-ähnlicher Algorithmus verwendet. Für jeden Schritt gibt die Variable Gap den Abstand zwischen den Komponenten an. Die Variable Index läuft dann von Gap + 1 bis zum Ende der Tabelle durch. Für jeden Wert von Index wird ein Sortierlauf gestartet, mit Index als oberer Grenze. Welche Gruppe dabei sortiert wird, hängt also von Index ab. Die Variable j wird auf die nächstkleinere Komponente der Gruppe initialisiert (also Index - Gap), dann wird es mit der nächsthöheren verglichen und gegebenenfalls vertauscht. Dann geht j wieder einen Schritt nach unten (Schrittweite Gap), usw., bis j kleiner 0 ist.

Wenn Index auf die n-te Komponente einer Gruppe verweist, sind alle Komponenten (dieser Gruppe) unterhalb von Index sortiert. Ist Index bis zum Ende des Arrays durchlaufen, sind auch alle Gruppen sortiert.

void ShellSort (int Table[])
  {
  int x;
  int Gap, Index, j;
  Gap := TableSize / 2;
  while (Gap > 0) do
    {
    for (Index = Gap + 1;  Index <= TableSize; Index++)
      {
	  j := Index - Gap;
	  while (j > 0)
	    {
	    if (Table[j] <= Table[j + Gap])
	      j := 0;
	    else
	      {
	      x := Table[j];
	      Table[j] := Table[j + Gap];
	      Table[j + Gap] := x;
	      }
	    j = J - Gap;
	    }
      }
    Gap := Gap / 2;
    }
  }
Shellsort zählt zu den schnelleren Algorithmen. Leider kommt es mit sehr großen Arrays überhaupt nicht zurecht.

Quicksort

Quicksort ist in den meisten Fällen der schnellste Algorithmus. Man greift sich eine beliebige Komponente des Arrays heraus - beispielsweise die mittlere - und teilt das Array in zwei Gruppen: Eine mit den Komponenten, die größer sind als die herausgegriffene, und eine mit den kleineren (oder gleichen). Diese beiden Hälften übergibt man wieder an Quicksort. Es handelt sich also um eine rekursive Funktion. Irgendwann sind die Arrays nur noch eine Komponente groß und damit sortiert. Um nicht bei jedem Aufruf immer Arrays erzeugen zu müssen, arbeitet Quicksort mit linker und rechter Grenze. Dafür müssen dann natürlich alle Komponenten, die größer sind als die herausgegriffene, in den unteren Teil verschoben werden, die anderen in den oberen Teil. Darin besteht die eigentliche Arbeit von Quicksort:
void QSort (int Links, int Rechts, int Table[])
  {
  int i, j;
  int x, w;

  i := Links;
  j := Rechts;
  x := Table[(Links + Rechts) / 2];
  do
    {
    while (Table[i] < x) i++;
    while (Table[j] > x) j--;
    if (i <= j)
      { /* Element vertauschen */
      w := Table[i];
      Table[i] := Table[j];
      Table[j] := w;
      i++; j--;
      }
    }
  while (i <= j);
  if (Links < j) QSort (Links, j, Table);
  if (Rechts > i) QSort (i,Rechts, Table);
  }

Quicksort ist, wie eingangs gesagt, in der Regel das schnellste Suchverfahren. Im schlimmsten Fall jedoch, wenn das Array bereits sortiert ist, fällt Quicksort leider auf das Niveau von Bubblesort herab.

Praktischer Einsatz von Sortierverfahren

In den vorangegangenen Abschnitten befanden sich die Algorithmen immer in einer sehr "sterilen" Umgebung, um sie von allem Beiwerk, das nicht unmittelbar zum Algorithmus gehört, zu befreien. In der Praxis hat man es mit unterschiedlichsten Bedingungen zu tun: Mal möchte man Strings sortieren, mal Zahlen, mal eine komplexe Struktur. Auch wünscht man sich manchmal, die Sortierreihenfolge (auf- oder absteigend) angeben zu können. Das Sortierverfahren muß zudem unbekannte Datentypen vergleichen können. Es muß also eine Funktion existieren, die für zwei Elementen des Arrays festlegt, welches von beiden größer ist.

Erweitern wir Quicksort zuerst auf das Sortieren von Strings. Da die Eingabestrings unterschiedlich lang sind, wird durch Speicherung von Strings fester Länge sehr viel Speicherplatz verschwendet. Für 1000 Zeichenketten mit maximal 150 Zeichen Länge müßte man definieren:

     char feld[1000][150].
Das Feld würde 1000*150 = 150'000 Bytes belegen ­ unabhängig von der wirklichen Länge der eingelesenen Zeilen. Daher sollte man für die Speicherung und Sortierung ein Feld von Zeigern auf Strings verwenden und den Platz für die aktuellen Zeile jeweils ihrer Länge entsprechend mit malloc reservieren. Das sieht dann etwa, so aus:
#define MAX 1000                  /* Maximalzahl Feldelemente */

...

char *feld[MAX];                  /* Feld mit String-Zeigern */
char *ptr;                        /* Zeiger zum Prüfen auf EOF */
char puffer[151];                 /* Puffer für akt. String */

    ...
    ptr = gets(puffer);                /* String einlesen */
    if (ptr != NULL)                   /* EOF,wenn (ptr rr NULL) */
      {                                /* Platz reservieren */
      feld[i] = (char *) malloc(strlen(puffer) + 1)
     /* Platz für den String einschl. des Zeichens '\0' am Ende */
      strcpy(feld[i],puffer);          /* String in feld kopieren */
      }
    ...
Auch bei Sortieren ist das Zeigerfeld günstiger, denn beim Vertauschen müssen nur Zeiger und nicht die ganzen Strings bewegt werden.

Diesmal wurde nicht nur Quicksort definiert, sondern auch das ganze Tetsprogramm:

#include <stdio.h>
#include <string.h>

#define MAX 1000                       /* Maximalzahl Feldelemente */
#define TRUE 1                         /* Wahrheitswerte */
#define FALSE 0

/* globale Variable */
/* ---------------- */

char *string_feld[MAX];                /* Feld mit String-Zeigern */
int count;                             /* Anzahl der eingeg. Strings */
int aufsteigend;                       /* aufsteigend/absteigend */

/* Funktions-Prototypen */
/* -------------------- */

int  einlesen(char *feld[]);           /* Eingabefunktion */
void ausgabe(int anzahl,char *feld[]); /* Ausgabefunktion */
void quicksort(char *feld[],int auf, int links, int rechts);
				       /* Quicksort-Routine */


/* Hauptprogramm */
/* ------------- */
main(int argc,char *argv[])
  {
  aufsteigend = TRUE;                  /* Voreinstellung */
  if (argc == 2)                       /* Argument pruefen */
    aufsteigend = (strcmp(argv[1],"auf") == 0);

  count = einlesen(string_feld);
  quicksort(string_feld,aufsteigend,0,count-1);
  ausgabe(count,string_feld);
  }


/* Funktions-Definitionen */
/* ---------------------- */

int einlesen(char *feld[])
  /* Liest Strings auf die Variable feld ein, liefert Anzahl zurueck */
  {
  int i;	                           /* Zaehler fuer Strings */
  char *ptr;                           /* Zeiger zum Pruefen auf EOF */
  char puffer[151];                    /* Puffer fuer akt. String */
  i = 0;
  do
    {
    ptr = fgets(puffer,150,stdin);     /* String einlesen */
    if (ptr != NULL)                   /* EOF == (ptr == NULL) */
      {                                /* Platz reservieren */
      feld[i] = (char *) malloc(strlen(puffer) + 1);
                                       /* einschl. '\0' am Ende */
      strcpy(feld[i],puffer);          /* String in feld kopieren */
      i++;                             /* Zaehler erhoehen */
      }
    }
  while (ptr != NULL);                 /* lesen bis EOF */
  return(i);
  }

void ausgabe(int anzahl,char *feld[])
  /* Ausgabe der Strings in feld, der Parameter gbt die Anzahl an */
  {
  int i;
  puts("\n");                          /* Leerzeile */
  for (i=0; i<anzahl; i++)
    puts(feld[i]);                     /* haengt \n automatisch an */
  }


void quicksort(char *feld[],int auf, int links, int rechts)
  /* Quicksort-Routine: feld wird im Bereich [lins,rechts] sortiert */
  {
  int i, j;  			               /* Hilfsvariable */
  char *x, *y;                         /* Hilfszeiger fuer Tausch */
  i = links; j = rechts;
  x = feld[(i + j)/2];                 /* mittleres Element */
  do
    {                                  /* partitionieren */
    if(auf)                            /* aufsteigend sortieren */
      {
      while(strcmp(feld[i],x) < 0 && i < rechts) i++;
      while(strcmp(feld[j],x) > 0 && j > links) j--;
      }
    else                               /* absteigend sortieren */
      {
      while(strcmp(feld[i],x) > 0 && i < rechts) i++;
      while(strcmp(feld[j],x) < 0 && j > links) j--;
      }
    if (i <= j)
      {                                /* Zeiger-Tausch! */
      y = feld[i];                     /* Die Strings bleiben an der */
      feld[i] = feld[j];               /* urspruenglichen Position */
      feld[j] = y;
      i++; j--;
      }
    }
  while (i <= j);
  if (links < j) quicksort(feld,auf,links,j);
  if (rechts > i) quicksort(feld,auf,i,rechts);
  }

Suchen mit bsearch

Die Bibliotheksfunktion bsearch() führt eine binäre Suche in einem Datenarray durch, wobei sie nach einem Array-Element Ausschau hält, das mit einem gesuchten Wert (dem Schlüssel oder "key") übereinstimmt. Um bsearch() anwenden zu können, muß das Array in aufsteigender Reihenfolge sortiert sein. Außerdem muß das Programm die Vergleichsfunktion bereitstellen, die bsearch() benötigt, um festzustellen, ob ein Datenelement größer, kleiner oder gleich einem anderen Element ist. Der Prototyp von bsearch() steht in stdlib.h und lautet:
void *bsearch(const void *key, const void *base, size_t num, size_t size,
     int (*cmp)(void *elem1, void *elem2));
Dieser Prototyp ist ziemlich komplex. Deshalb sollten Sie ihn sorgfältig studieren. Das Argument key ist ein Zeiger auf das gesuchte Datenelement und base ein Zeiger auf das erste Element in dem zu durchsuchenden Array. Beide werden mit dem Typ void deklariert, so daß sie auf irgendein beliebiges C-Datenobjekt zeigen können.

Das Argument num ist die Anzahl der Arraykomponenten und size die Größe einer Komponente in Byte. Üblicherweise wird der sizeof()-Operator verwendet, um die Werte für num und size anzugeben.

cmp ist ein Zeiger auf die Vergleichsfunktion. Dabei kann es sich um eine vom Programmierer aufgesetzte Funktion handeln, oder - wenn Stringdaten durchsucht werden - um die Bibliotheksfunktion strcmp(). Die Vergleichsfunktion muß die folgenden zwei Kriterien erfüllen:

Der Rückgabewert von bsearch() ist ein Zeiger vom Typ void. Die Funktion gibt einen Zeiger auf die erste Array-Komponente zurück, die dem Schlüssel entspricht, oder NULL, wenn keine Übereinstimmung gefunden wird. Der Typ des zurückgegebenen Zeigers muß entsprechend umgewandelt werden, bevor der Zeiger verwendet werden kann.

Der sizeof()-Operator kann die num- und size-Argumente wie folgt bereitstellen. Wenn array[] das zu durchsuchende Array ist, dann liefert die Anweisung

sizeof(array[0]);
den Wert für size, das heißt die Größe eines Array-Elements in Byte. Da der Ausdruck sizeof(array) die Größe eines ganzen Arrays in Byte zurückliefert, können Sie mit der folgenden Anweisung den Wert von num, der Anzahl der Elemente im Array, ermitteln:
sizeof(array)/sizeof(array[0])

Sortieren mit qsort

Die Bibliotheksfunktion qsort() ist eine Implementierung des Quicksort-Algorithmus, der von C.A.R. Hoare erfunden wurde. Diese Funktion sortiert ein Array in eine vorgegebene Reihenfolge. Normalerweise wird aufsteigend sortiert, aber qsort() kann auch absteigend sortieren. Der Prototyp dieser Funktion ist in stdlib.h definiert und lautet:
void qsort(void *base, size_t num, size_t size,
           int (*cmp)(void *elem1, void *elem2));
Das Argument base zeigt auf das erste Element in dem Array, num ist die Anzahl der Komponenten im Array und size die Größe einer Array-Komponente in Byte. Das Argument cmp ist eine Zeiger auf eine Vergleichsfunktion. Für diese Vergleichsfunktion gelten die gleichen Regeln wie bei bsearch(). Oft verwendet man für bsearch() und qsort() die gleiche Vergleichsfunktion. Die Funktion qsort() hat keinen Rückgabewert.

Das folgende Listing veranschaulicht den Einsatz von qsort() und bsearch(). Das Programm sortiert und durchsucht ein Array von Integer-Werten. Zu Beginn des Programms können Sie bis zu MAX Werte eingeben. Die Werte werden sortiert und dann in der neuen Reihenfolge ausgegeben. Danach können Sie einen Wert eingeben, nach dem im Array gesucht werden soll. Eine abschließende Meldung informiert Sie darüber, ob der Wert im Array gefunden wurde oder nicht.

#include <stdio.h>
#include <stdlib.h>

#define MAX 20

int intvgl(const void *v1, const void *v2)
   { return (*(int *)v1 - *(int *)v2); }

int main(void)
  {
  int arr[MAX], count, suche, *zgr;

  /* Werte einlesen */
  printf("Geben Sie %d Integer-Werte ein.\n", MAX);
  for (count = 0; count < MAX; count++)
    scanf("%d", &arr[count]);

  /* Sortiert das Array in aufsteigender Reihenfolge */
  qsort(arr, MAX, sizeof(arr[0]), intvgl);

  /* Gibt das sortierte Array aus. */
  for (count = 0; count < MAX; count++)
    printf("\narr[%d] = %d.", count, arr[count]);

  /* Suchwert eingeben */
  printf("Geben Sie einen Wert für die Suche ein: ");
  scanf("%d", &suche);

  /* Suche durchfuehren */
  zgr = (int *)bsearch(&suche, arr, MAX, sizeof(arr[0]),intvgl);

  if ( zgr != NULL )
    printf("%d bei arr[%d] gefunden.\n", suche, (zgr - arr));
  else
    printf("%d nicht gefunden.\n", suche);
  return(0);
  }

Das nächste Listing macht im Prinzip das Gleiche wie das vorstehende, nur daß diesmal Strings sortiert und gesucht werden. Die Strings werden sortieren, indem das Array der Zeiger sortiert wird. Dazu muß allerdings die Vergleichsfunktion angepasst werden. Der Vergleichsfunktion werden Zeiger auf die zwei Elemente in dem Array übergeben, die verglichen werden. Sie wollen jedoch das Array von Zeigern nicht nach den Werten der Zeiger selbst, sondern nach den Werten der Strings, auf die die Zeiger verweisen, sortieren.

Deshalb müssen Sie eine Vergleichsfunktion verwenden, der Zeiger auf Zeiger übergeben werden. Jedes Argument an vergl() ist ein Zeiger auf eine Array-Komponente und da jede Komponente selbst ein Zeiger auf einen String ist, so ist das Argument ein Zeiger auf einen Zeiger. Innerhalb der Funktion selbst dereferenzieren Sie die Zeiger, so daß der Rückgabewert von vergl() von den Werten der Strings abhängt, auf die verwiesen wird.

Die Tatsache, daß die Argumente, die vergl() übergeben werden, Zeiger auf Zeiger sind, schafft auch noch in anderer Hinsicht Probleme. Sie speichern den Suchbegriff in puffer[] und Sie wissen auch, daß der Name eines Arrays (in diesem Fall puffer) ein Zeiger auf das Array ist. Sie müssen jedoch nicht puffer selbst übergeben, sondern einen Zeiger auf puffer. Das Problem dabei ist, daß puffer eine Zeigerkonstante ist und keine Zeigervariable. puffer selbst hat keine Adresse im Speicher; es ist ein Symbol, das zur Adresse des Arrays auswertet. Deshalb können Sie keinen Zeiger erzeugen, der auf puffer zeigt, indem Sie den Adressoperator vor puffer (wie in &puffer) verwenden.

Wie verhält man sich in einem solchen Fall? Zuerst erzeugen Sie eine Zeigervariable und weisen ihr den Wert von puffer zu. In unserem Programm trägt diese Zeigervariable den Namen suche. Da suche eine Zeigervariable ist, hat sie eine Adresse, und Sie können einen Zeiger erzeugen, der diese Adresse als Wert aufnimmt. Wenn Sie schließlich bsearch() aufrufen, übergeben Sie als erstes Argument suche1 - einen Zeiger auf einen Zeiger auf den Suchstring. Die Funktion bsearch() übergibt das Argument an vergl(), und alles läuft wie geschmiert.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 20

int vergl(const void *s1, const void *s2)
  { return (strcmp(*(char **)s1, *(char **)s2)); }

int main(void)
  {
  char *daten[MAX], puffer[80], *zgr, *suche;
  int count;

  /* Eine Liste von Wörtern einlesen. */
  printf("Geben  Sie %d Wörter ein.\n",MAX);
  for (count = 0; count < MAX; count++)
    {
    printf("Wort %d: ", count+1);
    fgets(puffer,80,stdin);
    puffer[strlen(puffer)-1] = '\0';
    daten[count] = malloc(strlen(puffer)+1);
    strcpy(daten[count], puffer);
    }

  /* Sortiert die Woerter (genauer: die Zeiger) */
  qsort(daten, MAX, sizeof(daten[0]), vergl);

  /* Die sortierten Woerter ausgeben */
  for (count = 0; count < MAX; count++)
    printf("\n%d: %s", count+1, daten[count]);

  /* Suchbegriff einlesen */
  printf("\n\nGeben Sie einen Suchbegriff ein: ");
  fgets(puffer,80,stdin);
  puffer[strlen(puffer)-1] = '\0';

  /* Fuehrt die Suche durch */
  /* &suche ist Zeiger auf den Zeiger auf den Suchbegriff.*/
  suche = puffer;
  zgr = bsearch(&suche, daten, MAX, sizeof(daten[0]), vergl);
  if (zgr != NULL)
    printf("%s gefunden.\n", puffer);
  else
    printf("%s nicht gefunden.\n", puffer);
  return(0);
  }

Boyer-Moore-Suche

Diesen Algorithmus basiert auf der Idee, daß es eigentlich unsinnig ist, nach jedem Fehlschlag beim Durchsuchen eines Strings wieder ganz von vorne anzufangen. Wenn man z. B. auf ein Zeichen trifft, das überhaupt nicht im Suchmuster vorkommt, lohnt es sich erst hinter dem Zeichen weiterzusuchen. Kommt das Zeichen im Suchmuster vor, aber nicht an der aktuellen Stelle, kann das Muster mehrere Stellen nach rechts verschoben werden.

Die Boyer-Moore-Suche geht dabei das Suchmuster von rechts nach links durch. Wenn sie dabei auf ein Zeichen im Text trifft, das ungleich dem korrespondierenden Zeichen im Suchmuster ist, gibt es drei verschiedene Möglichkeiten:

  1. Das Zeichen im Text kommt im Suchmuster gar nicht vor. In diesem Fall kann das Suchmuster bis hinter dieses Zeichen nach rechts verschoben werden.
  2. Das Zeichen im Text steht weiter vorne im Suchmuster (betrachtet wird sein letztes Vorkommen im Muster). In diesem Fall können wir das Suchmuster so weit nach rechts verschieben, daß das Zeichen im Suchmuster unter dem identischen Zeichen im Text steht.
  3. Das Zeichen im Text steht weiter hinten im Suchmuster. In diesem Fall können wir lediglich das Muster um eine Position nach rechts schieben.
Anschließend wird das Suchmuster erneut von hinten nach vorne durchsucht. Das wird so lange gemacht, bis entweder das Suchmuster das Ende des Textes erreicht hat (ohne daß es gefunden wurde), oder die Überprüfung erfolgreich bis zum Anfang des Suchmusters war (es also gefunden wurde). Es bleibt nun noch die Frage, wie man effizient die letze Position eines Zeichens im Suchmuster findet. Dies geschieht üblicherweise über eine Tabelle, in der zu jedem Zeichen einmal die entsprechende Position eingetragen wird, und dann später nur noch nachgesehen wird. Das Eintragen kann in einem Durchgang erfolgen, wobei ein Vorkommen eines Zeichens das jeweils vorhergehende Vorkommen dieses Zeichens überschreibt. Die Position -1 steht für "Zeichen nicht vorhanden".
int BMSearch(char *Pat, char *Txt)
  {
  int PosTable[256];
  int PatLen, TxtLen, Index, PatIndex, Position;
  if (strlen(Pat) == 0) return (0);
  PatLen = strlen(Pat);
  TxtLen = strlen(Txt);
  for (PatIndex = 0; PatIndex < 256; PatIndex++)
    PosTable[PatIndex] := -1;
  for (PatIndex = 0; PatIndex <= PatLen; PatIndex++)
      PosTable[(int) Pat[PatIndex]] := PatIndex;
  Index := 0;
  while (PatIndex >= 0) && (Index <= (TxtLen - PatLen)))
    {
    PatIndex := PatLen;
    while ((Pat[PatIndex] == Txt[Index + PatIndex]) && (PatIndex > 0))
	  PatIndex--;
    if (PatIndex >= 0)
      {
	  Position := PosTable[(char) Txt[Index + PatIndex]];
	  if (Position == -1) Index = Index + PatIndex;
      else
        if (Position > PatIndex) Index++;
        else Index = Index + PatIndex - Position;
      }
    }
   if (PatIndex < 0) return (Index + 1);
   else return(0);
  }
Es gibt auch noch weiter verbesserte Versionen dieses Algorithmus; dieser sollte jedoch für die meisten Fälle ausreichen.

Sortieren von linearen Listen

Die oben behandelten Algorithmen lassen sich nicht nur auf Tabellen (Arrays) anwenden, sondern auch auf andere Datenstrukturen adaptieren. Beispielhaft soll hier die Portierung zweier Verfahren auf lineare Listen gezeigt werden. Wenn Elemente in eine lineare Liste eingefügt werden sollen, dann tut man dies am besten gleich an der "richtigen" Stelle. Dies zeigt die Funktion InsertionSort im folgenden Listing.

Für das nachträgliche Sortieren einer linearen Liste wurde die Funktion BubbleSort gewählt, da hier der Algorithmuns sehr übersichtlich ist. Die anderen Sortierverfahren lassen sich nach dem gleichen Schema implementieren.


#include <stdio.h>
#include <stdlib.h>

struct LineareListe
  {
  double Element;
  struct LineareListe *next;
  };

typedef struct LineareListe LinList;

/*Insertion Sort mit verketteter Liste
 * Werte werden bei jedem Aufruf in der Liste eingereiht
 * Uebergeben werden Liste und einzureihendes Element
 */

LinList *InsertionSort ( LinList *Liste, double Wert )
  {
  LinList *temp = Liste;
  LinList *neu = malloc(sizeof(LinList));
  neu->Element = Wert;
  neu->next = NULL;

  if(Liste == NULL) return neu;

  /* Liste durchwandern, notfalls einreihen */
  while (temp->next != NULL)
    {
    if (temp->next->Element > Wert)
      {
      neu->next  = temp->next;
      temp->next  = neu;
      return Liste;
      }
    temp = temp->next;
    }
  /* Am Ende angelangt, Element einreihen */
  temp->next  = neu;
  /* Wenn letztes Element > neues Element,
       dann vertauschen */
  if (temp->Element > Wert)
    {
    neu->Element  = temp->Element;
    temp->Element  = Wert;
    }
  /* Listenanfang zurückgeben */
  return Liste;
  }


/*Bubble Sort mit Liearen Listen
 * Es wird bei einer Liste erst das erste und dann alle nachfolgenden
 * Elemente mit der Restliste verglichen und mit kleineren Elementen vertauscht
 */

LinList *BubbleSort (LinList *Liste)
  {
  LinList *Rest, *Akt = Liste;
  double swap;
  /* Liste ist leer oder hat nur ein Element */
  if ((Liste == NULL) || (Liste->next == NULL)) return Liste;
  /* Sortierverfahren Bubblesort */
  do
    {
    Rest = Akt;
    do
      {
      Rest = Rest->next;
      /* Wenn der Restwert kleiner als Vergleichswert, dann vertauschen */
      if (Rest->Element < Akt->Element)
        {
        swap = Rest->Element;
        Rest->Element = Akt->Element;
        Akt->Element = swap;
        }
      } while (Rest->next != NULL);
    Akt = Akt->next;
    } while (Akt->next != NULL);
  return Liste;
  }

Soundex-Verfahren

Der Soundex-Code für einen Begriff wird wie folgt berechnet:
  1. Entferne alle Vokale und die Konsonanten H, W, Y. Von aufeinanderfolgenden gleichen Zeichen bleibt nur eins erhalten. Das erste Zeichen bleibt erhalten.
  2. Entwickle den Soundex-Code für den ersten und die darauffolgenden maximal 3 Zeichen nach der Soundex-Tabelle.
Buchstaben Ziffern Erzeugung der Laute
b, f, p, v 1 Lippen, öffnend
c, g, j, k, q, s, x, z 2 Rachen, Zunge
d, t 3 Zunge, Zähne
l 4 Zunge, Gaumen
m, n 5 Lippen, geschlossen
r 6 Zunge, rollend

Der Soundex-Algorithmus basiert auf der Annahme, daß Worte, die ähnlich klingen, auch von der Semantik her ähnlich sind. Soundex reduziert jedes Wort auf einen eindeutigen maximal vier Zeichen langen Code.
In der letzten Spalte wird die Erzeugung der Laute klassifiziert. Wir sehen, daß die Zusammenfassung sich an der Erzeugung orientiert. Somit ergibt sich immer eine Kombination aus einem Buchstaben und einer dreistelligen Zahl, die maximal 666 erreichen kann.
Die Verbesserungen bzw. - vorsichtiger ausgedrückt - die Variationen können sich z. B. auf die Behandlung des Anfangsbuchstabens beziehen, indem wir ihn wie die anderen Buchstaben behandeln. Dieser Algorithmus wird als Extended Soundex Algorithmus bezeichnet. Hier ergibt sich eine vierstellige Zahl, die 6666 nicht überschreitet, so daß sie in max. 2 Byte abgespeichert werden kann, was bei sehr großen Dateien natürlich erheblichen Speicherplatz einspart.
Wir können nun versuchen, Verbesserungen vorzunehmen. Diese müssen sich aber immer am Sprachverständnis der erfassenden Person orientieren.

Beispiele:

StringZwischenschrittSoundex-Code
Stadtstdt2333
stattst23
Staatst23

Soundex ist leicht in relationalen Datenbanken implementierbar. Der Soundex-Code sollte für jeden Begriff in der Datenbank in einer Relation abgespeichert werden. Die Suche nach Begriffen, die ähnlich zu einem Suchwort sind, kann man über den invertierten Index der Soundex-Codes realisieren. Soundex liefert aufgrund seiner Einfachheit vergleichsweise schlechte Ergebnisse. Die folgende Implementierung hat zwei Parameter, instr ist ein beliebiger Eingabstring, outstr liefert den erzeugten Soundex-String. Dies ist auch gleichzeitig der Return-Wert der Funktion. Da der Standard-Soundex nur für ASCCI (ohne Umlaute) geeignet ist, sind die Umlaute auf die entsprechenden Vokale umcodiert wirden.

char *Soundex(char *instr, char *outstr)
  {           /* ABCDEFGHIJKLMNOPQRSTUVWXYZ */
  char *table = "01230120022455012623010202";
  char *outptr = outstr;
  int count = 0;

  while(!isalpha(instr[0]) && instr[0] != '\0') ++instr;
  if(instr[0] == '\0') return(NULL); /* Stringende */

  if(toupper(instr[0]) == 'P' && toupper(instr[1]) == 'H')
    {
    instr[0] = 'F';
    instr[1] = 'A';
    }

  *outptr++ = (char)toupper(*instr++);

  while((*instr != '\0') && (count < 5))
    {
    if(isalpha(*instr) && (*instr != *(instr-1)))
      {
      switch (instr[0])
        {
        case 'ä': instr[0] = 'a'; break;
        case 'ö': instr[0] = 'o'; break;
        case 'ü': instr[0] = 'u'; break;
        case 'Ä': instr[0] = 'A'; break;
        case 'Ö': instr[0] = 'O'; break;
        case 'Ü': instr[0] = 'U'; break;
        case 'ß': instr[0] = 's'; break;
        default: break;
        }
      *outptr = table[toupper(instr[0]) - 'A'];
      if(*outptr != '0')
        {
         ++outptr;
         ++count;
        }
      }
    ++instr;
    }

  *outptr = '\0';
  return(outstr);
  }

Die folgende, etwas komplexere Variante von Soundex eignet sich besser für die Indizierung von Namen. Das Original stammt von Joe Celko ("The C Gazette" Vol. 4 Nr. 2). Dieser Algorithmus hat folgende Eigenschaften:

Es wäre möglich gewesen, etliche Konvertierungen in einer Schleife zusammenzufassen. Joe Celko hat etwas "großzügiger" programmiert, um Änderungen leichter zu machen.

#define WBUFSIZE 512

void soundex4(const char *instr, char *outstr, int N)
  {
  char *p, *p1;
  int i;
  char workbuf[WBUFSIZE + 1];
  char priorletter;

  /* Make a working copy */
  strncpy(workbuf, instr, WBUFSIZE);
  workbuf[WBUFSIZE] = '\0';

  /* Konvertieren zu Grossbuchstaben und Umlaute */
  for (p = workbuf; *p; ++p)
    {
    *p = toupper(*p);
    switch (*p)
      {
      case 'ä': *p = 'A'; break;
      case 'ö': *p = 'O'; break;
      case 'ü': *p = 'U'; break;
      case 'Ä': *p = 'A'; break;
      case 'Ö': *p = 'O'; break;
      case 'Ü': *p = 'U'; break;
      case 'ß': *p = 'S'; break;
      default: break;
      }
    }
  /* Konvertieren alle Vokale zu 'A' */
  for (p = workbuf; *p; ++p)
    if (strchr("AEIOUY", *p)) *p = 'A';

  /* Praefix-Transformation: Nur am Anfang des Namens */
  if (strncmp(workbuf, "MAC", 3) == NULL)          /* MAC to MCC */
    workbuf[1] = 'C';
  else if (strncmp(workbuf, "KN", 2) == NULL)  /* KN to NN */
    workbuf[0] = 'N';
  else if (workbuf[0] == 'K')                      /* K to C */
    workbuf[0] = 'C';
  else if (strncmp(workbuf, "PF", 2) == NULL)  /* PF to FF */
    workbuf[0] = 'F';
  else if (strncmp(workbuf, "SCH", 3) == NULL) /* SCH to SSS */
   workbuf[1] = workbuf[2] = 'S';

  /*Infix-Transformationen: ab dem 2. Buchstaben,
   * von links nach rechts                                   */
  while ((p = strstr(workbuf, "DG")) > workbuf)   /* DG to GG */
    p[0] = 'G';
  while ((p = strstr(workbuf, "CAAN")) > workbuf) /* CAAN to TAAN */
    p[0] = 'T';
  while ((p = strchr(workbuf, 'D')) > workbuf)    /* D to T */
    p[0] = 'T';
  while ((p = strstr(workbuf, "NST")) > workbuf)  /* NST to NSS */
    p[2] = 'S';
  while ((p = strstr(workbuf, "AV")) > workbuf)   /* AV to AF */
    p[1] = 'F';
  while ((p = strchr(workbuf, 'Q')) > workbuf)    /* Q to G */
    p[0] = 'G';
  while ((p = strchr(workbuf, 'Z')) > workbuf)    /* Z to S */
    p[0] = 'S';
  while ((p = strchr(workbuf, 'M')) > workbuf)    /* M to N */
    p[0] = 'N';
  while ((p = strstr(workbuf, "KN")) > workbuf)   /* KN to NN */
    p[0] = 'N';
  while ((p = strchr(workbuf, 'K')) > workbuf)    /* K to C */
    p[0] = 'C';
  while ((p = strstr(workbuf, "AH")) > workbuf)   /* AH to AA */
    p[1] = 'A';
  while ((p = strstr(workbuf, "HA")) > workbuf)   /* HA to AA */
    p[0] = 'A';
  while ((p = strstr(workbuf, "AW")) > workbuf)   /* AW to AA */
    p[1] = 'A';
  while ((p = strstr(workbuf, "PH")) > workbuf)   /* PH to FF */
    p[0] = p[1] = 'F';
  while ((p = strstr(workbuf, "SCH")) > workbuf)  /* SCH to SSS */
    p[0] = p[1] = 'S';

  /*Suffix-Transformationen: am Wortende */
  /* (1) 'A's und 'S's am Ende weg */
  for (i = strlen(workbuf) - 1;
    (i > 0) && ((workbuf[i] == 'A') || (workbuf[i] == 'S'));
    --i)
      workbuf[i] = '\0';
  /* (2) NT -&lt; TT */
  for (i = strlen(workbuf) - 1;
    (i > 1) && ('N' == workbuf[i - 1] || 'T' == workbuf[i]);
    --i)
      workbuf[i - 1] = 'T';
  /* Nun alle Vokale weg (bis auf den ersten) */
  p = p1 = workbuf;
  while ((*p1++ = *p++) != '\0')
    while (*p == 'A') ++p;
  /* Dubletten weg */
  p = p1 = workbuf;
  priorletter = '\0';
  do
    {
    while (*p == priorletter) ++p;
    priorletter = *p;
    } while ((*p1++ = *p++) != '\0');

  strncpy(outstr, workbuf, N);
  outstr[N] = '\0';
  }

8.6 Implementierung von Mengen (Sets)

Andere Programmiersprachen (z. B. Pascal) kennen den Datentyp der Menge und entsprechenden Operationenen auf Mengen. In C gibt es nicht s vergleichbares. Mengen lassen sich aber als Bit-Arrays implementieren. Die Elemente der Menge werden numeriert und jedes Mengenelement wird durch ein Bit repräsentiert. Ist das entsprechende Bit gesetzt (also 1), so ist das Element in der Menge enthalten, ist das Bit auf 0 gesetzt, ist das entsprechende Element nicht in der Menge enthalten. Schnittmenge und Vereinigung lassen sich dann durch logische UND- bzw. ODER-Verknüpfung erreichen. Da eine Variable vom Typ int oder char nur relativ kleine Mengen repräsentieren kann, wird eine Menge als zusammenhängender Speicherbereich allokiert und über Zeiger darauf zugegriffen. So kann man die Menge an die jeweilige Problemstellung anpassen, ohne die Funktionen ändern zu müssen.

Mengen eigenen sich auch im Zusammenhang mit Datenbanken oder Suchsystemen zur Speicherhung des Suchergebnisses (Suchbegriff ist im Datensatz X enthalte/nicht enthalten). Durch die Schnittmenge lassen sich zwei Suchergebnisse UND-verknüpfen und durch die Vereinigungsmenge ODER-verknüpfen. Die Ergebnisspeicherung ist mit der folgenden Mengenimplementierung sehr kompakt. Es kommen bitweise Verknüpfungen und Schiebeoperationen zur Anwendung.

#include <stdio.h>
#include <stdlib.h>     /* fuer size_t   */
#include <limits.h>     /* fuer CHAR_BIT */

/* Speicher fuer das Bitarray belegen */
char *alloc_bitarray(size_t bits)
  {
  char *set = calloc((bits + CHAR_BIT - 1) / CHAR_BIT, sizeof(char));
  return set;
  }

/* Wert eines bestimmten Bits lesen
*    Rueckgabewert: 0 oder 1
*    Bei Betrachtung als Menge:
*      1: Element ist enthalten
*      0: Element ist nicht enthalten
*/
int liesbit(char *set, int number)
  {
  set += number / CHAR_BIT;
  return (*set & (1 << (number % CHAR_BIT))) != 0;
  }

/* ein bestimmtes Bit setzen
*     Bei Betrachtung als Menge:
*       1: Element der Menge hinzufuegen
*       0: Element aus der Menge entfernen
*/
void setzebit(char *set, int number, int value)
  {
  set += number / CHAR_BIT;
  if (value)
    *set |= 1 << (number % CHAR_BIT);    /* set bit */
  else
    *set &= ~(1 << (number % CHAR_BIT)); /* clear bit */
  }

/* ein bestimmtes Bit invertieren
*     (0 -> 1 bzw. 1 -> 0
*/
void invertbit(char *set, int number)
  {
  set += number / CHAR_BIT;
  *set ^= 1 << (number % CHAR_BIT);
  }

/* Schnittmenge von set1 und set2 berechnen
*    (bitweise UND-Verknuepfung)
*    Rueckgabewert in set3
*    Der Parameter 'bits' muss den gleichen Wert wie bei
*    'alloc_bitarray' haben!
*/
void schnitt(char *set1, char *set2, char *result, size_t bits)
  {
  int i;
  for (i = 0; i <= (bits + CHAR_BIT - 1) / CHAR_BIT; i++)
    {
    *result = *set1 & *set2;
    result++; set1++;set2++;
    }
  }

/* Vereinigungsmenge von set1 und set2 berechnen
*    (bitweise ODER-Verknuepfung)
*    Rueckgabewert in set3
*    Der Parameter 'bits' muss den gleichen Wert wie bei
*    'alloc_bitarray' haben!
*/
void vereinigung(char *set1, char *set2, char *result, size_t bits)
  {
  int i;
  for (i = 0; i <= (bits + CHAR_BIT - 1) / CHAR_BIT; i++)
    {
    *result = *set1 | *set2;
    result++; set1++;set2++;
    }
  }

/* Bitweise Ausgabe einer Menge (0 oder 1)
*    Der Parameter 'bits' muss den gleichen Wert wie bei
*    'alloc_bitarray' haben!
*/
void print_bitarray(char *set, size_t bits)
  {
  int i, j;
  for (i = 0; i < (bits + CHAR_BIT - 1) / CHAR_BIT; i++)
    {
    for (j = 0; j < CHAR_BIT; j++)
      if (*set & (1 << j)) putchar('1');
      else                 putchar('0');
    set++;
    }
  putchar('\n');
  }

/* Testprogramm */
int main ()
  {
  char *Menge1, *Menge2, *Menge3;
  Menge1 = alloc_bitarray(40);
  Menge2 = alloc_bitarray(40);
  Menge3 = alloc_bitarray(40);

  setzebit(Menge1,0,1);
  setzebit(Menge1,7,1);
  setzebit(Menge1,20,1);
  setzebit(Menge1,39,1);

  setzebit(Menge2,0,1);
  setzebit(Menge2,8,1);
  setzebit(Menge2,21,1);
  setzebit(Menge2,39,1);

  printf("          1         2         3         4\n");
  printf("01234567890123456789012345678901234567890\n");
  print_bitarray(Menge1,40);
  print_bitarray(Menge2,40);

  schnitt(Menge1, Menge2, Menge3,40);
  print_bitarray(Menge3,40);

  vereinigung(Menge1, Menge2, Menge3,40);
  print_bitarray(Menge3,40);
  return 0;
  }

8.7 Common Gateway Interface in C

Das Common Gateway Interface (CGI) beschreibt nur ein Protokoll, nicht eine bestimmte Programmiersprache. CGI-Programme lassen sich somit in jeder auf dem Server verfügbaren Programmiersprache erstellen. Häufig wird jedoch die Sprache Perl verwendet, da sie plattformübergreifend verfügbar ist und sich besonders zur Manipulation von Texten eignet - und das ist meist die Hauptanwendung für CGI-Programme. Ein CGI-Programm (wegen der Interpretersprache Perl auch oft "CGI-Script" genannt) ist nichts besonderes. Es ist ein Programm, das von der Standardeingabe (stdin) lesen und auf die Standardausgabe (stdout) schreiben kann. Wer in der Lage ist, ein solches Programm zu schreiben, kann auch CGI-Scripts erstellen.

CGI ist, wie gesagt, keine Sprache. Es ist vielmehr ein einfaches Protokoll, das der Kommunikation zwischen HTML-Formularen und einem Programm dient. Ein CGI-Script kann in jeder Sprache geschrieben sein. Diese Kurzanleitung konzentriert sich daher auch auf die Verarbeitung von HTML-Forms. Einige Details werden nicht behandelt, dafür kommt man um so schneller zum Ziel und deckt 90% der üblichen Anwendungen ab.

Ein CGI-Script führt die folgenden typischen Schritte aus:

  1. Lesen der vom Clienten erzeugten Daten (entweder von der Parameterzeile des Programms oder von der Standardeingabe.
  2. Verarbeiten der Daten
  3. Schreiben einer Antwort in HTML auf die Standardausgabe.
Eine URL für ein CGI-Script sieht genau wie eine normale URL aus. Wie weiß der Server aber, daß es sich um eine ausführbare Datei und nicht um eine normale HTML-Seite handelt? Das ist ganz einfach. In der Konfigurationsdatei wurde eine Exec-Regel definiert. Sie zeigt auf das Verzeichnis, in dem sich die Scripte befinden.

Sofort stellt sich die Frage, "Wie kann man dem Script Anfragen mitteilen?". Dazu müssen einfach Parameter durch ein Fragezeichen getrennt an die URL angehängt werden (kann man bei Google gut studieren). Alternativ werden die Daten aus einem Formular an die Standardeingabe eines Programms geschickt. In einer Parameterzeile dürfen keine Leerzeichen stehen, weshalb sie durch ein "+"-Zeichen ersetzt werden. Sonderzeichen (Code > 127) werden durch ein Prozentzeichen (%) und den hexadezimalen Code des Zeichens ersetzt. Man kann also z. B. für ein Shop-Programm ein Bestell-Link der folgenden Form in eine Webseite einfügen:

<A HREF="http://shop.server.de/cgi-bin/shopper.pl?prodid=23481227">Bestellen</A>
Genauso häufig sind Daten, die durch die Eingabe in ein Formular erzeugt werden. Wenn der Client seine Daten übermittelt (Submit-Knopf im Formular), erhält das Script alle erzeugten Daten als einen Satz von Name-Wert-Paaren. Der Name ist jeweils der, den man beim INPUT-Tag (bzw. beim SELECT- oder TEXTAREA-Tag) festgelegt hat, die Werte sind das, was der Anwender ins Formular eingetragen oder gewählt hat. Dieser Satz von Name-Wert-Paaren wird in einem einzigen langen String übermittelt, den das CGI-Programm auflösen muß. Das ist nicht sehr kompliziert, und es gibt viele fertige Routinen dazu. Der Aufbau des Strings ist recht einfach:
     name1=wert1&name2=wert2&name3=wert3
Man muß den String also einfach beim &-Zeichen zerlegen. Dann erhält man die Paare
name1=wert1
name2=wert2
name3=wert3
In den entstandenen Häppchen muß man nun noch

Das kommt daher, das der übermittelte String in der URL des CGI-Programms codiert ist. Bei einer Form der Übermittlung zum Server wird er durch "?" getrennt an die URL angehängt, was Sie beispielsweise beim Bedienen einer Suchmaschine in der URL-Zeile des Browsers sehen kann. Der Anwender muß aber nach wie vor die Möglichkeit haben, &-Zeichen und Gleichheitszeichen zu übergeben - deshalb die Codierung durch "%xx". Die folgende Tabelle zeigt die Zeichencodierung:

ZeichenCodeZeichenCode ZeichenCodeZeichenCode
Leerz.+ !%21 "%22 #%23
$%24 %%25 &%26 '%27
(%28 )%29 +%2B ,%2C
/%2F :%3A ;%3B <%3C
=%3D >%3E ?%3F [%5B
\%5C ]%5D ^%5E "%60
{%7B |%7C }%7D ~%7E
°%A7 Ä%C4 Ö%D6 Ü%DC
ß%DF ä%E4 ö%F6 ü%FC

Von wo das CGI-Programm den Formularinhalt erhält, hängt von der Methode ab, mit der die HTTP-Form übermittelt wurde:

All das geschieht hinter den Kulissen. Für den CGI-Programmierer funktionieren GET und POST fast gleich und sind gleich einfach zu benutzen. Der Vorteil von POST ist, daß man beliebig viele Daten übertragen kann. Der Vorteil von GET ist, daß alle Daten in eine URL gebastelt sind - man kann auf sie also verweisen oder sie in die Bookmarks aufnehmen.

Hier sind noch einmal die Schritte aufgeführt, die ein CGI-Script normalerweise durchlebt, wenn es vom Benutzer aufgerufen wird:

Damit sind die wesentlichsten Merkmale eines CGI-Scriptes erklärt. Alles was man tun muß, um selber ein CGI-Script zu schreiben, ist diese Punkte umzusetzen. Wie man das am besten tun kann, soll in den folgenden Abschnitten näher erklärt werden.

Der Browser sendet die Anfrage an ein CGI-Programm genauso ab, wie die Anforderung eines HTML-Dokuments und er erwartet natürlich auch, daß der Server mit entsprechenden Daten antwortet. Bei CGI wird jedoch keine HTML-Seite gesendet, sondern das Programm erzeugt die Daten dynamisch. Als erstes gibt es die Zeile

Content-Type: text/html
gefolgt von einer Leerzeile auf die Standardausgabe aus. Nun läßt es eine normale HTML-Antwort folgen, die es ebenfalls auf die Standardausgabe ausgibt. Wenn das Script beendet ist, sieht der Anwender die so erzeugte Seite. Das Script liegt in einem speziellen Verzeichnis auf dem Server (meist "cgi-bin"). Der Content-Type kann natürlich variieren, es sind alle gebräuchlichen und vom Browser akzepierten MIME-Typen erlaubt. Versuchen wir es mal mit einem einfachen Beispiel.

Das folgende Programm liefern jeweils nur ein "Hello World" als HTML-Seite.

/************************************************/
/**  hello.c -- simple "hello, world" fuer cgi **/
/************************************************/
#include <stdio.h>
int main(void)
  {
  /** CGI response header **/
  printf("Content-type: text/html\n\n");

  /** HTML response page **/
  printf("<html>\n");
  printf("<head><title>CGI Output</title></head>\n");
  printf("<body>\n");
  printf("<h1>Hello, world.</h1>\n");
  printf("</body>\n");
  printf("</html>\n");

  return(0);
  }

Formulareingaben bearbeiten

Das Bearbeiten von Formulardaten ist der Kern einer jeden Webanwendung. Um sich das Leben leichter zu machen, kann man die wichtigsten Environment-Variablen über Makros zugänglich machen (spart das ständige getenv() im Quelltext):
/* CGI Environment Variablen */
#define SERVER_NAME getenv("SERVER_NAME")
#define SERVER_PROTOCOL getenv("SERVER_PROTOCOL")
#define SERVER_PORT getenv("SERVER_PORT")
#define PATH_INFO getenv("PATH_INFO")
#define PATH_TRANSLATED getenv("PATH_TRANSLATED")
#define SCRIPT_NAME getenv("SCRIPT_NAME")
#define REMOTE_HOST getenv("REMOTE_HOST")
#define REMOTE_ADDR getenv("REMOTE_ADDR")
#define CONTENT_TYPE getenv("CONTENT_TYPE")
#define REQUEST_METHOD getenv("REQUEST_METHOD")
#define CONTENT_LENGTH getenv("CONTENT_LENGTH")
#define QUERY_STRING getenv("QUERY_STRING")
Als ersten Versuch kann man diese per Script ausgeben:
#include <stdio.h>
#include <stlib.h>
#include <string.h>

/* DEFINEs wie oben */

/* Funktionsprototypen */
void PrintCGIVars(void);

int main(void)
  {
  /** CGI response header **/
  printf("Content-type: text/html\n\n");

  /** HTML response page **/
  printf("<html>\n");
  printf("<head><title>CGI Output</title></head>\n");
  printf("<body>\n");

  PrintCGIVars();

  printf("</body>\n");
  printf("</html>\n");

  return(0);
  }

void PrintCGIVars(void)
  /* Einige Umgebungsvariablen ausgeben */
  {
  printf("SERVER_NAME = %s<br>\n",SERVER_NAME);
  printf("SERVER_PROTOCOL = %s<br>\n",SERVER_PROTOCOL);
  printf("SERVER_PORT = %s<br>\n",SERVER_PORT);
  printf("REQUEST_METHOD = %s<br>\n",REQUEST_METHOD);
  printf("PATH_INFO = %s<br>\n",PATH_INFO);
  printf("PATH_TRANSLATED = %s<br>\n",PATH_TRANSLATED);
  printf("SCRIPT_NAME = %s<br>\n",SCRIPT_NAME);
  printf("QUERY_STRING = %s<br>\n",QUERY_STRING);
  printf("REMOTE_HOST = %s<br>\n",REMOTE_HOST);
  printf("REMOTE_ADDR = %s<br>\n",REMOTE_ADDR);
  printf("CONTENT_TYPE = %s<br>\n",CONTENT_TYPE);
  printf("CONTENT_LENGTH = %s<br>\n",CONTENT_LENGTH);
  }
Kern jedes CGI-Scripts ist das Bearbeiten der Formular-Eingaben. Die folgende Funktion CGIReadInput erledigt dies sowohl für POST als auch für GET. Die Wertepaare (Name, Wert) aus dem Formular werden in einer linearen Liste gespeichert, auf die dann in anderen Programmteilen zugegriffen werden kann. Dazu wird im folgende Struktur dfiniert:
struct LinListe
  {
  char *name;
  char *value;
  struct LinListe *next;
  };
Ausserdem braucht die Funktion noch zwei Hilfsroutinen zum Decodieren der Formulardaten. x2c() wandelt eine zweistellige Hexadezimalzahl in das entsprechende ASCII-Zeichen um und unescape() verwendet x2c(), um einen ganzen String von den Ersatzdarstellungen der Form "%XX" zu befreien und in einen reinen ASCII-String umzuwandeln:
char x2c(char hex[])
  {
  /* Hexadezimal zu Character-Umwandlung */
  char digit;

  if (hex[0] >= 'A') digit = ((hex[0] & 0xdf) - 'A') + 10;
  else               digit = (hex[0] - '0');
  digit = digit * 16;
  if (hex[1] >= 'A') digit = digit + ((hex[1] & 0xdf) - 'A') + 10;
  else               digit = digit + (hex[1] - '0');
  return(digit);
  /* Das ginge sogar noch einfacher:
     digit = (hex[0] >= 'A' ? ((hex[0] & 0xdf) - 'A')+10 : (hex[0] - '0'));
     digit = digit * 16;
     digit += (hex[1] >= 'A' ? ((hex[1] & 0xdf) - 'A')+10 : (hex[1] - '0')); */
  }

void unescape(char *url)
  /* Diese Funktion wandelt eine URL wieder in eine Folge
     von ASCII-Zeichen um */
  {
  int x, y;
  char hex[2];

  for (x=0,y=0; url[y] != '\0'; x++,y++)
    {
    if (url[y] == '+')           /* Leerzeichen restaurieren */
      url[x] = ' ';
    else if(url[y] == '%')       /* Hexadezimalangabe */
      {
      hex[0] = url[y+1];
      hex[1] = url[y+2];
      y = y + 2;
      url[x] = x2c(hex);
      }
    else
      url[x] = url[y];           /* 'normales' Zeichen */
    }
  url[x] = '\0';                 /* Stringende-Zeichen anhängen */
  }
Die Listenfunktionen enthalten keine Besonderheiten, eine erklärende Beschreibung ist in fast jedem C-Buch zu finden. Für die Verarbeitung von Formulardaten sind folgende Funktionen definiert:
struct LinListe *CGIReadInput(struct LinListe *root);
struct LinListe *Enter(struct LinListe *root, char *Name, char *Value);
struct LinListe *Suche(struct LinListe *root, char *SuchName);
void Drucke(struct LinListe *root);
CGIReadInput() nimmt die Formulareingaben entgegen (bei GET aus der Umgebungsvariablen und bei POST von der Standardeingabe), teilt sie in die einzelnen "Name=Wert"-Paare, decodiert die Ersatzdarstellung der ASCII-Zeichen mit den oben beschriebenen Funktionen und speichert die Paare schliesslich in der linearen Liste unter Zuhilfenahme von Enter(). Die Funktion Drucke() dient eigentlich nur dem Test uund der Fehlersuche. Mittels Suche() kann man dann innerhalb des Programms nach einem bestimmten Feldnamen des Formulars suchen und erhält dessen Wert.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>

/* CGI Environment Variablen */
#define SERVER_NAME getenv("SERVER_NAME")
#define SERVER_PROTOCOL getenv("SERVER_PROTOCOL")
#define SERVER_PORT getenv("SERVER_PORT")
#define PATH_INFO getenv("PATH_INFO")
#define PATH_TRANSLATED getenv("PATH_TRANSLATED")
#define SCRIPT_NAME getenv("SCRIPT_NAME")
#define REMOTE_HOST getenv("REMOTE_HOST")
#define REMOTE_ADDR getenv("REMOTE_ADDR")
#define CONTENT_TYPE getenv("CONTENT_TYPE")
#define REQUEST_METHOD getenv("REQUEST_METHOD")
#define CONTENT_LENGTH getenv("CONTENT_LENGTH")
#define QUERY_STRING getenv("QUERY_STRING")

struct LinListe
  {
  char *name;
  char *value;
  struct LinListe *next;
  };

/* Funktionsprototypen */
char x2c(char hex[]);
void unescape(char *url);
struct LinListe *CGIReadInput(struct LinListe *root);
struct LinListe *Enter(struct LinListe *root, char *Name, char *Value);
void Drucke(struct LinListe *root);
struct LinListe *Suche(struct LinListe *root, char *SuchName);

struct LinListe *root = NULL;

int main(void)
  {
 struct LinListe *Erg;

  printf("Content-Type: text/html\r\n\r\n");
  printf("<HTML><HEAD><TITLE>Formular-Eingabe</TITLE></HEAD>\n");
  printf("<BODY><H1>Wiki-Eingabe</H1>\n");

  root = CGIReadInput(root);
  Drucke(root);

  Erg = Suche(root,"Autor");
  if (Erg == NULL)
    printf("Nicht gefunden\n");
  else
    printf("Suchergebnis: %s\n",Erg->value);

  printf("</BODY></HTML>\n");
  return EXIT_SUCCESS;
  }

struct LinListe *Enter(struct LinListe *root, char *Name, char *Value)
  {
  struct LinListe *Neu;

  Neu = (struct LinListe *) malloc(sizeof(struct LinListe));
  if (Neu == NULL)
    {
    printf("Speicher voll, Abbruch...\n");
    exit(1);
    }
  Neu->name = (char *) malloc(strlen(Name)+1);
  Neu->value = (char *) malloc(strlen(Value)+1);
  Neu->next = NULL;
  strcpy(Neu->name,Name);
  strcpy(Neu->value,Value);
 /* Element vor root einhaengen, root wird neues Element */
  Neu->next = root;
  root = Neu;
  return(root);
  }

void Drucke(struct LinListe *root)
  {
  struct LinListe *Tail = root;
  while (Tail != NULL)
    {
    printf("%s: %s\n", Tail->name, Tail->value);
    Tail = Tail->next;
    }
  }

struct LinListe *Suche(struct LinListe *root, char *SuchName)
  {
  struct LinListe *Tail = root;
  while (Tail != NULL)
    {
    if (strcmp(SuchName,Tail->name) == 0)
      return(Tail);
    Tail = Tail->next;
    }
  return(NULL);
  }

struct LinListe *CGIReadInput(struct LinListe *root)
  /* Bearbeiten der CGI-Daten und Aufspalten in
     die Paare Name/Wert. Es werden GET- und
     POST-Requests verarbeitet. */
  {
  int i, j, content_length, maxlen;
  short NM = 1; /* Statusvariable, NM=1: Name, NM=0: Wert */
  char *input, *name, *value, *filename;

  /* Eingabe prüfen */
  if (REQUEST_METHOD == NULL)
    {
    printf("Error: REQUEST_METHOD is null\n");
    exit(1);
    }
  if (CONTENT_LENGTH == NULL)
    {
    return(NULL);
    }

  /* Benoetigte Werte holen und Speicher reservieren */
  content_length = atoi(CONTENT_LENGTH);
  maxlen = content_length - 1;
  /* genügend Speicher fuer die Eingabe reservieren */
  input = malloc(sizeof(char) * content_length + 1);
  /* Name und Wert koennen maximal so lang sein wie die Eingabe */
  name = malloc(sizeof(char) * content_length + 1);
  value = malloc(sizeof(char) * content_length + 1);
  filename = malloc(sizeof(char) * content_length + 1);
  if (!strcmp(REQUEST_METHOD,"POST"))
    { /* Daten von der Standardeingabe lesen */
    if (fread(input,sizeof(char),content_length,stdin) != content_length)
      {
      /* consistency error. */
      printf("Error: input length < CONTENT_LENGTH\n");
      exit(1);
      }
    }
  else if (!strcmp(REQUEST_METHOD,"GET"))
    { /* Daten aus der Umgebungsvariablen QUERY_STRING holen */
    if (QUERY_STRING == NULL)
      {
      printf("Error: QUERY_STRING is null\n");
      exit(1);
      }
    strcpy(input,QUERY_STRING);
    }
  else
    { /* error: invalid request method */
    printf("Error: REQUEST_METHOD invalid\n");
    exit(1);
    }

  /* Daten aufsplitten */
  j = 0;
  for (i = 0; i < content_length; i++)
    {
    if (input[i] == '=')
      { /* Name zuende, nun Wert verarbeiten */
      name[j] = '\0';
      unescape(name);
      if (i == maxlen)
        { /* Ende der Eingabe, kein Wert */
        strcpy(value,"");
        /* abspeichern */
        root = Enter(root,name,value);
        printf ("%s --> '%s'<br>\n",name, value);

        }
      j = 0; NM = 0;
      }
    else if ((input[i] == '&') || (i == maxlen))
      { /* Wertangabe zuende */
      if (i == maxlen)
        { /* Ende der Eingabe, letzter Wert */
        value[j] = input[i];
        j++;
        }
      value[j] = '\0';
      unescape(value);
      /* abspeichern */
      root = Enter(root,name,value);
      printf ("%s --> '%s'<br>\n",name, value);
      j = 0; NM = 1;
      }
    else if (NM)
      { /* Name wird gerade gelesen */
      name[j] = input[i];
      j++;
      }
    else if (!NM)
      { /* Wert wird gerade gelesen */
      value[j] = input[i];
      j++;
      }
    }
  return(root);
  }
Damit stehen die wichtigsten C-Grundroutinen für CGI-Anwendungen zur Verfügung.
Zum Inhaltsverzeichnis Zum nächsten Abschnitt


Copyright © FH München, FB 04, Prof. Jürgen Plate