ANSI C 0

5 WSKAŹNIKI I TABLICE --------

ten program tak, aby najlepiej wykorzystywał dostępną mu pamięć: wiersze powinny być gromadzone podobnie jak w programie sortującym z p. 5.6, nie zaś w dwuwymiarowej tablicy o stałym rozmiarze.

Wskaźniki do funkcji

Funkcje w języku C same nie są zmiennymi, ale istnieje możliwość definiowania wskaźników do funkcji. Takim wskaźnikom można nadawać wartości, umieszczać je w tablicach, przekazywać do funkcji, zwracać je jako wartość funkcyjną itp. Wyjaśnimy to dokładniej, zmieniając program sortowania napisany wcześniej w tym rozdziale: podanie opcji -n spowoduje, że program będzie porządkował wiersze wejściowe numerycznie, a nie leksykograficznie.

Sortowanie często składa się z trzech części: porównania ustalającego porządek między każdymi dwoma obiektami, zamiany przestawiającej te obiekty oraz algorytmu sortowania dokonującego porównań i zamian aż do uporządkowania obiektów we właściwej kolejności. Algorytm sortowania nie zależy od sposobu porównywania i zamieniania, zatem - przyłączając różne funkcje porównujące i zamieniające - możemy przeprowadzić porządkowanie według różnych kryteriów. Ten chwyt zastosujemy w naszym nowym programie sortującym.

Jak poprzednio, porównania leksykograficznego dwóch wierszy dokona funkcja strcmp; będziemy więc potrzebować funkcji numcmp, która porówna dwa wiersze na podstawie ich wartości liczbowych i da odpowiedź tego samego rodzaju, co funkcja strcmp. Funkcje te są zadeklarowane przed funkcją main, a wskaźnik do właściwej zostanie przekazany funkcji qsort. Celowo opuściliśmy obsługę błędów w argumentach, aby skupić się na głównym zadaniu.

#include <stdio.h>

#include <string.h>

#define MAXLINES 5000    /* maks. liczba wierszy do sortowania */

char *lineptr[MAXLINES]; /* wskaźniki do wierszy tekstu */

int readlines(char *lineptr[], int nlines); void writelines(char *lineptr[], int nlines);

void q$ort(void *lineptr[], int left, int right, int (*comp)(void *, void *)); int numcmp (char *, char *);

I* uporządkuj wiersze z wejścia */

_pQwered_b.y

Mi si ol

main(int argc, char *argv[ ])

{

int nlines; /* liczba wczytanych wierszy */

int numeric = 0; /* 1, jeśli sortowanie numeryczne */

if (argc > 1 && strcmp(argv[1], ”-n”) == 0) numeric = 1;

if ((nlines = readlines(lineptr, MAXLINES)) >= 0) { qsort((void **) lineptr, 0, nlines-1,

(int (*)(void*, void*)) (numeric ? numcmp : strcmp)); writelines (lineptr, nlines); return 0;

} else {

printffza dużo wierszy do sortowania\n”); return 1;

}

}

W wywołaniu funkcji qsort nazwy strcmp i numcmp reprezentują adresy tych funkcji. Są one znane jako funkcje, toteż operator adresu & jest zbędny, tak samo jak nie jest potrzebny przed nazwą tablicy.

Funkcję qsort napiszemy tak, aby mogła operować na danych dowolnego typu, a nie tylko na tekstach. Jak wynika z prototypu funkcji, qsort oczekuje argumentów, którymi są: tablica wskaźników, dwie liczby całkowite oraz funkcja porównująca o dwóch argumentach wskaźnikowych. Dla argumentów wskaźnikowych zastosowano ogólny typ void *. Za pomocą operacji rzutowania dowolny wskaźnik można przekształcić do typu void * i z powrotem bez utraty informacji, wobec tego funkcję qsort możemy wywoływać z dowolnymi argumentami, stosując rzutowanie do typu void *. Szczegółowy rzut argumentu funkcyjnego dopasowuje argumenty funkcji porównującej do prototypu qsort. Dla faktycznej reprezentacji argumentów nie ma to żadnego znaczenia, ale upewnia kompilator, że wszystko jest w porządku.

/* qsort: uporządkuj v[left]...v[right] rosnąco */ void qsort(void *v[], int left, int right,

int (*comp) (void *, void *))

{

int i, last;

void swap(void *v[ ], int, int);

163