 |
Algorithmen & Datenstrukturen
|
|
Algorithmen & Datenstrukturen
|
Ü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;
}
UNIX und Linux stellen, wie viele andere Betriebssysteme auch, eine spezielle Funktion zur Verfügung, mit deren Hilfe man die PID eines Prozesses abfragen kann. Eine zweite Funktion erlaubt es einem Kindprozess, die PID seines Elternprozesses zu ermitteln. Beide Funktion sind in der Header-Datei unistd.h definiert:
pid_t getpid(void); pid_t getppid(void);
Die erste Funktion, getpid(), liefert die PID des Prozesses zurück, der getpid() aufgerufen hat. Die zweite Funktion, getppid(), liefert die Eltern-PID des Prozesses. Der Rückgabewert ist jeweils vom Typ pid_t, der in einer der in stdlib.h eingeschlossenen Header-Dateien als int definiert ist.
Beispiel: Die ID des aktuellen Prozesses und seines Elternprozesses ermitteln.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main(void)
{
pid_t pid;
pid = getpid();
printf ("Meine PID = %d\n", pid) ;
pid = getppid();
printf ("Meine Eltern-PID = %d\n", pid) ;
return 0;
}
Das Programm aus diesem Listing definiert eine Variable vom Typ pid_t. Die Werte, die von den Funktionen getpid() und getppid() zurückgegeben werden, werden dann ausgegeben. Wenn Sie das Programm mehrmals im gleichen Konsolenfenster ausführen, erhalten Sie jedes Mal eine andere Prozess-ID, während die ID für den Elternprozess immer die gleiche bleibt.
pid_t fork(void);Tritt kein Fehler auf, erzeugt fork() einen neuen Prozess, der mit dem aufrufenden Prozess identisch ist. Sowohl der alte als auch der neue Prozess werden danach - ab der Anweisung hinter dem fork()-Aufruf - parallel ausgeführt. Obwohl beide Prozesse das gleiche Programm ausführen, verfügen sie über eigene Kopien aller Daten und Variablen. Eine dieser Variablen ist der Rückgabewert von fork().
Beispiel: Mit Hilfe von fork() einen neuen Prozess erzeugen.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main(void)
{
pid_t pid;
int x = 22;
pid = fork();
if (pid < 0)
{
printf("Fehler: fork()-Rsultat %d.\n", pid);
exit(1);
}
if (pid == 0)
{
printf("Kind: PID = %u. Eltern-PID = %u\n",
getpid(), getppid());
printf("Kind: xalt = %d\n", x);
x = 11;
printf("Kind: xneu = %d\n", x);
sleep(2);
puts ("Kind: Beendet.");
exit(42);
}
else
{
printf("Eltern: PID = %u. Kind-PID = %u\n",
getpid(), pid);
puts("Eltern: 60 Sekunden Pause.");
sleep(60);
puts("Eltern: wieder wach.");
printf("Eltern: x = %d\n", x);
}
return 0;
}
Ausgabe:
Eltern: PID = 1535. Kind-PID = 1536 Eltern: 60 Sekunden Pause. Kind: PID = 1536. Eltern-PID = 1535 Kind: xalt = 22 Kind: xneu = 11 Kind: Beendet. Eltern: wieder wach. Eltern: x = 22
Anhand des Rückgabewertes von fork() wird festgestellt, ob ein Fehler aufgetreten ist. Sind keine Fehler aufgetreten, werden zwei Prozesse ausgeführt. Im Kindprozess ist der Wert von pid 0, im Elternprozess enthält die Variable eine Prozess-ID im Bereich zwischen 1 und 32767. Die if-Anweisung wird von beiden Prozessen ausgewertet. Der Kindprozess führt danach den Block nach dem if aus, der Elternprozess den Block nach dem else.
An der Programmausgabe können Sie erkennen, daß der Elternprozess nach dem fork()-Aufruf eine Meldung ausgibt und sich dann schlafen legt. Parallel wird der Kindprozess weiter ausgeführt. Als erstes gibt er seine eigene PID und die seines Elternprozesses aus. Als Nächstes gibt der Kindprozess den Wert der Variablen x aus, ändert den Wert und gibt ihn erneut aus. Schließlich geht auch er für 2 Sekunden Pause. Da der Elternprozess 60 Sekunden schläft, wacht der Kindprozess vor seinem Eltern auf und gibt eine Meldung aus. Dann beendet er sich und gibt den Wert 42 zurück. 60 Sekunden später erwacht der Elternprozess von seinem eigenen sleep()-Aufruf, gibt den Wert der Variablen x aus und beendet sich ebenfalls.
... jpl 1714 0.0 0.0 0 0 pts/5 Z Jan27 0:00 [kind <defunct>] ...Der Kind-Prozess wird als erloschen (defunct) gemeldet. In der STAT-Spalte dieses Prozesses steht ein Z, was bedeutet, daß es sich um einen so genannten "Zombie"-Prozess handelt.
Prozesse verwenden zum Beenden die return-Anweisung oder rufen die Funktion exit() mit einem Wert auf, der an das Betriebssystem zurückgeliefert wird. Das Betriebssystem lässt den Prozess so lange in seiner Prozesstabelle eingetragen, bis entweder der Elternprozess des Prozesses den zurückgelieferten Wert liest oder der Elternprozess selbst beendet wird. Ein Zombie-Prozess ist in diesem Sinne ein Prozess, der zwar beendet wurde, dessen Elternprozess den Exit-Wert des Kindes aber noch nicht gelesen hat. Erst wenn der Elternprozess beendet wird, wird auch der Zombie-Prozess aus der Prozesstabelle des Betriebssystems entfernt.
Es gibt mehrere Wege, die Entstehung von Zombie-Prozessen zu verhindern. Am häufigsten wird die Systemfunktion wait() verwendet (Header-Datei sys/wait.h):
pid_t wait(int *status);Diese Funktion hat eine int-Variablenparameter und liefert einen Wert vom Typ pid_t zurück. Wenn die Funktion aufgerufen wird, hält sie die Ausführung des Elternprozesses so lange an, bis ein Kindprozess beendet wird. Tritt dieser Fall ein oder liegt ein Kindprozess als Zombie-Prozess vor, liefert wait() die Prozess-ID des Kindes zurück und kopiert den Exit-Wert des Kindprozesses in die status-Variable. Wenn Sie an dem Rückgabewert des Kindprozesses nicht interessiert sind, übergeben wait() den Wert NULL. Gibt es keinen Kindprozess, liefert wait() den Wert -1 zurück.
Beispiel: Mit wait() Zombie-Prozesse verhindern.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main(void)
{
pid_t pid;
int status;
pid = fork();
if (pid < 0)
{
printf("Fehler: fork()-Rsultat %d.\n", pid);
exit(1);
}
if (pid == 0)
{
printf("Kind: PID = %u. Eltern-PID = %u\n",
getpid(), getppid());
sleep(1);
puts ("Kind: Beendet.");
exit(42);
}
else
{
printf("Eltern: PID = %u. Kind-PID = %u\n",
getpid(), pid);
puts("Eltern: 10 Sekunden Pause.");
sleep(10);
puts("Eltern: wieder wach.")
pid = wait(&status);
printf("Eltern: Kind mit PID %u ", pid);
if (WIFEXITED(status) != 0)
printf("wurde mit Status %d beendet\n",WEXITSTATUS(status));
else
printf("wurde mit Fehler beendet.\n");
}
return 0;
}
Dieses Listing entspricht weitgehend dem vorhergehenden Programm. Der Hauptunterschied liegt darin, daß der Elternprozess nach dem Erwachen die Funktion wait() aufruft. Da der Kindprozess schon vorher beendet wurde, kehrt wait() sofort nach dem Aufruf zurück und setzt die Variable pid auf die Prozess-ID des beendeten Kindprozesses. Des Weiteren kopiert die Funktion den Exit-Wert des Prozesses in die Variable status, deren Adresse der Funktion als Argument übergeben wurde. Der Elternprozess gibt die Prozess-ID des Kindes aus und verwendet die Makros, WIFEXITED() and WEXITSTATUS(), die in sys/wait.h definiert sind, um den Rückgabestatus des Kindprozesses abzufragen und ebenfalls auszugeben. Auf der Manpage zur wait()-Funktion können Sie nachlesen, daß diese Makros dafür sorgen, daß nur 8-Bit-Werte (1 bis 255) als Exit-Status zurückgeliefert werden.
Die wait()-Funktion ist offensichtlich recht nützlich, wenn man weiß, daß der Kindprozess bereits beendet wurde. Sollte dies nicht der Fall sein, hält die wait()-Funktion den Elternprozess so lange an, bis der Kindprozess beendet wird. Wenn dieses Verhalten nicht gewünscht, kann man die waitpid()-Funktion verwenden, die in der Header-Datei sys/wait.h definiert ist:
pid_t waitpid(pid_t pid, int *status, int options);Mit waitpid() können Sie auf einen bestimmten Prozess (spezifiziert durch seine Prozess-ID) oder einen beliebigen Kindprozess (falls für pid der Wert -1 übergeben wird) warten. Der Exit-Status des Kindprozesses wird im zweiten Argument zurückgeliefert. Dem letzten Parameter, options, kann man eine der Konstanten WNOHANG, WUNTRACED oder 0 (waitpid() verhält sich dann wie wait()) übergeben. Die erste dieser Konstanten ist die interessanteste, da sie dafür sorgt, daß waitpid() sofort mit einem Wert von 0 - einer ungültigen Prozess-ID - zurückkehrt, wenn kein Kindprozess beendet wurde. Der Elternprozess kann dann mit der Ausführung fortfahren und waitpid() zu einem späteren Zeitpunkt wieder aufrufen.
Beispiel: Mit waitpid() Zombie-Prozesse verhindern.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
int main(void)
{
pid_t pid;
int status;
pid = fork();
if (pid < 0)
{
printf("Fehler: fork()-Rsultat %d.\n", pid);
exit(1);
}
if (pid == 0)
{
printf("Kind: PID = %u. Eltern-PID = %u\n",
getpid(), getppid());
sleep(10);
puts ("Kind: Beendet.");
exit(66);
}
else
{
printf("Eltern: PID = %u. Kind-PID = %u\n",
getpid(), pid);
while ((pid = waitpid (-1, &status, WNOHANG)) == 0)
{
printf("Eltern: Kein Kind beendet.");
puts(" 1 Sekunde Pause.");
sleep(1);
}
printf("Eltern: Kind mit PID %u ", pid);
if (WIFEXITED(status) != 0)
printf("wurde mit Status %d beendet\n", WEXITSTATUS(status));
else
printf("wurde mit Fehler beendet.\n");
}
return 0;
}
int execl( const char *path, const char *arg, ...);Diese Funktion kehrt nur dann zurück, wenn ein Fehler auftritt. Andernfalls wird der aufrufende Prozess vollständig durch den neuen Prozess ersetzt. Den Programmnamen des Prozesses, der den aufrufenden Prozess ersetzen soll, übergibt man im Argument zu path, etwaige Kommandozeile-Parameter werden danach übergeben. Im Unterschied zu Funktionen wie printf() ist execl() darauf angewiesen, daß man als letztes Argument einen NULL-Zeiger übergibt, der das Ende der Argumentenliste anzeigt.
Der zweite an execl() übergebene Parameter ist nicht der erste Kommandozeilen-Parameter, der an das aufzurufende Programm (spezifiziert in path) übergeben wird. Vielmehr ist er der Name, unter dem der neue Prozess in der vom ps-Befehl erzeugten Prozessliste aufgeführt wird. Der erste Parameter, der an das (in path spezifizierte) Programm übergeben wird, ist also tatsächlich der dritte Parameter von execl(). Wenn Sie beispielsweise das Programm /bin/ls mit dem Parameter -lisa aufrufen wollen und möchten, daß das Programm in der Prozessliste unter dem Namen "verz" aufgerufen wird, würden Sie execl() wie folgt aufrufen:
execl("/bin/ls", "verz", "-lisa", NULL);
Dieser Aufruf würde den aktuellen Prozess durch einen Prozess ersetzen, der dem
Aufruf von /bin/ls -lisa von der Befehlszeile entspricht.
Beispiel: Mit execl() einen Prozess durch einen anderen ersetzen.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
int main(void)
{
pid_t pid ;
pid = getpid();
printf ("Meine PID = %u\n", pid);
execl ("/bin/ps", "ps-proggie", "u", NULL);
puts("Ein Fehler ist aufgetreten.");
return 0;
}
Beachten Sie, daß der ursprüngliche Prozess die gleiche Prozess-ID trägt wie später der neue Prozess, der ihn ersetzte.
execl() ist nicht die einzige Funktion dieser Art, es gibt eine ganze Familie mit leicht unterschiedlicher Arbeitsweise.
system() erzeugt einen eigenen Prozeß. Dieser führt das Kommando aus, was aber keinen Effekt für den aufrufenden Prozeß hat.
| Name | Wert | Funktion |
|---|---|---|
| SIGHUP | 1 | Logoff |
| SIGINT | 2 | Benutzer-Interrupt (ausgelöst durch [Strg]+[C]) |
| SIGQUIT | 3 | Benutzeraufforderung zum Beenden (ausgelöst durch [Strg]+[\]) |
| SIGFPE | 8 | Fließkommafehler, beispielsweise Null-Division |
| SIGKILL | 9 | Prozess killen |
| SIGUSR1 | 10 | Benutzerdefiniertes Signal |
| SIGSEGV | 11 | Prozess hat versucht, auf Speicher zuzugreifen, der ihm nicht zugewiesen war |
| SIGUSR2 | 12 | Weiteres benutzerdefiniertes Signal |
| SIGALRM | 14 | Timer (Zeitgeber), der mit der Funktion alarm() gesetzt wurde, ist abgelaufen |
| SIGTERM | 15 | Aufforderung zum Beenden |
| SIGCHLD | 17 | Kindprozess wird aufgefordert, sich zu beenden |
| SIGCONT | 18 | Nach einem SIGSTOP- oder SIGTSTP-Signal fortfahren |
| SIGSTOP | 19 | Den Prozess anhalten |
| SIGTSTP | 20 | Prozess suspendiert, ausgelöst durch [Strg)+[Z]. |
Abgesehen von SIGSTOP und SIGKILL kann man das Standardverhalten jedes Signals durch Installation einer Signal-Bearbeitungsroutine anpassen. Eine Signal- Bearbeitungsroutine ist eine Funktion, die vom Programmierer implementiert wurde und die jedes Mal aufgerufen wird, wenn der Prozess ein entsprechendes Signal empfängt. Abgesehen von SIGSTOP und SIGKILL können Sie für jedes Signal aus eine eigene Signal-Bearbeitungsroutine einrichten. Eine Funktion, die als Signal-Bearbeitungsroutine fungieren soll, muss einen einzigen Parameter vom Typ int und einen void-Rückgabetyp definieren. Wenn ein Prozess ein Signal empfängt, wird die Signal-Bearbeitungsroutine mit der Kennnummer des Signals als Argument aufgerufen.
Um Signale abfangen und mit einer geeigneten Signal-Bearbeitungsroutine bearbeiten zu können, muss der Programmierer dem Betriebssystem mitteilen, daß es bei jedem Auftreten des betreffenden Signals für das Programm die zugehörige Signal- Bearbeitungsroutine aufrufen soll. Zwei Funktionen gibt es, mit denen man unter Unix eine Signal-Bearbeitungsroutine verändern oder untersuchen kann: signal() und sigaction(), die beide in der Header-Datei signal.h definiert sind. Die zweite Funktion, sigaction(), ist die aktuellere und wird auch häufiger eingesetzt. Sie ist wie folgt definiert:
int sigaction(int signum, const struct sigaction *act,
struct sigaction *oldact);
Im Erfolgsfall liefert die Funktion 0 zurück, im Fehlerfall -1. Der erste Parameter von sigaction() ist die Nummer des Signals, dessen Verhalten Sie verändern oder untersuchen wollen. Man übergibt dem Parameter aber nicht die tatsächliche Signal-Nummer, sondern die zugehörige symbolische Konstante - also beispielsweise SIGINT statt der Zahl 2. Der zweite und der dritte Parameter sind Zeiger auf eine sigaction-Struktur. Diese Struktur ist in signal.h definiert:
struct sigaction
{
void (*sa_handler)(int);
sigset_t sa_mask;
int sa_flags;
void (*sa_restorer)(void);
}
Indem Sie dem zweiten Parameter der sigaction()-Funktion einen Zeiger auf eine korrekt eingerichtete sigaction-Struktur übergeben, können Sie das Verhalten für das zugehörige Signal verändern. Indem Sie einen Zeiger auf eine solche Struktur als dritten Parameter übergeben, fordern Sie die sigaction()-Funktion auf, die Daten, die das aktuelle Verhalten zu dem Signal bestimmen, in die übergebene sigaction-Struktur zu kopieren. Beiden Parametern kann man auch NULL- Zeiger übergeben.
Es ist also möglich, das aktuelle Verhalten zu ändern, sowie das aktuelle Verhalten zu untersuchen, ohne es zu ändern, das aktuelle Verhalten zu untersuchen und vor dem Ändern abzuspeichern, so daß es später wieder hergestellt werden kann.
int sigemptyset(sigset_t *set);Das letzte Element der Struktur, sa_restorer, wird heute nicht mehr verwendet.
Beispiel: Ein einfaches Beispiel zur Behandlung von Signalen.
#include <stdio.h>
#include <unistd.h>
#include <signal.h>
static int BEENDEN = 0;
void sig_bearbeiter(int sig)
{
printf("Signal %d empfangen. Programm wird beendet.\n", sig);
BEENDEN = 1;
}
int main(void)
{
struct sigaction sig_struct;
sig_struct.sa_handler = sig_bearbeiter;
sigemptyset(&sig_struct.sa_mask);
sig_struct.sa_flags = 0;
if (sigaction(SIGINT,&sig_struct,NULL) != 0)
{
puts ("Fehler beim Aufruf von sigaction!") ;
exit (1);
}
puts("Programm gestartet, beenden mit [Strg]+[C].");
while (BEENDEN == 0)
{
puts("Programm läuft.");
sleep(1);
}
puts("Erstmal aufraeumen.");
sleep(5);
puts("Fertig!");
return 0;
}
Wurde die Signal-Bearbeitungsroutine korrekt eingerichtet, gibt das Programm in
eine Meldung aus und tritt in die Schleife des Hauptprogramms ein. Solange die
Variable BEENDEN gleich 0 ist, gibt die
while-Schleife die Meldung "Programm läuft." aus und
legt sich jeweils für eine Sekunde schlafen.
Wenn die Signal-Bearbeitungsroutine sig_bearbeiter() aufgerufen wird, gibt sie die Meldung "Signal 2 empfangen. Programm wird beendet." auf den Bildschirm aus und setzt danach den Wert der statischen Variablen BEENDEN auf 1. Nur das führt zum Beeenden und nicht das Betätigen von [Ctrl]+[C]. Da Programm könnte auch einfach weiterlaufen und die Benuterunterbrechung ignorieren. Hier die Ausgabe eines Beispiel-Laufs:
Beenden mit [Strg]+[C]. Programm läuft. Programm läuft. Programm läuft. Signal 2 empfangen. Programm wird beendet. Erstmal aufraeumen. Fertig!
| Mehr dazu und auch zur Prozess-Kommunikation bietet das Kapitel über Prozesse bei der Internet-Technologie. |
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 |