Algorytmy i struktury
Algorytmy i struktury
danych
danych
Uniwersytet J.Kochanowskiego w Kielcach
Uniwersytet J.Kochanowskiego w Kielcach
Dr Zbigniew Bem
Dr Zbigniew Bem
Literatura
Literatura
" Banachowski L., Dikes K., Rytter W., Algorytmy i
" Banachowski L., Dikes K., Rytter W., Algorytmy i
struktury danych, WNT, 2003.
struktury danych, WNT, 2003.
" T. H. Cormen, C. E. Leiserson, C. Stein i R. L.
" T. H. Cormen, C. E. Leiserson, C. Stein i R. L.
Rivest, Wprowadzenie do algorytmów, WNT 2004.
Rivest, Wprowadzenie do algorytmów, WNT 2004.
" Wróblewski P., Algorytmy struktury danych i
" Wróblewski P., Algorytmy struktury danych i
techniki programowania, Helion 1997.
techniki programowania, Helion 1997.
Projektowanie programu
Projektowanie programu
komputerowego
komputerowego
Tworzenie programu komputerowego rozwiązującego
Tworzenie programu komputerowego rozwiązującego
konkretny problem jest procesem wieloetapowym. Jak
konkretny problem jest procesem wieloetapowym. Jak
już omawialiśmy w procesie projektowania
już omawialiśmy w procesie projektowania
wyróżniamy pewne etapy, początkowe to:
wyróżniamy pewne etapy, początkowe to:
" Sformułowanie problemu.
" Sformułowanie problemu.
" Zbudowanie modelu logiczno-matematycznego.
" Zbudowanie modelu logiczno-matematycznego.
" Określenie metody rozwiązania problemu i algorytmu
" Określenie metody rozwiązania problemu i algorytmu
obliczeń.
obliczeń.
" Zakodowanie algorytmu, czyli napisanie programu w
" Zakodowanie algorytmu, czyli napisanie programu w
postaci ciągu rozkazów.
postaci ciągu rozkazów.
� Zbigniew Bem
Kiedy już dysponujemy odpowiednim modelem
Kiedy już dysponujemy odpowiednim modelem
matematycznym dla naszego problemu, szukamy
matematycznym dla naszego problemu, szukamy
rozwiązania wyrażającego się w kategoriach tegoż
rozwiązania wyrażającego się w kategoriach tegoż
modelu. Naszym głównym celem jest poszukiwanie
modelu. Naszym głównym celem jest poszukiwanie
rozwiązania w postaci algorytmu  pod tym pojęciem
rozwiązania w postaci algorytmu  pod tym pojęciem
rozumiemy skończoną sekwencję instrukcji, z których
rozumiemy skończoną sekwencję instrukcji, z których
każda ma klarowne znaczenie i może być wykonana w
każda ma klarowne znaczenie i może być wykonana w
skończonym czasie przy użyciu skończonej mocy
skończonym czasie przy użyciu skończonej mocy
obliczeniowej. Dobrym przykładem klarownej
obliczeniowej. Dobrym przykładem klarownej
instrukcji, wykonywalnej ,,w skończonym czasie i
instrukcji, wykonywalnej ,,w skończonym czasie i
skończonym wysiłkiem", jest instrukcja przypisania w
skończonym wysiłkiem", jest instrukcja przypisania w
rodzaju x �! y + z.
rodzaju x �! y + z.
Dane
Dane
" Każdy algorytm składa się z opisu obiektów na
" Każdy algorytm składa się z opisu obiektów na
których działa, oraz opisu czynności które są do
których działa, oraz opisu czynności które są do
wykonania na tych obiektach. Algorytm zapisany
wykonania na tych obiektach. Algorytm zapisany
w języku programowania nazywa się programem,
w języku programowania nazywa się programem,
a występujące w nim obiekty nazywa się danymi,
a występujące w nim obiekty nazywa się danymi,
wykonywane czynności opisane są za pomocą
wykonywane czynności opisane są za pomocą
odpowiednich instrukcji tego języka.
odpowiednich instrukcji tego języka.
" W wielu językach programowania dane są
" W wielu językach programowania dane są
elementami ustalonego zbioru zwanego typem.
elementami ustalonego zbioru zwanego typem.
� Zbigniew Bem
" Będziemy zakładać, że elementy wchodzące w
" Będziemy zakładać, że elementy wchodzące w
skład rozważanych struktur danych pochodzą z
skład rozważanych struktur danych pochodzą z
pewnego niepustego uniwersum U. Jak wiadomo z
pewnego niepustego uniwersum U. Jak wiadomo z
zasad programowania strukturalnego, zagadnienia
zasad programowania strukturalnego, zagadnienia
dotyczące budowy samej struktury danych i jej
dotyczące budowy samej struktury danych i jej
użycia w algorytmie wygodnie jest rozważać
użycia w algorytmie wygodnie jest rozważać
oddzielnie.
oddzielnie.
Procedury
Procedury
Procedury, jako podstawowe narzędzie każdego
Procedury, jako podstawowe narzędzie każdego
języka algorytmicznego, stanowią tak naprawdę
języka algorytmicznego, stanowią tak naprawdę
uogólnienie operatorów. Uwalniają one od
uogólnienie operatorów. Uwalniają one od
kłopotliwego ograniczenia się do podstawowych
kłopotliwego ograniczenia się do podstawowych
operacji (w rodzaju dodawania czy mnożenia
operacji (w rodzaju dodawania czy mnożenia
liczb), pozwalając na dokonywanie operacji
liczb), pozwalając na dokonywanie operacji
bardziej zaawansowanych, jak np. mnożenie
bardziej zaawansowanych, jak np. mnożenie
macierzy.
macierzy.
� Zbigniew Bem
Inną użyteczną cechą procedur jest enkapsulacja
Inną użyteczną cechą procedur jest enkapsulacja
niektórych fragmentów kodu. Określony fragment
niektórych fragmentów kodu. Określony fragment
programu, związany ściśle z pewnym aspektem
programu, związany ściśle z pewnym aspektem
funkcjonalnym programu, zamykany jest w ramach
funkcjonalnym programu, zamykany jest w ramach
ściśle zlokalizowanej sekcji.
ściśle zlokalizowanej sekcji.
Jako przykład posłuży procedura dokonująca
Jako przykład posłuży procedura dokonująca
wczytywania i weryfikacji danych. Jeżeli w pewnym
wczytywania i weryfikacji danych. Jeżeli w pewnym
momencie okaże się, że program powinien
momencie okaże się, że program powinien
(powiedzmy) oprócz liczb dziesiętnych honorować
(powiedzmy) oprócz liczb dziesiętnych honorować
także liczby w postaci szesnastkowej, niezbędne
także liczby w postaci szesnastkowej, niezbędne
zmiany trzeba będzie wprowadzić jedynie w ściśle
zmiany trzeba będzie wprowadzić jedynie w ściśle
określonym fragmencie kodu, bez ingerowania w inne
określonym fragmencie kodu, bez ingerowania w inne
fragmenty programu.
fragmenty programu.
Abstrakcyjne typy danych
Abstrakcyjne typy danych
Abstrakcyjne typy danych, oznaczane skrótem ADT
Abstrakcyjne typy danych, oznaczane skrótem ADT
(ang. Abstract Data Types), mogą być traktowane jak
(ang. Abstract Data Types), mogą być traktowane jak
model matematyczny, z którym związano określoną
model matematyczny, z którym związano określoną
kolekcję operacji. Przykładem prostego ADT może być
kolekcję operacji. Przykładem prostego ADT może być
zbiór liczb całkowitych, w stosunku do którego określono
zbiór liczb całkowitych, w stosunku do którego określono
operacje sumy, iloczynu i różnicy (w rozumieniu teorii
operacje sumy, iloczynu i różnicy (w rozumieniu teorii
mnogości). Argumentami operacji związanych z
mnogości). Argumentami operacji związanych z
określonym ADT mogą być także dane innych typów,
określonym ADT mogą być także dane innych typów,
dotyczy to także wyniku operacji. Przykładowo, wśród
dotyczy to także wyniku operacji. Przykładowo, wśród
operacji związanych z ADT reprezentującym zbiór liczb
operacji związanych z ADT reprezentującym zbiór liczb
całkowitych znajdować się mogą procedury badające
całkowitych znajdować się mogą procedury badające
przynależność określonego elementu do zbioru,
przynależność określonego elementu do zbioru,
zwracające liczbę elementów czy też tworzące nowy
zwracające liczbę elementów czy też tworzące nowy
zbiór złożony z podanych parametrów.
zbiór złożony z podanych parametrów.
� Zbigniew Bem
Operacje na ADT mogą być realizowane za pomocą
Operacje na ADT mogą być realizowane za pomocą
funkcji albo procedur.
funkcji albo procedur.
Tak jak procedury stanowią uogólnienie
Tak jak procedury stanowią uogólnienie
elementarnych operatorów (+, -, *, / itd.), tak
elementarnych operatorów (+, -, *, / itd.), tak
abstrakcyjne typy danych są uogólnieniem
abstrakcyjne typy danych są uogólnieniem
elementarnych typów danych (integer, real,
elementarnych typów danych (integer, real,
boolean itd.). Odpowiednikiem enkapsulacji kodu
boolean itd.). Odpowiednikiem enkapsulacji kodu
przez procedury jest natomiast enkapsulacja typu
przez procedury jest natomiast enkapsulacja typu
danych  w tym sensie, że definicja struktury
danych  w tym sensie, że definicja struktury
konkretnego ADT wraz z towarzyszącymi tej
konkretnego ADT wraz z towarzyszącymi tej
strukturze operacjami zamknięta zostaje w ściśle
strukturze operacjami zamknięta zostaje w ściśle
zlokalizowanym fragmencie programu.
zlokalizowanym fragmencie programu.
Implementacja
Implementacja
Implementacja abstrakcyjnego typu danych polega na
Implementacja abstrakcyjnego typu danych polega na
zdefiniowaniu jego odpowiednika (jako typu) w
zdefiniowaniu jego odpowiednika (jako typu) w
kategoriach konkretnego języka programowania oraz
kategoriach konkretnego języka programowania oraz
zapisaniu (również w tym języku) procedur
zapisaniu (również w tym języku) procedur
implementujących jego podstawowe operacje.
implementujących jego podstawowe operacje.
 Typ" w języku programowania stanowi zazwyczaj
 Typ" w języku programowania stanowi zazwyczaj
kombinację typów elementarnych tego języka oraz
kombinację typów elementarnych tego języka oraz
obecnych w tym języku mechanizmów agregujących.
obecnych w tym języku mechanizmów agregujących.
Najważniejszymi mechanizmami agregującymi języka
Najważniejszymi mechanizmami agregującymi języka
Pascal są tablice i rekordy. Na przykład abstrakcyjny
Pascal są tablice i rekordy. Na przykład abstrakcyjny
zbiór SET zawierający liczby całkowite może być
zbiór SET zawierający liczby całkowite może być
zaimplementowany jako tablica liczb całkowitych.
zaimplementowany jako tablica liczb całkowitych.
� Zbigniew Bem
Typy danych, struktury danych
Typy danych, struktury danych
Mimo że określenia  typ danych" ( lub po prostu
Mimo że określenia  typ danych" ( lub po prostu
 typ ),  struktura danych" i  abstrakcyjny typ
 typ ),  struktura danych" i  abstrakcyjny typ
danych" brzmią podobnie, ich znaczenie jest
danych" brzmią podobnie, ich znaczenie jest
całkowicie odmienne. W terminologii języka
całkowicie odmienne. W terminologii języka
programowania  typem danych" nazywamy zbiór
programowania  typem danych" nazywamy zbiór
wartości, jakie przyjmować mogą zmienne tego
wartości, jakie przyjmować mogą zmienne tego
typu. Na przykład zmienna typu boolean
typu. Na przykład zmienna typu boolean
przyjmować może tylko dwie wartości: true i
przyjmować może tylko dwie wartości: true i
false.
false.
Poszczególne języki programowania różnią się od siebie
Poszczególne języki programowania różnią się od siebie
zestawem elementarnych typów danych; w języku Pascal
zestawem elementarnych typów danych; w języku Pascal
elementarnymi typami danych są: liczby całkowite
elementarnymi typami danych są: liczby całkowite
(integer), liczby rzeczywiste (real), wartości
(integer), liczby rzeczywiste (real), wartości
boolowskie (boolean) i znaki (char). Także
boolowskie (boolean) i znaki (char). Także
mechanizmy agregacyjne, za pomocą których tworzy się
mechanizmy agregacyjne, za pomocą których tworzy się
typy złożone z typów elementarnych, różne są w różnych
typy złożone z typów elementarnych, różne są w różnych
językach. W języku C++ elementarnymi typami danych są
językach. W języku C++ elementarnymi typami danych są
typy wbudowane: cztery typy całkowite ze znakiem
typy wbudowane: cztery typy całkowite ze znakiem
(char,short int, int oraz long int), liczby
(char,short int, int oraz long int), liczby
niecałkowite (typ zmiennopozycyjny) (float,
niecałkowite (typ zmiennopozycyjny) (float,
double, long double), wartości boolowskie (bool)
double, long double), wartości boolowskie (bool)
oraz typ void.
oraz typ void.
ADT jest to model, z którym skojarzono zestaw
ADT jest to model, z którym skojarzono zestaw
operacji podstawowych. Jak już wspominaliśmy,
operacji podstawowych. Jak już wspominaliśmy,
możemy formułować algorytmy w kategoriach ADT,
możemy formułować algorytmy w kategoriach ADT,
chcąc jednak zaimplementować dany algorytm w
chcąc jednak zaimplementować dany algorytm w
konkretnym języku programowania, musimy znalez
ć
konkretnym języku programowania, musimy znalez
ć
sposób reprezentowania tych ADT w kategoriach
sposób reprezentowania tych ADT w kategoriach
typów danych i operatorów właściwych temu
typów danych i operatorów właściwych temu
językowi. Do reprezentowania modeli
językowi. Do reprezentowania modeli
matematycznych składających się na poszczególne
matematycznych składających się na poszczególne
ADT służą struktury danych, które stanowią kolekcje
ADT służą struktury danych, które stanowią kolekcje
zmiennych (być może różnych typów) połączonych ze
zmiennych (być może różnych typów) połączonych ze
sobą na różne sposoby.
sobą na różne sposoby.
� Zbigniew Bem
Podstawowymi blokami tworzącymi struktury
Podstawowymi blokami tworzącymi struktury
danych są komórki. Komórkę można obrazowo
danych są komórki. Komórkę można obrazowo
opisać jako skrzynkę (kontener), w której można
opisać jako skrzynkę (kontener), w której można
przechowywać pojedynczą wartość należącą do
przechowywać pojedynczą wartość należącą do
danego typu (elementarnego lub złożonego).
danego typu (elementarnego lub złożonego).
Struktury danych tworzy się przez nadanie nazwy
Struktury danych tworzy się przez nadanie nazwy
agregatom takich komórek i (opcjonalnie) przez
agregatom takich komórek i (opcjonalnie) przez
zinterpretowanie zawartości niektórych komórek
zinterpretowanie zawartości niektórych komórek
jako połączenia (czyli wskaz
nika) między
jako połączenia (czyli wskaz
nika) między
komórkami.
komórkami.
� Zbigniew Bem
" Najprostszym mechanizmem agregującym, obecnym
" Najprostszym mechanizmem agregującym, obecnym
w Pascalu i większości innych języków
w Pascalu i większości innych języków
programowania, jest (jednowymiarowa) tablica (ang.
programowania, jest (jednowymiarowa) tablica (ang.
array) stanowiąca sekwencję komórek zawierających
array) stanowiąca sekwencję komórek zawierających
wartości określonego typu, zwanego często typem
wartości określonego typu, zwanego często typem
bazowym. Pod względem matematycznym można
bazowym. Pod względem matematycznym można
postrzegać tablicę jako odwzorowanie zbioru
postrzegać tablicę jako odwzorowanie zbioru
indeksów (którymi mogą być liczby całkowite) w typ
indeksów (którymi mogą być liczby całkowite) w typ
bazowy. Konkretna komórka w ramach konkretnej
bazowy. Konkretna komórka w ramach konkretnej
tablicy może być identyfikowana w postaci nazwy,
tablicy może być identyfikowana w postaci nazwy,
której towarzyszy konkretna wartość indeksu. W
której towarzyszy konkretna wartość indeksu. W
języku Pascal indeksami mogą być m.in. liczby
języku Pascal indeksami mogą być m.in. liczby
całkowite z określonego przedziału (noszącego nazwę
całkowite z określonego przedziału (noszącego nazwę
typu okrojonego) oraz wartości typu wyliczeniowego,
typu okrojonego) oraz wartości typu wyliczeniowego,
jak np. typ (czarny, niebieski, czerwony, zielony).
jak np. typ (czarny, niebieski, czerwony, zielony).
Typ bazowy tablicy może być w zasadzie
Typ bazowy tablicy może być w zasadzie
dowolnym typem, tak więc deklaracja:
dowolnym typem, tak więc deklaracja:
name: array [ indextype ] of celltype:
name: array [ indextype ] of celltype:
określa tablicę o nazwie name, złożoną z
określa tablicę o nazwie name, złożoną z
elementów typu bazowego celltype,
elementów typu bazowego celltype,
indeksowanych wartościami typu indextype.
indeksowanych wartościami typu indextype.
Innym powszechnie używanym mechanizmem
Innym powszechnie używanym mechanizmem
agregującym są rekordy. Rekord jest komórką
agregującym są rekordy. Rekord jest komórką
składającą się z innych komórek zwanych polami,
składającą się z innych komórek zwanych polami,
mających na ogół różne typy. Rekordy często
mających na ogół różne typy. Rekordy często
łączone są w tablice  typ rekordowy staje się
łączone są w tablice  typ rekordowy staje się
wówczas typem bazowym tablicy.
wówczas typem bazowym tablicy.
Deklaracja pascalowa:
Deklaracja pascalowa:
var
var
reclist: array[1..4] of record
reclist: array[1..4] of record
data: real;
data: real;
next: integer;
next: integer;
end;
end;
określa czteroelementową tablicę, której komórka jest
określa czteroelementową tablicę, której komórka jest
rekordem zawierającym dwa pola: data i next.
rekordem zawierającym dwa pola: data i next.
" Trzecim mechanizmem agregującym, dostępnym w
" Trzecim mechanizmem agregującym, dostępnym w
niektórych językach, są pliki.
niektórych językach, są pliki.
Plik, podobnie jak jednowymiarowa tablica, stanowi
Plik, podobnie jak jednowymiarowa tablica, stanowi
sekwencję elementów określonego typu. W
sekwencję elementów określonego typu. W
przeciwieństwie jednak do tablicy, plik nie podlega
przeciwieństwie jednak do tablicy, plik nie podlega
indeksowaniu; elementy dostępne są tylko w takiej
indeksowaniu; elementy dostępne są tylko w takiej
kolejności w jakiej fizycznie występują w pliku.
kolejności w jakiej fizycznie występują w pliku.
Poszczególne elementy tablicy ( i poszczególne pola
Poszczególne elementy tablicy ( i poszczególne pola
rekordu ) są natomiast dostępne w sposób
rekordu ) są natomiast dostępne w sposób
bezpośredni, czyli szybciej niż w pliku. Plik odróżnia
bezpośredni, czyli szybciej niż w pliku. Plik odróżnia
jednak od tablicy istotna zaleta  jego wielkość
jednak od tablicy istotna zaleta  jego wielkość
(liczba zawartych w nim elementów) może zmieniać
(liczba zawartych w nim elementów) może zmieniać
się w czasie i jest potencjalnie nieograniczona.
się w czasie i jest potencjalnie nieograniczona.
Wskaz
niki i kursory
Wskaz
niki i kursory
Oprócz mechanizmów agregujących istnieją
Oprócz mechanizmów agregujących istnieją
jeszcze inne sposoby ustanawiania relacji między
jeszcze inne sposoby ustanawiania relacji między
komórkami  służą do tego wskaz
niki i kursory.
komórkami  służą do tego wskaz
niki i kursory.
" Wskaz
nik jest komórką, której zawartość
" Wskaz
nik jest komórką, której zawartość
jednoznacznie identyfikuje inną komórkę. Fakt, że
jednoznacznie identyfikuje inną komórkę. Fakt, że
komórka A jest wskaz
nikiem komórki B,
komórka A jest wskaz
nikiem komórki B,
zaznaczamy na schemacie struktury danych
zaznaczamy na schemacie struktury danych
rysując strzałkę od A do B.
rysując strzałkę od A do B.
W języku Pascal to, że zmienna ptr może
W języku Pascal to, że zmienna ptr może
wskazywać komórkę o typie celltype,
wskazywać komórkę o typie celltype,
zaznaczamy w następujący sposób:
zaznaczamy w następujący sposób:
var
var
ptr: ^celltype;
ptr: ^celltype;
Znak  ^  poprzedzający nazwę typu bazowego
Znak  ^  poprzedzający nazwę typu bazowego
oznacza typ wskaz
nikowy (czyli zbiór wartości
oznacza typ wskaz
nikowy (czyli zbiór wartości
stanowiących wskazania na komórkę o typie
stanowiących wskazania na komórkę o typie
celltype). Odwołanie do komórki wskazywanej
celltype). Odwołanie do komórki wskazywanej
przez zmienną ptr (zwane także dereferencją
przez zmienną ptr (zwane także dereferencją
wskaz
nika) ma postać ptr^  znak  ^ 
wskaz
nika) ma postać ptr^  znak  ^ 
występuje za nazwą zmiennej.
występuje za nazwą zmiennej.
W języku C++ , np
W języku C++ , np
celltype * ptr
celltype * ptr
" Kursor tym różni się od wskaz
nika, że
" Kursor tym różni się od wskaz
nika, że
identyfikuje komórkę w ramach konkretnej tablicy
identyfikuje komórkę w ramach konkretnej tablicy
 wartością kursora jest indeks odnośnego
 wartością kursora jest indeks odnośnego
elementu. W samym zamyśle nie różni się on od
elementu. W samym zamyśle nie różni się on od
wskaz
nika  jego zadaniem jest także
wskaz
nika  jego zadaniem jest także
identyfikowanie komórki  jednak, w
identyfikowanie komórki  jednak, w
przeciwieństwie do niego, nie można za pomocą
przeciwieństwie do niego, nie można za pomocą
kursora identyfikować komórek  samodzielnych",
kursora identyfikować komórek  samodzielnych",
które nie wchodzą w skład tablicy.
które nie wchodzą w skład tablicy.
W Pascalu nie jest możliwe utworzenie wskaz
nika
W Pascalu nie jest możliwe utworzenie wskaz
nika
do konkretnej komórki tablicy, więc jedynie
do konkretnej komórki tablicy, więc jedynie
kursory umożliwiają identyfikowanie
kursory umożliwiają identyfikowanie
poszczególnych komórek.
poszczególnych komórek.
" Na schemacie struktury danych kursory zaznaczane są
" Na schemacie struktury danych kursory zaznaczane są
podobnie jak wskaz
niki, czyli za pomocą strzałek, a
podobnie jak wskaz
niki, czyli za pomocą strzałek, a
dodatkowo w komórkę będącą kursorem może być
dodatkowo w komórkę będącą kursorem może być
wpisana jej zawartość dla zaznaczenia, iż nie mamy do
wpisana jej zawartość dla zaznaczenia, iż nie mamy do
czynienia z  typowym" wskaz
nikiem.
czynienia z  typowym" wskaz
nikiem.
" Z fundamentalnej różnicy między wskaz
nikiem a
" Z fundamentalnej różnicy między wskaz
nikiem a
kursorem, implementacja wskaz
ników ( we wszystkich
kursorem, implementacja wskaz
ników ( we wszystkich
niemal językach, w których wskaz
niki są obecne) bazuje
niemal językach, w których wskaz
niki są obecne) bazuje
na adresie komórki w przestrzeni adresowej procesu.
na adresie komórki w przestrzeni adresowej procesu.
Adres ten (a więc i konkretna wartość wskaz
nika) ma
Adres ten (a więc i konkretna wartość wskaz
nika) ma
sens jedynie w czasie wykonywania programu  nie
sens jedynie w czasie wykonywania programu  nie
istnieje więc jakakolwiek wartość wskaz
nika, którą
istnieje więc jakakolwiek wartość wskaz
nika, którą
można by umieścić na schemacie. Kursor natomiast jest
można by umieścić na schemacie. Kursor natomiast jest
wielkością absolutną, pozostającą bez związku z
wielkością absolutną, pozostającą bez związku z
konkretnymi adresami komórek
konkretnymi adresami komórek