5032124668

1.3. TYPY DANYCH, STRUKTURY DANYCH 1ADT

Drugim abstrakcyjnym typem danych, używanym przez procedurę greedy, jest GRAPH reprezentujący graf, z następującymi operacjami podstawowymi:

(1)    Udostępnij pierwszy niepokolorowany wierzchołek.

(2)    Sprawdź, czy dwa podane wierzchołki połączone są krawędzią.

(3)    Przyporządkuj kolor wierzchołkowi.

(4)    Udostępnij kolejny niepokolorowany wierzchołek.

Wymienione cztery operacje są co prawda wystarczające w procedurze greedy, lecz oczywiście zestaw podstawowych operacji na grafie powinien być nieco bogatszy i powinien obejmować na przykład: dodanie krawędzi między podanymi wierzchołkami, usunięcie konkretnej krawędzi, usunięcie kolorowania z wszystkich wierzchołków itp. Istnieje wiele struktur danych zdolnych do reprezentowania grafu w tej postaci — przedstawimy je dokładniej w rozdziałach 6. i 7.

Należy wyraźnie zaznaczyć, że nie istnieje ograniczenie liczby operacji podstawowych związanych z danym modelem matematycznym. Każdy zbiór tych operacji definiuje odrębny ADT. Przykładowo, zestaw operacji podstawowych dla abstrakcyjnego typu danych SET mógłby być następujący:

(1)    MAKENULL04) — procedura usuwająca wszystkie elementy ze zbioru A,

(2)    UNI0N(A, B, C) — procedura przypisująca zbiorowi C sumę zbiorów A i B,

(3)    SIZE(A) — funkcja zwracająca liczbę elementów w zbiorze A.

Implementacja abstrakcyjnego typu danych polega na zdefiniowaniu jego odpowiednika (jako typu) w kategoriach konkretnego języka programowania oraz zapisaniu (również w tym języku) procedur implementujących jego podstawowe operacje. „Typ” w języku programowania stanowi zazwyczaj kombinację typów elementarnych tego języka oraz obecnych w tym języku mechanizmów agregujących. Najważniejszymi mechanizmami agregującymi języka Pascal są tablice i rekordy. Na przykład abstrakcyjny zbiór SET zawierający liczby całkowite może być zaimplementowany jako tablica liczb całkowitych.

Należy także podkreślić jeden istotny fakt. Abstrakcyjny typ danych jest kombinacją modelu matematycznego i zbioru operacji, jakie można na tym modelu wykonywać, dlatego dwa identyczne modele, połączone z różnymi zbiorami operacji, określają różne ADT. Większość materiału zawartego w niniejszej książce poświęcona jest badaniu podstawowych modeli matematycznych, jak zbiory i grafy, i znajdowaniu najodpowiedniejszych (w konkretnych sytuacjach) zestawów operacji dla tych modeli.

Byłoby wspaniale, gdybyśmy mogli tworzyć programy w językach, których elementarne typy danych i operacje sąjak najbliższe używanym przez nas modelom i operacjom abstrakcyjnych typów danych. Język Pascal (pod wieloma względami) nie jest najlepiej przystosowany do odzwierciedlania najczęściej używanych ADT, w dodatku nieliczne języki, w których abstrakcyjne typy danych deklarować można bezpośrednio, nie są powszechnie znane (o niektórych z nich wspominamy w notce bibliograficznej).

1.3. Typy danych, struktury danych i ADT

Mimo że określenia „typ danych” (lub po prostu „typ”), „struktura danych” i „abstrakcyjny typ danych” brzmią podobnie, ich znaczenie jest całkowicie odmienne. W terminologii języka programowania „typem danych” nazywamy zbiór wartości, jakie przyjmować mogą zmienne tego typu. Na przykład zmienna typu boolean przyjmować może tylko dwie wartości: true i false. Poszczególne języki

Wyszukiwarka

Podobne podstrony:
skanuj0014 (316) Rozdział 2. ♦ Znaczniki, zmienne i typy danych 25 <script language="php&quo
Struktury danych. Proste typy danych: standardowe, okrojone, tablice, rekordy, rekordy z wariantami,
WYKŁAD4 i5 TYPY STRUKTURALNE Poznane dotąd typy danych : Integer, Real, Clar, Boolean, wyfcczeniowy
23 1.2. ABSTRAKCYJNE TYPY DANYCHPodsumowanie Na rysunku 1.4 przedstawiamy schemat procesu tworzenia
27 1.3. TYPY DANYCH, STRUKTURY DANYCH I ADT pola rekordu) są natomiast dostępne w sposób bezpośredni
Strukturalne typy danych: tablica, rekord, plik tekstowy i elementowy. Operacje na strukturach. Dyna
Wykład IITyp danych, proste typy danych Algorytmy i struktury danych Wyższa Szkoła Biznesu Seme
Obiektowo-relacyjny model danych ® Abstrakcyjne typy danych (ADT) definiowane przez użytkownika • Na
Dell Laser MFP00n 081209201503 3 (strukturalny język zapytań)tYPY DANYCH ccł. Typy znakowe char rep
Złożone typy danych Na podstawie http://pl.wikibooks.org/wiki/C/Typy_złożoneStruktury Struktury to
skanuj0018 (274) fezdział 2. ♦ Znaczniki, zmienne i typy danych 29 być dla nas przydatne podczas jeg

więcej podobnych podstron