Um nicht mit den Namen der Standardfunktionen zu kollidieren, werden in der folgenden Musterlösung andere Funktionsnamen verwendet, nämlich msearch() und msort().
// Time-stamp: "(31.10.01 19:28) msearchmsort.cpp [Klaus Wachtler (aw38)]" // // Lösung der Beispielaufgabe "Neuprogrammieren von bsearch() und qsort()". // // Diese Version läuft nur unter dem gcc, weil zum Allokieren von // Speicherplatz die Funktion alloca() verwendet wird. Dies ist kein // ANSI-Standard! #include <stdlib.h> #include <stdio.h> // sucht in einem sortierten Feld (*base)[] nach einem // Element, für das die Funktion (*compar)() Gleichheit mit dem // Schlüssel (*key) verspricht, und liefert einen Zeiger auf // das gefundene Element, oder NULL // (entspricht dem Original-bsearch() nach ANSI-C) void *msearch( const void *key, const void *base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) ) { switch( nmemb ) { case 0: return NULL; case 1: return ( (*compar)( base, key )==0 ? (void *)base : NULL ); default : // Teilen, und suchen lassen: { size_t n1 = nmemb/2; const void *p1 = (const char*)base+(n1*size); int v1 = (*compar)( p1, key ); if( v1==0 ) { // Schlüssel genau getroffen return(void *) p1; } else if( v1<0 ) { // base[n1] kleiner als Schlüssel; // also in der oberen Hälfte suchen. // base[n1] braucht schon nicht mehr betrachtet // zu werden. return msearch( key, (const char*)p1+size, nmemb - n1 - 1, size, compar ); } else { // base[n1] größer als Schlüssel; // also in der unteren Hälfte suchen. // base[n1] braucht schon nicht mehr betrachtet // zu werden. return msearch( key, base, n1, size, compar ); } } } // switch } // msearch() // Aus c't 3/92, S. 263ff. entnommen: // {Bezugsdatenstruktur a : ARRAY [1 .. n] und temp} // // PROCEDURE quicksort ( links, rechts : integer); // VAR k, i, j : integer; // BEGIN // IF rechts > links THEN BEGIN // i := links -1; j := rechts; k := a[rechts].key; // REPEAT // REPEAT i := i +1 UNTIL a[i].key > k; // REPEAT j := j -1 UNTIL a[j].key <= k; // IF i >= j THEN // BEGIN // temp := a[i]; a[i] := a[r]; a[r] := temp; // END // ELSE // BEGIN // temp := a[i]; a[i] := a[j]; a[j] := temp; // END; // UNTIL i >= j; // quicksort( links, i-1 ); // quicksort( i+1, rechts); // END; // END; void msort( const void *base, size_t nmemb, size_t size, int (*compar)( const void *, const void * ) ) { // VAR k, i, j : integer; int i, j; void *key_p = alloca( size ); // IF rechts > links THEN BEGIN if( nmemb>1 ) { // Feldlänge größer als 1 // i := links -1; j := rechts; k := a[rechts].key; i = -1; j = nmemb - 1; memcpy( key_p, (char*)base + size*j, size ); // REPEAT do { // REPEAT i := i +1 UNTIL a[i].key > k; while( compar( (char*)base + size*++i, key_p )>0 ); // REPEAT j := j -1 UNTIL a[j].key <= k; while( compar( (char*)base + size*--j, key_p )<=0 ); // IF i >= j THEN if( i>=j ) { // temp := a[i]; a[i] := a[r]; a[r] := temp; // ? // 31.10.2001 Klaus Wachtler: // Was hier vertauscht werden soll, weiß ich nicht. // Die Variable r ist bisher nicht erwähnt; ich nehme // an, daß nichts vertauscht werden muß. // Mein Beispielfeld jedenfalls wird richtig // sortiert. // Was wirklich gemeint ist, muß ich noch klären. } // ELSE else { // temp := a[i]; a[i] := a[j]; a[j] := temp; void *temp_p = alloca( size ); memcpy( temp_p, (char*)base + size*i, size ); memcpy( (char*)base + size*i, (char*)base + size*j, size ); memcpy( (char*)base + size*j, temp_p, size ); }
} while( i<j ); // UNTIL i >= j; // quicksort( links, i-1 ); msort( base, i-1, size, compar ); // quicksort( i+1, rechts); msort( (char*)base + size*(i+1), nmemb - i - 1, size, compar ); } // Feldlänge größer als 1 } // msort( const void *base,... typedef struct { double d; char s[100]; } s_t; // vergleicht zwei Elemente vom Typ s_t (auf welche // die beiden übergebenen Zeiger zeigen) anhand ihrer // darin enthaltenen Gleitkommawerte d: int vergl_f( const void *p1, const void *p2 ) { if( ((const s_t*)p1)->d > ((const s_t*)p2)->d ) { return 1; } else if( ((const s_t*)p1)->d < ((const s_t*)p2)->d ) { return -1; } else { return 0; } } // zu sortierendes Beispielfeld: s_t f[] = { { 3.141592654, "pi" }, { 2.718281828, "e" }, { 53.00000000, "w" }, { 1.000000000, "eins" }, { 2.000000000, "zwoo" }, { 13.00000000, "drölf" }, }; // Anzahl der Feldelemente: const int l = sizeof(f)/sizeof(f[0]); // Testprogramm: int main( int nargs, char **args ) { qsort( f, l, sizeof(f[0]), vergl_f ); //for( int i=0; i<l; i++ ) // { // printf( "f[%2d]=%g\n", i, f[i].d ); // } while( 1 ) { double wert; printf( "Bitte einen Wert: " ); if( scanf( "%lf", &wert )!=1 ) { break; } s_t key = { wert, "" }; s_t *p = (s_t *)msearch( &key, f, l, sizeof(f[0]), vergl_f ); if( p ) { printf( "Gefunden: %f %s\n", p->d, p->s ); } else { printf( "nichts gefunden!\n" ); } } return 0; } /* main( int nargs, char **args ) */