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 ;