5032124667

24

1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW

oprócz liczb dziesiętnych honorować także liczby w postaci szesnastkowej, niezbędne zmiany trzeba będzie wprowadzić jedynie w ściśle określonym fragmencie kodu, bez ingerowania w inne fragmenty programu.

Definiowanie abstrakcyjnych typów danych

Abstrakcyjne typy danych, często dla prostoty oznaczane skrótem ADT (ang. Abstract Data Types), mogą być traktowane jak model matematyczny, z którym związano określoną kolekcję operacji. Przykładem prostego ADT może być zbiór liczb całkowitych, w stosunku do którego określono operacje sumy, iloczynu i różnicy (w rozumieniu teorii mnogości). Argumentami operacji związanych z określonym ADT mogą być także dane innych typów, dotyczy to także wyniku operacji. Przykładowo, wśród operacji związanych z ADT reprezentującym zbiór liczb całkowitych znajdować się mogą procedury badające przynależność określonego elementu do zbioru, zwracające liczbę elementów czy też tworzące nowy zbiór złożony z podanych parametrów. Tak czy inaczej, macierzysty ADT wystąpić musi jednak co najmniej raz jako argument którejś ze swych procedur.

Dwie wspomniane wcześniej cechy procedur — uogólnienie i enkapsulacja — stosują się jako żywo do abstrakcyjnych typów danych. Tak jak procedury stanowią uogólnienie elementarnych operatorów (+, -, *, / itd.), tak abstrakcyjne typy danych są uogólnieniem elementarnych typów danych (integer, real, boolean itd.). Odpowiednikiem enkapsulacji kodu przez procedury jest natomiast enkapsulacja typu danych — w tym sensie, że definicja struktury konkretnego ADT wraz z towarzyszącymi tej strukturze operacjami zamknięta zostaje w ściśle zlokalizowanym fragmencie programu. Każda zmiana postaci czy zachowania ADT uskuteczniana jest wyłącznie w jego definicji, natomiast przez pozostałe fragmenty ów ADT traktowany jest — to ważne — jako elementarny typ danych. Pewnym odstępstwem od tej reguły jest sytuacja, w której dwa różne ADT są ze sobą powiązane, czyli procedury jednego ADT uzależnione są od pewnych szczegółów drugiego. Enkapsulacja nie jest wówczas całkowita i niektórych zmian dokonać trzeba na ogół w definicjach obydwu ADT.

By dokładniej zrozumieć podstawowe idee tkwiące u podstaw koncepcji abstrakcyjnych typów danych, przyjrzyjmy się dokładniej typowi LIST wykorzystywanemu w procedurze greedy na listingu 1.3. Reprezentuje on listę liczb całkowitych (integer) o nazwie newclr, a podstawowe operacje wykonywane w kontekście tej listy są następujące:

(1)    Usuń wszystkie elementy z listy.

(2)    Udostępnij pierwszy element listy lub wartość nul 1, jeżeli lista jest pusta.

(3)    Udostępnij kolejny element listy lub wartość nul 1, jeżeli wyczerpano zbiór elementów.

(4)    Wstaw do listy nowy element (liczbę całkowitą).

Istnieje wiele struktur danych, które mogłyby posłużyć do efektywnej implementacji typu LIST — zajmiemy się nimi dokładniej w rozdziale 2. Gdybyśmy w zapisie algorytmu na listingu 1.3, używającym powyższych opisów, zastąpili je wywołaniami procedur:

(1)    MAKENULL(.newclr);

(2)    w := FIRST(newc7r);

(3)    w := NEXT(neivc/r);

(4)    INSERT!iz. newclr);

od razu widoczna stałaby się podstawowa zaleta abstrakcyjnych typów danych. Otóż program korzystający z ADT ogranicza się tylko do wywoływania związanych z nim procedur — ich implementacja jest dla niego obojętna. Dokonując zmian w tej implementacji nie musimy ingerować w wywołania procedur.