ANSI C 5

6 STRUKTURY-----------—

postępowanie polega najpierw na zadeklarowaniu malloc jako funkcji zwracającej wskaźnik do typu void, a następnie na wymuszeniu właściwego typu tego wskaźnika za pomocą operacji rzutowania. Funkcja malloc i procedury pokrewne są zadeklarowane w standardowym nagłówku <stdlib.h>. A zatem naszą funkcję talloc można napisać tak:

tinclude <stdlib.h>

/* talloc: utwórz węzeł */ struct tnode *talloc(void)

{

return (struct tnode *) malloc(sizeof(struct tnode));

}

Funkcja strdup po prostu kopiuje tekst ze swojego argumentu w bezpieczne miejsce, otrzymane również przez wywołanie funkcji malloc:

I* strdup: sporządź kopię s */ char *strdup(char *s)

{

char *p;

p = (char *) malloc(strlen(s)+1); /* +1 dla ’\0’ */ if (p != NULL) strcpy(p, s); return p;

}

Funkcja malloc zwraca NULL, jeśli brakuje miejsca w pamięci; funkcja strdup przekaże tę wartość dalej, pozostawiając obsługę takich błędów procedurze wywołującej.

Pamięć otrzymaną za pomocą malloc można zwolnić do ponownego użycia, wywołując funkcję free; zajrzyj do rozdz. 7 i 8.

Ćwiczenie 6.2. Napisz program, który czyta tekst programu napisanego w C i wypisuje w porządku alfabetycznym wszystkie grupy nazw zmiennych o identycznych sześciu początkowych znakach i różniących się którymkolwiek z dalszych znaków. Nie zliczaj słów występujących w stałych napisowych i w komentarzach. Niech liczba 6 będzie parametrem, który można zmienić w wierszu wywołania programu.

Ćwiczenie 6.3. Napisz program tworzący skorowidz, tj. wypisujący Bst^jyL^^ stkich słów dokumentu i dla każdego słowa listę numerów wierszy, w którycl to słowo wystąpiło. Ze skorowidza usuń słowa-ozdobniki w rodzaju „ten [ „lub” itp.

Ćwiczenie 6.4. Napisz program, który zlicza różne słowa podane na wejściu i wypisuje je uporządkowane według malejącej krotności ich wystąpień. Każde słowo poprzedź jego krotnością.

Przeglądanie tablic

Aby zilustrować dalsze właściwości struktur, napiszemy teraz pakiet podprogramów służących do przeglądania tablic. Będą to typowe narzędzia, z jakimi możemy się zetknąć przy obsłudze tablic symboli w makrogeneratorach i kompilatorach. Jako przykład weźmy instrukcję #define. Po napotkaniu wiersza w rodzaju:

#define IN 1 /* wewnątrz */

nazwa IN i zastępujący ją tekst 1 zostaną zapamiętane w odpowiedniej tablicy. Od tej pory, jeżeli nazwa IN pojawi się w jakiejś instrukcji, np.

State = IN; /* stan */

to musi być zastąpiona przez znak 1.

Mamy dwie procedury działające na nazwach i zastępujących je tekstach. Funkcja install(s,t) rejestruje nazwę s i odpowiadający jej tekst t w pewnej tablicy; s oraz t są po prostu ciągami znaków. Druga funkcja - lookup(s) - przegląda tę tablicę w poszukiwaniu nazwy s i zwraca wskaźnik do miejsca, w którym znaleziono nazwę, lub NULL, jeżeli takiej nazwy nie ma w tablicy.

Zastosujemy algorytm przeszukiwania rozproszonego (ang. hash)\ nadchodzącą nazwę przekształca się na pewną niewielką liczbę nieujemną (wartość rozproszenia), której następnie używa się do indeksowania tablicy wskaźników. Element tablicy wskazuje na początek połączonej w łańcuch listy opisów nazw z tą samą wartością rozproszenia. Jest on równy NULL, jeśli nie ma nazwy o takiej wartości.

0

0

nazwa

teksi

0

nazwa

tekst

¹³ - Język ANSI C 193