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
1
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.
Rodzaje typów danych:
proste
złożone
ASD LJ S
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)
wskaz
nikowy (pointer)
ASD LJ S
2
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)
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.
ASD LJ S
Typy danych
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.
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).
ASD LJ S
3
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.
Podstawowymi jednostkami tworzącymi struktury danych są komórki (cells).
Struktury danych tworzy się poprzez agregacje takich komórek.
Rwe E
E  nazwa struktury
Rwe  relacja wejściowa
Rwew  relacja węwnętrzna
Rwew
Wirth N:
Algorytmy+struktury danych=programy.
ASD LJ S
Struktury danych
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.
ASD LJ S
4
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 = (a1, a2, ..., an)
Lewy koniec listy a1 - głowa listy (head),
Prawy koniec listy an - ogon listy (tail),
Długością listy:ćłLćł=n
Lista pusta L=( ) - szczególny przypadek listy.
ASD LJ S
5
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:
(0 0)
(1 1)
(1 0)
ASD LJ S
Lista
Podstawowe własności:
L1 = (a1, a2, ..., an)
L2 = (b1, b2, ..., bm), 0 d" i d" j d" n, m
Pozycja elementu na liście, wystąpienie (occurence) elementu:
L[i] = ai
Podlista:
L[i..j] = (ai, ai+1, ..., aj)
Złożenie list, konkatenacja (concatenate):
L1 & L2 = (a1, a2, ..., an, b1, b2, ..., bm)
ASD LJ S
6
Lista
Aby zbudować ADT reprezentujący listę na podstawie jej pojęcia matematycznego
należy zdefiniować zestaw operacji wykonywanych na elementach listy.
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
Listy powiązane
Linked lists
7
Lista
Rodzaje list:
Jednokierunkowa (powiązana pojedynczo),
Dwukierunkowa (powiązana podwójnie),
Cykliczna.
Rodzaje implementacji:
Wskaz
nikowa (dowiązaniowa),
Tablicowa.
ASD LJ S
Lista jednokierunkowa
Lista jednokierunkowa (Singly linked list).
Przykładowa definicja listy:
struct node
{
węzeł wartownik
ogon
głowa
int key;
(node, cell) (sentinel)
(tail)
(head)
node *next;
};
node *head, *tail;
null
ASD LJ S
8
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 wskaz
nik (pointer) do
innego elementu danej listy,
element listy
ogon listy
głowa listy
. . .
. . . /
L.head
/ (NULL)
Inf. merytorycz. (klucz)
Inf. organiz. (wskaz
nik)
ASD LJ S
Lista jednokierunkowa
Reprezentacja dowiązaniowa listy jednokierunkowej.
key next
tail
head
. . . /
L.head
x.key - wartość pola klucza elementu listy,
x.next  wskaz
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).
ASD LJ S
9
Lista jednokierunkowa
Podstawowe operacje listy jednokierunkowej (implementacja dowiązaniowa).
Wstawianie elementu x (pole key zostało Wstawianie elementu o kluczu k na początek listy:
zainicjowane) na początek listy L.
(Pseudokod). node *head;
void insert(int k)
{
INSERT_1LIST(L,x)
node *ptr=new node;
{
ptr->key=k;
x.next=L.head;
ptr->next=head;
L.head=x;
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
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
10
Lista jednokierunkowa
Podstawowe operacje listy jednokierunkowej (implementacja dowiązaniowa).
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
Tablicowa reprezentacja listy
Lista w reprezenyacji tablicowej ma postać rekordu,
A[1]
który składa się z:
A[2]
Tablicy o rozmiarze wystarczającym do
Właściwa lista
A[i]
zapamiętania najdłuższej przewidywanej listy.
.
.
Zmiennej last przechowującej pozycję ostatniego
last
elementu.
A[n]
.
.
Niewykorzystana
.
pamięć
.
typedef struct {
int A[maxLenght];
int last;
maxLenght
} LIST;
LIST *L
Tablica A reprezentująca listę L = (a1,a2,..ai...,an),
A[i]=ai, i=1 .,n.
ASD LJ S
11
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
12
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
Lista dwukierunkowa
Double linked list
13
Lista dwukierunkowa
Schemat listy dwukierunkowej.
struct node
{
int key;
node *prev, *next;
};
node *head, *tail;
prev key next
tail
. . .
L.head / /
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
14
Lista dwukierunkowa
Podstawowe operacje listy dwukierunkowej (reprezentacja dowiązaniowa).
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
Lista dwukierunkowa
Podstawowe operacje listy dwukierunkowej (reprezentacja dowiązaniowa).
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 wskaz
nika x należy
wywołać SEARCH_2LIST.
ASD LJ S
15
Lista dwukierunkowa
Wielotablicowa reprezentacja listy dwukierunkowej.
Każdy węzeł listy dwukierunkowej jest rekordem o trzech polach next, key, prev.
L.head / 11 21 25 41 /
Dla danego indeksu k wartości Key[k], Next[k] oraz Prev[k] określają element
(węzeł) listy.
1 2 3 4 5 6 7 8
L 7
Prev 3 5 7 /
Key 41 25 21 11
Next / 2 3 5
Lista L reprezentowana za pomocą tablic: Next, Key, Prev.
ASD LJ S
Lista dwukierunkowa
Reprezentacja listy dwukierunkowej w pojedynczej tablicy.
L.head / 11 21 25 41 /
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 15 17 18
L 13
A 7 25 4 1 41 / 13 21 1 / 11 7
Lista L reprezentowana za pomocą pojedynczej tablicy A.
ASD LJ S
16
Przykładowe struktury listowe
a) b)
c)
d)
ASD LJ S
Lista z przeskokami
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
pi(1 - p), gdzie: pd"1/2
ASD LJ S
17
Lista z przeskokami
/
HD
33
42
20
38
6 10 25
Czteropoziomowa skip list
C /
HD
A D
A A B C E E
Wyszukiwanie w trójpoziomowej skip list
ASD LJ S
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 wskaz
nikowa wymaga uwagi w działaniu na wskaz
nikach.
ASD LJ S
18
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
19
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 (a1, a2, ..., an) jest na szczycie
stosu, to wynikiem operacji PUSH (S, x) będzie sekwencja:
(a1, a2, ..., an, x).
2. Analogicznie, w wyniku operacji POP (S) otrzymamy:
(a1, a2, ..., an-1).
Zdejmowanie z pustego stosu generuje błąd.
ASD LJ S
20
Reprezentacja dowiązaniowa stosu
S = (a1, a2, ..., an)
S.top
an an-1 a1
. . .
/
Element struktury danych stosu
(node)
key next
ASD LJ S
Reprezentacja tablicowa stosu
typedef struct {
A[1]
int A[maxLenght];
A[2]
int top;
.
obszar
} STACK;
.
zajęty
.
STACK *S
A[n]
S.top
.
obszar
.
wolny
.
maxLenght
Tablica A reprezentująca stos S=(a1, a2, ..., an)
ASD LJ S
21
Reprezentacja tablicowa stosu
Podstawowe operacje. A
A
10
Wstawianie elementu na stos. 10
4
4
PUSH(S,x)
8
8
{
S.top
PUSH(S,5)
S.top=S.top+1; 2
2
S.A[S.top]=x;
S.top
5
}
Usuwanie elementu ze stosu.
A
A
POP(S)
10
10
{
POP(S)
IF (EMPTY(S)) 4
4
retun( błąd );
S.top
8
8
ELSE{
2
S.top=S.top-1; S.top 2
retun(S.top);
}
}
ASD LJ S
Reprezentacja tablicowa stosu
Podstawowe operacje.
// Czy stos pełny? // Czy stos pełny?
EMPTY(S) FULL(S)
{ {
return(S.top < 1); return(S.top e" maxLenght);
} }
// Zwracanie elementu ze stosu
TOP(S)
{
IF (EMPTY(S))
return( błąd );
ELSE
retun(S.A[S.top]);
}
ASD LJ S
22
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
23
Wskaz
nikowa reprezentacja kolejki
Q.rear
Q.front . . . /
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).
ASD LJ S
Interfejs kolejki
Wstawianie elementu na koniec kolejki. Czy kolejka jest pusta?.
(Pseudokod).
(Pseudokod).
EMPTY(Q)
ENQUEUE(Q,x)
{
{
Q.rear.next=x; return(Q.rear == Q.front)
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;
}
ASD LJ S
24
Kolejka cykliczna
Tablicowa implementacja kolejki.
typedef struct {
int A[maxLenght];
int front,rear;
} QUEUE;
QUEUE *Q;
1 2 3 4 5 6 7 8 9 10
Q.rear
Q.front 2 5 6 11 3 9 0 1 8
ASD LJ S
Kolejka cykliczna
Elementy kolejki znajdują się na pozycjach: front, front+1, ..., rear-1.
a)
1 2 3 4 5 6 7 8 9 10
A 2 5 6 11 3 9 0 1 8
front rear
b)
1 2 3 4 5 6 7 8 9 10
A 2 5 6 11 9 0 1 8 7
rear front
Kolejka pełna: Q.front = (Q.rear mod maxLength + 1)
ASD LJ S
25
Kolejka cykliczna
c)
1 2 3 4 5 6 7 8 9 10
6 11 3 9 0
A
front
rear
d)
1 2 3 4 5 6 7 8 9 10
11 5 6 8 7
A
rear
front
e)
1 2 3 4 5 6 7 8 9 10
A 2 5 6 11 10 9 0 1 8 7
rear
front
Kolejka pusta: Q.front = Q.rear
ASD LJ S
Kolejka cykliczna
Interfejs kolejki cyklicznej.
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);
}
}
CYCLE(k)
{
return(k mod maxlength+1)
}
ASD LJ S
26
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
27