 |
Programmieren in Cvon Prof. Jürgen Plate |
|
Programmieren in Cvon Prof. Jürgen Plate |
| 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)
}
char a[100]; char b[100]; char c; int n; int m;
#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);
}
#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);
}
#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++;
}
#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);
}
#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);
}
#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') );
}
#include <stdio.h>
#include <string.h>
void main (void)
{
char a[100] ="Na, wo ist denn das Zeichen?";
printf ("%s" , strrchr (a , 'i') );
}
#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]);
}
#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) );
}
#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)
/* anz Zeichen aus str ab pos l”schen */
{
int i = pos + anz;
while ((str[pos++] = str[i++]) != '\0');
}
char *strupper(char *string)
{
char *s;
if (string != NULL)
for (s = string; *s; ++s)
*s = toupper(*s);
return string;
}
char *strlower(char *string)
{
char *s;
if (string != NULL)
for (s = string; *s; ++s)
*s = tolower(*s);
return string;
}
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;
}
# 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[] )
{
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];
}
}
#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);
}
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);
}
#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);
}
#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);
}
#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);
}
#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);
}
#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");
}
#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:
#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
/*
** 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;
}
Die Zeitfunktionen von C stellen Zeitangaben auf zwei verschiedene Weisen dar.
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);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 2003Beide 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:
| 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);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 fr 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("Ausfhrungszeit mit time() = %f Sekunden.\n", dauer);
/* Gibt die Programmdauer mit clock() in Mikrosekunden an */
printf("Ausfhrungszeit mit clock() = %ld .\n", clock());
return(0);
}
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.5Das 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);
}
#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);
wochentag = (Julianischer Tag + 1.5) % 7Fur 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);
}
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));
}
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));
}
/* 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:
| 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:
| 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!) |
| 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. |
| 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:
Format-Spezifier für strftime():
|
#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);
}
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:
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 fr neg. Vorzeichen */
int bruch = FALSE; /* Merker fr 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; /* fr 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);
}
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;
}
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);
}
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.
Ü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 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)
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];
}
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)
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;
}
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];
12 07 56 32 44 44 18Wenn 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.
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.
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.
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
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.
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).
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.
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.
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.
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);
}
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 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])
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);
}
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:
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.
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;
}
| 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.
| String | Zwischenschritt | Soundex-Code |
|---|---|---|
| Stadt | stdt | 2333 |
| statt | st | 23 |
| Staat | st | 23 |
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:
#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 -< 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';
}
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;
}
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:
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=wert3In 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:
| Zeichen | Code | Zeichen | Code | Zeichen | Code | Zeichen | Code |
|---|---|---|---|---|---|---|---|
| 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:
http://.../cgi-bin/testcgi.pl?Text=Hallo+dies+ist+ein+Test&Zeichen=%25Diese URL wird beim Absenden der Anfrage auch durch den Browser angezeigt. Die Nachteile der GET-Methode sind leicht ersichtlich:
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:
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/htmlgefolgt 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);
}
/* 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 |