1 Theorie | |
→ | 1.2 Häufig auftretende Problemstellungen |
Sortieren |
Suchen in sortierten Feldern |
Beispiel |
Zum Sortieren von Feldern steht die Funktion
void qsort( void *base, size_t nmemb, size_t elsize, int (*compar)(const void *, const void *) );
zur Verfügung.
Die ersten drei Argumente sind die Anfangsadresse des Feldes,
die Anzahl der Feldelemente und die Größe eines einzelnen
Feldelementes.
Das vierte Argument ist die Adresse einer Funktion, z.B. mit einem
Prototyp wie:
int elemente_vergleichen(const void *ptr_links, const void *ptr_rechts);
Diese Funktion erhält als Argumente Zeiger auf zwei Feldelemente. Diese Feldelemente werden verglichen, zurückgegeben wird das Vergleichsergebnis:
Ergebnis | Bedeutung |
---|---|
<0 | ptr_links < ptr_rechts, d.h. der Datensatz, auf den ptr_links zeigt, muss vor dem Datensatz platziert sein, auf den ptr_rechts zeigt. |
0 | ptr_links = ptr_rechts, d.h. beide Datensätze werden gleich bewertet, die Reihenfolge ist egal. |
>0 | ptr_link > ptr_rechts, d.h. der Datensatz, auf den ptr_links zeicht, muss nach dem Datensatz platziert sein, auf den ptr_rechts zeigt. |
Die Funktion elemente_vergleichen()
wird nicht von unserem Code aus aufgerufen. Die Funktion
qsort() erhält die Adresse der Funktion
elemente_vergleichen() und ruft diese Funktion dann auf, um
die Reihenfolge der Feldelemente zu bestimmen.
Funktionen wie elemente_vergleichen(), die nicht aus dem
Code heraus selbst aufgerufen werden, sondern deren Adresse einer
anderen Funktion übergeben wird, werden als Callback-Funktion
bezeichnet.
Mit der Funktion
void * bsearch( const void *key, const void *base, size_t nmemb, size_t elsize, int (*compar)(const void *, const void *) );
wird in einem sortierten Feld nach einem bestimmten
Datensatz gesucht.
Der erste Parameter key ist die Adresse eines Datensatzes,
der dem zu suchenden Datensatz entspricht.
Die nächsten drei Parameter base, nmemb und
elsize geben das zu durchsuchende Feld an: Anfangsadresse
des Feldes, Anzahl der Elemente im Feld und Größe eines einzelnen
Feldelementes.
Das fünfte Argument ist auch hier wieder die Adresse einer
Callback-Funktion zum Vergleichen des key-Elementes mit
einem Feldelement. Die Callback-Funktion erhält jeweils das
key-Element als ersten Zeiger, die Adresse eines
Feldelementes als zweiten Zeiger.
Wurde ein passendes Element im Feld gefunden, gibt die Funktion
einen Zeiger auf die Anfangsadresse des Feldelementes zurück.
Wurde kein passendes Element gefunden, liefert bsearch()
einen NULL-Zeiger.
/** @file ex080.c Beispiel fuer Sortierung mit qsort und Suche mit bsearch.
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/** Zuordnung von Monatsnummer zum Namen.
*/
typedef struct {
int nr; /**< Nummer des Monats. */
const char *name; /**< Name des Monats. */
} monat_t;
/** Feld, das Angaben zu allen Monaten enthaelt.
*/
static monat_t monate[] = {
{ 1, "Januar" }, { 2, "Februar" }, { 3, "Maerz" },
{ 4, "April" }, { 5, "Mai" }, { 6, "Juni" },
{ 7, "Juli" }, { 8, "August" }, { 9, "September" },
{ 10, "Oktober" }, { 11, "November" }, { 12, "Dezember" },
};
/** Anzahl der Elemente im Feld monate.
*/
static const size_t sz_monate = sizeof(monate)/sizeof(monat_t);
/** Vergleichsfunktion, die zwei monat_t-Datensaetze nach Namen vergleicht.
@param kptr Schluesselelement bzw linkes Element.
@param eptr Rechtes Element.
@return <0 wenn kptr<eptr, 0 wenn kptr=eptr, >0 wenn kptr>eptr.
*/
static
int
vergleiche_nach_namen(const void *kptr, const void *eptr)
{
const monat_t *k;
const monat_t *e;
k = (const monat_t *)kptr;
e = (const monat_t *)eptr;
return (strcmp(k->name, e->name));
}
/** Feld monate ausgeben.
*/
static
void
feld_ausgeben(void)
{
size_t i;
for (i = 0; i < sz_monate; i++) {
printf("%02d %s\n", monate[i].nr, monate[i].name);
}
}
/** Hauptprogramm.
@return EXIT_SUCCESS bei Erfolg, EXIT_FAILURE bei Fehlschlag.
*/
int
main(void)
{
monat_t suchschluessel;
monat_t *suchergebnis;
/* Originalzustand ausgeben.
*/
printf("Feld monate im Originalzustand:\n");
feld_ausgeben();
/* Feld monate umsortieren, so dass nach Namen geordnet.
*/
qsort(monate, sz_monate, sizeof(monat_t), vergleiche_nach_namen);
/* Umsortiertes Feld ausgeben.
*/
printf("\nFeld monate nach Umsortierung:\n");
feld_ausgeben();
/* Suche nach Monat "Oktober"
Im Element suchschluessel wird nur der Name gesetzt, da die
Vergleichsfunktion vergleiche_nach_namen nur den Namen nutzt,
nicht aber die Nummer.
Bevor mit bsearch in einem Feld gesucht werden kann, muss es mit
qsort unter Verwendung derselben Vergleichsfunktion sortiert worden
sein. Dies ist weiter oben bereits erfolgt.
*/
suchschluessel.name = "Oktober";
suchergebnis = bsearch (
&suchschluessel,
monate, sz_monate, sizeof(monat_t), vergleiche_nach_namen
);
if (NULL != suchergebnis) {
printf("\nGefunden: %02d %s\n", suchergebnis->nr, suchergebnis->name);
}
else {
printf("\nFEHLER: Monat \"Oktober\" wurde nicht gefunden!\n");
}
/* Suche nach nicht existierendem Monat "Urlaub".
*/
suchschluessel.name = "Urlaub";
suchergebnis = bsearch (
&suchschluessel,
monate, sz_monate, sizeof(monat_t), vergleiche_nach_namen
);
if (NULL != suchergebnis) {
printf("\nGefunden: %02d %s\n", suchergebnis->nr, suchergebnis->name);
}
else {
printf("\nFEHLER: Monat \"Urlaub\" wurde nicht gefunden!\n");
}
return(EXIT_SUCCESS);
}
/* vim: set ai sw=4 ts=4 : */
Die leicht abgewandelte Version ex081.c verwendet zwei unterschiedliche Callback-Funktionen: vergleiche_nach_namen() zum Sortieren, vergleiche_mit_namen() bei der Suche nach einem bestimmten Feldelement.
Die bei der Suche verwendete Callback-Funktion (hier vergleiche_mit_namen()) erhält den als key an bsearch() übergebenen Zeiger immer als erstes Argument und die Adresse des zu prüfenden Feldelementes immer als zweites Argument. Somit muss nicht erst ein Suchschlüssel-Datensatz zusammengestellt werden, der Monatsname wird direkt an bsearch() übergeben.
In beiden Callback-Funktionen wurde die Zeigerkonvertierung von "const void *" zu "const monat_t *" bzw. "const char *" direkt im Aufruf von strcmp() vorgenommen, anstatt hierfür extra Codezeilen zu schreiben.
/** @file ex080.c Beispiel fuer Sortierung mit qsort und Suche mit bsearch.
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/** Zuordnung von Monatsnummer zum Namen.
*/
typedef struct {
int nr; /**< Nummer des Monats. */
const char *name; /**< Name des Monats. */
} monat_t;
/** Feld, das Angaben zu allen Monaten enthaelt.
Das Feld ist beim Programmstart nach den Monatsnummern sortiert.
Waehrend des Programmlaufes wird es umsortiert nach Monatsnamen.
*/
static monat_t monate[] = {
{ 1, "Januar" }, { 2, "Februar" }, { 3, "Maerz" },
{ 4, "April" }, { 5, "Mai" }, { 6, "Juni" },
{ 7, "Juli" }, { 8, "August" }, { 9, "September" },
{ 10, "Oktober" }, { 11, "November" }, { 12, "Dezember" },
};
/** Anzahl der Elemente im Feld monate.
*/
static const size_t sz_monate = sizeof(monate)/sizeof(monat_t);
/** Vergleichsfunktion, die zwei monat_t-Datensaetze nach Namen vergleicht.
@param kptr Schluesselelement bzw linkes Element.
@param eptr Rechtes Element.
@return <0 wenn kptr<eptr, 0 wenn kptr=eptr, >0 wenn kptr>eptr.
*/
static
int
vergleiche_nach_namen(const void *kptr, const void *eptr)
{
return(strcmp(((const monat_t *)kptr)->name,((const monat_t *)eptr)->name));
}
/** Vergleichsfunktion, die zwei Monatsnamen vergleicht.
@param kptr Zu suchender Monatsname als String-Zeiger.
@param eptr Adresse des zu pruefenden Feldelementes.
@return <0 wenn kptr<eptr, 0 wenn kptr=eptr, >0 wenn kptr>eptr.
*/
static
int
vergleiche_mit_namen(const void *kptr, const void *eptr)
{
return ( strcmp( (const char *)kptr, ((const monat_t *)eptr)->name) );
}
/** Feld monate ausgeben.
*/
static
void
feld_ausgeben(void)
{
size_t i;
for (i = 0; i < sz_monate; i++) {
printf("%02d %s\n", monate[i].nr, monate[i].name);
}
}
/** Hauptprogramm.
@return EXIT_SUCCESS bei Erfolg, EXIT_FAILURE bei Fehlschlag.
*/
int
main(void)
{
monat_t *suchergebnis;
/* Originalzustand ausgeben.
*/
printf("Feld monate im Originalzustand:\n");
feld_ausgeben();
/* Feld monate umsortieren, so dass nach Namen geordnet.
*/
qsort(monate, sz_monate, sizeof(monat_t), vergleiche_nach_namen);
/* Umsortiertes Feld ausgeben.
*/
printf("\nFeld monate nach Umsortierung:\n");
feld_ausgeben();
/* Suche nach Monat "Oktober"
Bevor mit bsearch in einem Feld gesucht werden kann, muss es mit
qsort unter Verwendung derselben Vergleichsfunktion sortiert worden
sein. Dies ist weiter oben bereits erfolgt.
*/
suchergebnis = bsearch (
"Oktober",
monate, sz_monate, sizeof(monat_t), vergleiche_mit_namen
);
if (NULL != suchergebnis) {
printf("\nGefunden: %02d %s\n", suchergebnis->nr, suchergebnis->name);
}
else {
printf("\nFEHLER: Monat \"Oktober\" wurde nicht gefunden!\n");
}
/* Suche nach nicht existierendem Monat "Urlaub".
*/
suchergebnis = bsearch (
"Urlaub",
monate, sz_monate, sizeof(monat_t), vergleiche_mit_namen
);
if (NULL != suchergebnis) {
printf("\nGefunden: %02d %s\n", suchergebnis->nr, suchergebnis->name);
}
else {
printf("\nFEHLER: Monat \"Urlaub\" wurde nicht gefunden!\n");
}
return(EXIT_SUCCESS);
}
/* vim: set ai sw=4 ts=4 : */