Tip abstract

În calcul , un tip abstract (în engleză, abstract data type , sau ADT ) este o specificație matematică a unui set de date și a setului de operații care pot fi efectuate pe acestea. Acest tip de date se numește abstract deoarece corespunde unei specificații pe care o structură de date trebuie apoi să o implementeze .

Exemple

Cele mai utilizate tipuri abstracte sunt:

Structura

Un tip abstract este compus din cinci câmpuri :

Tip abstract;
Utilizări;
Operațiuni;
Pre-condiții;
Axiome.

Aceste cinci elemente sunt adesea unite sub acronimul: TUOPA .

Tip abstract

Câmpul „Tip abstract” conține numele tipului descris și, eventual, specifică dacă aceasta nu este o extensie a altui tip abstract. De exemplu, vom scrie „Abstract Type: Stack” pentru a crea un tip numit Stack care descrie ce este un stack și „Extension Abstract Type: Stack” dacă dorim să îl extindem (extindem un tip abstract prin atribuirea de noi operații nedefinite în prima specificație).

Utilizări

Câmpul „Utilizare” conține tipurile abstracte pe care le vom folosi în cel pe care îl descriem. De exemplu, tipul abstract Stack pe care îl definim va folosi în specificația sa tipul abstract Boolean și vom scrie „Use: Boolean ”.

Operațiuni

Câmpul „Operații” conține prototiparea tuturor operațiunilor. Prin prototipare , înțelegem o descriere a operațiunilor după numele lor, argumentele și revenirea lor.

Operațiunile sunt împărțite în mai multe tipuri:

a constructorilor (folosit pentru a crea un tip de obiect care este în curs de set);
transformatoare (vă permit să modificați obiectele și conținutul acestora);
a observatorilor ( în funcție de a da informații despre starea obiectului).

Exemplu de operație pentru tipul "Abstract type: Stack":

créer : → Pile

Rețineți că operațiunea „creați” este un constructor . Într-adevăr, această funcție creează un obiect de tip stivă . În plus, nu are nevoie de un argument pentru a crea această stivă . Acest lucru este demonstrat de absența indicației în stânga săgeții.

Condiții prealabile

Câmpul „Pre-condiții” conține condițiile care trebuie respectate pe argumentele operațiilor, astfel încât acestea să poată avea un comportament normal. Putem vorbi aici despre un set de definiții ale operațiilor.

Axiome

Câmpul „Axiome” conține o serie de axiome pentru a descrie comportamentul fiecărei operații de tip abstract. Fiecare axiomă este o adevărată propoziție logică.

Exemplu comentat: stiva

Amintiți-vă că o stivă este o structură simplă de date , care respectă principiul LIFO („Last In First Out”), adică accesăm întotdeauna ultimul element pe care tocmai l-am adăugat la această structură.

Tip abstract: Stivă Utilizare: Boolean, Element Operațiuni: creați: Pile $\ sageata dreapta$ stack: Stack Element Stack $\ ori$ $\ sageata dreapta$ sus: Stack Element $\ rightharpoonup$ rest: Baterie Baterie $\ rightharpoonup$ isEmpty: stivă booleană $\ sageata dreapta$ Introduceți capătul: baterie element baterie $\ ori$ $\ sageata dreapta$

Operațiunile de bază ale stivei sunt luate în considerare aici , precum și operația insertEnd care permite inserarea unui element la sfârșitul stivei (această operațiune va permite recursivitatea să fie prezentată în tip abstract). Simbolul " " înseamnă că operația este supusă unor condiții prealabile. $\ rightharpoonup$

Aici avem un constructor: create ; trei transformatoare: stivă , odihnă și insertEnd ; și doi observatori: vertex și estVide . Operația stivei este considerată de unii ca un constructor, deoarece vedem că orice stivă are forma "create ()" sau "stack (p, e)".

Condiții prealabile: p Baterie $\ in$ definit (vârf (p)) este gol (p) $\ Sageata dreapta$ $\ neg$ definit (restul (p)) este Gol (p) $\ Sageata dreapta$ $\ neg$

Aceste condiții prealabile corespund cu faptul că nu se poate „vedea” partea de sus sau a lua restul unei stive goale.

Axiome: p Stack și e, f Element $\ in$ $\ in$ (P1) vârf (stivă (p, e)) = e (P2) rest (stivă (p, e)) = p (P3) este Gol (create ()) = adevărat (P4) este Gol (stiva (p, e)) = fals (P5) insertEnd (create (), e) = stivă (create (), e) (P6) insertEnd (stack (p, f), e) = stack (insertEnd (p, e), f)

Note și referințe

Manfred Broy, Martin Wirsing și Claude Pair , „ Un studiu sistematic al modelelor de tipuri abstracte de date ”, Theoretical Computer Science , vol. 33,1984, p. 139-174
Sébastien Veigneau , Abordări imperative și funcționale ale algoritmilor: aplicații în C și în CAML Light , Springer Science & Business Media,1999( citește online )
http://pageperso.lif.univ-mrs.fr/~denis.lugiez/Enseignement/L2/Cours/cours4.pdf

Vezi și tu