Typ abstrakcyjny

Przykady

Najczciej uywane typy abstrakcyjne to:

• drzewo binarne
• pojemnik
• sownik lub tablica asocjacyjna
• razem
• plik
• kolejka priorytetowa
• Wykres
• wymienianie kolejno
• multiset
• bateria
• Znalezienie zwizku

Struktura

W tej sekcji niewystarczajco przytoczono jej róda  (grudzie 2017 r . ) . 

Aby to poprawi, dodaj sprawdzalne odniesienia [ jak to zrobi ] lub szablon {{Reference required}} w przypadku fragmentów wymagajcych róda.

Typ abstrakcyjny skada si z piciu pól ^{[ref. konieczne]}  :

• Typ abstrakcyjny;
• Uywa;
• Operacje;
• Warunki wstpne;
• Aksjomaty.

Te pi elementów czsto czy si skrótem: TUOPA .

Typ abstrakcyjny

Pole Typ abstrakcyjny zawiera nazw opisywanego typu i ewentualnie okrela, czy nie jest to rozszerzenie innego typu abstrakcyjnego. Na przykad, napiszemy Typ abstrakcyjny: Stos, aby utworzy typ o nazwie Stos, który opisuje, czym jest stos, oraz Typ abstrakcyjny rozszerzenia: Stos, jeli chcemy go rozszerzy (Typ abstrakcyjny rozszerzamy przez przypisanie nowych operacji niezdefiniowanych w pierwszej specyfikacji).

Uywa

Pole Uyj zawiera typy abstrakcyjne, których uyjemy w opisywanym. Na przykad typ abstrakcyjny Stack, który zdefiniujemy, uyje w swojej specyfikacji typu abstrakcyjnego Boolean , a my napiszemy Use: Boolean  .

Operacje

Pole Operacje zawiera prototypowanie wszystkich operacji. Przez prototypowanie rozumiemy opis operacji poprzez ich nazw, argumenty i zwrot.

Operacje s podzielone na kilka typów:

• z konstruktory (uywany do tworzenia typ obiektu, który jest ustawiany);
• transformatory (pozwalaj modyfikowa obiekty i ich zawarto);
• e obserwatorzy (w zalenoci udzielanie informacji o stanie obiektu).

Przykad operacji dla typu Abstract type: Stack:

             créer :  Pile

Zauwa, e operacja create jest konstruktorem . Rzeczywicie, ta funkcja tworzy obiekt typu stos . Ponadto do utworzenia tego stosu nie jest potrzebny argument . Wskazuje na to brak wskazania po lewej stronie strzaki.

Warunki wstpne

Pole Warunki wstpne zawiera warunki, które naley speni na argumentach operacji, aby mogy zachowywa si normalnie. Moemy tu mówi o zestawie definicji operacji.

Aksjomaty

Pole Axioms zawiera seri aksjomatów opisujcych zachowanie kadej operacji typu abstrakcyjnego. Kady aksjomat jest prawdziwym zdaniem logicznym.

Skomentowany przykad: stos

Pamitaj, e stos to prosta struktura danych , zgodna z zasad LIFO (Last In First Out), co oznacza, e zawsze mamy dostp do ostatniego elementu, który wanie dodalimy do tej struktury.

Pod uwag brane s tutaj podstawowe operacje na stosie , a take operacja insertEnd umoliwiajca wstawienie elementu na kocu stosu (operacja ta pozwoli na przedstawienie rekursji w typie abstrakcyjnym). Symbol     oznacza, e operacja podlega warunkom wstpnym. ${\ displaystyle \ rightharpoonup}$

Tutaj mamy konstruktora: create  ; trzy transformatory: stack , rest i insertEnd  ; i dwóch obserwatorów: vertex i estVide . Operacja na stosie jest uwaana przez niektórych za konstruktor, poniewa widzimy, e dowolny stos ma posta create () lub stack (p, e).

Warunki wstpne: p Bateria ${\ displaystyle \ in}$ zdefiniowany (wierzchoek (p)) jest pusty (p) ${\ displaystyle \ Rightarrow}$ ${\ displaystyle \ neg}$ zdefiniowana (reszta (p)) jest pusta (p) ${\ displaystyle \ Rightarrow}$ ${\ displaystyle \ neg}$

Te warunki wstpne odpowiadaj temu, e nie mona zobaczy góry ani zabra pozostaej czci pustego stosu .

Aksjomaty: p Stos i e, f Element ${\ displaystyle \ in}$${\ displaystyle \ in}$ (P1) wierzchoek (stos (p, e)) = e (P2) reszta (stos (p, e)) = p (P3) jest puste (create ()) = true (P4) jest puste (stos (p, e)) = fasz (P5) insertEnd (create (), e) = stack (create (), e) (P6) insertEnd (stack (p, f), e) = stack (insertEnd (p, e), f)

Uwagi i odniesienia

1. Manfred Broy, Martin Wirsing i Claude Pair ,   Systematyczne badanie modeli abstrakcyjnych typów danych  , Theoretical Computer Science , vol.  33,1984, s.  139-174
2. Sébastien Veigneau , Imperatywne i funkcjonalne podejcie do algorytmów: aplikacje w C i CAML Light , Springer Science & Business Media,1999( czytaj online )
3. http://pageperso.lif.univ-mrs.fr/~denis.lugiez/Enseignement/L2/Cours/cours4.pdf

Zobacz te

• Zespó (IT)
• Plik (struktura danych)
• Kolejka priorytetowa
• Lista (komputer)
• Wektor (struktura danych)
• Wykres (typ abstrakcyjny)