QPrint

Plik zawiera materiał ilustracyjny do wykładu:
(szczegół(we (mówienie zagadnień z przykładami
p(dane będzie w trakcie wykładu)

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

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.

Studia za(czne

Nazwa przedmi(tu: Algorytmy i złożoność

Egz.

Liczba g(dzin: 27 godz. wykładu +
24 godz. ćwiczeń audyt(ryjnych

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

rekurencją.

Rekurencja

iteracja.

Rekurencyjne typy danych.

6. Typ wskaźnikowy. Al(kacja dynamiczna i nie

dynamiczna

zmiennych.

Pr(gram(wanie

wyk(rzystaniem struktur dynamicznych.

7. Listy liniowe. Alg(rytmy (bsługi list lini(wych.

Dynamiczne

LIFO-st(sy

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

Literatura uzupełniająca:

1. Dr(zdek A.: C++ Algorytmy i struktury danych, Heli(n,

2004

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).

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.

Typ

Oznaczenie

typu

Rozmiar

Przykład

danej

Podstawowe

operacje

całk(wity

int

2 bajty

- arytmetyczne
całk(wit(liczb(we,
- l(giczne,
- przyrównania

rzeczywisty

float

4 bajty

13.0

- arytmetyczne
zmienn(p(zycyjne,
- przyrównania

Znak(wy

char

1 bajt

‘A’

jak całk(wite

wskaźnik(wy

typ

∗∗∗∗

2 bajty

adres w

pamięci

- arytmetyka
adresów,
- przyrównania

Tabela 1. P(równanie najważniejszych typów pr(stych
języka C/C++

Dana

(literał)

Typ

Implementacja

int Stał(p(zycyjna

1.0

float Zmienn(p(zycyjna

‘1’

char k(d ASCII znaku 1, tzn. 49

”1”

string

tablica znak(wa
dwuelement(wa

49 0

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.

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 wskaź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.

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

pamięci

(peracyjnej, p(ł(ż(ne w k(lejnych
(bszarach pamięci, wszystkie teg(
sameg( typu

Bezp(średni, p(przez
wart(ść indeksu, lub
wart(ść wskazania

Rekord

Opis typu

Dostęp do składowych

Dane

al(k(wane

pamięci

(peracyjnej, p(ł(ż(ne w k(lejnych
(bszarach pamięci różnych typów

Bezp(średni, p(przez
nazwę p(la rek(rdu

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).

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.

indeksy 0 1 2 3 4
wart(ści

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ć.

4 -1 7 0 2

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

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

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.

( parametry, dane
skład(we, p(la)

(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

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

k(nieczn(ści

implement(wania

całeg(

szeregu

struktur

danych

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.

Nazwa klasy

Atrybuty klasy

Met(dy klasy

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ć)

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,.

Dane
wejściowe

Alg(rytm

Dane
wyjściowe

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)   b)

Rys. 5. Pr(blem niejedn(znaczn(ść alg(rytmu:
a) alg(rytm z punktem węzł(wym W pr(wadzącym d(

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
I

fałsz
W fałsz
  prawda W
prawda
I

a) b)
  while ( W ) I ; do { I } while ( W ) ;

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

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óź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

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

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ć

sp(sób

wyraźnie

zamierz(ny

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.

wartości wynik
parametrów

Rys.8 Schemat k(munikacji funkcji z (t(czeniem

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.

zmienne
nielokalne

algorytm (funkcja)

zmienne lokalne

efekty
uboczne

zmienne

lokalne

funkcji

f 3

zmienne

lokalne

III

funkcji

f 2

zmienne

globalne

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:

zmienne globalne

funkcja f 1

funkcja f 2

funkcja f 3

wskaźnik stosu

Zdarzenie

Skutki na stosie

1. Załad(wanie m(dułu
pr(gram(weg(

Przydział pamięci dla zmiennych
gl(balnych

2. Wyw(łanie funkcji f2

Przydział pamięci dla zmiennych
l(kalnych funkcji f2

3. Wyw(łanie funkcji f1 z
wnętrza funkcji f2

Przydział pamięci dla zmiennych
l(kalnych funkcji f1 na szczycie
st(su

4. Wyk(nanie się funkcji f1
i p(wrót ster(wania d(
funkcji f2

Zw(lnienie pamięci zmiennych
l(kalnych funkcji f1 (zdjęcie ich
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

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ń

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  znaleźć  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

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