Algorytmy i struktury
Algorytmy i struktury
danych
danych
Uniwersytet J.Kochanowskiego w Kielcach
Uniwersytet J.Kochanowskiego w Kielcach
Dr Zbigniew Bem
Dr Zbigniew Bem
Podstawowe struktury danych
Podstawowe struktury danych
" Lista
" Lista
" Zbiór
" Zbiór
" Graf
" Graf
" Drzewo
" Drzewo
Lista
Lista
Lista to skończony ciąg ( sekwencja ) elementów:
Lista to skończony ciąg ( sekwencja ) elementów:
q = [x1, x2, ..., xn], inaczej: uporządkowany zbiór
q = [x1, x2, ..., xn], inaczej: uporządkowany zbiór
składników, niekoniecznie tego samego typu. Elementy
składników, niekoniecznie tego samego typu. Elementy
listy x1, i xn nazywają się końcami listy (odpowiednio -
listy x1, i xn nazywają się końcami listy (odpowiednio -
lewym i prawym), mówimy również, że x1 to pierwszy
lewym i prawym), mówimy również, że x1 to pierwszy
element listy, xn  ostatni element listy. Wielkość
element listy, xn  ostatni element listy. Wielkość
| q | = n nazywamy długością (lub rozmiarem) listy.
| q | = n nazywamy długością (lub rozmiarem) listy.
Szczegó lnym przypadkiem listy jest lista pusta: q =[ ].
Szczególnym przypadkiem listy jest lista pusta: q =[ ].
Ważną własnością listy jest liniowe uporządkowanie jej
Ważną własnością listy jest liniowe uporządkowanie jej
elementów, zgodne z ich pozycjami w liście. Mówimy
elementów, zgodne z ich pozycjami w liście. Mówimy
także, że element xi jest na pozycji i.
także, że element xi jest na pozycji i.
� Zbigniew Bem
Podstawowe operacje na listach
Podstawowe operacje na listach
Wez
my dwie listy: q = [x1, x2, ..., xn ] i r = [y1, y2, ..., ym],
Wez
my dwie listy: q = [x1, x2, ..., xn ] i r = [y1, y2, ..., ym],
i niech 0 < i < j < n:
i niech 0 < i < j < n:
Podstawowymi abstrakcyjnymi operacjami na listach są:
Podstawowymi abstrakcyjnymi operacjami na listach są:
" dostęp do elementu listy: q[i] = xi ;
" dostęp do elementu listy: q[i] = xi ;
" podlista : q[ i..j] = [xi, xi+1 , ..., xj] ;
" podlista : q[i..j] = [xi, xi+1 , ..., xj] ;
" złoż enie (konkatencja): q&r = [x1, ..., x n , y1, y2, ..., ym].
" złożenie (konkatencja): q&r = [x1, ..., xn, y1, y2, ..., ym].
Za pomocą tych trzech podstawowych operacji można
Za pomocą tych trzech podstawowych operacji można
definiować inne operacje na listach, na przykład
definiować inne operacje na listach, na przykład
wstawianie elementu u za element xi na liście q
wstawianie elementu u za element xi na liście q
realizuje: q[1& i]&[u]&q[i + 1& | q |] .
realizuje: q[1& i]&[u]&q[i + 1& | q |] .
Aby zbudować ADT reprezentujący listę, musimy określić
Aby zbudować ADT reprezentujący listę, musimy określić
zestaw podstawowych operacji wykonywanych na
zestaw podstawowych operacji wykonywanych na
listach.
listach.
" Operacje wykonywane na końcach listy:
" Operacje wykonywane na końcach listy:
(a) front(q) = q[1] (pobieranie lewego końca listy);
(a) front(q) = q[1] (pobieranie lewego końca listy);
(b) push(q, x) = [x]&q (wstawienie elementu x na lewy
(b) push(q, x) = [x]&q (wstawienie elementu x na lewy
koniec listy);
koniec listy);
(c) pop(q) = q[2.. |q| ] (usunięcie bieżącego lewego
(c) pop(q) = q[2.. |q| ] (usunięcie bieżącego lewego
końca listy);
końca listy);
(d) rear(q) = q[| q |] (pobieranie prawego końca listy);
(d) rear(q) = q[| q |] (pobieranie prawego końca listy);
(e) inject(q, x) = q&[x] (wstawienie elementu x na
(e) inject(q, x) = q&[x] (wstawienie elementu x na
prawy koniec listy);
prawy koniec listy);
(f) eject(q) = q[1.. |q| -1] (usunięcie bieżącego
(f) eject(q) = q[1.. |q| -1] (usunięcie bieżącego
prawego końca listy).
prawego końca listy).
Listę, na której można wykonać wszystkich sześć
Listę, na której można wykonać wszystkich sześć
operacji, nazywa się kolejką podwójną. W
operacji, nazywa się kolejką podwójną. W
szczególnych przypadkach, tzn. kiedy uwzględnia
szczególnych przypadkach, tzn. kiedy uwzględnia
się tylko operacje front, push i pop, nazywa się ją
się tylko operacje front, push i pop, nazywa się ją
stosem, a kiedy uwzględnia się tylko operacje
stosem, a kiedy uwzględnia się tylko operacje
front, pop i inject kolejką.
front, pop i inject kolejką.
Stos jest abstrakcyjnym typem danych do którego
Stos jest abstrakcyjnym typem danych do którego
elementy mogą być wstawiane i z którego mogą
elementy mogą być wstawiane i z którego mogą
być pobierane wyłącznie na jednym końcu
.
być pobierane wyłącznie na jednym końcu
.
Kolejka jest typem danych do którego elementy
Kolejka jest typem danych do którego elementy
dołączane są na jednym końcu a pobierane są z
dołączane są na jednym końcu a pobierane są z
drugiego końca
drugiego końca
� Zbigniew Bem
Implementacje list
Implementacje list
Dwie podstawowe implementacje (reprezentacje)
Dwie podstawowe implementacje (reprezentacje)
listy q = [x1, x2, ..., xn ] to:
listy q = [x1, x2, ..., xn ] to:
" tablicowa: q[i] = xi gdzie 1 < i < n,
" tablicowa: q[i] = xi gdzie 1 < i < n,
" dowiązaniowa: której różne warianty są
" dowiązaniowa: której róż ne warianty są
przedstawione na rysunku 1.
przedstawione na rysunku 1.
W ramach każdej z tych implementacji istnieją
W ramach każdej z tych implementacji istnieją
operacje, które wykonywane są efektywniej niż w
operacje, które wykonywane są efektywniej niż w
pozostałych implementacjach.
pozostałych implementacjach.
� Zbigniew Bem
x1 x2 ... xn
x1 x2 ... xn Pojedyncza liniowa
Pojedyncza liniowa
x1 x2 ... xn Pojedyncza cykliczna
x1 x2 ... xn Pojedyncza cykliczna
�! Podwójna liniowa
�! �! �! Podwójna liniowa
x1 x2 . . . xn
x1 �! x2�! . . . xn

x1 �! x2 �! . . .�! xn
x1 �! x2 �! . . .�! xn Podwójna cykliczna
Podwójna cykliczna


Rysunek 1
Tablicowa implementacja listy
Tablicowa implementacja listy
W ramach implementacji tablicowej poszczególne
W ramach implementacji tablicowej poszczególne
elementy listy są po prostu kolejnymi elementami
elementy listy są po prostu kolejnymi elementami
tablicy.
tablicy.
Tablica jednowymiarowa to funkcja f: I X gdzie
Tablica jednowymiarowa to funkcja f: I X gdzie
I = {1, 2, ..., n} jest zbiorem indeksów a X
I = {1, 2, ..., n} jest zbiorem indeksów a X
ustalonym zbiorem ( typem ).
ustalonym zbiorem ( typem ).
A
atwo zrozumieć, że dołączanie nowego elementu
A
atwo zrozumieć, że dołączanie nowego elementu
na koniec listy jest wówczas sprawą bardzo prostą,
na koniec listy jest wówczas sprawą bardzo prostą,
jednakże już wstawianie elementów w środku listy
jednakże już wstawianie elementów w środku listy
czy usuwanie ich ze środka wiąże się z
czy usuwanie ich ze środka wiąże się z
koniecznością przesuwania całych grup
koniecznością przesuwania całych grup
elementów ku początkowi lub ku końcowi tablicy.
elementów ku początkowi lub ku końcowi tablicy.
Strukturą danych, która realizuje tablicową
Strukturą danych, która realizuje tablicową
implementację listy, jest rekord zawierający dwa
implementację listy, jest rekord zawierający dwa
pola. Pierwszym polem jest wspomniana tablica
pola. Pierwszym polem jest wspomniana tablica
elementów o rozmiarze wystarczającym do
elementów o rozmiarze wystarczającym do
zapamiętania najdłuższej spodziewanej listy. W
zapamiętania najdłuższej spodziewanej listy. W
drugim polu zapamiętywana jest natomiast
drugim polu zapamiętywana jest natomiast
pozycja ostatniego (last) elementu w liście.
pozycja ostatniego (last) elementu w liście.
Pozycje elementów w liście utożsamiane są z ich
Pozycje elementów w liście utożsamiane są z ich
indeksami w tablicy  element o pozycji i jest
indeksami w tablicy  element o pozycji i jest
i -tym elementem tablicy dla l d" i d" last, jak
i -tym elementem tablicy dla l d" i d" last, jak
pokazano na przykładzie 1. Wartością zwracaną
pokazano na przykładzie 1. Wartością zwracaną
przez funkcję END jest last + 1.
przez funkcję END jest last + 1.
Oto związane z tym opisem deklaracje :
Oto związane z tym opisem deklaracje :
const
const
maxlength = 100 { należy dobrać odpowiedni rozmiar,
maxlength = 100 { należy dobrać odpowiedni rozmiar,
ten jest tylko przykładowy };
ten jest tylko przykładowy };
type
type
LIST = record
LIST = record
elements: array[l..maxlength] of elmenttype;
elements: array[l..maxlength] of elmenttype;
last: integer;
last: integer;
end;
end;
positnon = integer;
positnon = integer;
function END ( var L: LIST ): position;
function END ( var L: LIST ): position;
begin
begin
return (L.last + 1)
return (L.last + 1)
end; {END}
end; {END}
Przykład 1.
Dowiązaniowa ( wskaz
nikowa )
Dowiązaniowa ( w skaz
nikowa )
implementacja listy
implementacja listy
Różne warianty implementacji
Różne warianty implementacji
dowiązaniowej list są przedstawione na
dowiązaniowej list są przedstawione na
rysunku 2 i 3
rysunku 2 i 3
Lista w implementacji wskaz
nikowej składa się z
Lista w implementacji wskaz
nikowej składa się z
komórek, z których każda zawiera dwa
komórek, z których każda zawiera dwa
komponenty: element listy oraz wskaz
nik do
komponenty: element listy oraz wskaz
nik do
następnej komórki. Komórka zawierająca element
następnej komórki. Komórka zawierająca element
ai, zawiera jednocześnie wskaz
nik do komórki ai+1
ai, zawiera jednocześnie wskaz
nik do komórki ai+1
dla i = 1,2, ..., n-1, gdzie n jest długością listy.
dla i = 1,2, ..., n-1, gdzie n jest długością listy.
Komórka zawierająca element an zawiera wskaz
nik
Komórka zawierająca element an zawiera wskaz
nik
pusty (nil). Potrzebna jest takż e specjalna
pusty (nil). Potrzebna jest także specjalna
komórka (zwana komórką nagłówkową  header),
komórka (zwana komórką nagłówkową  header),
której wskaz
nik wskazuje na pierwszy element listy
której wskaz
nik wskazuje na pierwszy element listy
(a1); komórka nagłówkowa nie zawiera żadnego
(a1); komórka nagłówkowa nie zawiera żadnego
elementu listy. Jeżeli lista jest pusta, komórka
elementu listy. Jeżeli lista jest pusta, komórka
nagłówkowa jest jej jedyną komórką i zawiera
nagłówkowa jest jej jedyną komórką i zawiera
pusty wskaz
nik nil co daje gwarancję, że struktura
pusty wskaz
nik nil co daje gwarancję, że struktura
dowiązaniowa nigdy nie będzie pusta.
dowiązaniowa nigdy nie będzie pusta.
Wskaz
nikowa implementacja listy
Wskaz
nikowa implementacja listy
ai
Elementy listy oznaczamy lub
Elementy listy oznaczamy lub
Wskaz
nik
Nil
Pojedyncza liniowa (jednokierunkowa)
Pojedyncza liniowa (jednokierunkowa)
Początek
. . . . .
Nil
Nil
Koniec
Podwójna liniowa (dwukierunkowa)
Podwójna liniowa (dwukierunkowa)
Rysunek 2
Wskaz
nikowa implementacja listy
Wskaz
nikowa implementacja listy
Pojedyncza cykliczna (jednokierunkowa)
Pojedyncza cykliczna (jednokierunkowa)
Rysunek 3
" W implementacji list  jednokierunkowo
" W implementacji list  jednokierunkowo
połączone komórki  nazywa się też dla wygody
połą czone komórki  nazywa się też dla wygody
listą jednokierunkową. Jest ona oparta na
listą jednokierunkową. Jest ona oparta na
wskaz
nikach umożliwiających poruszanie się  w
wskaz
nikach umożliwiających poruszanie się  w
przód" po elementach listy.
przód" po elementach listy.
" Implementacja ta, w przeciwieństwie do
" Implementacja ta, w przeciwieństwie do
implementacji tablicowej, nie wymaga ani
implementacji tablicowej, nie wymaga ani
ciągłego obszaru pamięci dla elementów, ani też
ciągłego obszaru pamięci dla elementów, ani też
czasochłonnego przesuwania elementów w celu
czasochłonnego przesuwania elementów w celu
zrobienia miejsca dla nowych elementów lub
zrobienia miejsca dla nowych elementów lub
zapełnienia dziur po elementach usuniętych. Nie
zapełnienia dziur po elementach usuniętych. Nie
jest konieczna również znajomość a priori
jest konieczna również znajomość a priori
największej możliwej długości listy. Ceną
największej możliwej długości listy. Ceną
płaconą za te udogodnienia jest dodatkowa pamięć
płaconą za te udogodnienia jest dodatkowa pami ęć
potrzebna na wskaz
niki.
potrzebna na wskaz
niki.
� Zbigniew Bem
" Należy tym miejscu zwrócić uwagę na odmienne
" Należy tym miejscu zwrócić uwagę na odmienne
niż w implementacji tablicowej znaczenie pozycji.
niż w implementacji tablicowej znaczenie pozycji.
Załóżmy, że mamy trójelementową listę a, b, c i
Załóżmy, że mamy trójelementową listę a, b, c i
zmienną p reprezentującą aktualnie drugą pozycję
zmienną p reprezentującą aktualnie drugą pozycję
listy, czyli element b. Zgodnie z przyjętą
listy, czyli element b. Zgodnie z przyjętą
konwencją zmienna ta nie wskazuje wcale na
konwencją zmienna ta nie wskazuje wcale na
komórkę zawierającą element b, lecz na komórkę
komórkę zawierającą element b, lecz na komórkę
z elementem c.
z elementem c.
W implementacjach pojedynczej liniowej i
W implementacjach pojedynczej liniowej i
podwójnej liniowej dowiązanie prowadzące do
podwójnej liniowej dowiązanie prowadzące do
listy wskazuje na pierwszy element na liście, a w
listy wskazuje na pierwszy element na liście, a w
implementacji pojedynczej cyklicznej i podwójnej
implementacji pojedynczej cyklicznej i podwójnej
cyklicznej - na ostatni.
cyklicznej - na ostatni.
Zadanie !
Napisać program w j. Pascal realizujący listę
jednokierunkową w implementacji tablicowej.
Napisać program w j. C realizujący listę
jednokierunkową w implementacji wskaz
nikowej.
Porównanie implementacji
Porównanie implementacji
" Odpowiedz
na to pytanie, która z przedstawionych
" Odpowiedz
na to pytanie, która z przedstawionych
implementacji listy  tablicowa czy wskaz
nikowa
implementacji listy  tablicowa czy wskaz
nikowa
 lepsza jest w konkretnym zastosowaniu? zależy
 lepsza jest w konkretnym zastosowaniu? zależy
od tego, jakie operacje wykonywać chcemy na
od tego, jakie operacje wykonywać chcemy na
danej liście, ewentualnie  jakie operacje będą na
danej liście, ewentualnie  jakie operacje będą na
niej wykonywane najczęściej.
niej wykonywane najczęściej.
" Inne ważne kryterium wyboru konkretnej
" Inne ważne kryterium wyboru konkretnej
implementacji to związane z nią wymagania
implementacji to związane z nią wymagania
pamięciowe.
pamięciowe.
� Zbigniew Bem
Kursorowa implementacja listy
Kursorowa implementacja listy
jednokierunkowej
jednokierunkowej
" Niektóre języki, jak Fortran czy Algol, w ogóle
" Niektóre języki, jak Fortran czy Algol, w ogóle
nie obsługują wskaz
ników. W tej sytuacji
nie obsługują wskaz
ników. W tej sytuacji
wskaz
niki mogą by ć jedynie symulowane przez
wskaz
niki mogą być jedynie symulowane przez
kursory, czyli liczby całkowite wskazujące
kursory, czyli liczby całkowite wskazujące
pozycje w tablicach. Dla wszystkich list
pozycje w tablicach. Dla wszystkich list
zawierających elementy tego samego typu
zawierających elementy tego samego typu
bazowego tworzymy wówczas jedną tablicę,
bazowego tworzymy wówczas jedną tablicę,
której każda komórka zawiera dwa komponenty:
której każda komórka zawiera dwa komponenty:
element listy oraz kursor następnego elementu.
element listy oraz kursor następnego elementu.
Przykładem może być
Przykładem może być
var
var
list:array[1..maxlength] of record
list:array[1..maxlength] of record
element: elementtype;
element: elementtype;
next: integer
next: integer
end
end
� Zbigniew Bem
Listy dwukierunkowe
Listy dwukierunkowe
" Wiele algorytmów wymaga efektywnego
" Wiele algorytmów wymaga efektywnego
przeglądania listy w obydwu kierunkach, jak
przeglądania listy w obydwu kierunkach, jak
również szybkiego docierania do następnego i
również szybkiego docierania do następnego i
poprzedniego, w stosunku do wskazanego,
poprzedniego, w stosunku do wskazanego,
elementu. Jak mogliśmy się przekonać, lista
elementu. Jak mogliśmy się przekonać, lista
jednokierunkowa nie jest w stanie zapewnić takiej
jednokierunkowa nie jest w stanie zapewnić takiej
efektywności, konieczne staje się więc
efektywności, konieczne staje się więc
wyposażenie każdej z komórek w dwa wskaz
niki
wyposażenie każdej z komórek w dwa wskaz
niki
do komórki (odpowiednio) poprzedniej i
do komórki (odpowiednio) poprzedniej i
następnej, jak to schematycznie pokazano na
następnej, jak to schematycznie pokazano na
rysunku 4.
rysunku 4.
Wskaz
nikowa lista dwukierunkowa
Wskaz
nikowa lista dwukierunkowa
Początek
. . . . .
Nil
Nil
Koniec
Podwójna liniowa (dwukierunkowa)
Podwójna liniowa (dwukierunkowa)
Stos
Stos
" Stos stanowi specjalną postać listy, w której
" Stos stanowi specjalną postać listy, w której
operacje wstawiania i usuwania elementu mają
operacje wstawiania i usuwania elementu mają
miejsce tylko na jednym końcu, zwanym
miejsce tylko na jednym końcu, zwanym
wierzchołkiem lub szczytem. Stos nazywany bywa
wierzchołkiem lub szczytem. Stos nazywany bywa
także  listą popychaną" (pushdown list) i
także  listą popychaną" (pushdown list) i
oznaczany skrótem LIFO, od angielskiego last-in-
oznaczany skrótem LIFO, od angielskiego last-in-
first-out, czyli  ostatni wchodzi, pierwszy
first-out, czyli  ostatni wchodzi, pierwszy
wychodzi". Intuicyjnym modelem stosu może być
wychodzi". Intuicyjnym modelem stosu może być
np. talia kart, kolumna książek czy  wieżyczka"
np. talia kart, kolumna książek czy  wieżyczka"
naczyń kuchennych. We wszystkich tych
naczyń kuchennych. We wszystkich tych
przypadkach można wziąć tylko jeden element ze
przypadkach można wziąć tylko jeden element ze
szczytu lub położyć jeden na szczycie.
szczytu lub położyć jeden na szczycie.
Podstawowe działania (push, pop+front) na stosie
Podstawowe działania (push, pop+front) na stosie
w implementacji wskaz
nikowej, elementy stosu są
w implementacji wskaz
nikowej, elementy stosu są
słowa (string):
słowa (string):
type
type
TWskaznik = ^TElement;
TWskaznik = ^TElement;
TElement = record
TElement = record
slowo : String;
slowo : String;
nast : TWskaznik;
nast : TWskaznik;
end;
end;
var
var
stos : TWskaznik;
stos : TWskaznik;
slowo : String;
slowo : String;
procedure Push (slowo: String);
procedure Push (slowo: String);
{ Procedura odkłada słowo na stosie - czyli umieszcza
{ Procedura odkłada słowo na stosie - czyli umieszcza
go na początku listy (o ile nie jest puste).}
go na początku listy (o ile nie jest puste).}
var
var
E : TWskaznik;
E : TWskaznik;
begin
begin
if slowo <> ' ' then begin
if slowo <> ' ' then begin
New (E);
New (E);
E^.slowo := slowo;
E^.slowo := slowo;
E^.nast := stos;
E^.nast := stos;
stos := E;
stos := E;
end;
end;
end;
end;
function Pop: String;
function Pop: String;
{ Funkcja ściąga ze stosu pierwsze słowo (o ile jest) i je
{ Funkcja ściąga ze stosu pierwsze słowo (o ile jest) i je
zwraca. Jeżeli stos jest pusty - zwraca łańcuch pusty.
zwraca. Jeżeli stos jest pusty - zwraca łańcuch pusty.
Realizuje operacje front i pop }
Realizuje operacje front i pop }
begin
begin
if (Stos = Nil) then Pop := ' '
if (Stos = Nil) then Pop := ' '
else begin
else begin
E := stos;
E := stos;
Pop := E^.slowo;
Pop := E^.slowo;
Stos := E^.nast;
Stos := E^.nast;
Dispose (E);
Dispose (E);
end;
end;
end;
end;
procedure WypiszStos;
procedure WypiszStos;
{ Procedura wypisuje wszystkie elementy stosu.}
{ Procedura wypisuje wszystkie elementy stosu.}
var
var
E : TWskaznik;
E : TWskaznik;
begin
begin
E := stos;
E := stos;
while E <> nil do
while E <> nil do
begin
begin
writeln (E^.slowo);
writeln (E^.slowo);
E := E^.nast;
E := E^.nast;
end;
end;
end;
end;
Kolejka
Kolejka
" Kolejka jest innym szczególnym przypadkiem
" Kolejka jest innym szczególnym przypadkiem
listy. Jej elementy dołączane są na jednym końcu,
listy. Jej elementy dołączane są na jednym końcu,
zwanym tyłem (ang. rear), a usuwane są z
zwanym tyłem (ang. rear), a usuwane są z
drugiego zwanego czołem (ang. head). Ze względu
drugiego zwanego czołem (ang. head). Ze względu
na tę właściwość kolejki oznaczane są także
na tę właściwość kolejki oznaczane są także
skrótem FIFO, od angielskiego first-in-first-out,
skrótem FIFO, od angielskiego first-in-first -out,
czyli  pierwszy wchodzi, pierwszy wychodzi" na
czyli  pierwszy wchodzi, pierwszy wychodzi" na
końcach. Podstawowe operacje kolejek są
końcach. Podstawowe operacje kolejek są
analogiczne do operacji stosowych, a oczywista
analogiczne do operacji stosowych, a oczywista
różnica związana jest ze wstawianiem i
różnica związana jest ze wstawianiem i
usuwaniem elementów na dwóch różnych
usuwaniem elementów na dwóch różnych
końcach.
końcach.
� Zbigniew Bem
Podstawowe działania (front, pop, inject) na
Podstawowe działania (front, pop, inject) na
kolejce w implementacji wskaz
nikowej,
kolejce w implementacji wskaz
nikowej,
elementami kolejki są liczby (byte):
elementami kolejki są liczby (byte):
type
type
TWskaznik = ^TElement;
TWskaznik = ^TElement;
TElement = record
TElement = record
liczba : Byte;
liczba : Byte;
nast : TWskaznik;
nast : TWskaznik;
end;
end;
var
var
kolejka : TWskaznik;
kolejka : TWskaznik;
liczba : Byte;
liczba : Byte;
procedure Ustaw (liczba: Byte);
procedure Ustaw (liczba: Byte);
{ Procedura ustawia element w kolejce, realizuje operacje inject.}
{ Procedura ustawia element w kolejce, realizuje operacje inject.}
var
var
E,pop, nast : TWskaznik;
E,pop, nast : TWskaznik;
begin
begin
New (E);
New (E);
E^.liczba := liczba;
E^.liczba := liczba;
if kolejka = nil then begin
if kolejka = nil then begin
E^.nast := kolejka
E^.nast := kolejka
kolejka:=E;
kolejka:=E;
end
end
else begin
else begin
pop := kolejka;
pop := kolejka;
nast := kolejka^.nast;
nast := kolejka^.nast;
while (nast <> nil) do
while (nast <> nil) do
begin
begin
pop := nast;
pop := nast;
nast := nast^.nast;
nast := nast^.nast;
end;
end;
E^.nast := nast;
E^.nast := nast;
pop^.nast := E;
pop^.nast := E;
end;
end;
end;
end;
function Obsluz: String;
function Obsluz: String;
{ Funkcja zwraca pierwszy element z kolejki i jednocześnie
{ Funkcja zwraca pierwszy element z kolejki i jednocześnie
go z niej usuwa. Realizuje operacje front i pop }
go z niej usuwa. Realizuje operacje front i pop }
var
var
E : TWskaznik;
E : TWskaznik;
begin
begin
if (kolejka = Nil) then Obsluz := 0
if (kolejka = Nil) then Obsluz := 0
else begin
else begin
E := kolejka;
E := kolejka;
Obsluz := E^.liczba;
Obsluz := E^.liczba;
kolejka := E^.nast;
kolejka := E^.nast;
end;
end;
end;
end;
procedure WypiszKolejke;
procedure WypiszKolejke;
{ Procedura wypisuje wszystkie elementy kolejki.}
{ Procedura wypisuje wszystkie elementy kolejki.}
var
var
E : TWskaznik;
E : TWskaznik;
begin
begin
E := kolejka;
E := kolejka;
while E <> nil do
while E <> nil do
begin
begin
write (E^.liczba, ' ');
write (E^.liczba, ' ');
E := E^.nast;
E := E^.nast;
end;
end;
end;
end;
Zbiór
Zbiór
" W projektowaniu algorytmów zbiory są podstawą
" W projektowaniu algorytmów zbiory są podstawą
wielu abstrakcyjnych typów danych.
wielu abstrakcyjnych typów danych.
" Zbiór ( ang. Set ) jest kolekcję rozróżnialnych
" Zbiór ( ang. Set ) jest kolekcję rozróżnialnych
elementów ( wszystkie elementy zbioru są różne ).
elementów ( wszystkie elementy zbioru są różne ).
" Element zbioru sam jest albo zbiorem, albo
" Element zbioru sam jest albo zbiorem, albo
elementem pierwotnym zwanym atomem. Gdy
elementem pierwotnym zwanym atomem. Gdy
zbiór używany jest jako narzędzie do projektowana
zbiór używany jest jako narzędzie do projektowana
algorytmów ich atomy z reguły są liczbami,
algorytmów ich atomy z reguły są liczbami,
znakami lub łańcuchami znaków, i w danym
znakami lub łańcuchami znaków, i w danym
zbiorze są zazwyczaj tego samego typu.
zbiorze są zazwyczaj tego samego typu.
" Zawsze będziemy zakładać, że rozważany zbiór
" Zawsze będziemy zakładać, że rozważany zbiór
jest skończony.
jest skończony.
" W przeciwieństwie do elementów listy, elementy
" W przeciwieństwie do elementów listy, elementy
w zbiorze S = {x1, x2, ..., xn} nie są podane w
w zbiorze S = {x1, x2, ..., xn} nie są podane w
żadnym ustalonym porządku.
żadnym ustalonym porządku.
" Liczbę n elementów w zbiorze S oznaczamy przez
" Liczbę n elementów w zbiorze S oznaczamy przez
�#S�# i nazywamy rozmiarem zbioru S.
�#S�# i nazywamy rozmiarem zbioru S.
Podstawowymi operacjami na zbiorach są:
Podstawowymi operacjami na zbiorach są:
(a) insert(x, S):: S := S *" {x} (wstawienie
(a) insert(x, S):: S := S *" {x} (wstawienie
elementu x do zbioru S);
elementu x do zbioru S);
(b) delete(x, S):: S := S - {x} (usunięcie elementu x
(b) delete(x, S):: S := S - {x} (usunięcie elementu x
ze zbioru S);
ze zbioru S);
treue, jeśli x"S
treue, jeśli x"S
(c ) member(x,S):: wynikiem jest
(c ) member(x,S):: wynikiem jest
false, jeśli x "S
false, jeśli x "S
(d) min(S):: zwrócenie najmniejszego elementu w
(d) min(S):: zwrócenie najmniejszego elementu w
zbiorze S z uwzględnieniem pewnego ustalonego
zbiorze S z uwzględnieniem pewnego ustalonego
liniowego porządku d" ;
liniowego porządku d" ;
(e) deletemin(S):: S := S - {min(S)};
(e) deletemin(S):: S := S - {min(S)};
(f) union(S1, S2):: obliczenie S1 *" S2 (przy założeniu,
(f) union(S1, S2):: obliczenie S1 *" S2 (przy założeniu,
że zbiory S1 i S2 są rozłączne).
że zbiory S1 i S2 są rozłączne).
Implementacje
Implementacje
To, jaka implementacja abstrakcyjnego typu
To, jaka implementacja abstrakcyjnego typu
danych SET jest najlepsza, zależy od dwóch
danych SET jest najlepsza, zależy od dwóch
czynników: rozmiaru zbioru oraz zestawu
czynników: rozmiaru zbioru oraz zestawu
operacji, które na tym zbiorze mają być
operacji, które na tym zbiorze mają być
wykonywane.
wykonywane.
Podstawowe implementacje zbioru
Podstawowe implementacje zbioru
S = {x1
, x2, ..., xn}.
S = {x1, x2 , ..., xn }.
" Wektor charakterystyczny ( bitowy )
" Wektor charakterystyczny ( bitowy )
true, gdy x"S
ż#
C[x] =
�#
false, gdy x "S
�#
" Jeśli wszystkie używane zbiory będą podzbiorami
" Jeśli wszystkie używane zbiory będą podzbiorami
pewnego uniwersum (  uniwersalnego nadzbioru )
pewnego uniwersum (  uniwersalnego nadzbioru )
niewielkich rozmiarów, to wygodnie reprezentować
niewielkich rozmiarów, to wygodnie reprezentować
te zbiory w postaci wektorów bitów, które w języku
te zbiory w postaci wektorów bitów, które w języku
Pascal mogą być wyrażone w postaci tablic
Pascal mogą być wyrażone w postaci tablic
boolowskich.
boolowskich.
" W języku Pascal deklaracja abstrakcyjnego
" W języku Pascal deklaracja abstrakcyjnego
typu SET w tej reprezentacji ma postać:
typu SET w tej reprezentacji ma postać:
const
const
N = ;
wartość odpowiednia w danym zastosowaniu
N = < >;
type
type
SET = array[1..N] of boolean
SET = array[1..N] of boolean
" Implementacje listowe
" Implementacje listowe
Często przyjmuje się, że elementy zbioru są
Często przyjmuje się, że elementy zbioru są
uporządkowane przez relację porządku <
uporządkowane przez relację porządku <
spełniającą następujące warunki:
spełniającą następujące warunki:
" Dla dwóch elementów a i b należących do
" Dla dwóch elementów a i b należących do
zbioru S zachodzi tylko jedna z trzech
zbioru S zachodzi tylko jedna z trzech
zależności: a < b, a = b, b < a.
zależności: a < b, a = b, b < a.
" Dla dowolnych trzech elementów a, b, c,
" Dla dowolnych trzech elementów a, b, c,
jeżeli a < b i b < c, to a < c.
jeżeli a < b i b < c, to a < c.
( przechodniość )
( przechodniość )
" Jest oczywiste, że ustawiając elementy zbioru S w
" Jest oczywiste, że ustawiając elementy zbioru S w
pewnym porządku, otrzymujemy listę. Wszystkie
pewnym porządku, otrzymujemy listę. Wszystkie
implementacje listy mogą być użyte do
implementacje listy mogą być użyte do
reprezentowania zbioru.
reprezentowania zbioru.
" Lista reprezentująca ten zbiór może być wówczas
" Lista reprezentująca ten zbiór może być wówczas
listą posortowaną.
listą posortowaną.
Słowniki
Słowniki
W wielu zastosowaniach zbiorów często wystarczą
W wielu zastosowaniach zbiorów często wystarczą
jedynie efektywne (bo często wykonywane)
jedynie efektywne (bo często wykonywane)
operacje w pojedynczym zbiorze: wstawianie i
operacje w pojedynczym zbiorze: wstawianie i
usuwanie elementów, jak również sprawdzanie, czy
usuwanie elementów, jak również sprawdzanie, czy
dany element należy do tego zbioru. Abstrakcyjny
dany element należy do tego zbioru. Abstrakcyjny
typ danych, oparty na matematycznym modelu
typ danych, oparty na matematycznym modelu
zbioru i wyposażony w operacje insert, delete i
zbioru i wyposażony w operacje insert, delete i
member, nazywamy słownikiem (ang. dictionary).
member, nazywamy słownikiem (ang. dictionary).
Do wymienionych operacji często dołącza się
Do wymienionych operacji często dołącza się
operację przypisującą parametrowi zbiór pusty,
operację przypisującą parametrowi zbiór pusty,
niezbędną do zainicjowania struktury danych
niezbędną do zainicjowania struktury danych
spełniającej rolę słownika.
spełniającej rolę słownika.
� Zbigniew Bem
" Ważnym przykładem zastosowań słownika
" Ważnym przykładem zastosowań słownika
są bazy danych, tablice identyfikatorów w
są bazy danych, tablice identyfikatorów w
kompilatorach itp..
kompilatorach itp..
Graf
Graf
W wielu dyscyplinach wiedzy spotykamy się z potrzebą
W wielu dyscyplinach wiedzy spotykamy się z potrzebą
reprezentowania arbitralnych powiązań między
reprezentowania arbitralnych powiązań między
obiektami danych. Naturalnym modelem tych powiązań
obiektami danych. Naturalnym modelem tych powiązań
są grafy.
są grafy.
Graf to system, który zapisujemy jako G = (V, E), gdzie
Graf to system, który zapisujemy jako G = (V, E), gdzie
V oznacza zbiór skończony, którego elementy są
V oznacza zbiór skończony, którego elementy są
nazywane wierzchołkami (gdy chcemy podkreślić, że
nazywane wierzchołkami (gdy chcemy podkreślić, że
graf jest strukturą danych, używać też będziemy nazwy
graf jest strukturą danych, używać też będziemy nazwy
węzły), a E - zbiór krawędzi, czyli par wierzchołków ze
węzły), a E - zbiór krawędzi, czyli par wierzchołków ze
zbioru V.
zbioru V.
Rozróżniamy przypadki kiedy kolejność wierzchołków
Rozróżniamy przypadki kiedy kolejność wierzchołków
połączonych jest istotna lub nieistotna.
połączonych jest istotna lub nieistotna.
� Zbigniew Bem
Graf skierowany
Graf skierowany
Jeśli E jest podzbiorem zbioru par
Jeśli E jest podzbiorem zbioru par
uporządkowanych {(x, y): x, y " V '" x `" y}
uporządkowanych {(x, y): x, y " V '" x `" y}
to wtedy graf nazywa się skierowanym
to wtedy graf nazywa się skierowanym
(zorientowany), wierzchołek x nazywany
(zorientowany), wierzchołek x nazywany
jest wierzchołkiem początkowym a
jest wierzchołkiem początkowym a
wierzchołek y nazywany jest wierzchołkiem
wierzchołek y nazywany jest wierzchołkiem
końcowym. Krawędzie (x, y) są oznaczane
końcowym. Krawędzie (x, y) są oznaczane
strzałkami łączącymi wierzchołki.
strzałkami łączącymi wierzchołki.
x y
x y
Strzałka reprezentująca krawędz
skierowana
Strzałka reprezentująca krawędz
skierowana
jest od wierzchołka początkowego do
jest od wierzchołka początkowego do
wierzchołka końcowego. Mówimy także, że
wierzchołka końcowego. Mówimy także, że
krawędz
(x, y) prowadzi od wierzchołka x
krawędz
(x, y) prowadzi od wierzchołka x
do wierzchołka y albo że wierzchołek x jest
do wierzchołka y albo że wierzchołek x jest
sąsiadem dla wierzchołka y.
sąsiadem dla wierzchołka y.
1 2
3 4
Wierzchołki grafu skierowanego używane bywają
Wierzchołki grafu skierowanego używane bywają
najczęściej do przedstawiania obiektów, zaś
najczęściej do przedstawiania obiektów, zaś
krawędzie łączące te wierzchołki  do
krawędzie łączące te wierzchołki  do
reprezentowania relacji pomiędzy tymi obiektami.
reprezentowania relacji pomiędzy tymi obiektami.
Przykładowo:
Przykładowo:
" wierzchołki są miastami, a krawędzie reprezentują
" wierzchołki są miastami, a krawędzie reprezentują
połączenia między miastami,
połączenia między miastami,
" w programie komputerowym wierzchołki
" w programie komputerowym wierzchołki
reprezentują bloki schematu, zaś krawędzie
reprezentują bloki schematu, zaś krawędzie
możliwy przepływ sterowania między tymi
możliwy przepływ sterowania między tymi
blokami.
blokami.
Graf nieskierowany
Graf nieskierowany
" Gdy E jest podzbiorem zbioru wszystkich
" Gdy E jest podzbiorem zbioru wszystkich
dwuelementowych podzbiorów zbioru V to
dwuelementowych podzbiorów zbioru V to
wtedy graf nazywa się niezorientowany, a
wtedy graf nazywa się niezorientowany, a
krawędzie są oznaczane liniami.
krawędzie są oznaczane liniami.
x y
x y
" W obu tych przypadkach krawędz
łączącą
" W obu tych przypadkach krawędz
łączącą
wierzchołki x i y oznaczamy tak samo, jako
wierzchołki x i y oznaczamy tak samo, jako
(x, y).
(x, y).
Rozmiar grafu G = (V, E) jest równy sumie
Rozmiar grafu G = (V, E) jest równy sumie
dwóch liczb: n = | V | i m = | E |.
dwóch liczb: n = | V | i m = | E |.
Dla grafu
Dla grafu
n(n -1)
niezorientowanego (co oczywiste) m < ,
niezorientowanego (co oczywiste) m < ,
2
a dla zorientowanego m d" n(n - 1).
a dla zorientowanego m d" n(n - 1).
Podstawowe implementacje
Podstawowe implementacje
grafu G = (V, E )
grafu G = (V, E )
Zakładamy, że zbiór węzłów V może być
Zakładamy, że zbiór węzłów V może być
zbiorem indeksów dla tablic.
zbiorem indeksów dla tablic.
" Listy sąsiedztwa
" Listy sąsiedztwa
Dla każdego x " V budujemy listę
Dla każdego x " V budujemy listę
(oznaczaną przez L[x]) wierzchołków y
(oznaczaną przez L[x]) wierzchołków y
będących sąsiadami x (tj. (x, y) " E).
będących sąsiadami x (tj. (x, y) " E).
W tej implementacji jest potrzebna pamięć
W tej implementacji jest potrzebna pamięć
O(n + m).
O(n + m).
" Macierz sąsiedztwa
" Macierz sąsiedztwa
1 gdy ( x, y ) " E
ż#
A[ x, y ] =
�#
0 gdy ( x, y ) " E
�#
W tej implementacji jest potrzebna pamięć
W tej implementacji jest potrzebna pamięć
O(n2).
O(n2).
Przykład: Algorytm przechodzenia
Przykład: Algorytm przechodzenia
grafu
grafu
" Niech G = (V, E), | V | = n i | E | = m, p " V.
" Niech G = (V, E), | V | = n i | E | = m, p " V.
Wychodząc od wierzchołka p, należy odwiedzić
Wychodząc od wierzchołka p, nale ży odwiedzić
każdy wierzchołek i każdą krawędz
, które są
każdy wierzchołek i każdą krawędz
, które są
osiągalne z p.
osiągalne z p.
Dozwolonym ruchem jest przejście krawędzią grafu
Dozwolonym ruchem jest przejście krawędzią grafu
wychodzącą z odwiedzonego już wierzchołka.
wychodzącą z odwiedzonego już wierzchołka.
" W jednym kroku będziemy odwiedzać jeden z
" W jednym kroku będziemy odwiedzać jeden z
wierzchołków oraz jedną z krawędzi grafu i
wierzchołków oraz jedną z krawędzi grafu i
zaznaczać je jako odwiedzone. Na początku
zaznaczać je jako odwiedzone. Na początku
wszystkie wierzchołki i wszystkie krawędzie są
wszystkie wierzchołki i wszystkie krawędzie są
zaznaczone jako nie odwiedzone.
zaznaczone jako nie odwiedzone.
1. Odwiedz
wierzchołek p i zaznacz go jako
1. Odwiedz
wierzchołek p i zaznacz go jako
odwiedzony.
odwiedzony.
2. Dopóki z jednego z odwiedzonych wierzchołków
2. Dopóki z jednego z odwiedzonych wierzchołków
wychodzi nie odwiedzona jeszcze krawędz
,
wychodzi nie odwiedzona jeszcze krawędz
,
wykonuj podane czynności:
wykonuj podane czynności:
a) wybierz odwiedzony wierzchołek, powiedzmy
a) wybierz odwiedzony wierzchołek, powiedzmy
v, z którego wychodzi nie odwiedzona krawędz
;
v, z którego wychodzi nie odwiedzona krawędz
;
b) wybierz nie odwiedzoną krawędz
, powiedzmy
b) wybierz nie odwiedzoną krawędz
, powiedzmy
(v, w), wychodzącą z wierzchołka v;
(v, w), wychodzącą z wierzchołka v;
c) zaznacz krawędz
(v, w) jako odwiedzoną;
c) zaznacz krawędz
(v, w) jako odwiedzoną;
d) jeśli wierzchołek w nie został odwiedzony,
d) jeśli wierzchołek w nie został odwiedzony,
odwiedz
go i zaznacz jako odwiedzony.
odwiedz
go i zaznacz jako odwiedzony.
" Stosując indukcję względem odległości danego
" Stosując indukcję względem odległości danego
wierzchołka od wierzchołka początkowego p,
wierzchołka od wierzchołka początkowego p,
możemy udowodnić, że w każdym algorytmie
możemy udowodnić, że w każdym algorytmie
stosującym się do powyższego schematu musi
stosującym się do powyższego schematu musi
nastąpić odwiedzenie jeden raz każdego
nastąpić odwiedzenie jeden raz każdego
wierzchołka i każdej krawędzi grafu G osiągalnej
wierzchołka i każdej krawędzi grafu G osiągalnej
z p.
z p.
" Nie biorąc pod uwagę samej procedury
" Nie biorąc pod uwagę samej procedury
odwiedzania wierzchołków i krawędzi, złożoność
odwiedzania wierzchołków i krawędzi, złożoność
każdego takiego algorytmu jest proporcjonalna do
każdego takiego algorytmu jest proporcjonalna do
łącznej liczby wierzchołków i krawędzi (a więc
łącznej liczby wierzchołków i krawędzi (a więc
jest liniowa względem rozmiaru grafu).
jest liniowa względem rozmiaru grafu).
" Powyższy opis stanowi schemat pewnej klasy
" Powyższy opis stanowi schemat pewnej klasy
algorytmów. Aby otrzymać konkretny algorytm,
algorytmów. Aby otrzymać konkretny algorytm,
należy wykonać podane teraz kroki.
należy wykonać podane teraz kroki.
1. Przyjąć odpowiednią reprezentację grafu, na
1. Przyjąć odpowiednią reprezentację grafu, na
przykład V = {1,2, ..., n} i listy sąsiedztwa L[v]
przykład V = {1,2, ..., n} i listy sąsiedztwa L[v]
dla v " V.
dla v " V.
2. Określić, co to znaczy  zaznacz wierzchołek
2. Określić, co to znaczy  zaznacz wierzchołek
jako odwiedzony". Można na przykład dołączyć do
jako odwiedzony". Można na przykład dołączyć do
każdego wierzchołka v pole visited[v] i przyjąć, że
każdego wierzchołka v pole visited[v] i przyjąć, że
false oznacza  wierzchołek nie odwiedzony", a true
false oznacza  wierzchołek nie odwiedzony", a true
 wierzchołek odwiedzony".
 wierzcho łek odwiedzony".
3. Określić sposób wyboru odwiedzanego
3. Określić sposób wyboru odwiedzanego
wierzchoł
ka, z którego wychodzi nie odwiedzona
wierzchoł
ka, z którego wychodzi nie odwiedzona
krawędz
. Można na przykład przechowywać takie
krawędz
. Można na przykład przechowywać takie
wierzchołki w kolejce lub na stosie.
wierzchołki w kolejce lub na stosie.
4. Określić sposób odróżniania (dla danego
4. Określić sposób odróżniania (dla danego
wierzchołka) krawędzi odwiedzonych od nie
wierzchołka) krawędzi odwiedzonych od nie
odwiedzonych. Można na przykład trzymać na
odwiedzonych. Można na przykład trzymać na
liście sąsiedztwa danego wierzchołka v
liście sąsiedztwa danego wierzchołka v
wskaz
nik current[v] do pierwszej nie odwiedzonej
wskaz
nik current[v] do pierwszej nie odwiedzonej
krawędzi (current[v] = nil oznacza, że wszystkie
krawędzi (current[v] = nil oznacza, że wszystkie
krawędzie wychodzące z danego wierzchołka
krawędzie wychodzące z danego wierzchołka
zostały odwiedzone).
zostały odwiedzone).
" Przyjmując te przykładowe ustalenia, uzyskujemy
" Przyjmując te przykładowe ustalenia, uzyskujemy
uszczegółowiony schemat przechodzenia grafu
uszczegółowiony schemat przechodzenia grafu
(visit jest procedurą  odwiedzania" wierzchołka).
(visit jest procedurą  odwiedzania" wierzchołka).
Zrezygnowaliśmy z procedury odwiedzania
Zrezygnowaliśmy z procedury odwiedzania
krawędzi.
krawędzi.
for v:=l to n do
for v:=l to n do
begin
begin
visited[v] := false;
visited[v] := false;
ustaw wskaz
nik current[v] na pierwszy
ustaw wskaz
nik current[v] na pierwszy
wierzchołek na liście L[v]
wierzchołek na liście L[v]
end;
end;
visit(p);
visit(p);
visited[p] := true;
visited[p] := true;
if current[p] <> nil then
if current[p] <> nil then
begin
begin
S:=[p];
S:=[p];
while S <> [] do {S jest zbiorem wszystkich
while S <> [] do {S jest zbiorem wszystkich
odwiedzonych do tej pory wierzchołków, z których
odwiedzonych do tej pory wierzchołków, z których
wychodzą nie odwiedzone jeszcze krawędzie}
wychodzą nie odwiedzone jeszcze krawędzie}
begin
begin
wybierz wierzchołek v ze zbioru S;
wybierz wierzchołek v ze zbioru S;
niech w będzie wierzchołkiem wskazywanym
niech w będzie wierzchołkiem wskazywanym
przez current[v];
przez current[v];
przesuń wskaz
nik current[v] do następnego
przesuń wskaz
nik current[v] do następnego
wierzchołka na liście L[v];
wierzchołka na liście L[v];
if current[v] = nil then
if current[v] = nil then
S := S - [v];
S := S - [v];
if not visited[w] then
if not visited[w] then
begin
begin
visit(w) ;
visit(w) ;
visited[w] := true;
visited[w] := true;
if current[w] <> nil then
if current[w] <> nil then
S := S + [w]
S := S + [w]
end
end
end
end
end;
end;
Dwie podstawowe implementacje zbioru S to stos i
Dwie podstawowe implementacje zbioru S to stos i
kolejka.
kolejka.
Najpierw uszczegółowimy schemat przechodzenia
Najpierw uszczegółowimy schemat przechodzenia
grafu, przedstawiając S za pomocą stosu i
grafu, przedstawiając S za pomocą stosu i
interpretując operacje na S jako operacje na stosie.
interpretując operacje na S jako operacje na stosie.
" Przyjmujemy, że operacje pop i push będą
" Przyjmujemy, że operacje pop i push będą
realizowane jako procedury, a front jako
realizowane jako procedury, a front jako
funkcja.
funkcja.
" Otrzymujemy algorytm przechodzenia
" Otrzymujemy algorytm przechodzenia
grafu w głąb (metoda DFS).
grafu w głąb (metoda DFS).
procedure dfs;
procedure dfs;
begin
begin
for v := l to n do
for v := l to n do
begin
begin
visited[v]:= false;
visited[v]:= false;
ustaw wskaz
nik current[v] na pierwszy
ustaw wskaz
nik current[v] na pierwszy
wierzchołek na liście L[v]
wierzchołek na liście L[v]
end;
end;
visit(p);
visit(p);
visited[p] := true;
visited[p] := true;
if current[p] <> nil then
if current[p] <> nil then
begin
begin
S := []; push(S, p);
S := []; push(S, p);
while S <> [] do
while S <> [] do
{stos S zawiera wszystkie odwiedzone do tej pory
{stos S zawiera wszystkie odwiedzone do tej pory
wierzchołki, z których wychodzą nie odwiedzone jeszcze
wierzchołki, z których wychodzą nie odwiedzone jeszcze
krawędzie}
krawędzie}
begin
begin
v := front(S);
v := front(S);
niech w będzie wierzchołkiem
niech w będzie wierzchołkiem
wskazywanym przez current[v] ;
wskazywanym przez current[v] ;
przesuń wskaz
nik current[v] do
przesuń wskaz
nik current[v] do
następnego wierzchołka na liście L[v];
następnego wierzchołka na liście L[v];
if current[v] = nil then pop(S);
if current[v] = nil then pop(S);
if not visited[w] then
if not visited[w] then
begin
begin
visit (w);
visit (w);
visited[w] := true;
visited[w] := true;
if current[w] <> nil then push(S,w)
if current[w] <> nil then push(S,w)
end
end
end
end
end
end
end;
end;
Zapiszemy teraz schemat przechodzenia grafu,
Zapiszemy teraz schemat przechodzenia grafu,
przedstawiając S jako kolejkę i interpretując operacje
przedstawiając S jako kolejkę i interpretując operacje
na S jako operacje na kolejce.
na S jako operacje na kolejce.
Przyjmujemy tutaj, że operacje pop i inject będą
Przyjmujemy tutaj, że operacje pop i inject będą
realizowane jako procedury, a front jako funkcja.
realizowane jako procedury, a front jako funkcja.
" Otrzymujemy algorytm przechodzenia
grafu wszerz (metoda BFS).
procedure bfs;
procedure bfs;
begin
begin
for v : = l to n do
for v : = l to n do
begin
begin
visited[v] := false;
visited[v] := false;
ustaw wskaz
nik current[v] na pierwszy
ustaw wskaz
nik current[v] na pierwszy
wierzchołek na liście L[v]
wierzchołek na liście L[v]
end;
end;
visit(p); visited[p] := true;
visit(p); visited[p] := true;
if current[p] <> nil then
if current[p] <> nil then
begin
begin
S := []; inject(S, p);
S := []; inject(S, p);
while S <>[] do
while S <>[] do
{kolejka S zawiera wszystkie odwiedzone do tej pory
{kolejka S zawiera wszystkie odwiedzone do tej pory
wierzchołki, z których wychodzą nie odwiedzone jeszcze
wierzchołki, z których wychodzą nie odwiedzone jeszcze
krawędzie}
krawędzie}
begin
begin
v := front(S);
v := front(S);
niech w będzie wierzchołkiem wskazywanym
niech w będzie wierzchołkiem wskazywanym
przez current[v];
przez current[v];
przesuń wskaz
nik current[v] do następnego
przesuń wskaz
nik current[v] do następnego
wierzchołka na liście L[v];
wierzchołka na liście L[v];
if current[v] = nil then pop(S);
if current[v] = nil then pop(S);
if not visited[w] then
if not visited[w] then
begin
begin
visit (w);
visit (w);
visited[w] := true;
visited[w] := true;
if current[w] o nil then inject(S,w)
if current[w] o nil then inject(S,w)
end
end
end
end
end
end
end;
end;
Przykładowy graf
Przykładowy graf
" Jeśli p =1, L[1] = [2,3], L[2] =
" Jeśli p =1, L[1] = [2,3], L[2] =
[4,5], L[3] = [5,6], L[4] = [5],
[4,5], L[3] = [5,6], L[4] = [5],
1
1
L[5] = [1], L[6] = [], to podczas
L[5] = [1], L[6] = [], to podczas
przechodzenia grafu w głąb (
przechodzenia grafu w głąb (
algorytm dfs ) nastąpi
algorytm dfs ) nastąpi
odwiedzenie wierzchołków
odwiedzenie wierzchołków
grafu w kolejności 1, 2, 4, 5, 3,
grafu w kolejności 1, 2, 4, 5, 3,
2 3
2 3
6.
6.
" Natomiast w wyniku realizacji
" Natomiast w wyniku realizacji
algorytmu bfs ( przechodzenie
algorytmu bfs ( przechodzenie
wszerz ) odwiedzimy
wszerz ) odwiedzimy
wierzchołki w kolejności 1, 2,
wierzchołki w kolejności 1, 2,
4 5 6
4 5 6
3, 4, 5, 6.
3, 4, 5, 6.
Drzewo
Drzewo
Drzewa wymuszają hierarchiczną organizację
Drzewa wymuszają hierarchiczną organizację
elementów, z tego względu znajdują powszechne
elementów, z tego względu znajdują powszechne
zastosowanie w przetwarzaniu wszelkiego rodzaju
zastosowanie w przetwarzaniu wszelkiego rodzaju
danych o układzie hierarchicznym, na przykład
danych o układzie hierarchicznym, na przykład
schematów organizacyjnych firm. Drzewa stanowią
schematów organizacyjnych firm. Drzewa stanowią
także nieodłączny element wszelkiego rodzaju
także nieodłączny element wszelkiego rodzaju
kompilatorów, które wykorzystują je do
kompilatorów, które wykorzystują je do
reprezentowania wyrażeń matematycznych i ogólnie
reprezentowania wyrażeń matematycznych i ogólnie
składni kodu z
ródłowego. Analiza wszelkiego rodzaju
składni kodu z
ródłowego. Analiza wszelkiego rodzaju
połączeń, jak np. obwodów elektrycznych czy układów
połączeń, jak np. obwodów elektrycznych czy układów
komunikacyjnych, także odbywa się z wykorzystaniem
komunikacyjnych, także odbywa się z wykorzystaniem
drzew.
drzew.
� Zbigniew Bem
Drzewo stanowi kolekcję elementów,
Drzewo stanowi kolekcję elementów,
zwanych węzłami (ang. nodes), z których
zwanych węzłami (ang. nodes), z których
jeden wyróżniony jest jako korzeń (ang.
jeden wyróżniony jest jako korzeń (ang.
root). Węzły powiązane są ze sobą relacją
root). Węzły powiązane są ze sobą relacją
rodzicielstwa (ang. parenthood), która
rodzicielstwa (ang. parenthood), która
decyduje o ich hierarchicznym układzie.
decyduje o ich hierarchicznym układzie.
Węzeł drzewa, podobnie jak element listy,
Węzeł drzewa, podobnie jak element listy,
może mieć dowolną strukturę wewnętrzną.
może mieć dowolną strukturę wewnętrzną.
Graficznie węzł y przedstawiane są
Graficznie węzły przedstawiane są
najczęściej w postaci otoczonych
najczęściej w postaci otoczonych
kółeczkami liter, napisów lub liczb.
kółeczkami liter, napisów lub liczb.
Przykładowe drzewo o korzeniu x
Przykładowe drzewo o korzeniu x
x
x
Wierzchołek z ma trzy
Wierzchołek z ma trzy
następniki: t, u i w. Każdy
następniki: t, u i w. Każdy
wierzchołek, który ma
wierzchołek, który ma
następnik, jest
następnik, jest
z
z
wierzchołkiem
wierzchołkiem
y
y
wewnętrznym, w
wewnętrznym, w
przeciwnym razie jest liściem
przeciwnym razie jest liściem
(na przykład y). Zbiór
(na przykład y). Zbiór
w
w
t
t
następników wierzchołka x w
następników wierzchołka x w
u
u
drzewie T będziemy
drzewie T będziemy
oznaczać jako childrenr(x).
oznaczać jako childrenr(x).
(Będziemy pomijać indeks T
(Będziemy pomijać indeks T
wtedy, kiedy będzie
wtedy, kiedy będzie
jednoznacznie wiadomo, o
jednoznacznie wiadomo, o
v
v
które drzewo chodzi).
które drzewo chodzi).
Każdy wierzchołek z wyjątkiem korzenia ma poprzednik
Każdy wierzchołek z wyjątkiem korzenia ma poprzednik
(na przykład v ma poprzednik u). Poprzednik wierzchołka x
(na przykład v ma poprzednik u). Poprzednik wierzchołka x
w drzewie T będziemy oznaczać jako pT(x). (Będziemy
w drzewie T będziemy oznaczać jako pT(x). (Będziemy
pomijać indeks T wtedy, kiedy będzie jednoznacznie
pomijać indeks T wtedy, kiedy będzie jednoznacznie
wiadomo, o które drzewo chodzi). Potomkami wierzchołka
wiadomo, o które drzewo chodzi). Potomkami wierzchołka
z są zarówno on sam, jak i jego następniki t, u i w, ale także
z są zarówno on sam, jak i jego następniki t, u i w, ale także
następnik v wierzchołka u. Z kolei za przodków
następnik v wierzchołka u. Z kolei za przodków
wierzchołka v uważa się jego samego, jego poprzednika u, a
wierzchołka v uważa się jego samego, jego poprzednika u, a
także wierzchołki z i x, leżące na ścieżce od v do korzenia.
także wierzchołki z i x, leżące na ścieżce od v do korzenia.
Głębokość (lub poziom) wierzchołka w drzewie to jego
Głębokość (lub poziom) wierzchołka w drzewie to jego
odległość od korzenia (x na przykład ma głębokość 0, a v
odległość od korzenia (x na przykład ma głębokość 0, a v
ma głębokość 3). Wysokość wierzchołka to maksymalna
ma głębokość 3). Wysokość wierzchołka to maksymalna
długość drogi od danego wierzchołka do liścia (na przykład
długość drogi od danego wierzchołka do liścia (na przykład
wysokość x wynosi 3, a wysokość y - 0). Wysokość drzewa
wysokość x wynosi 3, a wysokość y - 0). Wysokość drzewa
to wysokość jego korzenia (w naszym przykładzie wynosi
to wysokość jego korzenia (w naszym przykładzie wynosi
3).
3).
" Formalnie, drzewo może zostać zdefiniowane w
" Formalnie, drzewo może zostać zdefiniowane w
spos ób rekurencyjny :
sposób rekurencyjny :
1. Pojedynczy węzeł jest zarazem drzewem i
1. Pojedynczy węzeł jest zarazem drzewem i
korzeniem.
korzeniem.
2. Załóżmy, że n jest węzłem, a T1, T2, ..., Tk są
2. Załóżmy, że n jest węzłem, a T1, T2, ..., Tk są
drzewami o korzeniach (odpowiednio) n1, n2, ..., nk.
drzewami o korzeniach (odpowiednio) n1, n 2, ..., n k.
Czyniąc węzeł n rodzicem węzłów n1, n2, ..., nk
Czyniąc węzeł n rodzicem węzłów n1, n2, ..., nk
tworzymy drzewo o korzeniu n;
tworzymy drzewo o korzeniu n;
drzewa T1, T2, ..., Tk stają się poddrzewami (ang.
drzewa T1, T2, ..., Tk stają się poddrzewami (ang.
subtrees) tego drzewa, a węzły n1, n2, ..., nk
subtrees) tego drzewa, a węzły n1, n2, ..., nk
nazywane są dziećmi (ang. childrens) węzła n.
nazywane są dziećmi (ang. childrens) węzł a n.
Węzeł rodzicielski nazywany jest też ojcem węzłów,
Węzeł rodzicielski nazywany jest też ojcem węzłów,
będących jego synami (parent i child ).
będących jego synami (parent i child ).
Implementacja drzewa
Implementacja drzewa
" Drzewo reprezentuje się zwykle albo za pomocą
" Drzewo reprezentuje się zwykle albo za pomocą
struktury dowiązaniowej (używając rekordów i
struktury dowiązaniowej (używając rekordów i
dowiązań), albo za pomocą struktury indeksowej
dowiązań), albo za pomocą struktury indeksowej
(używając tablicy).
(używając tablicy).
" Gdy struktura drzewa jest ustalona, stosuje się na ogół
" Gdy struktura drzewa jest ustalona, stosuje się na ogół
reprezentację tablicową, a gdy reprezentowane drzewo
reprezentację tablicową, a gdy reprezentowane drzewo
może mieć dowolny kształt - dowiązaniową. Często
może mieć dowolny kształt - dowiązaniową. Często
przy przedstawianiu algorytmów nie jest istotne, jaka
przy przedstawianiu algorytmów nie jest istotne, jaka
reprezentacja jest używana. W takim wypadku
reprezentacja jest używana. W takim wypadku
będziemy stosować ogólną, abstrakcyjną notację
będziemy stosować ogólną, abstrakcyjną notację
funkcyjną p(x) i chlldren(x) zamiast konkretnych x^.p i
funkcyjną p(x) i chlldren(x) zamiast konkretnych x^.p i
x^.children czy p[x] i children[x].
x^.children czy p[x] i children[x].
I Przykład: Algorytm przechodzenia
I Przykład: Algorytm przechodzenia
drzewa z korzeniem
drzewa z korzeniem
" W podanym tu algorytmie zakładamy, że vertex jest
" W podanym tu algorytmie zakładamy, że vertex jest
typem danych, reprezentującym wierzchołek
typem danych, reprezentującym wierzchołek
drzewa, a previsit(v) i postvisit(v) to procedury
drzewa, a previsit(v) i postvisit(v) to procedury
specyfikujące działania wykonywane - odpowiednio
specyfikujące działania wykonywane - odpowiednio
- przy wejściu do wierzchołka v i przy wyjściu z
- przy wejściu do wierzchołka v i przy wyjściu z
niego.
niego.
" Aby przejść cale drzewo o korzeniu r wywołujemy
" Aby przejść cale drzewo o korzeniu r wywołujemy
traverse(r).
traverse(r).
procedure traverse(v: vertex);
procedure traverse(v: vertex);
var w : vertex;
var w : vertex;
begin
begin
previsit(v);
previsit(v);
for each w in children(v) do
for each w in children(v) do
traverse(w);
traverse(w);
postvisit(v)
postvisit(v)
end {traverse};
end {traverse};
Gdy procedura postvisit(v) nie ma treści, mamy do
Gdy procedura postvisit(v) nie ma treści, mamy do
czynienia z przejściem drzewa metodą preorder,
czynienia z przejściem drzewa metodą preorder,
a gdy procedura previsit(v) nie ma treści - metodą
a gdy procedura previsit(v) nie ma treści - metodą
postorder.
postorder.
Metody preorder użyjemy na przykład do obliczenia
Metody preorder użyjemy na przykład do obliczenia
głębokości wierzchołków drzewa, a metody
głębokości wierzchołków drzewa, a metody
postorder do obliczenia ich wysokości .
postorder do obliczenia ich wysokości .
Szczególnym przypadkiem drzewa z korzeniem jest
Szczególnym przypadkiem drzewa z korzeniem jest
drzewo binarne, w którym dla każdego wierzchołka
drzewo binarne, w którym dla każdego wierzchołka
v mamy �#children(v)�#d" 2. W drzewie binarnym
v mamy �#children(v)�#d" 2. W drzewie binarnym
każdy następnik wierzchołka v jest albo lewy, albo
każdy następnik wierzchołka v jest albo lewy, albo
prawy (przy czym tylko jeden może być lewy i tylko
prawy (przy czym tylko jeden może być lewy i tylko
jeden prawy). Używać będziemy następujących
jeden prawy). Używać będziemy następujących
oznaczeń:
oznaczeń:
lewy następnik v, jeśli jest określony
lewy następnik v, jeśli jest określony
left(v) =
left(v) =
nil w przeciwnym razie
nil w przeciwnym razie
prawy następnik v, jeśli jest określony
prawy następnik v, jeśli jest określony
right(v) =
right(v) =
nil w przeciwnym razie
nil w przeciwnym razie
Dla każdego wierzchołka v zbiór potomków jego
Dla każdego wierzchołka v zbiór potomków jego
lewego następnika oraz zbiór potomków jego
lewego następnika oraz zbiór potomków jego
prawego następnika tworzą drzewa nazywane -
prawego następnika tworzą drzewa nazywane -
odpowiednio - lewym i prawym poddrzewem
odpowiednio - lewym i prawym poddrzewem
wierzchołka v.
wierzchołka v.
II przykład: Algorytm przechodzenia
II przykład: Algorytm przechodzenia
drzewa binarnego
drzewa binarnego
W podanym tu algorytmie zakładamy, jak
W podanym tu algorytmie zakładamy, jak
poprzednio, że vertex jest typem danych,
poprzednio, że vertex jest typem danych,
reprezentującym wierzchoł ek drzewa, a
reprezentującym wierzchołek drzewa, a
previsit(v), invisit(v) i postvisit(v) to procedury
previsit(v), invisit(v) i postvisit(v) to procedury
specyfikujące działania wykonywane -
specyfikujące działania wykonywane -
odpowiednio - przy wejściu do wierzchołka v, po
odpowiednio - przy wejściu do wierzchołka v, po
rozpatrzeniu wierzchołków w lewym poddrzewie
rozpatrzeniu wierzchołków w lewym poddrzewie
a przed rozpatrzeniem wierzchołków w prawym
a przed rozpatrzeniem wierzchołków w prawym
poddrzewie i przy wyjściu z wierzchołka v.
poddrzewie i przy wyjściu z wierzchołka v.
procedurę b-traverse(v: vertex);
begin
previsit(v);
if left(v) <> nil then b-traverse(left(v));
invisit(v);
if right(v) <> nil then b-traverse(right(v));
postvisit(v)
end {b-traverse}
Gdy procedury invisit i postvisit nie mają treści, mamy do
czynienia z przejściem metodą preorder, a gdy previsit i
postvisit nie mają treści - z przejściem metodą inorder. Gdy
dotyczy to procedur previsit i invisit mamy do czynienia z
przejściem metodą postorder.