 |
Manchmal ist es wichtig, das erste Vorkommen eines Schlüssel zu
finden (also 4). Außerdem kann es vorkommen, daß ein Schlüssel gar
nicht gefunden wird. Die vorgestellten Funktionen signalisieren dies, indem sie den
Index -1 zurückgeben.
Lineare Suche
Wenn man nichts über die Anordnung der Komponenten im Array weiß,
bleibt einem nichts anderes übrig, als sie beginnend
bei der ersten Komponente linear zu durchsuchen, bis man entweder
die gesuchte Komponente gefunden hat, oder bis das Ende des Arrays erreicht wurde.
Im statistischen Mittel werden bei N Tabelleineinträgen N/2 Suchschritte
benötigt, im günstigsten Fall nur einer und im schlechtsten Fall N
Schritte.
Um nicht jedesmal prüfen zu müssen, ob das Ende des Arrays schon erreicht
ist, wenden wir einen kleinen Trick an: Am Ende des Arrays fügen wir noch ein
Element an, das genau dem gesuchten Wert entspricht - auf diese Weise wird
dann jedesmal ein Wert gefunden.
Natürlich muß anschließend geprüft werden,
ob der gefundene Wert nun ein "echter" Treffer oder die eigene Endemarke war.
Diese Endemarke wird "Sentinel" genannt. Die Konstante Tablesize
muß entsprechend großzügig gewählt werden.
Die Funktion LinSearch hat als Parameter den Suchschlüssel und
gibt den gefundenen Index zurück:
int LinSearch(int Key, int Table[])
{
int Index;
Table[TableSize] := Key;
Index := 0;
while (Table[Index] != Key)
Index++;
if (Index = TableSize)
Index := -1;
return(Index);
}
Wie man sieht, wird im ersten Schritt der Sentinel gesetzt, dann wird der
Index auf 0 initialisiert und dann so lange erhöht, bis der Key gefunden
wurde. Zum Schluß wird noch geprüft, ob der Index außerhalb
des gültigen Bereichs liegt. In diesem Fall wird der Index auf -1
korrigiert, denn das ist der Wert für "nicht gefunden". Daß der
Algorithmus stets das erste Vorkommen des Keys findet, ist offensichtlich.
Binäre Suche
Um die Suche zu beschleunigen, müssen die Elemente in der Tabelle sortiert
vorliegen. Dies kann man entweder durch eines der später beschriebenen
Sortierverfahren erreichen, oder indem man neue Elemente gleich an der richtigen
Stelle einfügt. Beides benötigt zusätzlichen Aufwand, spart aber
Zeit beim Suchen. Wie nutzt man nun die Ordnung in der Tabelle aus?
Man sucht das mittlere Element der Tabelle und prüft, ob es größer
oder kleiner als dder Key ist. Ist es größer oder gleich, braucht man
nur noch in der unteren Hälfte der Tabelle zu suchen, ist es kleiner, sucht man
nur noch in der oberen Hälfte. Irgendwann ist die Größe des
Suchintervalls auf 1 geschrumpft, und dann hat man das gesuchte Element gefunden,
oder es ist nicht vorhanden. Die Zahl der Suchschritte reduziert sich bei N
Tabelleneinträgen auf ln(N) (ln: Logarithmus zur Basis 2).
Der folg}e Algorithmus benutzt die Variablen L(inks) und R(echts),
um den Suchbereich zu definieren, sowie Middle, um die Mitte zu markieren.
Soll oberhalb der Mitte weitergesucht werden, wird L zu Middle + 1,
wird im unteren Teil weitergesucht, so ergibt sich R = Middle.
int BinSearch (int Key, int Table[])
{
int L, R, Middle;
L := 1;
R := TableSize + 1;
while (L < R)
{
Middle := (L + R) / 2;
if (Table[Middle] < Key) L := Middle + 1;
else R := Middle;
}
if (Table[R] == Key) return(R);
else return(-1);
}
Wenn die Funktion das gesuchte Element früher als erwartet findet (z. B. wenn
es genau in der Mitte liegt), könnte sie eigentlich abbrechen. Es ist dann nicht
mehr garantiert, daß man das erste Vorkommen von Key findet.
Sortieren von Tabellen
Das Sortieren ist eines der wichtigsten Gebiete der Datenverarbeitung.
Etwa 25% aller Rechenzeit im kommerziellen Bereich wird auf das Sortieren
von Daten verwendent. An Beispielen zum Sortieren mangelt es nicht:
- Statistiken
- Telefonbücher, Wörterbücher
- Listen, ...
Die Problemstellung: Gegeben ist ein Array mit Komponenten, die nach ihrem Schlüssel
sortiert werden können, über deren momentane Anordnung jedoch nichts bekannt
ist (das heißt auch, daß sie theoretisch schon sortiert sein oder in der
umgekehrten Reihenfolge vorliegen könnten). Der Sortieralgorithmus soll die
Elemente in die richtige Reihenfolge bringen.
Definition:
"Unter Sortieren versteht man allgemein den Prozess des Anordnens einer
gegebenen Menge von Objekten in einer bestimmten Ordnung."
Das Sortieren ist ebenfalls einer der Grundalgorithmen in der Informatik
insbesondere für die effiziente Speicherung von Informationen
hinsichtlich der Auswertung bzw. Suche. Bei den Sortierverfahren
unterscheidet man die
- interne Sortierung: als Bearbeitung von Listen im
Hauptspeicher,
- externe Sortierung: als Bearbeitung von Listen, die
sich auch auf externen Speichermedien (Magnetband, Festplatte)
befinden können.
Bubblesort
Bubblesort ist einer der einfachsten Sortieralgorithmen. Im ersten Durchgang wird das
Array vom Ende bis zum Anfang bearbeitet und bei jedem Schritt die aktuelle Komponente
mit der nächsten verglichen. Ist die untere Komponente kleiner als die obere, werden
die beiden vertauscht. Die größere Komponente behält also ihren Platz
und die jeweils kleinere wandert weiter nach oben.
Im nächsten Durchlauf wird dann die zweitkleinste Komponente gesucht und nach
oben durchgereicht. Logischerweise muß dieser Durchlauf nicht ganz bis zum
Anfang gehen, sondern nur bis Index 1. der dritte Durchlauf läuft nur noch bis
Index 2, usw. - bis das Verfahren abgeschlossen ist. Der Name "Bubblesort" kommt
daher, daß die kleineren Komponente aufsteigen wie Blasen in einer Flüssigkeit.
void Bubblesort (int Table[])
{
int x;
int Run, Index;
for (Run = 1; Run < TableSize; Run++)
{
for (Index = TableSize; Index >= Run; Index--)
{
if (Table[Index] < Table[Index - 1])
{
x := Table[Index];
Table[Index] := Table[Index - 1];
Table[Index - 1] := x;
}
}
}
}
Deutlich zu erkennen ist der Vertauschungsvorgang, bei dem die
"untere" Komponente zunächst in der Variablen x zwischengespeichert
wird, dann den Wert der "oberen" zugewiesen bekommt und anschließend
x im "oberen" Index gespeichert wird.
Bubblesort genießt keinen besonders guten Ruf, weil es sehr langsam ist.
Trotzdem ist es häufig anzutreffen, nicht zuletzt wegen seines hohen
Bekanntheitsgrades.
Sortieren durch Auswählen
Selectionsort ist ebenfalls ein sehr einfacher Algorithmus. Das Prinzip dahinter
besteht darin, daß das Array von vorn nach hinten durchlaufen wird, und
für jeden Platz die passende Komponente herausgesucht wird.
Man beginnt mit Table[0] und durchläft dann das Array.Dabei
merkt sich die Funktion das kleinste Element. Dieses vertauscht sie dann mit der ersten
Komponente, so daß nun die kleinste Komponente ganz vorne steht. Im nächsten
Durchgang beginnt man bei Table[1] und durchsucht wieder das Array nach
der kleinsten Komponente, wobei natürlich Table[0] unberücksichtigt
bleibt. Im dritten Durchgang bleiben dann die ersten beiden Tabellenelemente
unberührt usw.
void SelectionSort (int Table[])
{
int Komponente, Smallest;
int Index, Smallidx;
for (Komponente = 0; Komponente < TableSize; Komponente++)
{
Smallidx := Komponente;
Smallest := Table[Smallidx];
for (Index = Komponente + 1; Index <= TableSize; Index++)
{
if (Table[Index] < Smallest)
{
Smallest := Table[Index];
Smallidx := Index;
}
}
if (Smallidx != Komponente)
{
Table[Smallidx] := Table[Komponente];
Table[Komponente] := Smallest;
}
}
}
In der Variablen Smallest merkt sich der Algorithmus den Wert die bislang
kleinste Komponente, in Smallidx ihre Positeon. Beide werden zunächst
auf die Komponente initialisiert, deren Positeon 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 Positeon gefunden wurde. Selectionsort ist schneller als
Bubblesort (ca. Faktor 2).
Sortieren durch Einfügen
Es wird angenommen, daß ein Teil am Anfang des Arrays schon sortiert ist (zu
Beginn ist dieser Teil natürlich 0 Komponenten groß!). Nun wird die erste
Komponente aus dem unsortierten Teil genommen und an der richtigen Stelle in den
sortierten Teil eingefügt. Der sortierte Teil wächst dabei natürlich
um eine Komponente, bleibt aber sortiert, wohingegen der unsortierte Teil um eine
Komponente schrumpft.
Der Algorithmus durchläft die Arraykomponenten von Anfang bis Ende. Für jede
Komponente geschieht nun folgendes: Von seiner Positeon 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 Positeon eine freie Array-Komponente.
Diese "Lücke" wird dann an der richtigen Positeon mit dem einzufügenden
Wert gefüllt. Auf diese Weise verbindet der Algorithmus die Suche nach der
richtigen Positeon 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
Positeon 0.
Shellsort
Shellsort ist ein Kompromiß aus Einfachheit und Geschwindigkeit. Das Array
wird zunächst in mehrere Gruppen aufgeteilt, zwischen deren Mitgliedern der
gleiche Abstand besteht. Angenommen, man verwendet den Abstand 3, dann gehören
die Komponenten 1, 4, 7, ... in eine Gruppe, genauso 2, 5, 8, ..., 3, 6, 9, ... usw.
Diese Gruppen werden nun einzeln sortiert, dann wird der Abstand verringert
und die Vorgehensweise wiederholt. Das macht man so lange, bis der Abstand 1
ist, so daß im letzten Schritt gar keine Unterteilung mehr stattfindet.
Zum Sortieren der Gruppen wird ein Bubblesort-ähnlicher Algorithmus verwendet.
Für jeden Schritt gibt die Variable Gap den Abstand zwischen den
Komponenten an. Die Variable Index läuft dann von Gap + 1
bis zum Ende der Tabelle durch. Für jeden Wert von Index wird ein
Sortierlauf gestartet, mit Index als oberer Grenze. Welche Gruppe dabei
sortiert wird, hängt also von Index ab. Die Variable j wird auf die
nächstkleinere Komponente der Gruppe initialisiert (also Index - Gap),
dann wird es mit der nächsthöheren verglichen und gegebenenfalls vertauscht.
Dann geht j wieder einen Schritt nach unten (Schrittweite Gap),
usw., bis j kleiner 0 ist.
Wenn Index auf die n-te Komponente einer Gruppe verweist, sind alle Komponenten
(dieser Gruppe) unterhalb von Index sortiert. Ist Index bis zum
Ende des Arrays durchlaufen, sind auch alle Gruppen sortiert.
void ShellSort (int Table[])
{
int x;
int Gap, Index, j;
Gap := TableSize / 2;
while (Gap > 0) do
{
for (Index = Gap + 1; Index <= TableSize; Index++)
{
j := Index - Gap;
while (j > 0)
{
if (Table[j] <= Table[j + Gap])
j := 0;
else
{
x := Table[j];
Table[j] := Table[j + Gap];
Table[j + Gap] := x;
}
j = J - Gap;
}
}
Gap := Gap / 2;
}
}
Shellsort zählt zu den schnelleren Algorithmen. Leider kommt es mit sehr
großen Arrays überhaupt nicht zurecht.
Quicksort
Quicksort ist in den meisten Fällen der schnellste Algorithmus. Man greift sich
eine beliebige Komponente des Arrays heraus - beispielsweise die mittlere - und teilt
das Array in zwei Gruppen:
Eine mit den Komponenten, die größer sind als die herausgegriffene, und eine
mit den kleineren (oder gleichen). Diese beiden Hälften übergibt man
wieder an Quicksort. Es handelt sich also um eine rekursive Funktion. Irgendwann
sind die Arrays nur noch eine Komponente groß und damit sortiert.
Um nicht bei jedem Aufruf immer Arrays erzeugen zu müssen, arbeitet Quicksort mit
linker und rechter Grenze. Dafür müssen dann natürlich alle Komponenten, die
größer sind als die herausgegriffene, in den unteren Teil verschoben werden,
die anderen in den oberen Teil. Darin besteht die eigentliche Arbeit von Quicksort:
void QSort (int Links, int Rechts, int Table[])
{
int i, j;
int x, w;
i := Links;
j := Rechts;
x := Table[(Links + Rechts) / 2];
do
{
while (Table[i] < x) i++;
while (Table[j] > x) j--;
if (i <= j)
{ /* Element vertauschen */
w := Table[i];
Table[i] := Table[j];
Table[j] := w;
i++; j--;
}
}
while (i <= j);
if (Links < j) QSort (Links, j, Table);
if (Rechts > i) QSort (i,Rechts, Table);
}
Quicksort ist, wie eingangs gesagt, in der Regel das schnellste Suchverfahren. Im
schlimmsten Fall jedoch, wenn das Array bereits sortiert ist, fällt Quicksort
leider auf das Niveau von Bubblesort herab.
Praktischer Einsatz von Sortierverfahren
In den vorangegangenen Abschnitten befanden sich die Algorithmen immer in einer
sehr "sterilen" Umgebung, um sie von allem Beiwerk, das nicht unmittelbar zum
Algorithmus gehört, zu befreien. In der Praxis hat man es mit unterschiedlichsten
Bedingungen zu tun: Mal möchte man Strings sortieren, mal Zahlen, mal eine
komplexe Struktur. Auch wünscht man sich manchmal, die Sortierreihenfolge
(auf- oder absteigend) angeben zu können. Das Sortierverfahren muß zudem
unbekannte Datentypen vergleichen können. Es muß also eine Funktion
existieren, die für zwei Elementen des Arrays festlegt, welches von beiden
größer ist.
Erweitern wir Quicksort zuerst auf das Sortieren von Strings. Da die Eingabestrings
unterschiedlich lang sind, wird durch Speicherung von Strings fester Länge sehr
viel Speicherplatz verschwendet. Für 1000 Zeichenketten mit maximal
150 Zeichen Länge müßte man definieren:
char feld[1000][150].
Das Feld würde 1000*150 = 150'000 Bytes belegen unabhängig von der
wirklichen Länge der eingelesenen Zeilen. Daher sollte man für die
Speicherung und Sortierung ein Feld von Zeigern auf Strings verwenden und den
Platz für die aktuellen Zeile jeweils ihrer Länge entsprechend mit
malloc reservieren. Das sieht dann etwa, so aus:
#define MAX 1000 /* Maximalzahl Feldelemente */
...
char *feld[MAX]; /* Feld mit String-Zeigern */
char *ptr; /* Zeiger zum Prüfen auf EOF */
char puffer[151]; /* Puffer für akt. String */
...
ptr = gets(puffer); /* String einlesen */
if (ptr != NULL) /* EOF,wenn (ptr rr NULL) */
{ /* Platz reservieren */
feld[i] = (char *) malloc(strlen(puffer) + 1)
/* Platz für den String einschl. des Zeichens '\0' am Ende */
strcpy(feld[i],puffer); /* String in feld kopieren */
}
...
Auch bei Sortieren ist das Zeigerfeld günstiger, denn beim Vertauschen
müssen nur Zeiger und nicht die ganzen Strings bewegt werden.
Diesmal wurde nicht nur Quicksort definiert, sondern auch das ganze
Tetsprogramm:
#include <stdio.h>
#include <string.h>
#define MAX 1000 /* Maximalzahl Feldelemente */
#define TRUE 1 /* Wahrheitswerte */
#define FALSE 0
/* globale Variable */
/* ---------------- */
char *string_feld[MAX]; /* Feld mit String-Zeigern */
int count; /* Anzahl der eingeg. Strings */
int aufsteigend; /* aufsteigend/absteigend */
/* Funktions-Prototypen */
/* -------------------- */
int einlesen(char *feld[]); /* Eingabefunktion */
void ausgabe(int anzahl,char *feld[]); /* Ausgabefunktion */
void quicksort(char *feld[],int auf, int links, int rechts);
/* Quicksort-Routine */
/* Hauptprogramm */
/* ------------- */
main(int argc,char *argv[])
{
aufsteigend = TRUE; /* Voreinstellung */
if (argc == 2) /* Argument pruefen */
aufsteigend = (strcmp(argv[1],"auf") == 0);
count = einlesen(string_feld);
quicksort(string_feld,aufsteigend,0,count-1);
ausgabe(count,string_feld);
}
/* Funktions-Definitionen */
/* ---------------------- */
int einlesen(char *feld[])
/* Liest Strings auf die Variable feld ein, liefert Anzahl zurueck */
{
int i; /* Zaehler fuer Strings */
char *ptr; /* Zeiger zum Pruefen auf EOF */
char puffer[151]; /* Puffer fuer akt. String */
i = 0;
do
{
ptr = fgets(puffer,150,stdin); /* String einlesen */
if (ptr != NULL) /* EOF == (ptr == NULL) */
{ /* Platz reservieren */
feld[i] = (char *) malloc(strlen(puffer) + 1);
/* einschl. '\0' am Ende */
strcpy(feld[i],puffer); /* String in feld kopieren */
i++; /* Zaehler erhoehen */
}
}
while (ptr != NULL); /* lesen bis EOF */
return(i);
}
void ausgabe(int anzahl,char *feld[])
/* Ausgabe der Strings in feld, der Parameter gbt die Anzahl an */
{
int i;
puts("\n"); /* Leerzeile */
for (i=0; i<anzahl; i++)
puts(feld[i]); /* haengt \n automatisch an */
}
void quicksort(char *feld[],int auf, int links, int rechts)
/* Quicksort-Routine: feld wird im Bereich [lins,rechts] sortiert */
{
int i, j; /* Hilfsvariable */
char *x, *y; /* Hilfszeiger fuer Tausch */
i = links; j = rechts;
x = feld[(i + j)/2]; /* mittleres Element */
do
{ /* partitionieren */
if(auf) /* aufsteigend sortieren */
{
while(strcmp(feld[i],x) < 0 && i < rechts) i++;
while(strcmp(feld[j],x) > 0 && j > links) j--;
}
else /* absteigend sortieren */
{
while(strcmp(feld[i],x) > 0 && i < rechts) i++;
while(strcmp(feld[j],x) < 0 && j > links) j--;
}
if (i <= j)
{ /* Zeiger-Tausch! */
y = feld[i]; /* Die Strings bleiben an der */
feld[i] = feld[j]; /* urspruenglichen Positeon */
feld[j] = y;
i++; j--;
}
}
while (i <= j);
if (links < j) quicksort(feld,auf,links,j);
if (rechts > i) quicksort(feld,auf,i,rechts);
}
Suchen mit bsearch
Die Bibliotheksfunktion bsearch() führt eine binäre Suche in
einem Datenarray durch, wobei sie nach einem Array-Element Ausschau hält, das
mit einem gesuchten Wert (dem Schlüssel oder "key") übereinstimmt. Um
bsearch() anwenden zu können, muß das Array in aufsteigender
Reihenfolge sortiert sein. Außerdem muß das Programm
die Vergleichsfunktion bereitstellen, die bsearch() benötigt, um
festzustellen, ob ein Datenelement größer, kleiner oder gleich einem anderen
Element ist. Der Prototyp von bsearch() steht in stdlib.h und lautet:
void *bsearch(const void *key, const void *base, size_t num, size_t size,
int (*cmp)(void *elem1, void *elem2));
Dieser Prototyp ist ziemlich komplex. Deshalb sollten Sie ihn sorgfältig studieren.
Das Argument key ist ein Zeiger auf das gesuchte Datenelement und base
ein Zeiger auf das erste Element in dem zu durchsuchenden Array. Beide werden mit dem
Typ void deklariert, so daß sie auf irgendein beliebiges C-Datenobjekt
zeigen können.
Das Argument num ist die Anzahl der Arraykomponenten und size die
Größe einer Komponente in Byte. Üblicherweise wird der
sizeof()-Operator verwendet, um die Werte für num und size
anzugeben.
cmp ist ein Zeiger auf die Vergleichsfunktion. Dabei kann es sich
um eine vom Programmierer aufgesetzte Funktion handeln, oder - wenn Stringdaten
durchsucht werden - um die Bibliotheksfunktion strcmp(). Die Vergleichsfunktion
muß die folgenden zwei Kriterien erfüllen:
- Sie muß Zeiger auf zwei Datenelemente übernehmen.
- Sie muß einen der folgenden int-Werte zurückgeben:
- < 0: Parameter 1 ist kleiner als Parameter 2.
- 0: Parameter 1 ist gleich Parameter 2.
- > 0: Parameter 1 ist größer als Parameter 2.
Der Rückgabewert von bsearch() ist ein Zeiger vom Typ void. Die
Funktion gibt einen Zeiger auf die erste Array-Komponente zurück, die dem
Schlüssel entspricht, oder NULL, wenn keine Übereinstimmung
gefunden wird. Der Typ des zurückgegebenen Zeigers muß entsprechend
umgewandelt werden, bevor der Zeiger verwendet werden kann.
Der sizeof()-Operator kann die num- und size-Argumente wie
folgt bereitstellen. Wenn array[] das zu durchsuchende Array ist, dann liefert
die Anweisung
sizeof(array[0]);
den Wert für size, das heißt die Größe eines
Array-Elements in Byte. Da der Ausdruck sizeof(array) die Größe
eines ganzen Arrays in Byte zurückliefert, können Sie mit der folgenden
Anweisung den Wert von num, der Anzahl der Elemente im Array, ermitteln:
sizeof(array)/sizeof(array[0])
Sortieren mit qsort
Die Bibliotheksfunktion qsort() ist eine Implementierung des Quicksort-Algorithmus, der von C.A.R. Hoare erfunden wurde. Diese Funktion sortiert ein Array in eine
vorgegebene Reihenfolge. Normalerweise wird aufsteigend sortiert, aber qsort()
kann auch absteigend sortieren. Der Prototyp dieser Funktion ist in stdlib.h
definiert und lautet:
void qsort(void *base, size_t num, size_t size,
int (*cmp)(void *elem1, void *elem2));
Das Argument base zeigt auf das erste Element in dem Array, num ist die
Anzahl der Komponenten im Array und size die Größe einer
Array-Komponente in Byte. Das Argument cmp ist eine Zeiger auf eine
Vergleichsfunktion. Für diese Vergleichsfunktion gelten die gleichen Regeln wie
bei bsearch(). Oft verwendet man für bsearch() und
qsort() die gleiche Vergleichsfunktion. Die Funktion qsort() hat keinen
Rückgabewert.
Das folgende Listing veranschaulicht den Einsatz von qsort() und bsearch().
Das Programm sortiert und durchsucht ein Array von Integer-Werten.
Zu Beginn des Programms können Sie bis zu MAX Werte eingeben.
Die Werte werden sortiert und dann in der neuen Reihenfolge ausgegeben. Danach
können Sie einen Wert eingeben, nach dem im Array gesucht werden soll. Eine
abschließende Meldung informiert Sie darüber, ob der Wert im Array gefunden
wurde oder nicht.
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int intvgl(const void *v1, const void *v2)
{ return (*(int *)v1 - *(int *)v2); }
int main(void)
{
int arr[MAX], count, suche, *zgr;
/* Werte einlesen */
printf("Geben Sie %d Integer-Werte ein.\n", MAX);
for (count = 0; count < MAX; count++)
scanf("%d", &arr[count]);
/* Sortiert das Array in aufsteigender Reihenfolge */
qsort(arr, MAX, sizeof(arr[0]), intvgl);
/* Gibt das sortierte Array aus. */
for (count = 0; count < MAX; count++)
printf("\narr[%d] = %d.", count, arr[count]);
/* Suchwert eingeben */
printf("Geben Sie einen Wert für die Suche ein: ");
scanf("%d", &suche);
/* Suche durchfuehren */
zgr = (int *)bsearch(&suche, arr, MAX, sizeof(arr[0]),intvgl);
if ( zgr != NULL )
printf("%d bei arr[%d] gefunden.\n", suche, (zgr - arr));
else
printf("%d nicht gefunden.\n", suche);
return(0);
}
Das nächste Listing macht im Prinzip das Gleiche wie das vorstehende, nur daß
diesmal Strings sortiert und gesucht werden.
Die Strings werden sortieren, indem das Array der Zeiger sortiert wird. Dazu muß
allerdings die Vergleichsfunktion angepasst werden. Der Vergleichsfunktion werden
Zeiger auf die zwei Elemente in dem Array übergeben, die verglichen werden. Sie
wollen jedoch das Array von Zeigern nicht nach den Werten der Zeiger selbst,
sondern nach den Werten der Strings, auf die die Zeiger verweisen, sortieren.
Deshalb müssen Sie eine Vergleichsfunktion verwenden, der Zeiger auf Zeiger
übergeben werden. Jedes Argument an vergl() ist ein Zeiger auf eine
Array-Komponente und da jede Komponente selbst ein Zeiger auf einen String ist, so
ist das Argument ein Zeiger auf einen Zeiger. Innerhalb der Funktion selbst
dereferenzieren Sie die Zeiger, so daß der Rückgabewert von vergl()
von den Werten der Strings abhängt, auf die verwiesen wird.
Die Tatsache, daß die Argumente, die vergl() übergeben werden, Zeiger
auf Zeiger sind, schafft auch noch in anderer Hinsicht Probleme. Sie speichern den
Suchbegriff in puffer[] und Sie wissen auch, daß der Name eines Arrays
(in diesem Fall puffer) ein Zeiger auf das Array ist. Sie müssen jedoch
nicht puffer selbst übergeben, sondern einen Zeiger auf puffer.
Das Problem dabei ist, daß puffer eine Zeigerkonstante ist
und keine Zeigervariable. puffer selbst hat keine Adresse im Speicher; es ist ein
Symbol, das zur Adresse des Arrays auswertet. Deshalb können Sie keinen Zeiger
erzeugen, der auf puffer zeigt, indem Sie den Adressoperator vor puffer
(wie in &puffer) verwenden.
Wie verhält man sich in einem solchen Fall? Zuerst erzeugen Sie eine Zeigervariable
und weisen ihr den Wert von puffer zu. In unserem Programm trägt diese
Zeigervariable den Namen suche. Da suche eine Zeigervariable ist, hat
sie eine Adresse, und Sie können einen Zeiger erzeugen, der diese Adresse als Wert
aufnimmt. Wenn Sie schließlich bsearch() aufrufen, übergeben Sie als
erstes Argument suche1 - einen Zeiger auf einen Zeiger auf den Suchstring. Die
Funktion bsearch() übergibt das Argument an vergl(), und alles
läuft wie geschmiert.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
int vergl(const void *s1, const void *s2)
{ return (strcmp(*(char **)s1, *(char **)s2)); }
int main(void)
{
char *daten[MAX], puffer[80], *zgr, *suche;
int count;
/* Eine Liste von Wörtern einlesen. */
printf("Geben Sie %d Wörter ein.\n",MAX);
for (count = 0; count < MAX; count++)
{
printf("Wort %d: ", count+1);
fgets(puffer,80,stdin);
puffer[strlen(puffer)-1] = '\0';
daten[count] = malloc(strlen(puffer)+1);
strcpy(daten[count], puffer);
}
/* Sortiert die Woerter (genauer: die Zeiger) */
qsort(daten, MAX, sizeof(daten[0]), vergl);
/* Die sortierten Woerter ausgeben */
for (count = 0; count < MAX; count++)
printf("\n%d: %s", count+1, daten[count]);
/* Suchbegriff einlesen */
printf("\n\nGeben Sie einen Suchbegriff ein: ");
fgets(puffer,80,stdin);
puffer[strlen(puffer)-1] = '\0';
/* Fuehrt die Suche durch */
/* &suche ist Zeiger auf den Zeiger auf den Suchbegriff.*/
suche = puffer;
zgr = bsearch(&suche, daten, MAX, sizeof(daten[0]), vergl);
if (zgr != NULL)
printf("%s gefunden.\n", puffer);
else
printf("%s nicht gefunden.\n", puffer);
return(0);
}
Boyer-Moore-Suche
Diesen Algorithmus basiert auf der Idee, daß es eigentlich unsinnig ist, nach
jedem Fehlschlag beim Durchsuchen eines Strings wieder ganz von vorne anzufangen.
Wenn man z. B. auf ein Zeichen trifft, das überhaupt nicht im Suchmuster
vorkommt, lohnt es sich erst hinter dem Zeichen weiterzusuchen.
Kommt das Zeichen im Suchmuster vor, aber nicht an der aktuellen Stelle, kann
das Muster mehrere Stellen nach rechts verschoben werden.
Die Boyer-Moore-Suche geht dabei das Suchmuster von rechts nach links durch. Wenn
sie dabei auf ein Zeichen im Text trifft, das ungleich dem korrespondierenden
Zeichen im Suchmuster ist, gibt es drei verschiedene Möglichkeiten:
- Das Zeichen im Text kommt im Suchmuster gar nicht vor. In diesem Fall kann das Suchmuster
bis hinter dieses Zeichen nach rechts verschoben werden.
- Das Zeichen im Text steht weiter vorne im Suchmuster (betrachtet wird sein letztes
Vorkommen im Muster). In diesem Fall können wir das Suchmuster so weit nach rechts
verschieben, daß das Zeichen im Suchmuster unter dem identischen Zeichen im Text
steht.
- Das Zeichen im Text steht weiter hinten im Suchmuster. In diesem Fall können wir
lediglich das Muster um eine Positeon nach rechts schieben.
Anschließend wird das Suchmuster erneut von hinten nach vorne durchsucht. Das wird
so lange gemacht, bis entweder das Suchmuster das Ende des Textes erreicht hat
(ohne daß es gefunden wurde), oder die Überprüfung erfolgreich bis
zum Anfang des Suchmusters war (es also gefunden wurde).
Es bleibt nun noch die Frage, wie man effizient die letze Positeon eines Zeichens im
Suchmuster findet. Dies geschieht üblicherweise über eine Tabelle, in der zu
jedem Zeichen einmal die entsprechende Positeon eingetragen wird, und dann
später nur noch nachgesehen wird. Das Eintragen kann in einem Durchgang erfolgen,
wobei ein Vorkommen eines Zeichens das jeweils vorhergehende Vorkommen dieses Zeichens
überschreibt. Die Positeon -1 steht für "Zeichen nicht vorhanden".
int BMSearch(char *Pat, char *Txt)
{
int PosTable[256];
int PatLen, TxtLen, Index, PatIndex, Positeon;
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)
{
Positeon := PosTable[(char) Txt[Index + PatIndex]];
if (Positeon == -1) Index = Index + PatIndex;
else
if (Positeon > PatIndex) Index++;
else Index = Index + PatIndex - Positeon;
}
}
if (PatIndex < 0) return (Index + 1);
else return(0);
}
Es gibt auch noch weiter verbesserte Versionen dieses Algorithmus; dieser sollte
jedoch für die meisten Fälle ausreichen.
Sortieren von linearen Listen
Die oben behandelten Algorithmen lassen sich nicht nur auf Tabellen (Arrays) anwenden,
sondern auch auf andere Datenstrukturen adaptieren. Beispielhaft soll hier die
Portierung zweier Verfahren auf lineare Listen gezeigt werden. Wenn Elemente
in eine lineare Liste eingefügt werden sollen, dann tut man dies am besten
gleich an der "richtigen" Stelle. Dies zeigt die Funktion InsertionSort
im folgenden Listing.
Für das nachträgliche Sortieren einer linearen Liste wurde die Funktion
BubbleSort gewählt, da hier der Algorithmuns sehr übersichtlich
ist. Die anderen Sortierverfahren lassen sich nach dem gleichen Schema implementieren.
#include <stdio.h>
#include <stdlib.h>
struct LineareListe
{
double Element;
struct LineareListe *next;
};
typedef struct LineareListe LinList;
/*Insertion Sort mit verketteter Liste
* Werte werden bei jedem Aufruf in der Liste eingereiht
* Uebergeben werden Liste und einzureihendes Element
*/
LinList *InsertionSort ( LinList *Liste, double Wert )
{
LinList *temp = Liste;
LinList *neu = malloc(sizeof(LinList));
neu->Element = Wert;
neu->next = NULL;
if(Liste == NULL) return neu;
/* Liste durchwandern, notfalls einreihen */
while (temp->next != NULL)
{
if (temp->next->Element > Wert)
{
neu->next = temp->next;
temp->next = neu;
return Liste;
}
temp = temp->next;
}
/* Am Ende angelangt, Element einreihen */
temp->next = neu;
/* Wenn letztes Element > neues Element,
dann vertauschen */
if (temp->Element > Wert)
{
neu->Element = temp->Element;
temp->Element = Wert;
}
/* Listenanfang zurückgeben */
return Liste;
}
/*Bubble Sort mit Liearen Listen
* Es wird bei einer Liste erst das erste und dann alle nachfolgenden
* Elemente mit der Restliste verglichen und mit kleineren Elementen vertauscht
*/
LinList *BubbleSort (LinList *Liste)
{
LinList *Rest, *Akt = Liste;
double swap;
/* Liste ist leer oder hat nur ein Element */
if ((Liste == NULL) || (Liste->next == NULL)) return Liste;
/* Sortierverfahren Bubblesort */
do
{
Rest = Akt;
do
{
Rest = Rest->next;
/* Wenn der Restwert kleiner als Vergleichswert, dann vertauschen */
if (Rest->Element < Akt->Element)
{
swap = Rest->Element;
Rest->Element = Akt->Element;
Akt->Element = swap;
}
} while (Rest->next != NULL);
Akt = Akt->next;
} while (Akt->next != NULL);
return Liste;
}
Soundex-Verfahren
Der Soundex-Code für einen Begriff wird wie folgt berechnet:
- Entferne alle Vokale und die Konsonanten H, W, Y. Von aufeinanderfolgenden gleichen Zeichen bleibt nur eins erhalten. Das erste Zeichen bleibt erhalten.
- Entwickle den Soundex-Code für den ersten und die darauffolgenden maximal 3 Zeichen nach der Soundex-Tabelle.
| Buchstaben | Ziffern | Erzeugung der Laute |
|---|
| b, f, p, v | 1 | Lippen, öffnend |
| c, g, j, k, q, s, x, z | 2 | Rachen, Zunge |
| d, t | 3 | Zunge, Zähne |
| l | 4 | Zunge, Gaumen |
| m, n | 5 | Lippen, geschlossen |
| r | 6 | Zunge, rollend |
Der Soundex-Algorithmus basiert auf der Annahme, daß Worte, die
ähnlich klingen, auch von der Semantik her ähnlich sind. Soundex
reduziert jedes Wort auf einen eindeutigen maximal vier Zeichen langen
Code.
In der letzten Spalte wird die Erzeugung der Laute klassifiziert. Wir sehen,
daß die Zusammenfassung sich an der Erzeugung orientiert. Somit ergibt sich
immer eine Kombination aus einem Buchstaben und einer dreistelligen Zahl, die
maximal 666 erreichen kann.
Die Verbesserungen bzw. - vorsichtiger ausgedrückt - die Variationen können
sich z. B. auf die Behandlung des Anfangsbuchstabens beziehen, indem wir ihn wie die
anderen Buchstaben behandeln. Dieser Algorithmus wird als Extended Soundex Algorithmus
bezeichnet. Hier ergibt sich eine vierstellige Zahl, die 6666 nicht überschreitet,
so daß sie in max. 2 Byte abgespeichert werden kann, was bei sehr großen
Dateien natürlich erheblichen Speicherplatz einspart.
Wir können nun versuchen, Verbesserungen vorzunehmen. Diese müssen sich
aber immer am Sprachverständnis der erfassenden Person orientieren.
Beispiele:
| 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:
- der erste Buchstabe bleibt erhalten
- Umlaute werden konvertiert
- Kleinbuchstaben werden in Großbuchstaben konvertiert
- Konvertiert die ersten N Buchstaben zu Soundex-Codes (N ist Parameter)
Es wäre möglich gewesen, etliche Konvertierunge in einer Schleife
zusammenzufassen. Joe Celko hat etwas "großzügiger" programmiert,
um Änderungen leichter zu machen.
#define WBUFSIZE 512
void soundex4(const char *instr, char *outstr, int N)
{
char *p, *p1;
int i;
char workbuf[WBUFSIZE + 1];
char priorletter;
/* Make a working copy */
strncpy(workbuf, instr, WBUFSIZE);
workbuf[WBUFSIZE] = '\0';
/* Konvertieren zu Grossbuchstaben und Umlaute */
for (p = workbuf; *p; ++p)
{
*p = toupper(*p);
switch (*p)
{
case 'ä': *p = 'A'; break;
case 'ö': *p = 'O'; break;
case 'ü': *p = 'U'; break;
case 'Ä': *p = 'A'; break;
case 'Ö': *p = 'O'; break;
case 'Ü': *p = 'U'; break;
case 'ß': *p = 'S'; break;
default: break;
}
}
/* Konvertieren alle Vokale zu 'A' */
for (p = workbuf; *p; ++p)
if (strchr("AEIOUY", *p)) *p = 'A';
/* Praefix-Transformation: Nur am Anfang des Namens */
if (strncmp(workbuf, "MAC", 3) == NULL) /* MAC to MCC */
workbuf[1] = 'C';
else if (strncmp(workbuf, "KN", 2) == NULL) /* KN to NN */
workbuf[0] = 'N';
else if (workbuf[0] == 'K') /* K to C */
workbuf[0] = 'C';
else if (strncmp(workbuf, "PF", 2) == NULL) /* PF to FF */
workbuf[0] = 'F';
else if (strncmp(workbuf, "SCH", 3) == NULL) /* SCH to SSS */
workbuf[1] = workbuf[2] = 'S';
/*Infix-Transformationen: ab dem 2. Buchstaben,
* von links nach rechts */
while ((p = strstr(workbuf, "DG")) > workbuf) /* DG to GG */
p[0] = 'G';
while ((p = strstr(workbuf, "CAAN")) > workbuf) /* CAAN to TAAN */
p[0] = 'T';
while ((p = strchr(workbuf, 'D')) > workbuf) /* D to T */
p[0] = 'T';
while ((p = strstr(workbuf, "NST")) > workbuf) /* NST to NSS */
p[2] = 'S';
while ((p = strstr(workbuf, "AV")) > workbuf) /* AV to AF */
p[1] = 'F';
while ((p = strchr(workbuf, 'Q')) > workbuf) /* Q to G */
p[0] = 'G';
while ((p = strchr(workbuf, 'Z')) > workbuf) /* Z to S */
p[0] = 'S';
while ((p = strchr(workbuf, 'M')) > workbuf) /* M to N */
p[0] = 'N';
while ((p = strstr(workbuf, "KN")) > workbuf) /* KN to NN */
p[0] = 'N';
while ((p = strchr(workbuf, 'K')) > workbuf) /* K to C */
p[0] = 'C';
while ((p = strstr(workbuf, "AH")) > workbuf) /* AH to AA */
p[1] = 'A';
while ((p = strstr(workbuf, "HA")) > workbuf) /* HA to AA */
p[0] = 'A';
while ((p = strstr(workbuf, "AW")) > workbuf) /* AW to AA */
p[1] = 'A';
while ((p = strstr(workbuf, "PH")) > workbuf) /* PH to FF */
p[0] = p[1] = 'F';
while ((p = strstr(workbuf, "SCH")) > workbuf) /* SCH to SSS */
p[0] = p[1] = 'S';
/*Suffix-Transformationen: am Wortende */
/* (1) 'A's und 'S's am Ende weg */
for (i = strlen(workbuf) - 1;
(i > 0) && ((workbuf[i] == 'A') || (workbuf[i] == 'S'));
--i)
workbuf[i] = '\0';
/* (2) NT -< 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';
}
|
| |
DIENSTE
