1
Plik zawiera materiał ilustracyjny do wykładu:
(szczegół(we (mówienie zagadnień z przykładami
p(dane będzie w trakcie wykładu)
Studia za(czne
Nazwa przedmi(tu: Algorytmy i złożonośćEgz.
Liczba g(dzin: 27 godz. wykładu +
24 godz. ćwiczeń audyt(ryjnych
Efekty kształcenia:
1. Nabycie te(retycznej i praktycznej umiejętn(ści
p(sługiwania się zł(ż(nymi strukturami danych.
2. Nabycie umiejętn(ści r(związywanie pr(blemów
p(przez p(prawną alg(rytmizację.
3. Nabycie umiejętn(ści (ceny klasy alg(rytmów z
p(dstawami szac(wania ich zł(ż(n(ści (bliczeni(wej.
4. Przysw(jenie s(bie ideii pr(gram(wania strukturalneg(.
Pr(gram ram(wy przedmi(tu:
1. Typy danych. Typy pr(ste i zł(ż(ne. Implementacja
typów pr(stych i sp(s(by ich wyk(rzystania przez
pr(gram. Typy p(rządk(we.
2. Tablica i rekord jak( agregaty danych. Reprezentacja w
pamięci. Bezp(średni d(stęp d( skład(wych.
3. Pojęcie, postacie i własności algorytmów.
Przetwarzanie imperatywne. Asercje: p(czątk(wa i
k(ńc(wa alg(rytmu. P(dstaw(we met(dy strukturalizacji
alg(rytmów: pętle iteracyjne, rekurencja. Warunek st(pu.
4. Podstawowe idee programowania strukturalnego.
Pr(cedury i funkcje. K(munikacja funkcji z (t(czeniem.
 2
Zjawiska na st(sie dla zmiennych. Met(dy t(p-d(wn i
t(p-up k(nstru(wania alg(rytmów.
5. Algorytmy rekurencyjne. Przykłady. St(s dla
zmiennych w rekurencji. Rekurencja zagnieżdż(na.
Kł(p(ty z rekurencją. Rekurencja a iteracja.
Rekurencyjne typy danych.
6. Typ wskaz
nikowy. Al(kacja dynamiczna i nie
dynamiczna zmiennych. Pr(gram(wanie z
wyk(rzystaniem struktur dynamicznych.
7. Listy liniowe. Alg(rytmy (bsługi list lini(wych.
Dynamiczne LIFO-st(sy i FIFO-k(lejki, listy
dwukierunk(we, sam((rganizujące się listy. Listy z
przesk(kami. K(d(wanie mieszające.
8. Drzewa i lasy. Drzewa binarne. Drzew( binarnych
p(szukiwań. Drzew( zrówn(waż(ne i drzew( AVL.
Drzewa decyzyjne. Wyrażenia kr(pk(we.
9. Grafy. Met(dy reprezentacji grafu. Alg(rytm szukania w
głąb dla grafu. Drzewa r(zpinające graf.
10. Algorytmy z powrotami. Met(dy usprawniania
alg(rytmów żarł(cznych: systematyczne, heurystyczne.
11. Szacowanie zł(ż(n(ści (bliczeni(wej alg(rytmów
iteracyjnych. Klasy P- i NP-pr(blemów. Pr(blemy NP-
zupełne i silnie NP-zupełne.
Wykład ma charakter autorski.
Literatura p(dstaw(wa:
1. Wróblewski P.: Algorytmy, struktury danych i techniki
programowania, Heli(n, 2003
2. K(leśnik K: Wstęp do programowania, Heli(n, 1999
 3
Literatura uzupełniająca:
1. Dr(zdek A.: C++ Algorytmy i struktury danych, Heli(n,
2004
2. Ah( V., Ullman J. D.: Wykłady z informatyki z
przykładami w języku C, Heli(n, 2003
3. Ah( V., H(pcr(ft J. E., Ullman J. D.: Projektowanie i
analiza algorytmów, Heli(n, 2003
4. Harris S., R(ss J.: Od podstaw Algorytmy, WNT, Heli(n,
2006
5. Neap(litan R., Naimip(ur K.: Podstawy algorytmów z
przykładami w języku C++, Heli(n, 2004
1. Typy danych
1.1. Typy proste
Języki pr(gram(wania p(sługują się p(jęciem typu danej.
P(jęcie t( zdefiniujemy mówiąc, że typ danej jest (kreśl(ny
p(przez:
" r(zmiar pamięci zajm(wanej przez daną (kreślaneg(
typu (wyraż(ny w bajtach),
" sp(sób implementacji, czyli sp(sób przech(wywania
danej w pamięci k(mputera,
" zestaw (peracji, jakie m(żna wyk(nać na danej w
(kreśl(nym języku pr(gram(wania.
Typy danych dzielimy na pr(ste i zł(ż(ne. Dana typu
prostego reprezentuje zawsze p(jedynczą wart(ść. Dana typu
złożonego zawiera wiele danych teg( sameg(, lub różnych
typów (w tym innych typów zł(ż(nych).
 4
Literał jest napisem, któreg( p(stać zawiera inf(rmacje
zarówn( ( typie danej, jak również ( jej wart(ści. Zmienne w
pr(gramach przech(wują wart(ści danych zawsze ściśle
(kreśl(neg( typu.
Oznaczenie Przykład Podstawowe
Typ Rozmiar
typu danej operacje
- arytmetyczne
całk(wit(liczb(we,
całk(wity int 2 bajty 13
- l(giczne,
- przyrównania
- arytmetyczne
rzeczywisty float 4 bajty 13.0 zmienn(p(zycyjne,
- przyrównania
Znak(wy char 1 bajt  A jak całk(wite
- arytmetyka
adres w
wskaz
nik(wy typ " 2 bajty adresów,
"
"
"
pamięci
- przyrównania
Tabela 1. P(równanie najważniejszych typów pr(stych
języka C/C++
Dana
Typ Implementacja
(literał)
1 int Stał(p(zycyjna
1.0 float Zmienn(p(zycyjna
 1 char k(d ASCII znaku 1, tzn. 49
tablica znak(wa
 1 string
49 0
dwuelement(wa
Tabela 2. Różne met(dy implementacji w języku C/C++,
p(z(rnie tej samej zmiennej w p(staci jedynki, w
zależn(ści (d typu tej danej.
 5
Ob(k r(zmiaru i implementacji, p(szczególne typy danych
różnią się sposobem wykorzystania przez program. Wyraża
się t( (kreśl(nym dla daneg( typu zestawem (peracji
((perat(rów) na danej, typami wyników (peracji, itd.
Przykłady (peracji na danych w języku C/C++:
" 1 / 4 jest (peracją stał(p(zycyjną, a jej wynikiem jest 0,
" 1.0/4 jest (peracją zmienn(p(zycyjną, a jej wynikiem
jest 0.25,
" jeśli dana a będzie typu znak(weg( ( wart(ści  A , t(
wynikiem (peracji a+1 będzie znak  B ,
" jeśli dana p będzie typu wskaz
nik(weg( i
przech(wywać będzie adres zmiennej pewneg( typu, t(
p+1 będzie adresem następnej zmiennej teg( typu w
pamięci (peracyjnej.
Ważnym jest uświad(mienie s(bie, że takie typy pr(ste, jak:
całk(wity, l(giczny, znak(wy, wyliczeni(wy, są typami
porządkowanymi (skalarnymi), tzn. mają taką własn(ść, że
dla każdej wart(ści teg( typu (za wyjątkiem pierwszej i
(statniej (granicz(neg( zbi(ru wart(ści) m(żemy zawsze
(kreślić wart(ść p(przednią i następną. Własn(ści tej nie mają
typy rzeczywiste (zmienn(p(zycyjne), takie jak: float, double.
1.2. Typy złożone
Dane typu złożonego (agregaty) reprezentują pewne
sk(ńcz(ne zbi(ry wart(ści tych samych, lub różnych typów,
zwanych typami podstawowymi lub typami bazowymi.
 6
Aby (kreślić typ zł(ż(ny należy p(dać:
" typy jeg( skład(wych (tzw. typy baz(we),
" met(dę strukturalizacji (p(łączenie skład(wych w
cał(ść).
Tablica
Opis typu Dostęp do składowych
Dane al(k(wane w pamięci
Bezp(średni, p(przez
(peracyjnej, p(ł(ż(ne w k(lejnych
wart(ść indeksu, lub
(bszarach pamięci, wszystkie teg(
wart(ść wskazania
sameg( typu
Rekord
Opis typu Dostęp do składowych
Dane al(k(wane w pamięci
Bezp(średni, p(przez
(peracyjnej, p(ł(ż(ne w k(lejnych
nazwę p(la rek(rdu
(bszarach pamięci różnych typów
Tabela 3. P(dstaw(we typy zł(ż(ne języka C++
Każda zmienna, zarówn( pr(sta jak i zł(ż(na, m(że być
p(w(łana d( życia jak( zmienna nie dynamiczna lub zmienna
dynamiczna. Mówiąc najbardziej (gólnie, ist(tna różnica
między nimi p(lega na tym, że ( ile d(stęp d( zmiennych nie
dynamicznych uzyskujemy p(sługując się ich nazwami, ( tyle
d(stęp d( zmiennych dynamicznych uzyskujemy wyłącznie
p(przez p(danie ich adresu (p(ł(żenia w pamięci
(peracyjnej).
 7
Oprócz wyżej wymieni(nych, w trakcie niniejszeg( wykładu
(mawiane będą jeszcze p(niższe struktury danych:
" listy lini(we jedn(- i dwukierunk(we,
" st(sy i k(lejki,
" drzewa binarne i wiel(kierunk(we,
" grafy.
Wyżej wymieni(ne struktury, zwłaszcza p(w(łane d( życia
jak( dynamiczne, (dgrywają zasadniczą r(lę w inf(rmatyce,
dlateg( właśnie im p(święc(na będzie większa część
wykładu.
2. Typ tablicowy
Jak t( już z(stał( p(wiedziane, tablice są zł(ż(nymi
strukturami danych przech(wującymi pewną il(ść danych
teg( sameg( typu ( typu baz(weg(). Typem baz(wym m(że
być d(w(lny typ danych (pr(sty lub zł(ż(ny), nie zawierający
w swej strukturze, na d(w(lnym p(zi(mie, typów
al(k(wanych p(za pamięcią (peracyjną (takich jak pliki czy
strumienie). W trakcie realizacji pr(gramu tablice są
przech(wywane w pamięci (peracyjnej k(mputera.
Przykład deklaracji tablicy w języku C/C++:
int t [ N ]; (1)
Interpretacja tej deklaracji: t jest identyfikat(rem (nazwą)
jednowymiarowej tablicy danych typu całk(witeg( (
r(zmiarze N.
Tablicę charakteryzują więc dwie wielk(ści:
" wymiar, który p(daje liczbę przestrzennych kierunków
r(zmieszczenia elementów tablicy,
" rozmiary, które (kreślają liczbę elementów tablicy w
każdym wymiarze.
 8
indeksy 0 1 2 3 4
wart(ści
4 -1 7 0 2
Rys. 1 Przykład(wa tablica jedn(wymiar(wa,
(dp(wiadająca deklaracji (1), gdy N=5
Zasadniczą wadą tablicy jest stałość jej rozmiarów. Jeżeli
chcemy przydzielić w pr(gramie pamięć na tablicę musimy
p(dać k(nkretną wart(ść jej r(zmiarów.
W bibli(tece STL (Standard Template Library) języka C++
tablicę zaimplement(wan( w sp(sób, który p(zwala
elastycznie trakt(wać sprawę r(zmiarów tablicy. Mian(wicie
próba wstawienia n(weg( elementu p(za aktualny r(zmiar,
p(w(duje aut(matyczne r(zszerzenie zajm(waneg( przez
tablicę (bszaru. Jest t( jednak (peracja k(szt(wna, związana z
przen(szeniem wart(ści elementów tablicy d( n(weg(,
szerszeg( (bszaru pamięci, a następnie zw(lnieniem (bszaru
pamięci d(tychczas zajm(waneg( przez tablicę. Z punktu
widzenia alg(rytmów, (bsługujących tablicę, będziemy ją
trakt(wać jak( strukturę ( stałych r(zmiarach.
Nat(miast niewątpliwą zaletą tablicy jest bezpośredni dostęp.
Dzięki niemu uzyskujemy, p(przez p(danie p(ł(żenia
elementu w tablicy (indeksu) np. w zapisie t[i], m(żliw(ść
natychmiast(weg( d(stępu d( teg( elementu.
Obie, wyżej (mówi(ne cechy tablicy  stał(ść r(zmiaru i
bezp(średni d(stęp d( jej skład(wych, wyznaczają d(ść wąski
(bszar zast(s(wań tablicy w pr(gram(waniu. Nadaje się (na
d( przech(wywania niewielkich il(ści danych, d( których
chcemy mieć bardz( szybki (bezp(średni) d(stęp i których
il(ść m(żna wcześniej przewidzieć.
 9
3. Typ rekordowy
Typ rekordowy (zwany czasem typem strukturowym) jest
typem zł(ż(nym i p(d(bnie jak typ tablic(wy, charakteryzuje
g( stał(ść r(zmiarów i bezp(średni d(stęp. W (dróżnieniu
jednak (d tablicy, składowe danej teg( typu (zwane polami),
m(gą być różnych typów. D(puszczalne są (jak( skład(we)
wszystkie typy (pr(ste i zł(ż(ne), jeżeli tylk( m(gą być
al(k(wane w pamięci (peracyjnej.
a)
Nazwisk( Imię Waga Płeć Data_ur(dz.
25 bajtów 25 bajtów 2 bajty 1 bajt 8 bajtów
b)
Nazwisk(
Imię
Waga
Płeć
Data_ur(dz.
25 bajtów
Rys. 2 Schemat al(kacji w pamięci :
a) przykład(weg( rek(rdu, przech(wująceg( dane (s(by,
b) te same dane przech(wywane w unii
P(szczególne p(la rekordu (struktury) są al(k(wane w
pamięci jedn( za drugim w k(lejn(ści zadeklar(wania.
Odmianą typu rek(rd(weg( jest unia. Unia jest al(k(wana w
ten sp(sób, że p(szczególne p(la są umieszczane w tym
samym miejscu pamięci p(cząwszy (d bajtu, który jest
 10
p(czątkiem al(kacji całej unii. W rezultacie r(zmiary unii są
równe dług(ści największeg( p(la. Unia jest więc d(sk(nałą
strukturą d( przech(wywania danych różnych typów, ale w
sytuacji, gdy w danej chwili wystarczy przech(wywać tylk(
jedną z nich. W takich sytuacjach unia daje (czywistą
(szczędn(ść pamięci.
Rek(rd jest przykładem struktury danych, w których d(stęp
d( jeg( skład(wych uzyskujemy p(przez nazwę skład(wej.
Niech r będzie nazwą nie dynamiczneg( rek(rdu z rys. 2a,
nat(miast ref - nazwą wskazania rek(rdu dynamiczneg(.
Wtedy d(stęp d( skład(wej rek(rdu, przech(wującej na
przykład wagę (s(by, uzyskać m(żna w dw(jaki sp(sób:
- dla rek(rdu nie dynamiczneg( - za p(m(cą selektora struk-
turowego w p(staci kr(pki r.waga,
- dla rek(rdu dynamiczneg( - za p(m(cą dwuargumentowe-
go operatora selekcji pola rek(rdu w p(staci strzałki
ref
waga.


Oba zapisy reprezentują ten sam (bszar pamięci w rek(rdzie.
Musimy mieć świad(m(ść, że zarówn( typ rek(rd(wy, jak i
unia, są szczególnymi przypadkami typu obiektowego,
zwaneg( inaczej klasą, w którym (prócz pól skład(wych
definiuje się funkcje, zwane metodami, lub usługami. Są (ne
uprawni(ne d( bezp(średnieg( wyk(nywania (peracji na
p(lach (biektu danej klasy. Zwyczaj(w( zmienną (kreśl(neg(
typu (biekt(weg( nazywamy obiektem klasy.
 11
Nazwa klasy
( parametry, dane
Atrybuty klasy
skład(we, p(la)
Met(dy klasy
(usługi, funkcje
skład(we)
Rys. 3. Schemat (gólny typu (biekt(weg( (klasy)
Wśród typów (zarówn( pr(stych jak i zł(ż(nych)
wyróżniamy: typy standardowe ( predefini(wane, d(stępne w
językach pr(gram(wania d( bezp(średnieg( użycia, których
d(kładna definicja (biekt(wa jest na (gół pr(gramiście
nieznana) i typy defini(wane ad hoc przez pr(gramistów.
Większ(ść (mawianych w trakcie teg( wykładu typów,
struktur danych i alg(rytmów ich (bsługi z(stała w języku
C++ zaimplement(wana w Standardowej Bibliotece
Szablonów ( STL). Bibli(teka ta jest (gr(mnym zbi(rem
elementów wiel(kr(tneg( użytku w f(rmie (gólnych
(szabl(n(wych) klas i funkcji, c( jest wielkim ułatwieniem dla
pr(gramistów. Zwalnia b(wiem z k(nieczn(ści
implement(wania całeg( szeregu struktur danych i
alg(rytmów. Jednak k(mp(nentów STL m(żna używać
prawidł(w( tylk( wtedy, gdy d(brze r(zumie się ich działanie
i zast(s(wania. Właśnie t( zr(zumienie jest celem teg(
wykładu.
 12
4. Pojęcie algorytmu
Najbardziej (gólnie przez algorytm r(zumie się, składający
się z ciągu kr(ków, przepis na (trzymanie jakieg(ś
k(nkretneg( pr(duktu, niek(niecznie materialneg(.
Najstarszymi alg(rytmami, jakie p(jawiły się w inf(rmatyce,
były alg(rytmy służące d( przetwarzania inf(rmacji
numerycznych. Dzisiaj te alg(rytmy nazywamy alg(rytmami
imperatywnymi ((d greckieg( sł(wa impero  r(zkazywać)
Dane Alg(rytm Dane
wejściowe wyjściowe
P(c) Q(d)
Rys. 4. Schemat przetwarzania imperatywneg(
Przetwarzanie imperatywne charakteryzuje się tym, że
alg(rytm p(biera pewne dane wejści(we i przetwarza je na
dane wyjści(we.
Na rysunku 4: c"C jest p(jedynczym zestawem danych
wejściowych, branych z całeg(, d(puszczalneg( zbi(ru
danych wejści(wych C. Funkcję P(c) nazywamy asercją
początkową. Określa (na, jakie warunki muszą spełniać
p(szczególne dane wejści(we c, aby alg(rytm (pr(gram)
wyk(nywał się p(prawnie (zg(dnie z zał(żeniami) w całym
zestawie danych wejści(wych C.
P(d(bnie  d"D jest p(jedynczym zestawem danych
wyjściowych, pr(duk(wanych przez pr(gram, branych z
całeg( zbi(ru danych wyjści(wych D. Q(d) nazywamy
asercją końcową. Określa (na, jakie warunki spełniają
p(szczególne zestawy danych wyjści(wych, przy zał(żeniu,
że asercja p(czątk(wa P(c) jest spełni(na, a więc alg(rytm
działa p(prawnie w całym zestawie danych wejści(wych C,.
 13
Określenie zbi(rów C i D, jak również p(danie pełnej p(staci
funkcji P(c) i Q(d), należy d( (b(wiązków tw(rząceg(
alg(rytm.
Sp(tykane p(stacie alg(rytmu:
" schemat bl(k(wy,
" sł(wny (pis f(rmalny,
" pseud(k(d,
" zapis w języku pr(gram(wania (pr(gram).
Wszystkie te p(staci alg(rytmu są tylk( jeg( zewnętrzną
f(rmą, więc semantycznie są równ(ważne.
Cechy, jakie p(winien p(siadać alg(rytm:
" (kreśl(n(ść,
" jedn(znaczn(ść,
" sk(ńcz(n(ść.
Określoność algorytmu spr(wadza się d( używania w jeg(
(pisie wyłącznie p(jęć, których znaczenie w danej dziedzinie
pr(blemu jest ściśle i jedn(znacznie (kreśl(ne.
Jednoznaczność algorytmu d(tyczy tzw. punktów
węzł(wych, w których zmuszeni jesteśmy p(djąć decyzję
d(tyczącą dalszeg( przetwarzania danych.
P P
A
A
W
W
B
a) b)
B
Rys. 5. Pr(blem niejedn(znaczn(ść alg(rytmu:
a) alg(rytm z punktem węzł(wym W pr(wadzącym d(
 14
niejedn(znaczn(ści,
b) r(związanie teg( pr(blemu p(przez umieszczenie w
punkcie niejedn(znaczn(ści warunku l(giczneg(
Skończoność algorytmu wymaga, aby dla każdeg( zestawu
danych wejści(wych c"C, spełniająceg( asercję p(czątk(wą,
alg(rytm d(szedł d( punktu k(ńc(weg( (zak(ńczył się),
(siągając zestaw wyników d"D, spełniający asercje k(ńc(wą.
M(gą być dwie przyczyny nie d(jścia alg(rytmu d( punktu
k(ńc(weg(: zawieszenie przetwarzania, zapętlenie.
4.1. Podstawowe metody strukturalizacji algorytmów
4.1.1. Pętle iteracyjne
Przez proces iteracyjny r(zumieć będziemy k(ntynu(wanie
p(wtórzeń wskazaneg( ciągu kr(ków alg(rytmu d(w(lną
(te(retycznie niesk(ńcz(ną) il(ść razy. P(dstaw(wymi
schematami realizacji teg( pr(cesu są pętla while i pętla
repeat.
P
P
I
fałsz
W fałsz
prawda W
prawda
I
a) b)
while ( W ) I ; do { I } while ( W ) ;
 15
Rys. 6. Pętle iteracyjne: a) - pętla while b) - pętla repeat
M(żna wykazać, że (bie pętle są równ(ważne . Wybór jednej
z nich jest p(dykt(wany najczęściej wyg(dą zapisu.
Oprócz wyżej wymieni(nych, st(sunk(w( częst( używaną
jest pętla for. Jest (na m(dyfikacją pętli while, w której użyt(
zmiennej sterującej pętlą. Zmienna sterująca musi być typu
porządkowego. Przypisuje się jej jedn(raz(w(, przed
wejściem d( pętli, pewną wart(ść p(czątk(wą. Wart(ść ta jest
następnie, przy każdym nawr(cie, m(n(t(nicznie zmieniana
(zwiększana, lub zmniejszana). Warunek petli W (kreśla, d(
jakiej wart(ści (największej, lub (dp(wiedni( - najmniejszej)
wart(ść zmiennej sterującej ma praw( się zwiększyć (lub
(dp(wiedni(  zmniejszyć), wyznaczając tym samym il(ść
nawr(tów w pętli iteracyjnej.
for(nadanie wartości początkowej; warunek stopu; instrukcja
zwiększająca) Instrukcja wewnętrzna cyklu; (a)
for(int i=1; i<=N; i++)I; (b)
Rys. 7. (a) - p(stać (gólna pętli for, (b)  przykład użycia w
języku C. Tutaj: i jest zmienna sterującą typu
całk(witeg(, N jest pewną stałą całk(witą, I jest
instrukcją wewnętrzną cyklu.
Zasadnicze znaczenie przy tw(rzeniu alg(rytmów z użyciem
pętli iteracyjnych ma zapewnienie warunku st(pu, t( jest
nied(puszczenie d( zapętlenia się alg(rytmu. M(żna g(
sf(rmuł(wać jak niżej
 16
Warunek stopu pętli iteracyjnej:
Warunek W i ciąg instrukcji I muszą być tak sk(nstru(wane,
aby dla każdeg( zestawu danych, jaki jest d(puszczalny w
punkcie P alg(rytmu, wyk(nanie pętli m(gł( być zak(ńcz(ne
p( wyk(naniu sk(ńcz(nej il(ści p(wtórzeń.
Warunkiem k(niecznym tak sf(rmuł(waneg( żądania jest, c(
najmniej, zapewnienie wpływu instrukcji I na wart(ści
zmiennych, wch(dzących w skład wyrażenia W.
4.1.2. Rekurencja
Zjawisk( rekurencji inaczej zwane rekursją, jest naturalnym
zjawiskiem sp(tykanym p(wszechnie. Jeg( ist(tą jest
(dw(ływanie się d( sameg( siebie. Alg(rytmy rekurencyjne
przerywają więc w trakcie przetwarzania swój wewnętrzny,
sekwencyjny pr(ces (bliczeni(wy, p( czym wznawiają n(wy
pr(ces r(zp(czynający działanie alg(rytmu (d p(czątku,
p(z(stawiając d(k(ńczenie p(przednieg( pr(cesu na (kres
póz
niejszy. W ten sp(sób p(wstaje te(retycznie niesk(ńcz(ny,
ciąg wyw(łań rekurencyjnych alg(rytmu, który aby mógł się
zak(ńczyć wymaga (siągnięcia prawdziw(ści warunku st(pu.
Rekurencja jest k(lejną, (b(k pr(cesu iteracyjneg(, ważną
met(dą strukturalizacji alg(rytmów.
4.2. Podstawowe idee programowania strukturalnego.
Zwykle alg(rytm, zapisany w wybranym języku
pr(gram(wania, stan(wi najmniejszą, niep(dzielną już,
jedn(stką (rganizacyjną pr(gramu k(mputer(weg(. Jest (n
(dsepar(wanym (d (t(czenia bytem, m(gącym jednak
 17
k(munik(wać się z (t(czeniem w ściśle (kreśl(ny sp(sób. W
języku C/C++ byt ten ma p(stać funkcji (patrz rys. 8).
Funkcja p(siada sw(je zmienne lokalne, których wart(ści są
nied(stępne na zewnątrz. Danymi wejściowymi funkcji są
wart(ści parametrów, z jakimi funkcja z(staje uruch(mi(na
(wyw(łana).
Języki pr(gram(wania zwykle p(zwalają, aby funkcja sięgała
(ch(ć jest t( sprzeczne z ideą pr(gram(wania strukturalneg()
d( zmiennych nielokalnych. Są t( zmienne, które z(stały
zadeklar(wane na zewnątrz wszystkich m(dułów (zmienne
globalne), lub też są zmiennymi l(kalnymi funkcji, która
przerwała sw(ją realizację i wyw(łała funkcję przez nas
r(zpatrywaną.
Takie sięganie przez alg(rytm d( zmiennych niel(kalnych
m(że p(w(d(wać jednak trudne d( przewidzenia zmiany
wart(ści zmiennych niel(kalnych. Z m(żliw(ści tych należy
więc k(rzystać w sp(sób wyraz
nie zamierz(ny i
k(ntr(l(wany. Jeżeli (dbywa się t( właśnie w taki sp(sób, t(
(siągnięte efekty d(tyczące zmiennych niel(kalnych
nazywamy efektami ubocznymi.
Czasem cel(w( tw(rzy się alg(rytmy wyłącznie w celu
pr(dukcji efektów ub(cznych. Nie zwracają (ne wyników.
Przyjęt( nazywać je procedurami. Ob(k zmiany wart(ści
zmiennych niel(kalnych, pr(cedury przede wszystkim
pr(dukują takie efekty, jak: p(branie lub wysłanie danych d(
strumienia, uruch(mienia urządzenia zewnętrzneg( k(mputera
itd.
W niektórych językach pr(gram(wania pr(cedury występują
jak( sam(dzielne byty (języki klasy Pascal), nat(miast w
języku C/C++ występują wyłącznie funkcje, których jednak
jeśli zajdzie taka p(trzeba, m(żemy użyć jak( pr(cedur,
(drzucając zwracany przez nie wynik.
 18
zmienne
nielokalne
zmienne lokalne
algorytm (funkcja)
wartości wynik
parametrów
efekty
Rys.8 Schemat k(munikacji funkcji z (t(czeniem
uboczne
Przykłady:
int length (char * s) ;
//deklaracja funkcji length, zwracającej dług(ść łańcucha
//(wart(ść całk(wita), wskazywaneg( przez s
int x=length (s) ;
// wyw(łanie funkcji length w celu uzyskania wyniku
length (s) ;
//wyw(łanie funkcji length w sp(sób typ(wy dla pr(cedury
//(z (drzuceniem wyniku).
Moduł programu strukturalnego, który jest większą
jedn(stką pr(gramu, m(że w języku C/C++ zawierać m.in.:
deklarację zmiennych gl(balnych (raz pewne il(ści funkcji.
 19
zmienne globalne
wskaz
nik stosu
zmienne
funkcja f 1
II lokalne
funkcji
I f 3
zmienne
funkcja f 2
lokalne
III funkcji
f 2
funkcja f 3
zmienne
globalne
a) b)
Rys. 9. a) Przykład(wy m(duł pr(gramu, b) wygląd st(su dla
zmiennych p( wyk(naniu wyw(łania III.
Strzałkami zaznacz(n( przykład(we wzajemne wyw(ływania
się funkcji w p(danej na rysunku k(lejn(ści: I, II, III.
Opis zdarzeń na st(sie, (d m(mentu załad(wania m(dułu
pr(gram(weg( z rys.9 d( chwili wyw(łania (znacz(neg( jak(
III, przedstawia p(niższa tabela:
 20
Zdarzenie Skutki na stosie
1. Załad(wanie m(dułu Przydział pamięci dla zmiennych
pr(gram(weg( gl(balnych
2. Wyw(łanie funkcji f2 Przydział pamięci dla zmiennych
l(kalnych funkcji f2
3. Wyw(łanie funkcji f1 z Przydział pamięci dla zmiennych
wnętrza funkcji f2 l(kalnych funkcji f1 na szczycie
st(su
4. Wyk(nanie się funkcji f1 Zw(lnienie pamięci zmiennych
i p(wrót ster(wania d( l(kalnych funkcji f1 (zdjęcie ich
funkcji f2 ze szczytu st(su)
5. Wyw(łanie funkcji f3 Przydział pamięci dla zmiennych
l(kalnych funkcji f3 na szczycie
st(su
Tabela 4. Opis zdarzeń na st(sie dla zmiennych dla
przykład(wych wyw(łań funkcji w m(dule
pr(gram(wym z rys. 9
4.3. Metody konstruowania algorytmów: top-up i top-
down. Pseudokod.
Metoda top-up w pr(gram(waniu strukturalnym
k(nstru(wania większeg( m(dułu pr(gram(weg( p(lega na
zapr(jekt(waniu i zbud(waniu pewnej il(ści niewielkich
funkcji, z których każda wyspecjaliz(wana jest w pewnych,
d(ść uniwersalnych w zast(s(waniach, czynn(ściach.
W celu zbud(wania większeg( m(dułu pr(gram(weg( (
pewnej, bardziej zł(ż(nej funkcj(naln(ści, pr(jektujemy
gl(balną strukturę danych teg( m(dułu, a następnie
(dp(wiednie funkcje ,,sterujące , które wyw(łując funkcje
niższeg( p(zi(mu, zapewniają (dp(wiednią ścieżkę (bliczeń
 21
w ramach p(żądanej funkcj(naln(ści m(dułu pr(gram(weg(.
Pełnią (ne zwykle r(le interfejsu d( całeg( m(dułu
pr(gram(weg(.
Na (gół funkcji najniższeg( p(zi(mu nie musimy tw(rzyć
gdyż dla większ(ści struktur danych znalez
ć je m(żna w
(dp(wiednich bibli(tekach, takich jak STL. Zbud(wane
m(duły m(żemy łączyć w większe jedn(stki. Przyp(mina t(
st(pni(we bud(wanie z małych ,,cegiełek większych
elementów budynku, aż d( pełnej bud(wli.
Metoda top-down p(lega na zapr(jekt(waniu najpierw
(gólneg( zarysu struktur danych i (gólnej funkcj(naln(ści
m(dułu, a następnie sch(dzeniu niżej i st(pni(wym
d(precyz(wywaniu szczegółów p(przez, najpierw
zapr(jekt(wanie (dp(wiednich funkcji, a następnie ich
zapisaniu w wybranym języku pr(gram(wania.
Z met(dą tą wiąże się p(jęcie pseudokodu. Jest t( sp(sób
zapisu alg(rytmu z wyk(rzystaniem met(d strukturalizacji
języka pr(gram(wania, ale bez d(prac(wywania szczegółów.
Część alg(rytmu zapisujemy więc w języku naturalnym. Taki
sp(sób zapisu alg(rytmu p(zwala sp(jrzeć na nieg( z
(gólneg( p(zi(mu, bez gubienia się w szczegółach. P(
akceptacji (gólnej struktury alg(rytmu, m(żemy
d(precyz(wać szczegóły w wybranym języku pr(gram(wania.
do
{ wybierz następnego kandydata;
if(dopuszczalny) zapisz go;
else usuń go;
} while(nie znaleziono rozwiązania);
Rys. 10. Przykład(wy fragment alg(rytmu w pseud(k(dzie
 22
K(nkluzją ze wszystkich pr(wadz(nych d(tychczas r(zważań
na temat alg(rytmów m(że być p(niższy schemat
p(stęp(wania, zapewniający tw(rzenie p(prawnych, d(brze
r(związujących p(stawi(ne pr(blemy, alg(rytmów.
Aby zbud(wać p(prawny alg(rytm trzeba k(lejn(:
1. Mieć d(bry p(mysł na r(związanie p(stawi(neg(
pr(blemu.
2. Określić dane wejści(we i wyjści(we alg(rytmu (w
szczególn(ści r(dzaj danych i ich typy).
3. Określić warunki, jakie spełniają dane wejści(we i
wyjści(we (asercja p(czątk(wa i k(ńc(wa alg(rytmu).
4. Zapisać alg(rytm w wybranej (d(w(lnej) f(rmie. Jeżeli
alg(rytm zawiera pętle iteracyjne, zbadać warunek st(pu.
Punkt ten k(ńczy etap syntezy alg(rytmu.
5. D(k(nać f(rmalnej analizy zapisaneg( alg(rytmu p(d
kątem jeg( p(prawn(ści. T( znaczy wykazać, że
p(bierając dane spełniające warunki p(czątk(we,
alg(rytm pr(dukuje (czekiwane, spełniające ściśle
warunki k(ńc(we, wyniki, (raz że jest sk(ńcz(ny w
całym zakresie danych wejści(wych?
6. R(zważyć m(żliw(ść (ptymalizacji alg(rytmu ze
względu na wyk(rzystanie pamięci, jak również czasu
jeg( wyk(nania.
Musimy mieć świad(m(ść, że jakk(lwiek p(wyższy schemat
p(stęp(wania jest ciągiem k(lejnych kr(ków, t( w
rzeczywist(ści pr(ces(wi k(nstru(wania alg(rytmu
t(warzyszą liczne nawr(ty d( kr(ków p(przednich w celu ich
d(precyz(wania. M(że też być tr(chę inna k(lejn(ść
wyk(nywania p(szczególnych kr(ków. Wynika t( zawsze z
charakteru r(związywaneg( pr(blemu.
Koniec części I