Programowanie ze strukturami danych
Wykªad 4
Stanisªaw Goldstein
Wydziaª Matematyki i Informatyki U
March 19, 2012
Stanisªaw Goldstein
Programowanie ze strukturami danych Wykªad 4
Spis tre±ci
Stanisªaw Goldstein
Programowanie ze strukturami danych Wykªad 4
Abstrakcyjny obiekt danych denicja
Abstrakcyjny obiekt danych jest to pojedynczy obiekt, znany tylko poprzez swoje operacje (metody).
Maj¡c dany ATD mo»na tworzy¢ wiele obiektów tego typu. AOD
dostarcza zawsze tylko jednego obiektu.
Stanisªaw Goldstein
Programowanie ze strukturami danych Wykªad 4
Realizacja ATD i AOD w Adzie
ATD jest realizowany jako pakiet z typem prywatnym i z
operacjami dziaªaj¡cymi na tym typie. W cz¦±ci prywatnej
pakietu podany jest sposób implementacji struktury tego typu.
AOD jest realizowany jako pakiet (na ogóª) bez cz¦±ci
prywatnej, podaj¡cy w specykacji wyª¡cznie operacje
(metody) danego AOD.
Stanisªaw Goldstein
Programowanie ze strukturami danych Wykªad 4
Denicja przypomnienie
Stos to abstrakcyjny typ danych z dwiema operacjami: wstawiania i usuwania elementu wstawionego jako ostatni (spo±ród elementów pozostaj¡cych w stosie). Operacje te w przypadku stosu nazywa si¦
zwyczajowo wstawianiem na stos (push) i zdejmowaniem ze stosu (pop).
Stanisªaw Goldstein
Programowanie ze strukturami danych Wykªad 4
Realizacja AOD Stos ograniczony
package stos_ogr i s
subtype typ i s i n t e g e r ;
−− max : c o n s t a n t i n t e g e r : = 1 0 0 ;
−− s t a ª a max j e s t t u podana t y l k o d l a i n f o r m a c j i u » y t k o w n i k a
−− sªowo i n t e g e r w t e j d e f i n i c j i mo»na o p u ± c i ¢
procedure push ( x : i n typ ) ;
f u n c t i o n pop r e t u r n typ ;
end stosy_ogr ;
Stanisªaw Goldstein
Programowanie ze strukturami danych Wykªad 4
Realizacja ATD Stosy ograniczone
package stosy_ogr i s
subtype typ i s i n t e g e r ;
max : c o n s t a n t i n t e g e r :=100;
type stos_ogr i s p r i v a t e ;
procedure push ( s : i n out stos_ogr ; x : i n typ ) ;
procedure pop ( s : i n out stos_ogr ; x : out typ ) ;
p r i v a t e
subtype i n d e k s i s i n t e g e r range 1 . . max ;
subtype i n d e k s _ r o z s z e r z o n y i s i n t e g e r range 0 . . max ; type Tablica_Ustalona i s a r r a y ( i n d e k s ) of typ ; type stos_ogr i s r e c o r d
T a b l i c a
: Tablica_Ustalona ;
Wskaznik
: Indeks_Rozszerzony := 0 ;
end r e c o r d ;
end stosy_ogr ;
Stanisªaw Goldstein
Programowanie ze strukturami danych Wykªad 4
Implementacja ATD Stosy ograniczone
package body stosy_ogr i s
procedure push ( s : i n out stos_ogr ; x : i n typ ) i s begin
s . wskaznik := s . wskaznik + 1 ;
s . t a b l i c a ( s . wskaznik ) := x ;
end push ;
procedure pop ( s : i n out stos_ogr ; x : out typ ) i s
begin
x := s . t a b l i c a ( s . wskaznik ) ;
s . wskaznik := s . wskaznik − 1 ;
end pop ;
end stosy_ogr ;
Stanisªaw Goldstein
Programowanie ze strukturami danych Wykªad 4
Implementacja AOD Stos ograniczony
package body stos_ogr i s
max : c o n s t a n t := 100;
wskaznik : i n t e g e r range 0 . . max := 0 ;
t a b l i c a : a r r a y ( 1 . . max) of typ ;
procedure push ( x : i n typ ) i s
begin
wskaznik := wskaznik + 1 ;
t a b l i c a ( wskaznik ) := x ;
end push ;
f u n c t i o n pop r e t u r n typ i s
x : typ := t a b l i c a ( wskaznik ) ;
begin
wskaznik := wskaznik − 1 ;
r e t u r n x ;
end pop ;
end stos_ogr ;
Stanisªaw Goldstein
Programowanie ze strukturami danych Wykªad 4