8 Ausgewählte Algorithmen (Teil 1)

8.1 Verarbeitung von Zeichenketten (Strings)

Einfache Stringoperationen

Bibliothek zum Test von Zeichen: <ctype.h>

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);
  }

#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

char a[100];
char b[100];
char c;
int n;
int m;

strcat ( char *a , char *b )

#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 )

#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 )

#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);
  }

void strcpy(char *a, char *b)
  { 
  int i = 0;
  while ((a[i] = b[i]) != '\0')
     i++;
  }

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

#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 )

#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 )

#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 )

#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 )

• a < b --> m = -1 (bzw. negativ)
• a = b --> m = 0
• a > b --> m = 1 (bzw. positiv)

#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 )

• a < b --> m = -1 (bzw. negativ)
• a = b --> m = 0
• a > b --> m = 1 (bzw. positiv)

#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)

#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)

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)

char *strupper(char *string)
  {
  char *s;
  if (string != NULL)
    for (s = string; *s; ++s)
      *s = toupper(*s);
  return string;
  } 

char *strlower(char *string)

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 )

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;
  }

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[])

# 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[] )

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

• am Anfang der Zeichenkette
• am der Zeichenkette
• und mehrfach aufeinanderfolgende innerhalb der Zeichenkettte

#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

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,...

double atof(const char *s)

#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)

#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)

#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, ...)

#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

• Einerstelle: I, V, und X
• Zehnerstelle: X, L und C
• Hunderterstelle: C, D und M

#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

#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:

• char *gets(char *s)
  Die Funktion gets liest die nächste Zeile von der Standardeingabe in den Vektor s ein und setzt das Endezeichen '\0'. Das Ergebnis der Funktion ist der Zeiger auf das Zeichenfeld s, bei Fehler oder Dateiende der NULL-Zeiger.
• int puts(const char *s)
  Die Funktion puts schreibt die Zeichenkette s und einen Zeilentrenner (!) auf die Standardausgabe. Das Ergebnis der Funktion ist eine nichtnegative Zahl oder EOF bei Fehler.

#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

/*
**  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

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

• Die Zeit wird als Anzahl der seit Mitternacht des 1. Januar 1970 verstrichenen Sekunden dargestellt. Negative Werte stellen die Zeit vor diesem Datum dar. Die Zeitwerte selbst werden als Integer-Werte vom Typ time_t gespeichert. In den Prototypen der Zeitfunktionen sind die Typen time_t und clock_t als long definiert. Spätere Äderungen sind möglich (long reicht nur noch bis MItte 2038).
• Bei der zweiten Form der Darstellung werden die Zeitangaben in ihre Bestandteile (Jahr, Monat, Tag, usw.) zerlegt. Für diese Art der Darstellung verwenden die Zeitfunktionen die Struktur tm, die in time.h wie folgt definiert ist:

  struct tm
    {
    int tm_sec;     /* Sekunden nach der vollen Minute [0,59] */
    int tm_min;     /* Minuten nach der vollen Stunde  [0,59] */
    int tm_hour;    /* Stunden seit Mitternacht        [0,23] */
    int tm_mday;    /* Tag des Monats                  [1,31] */
    int tm_mon;     /* Monate seit Januar              [0,11] */
    int tm_year;    /* Jahre seit 1900                        */
    int tm_wday;    /* Wochentag (Tage seit Sonntag)   [0,6]  */
    int tm_yday;    /* Tage seit dem 1. Januar        [0,365] */  
    int tm_isdst;   /* Flag für Sommerzeit               */
    };
  

time_t time(time_t *ptr);

time_t jetzt;
jetzt = time(NULL);

time_t jetzt;
time(&jetzt);

struct tm *localtime(time_t *ptr);

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);

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);

Thu Apr 30 11:22:15 2003

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);

Spezifizierer	wird ersetzt durch:
%a	Abgekürzter Wochentagsname
%A	Voller Wochentagsname
%b	Abgekürzter Monatsname
%B	Voller Monatsname
%c	Datums- und Zeitdarstellung (zum Beispiel, Tue Apr 18 10:41:50 2000)
%d	Tag des Monats als Dezimalzahl von 01 bis 31
%H	Die Stunde als Dezimalzahl von 00 bis 23
%I	Die Stunde als Dezimalzahl von 00 bis 11
%j	Der Tag des Jahres als Dezimalzahl von 001 bis 366
%m	Der Monat als Dezimalzahl von 01 bis 12
%M	Die Minute als Dezimalzahl von 00 bis 59
%p	AM oder PM
%S	Die Sekunde als Dezimalzahl von 00 bis 59
%U	Die Woche des Jahres als Dezimalzahl von 00 bis 53. Der Sonntag wird als erster Tag der Woche betrachtet
%w	Der Wochentag als Dezimalzahl von 0 bis 6 (Sonntag = 0)
%W	Die Woche des Jahres als Dezimalzahl von 00 bis 53. Der Montag wird als erster Tag der Woche betrachtet
%x	Datumsdarstellung (zum Beispiel, 30-Jun-91)
%X	Zeitdarstellung (zum Beispiel, 10:41:50)
%y	Das Jahr, ohne Jahrhundert, als Dezimalzahl von 00 bis 99
%Y	Das Jahr, mit Jahrhundert, als Dezimalzahl
%Z	Der 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);

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

clock_t clock(void);

/* 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

Julianischer Tag

• den 28jährigen Sonnenzyklus, in dem sich (im Julianischen Kalender) die Kalenderdaten auf denselben Wochentagen wiederholen (im Gregorianischen Kalender wäre dieser Zyklus 400 Jahre lang);
• den 19jährigen Metonischen Zyklus, in dem sich die Mondphasen und Finsternisse an nahezu denselben Kalenderdaten wiederholen; und
• den 15jährigen Indiktionszyklus, der im Römischen Reich zur Steuererhebung und Volkszählung verwendet wurde und, beginnend mit dem 25.Dezember 312 n.Chr, zur fortlaufenden Datierung bis in die heutige Zeit diente.

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 

#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

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);
  }

tage_im_jahr = 365 + schaltjahr(jahr);

Wochentagsberechnung

wochentag = (Julianischer Tag + 1.5) % 7

/* 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

int day_of_year(double day, int month, int year)
  {
  return ((int) julian_day(day, month, year)
          - (int) julian_day(0.0, 1, year));
  }

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

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)

1. der Frühlingsbeginn auf den 21. März 0 Uhr festgesetzt und
2. von einem gleichmäßig auf einer Kreisbahn umlaufenden Mond ausgegangen.

/* 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);
  }

• Rosenmontag -48 Tage
• Faschinsdienstag -47 Tage
• Aschermittwoch -46 Tage
• Palmsonntag -7 Tage
• Gründonnerstag -3 Tage
• Karfreitag -2 Tage
• Christi Himmelfahrt +39 Tage
• Pfingstsonntag +49 Tage
• Fronleichnam +60 Tage

Datums- und Zeitfunktionen

• Funktionen zur Ermittlung von Zeiten und Zeitdifferenzen
• Funktionen zur Umwandlung von Zeitdarstellungen
• Funktionen zur Darstellung von Zeiten als Strings

• Prozessorzeit (processor time), ausgedrückt in Systemzeit-Perioden.
• Kalenderzeit (calendar time), gemäß dem Gregorianischen Kalender, in einer implementierungsspezifischen unstrukturierten Darstellung.
• Ortszeit (local time), die für eine spezifische Zeitzone geltende Kalenderzeit, gegebenenfalls modifiziert als Sommerzeit (daylight saving time), in einer strukturierten Darstellung.

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:

• >0 wenn die Sommerzeit in Kraft ist
• =0 wenn die Sommerzeit nicht in Kraft ist
• <0 wenn die Information nicht verfügbar ist

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

#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

     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

• ::=: "wird definiert als"
• { ... }: Was in geschweiften Klammern steht, darf beliebig oft wiederholt werden.
• [ ... ]: Was in eckigen Klammern steht, darf auch fehlen.
• |: Alternative Auswahl, z. B. darf Faktor entweder eine Zahl oder eine Ausdruck in runden Klammern sein.

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?de 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

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);

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;

X = a - f(a)*(b-a)/(f(b)-f(a))

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);

Die verbesserte Näherung X₁ berechnet sich zu

X₁ = X₀ - f(X₀)/f'X₀

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;
    /* Begrenzung der Iterationen */
    if (it > ItMax)
      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 (1);
  return 0.0;
  }

Numerische Integration

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);
  }

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)

Ax = b

Wird die k-te Gleichung nach der Unbekannten x_k aufgelöst, gilt für a_kk 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

Dieses System kann dann durch Rückwärtseinseten gel?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]

 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]

   [ 1.00  -0.61  -0.23 ]  [1.5]
   [ 0      5.12   2.84 ]  [  7]
   [ 0      2.83  10.31 ]  [4.6]

   [ 1.00  -0.61  -0.23 ]  [1.5]
   [ 0      1.00  -0.56 ]  [1.4]
   [ 0      0      8.7  ]  [8.7]

   [ 1.00  -0.61  -0.23 ]  [1.5]
   [ 0      1.00  -0.56 ]  [1.4]
   [ 0      0      1.00 ]  [1.0]

    x - 0.6ly - 0.23z = 1.5
            y - 0.56z = 1.4
                    z = 1

    z = 1

    y = 1.4 + 0.56z

#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 ]

   [ 1 -0.6  -0.2 ]  [1.5]
   [ 0 -2.8  10.3 ]  [4.6]
   [ 0  5.1  -2.8 ]  [7.3]

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.

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