5. Dynamiczne przydzielanie pamięci

W języku C, jak w wielu innych językach programowania, są trzy różne sposoby przydzielania pamięci programowi. Jeśli potrzebna ilość pamięci lub przynajmniej jej rozsądne górne ograniczenie jest znane zawczasu, programista może spowodować przydzielenie pamięci przed wykonaniem programu. Jeśli zaś niezbędna ilość pamięci nie jest znana i może się wahać w szerokim zakresie lub gdy wymagania pamięciowe różnych części programu są zmienne, potrzebne jest dynamiczne przydzielanie pamięci, co oznacza, że pamięć będzie przydzielana i zwalniana w miarę potrzeb. Trzeci sposób przydzielania pamięci funkcjom będzie omówiony w rozdziale 7.
Ilość pamięci potrzebnej do przechowania zmiennych globalnych może być wyznaczona w czasie kompilacji programu i pamięć ta zostanie zarezerwowana przez kompilator. Aby uzyskać dostęp do nowego bloku pamięci podczas działania programu, trzeba wywołać funkcję malloc (), przekazując jej jako parametr ilość żądanej pamięci. Funkcja malloc () przydziela tę pamięć z obszaru zwanego kopcem (ang. heap) i zwraca wskaźnik do niej. Kopiec jest specjalnym fragmentem pamięci przeznaczonym do tego celu. Jeśli kopiec nie może udostępnić wymaganej ilości pamięci, malloc () zwraca wartość NULL. Typem zwracanej wartości jest wskaźnik do void, więc trzeba wykonać jej konwersję na wskaźnik do odpowiedniego typu.
Kiedy program wykorzystał już przydzieloną pamięć, można ją zwrócić na kopiec, używając funkcji free (). Programista musi mieć pewność, że żaden wskaźnik w programie nie zawiera odwołania do komórki pamięci wewnątrz zwolnionego bloku; próba dostępu do takiej komórki spowoduje błąd. Niestety, błąd ten może nie zostać wykryty w chwili niedozwolonego dostępu, ale spowodować kłopoty w późniejszym czasie. Dlatego właśnie błędy tego typu bywają bardzo trudne do wyśledzenia.

5.1. Listy

Wykorzystanie mechanizmu dynamicznego przydziału pamięci daje programiście swobodę tworzenia dynamicznych wiązanych struktur danych. Wiązana struktura danych różni się od ciągłej (tablicy) tym, że nie zakłada się tu, iż następny element
#80
w strukturze mieści się w pamięci bezpośrednio za bieżącym. W przypadku tablic założenie to jest kluczowe przy wyszukiwaniu. Aby znaleźć konkretny element w strukturze, możemy wyliczyć jego pozycję i sięgnąć bezpośrednio do niego. W wyszukiwaniu binarnym obliczenie średniej z pozycji pierwszego i ostatniego elementu daje lokalizację środkowego, ponieważ są one rozmieszczone w pamięci kolejno.
Wadą ciągłej struktury danych jest trudność dodania lub usunięcia elementu z jej środka. Zrobienie tego wymaga przesunięcia wszystkich dalszych elementów o jedną pozycję, jeśli ustalony porządek ma być zachowany. Jeśli jednak odrzucimy wymaganie, że elementy są umieszczone kolejno, to już tak nie jest. W wiązanej strukturze danych każdy element oprócz swoich danych zawiera dowiązanie - informację, gdzie jest przechowywany element następny. Aby dodać nowy element w środku struktury, umieszczamy nowe dane gdziekolwiek w pamięci i zmieniamy dowiązanie w elemencie, który ma poprzedzać nowy element, tak by wskazywało na ten nowy element. Dowiązanie w nowym elemencie musi wskazywać na następujący po nim. Czynności te można zrealizować w stałym czasie.
Strukturę wiązaną można zaimplementować w tablicy. Aby zaimplementować listę, każdy element tablicy musi mieć dwa pola: jedno do przechowywania danych, a drugie na dowiązanie, które przy implementacji tablicowej jest indeksem następnego elementu listy. Ponieważ pierwszy element listy nie musi być pierwszym elementem tablicy, potrzebujemy jakiejś zmiennej zawierającej indeks pierwszego elementu listy. Nowy element wstawiamy, znajdując wolne miejsce w tablicy, wypełniając jego pole przeznaczone na dane i zmieniając odpowiednie dowiązania. Dowiązaniem nowego elementu staje się indeks elementu, który powinien być jego następnikiem na liście, a dowiązaniem jego poprzednika staje się pozycja nowego elementu. Pole przeznaczone na dowiązanie w ostatnim elemencie listy musi zawierać specjalną wartość, na przykład -1, informującą, że lista nie ma już kolejnych elementów. Na rysunku 5.1 widać zawartość podwójnej tablicy przechowującej listę (1 3 4 10). Wartości oznaczone * są niezdefiniowane, data[] zawiera właściwą listę elementów, a next[] - indeks w tablicy kolejnego elementu listy. Pierwszy element listy, 1, jest umieszczony w data[2]. Drugi element, 3, mieści się na pozycji zapisanej w next[2], czyli 0; data[0] zawiera 3. Wartość next[0] to 6, więc trzeci element, 4, mieści się w data[6]. Na pozycji next[6] znajduje się liczba 3 - indeks czwartego elementu listy, 10, przechowywanego w data[3]. Ponieważ next[3] zawiera -1, oznacza to koniec listy.

i; data[i]; next[i]
0; 3; 6
1; *; *
2; 1; 0
3; 10; -1
4; *; *
5; *; *
6; 4; 3

Rys. 5.1. Lista (1 3 4 10) przechowywana w tablicy
#81
Jeśli elementy nigdy nie są usuwane z listy, to wolne miejsce łatwo znaleźć, zapamiętując liczbę wykorzystanych miejsc w tablicy, jeżeli elementy są umieszczane na kolejnych pozycjach, zaczynając od początku tablicy. Nowy element jest umieszczany na pierwszym wolnym miejscu, a licznik jest zwiększany. Jeśli dopuszczamy usuwanie elementów, to zajęte miejsca mogą nie zajmować ciągłego obszaru, a tablica może zawierać luki. Wtedy zwykle przechowuje się drugą listę, zwaną listą wolnych miejsc, zawierającą nie wykorzystane pozycje w tablicy. Na rysunku 5.2 widać tę samą listę (1 3 4 10), zaczynającą się od pozycji 2, oraz wolne miejsca w tablicy, powiązane w listę zaczynającą się na pozycji 5. Zauważmy, że zarówno koniec właściwej listy, jak i koniec listy wolnych miejsc rozpoznaje się po tym, że next[] = -1.

i; data[i]; next[i]
0; 3; 6
1; *; 4
2; 1; 0
3; 10; -1
4; *; -1
5; *; 1
6; 4; 3
Rys. 5.2. Lista (1 3 4 10) wraz z listą wolnych miejsc

Znacznie popularniejsze jest stosowanie dynamicznie tworzonych struktur wiązanych, takich jak listy, ponieważ często używa się ich w sytuacjach, kiedy maksymalny rozmiar listy nie jest uprzednio znany. Każdy element listy jest strukturą o dwóch polach: jednym na dane, a drugim na dowiązanie, które jest w tym wypadku wskaźnikiem do następnego elementu listy. Ostatni element listy zawiera pusty wskaźnik - NULL. Dostęp do całej listy jest zapewniony przez wskaźnik do pierwszego elementu. Zaletą takiej struktury jest to, że element można dodać lub usunąć z listy w stałym czasie, a wadą to, że przeszukiwanie takiej listy musi się zaczynać od jej początku i postępować kolejno, nawet jeśli lista jest uporządkowana. Inną wadą wiązanej struktury danych w porównaniu z ciągłą jest konieczność przeznaczenia dodatkowej pamięci na dowiązania. Miejsce na elementy listy jest przydzielane w miarę potrzeb i nie musi zajmować ciągłego obszaru w pamięci komputera. Na rysunku 5.3 widać
#82
dynamiczną listę zawierającą elementy (1 3 4 10). Prostokąty symbolizują struktury o dwóch polach, a strzałki reprezentują wskaźniki do struktur. Ostatnie pole zawiera wskaźnik NULL, zaznaczony jako ukośna kreska.

Rys.5.3. Dynamiczna lista (1 3 4 10)

/* database.h */
#ifndef DATABASE
#def ine DATABASE
#include
#include "dbdefs.h"

typedef struct dbrec {
dbkeytype key;
dbdatatype data;
struct dbrec *next;
} *Dbrec;

typedef struct {
struct dbrec *it, *prior;
} indextype;

int findRec(Dbrec *,dbkeytype, dbdatatype *, indextype *);
int createRec(Dbrec*, dbkeytype, dbdatatype, indextype*);
void setRec (Dbrec * ,indextype, dbdatatype);
void eachRec(Dbrec *, void (*) (indextype, dbdatatype));
void initDb(Dbrec *);

#define getKey(idx) ((idx).it->key)
#define getData(idx) ((idx).it->data)
#endif

Rys. 5.4. Plik database.h dla list

Listy można użyć do implementacji ATD-prostej bazy danych. Baza danych będzie przechowywana na liście uporządkowanej (można by także użyć listy nieuporządkowanej). Każdy element listy musi zawierać klucz, dane i wskaźnik do następnego elementu listy -pole next. Przypomnijmy, że funkcja findRec () zwraca informację o lokalizacji rekordu w bazie danych, wykorzystywaną przy innych operacjach: addRec (), setRec () i deleteRec (). Widać, że informacja ta musi zawierać wskaźnik do elementu listy przechowującego klucz i dane. Aby jednak usunąć element z listy, potrzebujemy wskaźnika do elementu, który ma być usunięty, a także do poprzedzającego go elementu, gdyż trzeba zmienić jego wskaźnik next tak, by wskazywał na element następny po usuniętym. Z tego powodu indeks zwracany przez findRec () będzie składał się z pary wskaźników: jednego do samego elementu i drugiego do elementu wskazującego na szukany. Jeśli poszukiwany element jest pierwszy na liście, to wskaźnik do poprzedniego elementu jest równy NULL, jeśli zaś w ogóle nie ma go w bazie danych, to wskaźnik do elementu będzie faktycznie
#83
wskazywał na pierwszy element o kluczu większym niż dany, a wskaźnik do poprzedniego będzie wskazywał na jego poprzednik na liście. Plik database . h jest pokazany na rysunku 5.4. Plik dbdefs .h zawiera definicje specyficzne dla tej implementacji. Odrzuciliśmy założenie, że będzie używana tylko jedna baza danych, więc program główny musi deklarować zmienne dla każdej bazy i jawnie je inicjować, wywołując funkcję initDb(). Każda z funkcji bazy danych została wzbogacona nowym parametrem, wyszczególniającym bazę, na której ma działać. Dodaliśmy makrodefinicje getKey() i getData(), którym przekazuje się indeks rekordu bazy danych, a one zwracają odpowiednio klucz i dane tego rekordu.
Najpierw musimy zaimplementować funkcję findRec (). Funkcja ta, rozpoczynając od początku listy, kolejno sprawdza klucze wszystkich elementów, dopóki nie dojdzie do końca listy lub nie znajdzie elementu o kluczu większym bądź równym szukanemu. Główna różnica między tą procedurą a liniowym przeszukiwaniem tablicy polega na sposobie przechodzenia do następnego elementu i sprawdzenia, czy jesteśmy na końcu listy. W wyszukiwaniu liniowym trzeba było jedynie zwiększyć indeks lub wskaźnik i sprawdzić, czy nadal wskazuje on na element tablicy. Aby znaleźć następny element na liście, musimy pójść za wskaźnikiem przechowywanym w polu next. Koniec listy następuje, kiedy wskaźnik ten staje się równy NULL. Kolejną różnicą między algorytmami jest to, że teraz musimy zapamiętywać element poprzedzający element bieżący na zmiennej prior, zawierającej poprzednią wartość wskaźnika do elementu bieżącego. Rysunek 5.5 zawiera kod implementujący funkcję findRec (). Zakładamy, że baza danych jest przechowywana na uporządkowanej liście wskazywanej przez db. Początkową wartością zmiennej prior jest NULL.
Aby wstawić nowy rekord do bazy danych, musimy utworzyć nowy element listy. Wymaga to wywołania funkcji malloc (). Funkcji tej przekazuje się rozmiar obiektu, który ma zostać utworzony, a zwraca ona wskaźnik do nowo przydzielonego bloku pamięci. Do wyznaczenia potrzebnej ilości pamięci używamy funkcji sizeof (), która dla danego typu danych lub zmiennej tego typu zwraca ilość pamięci niezbędną do przechowania jednego obiektu tego typu. Po przydzieleniu pamięci dokonujemy konwersji otrzymanego wskaźnika, by wskazywał na obiekt typu Dbrec. Klucz i dane są kopiowane do nowego rekordu, a następnie nowy element trzeba włączyć do listy. Na rysunku 5.6 widać, które dowiązania trzeba zmienić, aby wstawić nowy element 7 na listę (1 3 4 10).
Informacja dotycząca wskaźników, które trzeba zmienić, jest przechowywana w idx, parametrze zwracanym przez funkcję findRec (). Zawiera on wskaźnik do pierwszego elementu o kluczu większym niż dany klucz (lub NULL, jeśli nie ma takiego) oraz wskaźnik do elementu go poprzedzającego (lub ostatniego elementu listy, jeśli nie ma elementu o kluczu większym niż dany). Wskaźnik do poprzedniego elementu jest równy NULL, jeśli nowy rekord ma być wstawiony na początek listy. Aby nowy element został wstawiony na listę, musimy ustawić jego wskaźnik next na następny element (być może NULL) oraz zaktualizować wskaźnik next poprzedniego elementu. Jeśli wskaźnik do poprzedniego elementu jest równy NULL, zamiast tego trzeba poprawić wskaźnik do całej listy. Rysunek 5.7 zawiera kod funkcji createRec (). Zwraca ona wartość 0, jeśli zabrakło pamięci, a wartość 1, jeśli element został dodany do listy.
#84

int findRec (Dbrec *db, dbkeytype key, dbdatatype *data, indextype *idx)
/* Warunek wstępny: Klucze rekordów są uporządkowane.
Działanie: Szuka klucza na liście rekordów. Zwraca 1, jeśli klucz został znaleziony, 0 w przeciwnym razie. Jeśli rekord został znaleziony, data wskazuje na jego dane, a ( *idx) ->it na ten rekord. Jeśli nie, (*idx)->it wskazuje na rekord o kluczu bezpośrednio większym niż key (być może NULL). W obu przypadkach (*idx)->prior wskazuje na rekord poprzedzający (*idx)->it (być może NULL). */
{
Dbrec rec=*db, prior=NULL;
int cmp;

while(rec && (cmp=comparedbkey(key, rec->key)) > 0) {
/* Niezmiennik: (1) Wszystkie klucze na liście db aż do rec (ale nie uwzględniając go) są mniejsze niż key.
(2) prior wskazuje na rekord poprzedzający rec na liście . */
prior = rec;
rec = rec->next;
}
idx->it = rec;
idx->prior = prior;
if (rec && cmp==0) {
copydbdata(rec->data, *data);
return 1;
}
return 0;
}

Rys. 5.5. Funkcja findRec ()

Aby usunąć rekord, musimy zmienić wskaźnik z poprzedniego elementu, tak by wskazywał element następny po usuniętym, i zwolnić pamięć zajmowaną przez usuwany element. Jeśli poprzedni element nie istnieje, to trzeba przestawić wskaźnik db na nowy pierwszy element listy. Kod tej funkcji jest pokazany na rysunku 5.8.

Rys. 5.6. Wstawienie elementu 7 na listę (1 3 4 10)
#85

int createRec (Dbrec *db, dbkeytype key, dbdatatype data, indextype idx)
/* Warunek wstępny: idx->prior wskazuje na rekord, za który trzeba wstawić nowy (jeśli jest równy NULL, to nowy rekord należy wstawić na początek listy) . idx->it wskazuje na rekord następny za idx->prior.
Działanie: Jeśli baza danych nie jest przepełniona, dodaje rekord o kluczu key i danych data i zwraca wartość 1. W przeciwnym razie zwraca 0. */
{
Dbrec rec;

rec=(Dbrec)malloc(sizeof(struct dbrec));
if (rec==NULL)
return 0;
copydbkey(key, rec->key);
copydbdata(data, rec->data);
rec->next=idx.it;
if (idx.prior)
idx.prior->next =rec;
else
*db = rec;
return 1 ;
}

Rys. 5.7. Funkcja createRec ()

void deleteRec (Dbrec *db, indextype idx)
/* Warunek wstępny: idx->it wskazuje na rekord do usunięcia. idx->prior wskazuje rekord poprzedzający go lub NULL, jeśli takiego nie ma.
Warunek końcowy: idx->it jest usunięty. */
{
if (idx.prior)
idx.prior->next = idx.it->next;
else
*db = idx.it->next;
free((void*)idx.it);
}

Rys. 5.8. Funkcja deleteRec()

Funkcje initDb (), eachRec () i setRec () są proste, a ich kod jest zamieszczony na rysunku 5.9.
#86

void initDb(Dbrec *db)
/* Tworzy pustą bazę danych *db. */
{
*db = NULL;
}

void eachRec(Dbrec *db, void (*fn)(dbkeytype, dbdatatype))
/* Wykonuje funkcję fn dla każdego rekordu w *db. */
{
Dbrec rec ;

for (rec=*db; rec; rec=rec->next)
(*fn)(rec->key, rec->data);
}

void setRec(Dbrec *db, indextype idx, dbdatatype data)
/* Zmienia dane w rekordzie idx na data. */
{
copydbdata(data, idx.it->data);
}

Rys. 5.9. Funkcje: initDb() , eachRec () i setRec ()

5.1.1. Listy dwukierunkowe

Listę można przechodzić tylko w jedną stronę, ponieważ każdy element zawiera wskaźnik jedynie do następnego elementu listy. W zastosowaniach, w których listę trzeba przebiegać w obu kierunkach, wygodnie jest dla każdego elementu przechowywać zarówno wskaźnik do następnego, jak i poprzedniego elementu. Taką listę (zob. rys. 5.10) nazywamy listą dwukierunkową, a pole przeznaczone na drugi wskaźnik ma nazwę prev. Wskaźnik prev dla pierwszego elementu listy będzie równy NULL. Listę taką można przejść od końca do początku, idąc po wskaźnikach prev. Zazwyczaj w programie zapamiętujemy zarówno pierwszy, jak i ostatni element listy.
Jeśli do implementacji prostej bazy danych użyjemy listy dwukierunkowej, to indeks zwracany przez findRec () może zawierać jedynie wskaźnik do elementu o szukanym kluczu (jeśli taki klucz jest) lub do następnego elementu (jeśli elementu o danym kluczu nie ma w bazie). Dostęp do poprzednika, niezbędny przy wstawianiu

Rys. 5.10. Lista dwukierunkowa
#87
lub usuwaniu, zapewnia wskaźnik prev tego elementu. Sama operacja wstawiania lub usuwania elementu nieco się jednak komplikuje, ponieważ trzeba zmienić cztery wskaźniki zamiast dwóch. Napisanie kodu tych operacji pozostawiamy czytelnikowi.

5.1.2. Listy cykliczne

Wadą stosowania list jednokierunkowych jest to, że mając dany wskaźnik do elementu listy, możemy dotrzeć do elementów następujących po nim, ale nie do poprzedzających go. Zastosowanie listy dwukierunkowej jest jednym z rozwiązań tego problemu. Czasem jednak nie potrzebujemy przechodzić listy wstecz, a jedynie mieć dostęp z każdego elementu do wszystkich innych. Program może na przykład przechowywać wskaźniki do wielu elementów listy (niekoniecznie do pierwszego) i potrzebować dostępu z jednego z nich do wszystkich pozostałych, łącznie ze znajdującymi się przed nim.
Prostym rozwiązaniem tego problemu jest użycie listy cyklicznej. Na takiej liście (zob. rys. 5.11) pole next ostatniego elementu nie jest równe NULL, lecz wskazuje z powrotem na pierwszy element listy. Nie ma więc pierwszego ani ostatniego elementu listy, ponieważ elementy tworzą cykl. Potrzebny jest co najmniej jeden zewnętrzny wskaźnik do jakiegoś elementu listy, jeżeli ma ona być dostępna z programu. Jeśli lista zawiera tylko jeden element, to musi on wskazywać sam na siebie; jeśli lista jest pusta, to wartością każdego zewnętrznego wskaźnika do niej jest NULL.

Rys. 5.11. Lista cykliczna

Listy cyklicznej możemy użyć do implementacji prostej bazy danych, a także do innych celów, do jakich nadaje się zwykła lista. Załóżmy, że jest tylko jeden zewnętrzny wskaźnik db, wskazujący na listę. Przy przechodzeniu listy cyklicznej musimy umieć rozpoznać koniec listy, aby nie wejść w nieskończoną pętlę. Program nie może po prostu przebiegać przez listę do napotkania wskaźnika NULL, bo na liście cyklicznej takiego wskaźnika nie ma. Zamiast tego program musi kontynuować przechodzenie listy, aż natrafi na wskaźnik, od którego rozpoczął. Wymaga to użycia pętli do zamiast while, bo ta ostatnia zakończyłaby się natychmiast. Na rysunku 5.12 jest przedstawiona funkcja eachElement (), przebiegająca wszystkie elementy listy cyklicznej. Zwróćmy uwagę, że test if jest niezbędny, ponieważ jeśli lista jest pusta, nie należy nic robić.
Główna pętla realizująca wyszukiwanie na liście cyklicznej konkretnego klucza również musi być typu do. Poszukiwanie kończy się, gdy dany klucz, albo większy klucz na liście uporządkowanej, zostaje znaleziony. Poza tym kod funkcji findRec () jest taki sam, jak dla zwykłej listy (zob. rys. 5.13).
#88

void eachElement (Listptr ptr, void (*fn) (ListData)
{
Listptr p=ptr;
if (P) {
do {
(*fn)(p->data);
p = p->next;
}
while (p!=ptr);
}
}

Rys. 5.12. Funkcja eachElement () dla listy cyklicznej

int findRec(dbkeytype key, dbdatatype *data, indextype *idx)
{
Dbrec rec=db, prior=NULL;
int cmp;
if (rec)
do {
if ((cmp=comparedbkey(key, rec->key))<=0)
break;
prior = rec;
rec = rec->next;
} while (rec!=db);
idx->it = rec;
idx->prior = prior;
if(rec && cmp==0) {
copydbdata(rec->data, *data);
return 1;
}
return 0;
}

Rys. 5.13. Funkcja findRec () dla listy cyklicznej

Wstawianie elementu na listę cykliczną jest podobne do wstawiania na zwykłą listę. Musi być znany wskaźnik do poprzedniego elementu (który zawsze istnieje, chyba że lista jest pusta). Ponieważ implementowaliśmy bazę danych jako listę uporządkowaną, musimy uaktualnić wskaźnik do całej listy, jeżeli wstawiamy element na jej początek. Przy wstawianiu elementu na pustą listę trzeba zachować ostrożność. Efektem powinna być lista składająca się z jednego elementu, którego wskaźnik next wskazuje na niego samego. Zewnętrzny wskaźnik do pustej listy powinien być równy NULL, podobnie jak obydwa wskaźniki w indeksie (prior i it). Rysunek 5.14 zawiera kod funkcji wstawiającej element na listę cykliczną.
#89

int createRec(dbkeytype key, dbdatatype data, indextype idx)
/* Warunek wstępny: idx->prior wskazuje na rekord, za który trzeba wstawić nowy (jeśli jest równy NULL, to nowy rekord należy wstawić na początek listy). idx->it wskazuje na rekord następny za idx->prior.
Działanie: Jeśli baza danych nie jest przepełniona, dodaje rekord o kluczu key i danych data i zwraca wartość 1. W przeciwnym razie zwraca 0. */
{
Dbrec rec;

rec=(Dbrec)malloc(sizeof(struct dbrec));
if (rec==NULL)
return 0 ;
copydbkey(key, rec->key);
copydbdata(data, rec->data);
if (db==idx.it) /* Uwaga: jest to prawda, gdy db == NULL. */
db = rec;
if (idx.prior) {
idx.prior->next = rec;
rec->next=idx.it;
}
else
rec->next = rec;
return 1;
}

Rys. 5.14. Funkcja createRec () dla listy cyklicznej


5.2. Tablice rzadkie

W wielu zastosowaniach wybór tablicy jako struktury danych wydaje się najbardziej naturalny, jednak wykluczają go względy pamięciowe. Jest tak zwłaszcza wówczas, gdy jedynie niewielka część tablicy jest faktycznie używana. Tablicę tego typu nazywamy tablicą rzadką, ponieważ jest tylko gdzieniegdzie wypełniona danymi, a większość jej komórek jest pusta. W tej sytuacji tablicę można zastąpić systemem list.
Jako przykład rozważmy problem zapamiętywania ocen wszystkich studentów uczelni za dany semestr. Załóżmy, że jest 8000 studentów i 300 przedmiotów. Naturalną implementacją jest dwuwymiarowa tablica ocen, w której numery studentów są indeksami kolumn, a numery przedmiotów - indeksami wierszy (zob. rys. 5.15). Przyporządkowanie nazwiskom studentów i nazwom przedmiotów odpowiednich numerów odbywa się za pomocą umieszczenia ich w jednowymiarowych tablicach, o nazwach Students i Classes. Nazwy przedmiotów ani nazwiska nie muszą być uporządkowane. Jeśli wymagane jest uporządkowanie, można użyć dodatkowej tablicy,
#90
której każdy element jest rekordem o dwóch polach: nazwa i numer(Jest to tzw. indeks odwrócony.), lub też sortować początkową tablicę zawsze wtedy, kiedy potrzebne jest zachowanie porządku. Wiązałoby się to jednak z koniecznością ciągłej reorganizacji tablicy ocen, więc nie jest polecane.

Rys. 5.15. Tablice do przechowywania ocen studentów
#91
Każda komórka tablicy ocen zawiera stopień otrzymany przez studenta po zakończeniu nauki danego przedmiotu(W Stanach Zjednoczonych stosuje się literowy system ocen A-F (przyp. tłum.).). Jeśli stosuje się oceny ze znakiem + lub -, jak A-, B+ czy C+, to do przechowania każdego stopnia potrzebne są dwa bajty pamięci. W celu zmniejszenia rozmiaru tablicy ocen o połowę można użyć tablicy GradeCodes z rysunku 5.15c, powiązującej każdą ocenę z literą, co wymaga użycia tylko jednego bajtu pamięci.
Cała tablica (rys. 5.15d) zajmuje: 8000 studentów * 300 przedmiotów * 1 bajt == 2,4 miliona bajtów. Jest ona ogromna, ale bardzo rzadko wypełniona ocenami. Zakładając, że student wybiera średnio cztery przedmioty w semestrze, w każdej kolumnie tylko cztery miejsca będą zajęte przez oceny, a reszta, 296 komórek, czyli 98,7% komórek jest wolnych i marnuje się.
Lepszym rozwiązaniem jest użycie dwóch tablic dwuwymiarowych. Tablica ClassesTaken reprezentuje wszystkie przedmioty wybrane przez każdego studenta, a tablica StudentsInClasses zawiera dla każdego przedmiotu wszystkich studentów, którzy go wybrali (zob. rys. 5.16). Element każdej tablicy jest rekordem o dwóch polach określających numer studenta lub przedmiotu oraz ocenę. Zakładamy, że student może wybrać co najwyżej osiem przedmiotów i że na dany przedmiot może zapisać się nie więcej niż 250 studentów. Potrzebujemy dwóch tablic, ponieważ przy użyciu tylko jednej z nich tworzenie spisów byłoby bardzo czasochłonne. Gdyby na przykład użyć tylko tablicy ClassesTaken, wypisanie listy wszystkich studentów uczęszczających na dany przedmiot wymagałoby przejrzenia całej tablicy.
Załóżmy, że komputer, na którym program będzie pracował, potrzebuje dwóch bajtów do przechowania liczby całkowitej. Przy użyciu nowej struktury każda komórka tablicy zajmuje trzy bajty. W takim razie cała tablica ClassesTaken zajmuje: 8000 studentów * 8 przedmiotów * 3 bajty = 192000 bajtów, tablica StudentsInClasses zajmuje: 300 przedmiotów * 250 studentów * 3 bajty = 225000 bajtów, a więc łącznie zajmują 417000 bajtów, czyli mniej niż jedna piąta rozmiaru rzadkiej tablicy z rysunku 5.15d.
Chociaż jest to implementacja znacznie lepsza od poprzedniej, nadal jest marnotrawstwem pamięci; rzadko, jeśli w ogóle, obie tablice będą zapełnione, ponieważ na większość przedmiotów uczęszcza mniej niż 250 studentów, a większość studentów wybiera mniej niż osiem przedmiotów. Struktura ta jest również nieelastyczna: jeśli na jeden przedmiot może zapisać się więcej niż 250 studentów, to pojawia się problem, który trzeba obejść sztucznie. Jednym sposobem może być dodanie nie istniejącego przedmiotu, który obejmie nadmiarowych studentów danego przedmiotu. Innym sposobem jest ponowna kompilacja programu z nowym rozmiarem tablicy, który po jakimś czasie znowu może się okazać niepraktyczny. Przydałoby się bardziej elastyczne rozwiązanie, oszczędniej wykorzystujące pamięć.
#92
Rys. 5.16. Dwuwymiarowe tablice do przechowywania ocen studentów

Użyjemy dwóch jednowymiarowych tablic list, jak na rysunku 5.17. Każda komórka tablicy Class jest wskaźnikiem do listy studentów uczęszczających na dany przedmiot, a każda komórka tablicy Student wskazuje na listę przedmiotów wybranych przez studenta. Listy składają się z rekordów o pięciu polach zawierających: numer studenta, numer przedmiotu, ocenę, wskaźnik do następnego studenta i wskaźnik do następnego przedmiotu. Przy założeniu, że każdy wskaźnik zajmuje dwa bajty, jeden rekord zajmuje dziewięć bajtów, a cała struktura potrzebuje: 8000 studentów * 4 przedmioty (średnio) * 9 bajtów = 288000 bajtów, czyli mniej więcej 10% pamięci wymaganej przez pierwsze rozwiązanie i około 70% rozmiaru drugiego rozwiązania. Nie zużywamy pamięci niepotrzebnie, nie ma ograniczeń dotyczących liczby studentów jednego przedmiotu, a spis studentów uczęszczających na dany przedmiot można uzyskać od ręki.
#93
Rys. 5.17. Tabela ocen studentów utworzona przy użyciu list


5.3. Przykład: zarządzanie biblioteką

Jako przykład rozważymy bardzo prosty system zarządzania biblioteką. Potrzebny jest program, który pozwoli śledzić, co się dzieje z książkami zgromadzonymi w bibliotece. Kiedy czytelnik wypożycza książkę, bibliotekarz musi mieć możliwość zapisania, że książka została wypożyczona, kto i kiedy ją wziął oraz kiedy ma zostać zwrócona. Fakt zwrócenia książki należy także odnotować. Oprócz tego bibliotekarz musi mieć możliwość sprawdzenia, gdzie znajduje się dana książka oraz jakie książki wypożyczył dany czytelnik.
#94
Oto polecenia, jakie może wydawać bibliotekarz:
=> Checkout(patron, book, date) - powoduje odnotowanie w bazie danych, że czytelnik patron wypożyczył książkę book w dniu date.
=> Checkin(book, date) - powoduje odnotowanie w bazie danych, że książka book została zwrócona w dniu date.
=> Where(book) - powoduje wypisanie informacji, który czytelnik wypożyczył książkę book, lub komunikatu, że książka znajduje się w bibliotece.
=> HasWhat(patron) - powoduje wypisanie listy książek z biblioteki będących w posiadaniu czytelnika patron, według kolejności ich wypożyczania.

Załóżmy, że czytelnicy są identyfikowani przez nazwisko, składające się z co najwyżej 20 znaków, a książki - przez numer katalogowy, również co najwyżej 20-znakowy. Data jest reprezentowana przez liczbę całkowitą, powiedzmy, liczbę dni od otwarcia biblioteki.
Program wczyta ciąg wierszy, z których każdy zawiera polecenie i niezbędne parametry. Polecenia są reprezentowane przez dwuliterowe kody: Checkout = CO, Checkin = CI, Where = WH, HasWhat = HW. Parametry w wierszu są oddzielane przecinkami. Podczas testowania programu, jeśli zostaje wypożyczona książka, której dotychczas nie było w bazie danych, to automatycznie się ją dodaje. Podobnie, jeśli książkę wypożycza ktoś, kto dotychczas nie figurował w spisie czytelników, to zapis o nim zostaje dołączony do bazy danych. Przykładowy plik wejściowy zawiera następujące polecenia:

CO,QZ 105M,Joe Smith,10
CO,QA 12 1976,Bili Brown,12
CO,QA 14 1978,3111 Brown, 12
CI,QZ 105M,23
WH,QA 14 1978
WH,QZ 105M
HW,Bili Brown
CO,QB 13 1977 , Bob Brown, 17
CO,QB 14 1978, Bob Brown, 16
CO,QB 15 1979 , Bob Brown, 18
HW,Bob Brown
CI,QB 14 1978,20
HW,Bob Brown
WH,QB 13 1977
WH QJ 129D 1972
HW,Joe Smith

Efekt wykonania programu bibliotecznego na tym pliku mógłby wyglądać następująco:
#95
Książkę QA 14 1978 wypożyczył Bili Brown.
Książka QZ 105M jest w bibliotece.
Bili Brown wypożyczył następujące książki: QA 12 1976 QA 14 1978
Bob Brown wypożyczył następujące książki : QB 13 1977 QB 14 1978 QB 15 1979
Bob Brown wypożyczył następujące książki : QB 13 1977 QB 15 1979
Książkę QB 13 1977 wypożyczył Bob Brown.
Błąd: książka QJ 129D 1972 nie istnieje.
Joe Smith nie wypożyczył żadnej książki.

W programie jest nam potrzebna prosta baza danych, w której będzie można wyszukać książkę o danym numerze i odczytać wszelkie informacje z nią związane. Musimy też mieć możliwość wyszukania czytelnika o danym nazwisku i odczytania informacji o nim, takich jak ta, które książki wypożyczył. Celom tym służą dwie bazy danych: odpowiednio bookDb i patronDb. Podczas operacji wypożyczania książki trzeba połączyć informację o książce z informacją o czytelniku. Dlatego gdy książka jest wypożyczana, program tworzy rewers, który zawiera informację o książce i czytelniku oraz datę wypożyczenia. Każdy rekord przechowywany w bazie bookDb zawiera wskaźnik do takiego rewersu (lub wskaźnik NULL, jeśli książka nie jest wypożyczona). Czytelnik może wypożyczyć więcej niż jedną książkę, zatem każdy rekord z danymi o czytelniku z bazy patronDb zawiera listę rewersów.
Aby łatwo było dodawać i usuwać rewersy z listy czytelnika, jest ona zrealizowana jako dwukierunkowa lista cykliczna. Rekord czytelnika zawiera wskaźnik do jednego z jej elementów, więc wszystkie są dostępne. Każdy rekord z danymi o wypożyczonej książce zawiera wskaźnik do któregoś z elementów tej listy. Rewers ma trzy pola przeznaczone na dane określające wskaźnik do rekordu książki, wskaźnik do rekordu czytelnika i datę wypożyczenia, a poza tym pola niezbędne do zaimplementowania listy dwukierunkowej.
Kiedy książka jest wypożyczana, dostajemy jej numer i nazwisko czytelnika. Program musi odnaleźć te klucze w odpowiednich bazach danych, a następnie utworzyć nowy rewers z uzyskaną informacją. Rewers jest wstawiany do listy książek wypożyczonych przez czytelnika, a wskaźnik w rekordzie książki jest ustawiany tak, by wskazywał na nowo utworzony rewers. Przy zwrocie książki dostajemy jedynie jej numer. Program musi odnaleźć go w bazie danych i dostać się do rewersu. Rewers zawiera wskaźnik do rekordu czytelnika, potrzebny do usunięcia rewersu z listy książek wypożyczonych przez czytelnika; następnie trzeba uaktualnić rekordy dotyczące książki i czytelnika, aby uwzględniały to usunięcie. Ponieważ klucze w obydwu bazach danych są napisami długości 20 znaków, a dane w nich przechowywane to wskaźniki do rewersu, możemy w obu wypadkach użyć tego samego typu elementu bazy, chociaż same bazy będą różnymi obiektami.
#96
Wypisanie listy książek wypożyczonych przez danego czytelnika jest proste: wystarczy odnaleźć nazwisko czytelnika w bazie patronDb i wypisać jego listę książek. Trzeba to jednak zrobić ostrożnie, ponieważ lista jest cykliczna. Aby wyszukać daną książkę, trzeba znaleźć jej numer w bazie bookDb. Jeśli wskaźnik do rewersu jest równy NULL, to książka znajduje się w bibliotece. W przeciwnym razie rewers zawiera wskaźnik do rekordu czytelnika, który daną książkę wypożyczył.
Bazy danych o książkach i czytelnikach muszą być zaprogramowane przy użyciu stabilnej implementacji ATD-prostej bazy danych. Stabilność oznacza tutaj to, że jeśli rekord zostanie raz utworzony, to wskaźnik do niego zwracany przez funkcję createRec() (a później findRec()) nigdy się nie zmienia. Jest to konieczne, ponieważ wskaźniki te są umieszczane w rewersach i wykorzystywane później. Niektóre implementacje prostej bazy danych nie są stabilne, jeśli dopuszczamy usuwanie rekordów. Na przykład w tablicy nieuporządkowanej ostatni element jest kopiowany w miejsce usuwanego, zatem jego indeks się zmienia. Będziemy zakładali, że nasza implementacja bazy danych zawiera dwie dodatkowe operacje: getKey () i getData (), które dla danego indeksu rekordu zwracają odpowiednio klucz i dane tego rekordu.
Plik nagłówkowy dbdefs.h, definiujący typ klucza i danej w bazach danych, wygląda następująco:

#ifndef LIBDATA
#def ine LIBDATA
#include
#include

typedef char Name[21];

typedef struct listElement *Listptr;

typedef Name dbkeytype;
typedef Listptr dbdatatype;

#define comparedbkey(k1,k2) ((int)(strcmp((k1),(k2)
#define copydbkey (kl, k2 ) (strcpy((k2),(k1))
#define copydbdata(dl,d2) ((d2)=(d1))
#endif

Zwróćmy uwagę, że typ Listptr musi być zdefiniowany w tym miejscu, ponieważ jest użyty jako dbdatatype, chociaż struktura struct listElement jest zdefiniowana dopiero w programie głównym. W języku C nie stanowi to problemu, gdyż wskaźnik do struktury może być zdefiniowany przed definicją samej struktury.
Na rysunku 5.18 jest przedstawiony kod programu obsługi bibliotecznej bazy danych. Kod zawiera procedury manipulacji na listach rewersów. Nie zostały one umieszczone w osobnym module, ponieważ operacje na liście dwukierunkowej nie wydają się dostatecznie ogólne, aby potraktować je jako ATD.

97

#include
#include "database.h"

typedef struct {
indextype patron,book;
int datę;
} CheckoutData;

typedef CheckoutData ListData;

typedef struct listElement {
ListData data;
struct listElement *prev, *next;
} ListElement;

void deleteElement(Listptr element, Listptr *ptr) /* Usuwa element z dwukierunkowej listy cyklicznej wskazywanej
przez ptr. */
{
Listptr previous, following;

previous = element->prev;
following = element->next;
i f (previous==element) /* lista l-elementowa */
*ptr = NULL;
else {
previous->next = following;
f ollowing->prev =previous;
if (*ptr==element)
*ptr = following;
}
free((void *)element);
}
void addElement(ListData data, Listptr *ptr, Listptr *new)
/* Wstawia nowy element, zawierający dane data, na dwukierunkową listę
cykliczną wskazywaną przez ptr.
new staje się wskaźnikiem do nowego elementu. */
{
Listptr previous;

*new = (Listptr)mailoc(sizeof(ListElement));
(*new)->data = data;
if (!*ptr)
*ptr = (*new)->prev = (*new)->next = *new;
else {
previous = (*ptr)->prev;
previous->next = *new;

Rys. 5.18. Program implementujący biblioteczną bazę danych

98

(*new)->prev = previous;
(*ptr)->prev = *new;
(*new)->next = *ptr;
}
}

void eachElement (Listptr ptr, void (*fn) (ListData) )
/* Wywołuje funkcję f n dla każdego elementu listy cyklicznej wskazywanej przez ptr. */
{
Listptr p=ptr;

if (P)
do {
(*fn)(p->data);
p =p->next;
}

while (p!=ptr);
}

Dbrec bookDb, patronDb;

void checkOutBook(CheckoutData slip)
/* Odnotowuje wypożyczenie książki, mając dany rewers. */
{
char *patronName;
Listptr bookList,checkoutSlip;

patronName = strtok(NULL," , " ) ;
if (!findRec(ŁpatronDb, patronName, &bookList, &slip.patron))
createRec(&patronDb, patronName, bookList=NULL, Łslip.patron)
sscanf (strtok (NULL, ","), "%d" , &slip . datę) ;
addElement(slip, &bookList, &checkoutSlip) ;
setRec(ŁpatronDb, slip.patron, bookList);
setRec(&bookDb, slip.book, checkoutSlip);
}

void checkOut ()
/* Odnotowuje wypożyczenie książki. */
{
char *callNo;
Listptr checkoutSlip;
CheckoutData slip;

callNo=strtok(NULL, ",");
if (!findRec(ŁbookDb, callNo, ŁcheckoutSlip, &slip.book)) {
createRec(&bookDb, callNo, NULL, &slip.book);
checkOutBook(slip);
}
Rys. 5.18. Program implementujący biblioteczną bazę danych (cd.)

99

else if (checkoutSlip)
printf ( " Błąd: książka %s jest już wypożyczona . \n" , callNo)
else
checkOutBook(slip);
}
void checkln ()
/* Odnotowuje zwrot książki. */
{
char *callNo;
Listptr checkoutSlip, bookList;
indextype book, patron;

callNo=strtok(NULL, ",");
if (!findRec(&bookDb, callNo, &checkoutSlip, &book))
printf ( "Błąd: książka %s nie istnieje. \n" , callNo);
else if (!checkoutSlip)
printf ( "Błąd: książka %s nie była wypożyczona. \n" / callNo)
else {
patron = checkoutSlip->data.patron;
bookList = getData(patron);
deleteElement(checkoutSlip, ŁbookList);
setRec(ŁbookDb, book, NULL);
setRec(&patronDb, patron, bookList);
}
}

void printBook(CheckoutData slip)
/* Wypisuje numer książki, której dotyczy rewers. */
{
printf("%s ", getKey(slip.book));
}
void hasWhat ()
/* Wypisuje listę książek wypożyczonych przez czytelnika. */
{
char *patronName;
Listptr bookList;
indextype patron;

patronName = strtok(NULL, " , ") ;
if (!findRec(&patronDb, patronName, ŁbookList, &patron))
printf("Błąd: czytelnik %s nie istnieje.\n" , patronName);
else if(IbookList)
printf(" %s nie wypożyczył żadnej książki.\n" , patronName)

Rys. 5.18. Program implementujący biblioteczną bazę danych (cd.)
#100

else {
printf(" %s wypożyczył następujące książki eachElement(bookList, printBook);
printf("\n");
void where ( )
}
}
/* Wypisuje, gdzie znajduje się książka. */
{
char * callNo;
Listptr checkoutSlip;
indextype book;



callNo = strtok(NULL, ",");
if ( ! findRec (&bookDb, callNo, &checkoutSlip,&book) )
printf ( "Błąd: książka %s nie istnieje. \n" , callNo)
else if ( ! checkoutSlip)
printf ( "Książka %s jest w bibliotece. \n" , callNo)
else
printf (" Książkę %s wypożyczył %s.\n", callNo, getKey (checkoutSlip->data. patron) ) ;
}

main ( )
{
char line[81] , *command;

initDb(&bookDb) ;
initDb(&patronDb) ;
while (gets(line) !=NULL) {
coiranand - strtok (linę, " ,");
if (strcmp (command, "CI")==0
checkIn( ) ;
else if (strcmp (command, "CO")==0)
checkOut ( ) ;
else if (strcmp (command, "HW")==0)
hasWhat ( ) ;
else if (strcmp (command, "WH")==0)
where ( ) ;
else
printf ( "Błąd: nieznane polecenie . Pominięty wiersz : %s\n' linę) ;
}
}

Rys. 5.18. Program implementujący biblioteczną bazę danych (cd.)
#101

5.4. Ćwiczenia

1. Podaj inny sposób przechowania listy (1 3 4 10) z użyciem tablic data i next.
2. Jakie są zalety i wady dynamicznie tworzonych list w porównaniu ze statycznymi?
3. Przypuśćmy, że do listy trzeba dodać dziesięć elementów jednocześnie. Czy jest na to szybszy sposób niż wstawianie ich po kolei?
4. Napisz funkcję zliczającą liczbę elementów na zwykłej liście.
5. Napisz funkcję zliczającą liczbę elementów na dowolnej poprawnie zbudowanej liście, również cyklicznej.
6. Pokaż, jak odwrócić listę. Zmień na przykład listę (A, B, C, D) na (D, C, B, A).
7. Czym różnią się funkcje prostej bazy danych dla list uporządkowanych i nieuporządkowanych?
8. Napisz kod wstawiania i usuwania elementu z listy dwukierunkowej.
9. Napisz funkcję usuwającą element z listy cyklicznej.
10. Przypuśćmy, że masz napisać program eliminujący powtórzenia niektórych słów w tekście przez zastąpienie ich synonimami. Program przechowuje listy synonimów takich słów. Kiedy słowo pojawia się w tekście po raz pierwszy, jest zastępowane pierwszym słowem ze swojej listy synonimów, za drugim razem - drugim słowem i tak dalej. Kiedy skończą się synonimy danego słowa, program przechodzi z powrotem na początek listy. Jakiej struktury danych użyłbyś do przechowywania listy synonimów i dlaczego?
11. Aby zwolnić blok pamięci na kopiec, przekazuje się systemowi wskaźnik do niego poprzez funkcję free (). Skąd system wie, jaki jest rozmiar zwalnianego bloku? Na przykład typem wskaźnika może być po prostu wskaźnik do char, ale podczas przydzielania pamięci przypisuje mu się blok mieszczący 10-elementową tablicę. Omów metody implementacji przydziału i zwalniania pamięci, za pomocą których można rozwiązać ten problem. Jaka dodatkowa informacja musi być zapamiętana i gdzie powinna być przechowywana?
12. Załóżmy, że wskaźnik zajmuje tyle samo pamięci co liczba całkowita. W jakim stopniu powinna być wypełniona tablica, aby macierzowa reprezentacja listy była oszczędniejsza od opartej na wskaźnikach? A jeśli wskaźnik zajmuje 2-krotnie więcej pamięci niż liczba całkowita?

5.5. Zadania programistyczne

1. Zaimplementuj ATD-zbiór z użyciem list. ATD-zbiór obejmuje standardowe operacje na zbiorach: sumę, część wspólną, różnicę zbiorów, zawieranie i test przynależności dla elementów. Zasadniczą różnicą między zbiorem a listą jest to, że elementy na liście mogą się powtarzać, a w zbiorze każdy element może występować tylko raz, oraz to, że kolejność elementów w zbiorze jest nieistotna.
#102
Zakładając, że elementy można uporządkować, czy lista uporządkowana będzie efektywniejsza niż nieuporządkowana? Podaj oszacowania czasów wykonania Twoich operacji.
2. Zbiór z powtórzeniami różni się od zwykłego zbioru tym, że może zawierać więcej niż jedną kopię tego samego elementu, jak na przykład (B, A, A, B, A, C). Jest on podobny do listy, z tą różnicą, że kolejność elementów jest nieistotna, a więc poprzedni zbiór z powtórzeniami jest tym samym co (A, A, A, B, B, C). ATD-zbiór z powtórzeniami obejmuje następujące operacje: sumę, część wspólną, różnicę, zawieranie i przynależność. Operacje te uwzględniają krotność elementu w zbiorze z powtórzeniami. Na przykład (A, A, A, B, B, C) - (A, A, C) to (A, B, B). Zaimplementuj ATD-zbiór z powtórzeniami z użyciem list.
3. Tablica dynamiczna jest strukturą danych, która może zwiększać rozmiar przy zachowaniu własności, że dane są umieszczane w strukturze w sposób ciągły. Zaprojektuj system do dynamicznego przydzielania i zwalniania takich tablic. Odwołania do systemu powinny obejmować utworzenie początkowej tablicy danego rozmiaru, dodanie elementu na koniec tablicy oraz zmniejszenie tablicy do danego rozmiaru.
4. Zmodyfikuj program obsługujący biblioteczną bazę danych tak, by książki wypożyczone przez czytelnika były zawsze wypisywane w kolejności dat ich wypożyczenia.
5. Napisz wersję podstawową programu kontrolującego poprawność, który będzie sprawdzał, czy wszystkim zmiennym nadano wartości początkowe oraz czy zmienne lokalne nie mają tych samych nazw co globalne. Utwórz listę zmiennych globalnych, a dla każdej funkcji listę jej zmiennych lokalnych. Na obydwu listach zapisuj informację o pierwszym nadaniu wartości każdej zmiennej i sprawdzaj, czy przed pierwszym użyciem zmiennej została dokonana jej inicjacja. Oprócz tego porównaj obie listy, aby wykryć powtórzenia i wygeneruj ostrzeżenie, jeśli taka sama nazwa znajduje się na obu listach. Lista zmiennych lokalnych jest usuwana po zakończeniu przetwarzania jednej funkcji i tworzona na nowo po napotkaniu kolejnej. Rozważ możliwość utrzymywania kolejności alfabetycznej na obu listach.

Bibliografia

[1] Foster J. M.: Przetwarzanie struktur listowych. Warszawa, PWN 1976.
[2] Hansen W.J.: A predecessor algorithm for ordered lists. Information Processing Letters, 1978, 7, s. 137-138.
[3] Wilkes M.V.: Lists and why they are useful. Computer Journal, 1965, 7, s. 278-281.
[4] Williams R.: A survey of data structures for computer graphics systems. Computing Surveys, 1973, 3, s. 1-23.