1
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
1
Struktury dynamiczne
LISTY WSKAŹNIKOWE:
listy z dowiązaniami jednokierunkowymi,
listy z dowiązaniami dwukierunkowymi,
listy cykliczne z wartownikiem ...
Lista jednokierunkowa:
...
GŁOWA
pole kluczowe
(dane)
pole wskaźnikowe
(wskazanie na następny rekord)
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
2
Lista dwukierunkowa:
...
pole kluczowe
(dane)
pole wskaźnikowe
(na następny rekord)
pole wskaźnikowe
(na poprzedni rekord)
GŁOWA
Kolejność rekordów na liście jest jednoznacznie ustalona przez
liczbę wskazań (adresów) jakie należy odczytać zaczynając od
głowy listy np. w celu poznania zawartości ich pola kluczowego.
1.
2.
3.
N
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
3
Lista dwukierunkowa cykliczna z wartownikiem:
...
pole kluczowe
(dane)
pole wskaźnikowe
(na następny rekord)
pole wskaźnikowe
(na poprzedni rekord)
wartownik
(specjalna
wartość pola
kluczowego)
GŁOWA
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
4
Algorytm sumowania płac wszystkich pracowników firmy,
których dane zapamiętano w liście jednokierunkowej:
Użyte struktury danych
Rekord do przechowania danych pojedynczego pracownika:
2700
Dynamiczny
Jan
pole tekstowe
IMIĘ
-
pole liczbowe
PŁACA
-
pole tekstowe
NAZWISKO
-
pole wskaźnikowe
NASTĘPNY
-
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
5
Lista do przechowania danych wszystkich pracowników:
1750
3000
2700
2500
GŁOWA
(wskaźnik)
. . .
NIL
Zmienna wskaźnikowa P do wskazywania bieżącego
rekordu z danymi pracownika,
pomocnicza zmienna S do przechowywania wyniku.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
6
1. S
←
0 (ustalenie początkowej wartości sumy płac),
2. P
←
GŁOWA
(ustalenie początkowej wartości bieżącego wskaźnika),
3. dopóki P
≠
NIL wykonuj co następuje:
3.1. S
←
S + PŁACA.[P],
3.2. P
←
NASTĘPNY.[P],
4. odczytaj wartość zmiennej S.
1750
3000
2700
2500
GŁOWA
. . .
NIL
PŁACA
NASTĘPNY
P
2
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
7
P
≠
NIL
TAK
NIE
S
←
S + PŁACA.[P]
P
←
NASTĘPNY.[P]
P
←
GŁOWA
S
←
0
start
stop
po zakończeniu działania
algorytmu zmienna S ma
wartość sumy płac wszystkich
pracowników
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
8
STOS (zrealizowany na liście jednokierunkowej):
...
GŁOWA
WSTAW
Ustalamy, że nowy rekord może być wstawiony tylko jako
pierwszy na liście, czyli operacja WSTAW nie wymaga parametru!
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
9
...
GŁOWA
USUŃ
Ustalamy, że usuwany z listy może być tylko rekord, który jest
pierwszy na liście, czyli operacja USUŃ nie wymaga parametru!
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
10
STOS
zdjęcie
ze stosu
(
USUŃ
)
położenie
na stos
(
WSTAW
)
kolejność
wstawiania
1
2
n
n–1
Brak
dostępu
dla operacji
WSTAW
i USUŃ
STOS = lista LIFO (Last-In-First-Out)
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
11
KOLEJKA (zrealizowana na liście jednokierunkowej):
...
GŁOWA
WSTAW
Ustalamy, że nowy rekord może być wstawiony tylko jako
pierwszy na liście, czyli operacja WSTAW nie wymaga parametru!
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
12
...
GŁOWA
USUŃ
OGON
Ustalamy, że usuwany z listy może być tylko rekord, który jest
ostatni na liście, czyli operacja USUŃ nie wymaga parametru!
3
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
13
...
KOLEJKA
odłączenie
od kolejki
(
USUŃ
)
dołączenie
do kolejki
(
WSTAW
)
kolejność
wstawiania
1
2
n n–1
Brak
dostępu
dla operacji
WSTAW
i USUŃ
3
KOLEJKA = lista FIFO (First-In-First-Out)
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
14
DRZEWA (ukorzenione):
KORZEŃ
pole kluczowe
pole wskaźnikowe
(wskazanie na 2. potomka)
pole wskaźnikowe
(wskazanie na 1. potomka)
pole wskaźnikowe
(wskazanie na rodzica)
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
15
Drzewiaste struktury danych:
tylko jeden rekord w takiej strukturze ma w polu
wskaźnikowym na rodzica adres pusty NIL – ten rekord
nazywany jest korzeniem, bo przy budowaniu struktury był
pierwszym do niej wstawionym,
pola wskaźnikowe rekordu używanego do budowy takiej
struktury mogą wskazywać na wiele rekordów potomnych
oddalonych od pierwszego (korzenia) o taką samą liczbę
wskazań, które należy odczytać np. w celu poznania
zawartości ich pola kluczowego,
dla każdych dwóch rekordów w takiej strukturze istnieje
tylko jedna droga prowadząca od pierwszego do drugiego
rekordu przez kolejne wskazania.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
16
każdy rekord w strukturze drzewiastej nazywany jest
węzłem lub wierzchołkiem drzewa,
rekord, w którym wszystkie pola wskaźnikowe
przeznaczone do wskazywania rekordów potomnych
zawierają adres pusty (NIL) nazywamy liściem drzewa,
oba wskazania razem, które występują
pomiędzy dwoma rekordami będącymi
dla siebie bezpośrednim rodzicem
i potomkiem nazywamy gałęzią drzewa:
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
17
dla danego rekordu liczba wskazań (adresów), które
należy odczytać poczynając od wskaźnika na korzeń drzewa
np. w celu poznania zawartości jego pola kluczowego,
określa poziom na jakim ten rekord znajduje się w drzewie,
rzędem drzewa nazywamy największą liczbę
wierzchołków potomnych jaką można znaleźć wśród
wszystkich jego wierzchołków (jest to zatem największa
liczba pól w tym samym rekordzie, które wskazując na
rekordy potomne nie zawierają pustego adresu),
drzewo, w którym żaden wierzchołek nie ma więcej niż 2
wierzchołki potomne nazywamy drzewem binarnym,
drzewo, w którym wszystkie wierzchołki poza liśćmi mają
jednakową liczbę potomków i wszystkie liście są na tym
samym poziomie nazywamy drzewem pełnym.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
18
Poziom 1
Poziom 2
Poziom 3
Poziom 4
korzeń
węzły
liść
potomek
gałąź
rodzic
Drzewo rzędu 3
liść
4
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
19
prawy
potomek
lewy
potomek
lewe
poddrzewo
prawe
poddrzewo
Drzewo binarne
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
20
Binarne drzewo pełne o 4 poziomach
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
21
Algorytm sortowania drzewiastego:
Etap 1. Zapisanie elementów z nieuporządkowanej listy
wejściowej w wierzchołkach binarnego drzewa poszukiwań T
(ang. Binary Search Tree)
Etap 2. Obejście drzewa T (odwiedzenie wszystkich
wierzchołków) według zasady lewostronnego przeglądu w głąb i
wypisywanie elementów listy przy drugich odwiedzinach
wierzchołka.
Drzewo BST to takie drzewo binarne, w którym dla dowolnie
wskazanego wierzchołka spełnione są dwa warunki:
ż
aden z elementów zapisanych w wierzchołkach jego lewego
poddrzewa nie jest większy od elementu zapisanego w tym
wierzchołku i żaden z elementów zapisanych w wierzchołkach
jego prawego poddrzewa nie jest mniejszy od tego elementu .
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
22
Przykładowa realizacja algorytmu sortowania drzewiastego
128 76 106
100 46 354
402
112 28
987
35
396
kierunek odczytywania
Etap 1:
128
76
106
402
100
46
354
987
112
28
396
35
Drzewo BST
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
23
128
76
106
100
46
354
402
112
28
987
35
396
początek przeglądu
koniec przeglądu
Etap 2:
28
35
46
76 100 106 112 128 354 396 402 987
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2011 r.
24
Procedura obejdź(T)
1. jeśli drzewo T jest puste, to wróć do poziomu wywołania,
2. w przeciwnym przypadku wykonaj co następuje:
2.1. wywołaj obejdź (L
T
),
2.2. wypisz element umieszczony w korzeniu drzewa T,
2.3. wywołaj obejdź (P
T
),
3. wróć do poziomu wywołania.
drzewo T
lewe
poddrzewo
L
T
prawe
poddrzewo
P
T
Procedura
rekurencyjna
realizująca
2. etap algorytmu
sortowania
drzewiastego:
Reguła wypisywania
IN-ORDER