ANSI C 2

6 STRUKTURY

Warto tutaj omówić kilka spraw. Po pierwsze, deklaracja funkcji binsearch musi j* formować, że funkcja zwraca wskaźnik do struktury typu key, a nie wartość całkow, tą; jest to zadeklarowane zarówno w prototypie funkcji, jak i w binsearch. Jeże funkcja ta znajdzie słowo, to zwraca wskaźnik do niego, jeżeli nie - zwraca NULf

Po drugie, elementy tablicy keytab są teraz dostępne za pomocą wskaźników. To % wymaga znacznych zmian w funkcji binsearch.

Wartości początkowe zmiennych Iow i high są teraz wskaźnikami odnoszącymi się dr początku tablicy i miejsca tuż za koncern tablicy.

Obliczenie środkowego elementu nie może już być takie proste mid = (low+high) / 2    /* ŹLE */

ponieważ dodawanie do siebie wskaźników jest niedozwolone. Odejmowanie natomiast jest dozwolone: high-low oznacza liczbę elementów między wskaźnikami a więc

mid = Iow + (high-low) / 2

ustawia mid tak, aby wskazywał element położony w połowie odległości między Iow i high.

Najpoważniejszą zmianą jest zaprojektowanie algorytmu tak, by z całą pewnością nie generował niepoprawnego wskaźnika lub by nie próbował odwoływać się do elementu spoza tablicy. Problem polega na tym, że oba adresy &tab[-1] i &tab[n] leżą poza granicami tablicy tab. Pierwszy z nich jest całkowicie błędny, błędem będzie również odwołanie pośrednie poprzez ten drugi. W definicji języka zagwarantowano jednak że arytmetyka na wskaźnikach zadziała poprawnie dla pierwszego elementu poza końcem tablicy (to znaczy &tabfn]).

W funkcji main napisaliśmy

for (p = keytab; p < keytab + NKEYS; p^-t-)

Jeśli p jest wskaźnikiem do struktury, to wszelkie związane z nim obliczenia wykonu-je się z uwzględnieniem rozmiaru tej struktury. Zatem p++ zwiększa wskaźnik o po trzebną wielkość tak, aby otrzymać następny element tablicy struktur, a sprawdzeni? warunku zatrzymuje pętlę we właściwym momencie.

Nie spodziewaj się jednak, że rozmiar struktury jest prostą sumą rozmiarów jej składowych. Ze względu na wymagania, stawiane przez różne obiekty na położenie w pamięci, może się okazać, że w strukturze będą nienazwane „dziury”. A zatem, jeśli n przykład typ char zajmuje jeden bajt, a typ int cztery bajty, to struktura

struct { char c; int i;

oowered by

Mi sio!

};

może - zamiast pięciu - równie dobrze wymagać ośmiu bajtów. Za pomocą operatora sizeof otrzymuje się właściwy rozmiar obiektu.

Na koniec krótka uwaga dotycząca formy pisania programów. Jeżeli funkcja zwraca wartość o skomplikowanym typie, powiedzmy wskaźnik do struktury, np.

struct key *binsearch(char *word, struct key *tab, int n)

to w takiej formie trudno zauważyć nazwę funkcji lub znaleźć ją za pomocą edytora tekstów. Niekiedy więc stosuje się alternatywny styl zapisu:

struct key *

binsearch(char *word, struct key *tab, int n)

Jest to rzecz gustu: wybierz ten styl, który lubisz, i stosuj go konsekwentnie.

Struktury odwołujące się do samych siebie

Przypuśćmy, że chcemy rozwiązać bardziej ogólny problem zliczania wystąpień wszystkich słów jakiegoś tekstu wejściowego. Lista słów nie jest z góry znana, nie możemy więc ich tak łatwo uporządkować i skorzystać z funkcji wyszukiwania metodą bisekcji. Nie możemy też dla każdego nadchodzącego słowa stosować przeszukiwania liniowego, by sprawdzić, czy już wcześniej wystąpiło; nasz program pracowałby zbyt długo. (Dokładniej: należy oczekiwać, że czas działania programu rośnie proporcjonalnie do kwadratu liczby słów wejściowych.) Jak zatem mamy zorganizować nasze dane, aby skutecznie uporać się z listą dowolnych słów?

Jednym z rozwiązań jest sortowanie na bieżąco listy dotychczas wczytanych słów, wstawiając każde nowe słowo we właściwe miejsce listy. Nie należy tego robić przesuwając słowa w tablicy liniowej - to także zajmuje dużo czasu. Zastosujemy strukturę danych, którą zwykle nazywa się drzewem binarnym.

Drzewo składa się z „węzłów”, po jednym dla każego różnego słowa; każdy węzeł zawiera:

•    wskaźnik do tekstu słowa,

•    licznik krotności wystąpień,

•    wskaźnik do węzła lewego potomka,

•    wskaźnik do węzła prawego potomka.

187