Absztrakt adatszerkezetek definialasa. Halmaz, zsak, verem, sor mint absztrakt adatszerkezet szintaktikaja, szemantikaja.

Absztrakt adatszerkezetek definiálása. Halmaz, zsák, verem, sor mint absztrakt adatszerkezet szintaktikája, szemantikája.

Definíció: Absztrakt elemi adat: Olyan adategység, mellyel a programozás adott szintjén végezhetők műveletek, de annak részeivel nem.

Definíció: Elemi adattípus (objektum): egy (A,M 646h76g ) kettős, ahol A az adattípusba tartozó absztrakt adatok nem üres halmaza, M pedig az m: AxAx....xA A alakú műveletek véges halmaza.

Példa

Egész típus absztrakciója:

A:= ( egész számok )

M:=

Szintaktika: + : AxA A

- : AxA A

: A A

Boolean típus:

A:= M:=

Szintaktika: Ù : AxA A

: AxA A

: A A

Definíció: Összetett adattípus absztrakciója egy (V,F) kettős, ahol V=, m ³ 2 és

V₁ az összetett adatok (vagy adatszerkezetek) nem üres halmaza,

V₂ az összetett adatokat alkotó elemi adatok nem üres halmaza

V₃... V_m segédhalmazok

F a következő f_i műveletek véges halmaza:

f_i : V_i1 x V_i2 x ... x V_ik V_in (k³

és az f_i műveletek között az

f_j : V_j1 x V_j2 x ... x V_jm V₁ (m³

alakú műveleteknek egy olyan részhalmaza, melyek egymás utáni alkalmazásával a V₁ halmaz eleme előállítható.

Adatszerkezetek szemantikája

Definíció: Szemantika: a műveletek jelentését adja meg.

Megadás:

Matematikában:         axiómák segítségével

Itt:       Megadjuk a szelekciós műveleteknek a konstrukciós műveletekkel előállított adatszerkezetekre gyakorolt hatását.

Halmaz: h H              e₁, e₂, e₃ HE

delete ( empty,e ) = empty

delete ( insert(h, e₁), e₁ ) =

ha e₁= e₂ , akkor delete(h, e₁)

különben insert(delete(h, e₂), e₁)

e:= e₁= e₂

ha e h , akkor insert(h,e)=h

ha e Ï h , akkor delete(h,e)=h

másrészt delete(insert(h,e),e)=h

delete(insert(h,e),e)=delete(h,e)

has(empty,e)=¯

has(insert(h, e₁), e₂)=

ha e₁= e₂ , akkor

különben: has(h, e₂)

Zsák:

bdelete(bempty,e)=bempty

bdelete(binsert(b, e₁), e₂)=

ha e₁= e₂ , akkor b

különben: binsert(bdelete(b, e₂), e₁)

bhas(bempty,e)=¯

bhas(binsert(b, e₁), e₂)=

ha e₁= e₂ , akkor

különben: bhas (b, e₂)

Verem: v verem       e elem

pop(push(v,e))=v                      e

top(push(v,e))=e

pop(create)=create                             v push (v,e)

top(create=error

Sor: s sor             e elem

remove(add(s,e))=                                            add(s,e)

ha s=new, akkor new

különben: add(remove(s),e) e

s

remove(s)

front(add(s,e))=

ha s=new, akkor e

kül önben: front(s) add(s,e)

e s

remove(new)=new

front(new)=error