ELEMENTARNE

STRUKTURY DANYCH

ZBIORY



Zbiory dynamiczne



Operacje na zbiorach dynamicznych :



SEARCH (S, k)



INSERT (S, x)



DELETE (S, x)



MINIMUM (S)



MAXIMUM

(S)



SUCCESSOR (S, x)



PREDECESSOR (S, x)



STOSY

IMPLEMENTACJE ZBIORÓW

DYNAMICZNYCH



KOLEJKI



LISTY



jednokierunkowe



dwukierunkowe



cykliczne



DRZEWA

STOS

Struktura danych , w której

element

dodaje się za ostatnio wstawionym elementem,
a usuwa - ostatnio dodany element. (LIFO : LAST-IN, FIRST-
OUT)

Implementacja stosu w postaci tablicy :

array S[1..n] of integer ;

topS

= indeks ostatnio wstawionego elementu do S ;

( indeks wierzchołka stosu)

Stos S składa się z elementów

S[1 .. topS]

tablicy S .

Jeśli

topS = 0

, to stos S jest pusty.

4

7

2

tops = 3

STOSY

STOS_PUSTY(S) ;

{Sprawdza czy stos S
jest pusty}

begin
if topS = 0
then return TRUE
else return FALSE
end ;

PUSH ( S, x ) ;

{Dodaje element x do

stosu S}

begin
topS := topS + 1;
S[topS] := x
end ;

POP (S) ;

{Usuwa element ze stosu

S}

begin
if STOS-PUSTY (S)
then error
else
begin
topS := topS - 1;
return S[topS
+ 1]
end
end ;

KOLEJKA

Implementacja kolejki w postaci tablicy :

array Q[1..n] of integer ;

headQ

= indeks pierwszego elementu kolejki

(wskazuje na początek kolejki).

tailQ

= indeks wyznaczający miejsce,

w które można wstawić następny element do kolejki.

Kolejka Q składa się z elementów

Q

[headQ .. tailQ - 1]

tablicy Q .

Jesli

headQ = tailQ

, to kolejka Q jest pusta.

Struktura danych, w której element
dodaje się za ostatnio wstawionym elementem
a usuwa pierwszy wstawiony element (FIFO : FIRST-IN, FIRST-
OUT)

12 5

2 34

headQ = 1

tailQ = 5

KOLEJKA_PUSTA(Q) ;

{Sprawdza czy kolejka Q jest pusta}

begin
if headQ =tailQ
then return TRUE
else return FALSE
end ;

DO_KOLEJKI (Q, x ) ;

{Dodaje element x do

kolejki Q}

begin
Q[tailQ] := x;
tailQ:= tailQ+ 1;
end ;

Z_KOLEJKI(Q)

{Usuwa element z kolejki
Q }

begin
if
KOLEJKA_PUSTA(Q)
then error
else
begin
headQ:= headQ
+ 1;
return
Q[headQ -1]
end
end ;