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