1

Dynamiczne struktury danych

Lista, Stos, Kolejka

Podstawowa terminologia

Typy danych (

Data types

)

Struktury Danych (

Data Structures

)

Abstrakcyjne typy danych ADT (

Abstract Data Types

)

ASD

LJ

S

2

Typy danych

Typ danych - zbiór wartości, które może przyjmować zmienna (danego typu) lub
wyrażenie, albo które mogą być generowane przez operator lub funkcję.

Moc typu danych to liczba różnych wartości należących do typu. Moc typu wyznacza
wielkość pamięci (w bitach) potrzebnej do reprezentowania wartości tego typu.

Z typem danych skojarzone są operatory działające na wartościach tego typu.
Operatory mogą być standardowe (zdefiniowane w języku programowania) lub
niestandardowe (zdefiniowane przez użytkownika, programistę) w postaci
konkretnych funkcji.

Operatory stanowią integralny element definicji typu danych.

ASD

LJ

S

Rodzaje typów danych:



proste



złożone

Proste typy danych

Proste typy danych - typy, których elementy (wartości) nie składają się z elementów
innych typów danych (są nierozkładalne).

Przykłady prostych typów danych:



bitowy (

bit

)



bajtowy (

byte

)



całkowity (

integer

)



rzeczywisty (

real

)



logiczny (

boolean

)



znakowy (

char

)



łańcuchowy (

string

)



wyliczeniowy (

enumerated

)



okrojony (

subrange

)



wskaźnikowy (

pointer

)

ASD

LJ

S

3

Złożone typy danych

Złożony typ danych stanowi zazwyczaj kombinacje typów prostych oraz

mechanizmów agregujących.

Przykłady złożonych typów danych:



tablica (

array

)



rekord (

record

)



zbiór (

set

)



lista (

list

)



drzewo (

tree

)



graf (

graph

)



kolejka (

queue

)



stos (

stack

)

ASD

LJ

S

Mechanizmy agregujące za pomocą których tworzy się typy złożone z typów
prostych są zależne od języków programowania.

Typy danych

Podstawowa zasada realizowana przez większość języków programowania w
odniesieniu do typów danych określa dostęp do jedno lub wielobajtowych komórek
pamięci (

cells

).

Komórkę można traktować jako miejsce przechowujące pojedynczą wartość,
należącą do danego typu podstawowego lub złożonego.
Liczby całkowite i zmiennoprzecinkowe są traktowane jako typy arytmetyczne
(

arithmetic types

).

Aspekty rozpatrywania typów danych:

1. Statyczny – system typu (

type system

) związany ze zbiorem wartości

odniesionym do konkretnego typu,

2. Dynamiczny - związany z operacjami na wartościach z definiowanego zbioru.

ASD

LJ

S

4

Struktury danych

Struktura danych - zbiór zmiennych określonych typów, posiadający określoną
organizację (strukturę) i związany z nią sposób dostępu do danych.

Struktury danych opisują sposób organizacji oraz metody dostępu do danych.

Podstawowe mechanizmy agregujące: tablica, rekord, plik, drzewo, lista,
struktury, unie.

E – nazwa struktury
R

we

– relacja wejściowa

R

wew

– relacja węwnętrzna

Wirth N:
Algorytmy+struktury danych=programy.

Podstawowymi jednostkami tworzącymi struktury danych są komórki (

cells

).

Struktury danych tworzy się poprzez agregacje takich komórek.

R

we

E

R

wew

ASD

LJ

S

Struktury danych

ASD

LJ

S

Definiując strukturę danych, wiążemy ją z operacjami służącymi do:



wstawiania nowych danych,



wydobywania konkretnych danych na podstawie ustalonych kryteriów
wyszukiwania,



przeglądania wszystkich danych w strukturze w zadanej kolejności,



porządkowania danych według zadanego kryterium,



usuwania danych ze struktury.

5

Abstrakcyjne typy danych

ADT (

Abstract Data Types

) – zbiór danych tworzony i opisywany w formalny

sposób poprzez własności danych i operacji wykonywanych na nich (a nie
poprzez reprezentację danych w pamięci i ich implementację).

ADT - zbiór danych i operacji na tych danych, które są dostępne jedynie za

pośrednictwem zdefiniowanego interfejsu.

Interfejs ADT określa sposób dostepu do danych i definiuje operacje na nich.

Implementacja ADT polega na zdefiniowaniu jego odpowiednika w kategoriach

konkretnego języka programowania oraz zapisaniu w tym języku funkcji i
procedur do wykonywania podstawowych operacji.

Podstawowe ADT: lista, stos, kolejka.

ADT jest połączeniem modelu danych i zbioru operacji jakie można na tym modelu
wykonać. Dwa identyczne modele, połączone z różnymi zbiorami operacji
określają różne ADT.

ASD

LJ

S

Lista

Lista (

List

) - skończona sekwencją elementów (obiektów) ułożonych w liniowym

porządku.

W matematycznym sensie lista to zbiór elementów :

L = (a

1

, a

2

, ..., a

n

)



Lewy koniec listy a

1

- głowa listy (

head

),



Prawy koniec listy a

n

- ogon listy (

tail

),



Długością listy:L=n

Lista pusta L=( ) - szczególny przypadek listy.

ASD

LJ

S

6

Lista

Lista - przykłady:

L = (I, II, III, ..., XII) – lista miesięcy,

L = (hel, neon, argon, krypton, ksenon, radon) – lista gazów

szlachetnych uporządkowanych zgodnie z masą atomową,

L = <(0, 0), (1, 0), (1, 1)> – lista list współrzędnych wierzchołków

figury geometrycznej:

(1 0)

(1 1)

(0 0)

ASD

LJ

S

Lista

L1 = (a

1

, a

2

, ..., a

n

)

L2 = (b

1

, b

2

, ..., b

m

),

0 ≤ i ≤ j ≤ n, m

Pozycja elementu na liście, wystąpienie (

occurence

) elementu:

L[i] = a

i

Podlista:

L[i..j] = (a

i

, a

i+1

, ..., a

j

)

Złożenie list, konkatenacja (

concatenate

):

L1 & L2 = (a

1

, a

2

, ..., a

n

, b

1

, b

2

, ..., b

m

)

Podstawowe własności:

ASD

LJ

S

7

Lista



Operacje na początku (końcu ) listy:

-

wstawianie,

-

usuwanie,

-

dostęp do elementu.



Operacje złożone:

-

wyszukiwanie elementu,

-

wstawianie za k-ty element,

-

usunięcie k-tego elementu,

-

przestawienie k-tego elementu na początek (koniec),

-

odwracanie listy,

-

łączenie list.

ASD

LJ

S

Aby zbudować ADT reprezentujący listę na podstawie jej pojęcia matematycznego
należy zdefiniować zestaw operacji wykonywanych na elementach listy.

Listy powiązane

Linked lists

8

Lista

Rodzaje list:



Jednokierunkowa (powiązana pojedynczo),



Dwukierunkowa (powiązana podwójnie),



Cykliczna.

Rodzaje implementacji:



Wskaźnikowa (dowiązaniowa),



Tablicowa.

ASD

LJ

S

Lista jednokierunkowa

Lista jednokierunkowa (

Singly linked list

).

Przykładowa definicja listy:

struct node
{

int key;
node *next;

};

node *head, *tail;

głowa
(head)

ogon

(tail)

null

wartownik

(sentinel)

węzeł

(node, cell)

ASD

LJ

S

9

Lista jednokierunkowa

Każdy element listy przechowuje dwa typy informacji:

1.

Merytoryczną (widoczną na zewnątrz), zw. kluczem (

key

),

2.

Organizacyjną (widoczna wewnątrz), którą jest wskaźnik (

pointer

) do

innego elementu danej listy,

ASD

LJ

S

/ (NULL)

. . .

/

głowa listy

ogon listy

. . .

element listy

Inf. organiz. (wskaźnik)

Inf. merytorycz. (klucz)

L.head

Lista jednokierunkowa

Reprezentacja dowiązaniowa listy jednokierunkowej.

x.key - wartość pola klucza elementu listy,

x.next – wskaźnik do następnika (jeżeli x.next ma wartość

NULL

, to x jest

ogonem)

L.head – wskazuje na pierwszy element listy (głowę) (jeżeli L.head ma wartość

NULL

to lista jest pusta).

key

next

/

L.head

tail

. . .

head

ASD

LJ

S

10

Lista jednokierunkowa

Podstawowe operacje listy jednokierunkowej (implementacja dowiązaniowa).

Wyszukiwanie elementu x o kluczu k na liście L..
(Pseudokod).

SEARCH_1LIST(L,k)
{

x=L.head;
WHILE(x≠NULL and x.key≠k){

x=x.next;

}
return(x)

}

Złożonośc algorytmu O(n).

ASD

LJ

S

Lista jednokierunkowa

Podstawowe operacje listy jednokierunkowej (implementacja dowiązaniowa).

Wstawianie elementu x (pole key zostało
zainicjowane) na początek listy L.
(Pseudokod).

INSERT_1LIST(L,x)
{

x.next=L.head;
L.head=x;

}

Wstawianie elementu o kluczu k na początek listy:

node *head;
void insert(int k)
{

node *ptr=new node;
ptr->key=k;
ptr->next=head;
head=ptr;

}

Złożonośc algorytmów O(1).

Usuwanie elementu x z początku listy L.

(Pseudokod).

DELETE_1LIST(L,x)
{

L.head=x.next;

}

ASD

LJ

S

11

Lista jednokierunkowa

Wyszukiwanie elementu o kluczu k z użyciem wartownika.

node *head, *sentinel;

node *search (int k)
{

sentinel->key=k;
node *ptr=head;
while (ptr->key!=k)

ptr=ptr->next;

if(ptr==sentinel)

return NULL;

else

return ptr;

}

ASD

LJ

S

Podstawowe operacje listy jednokierunkowej (implementacja dowiązaniowa).

Tablicowa reprezentacja listy

Lista w reprezenyacji tablicowej ma postać rekordu,
który składa się z:



Tablicy o rozmiarze wystarczającym do
zapamiętania najdłuższej przewidywanej listy.



Zmiennej last przechowującej pozycję ostatniego
elementu.

A[1]
A[2]

A[i]

.
.

A[n]

.
.
.
.

maxLenght

last

Właściwa lista

Niewykorzystana
pamięć

Tablica A reprezentująca listę L = (a

1

,a

2

,..a

i

...,a

n

),

A[i]=a

i

, i=1H.,n.

typedef struct {

int A[maxLenght];
int last;

} LIST;

LIST *L

ASD

LJ

S

12

Tablicowa reprezentacja listy

Operacje reprezentacji tablicowej.

Wstawianie elementu o wartości x na pozycję p w liście L.
(Pseudokod).

INSERT_TAB(L,x,p)
{

IF(L.last > maxLenght)

return(„lista pełna”);

ELSE{
FOR q=L.last,L.last-1,...p

L.A[q+1]=L.A[q];

L.A[p]=x;
L.last=L.last+1;
}

}

Złożonośc algorytmu O(n).

ASD

LJ

S

Tablicowa reprezentacja listy

Operacje reprezentacji tablicowej.

Usuwanie elementu z pozycji p z listy L. (Pseudokod).

DELETE_TAB(L,p)
{

IF(p>L.last or p<1)

return(„w liście brak żądanej pozycji”);

ELSE{

L.last=L.last–1;
FOR q=p,p+1,...L.last

L.A[q]=L.A[q+1];

}

}

Złożoność algorytmu O(n).

ASD

LJ

S

13

Lista dwukierunkowa

Double linked list

Tablicowa reprezentacja listy

Operacje reprezentacji tablicowej.

Wyszukiwanie elementu x w liście L i zwracanie pozycji.
(Pseudokod).

SEARCH_TAB(L,x)
{

FOR q=1,2,...L.last

IF(L.A[q]==x)

return(q);

return(L.last+1);// jeśli nie znaleziono

}

Złożonośc algorytmu O(n).

ASD

LJ

S

14

Lista dwukierunkowa

/

key

next

/

L.head

tail

. . .

prev

Schemat listy dwukierunkowej.

struct node
{

int key;
node *prev, *next;

};

node *head, *tail;

ASD

LJ

S

Lista dwukierunkowa

Podstawowe operacje listy dwukierunkowej (reprezentacja dowiązaniowa).

Wstawianie elementu x (którego pole key zostało zainicjowane) na
początek listy L. (Pseudokod).

INSERT_2LIST(L,x)
{

x.next=L.head;
IF(L.head ≠ NULL)

L.head.prev=x;

L.head=x;
x.prev=NULL;

}

Złożonośc algorytmu O(1).

ASD

LJ

S

15

Lista dwukierunkowa

Wyszukiwanie elementu x o kluczu k na liście L.
(Pseudokod).

SEARCH_2LIST(L,k)
{

x=L.head;
WHILE (x≠NULL and x.key≠k){

x=x.next;

}
retun(x)

}

Złożonośc algorytmu O(n).

ASD

LJ

S

Podstawowe operacje listy dwukierunkowej (reprezentacja dowiązaniowa).

Lista dwukierunkowa

Usuwanie elementu x z listy L. (Pseudokod).

DELETE_2LIST(L,x)
{

IF(x.prev ≠ NIL)

x.prev.next=x.next;

ELSE

L.head=x.next;

IF(x.next ≠ NULL)

x.next.prev=x.prev;

}

Złożonośc algorytmu DELETE_2LIST: złożoność O(1). Pesymistyczna złożoność usunięcia
elementu o zadanym kluczu wynosi O(n) , ponieważ do wyznaczenia wskaźnika x należy
wywołać SEARCH_2LIST.

ASD

LJ

S

Podstawowe operacje listy dwukierunkowej (reprezentacja dowiązaniowa).

16

Lista dwukierunkowa

Wielotablicowa reprezentacja listy dwukierunkowej.

Każdy węzeł listy dwukierunkowej jest rekordem o trzech polach next, key, prev.

Dla danego indeksu k wartości Key[k], Next[k] oraz Prev[k] określają element
(węzeł) listy.

/

11

21

25

41

/

L.head

Lista L reprezentowana za pomocą tablic: Next, Key, Prev.

1

2

3

4

5

6

7

8

3

5

7

Prev

/

41

25

21

Key

11

/

2

3

Next

5

7

L

ASD

LJ

S

Lista dwukierunkowa

Reprezentacja listy dwukierunkowej w pojedynczej tablicy.

/

11

21

25

41

/

L.head

Lista L reprezentowana za pomocą pojedynczej tablicy A.

7

25

4

1

41

/

13

21

1

/

11

7

1

2

3

4

5

6

7

8

9

10

11

12 13

14

15 15

17 18

13

A

L

ASD

LJ

S

17

Przykładowe struktury listowe

a)

b)

c)

d)

ASD

LJ

S

Lista z przeskokami

ASD

LJ

S

Lista z przeskokami (

skip list

) jest przeznaczona do przechowywania danych

uporządkowanych.

Oparta na równoległej, warstwowej posortowanej liście jednokierunkowej.

Każdy element oprócz dowiązania do następnika może posiadać pewną liczbę

dowiązań do elementów dalszych.

Liczba połączeń elementu z innymi określa jego stopień (

degree

,

height

), przy czym

i-te łącze wskazuje na kolejny element stopnia co najmniej i.

Skip list stanowi alternatywę dla zrównoważonych drzew binarnych.

Oczekiwana złożoność operacji wyszukiwania, wstawiania nowego elementu do

listy oraz usunięcia elementu wynosi O(logn).

Pierwszy element ma zawsze maksymalny stopień a dodawane elementy

otrzymują stopień wylosowany wg geometrycznego rozkładu prawdopodobieństwa

p

i

(1 − p), gdzie: p≤1/2

18

Lista z przeskokami

ASD

LJ

S

42

HD

6

10

20

25

38

/

33

E

HD

/

C

C

D

E

A

B

A

A

Czteropoziomowa skip list

Wyszukiwanie w trójpoziomowej skip list

Porównanie implementacji list

Implementacja tablicowa wymaga a priori znajomości maksymalnej długości

listy.

Niektóre operacje w tablicowej implementacji trwają dłużej np.

INSERT

,

DELATE

.

Implementacja tablicowa z powodu statycznego operowania pamięcią jest

nieefektywna.

Implementacja wskaźnikowa wymaga uwagi w działaniu na wskaźnikach.

ASD

LJ

S

19

Zastosowania list

Zastosowania list powiązanych.

Listy w aplikacjach obsługujących pocztę elektroniczną,

Listy przewijane,

Zarządzanie pamięcią przez system operacyjny w zakresie sterowania

procesami,

Inne struktury danych oparte na listach: stosy, kolejki, grafy, tablice

asocjacyjne.

ASD

LJ

S

Stos

Stack

20

Stos

Podstawowa terminologia.

Stos – struktura liniowo uporządkowanych danych określonego typu. Wszystkie

dostępne operacje wykonywane są na jednym końcu tej struktury, szczycie
stosu (

top

).

Stos obsługiwany jest według zasady LIFO (

Last-in-First-out

).

Podstawowe operacje:

Wstawianie elementu x do struktury danych (

PUSH

),

Usuwanie elementu ze struktury danych (

POP

),

Sprawdzenie czy stos jest pusty (

EMPTY

),

Sprawdzenie czy stos jest pełny (

FULL

),

Zwrot elementu szczytu stosu, bez usuwania go ze struktury danych
TOP (S).

ASD

LJ

S

Stos

1.

Zakładając, że skrajnie prawy element sekwencji (a

1

, a

2

, ..., a

n

) jest na szczycie

stosu, to wynikiem operacji PUSH (S, x) będzie sekwencja:

(a

1

, a

2

, ..., a

n

, x).

2.

Analogicznie, w wyniku operacji POP (S) otrzymamy:

(a

1

, a

2

, ..., a

n-1

).

Zdejmowanie z pustego stosu generuje błąd.

ASD

LJ

S

21

Reprezentacja dowiązaniowa stosu

S = (a

1

, a

2

, ..., a

n

)

ASD

LJ

S

Element struktury danych stosu

(

node

)

key

next

a

1

S.top

. . .

a

n

a

n-1

/

Reprezentacja tablicowa stosu

A[1]
A[2]

.
.
.

A[n]

.
.
.

maxLenght

S.top

obszar
zajęty

obszar
wolny

Tablica A reprezentująca stos S=(a

1

, a

2

, ..., a

n

)

typedef struct {

int A[maxLenght];
int top;

} STACK;

STACK *S

ASD

LJ

S

22

Reprezentacja tablicowa stosu

Podstawowe operacje.

Wstawianie elementu na stos.

PUSH(S,x)
{

S.top=S.top+1;
S.A[S.top]=x;

}

Usuwanie elementu ze stosu.

POP(S)
{

IF (EMPTY(S))

retun(”błąd”);

ELSE{

S.top=S.top-1;
retun(S.top);

}

}

A

S.top

10

4

8

2

A

10

4

8

2

S.top

ASD

LJ

S

S.top

A

10

4

8

2

5

PUSH(S,5)

S.top

A

10

4

8

2

POP(S)

Reprezentacja tablicowa stosu

Podstawowe operacje.

// Czy stos pełny?

EMPTY(S)
{

return(S.top < 1);

}

// Czy stos pełny?

FULL(S)
{

return(S.top ≥ maxLenght);

}

// Zwracanie elementu ze stosu

TOP(S)
{

IF (EMPTY(S))

return(”błąd”);

ELSE

retun(S.A[S.top]);

}

ASD

LJ

S

23

Kolejka

Queue

Kolejka

Kolejka - dynamiczna struktura danych, oparta na modelu listy i zorganizowana

według zasady FIFO (

First-in First-out

).

Interfejs kolejki:

1. DEQUEUE – usuwanie elementu z początku kolejki

2. ENQUEUE – wstawianie elementu na koniec kolejki

3. EMPTY – sprawdzenie czy kolejka jest pusta

4. FRONT – zwracanie pierwszego elementu

5. CLEAR – tworzenie kolejki pustej

ASD

LJ

S

24

Wskaźnikowa reprezentacja kolejki

Q.front - wskazuje na początek kolejki (niezbędny do wykonywania operacji:

FRONT, DEQUEUE, EMPTY),

Q.rear - wskazuje na koniec kolejki (niezbędny do wykonywania operacji:

ENQUEUE, EMPTY).

Q.front

/

Q.rear

. . .

ASD

LJ

S

Interfejs kolejki

Wstawianie elementu na koniec kolejki.
(Pseudokod).

ENQUEUE(Q,x)
{

Q.rear.next=x;
x.next=NULL;
Q.rear=x;

}

Usuwanie elementu z początku kolejki.
(Pseudokod).

DEQUEUE(Q)
{

IF(EMPTY(Q))

return(0);

ELSE

Q.front=Q.front.next;

}

Czy kolejka jest pusta?.
(Pseudokod).

EMPTY(Q)
{

return(Q.rear == Q.front)

}

ASD

LJ

S

25

Kolejka cykliczna

Tablicowa implementacja kolejki.

2

1

5

2

6

3

11

4

3

5

9

6

0

7

1

8

8

9

10

Q.front

Q.rear

ASD

LJ

S

typedef struct {

int A[maxLenght];
int front,rear;

} QUEUE;

QUEUE *Q;

Kolejka cykliczna

Elementy kolejki znajdują się na pozycjach: front, front+1, ..., rear-1.

2

1

5

2

6

3

11

4

3

5

9

6

0

7

1

8

8

9

10

front

rear

a)

A

2

1

5

2

6

3

11

4

5

9

6

0

7

1

8

8

9

7

10

rear front

b)

A

Kolejka pełna: Q.front = (Q.rear mod maxLength + 1)

ASD

LJ

S

26

Kolejka cykliczna

1

2

6

3

11

4

3

5

9

6

0

7

8

9

10

front

rear

c)

A

11

1

5

2

3

4

5

6

7

6

8

8

9

7

10

d)

front

rear

A

2

1

5

2

6

3

11

4

10

5

9

6

0

7

1

8

8

9

7

10

rear

front

e)

A

ASD

LJ

S

Kolejka pusta: Q.front = Q.rear

Kolejka cykliczna

Interfejs kolejki cyklicznej.

CYCLE(k)
{

return(k mod maxlength+1)

}

ENQUEUE(Q,x)
{

IF (CYCLE(Q.rear)==Q.front)

return(error); // kolejka pełna

ELSE{

Q.A[Q.rear]= x;
Q.rear=CYCLE(Q.rear);

}

}

ASD

LJ

S

27

Kolejka cykliczna

Interfejs kolejki cyklicznej.

DEQUEUE(Q)
{

IF (Q.front == Q.rear)

return(error); // kolejka pusta

ELSE

Q.front=CYCLE(Q.front);

}

EMPTY(Q)
{

return(Q.front == Q.rear);

}

Funkcje ENQUEUE, DEQUEUE działają w czasie O(1).

ASD

LJ

S