ANSI C 1

4 FUNKCJE I STRUKTURA PROGRAMU

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

{

int i, last;

void swap(int v[], int i, int j);

if (left >= right) /* nic nie rób, jeśli tablica zawiera */ return; /* mniej niż dwa elementy */ swap(v, left, (left + right)/2); /* element podziału */ last = left;    /* przesuń do v[0] */

for (i = left+1; i <= right; i++) /* podział */ if (v[i] < v[left]) swap(v, ++last, i);

swap(v, left, last); /* odtwórz element podziału */ qsort(v, left, last—1); qsort(v, last+1, right);

}

Operację zamiany elementów miejscami napisaliśmy jako oddzielną funkcję, ponieważ trzy razy pojawia się w qsort.

I* swap: zamień miejscami v[i] i v[j] */ void swap(int v[], int i, int j)

{

int temp;

temp = v[i]; v[i] = v(ji; v[j] = temp;

}

W bibliotece standardowej występuje taka wersja funkcji qsort, która potrafi sortowa* obiekty dowolnego typu.

Rekurencja nie musi przynosić oszczędności pamięci, ponieważ trzeba gdzieś pt# chowywać stos używanych wartości. Nie przyspiesza też działania funkcji. Postać kurencyjna jest jednak bardziej zwarta i często łatwiejsza do napisania i zrozumiem-niż jej nierekurencyjny odpowiednik. Funkcje rekurencyjne nadają się zwłaszcza & obsługi rekurencyjnie zdefiniowanych struktur danych, np. drzew; w p. 6.5 zobacz) my dobry przykład takiego zastosowania.

4.11 PREPROCESOR JĘZYKA C

/    ■ I « I

Ćwiczenie 4.12. Zastosuj idee funkcji printd do napisania reknrencyineiŁi-e^.i.i tunkcji itoa, tj. zamieniającej liczbę całkowitą na ciąg cyfr za pomocą wywołania rekurencyjnego.

Ćwiczenie 4.13. Napisz rekurencyjną wersję funkcji reverse(s), która odwraca kolejność znaków tekstu w s.

Preprocesor języka C

C pozwala na pewne rozszerzenia języka za pomocą preprocesora, który jest pojęciowo oddzielnym, pierwszym krokiem tłumaczenia programu. Z tych rozszerzeń najczęściej są stosowane dwa: polecenie #include wstawienia zawartości pewnego pliku podczas kompilacji oraz definicja #define, umożliwiająca zastępowanie pewnego zwrotu dowolnym ciągiem znaków. Do innych rozszerzeń tu opisanych należą kompilacja warunkowa i makra z argumentami.

4.11-1 Wstawianie plików

Wstawianie plików ułatwia, między innymi, posługiwanie się zestawami deklaracji i definicji #define. Każdy wiersz źródłowy programu o postaci

#include "nazwa-pliku"

lub

#include <nazwa-pliku>

jest zastępowany zawartością pliku o wskazanej nazwie. Jeśli nazwa-pliku jest ograniczona cudzysłowami, poszukiwanie pliku zaczyna się tam, gdzie znaleziono właściwy program źródłowy. Jeśli w tym miejscu go nie ma lub jeśli nazwa-pliku jest zawarta między znakami < i >, to tego pliku szuka się zgodnie z zasadami obowiązującymi w danej implementacji. Wstawiany plik może sam zawierać wiersze #include.

Często kilka wierszy o takiej postaci pojawia się na początku pliku źródłowego; ich zadaniem jest dołączenie wspólnych definicji #define i deklaracji extern lub wprowadzenie deklaracji prototypów funkcji bibliotecznych ze standardowych nagłówków jak <stdio.h>. (Ściśle mówiąc, nie muszą być one plikami; szczegóły dotyczące dostępu do nagłówków są zależne od implementacji.)

Stosowanie #include jest zalecanym sposobem sporządzania deklaracji dla dużego programu. Gwarantuje to, że wszystkie pliki źródłowe będą zaopatrzone w te same definicje i deklaracje zmiennych, co eliminuje szczególnie złośliwy rodzaj błędów.

125