ANSI C 4

6 STRUKTURY

Funkcja addtree jest rekurencyjna. Funkcja main wprowadza wczytane słowo na najwyższy poziom (korzeń) drzewa. Na każdym etapie słowo to jest porównywane ze słowem uprzednio zapamiętanym w danym węźle i, jeśli trzeba, przesłane w dół do lewego lub prawego poddrzewa poprzez rekurencyjne wywołanie funkcji addtree. Szukane słowo może już występować w drzewie, wówczas jest zwiększany jego licznik. Napotkanie zerowego wskaźnika poddrzewa oznacza, że trzeba utworzyć i w tym miejscu dołączyć do drzewa nowy węzeł. Po utworzeniu nowego węzła funkcja addtree zwraca jego adres, który jest wstawiany zamiast zerowego wskaźnika w węźle przodka.

struct tnode *ta!loc(void); char *$trdup(char *);

/* addtree: dodaj węzeł dla w; szukaj w p lub poniżej p */ struct tnode *addtree(struct tnode *p, char *w)

{

int cond;

if (p == NULL) { I* w jest nowym słowem */ p = talloc();    /* utwórz nowy węzeł */

p->word = strdup(w); p->count = 1; p—>left = p—>right = NULL;

} else if ((cond = strcmp(w, p->word)) == 0) p->count++; /* powtórzone słowo */ else if (cond < 0) /* mniejsze: do lewego poddrzewa */ p->left = addtree(p->left, w); else    /* większe: do prawego poddrzewa */

p->right = addtree(p->right, w); return p;

}

Pamięć dla nowego węzła udostępnia funkcja talloc, która zwraca wskaźnik do wolnego obszaru pamięci wystarczającego na przechowanie węzła. Nowe słowo jest kopiowane w bezpieczne miejsce przez funkcję strdup. (Dokładniej zajmiemy się tymi funkcjami za chwilę.) Wskaźnik do tego miejsca zapamiętuje się w węźle, inicjuje licznik wystąpień słowa oraz zeruje oba wskaźniki potomków. Ten fragment programu jest wykonywany tylko dla liści drzewa, gdy dodaje się nowy węzeł. Pominęliśmy tu (nieostrożnie) obsługę błędów sygnalizowanych wartościami zwracanymi przez funkcje strdup i talloc.

1 6.5 STRUKTURY ODWOŁUJĄCE SIĘ DO SAMYCH SIEBIE

funkcja treeprint wypisuje zawartość drzewa w uporządkowanej kolejne dego węzła zostanie najpierw wypisane jego lewe poddrzewo (wszystkie słowa mniejsze niż słowo w tym węźle), potem słowo tego węzła, a następnie jego prawe poddrzewo (wszystkie słowa większe). Jeśli nie czujesz się pewnie w rekurencji, sprawdź, ak działa treeprint dla narysowanego wcześniej drzewa.

/* treeprint: wypisz uporządkowane drzewo p */ void treeprint(struct tnode *p)

{

if (p != NULL) { treeprint(p->left);

printf(”%4d %s\n”, p->count, p->word); treeprint(p->right);

}

}

Uwaga praktyczna: jeżeli drzewo staje się „niezrównoważone” z tego powodu, że słowa nadchodzą w nieprzypadkowej kolejności, to czas działania programu może być coraz dłuższy. W najgorszym przypadku, gdy nadchodzące słowa są już uporządkowane, program w sposób bardzo kosztowny symuluje przeszukiwanie liniowe. Istnieją konstrukcje ogólniejsze od drzew binarnych, przy których nie odczuwa się skutków takiego „złego zachowania się” danych, ale nie będziemy ich tu opisywać.

Zanim opuścimy ten przykład, jeszcze jedna dygresja dotycząca problemu przydziału pamięci. Oczywiście dobrze byłoby, gdyby w programie znajdował się tylko jeden dystrybutor pamięci - nawet wtedy, kiedy przydziela pamięć różnym obiektom. Ale jeśli ten jeden dystrybutor ma realizować żądania dotyczące, powiedzmy, wskaźników do znaków i wskaźników do struktury tnode, to musimy najpierw odpowiedzieć na dwa pytania. Po pierwsze, jak uwzględnić ograniczenia występujące w większości maszyn, dotyczące położenia różnego rodzaju obiektów w pamięci (na przykład liczby całkowite często muszą być umieszczane pod parzystym adresem)? I po drugie, jaka deklaracja poradzi sobie z tym, że dystrybutor z konieczności musi zwracać różne rodzaje wskaźników?

Ograniczenia dotyczące położenia w pamięci można, kosztem jednak pewnej straty pamięci, łatwo ominąć. Wystarczy przyjąć, że dystrybutor zawsze przydziela pamięć spełniającą wszystkie ograniczenia. Funkcja alloc z rozdz. 5 nie gwarantuje spełnienia jakichkolwiek ograniczeń, skorzystamy więc ze standardowej, bibliotecznej funkcji talloc, która je respektuje. W rozdziale 8 pokażemy jeden ze sposobów realizacji fonkcji malloc.

tytanie dotyczące deklaracji typu takiej funkcji, jak malloc, jest drażliwe w każdym Jfcyku, który poważnie podchodzi do kontroli zgodności typów. W języku C właściwe

191