Suchvorgänge kommen häufig dann vor, wenn ein Programm interaktiv bedient wird. So kan man z. B. aus einer Kundendatei den Datensatz eines Kunden an Hand seines Nachnamens finden. Vielleicht führt der Familienname aber auch zu einer ganzen Gruppe der "Meiers" oder "Hubers". Ist unsere Datei sortiert, dann können wir den ersten Datensatz suchen und bei Bedarf einfach zum nächsten weitergehen.
#include <stdlib.h>
void *bsearch(void *key,void *basis,size_t
anzahl, size_t egroesse, int (*vergleich)(void *, void *));
void qsort (void *base, size_t anzahl, size_t
egroesse, int (*vergleich)(void *, void *));
Beginnen wir zuerst mit dem Sortieren von Daten im Speicher. Die Funktion, die ANSI-C bereitstellt, heißt qsort() nach dem sogenannten "Quicksort"-Algorithmus von C.A.R. Hoare. Die Funktion sortiert den Inhalt eines Feldes.
Sortieren läßt sich immer in zwei grundlegende Schritte einteilen: ein Vergleich und ein Vertauschen. Je weniger Vergleiche und Vertauschungen notwendig sind, um zu einem geordneten Feld zu gelangen, desto besser ist ein Sortieralgorithmus. Der "Quicksort" (der schnelle Sortierer) macht seinem Namen dabei alle Ehre. Trotzdem lassen sich auch mit qsort() erhebliche Ablaufzeiten erreichen.
Bild 6-1: Quicksort - Grundlegendes Beispiel
Die Zeile 9 legt für verf den Typ fest. verf ist damit ein Zeiger auf eine Funktion, die zwei typlose Zeiger als Parameter erhält und als Ergebnis einen int-Wert zurückliefert. Die Anweisung typedef definiert diese Abkürzung. Eine andere Anwendung für typedef kennen wir bereits von der Definition des Datentyps bei Strukturen. Der große Vorteil einer solchen Abkürzung ist hier die wesentlich leichtere Lesbarkeit im nachfolgenden Programm.
In den Zeilen 11 bis 13 definieren wir ein Feld aus Zeilen und Spalten. Die Initialisierung belegt die Zeilen mit 5 verschiedenen Worten vor. Dabei beginnen manche Worte mit kleinen, andere mit großen Buchstaben. Dies hat Einfluß auf die Sortierung. In der Initialisierung sind die 5 Zeilen noch nicht geordnet.
Ab der Zeile 15 beginnt das Hauptprogramm. Nach dem Löschen des Bildschirms rufen wir die Sortiertfunktion auf. Der erste Parameter gibt dabei die Startadresse der zu sortierenden Tabelle an, der zweite die Anzahl der Elemente im Feld, der dritte die Größe einer einzelnen Feldvariablen, und schließlich übergeben wir als vierten Parameter die Adresse einer Vergleichsfunktion.
Die for-Schleife ab der Zeile 21 zeigt uns das Ergebnis des Sortiervorganges.
Schauen wir uns die einzelnen Vorgänge noch einmal genauer an. Das Feld mit den Textzeilen muß von qsort() lesbar und veränderbar sein. Die Sortierfunktion verschiebt innerhalb des Feldes die einzelnen Einträge so lange, bis die gewünschte Ordnung hergestellt ist.
Die Anzahl der Einträge in dem Textfeld haben wir als Konstante eingetragen. Im nächsten Beispiel werden wir diesen Wert berechnen.
Die Berechnung der Größe eines einzelnen Feldelements geschieht wie üblich mit sizeof.
Bleibt uns noch der letzte und schwierigste Parameter. Übergeben wird die Adresse einer Funktion. strcoll() erwartet als Parameter Zeiger auf char. Um die notwendige Typanpassung vorzunehmen, können wir in in einer expliziten Typwandlung dem Compiler sagen, daß er die übergebene Adresse als Adresse einer Funktion werten soll, die zwei typlose Zeiger als Parameter erhält. Dazu haben wir in der Zeile 9 einen Typ definiert und wenden ihn nun in der expliziten Typwandlung (cast) an.
Die Funktion strcoll() vergleicht zwei Texte, deren Adressen als Parameter übergeben werden. Falls der erste Text als logisch kleiner als der zweite ermittelt wird, gibt strcoll() eine negative Zahl zurück, bei Gleichheit die "0" und für den Fall, daß der zweite Text größer als der erste ist, wird ein positiver Wert zurückgegeben.
qsort() interpretiert nun die Ergebnisse der Vergleichsfunktion. Bei einem negativen Wert wird der erste Parameter im Ergebnis vor dem zweiten stehen, bei "0" ist die Reihenfolge beliebig, und schließlich bedeutet eine positive Rückgabe das Gegenteil der negativen. Nun soll der zweite Parameter vor dem ersten im Ergebnisfeld stehen.
Im Beispiel wurde als Vergleichsfunktion die internationalisierte Version von strcmp(), nämlich strcoll() verwendet.
Das erweiterte Beispiel verbessert die Handhabung und erweitert den Sortieralgorithmus auf ein Feld aus Zeigern. Das Feld wird mit Hilfe der Initialisierung mit den Startadressen von kurzen Texten vorbelegt. Nun hätte es in unserem Beispiel wenig Sinn, die Adressen in einem Feld zu sortieren. Wichtig für die Reihenfolge im Feld soll der Text sein, dessen Adresse im Feld liegt. Dazu benötigen wir eine eigene Vergleichsfunktion, die wir sortiere() nennen.
Die Vergleichsfunktion erhält zwei Zeiger auf die zu vergleichenden Feldelemente. sortiere() definiert diese Zeiger als Zeiger auf Zeiger auf char (oder als Zeiger, die auf char-Zeiger zeigen). Wieder nehmen wir die strcoll()-Funktion als Vergleicher. Diesmal versorgen wir sie aber mit dem Inhalt des Feldelements. Dazu greifen wir mit dem erhaltenen Parameter indirekt zu. Letzlich vergleichen wir wieder Texte, deren Adressen nun im Feld durch qsort() neu angeordnet werden.
Der qsort()-Aufruf verzichtet nun auf Konstante als Parameter. In der vorhergegangenen Zeile wird die Anzahl der Feldelemente berechnet. Eine Änderung der Feldgröße ist damit problemlos möglich.
Die Anzahl erhalten wir, wenn wir einfach die Größe des ganzen Feldes durch die Größe eines einzelnen Eintrags teilen. Es handelt sich dabei um einen Ausdruck, der nur aus Konstanten besteht. Damit kann er während der Übersetzungszeit vom Compiler berechnet werden und kostet keine Laufzeit.
Dank der expliziten Typkonvertierung können wir als vierten Parameter wieder die Adresse der Sortierfunktion übergeben.
Bild 6-3: Binäres Suchen in einem Feld
Einer der schnellsten Algorithmen ist die binäre Suche. Sie unterteilt das zu durchsuchende Feld immer in zwei Hälften. Durch fortgesetzte Halbierung findet man den gewünschten Eintrag. Ein Feld aus 2 hoch 10 Elementen kann damit in maximal 10 Halbierungschritten durchsucht werden.
Dies gilt aber nur dann, wenn das Feld sortiert wurde.
Die Funktion bsearch() erwartet als Parameter einen Zeiger auf ein konstantes Vergleichsobjekt. Nach diesem Vergleichsobjekt soll gesucht werden.
Beim Aufruf der Vergleichsfunktion wird als erster Parameter der Zeiger auf das Vergleichsobjekt übergeben und als zweiter der Zeiger auf das zu vergleichende Tabellenelement.
Im Beispiel wird ein Feld aus Zahlen angelegt. Nach einer der Zahlen soll gesucht werden. Um den Aufruf der Suchfunktion etwas handlicher zu gestalten, wird in der Zeile 6 (Bild 3) ein Makro zur Berechnung der Elementanzahl definiert. Dies ist besonders dann von Vorteil, wenn keine Konstante für die Feldgröße definiert wurde.
An bsearch() wird ein Zeiger auf eine lokale Variable mit dem Suchwert übergeben. Danach beschreiben die weiteren Parameter das zu durchsuchende Feld und schließlich wird eine typgewandelte Adresse der Vergleichsfunktion übergeben.
Die Vergleichsfunktion erhält nun einen Zeiger auf den Vergleichswert ("key" / Schlüssel) und einen Zeiger auf das Feldelement. Damit können wir einen einfachen Vergleich durch die Subtraktion der beiden int-Werte erreichen, auf die die Zeiger zeigen.
Die Vergleichsfunktion bestimmt die Sicht auf das Feld. Bei einem Feld aus Zahlen wird eine numerische Vergleichsfunktion benötigt, bei einem Textfeld eine Textvergleichsfunktion. Die Suchfunktion erwartet, daß das Feld nach den Kriterien sortiert wurde, die die Vergleichsfunktion bestimmt.
Um die gemeinsame Anwendung von Sortieren und Suchen zu zeigen, stellt das zweite Suchbeispiel ein Feld aus Zeigern auf Texte bereit ("tfeld"). Die Zeiger zeigen auf unsortierte Texte. Wie im zweiten qsort()-Beispiel wird daher das Feld zuerst sortiert. Die entsprechende Vergleichsfunktion stammt auch aus diesem Beispiel.
Für den Suchvergleich benötigt das Programm eine eigene Vergleichsfunktion. Der erste Parameter von bvergleich() ist der Zeiger auf den Schlüssel (das Vergleichsobjekt), der hier ein Text ist. Der zweite Zeiger gibt jedoch die Adresse des zu vergleichenden Feldelements an. Da das Feldelement seinerseits wieder ein Textzeiger ist, wird als Parameter ein Zeiger auf Zeiger auf char definiert.
Die Vergleichsfunktionen für Sortieren und Suchen unterscheiden sich nur im ersten Parameter.
Beim Sortieren ordnet man eine Menge von Elementen, beim Suchen wählt man ein bestimmtes Element, soweit vorhanden, aus der Menge aus und mit der Hilfe von Zufallszahlen kann man ebenfals ein Element aus einer Menge herauspicken. Der Unterschied wird nur sein, daß das Element nach anderen Kriterien gesucht wird.
#include <stdlib.h>
RAND_MAX
int rand (void);
void srand(unsigned int startwert);
In der stdlib.h sind zwei Funktionen und ein Makro beschrieben, die mit Zufallszahlen umgehen. Die Idee einer Zufallszahl ist es, bei jedem neuen Aufruf der Funktion rand() ( für random / zufällig) einen Wert zu liefern, der im Bereich von "0" bis einschließlich RAND_MAX liegen kann.
Da die Implementierung des Zufallszahlengenerators gleich bleibt, ist auch die Reihenfolge der gelieferten Zahlen gleich. Man spricht daher besser von einem Pseudezufallsgenerator.
Im ersten Beispiel löscht das Programm den Bildschirm und gibt die maximale Zufallszahl aus. Danach wird in einer Schleife der Zufallszahlengenerator aufgerufen. Die ausgegebenen Zahlen werden mit Hilfe von printf() angezeigt. Bei einem 16-Bit-Prozessor dürfte der größte Zufallwert normalerweise die größte ganze Zahl sein, die man in einer int-Variablen darstellen kann.
Ruft man das Programm mehrmals auf, so wird die Rückgabe vermutlich immer gleich bleiben.
Bild 6-5: Ausgabe von Pseudozufallszahlen
Mit Hilfe der Zufallszahlen wollen wir nun auf ein Feld aus Texten zugreifen und einen davon herauspicken. Dazu ist es notwendig, die erhaltene Zufallszahl zu normieren. Wenn der benutzte Index maximal X groß werden darf, und die Zufallszahl maximal RAND_MAX liefert, dann kann man das Verhältnis der beiden Zahlen benutzen, um eine Zufallszahl zu berechnen, die maximal so groß wird, wie der höchste benutzte Index.
Man bildet damit die Zahlenmenge der Zufallszahlen auf die Menge der möglichen Indizes ab.
Aber sehen wir uns dies lieber im Beispiel (Bild 6) an. Zuerst wird ein Textfeld mit verschiedenen Familiennamen vorbereitet. Die Größe des Feldes ergibt sich aus der Anzahl der Initialisierungseinträge. Das Hauptprogramm legt einige lokale Variable an, löscht den Bildschirm und liefert eine Begrüssungsmeldung. Die Variable faktor dient dazu, das Verhältnis der beiden Zahlenbereiche aufzunehmen. Dazu weist man ihr in der Zeile 14 das Divisionsergebnis zu. Der gültige Zahlenbereich für den Feldindex ergibt sich aus der Anzahl der Elemente weniger eins.
Sicherheitshalber wird faktor als double definiert. Die Division wird durch eine explizite Typwandlung ebenfalls mit double durchgeführt. Der berechnete Wert wird dann dem Benutzer mitgeteilt.
In einer Schleife zeigt dann das Programm den erhaltenen Zufallswert, den berechneten Index sowie den Namen an, der unter diesem Index im Feld gespeichert ist. Der Index wird einfach durch eine Diviosn durch den gefundenen Faktor ermittelt.
Während des Programmablaufes liefert rand() nun eine Serie von unterschiedlichen Zahlen, die im Programm durchaus einen zufälligen Charakter haben. Läßt man aber das Programm wiederholt ablaufen, dann ergibt sich immer wieder die gleiche Serie von Zahlen.
Bild 6-6: Zugriff auf ein Textelement im Feld
Um dies ebenfalls noch zu verändern, sehen wir uns einmal eine Implementierung der rand()-Funktion an, wie sie vom Standard vorgeschlagen wird.
Die Zufallsgeneratorfunktion benötigt einen internen Startwert, der in der Variablen Basiswert abgelegt wird. Dieser Wert ist "1". Bei jedem Aufruf von rand() wird ein neuer Basiswert berechnet. Der Rückgabewert von rand() wird dann mit Hilfe des veränderten Basiswertes gewonnen. Die Idee der Division ist es, möglichst viele unterschiedliche Reste bei der Ganzzahldivision zu erzeugen.
Bild 6-7: Implementierung von rand() und srand()
Die zweite Funktion, die ebenfalls im Bild 7 implementiert wurde, setzt einfach einen neuen Basiswert. Im Englischen nennt man ihn seed, die Aussaat.
Im letzten Beispiel zu den Zufallszahlen kann man nun den Zugriff auf das Textfeld "zufälliger" machen, indem man den Basiswert am Beginn "zufällig" setzt. Nur, wie erhält man einen zufälligen Wert? Schließlich kann man schlecht rand() dazu aufrufen.
Eine gute Möglichkeit bietet die Rückgabe von time(). Der zurückgegebene Wert ist die Anzahl von Sekunden seit dem 1.1.1970 um Mitternacht. Da sich die Sekundenzahl dauernd ändert, erhält man immer wieder neue Startwerte, die zu einem veränderten Ausgabe des Programmes führen. Der Eindruck der Zufälligkeit ist damit erheblich stärker.
Bild 6-8: "Zufälliges" Setzen des Basiswertes
Der mehrmalige Aufruf dieses Programms wird nun zu unterschiedlichen Ergebnissen führen, so als hätten wir tatsächlich einen Zufallszahlengenerator zur Verfügung.