ANSI C 0

4 FUNKCJE I STRUKTURA PROGRAMU--------------

zamiast

int Iow, high, mid;

Iow = 0; high = n - 1;

A więc inicjowanie zmiennych jest w istocie skróconym zapisem instrukcji przypisania. Wybór jednego z tych sposobów jest kwestią stylu. Dotychczas na ogół stosowaliśmy jawne przypisania, gdyż wartości początkowe w deklaracjach są mniej widoczne i położone daleko od miejsca użycia zmiennych.

Tablicę można zainicjować umieszczając po jej deklaracji znak równości, a następnie - w nawiasach klamrowych - listę wartości początkowych rozdzielonych przecinkami. Na przykład, aby zainicjować tablicę days liczbami dni przypadającymi na każdy miesiąc, można napisać tak:

int days[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

Jeżeli w deklaracji tablicy pominięto jej rozmiar, to kompilator obliczy jej długość na podstawie liczby podanych wartości początkowych, w tym przypadku 12.

Jeśli liczba wartości początkowych jest mniejsza od podanego rozmiaru tablicy, to brakujące elementy w zmiennych zewnętrznych, statycznych i automatycznych otrzymają wartość zero. Podanie zbyt wielu wartości początkowych jest błędem. Nie ma sposobu ani na sformułowanie powtórzeń wartości początkowej, ani na zainicjowanie środkowego elementu tablicy bez podania wszystkich wartości pośrednich.

Tablice znakowe mogą być inicjowane w szczególny sposób: zamiast nawiasów klamrowych i listy wartości z przecinkami można użyć stałej napisowej:

char patternf] = "nie”;

jest skróconym zapisem równoważnej deklaracji char pattern[] = {'n’, T, *e\ ^0’ };

W tym przypadku rozmiar tablicy wynosi 4 (trzy znaki wzorca plus znacznik końca tekstu ’\0’).

Funkcje języka C mogą być wywoływane rekurencyjnie, tzn. funkcja może wywofe samą siebie zarówno bezpośrednio, jak i pośrednio. Rozważmy wypisywanie liczb) w postaci ciągu znaków. Jak już wcześniej wspomnieliśmy, cyfry generuje się w od'

4.10 REKURENCJA____

wrotnej kolejności: mniej znaczące cyfry są znane przed bardziej winny być wypisane po tych ostatnich.

Istnieją dwa rozwiązania tego problemu. Jednym z nich jest zapamiętanie cyfr w tablicy w kolejności ich generowania, a następnie wypisanie ich w odwrotnym porządku. Tak właśnie zrobiliśmy w funkcji itoa z p. 3.6. Alternatywą jest rozwiązanie rekuren-cyjne, w którym funkcja printd najpierw wywołuje samą siebie dla uzyskania cyfr początkowych, a następnie wypisuje cyfrę końcową. Także ta wersja może działać niepoprawnie dla największej możliwej liczby ujemnej.

#include <stdio.h>

/* printd: wypisz n dziesiętnie */ void printd(int n)

{

if (n < 0) { putcharf-); n = -n;

}

if (n / 10)

printd(n / 10); putchar(n % 10 + ’0’);

}

Gdy funkcja wywołuje rekurencyjnie samą siebie, wówczas każde jej wznowienie otrzymuje nowy komplet wszystkich zmiennych automatycznych, niezależny od poprzedniego. Po wywołaniu printd(123) pierwsza funkcja printd otrzymuje więc argument n o wartości 123. Następnie przekazuje drugiej funkcji printd argument 12, która z kolei przekazuje trzeciej wartość 1. Funkcja printd z trzeciego poziomu wypisuje 1 i wraca na drugi poziom. Tutejsza printd wypisuje 2 i wraca na poziom pierwszy. Ta zaś printd wypisuje 3 i kończy działanie.

Innym dobrym przykładem rekurencji jest algorytm porządkowania „ąuicksort” (szybkie sortowanie), który wymyślił C. A. Hoare w 1962 r. Dla danej tablicy wybiera się jeden element, a pozostałe rozdziela na dwa podzbiory - tych elementów, które są mniejsze od wybranego, i tych, które są od niego większe lub są mu równe. Następnie proces ten powtarza się rekurencyjnie dla każdego z podzbiorów. Gdy podzbiór ma mniej niż dwa elementy, nie potrzebuje już być porządkowany; osiągnięcie tego stanu kończy rekurencję.

Nasza wersja algorytmu szybkiego sortowania nie jest najszybszą z możliwych, ale jest jedną z najprostszych. W naszym rozwiązaniu elementem podziału każdej tablicy na dwie „podtablice” jest element środkowy.

123