1

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 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 2006 r.

19

prawy

potomek

lewy

potomek

lewe

poddrzewo

prawe

poddrzewo

Drzewo binarne

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r.

20

Binarne drzewo pełne o 4 poziomach

Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 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 2006 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 2006 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 2006 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