Katedra Informatyki
Modele Danych W Językach
Modele Danych: Algorytmy:
Programowania:
" Algorytmy to techniki wykorzystywane do
" Pomoc w formułowaniu rozwiązań dla " Każdy język programowania ma własny
otrzymywania rozwiązań na podstawie
określonych problem ów: grafy, drzewa, model danych.
operacji wykonywanych na danych
listy, zbiory, relacje, automaty sko ńczone,
" Program ma dost ęp do obszaru pami ęci,
reprezentowanych przez abstrakcje modelu
gramatyka, logika
który ma swój typ. W tym obszarze mo żna
danych, struktury danych lub na inne
" W powiązaniu z językami programowania przechowywać dowolne warto ści zgodne z
sposoby.
model danych z łożony jest z okre ślonych tym typem. Te wartości nazywane są
" Algorytm jest precyzyjna i jednoznaczn ą
Algorytmy I Struktury Danych abstrakcji, jak znaki, liczby całkowite o obiektami danych.
specyfikacj ą sekwencji kroków, które mogą
różnych rozmiarach, liczby
" Obszary pamięci mogą mieć nazwy. Nazwy
być wykonane mechanicznie.
zmiennoprzecinkowe.
te są zmiennymi programu.
" Algorytm mo że być wyrażony w formalnym
języku programowania lub nieformalnie 
mieszaninie konstrukcji znanych z j ęzyka
programowania ze stwierdzeniami z języka
naturalnego.
A
ódz
, 2003/2004
Struktury Danych, Modele Danych,
Modele Danych: Modele Danych W Języku Pascal:
Opis Danych
Abstrakcje:
" Statyczna cz ę modelu danych: system ś
Struktury danych to konstrukcje j ęzyka
Do opisu danych s łuż definić sta łych, ą
cje
" Warto ści, które dany obiekt mo że
typów w języku Pascal. Na system typ ów
programowania wykorzystywane do
definicje typów i deklaracje zmiennych.
przyjmować. Statyczny aspekt modelu.
składa si ę zbiór typów prostych i zbi ór
reprezentowania modeli danych (czyli
Konkretne warto ści obiektów, na których
System typ ów.
zasad formu łowania złożonych typów na
abstrakcji wykorzystywanych do opisywania
algorytm dzia ła, są reprezentowane przez
" Operacje na danych. Dynamiczny aspekt podstawie typ ów już znanych.
problemów  abstrakcja oznacza tu
wartości zmiennych oraz przez sta łe. Stałe
modelu. Określa metody wykorzystywane
uproszczenie, zastąpienie skomplikowanych i " Dynamiczna cz ę modelu danych: ś ć
oznacza si ę w tekście programu albo w spos ób
do manipulowania wartościami oraz
szczegółowych okoliczności występujących w operacje w modelu danych w j ęzyku
standardowy, ustalony w j ęzyku
tworzenia nowych warto ści.
świecie rzeczywistym zrozumiałym modelem Pascal  operacje tworz ące i usuwające
programowania, albo za pomoc ą synonim ów
umożliwiającym rozwiązanie naszego obiekt danych, operacje dost ępu i
wprowadzanych na dora z
ne potrzeby
problemu; Oznacza to, że abstrahujemy od modyfikacji czę ci obiektu danych, ś
programu definicjami sta łych. Z ka żdą zmienną
szczegółów, które nie mają wpływu lub mają operacje ł czące wartościąobiektów
w chwili jej deklaracji wią emy identyfikator ż
minimalny wpływ na rozwiązanie problemu; danych w celu sformowania nowej
(nazwę) zmiennej i typ zmiennej, tzn. zbi ór
Opracowanie odpowiedniego modelu wartości obiektu danych.
wartości, jakie ta zmienna może przyjmować.
umożliwia nam zajęcie się istotą problemu)
Typ może być opisany bezpo średnio w
deklaracji zmiennej lub mo że być określony w
definicji typu. W drugim przypadku
wprowadzony w definicji identyfikator typu
może być używany np. w deklaracjach
zmiennych, w opisie parametr ów procedury.
Opis Danych Typy Strukturalne Zmienne Instrukcje
Wyróżnimy dwa rodzaje zmiennych: statyczne i W większości przypadków odpowiedni dobór
Definicja i deklaracja ustala zakres danego Typ strukturalny jest definiowany przez
dynamiczne. Zmienne statyczne s ą to zmienne instrukcji strukturalnych pozwala ca łkowicie
obiektu oraz jego identyfikatora  tzn. podanie typ ów składowych i metody
deklarowane w programie i opatrzone wyeliminować instrukcj ę skoku (jest to jeden z
Fragmenty tekstu programu, w kt órych ten strukturalizacji okre ślającej jednocze śnie
identyfikatorami. Istniej ą one przez ca ły czas postulat ów programowania strukturalnego).
obiekt jest dost ępny poprzez swój mechanizm dost ępu do element ów wartości
Instrukcje strukturalne dziel ą się na instrukcje
realizacji tej czę ci programu, w której są
ś
identyfikator. Dla jednych obiekt ów zakresem strukturalnej. Wyst ępują zwykle cztery rodzaje
złożone, iteracyjne, warunkowe i wi ą ce.
lokalne. Zmienne dynamiczne natomiast mog ą
jest ca ły program (z tym, że w pewnych jego struktur: tablice, rekordy, zbiory i pliki. W
Instrukcja z łożona grupuje sekwencyjnie
być wygenerowane w wyniku realizacji jednej z
czę ciach dany obiekt mo że nie by ć dost ępny, tablicy wszystkie elementy s ą dowolnego, ale
ś
instrukcje sk ładowe (proste lub strukturalne),
instrukcji i nie maj ą jawnych identyfikator ów.
jeżeli jego identyfikator zostanie u żyty do tego samego typu. Dost ęp do elementu
ujmując je w nawiasy zdaniowe. Instrukcje
Wygenerowanie zmiennej dynamicznej
chwilowego oznaczenia innego obiektu). uzyskuje się przez wyznaczenie warto ści
składowe są rozdzielane średnikiem, który to
powoduje jednoczesne utworzenie warto ści
Mówimy inaczej, że obiekty te s ą w programie wyrażenia zwanego indeksem. Typ indeksu
symbol może być w tym kontek ście
zwanej wskaz
nikiem, umożliwiającej dost ęp do
globalne. Zakresem obiektu wprowadzonego w musi być porządkowy i może być określony w
interpretowany jako symbol nast ępstwa.
tej zmiennej. Wska z
niki są wartościami typu
procedurze jest dana procedura, a obiekt taki definicji tablicy. Tablice mogą być
Instrukcja iteracyjna powoduje wielokrotne
wskaz
nikowego. Każda zmienna typu
nazywamy lokalnym w procedurze. wielowymiarowe i wówczas element tablicy
wykonanie pewnej grupy instrukcji. Liczba
wskaz
nikowego jest związana w chwili deklaracji
jest identyfikowany ci ągiem indeks ów. W
Do opisu obiekt ów złożonych u żywane są typy
powtórzeń może, ale nie musi być ustalona a
z pewnym typem i może przyjmować wartości (tj.
rekordzie elementy, zwane polami, mog ą być
strukturalne. Do definiowania typ ów
priori. Zależy ona od warto ści zadanego warunku
Wskaz
niki) wskazuj ące zmienne dynamiczne
różnych typ ów. Identyfikatory p ól podane w
strukturalnych w j ęzyku programowania u żywa
logicznego, sprawdzanego przy ka żdym
tylko tego typu.
definicji typu rekordowego umo żliwiają
się różnych schemat ów strukturalizacji.
powtórzeniu, albo od liczebności określonego
jednoznaczny dost ęp do elementu. Dost ęp ten
podzbioru wartości typu porządkowego.
jest uzyskiwany przez podanie bezpo średnio
identyfikatora.
Typy Danych Typy Strukturalne Instrukcje I Wyra żenia
Instrukcje
Rekord może mieć kilka wariantów, przy czym Instrukcje dziel ą się na proste i strukturalne.
Instrukcja warunkowa powoduje wybranie jednej
Typy danych dziel ą si ę na proste, strukturalne
każdy wariant może mieć różną liczbę pól. Podstawową instrukcj ą prost ą jest instrukcja
z kilku instrukcji i nast ępnie wykonanie jej.
i wskaz
nikowe. Typ prosty sk łada si ę z
Wybrany wariant wskazuje si ę na ogół poprzez przypisania. Instrukcja ta s łuży do nadawania
Sposób wyboru zależy od postaci instrukcji
uporz ądkowanego i skończonego zbioru
wartoś pola wspólnego dla ć wszystkich zmiennej nowej wartości, otrzymanej w wyniku
warunkowej i może być sterowany albo
wartości. W klasie tej wyr óżniamy typ
wariantów, zwanego polem znacznikowym. wartościowania wyrażenia (tj. Wyznaczenia jego
warunkiem logicznym, albo wyrażeniem typu
porządkowy i typ rzeczywisty. Typ porz ądkowy
Elementami typu zbiorowego s ą wszystkie wartości). Kolejną instrukcj ą prost ą jest
porządkowego. Instrukcja wi ą ca dotyczy ż
charakteryzuje si ę tym, że dla wartości tego
podzbiory pewnego typu porz ądkowego, instrukcja procedury. Powoduje ona wywo łanie
zmiennych typu rekordowego. Pozwala ona na
typu (z wyj ątkiem krańcowych) są określone
zwanego typem podstawowym i okre ślanego w odpowiedniej procedury, czyli wykonanie
bardziej przejrzysty i krótszy zapis niektórych
wartości poprzednie i nast ępne. Warto ści
definicji zbioru. Operacje na zbiorach maj ą algorytmu opisanego w deklaracji tej procedury
czę ci programu. Wyra żenia sk ładają się ze
ś
typów prostych s ą oznaczone bądz

charakter teoriomnogo ściowy. Plik reprezentuje dla argument ów określonych parametrami
stałych, zmiennych, operator ów i nazewników
identyfikatorami, b ądz
też  w przypadku
dane przechowywane w pami ęci zewnętrznej o aktualnymi w instrukcji procedury. Pozosta łe
funkcji. Reguły opisuj ące konstrukcj ę wyrażeń
typów standardowych  w konwencjonalnie
dostępie sekwencyjnym. Jako struktura danych dwie instrukcje proste to instrukcja pusta i
zawierają jednocześnie informacje o priorytetach
przyjęty spos ób. Typy standardowe s ą to typy,
jest to ci ąg element ów tego samego typu. instrukcja skoku. Pierwsza z nich nie powoduje
operator ów, tj. O kolejności wykonywania dzia łań.
których si ę w programie nie definiuje,
Przyjmuje się, że w dowolnej chwili mamy dostęp wykonania żadnej czynno ści i jest wprowadzona
Kolejnoś tę można zmieniać, ć stosuj ąc
ponieważ są określone standardowo w języku.
do jednego tylko elementu pliku (sprowadzonego do j ęzyka przede wszystkim w celu ujednolicenia
odpowiednio nawiasy. Operatory dziel ą się na:
Należ do nich: zbi ór liczb całkowitych, zbiór
ą
z pamięci zewnętrznej). Kolejne elementy (oraz opisu pewnych konstrukcji. Instrukcja skoku
arytmetyczne, logiczne, teoriomnogo ściowe oraz
liczb rzeczywistych, zbiór wartości logicznych,
pierwszy) mogą sta ć si ę dost ępne po wykonaniu służy do zmiany normalnego, sekwencyjnego
relacyjne. Warto ś nazewnika funkcji jestć
zbiór znaków dopuszczalnych na urz ądzeniach
odpowiednich operacji na pliku. Liczba porządku wykonywania instrukcji przez
wyznaczana w wyniku wywołania odpowiedniej
zewnętrznych.
elementów pliku jest zmienna. W chwili bezpośrednie wskazanie nast ępnej instrukcji do
funkcji.
utworzenia pliku jest on pusty, a kolejne wykonania.
elementy do ł cza się na końcu pliku.
ą
Symbole I Identyfikatory (Nazwy) Etykiety I Napisy Definicje Stałych I Typów Definicje Typów
Stałe w języku programowania s ą oznaczeniami
Poza określonymi wyjątkami, przy zapisywaniu
Alfabet j ęzyka programowania, czyli zbi ór
Liczby całkowite s ą inaczej reprezentowane w
takich warto ści, jak np. Liczby i napisy. Przyjmuje
programu jest konieczne przestrzeganie
znaków, przy użyciu kt órych zapisuje si ę każdy
komputerze ni ż liczby rzeczywiste. W
się przy tym pewne konwencje sk ładniowe. Język
zasady, że użycie identyfikatora
tekst programu, zawiera litery alfabetu
konsekwencji zarówno liczba cyfr znacz ących, jak
programowania umo żliwia ponadto
niestandardowego powinno by ć tekstowo
łacińskiego, cyfry i symbole specjalne, a w śród
i zakres liczb w obu typach s ą istotnie różne.
wprowadzenie przez programist ę identyfikator ów,
poprzedzone definicj ą tego identyfikatora.
nich określoną liczbę wyrazów angielskich,
Etykiety s łuż do wyróżnienia w programie
ą
które pełnią rolę synonimów stałych
Tablice stanowią najpopularniejsze z łożone
zwanych słowami kluczowymi. Symbole
istotnych instrukcji. Etykieta jest ci ągiem co
(dodatkowych oznacze ń wartości). Używanie
struktury danych wykorzystywane do
językowe są podstawowymi elementami
najwyżej czterocyfrowym. Standardowy typ
synonimów stałych zwi ększa czytelno ś ć
reprezentacji abstrakcyjnych regularnych
składowymi wszystkich konstrukcji j ęzykowych.
znakowy okre śla zbi ór znaków zewnętrznych oraz
programu. Jednocze śnie czyni rozwiązanie
układów danych, np. macierzy. Tablica sk łada
Symbole specjalne s łuż do określenia struktur ą
pojęcie napisu  tj. Ciągu znak ów zewnętrznych
bardziej ogólnym przez jego parametryzacj ę
się z ustalonej liczby element ów tego samego
składniowych j ęzyka. Identyfikatory s łuż do ą
ujętego w apostrofy. Zbi ór znaków zewnętrznych
(ułatwia modyfikacj ę programu i jego
typu zwanego typem sk ładowym. Rekordy
oznaczania program ów, stałych, typów,
nie jest ustalone na poziomie j ęzyka
przystosowanie do potrzeb konkretnego
wykorzystywane s ą do opisu obiekt ów
zmiennych, pól w rekordach, procedur i funkcji
programowania. Znak zewn ętrzny jest elementem
użytkownika). W języku programowania
złożonych, kt órych sk ładowe mają różne
oraz parametr ów formalnych. Powi ązanie
standardowego typu znakowego. Napisy
występuje pojęcie zmiennej. Każdą zmienną
charakterystyki. Rekord sk łada si ę z ustalonej
identyfikatora z oznaczonym przez niego
składające się z pojedynczych znak ów są stałymi
należy w programie zadeklarowa ć, tzn. Określić
liczby element ów zwanych polami, które mogą
obiektem jest jednoznaczne w obszarze
typu znakowego, napisy za ś składające się z n
jej nazwę oraz wartości, które może przyjmować.
być różnego typu.
stanowiącym zakres dzia łania identyfikatora.
znaków (n>1) są stałymi typu napisowego.
Zbiór tych warto ści nosi nazwę typu zmiennej. Z
Identyfikatory mog ą być dowolnej długości.
danym typem s ą związane operacje wykonywane
Wyrazy tworz ące s łowa kluczowe nie mog ą być
na jego wartościach.
używane jako identyfikatory.
Dyrektywy I Liczby Definicje Typów Zgodnoś Typów ć
Separatory
Dyrektywy wyst ępują po nag łówku procedury lub
Typy dzielą si ę na standardowe i
Poprawno ś użycia w danej konstrukcji
ć
funkcji. Używa się ich do zastąpienia bloku
Komentarze, odst ępy (spacje i tabulatory) i
niestandardowe, w zależności od tego, czy
językowej obiektu takiego, jak identyfikator,
procedury lub funkcji. Liczby w j ęzyku
przejścia do nowego wiersza nazywamy
odpowiednie zbiory warto ści są określone
stała, zmienna lub funkcja zale ży na ogół od typu
programowania zapisuje się w sposób zbliżony
separatorami. Komentarze to ci ąg dowolnych
standardowo w j ęzyku, czy te ż są wprowadzone
tego obiektu. W j ęzyku programowania s ą
do konwencjonalnej notacji matematycznej, z
znaków ograniczony wyr óżnionymi w języku
w konkretnym programie tylko na jego dora z
ny
zdefiniowane poj ęcia zgodności typu i zgodności
następującymi różnicami: cz ę całkowitą ś ć
programowania znakami. Komentarze nie
użytek. Dla typ ów standardowych j ęzyk
wartości typu w sensie przypisania.
oddzielamy od cz ę ci ułamkowej kropką, a nie
ś
wpływają na przebieg oblicze ń i mają na celu
programowania ustala ich nazwy
przecinkiem, dla liczb o małej liczbie cyfr
wył cznie zwiększą czytelno ści programu i
enie
(identyfikatory), spos ób oznaczenia
znaczących i jednocze śnie bardzo małym (lub
ułatwienie zrozumienia jego tre ści. Między dwa
poszczególnych wartości oraz dopuszczalne
dużym) module, wprowadzono skrócony zapis,
symbole j ęzyka (lub przed pierwszym symbolem
operacje. Wprowadzaj ąc nowy typ
korzystaj ąc z tzw. Mno żnika skaluj ącego. W
programu) mo żna wstawić dowolną liczbę
niestandardowy programista sam okre śla
konwencji matematycznej zapis taki jest
separator ów. Dowolne dwa symbole b ędące
odpowiedni zbiór wartości poprzez opis typu.
wyrażeniem, a nie liczb ą. Liczby s łuż do ą
identyfikatorami, liczbami, s łowami kluczowymi
Opis taki może być używany bezpo średnio w
oznaczania wartości typów standardowych: liczba
muszą być rozdzielone co najmniej jednym
deklaracji zmiennej bez uprzedniego nadania
całkowita, liczba rzeczywista. Litera  e
separatorem. Wewn ątrz symboli języka nie
typowi nazwy, albo mo że być wprowadzany w
występująca przed mno żnikiem skalującym
można umieszczać separator ów.
definicji typu. Definicja typu umo żliwia podanie
oznacza:  razy 10 do pot ęgi . Typ liczby jest
opisu typu i nadanie mu identyfikatora.
określony przez spos ób jej zapisu, 345 jest liczb ą
Zwiększa to czytelno ś programu i u łatwia jego ć
typu całkowitego, 345.0 lub 345E6 s ą liczbami
parametryzacj ę. Każde wystąpienie nowego
typu rzeczywistego.
typu oznacza typ r óżny od dotychczas
wprowadzonych w programie, mimo że wartości
w odpowiednich zbiorach mogą być identyczne.
Zmienne Zasłanianie Wyrażenia Instrukcja Procedury
Wyróżnimy: zmienne ca łościowe (zapisywane za Obiekty nielokalne w bloku procedury s ą Wyrażenie jest konstrukcj ą językową Instrukcja procedury powoduje wykonanie
pomocą identyfikatora), sk ładowe (element dostępne przez swoje identyfikatory. Je żeli oznaczającą wartoś pewnego typu . ć czę ci programu wyodrębnionej w postaci
ś
tablicy, pole rekordu), wskazywane (przez skorzystamy jednak z identyfikatora identycznego Wyznaczenie tej warto ści odbywa się przez deklaracji procedury (instrukcji wewn ętrznych
wskaz
niki), buforowe (związane ze zmiennymi z pewnym identyfikatorem nielokalnym do wartościowanie wyrażenia, tj. wykonanie procedury). Po zako ńczeniu realizacji
plikowymi). Deklaracja zmiennej okre śla oznaczenia obiektu lokalnego, to identyfikator ten operacji wskazanych przez wyst ępujące w procedury wykonywana jest instrukcja
staje się lokalny w danym bloku i tym samym wyrażeniu operatory na zadanych
identyfikator, za pomoc ą którego będziemy następna po danej instrukcji procedury. W
obiekt nielokalny o tym samym identyfikatorze argumentach . Wyrażenie jest zbudowane ze
odwoływać się do zmiennej oraz typ jej warto ści. przypadku procedur bezparametrowych w
przestaje by ć dostępny. Mówimy wówczas o stałych, zmiennych, operator ów, nazewników
W celu skr ócenia zapisu mo żna zadeklarowa ć zapisie instrukcji procedury wyst ępuje jedynie
zasłonięciu obiektu nielokalnego przez obiekt funkcji , zbiorów i nawias ów okrągłych.
kilka zmiennych tego samego typu w postaci identyfikator. W przeciwnym wypadku nale ży
lokalny. Warto ściowanie wyrażenia będącego sta ł , ą
jednej deklaracji. W zapisie zmiennej sk ładowej podać dodatkowo argumenty, tj. parametry
zmienną lub identyfikatorem granicznym
występuje oznaczenie zmiennej oraz oznaczenie aktualne.
sprowadza si ę do wyznaczenia warto ści stałej,
selektora, kt órego warto ś wybiera odpowiedni ą ć
zmiennej lub identyfikatora granicznego .
czę zmiennej. Zmienne wskazywane (inaczej  ć
ś
Warto ściowanie konstruktora zbioru
dynamiczne) istniej ą (są dost ępne) od chwili ich
sprowadza się do wartościowania kolejnych
utworzenia do chwili zakończenia wykonywania
jego elementów i utworzenia zbioru z łożonego
programu lub do chwili ich unicestwienia za
z obliczonych wartości. Reguły opisujące
pomocą odpowiedniej procedury. Dost ępnoś ć
konstrukcj ę wyrażeń zawierają jednocze śnie
zmiennej dynamicznej zale ży od istnienia
informacje o priorytetach operator ów, tj. o
zmiennej wskaz
nikowej, której wartoś wskazuje ć
kolejności wykonywania działań.
na tę zmienną dynamiczn ą.
Umowny Język Instrukcja Przypisania
Efekty Uboczne Instrukcja Pusta
We wprowadzonym na potrzeby niniejszego Instrukcje przypisania wykorzystywane s ą do
W bloku procedury mog ą występować obiekty Instrukcja pusta nie powoduje wykonania
wykładu umownym języku programowania zmiany wartości zmiennych (funkcji ). Zmiennej
nielokalne, a w szczególności obiekty nielokalne. żadnych czynno ści. Istnienie instrukcji pustej
strukturalnego b ędziemy zakładać istnienie zostaje nadana nowa warto ś otrzymana w ć
W takiej sytuacji procedura komunikuje si ę z jest usprawiedliwione syntaktyk ą programu.
nazw typów strukturalnych, sposobu wyniku wartościowania wyrażenia. Wartoś ć
otoczeniem nie tylko przez parametry, ale i przez
oznaczenia poszczeg ólnych warto ści i wyrażenia musi być zgodna w sensie
te nielokalne obiekty. Mo żliwe jest oczywi ście
dopuszczalnych operacji. Podamy przypisania z typem zmiennej (funkcji). Jeżeli
nadawanie nowych warto ści zmiennym
typ zmiennej jest różny od typu wyrażenia,
jednocześnie schematy definiowania typ ów
nielokalnym. Jest to powszechnie nazywane
wówczas przed dokonaniem przypisania
strukturalnych w Pascalu.
efektem ubocznym tej procedury, co ma
następuje automatyczna konwersja z typu
podkre ślić nietypowoś tego rozwiązania. Na ogół ć
wyrażenia do typu zmiennej . Zasady
nie zaleca si ę stosowania efekt ów ubocznych w
automatycznej konwersji s ą ściśle określone w
funkcjach.
języku programowania . Nie jest dozwolone
przypisywanie wartości wszystkich typów.
Procedury I Funkcje Procedury I Funkcje Wybór  Wariant 1 Iteracja Ograniczona
Instrukcja wyboru wybiera jedną z dwóch akcji ,
Procedura jest opisem algorytmu z Realizację procedury , czyli jej wywołanie Iteracja ograniczona wykonuje akcj ę określoną
a następnie j ą realizuje, przykładowo (IF x
iloś razy, przykładowo: ( FOR i:=min TO max
ć
przyporz ądkowanym mu identyfikatorem, za powoduje instrukcja procedury . W instrukcji
THEN a ELSE b;) gdzie x jest wyrażeniem
DO a); gdzie i to zmienna indeksowa
pośrednictwem którego można się do tego tej podaje si ę identyfikator procedury oraz
logicznym, natomiast a, b to instrukcje
przyjmująca warto ści z przedziału od min do
algorytmu odwo łać i spowodować jego ewentualnie parametry aktualne . elementarne.
max, a to akcja.
wykonanie dla okre ślonych argument ów.
Jeżeli procedura mia ła na celu wyznaczenie
Algorytm ten jest zapisywany na og ół w
jednej warto ści typu prostego lub
postaci sparametryzowanej, tj. przy u życiu
wskaz
nikowego, to taką procedur ę nazywa się
pomocniczych nazw zwanych parametrami
funkcj ą, a jej deklarację  deklaracj ą funkcji.
formalnymi. Bezpośrednio przed rozpocz ęciem
Wywołanie funkcji odbywa si ę za pomocą
realizacji procedury parametry formalne s ą
instrukcji lub w wyrażeniach , w których
zastępowane obiektami z otoczenia procedury,
chcemy skorzysta ć z wartości funkcji. Podaje
tzw. parametrami aktualnymi. Parametry
się wówczas nazewnik funkcji , który okre śla
aktualne pe łnią więc rolę argument ów
wartoś pewnego typu . ć
algorytmu.
Procedury I Funkcje Instrukcje W Algorytmach Iteracja Warunkowa  Wariant 1
Wybór  Wariant 2
Instrukcja wyboru wybiera jedną z wielu akcji, a
Iteracja warunkowa wykonuje akcj ę
Opis procedury wyst ępuje w programie w Algorytm zawiera instrukcje elementarne, kt óre
następnie ją realizuje , przykładowo (CASE x OF
wielokrotnie tak d ługo, jak długo spe łniony jest
postaci deklaracji procedury. W deklaracji tej wykonuj ą akcje podstawowe algorytmu i
x1: a1; x2: a; xn: an; ELSE a; END;), gdzie x jest
warunek, przykładowo (WHILE x DO a;), gdzie x
podaje si ę zarówno przyporz ądkowany instrukcje steruj ące, które steruj ą kolejnością
wyrażeniem, a1, a2, an to instrukcje.
jest wyrażeniem logicznym , a to instrukcja .
algorytmowi identyfikator oraz ewentualne ich wykonania. W śród instrukcji steruj ących,
.
parametry formalne (nag łówek procedury), jak nazywanych te ż strukturami przep ływu
i sam algorytm (blok procedury). Procedura, sterowania lub strukturami steruj ącymi,
wyróżnimy: nast ępstwo, wybór i iterację (pętlę
która nie ma parametr ów, komunikuje się z
lub zwrot pętlący). Jak pami ętamy z
otoczeniem poprzez obiekty nielokalne, tzn.
pierwszego wykładu, średnik ko ńczący
zdefiniowane lub zadeklarowane na zewn ątrz
instrukcję w Pascalu może by ć interpretowany
tej procedury. Niekiedy do opisu algorytmu
jako symbol nast ępstwa. Pętle występują w
użyteczne s ą pewne robocze obiekty,
wielu odmianach. Wyr óżnimy: iteracj ę
określone dora z
nie. Tego rodzaju obiekty
ograniczoną (wykonaj A dokładnie N razy),
wprowadza się definicjami i deklaracjami w
iterację warunkową (nieograniczon ą  wykonaj
samym bloku procedury i nazywa obiektami
A aż do Q lub dop óki Q, wykonaj A, gdzie Q to
lokalnymi.
pewien warunek).
Abstrakcyjny typ danych
Iteracja Warunkowa  Wariant 2 Diagramy Przepływu Sterowania Przykładowy Program
Abstrakcyjny typ danych (ATD) to typ
danych, dla którego operacje nie zależ
Jedną z metod przedstawiania przep ływów program abc;
Iteracja warunkowa wykonuje akcj ę
od jego szczególnych własności.
wielokrotnie tak d ługo, aż zostanie spełniony sterowania w algorytmie w przejrzysty i
var licznik: array['a'..'z'] of integer ;
Podstawą ATD jest oddzielenie operacji
warunek, przykładowo (REPEAT a UNTIL x;),
czytelny spos ób jest sporz ądzanie diagram ów
litery: set of 'a'..'z';
wykonywanych na danych i sposobów ich
gdzie x jest wyrażeniem logicznym , a to
(schemat ów blokowych). Istnieją rozmaite
zn: char;
instrukcja .
przechowywania od konkretnego typu
sposoby rysowania diagram ów. Najczę ciej ś
begin
instrukcje elementarne zapisuje si ę w ramkach danych. ATD można zdefiniować za
litery := ['a'..'z'];
prostok ątnych, a testy  w kszta łtach rombu.
pomocą operacji, które są wykonywane
Strzałki służ do opisania działań algorytmu.
ą
for zn:='a' to 'z' do
na danych, niezależnie od ich typu.
licznik[zn] := 0;
Zastosowania ATD umożliwia podzielenie
while not eof do
zadania programistycznego na dwie
begin
czę ci. Pierwsza polega na ś
while not eoln do
zaimplementowaniu ATD; wyborze
begin
struktury reprezentującej ATD i napisaniu
read(zn);
funkcji implementujących operacje. Druga
if zn in litery then
czę to napisanie programu głównego,
ś
licznik[zn]:=licznik[zn]+1;
który będzie wywoływał funkcje ATD.
end;
Program ma dostęp do danych ATD
readln;
wył cznie przez wywoływanie funkcji; nie
ą
end;
może bezpośrednio odczytywać lub
end.
modyfikować wartości przechowywanych
w wewnętrznych strukturach ATD.
Abstrakcyjny typ danych
Katedra Informatyki
Składanie Instrukcji Sterujących
Przykładowy Program
Przez odseparowanie implementacji ATD
od jego użycia dzielimy problem
Następstwo, wybór, iteracja mog ą być
program abc;
poprzeplatane i zagnie żdżane w sobie. programistyczny na dwa niezależne
const n=10;
Przykładowo, mogą występować pętle
zadania. Ponieważ program główny nie
type cyfra = 0..9;
zagnieżdżone (iteracje zagnie żdżone) postaci:
var może sięgać do struktur danych ATD
wykonaj A dok ładnie N razy, gdzie A samo jest
i, k, r: integer;
bezpośrednio, a jedynie przez wywo łanie
postaci: wykonaj B a ż do Q. Algorytm
d: array[1..n] of cyfra;
funkcji z interfejsu, b ędziemy mogli w
wykonuje A realizując pętlę zewnętrzną i B
Algorytmy i struktury danych
begin
wykonuj ąc pętlę wewnętrzną. przyszłości zmienić implementację ATD,
for k:=1 to n do begin
pozostawiając program główny nietknięty.
write('.'); kolejka, stos
Z drugiej strony, implementacja ATD jest
r:=0;
oderwana od jego użycia, zatem ten sam
for i:=1 to k-1 do begin
ATD można wł czyć do wielu r
ąóżnych
r:=10*r + d[i];
programów bez żadnych zmian. Jednym z
d[i]:=r div 2;
głównych celów programisty powinno by ć
r:=r - 2*d[i];
write(chr(d[i]+ord('0'))) utworzenie zestawu efektywnych,
end; bezbł dnych ATD, które będzie wł czał do ą
ę
d[k]:=5;
pisanych przez siebie programów.
writeln('5');
end;
end.
A
ódz
, 2003/2004
Funkcje operujące na stosie (2)
Implementacje stosu:
Operacje wykonywane na kolejce:
Definicja stosu:
4 4 4
Stos to liniowa struktura danych, " FUNCTION pop (var top: integer;
3 15 3 3
dostępna do zapisywania i 15 2 -11 2 15 2 stos: StackType ): ElType; enq 10 10
-11 1 0 1 -11 1
odczytywania tylko z jednego
" Begin
3 0 0 4 0 3 0 0
enq 5 5 10
końca. Stos można zdefiniowa ć za
" if (empty(stos)=TRUE ) then
stos
pomocą następujących operacji,
15 -11 0 deq 5
" begin
/
które zmieniają lub sprawdzają jego
stos
" write( Niedobór na stosie ); enq 15 15 5
stan:
" pop := 999;
" Initialize (stos)  powoduje 15 -11 0
enq 7 7 15 5
/
opróżnienie stosu " end
deq 7 15
" Empty (stos)  powoduje " else begin
" PROCEDURE initialize (var top: integer);
sprawdzenie, czy stos jest pusty
" top := top  1;
" Begin last first
" Full (stos)  powoduje sprawdzenie,
" pop := stos[top];
" top := 1; 8 6 10 11 15 2 4
czy stos jest zape łniony
" End; last first
" end
" Push (el, stos)  powoduje
" FUNCTION empty(top: integer): boolean; 11 15 2 4 8 6 10
" End;
umieszczenie elementu el na stosie
" Begin first
last
" Pop (stos)  powoduje zdjęcie " empty := (top = 1);
4
2 8
najwyższego elementu ze stosu " End;
15 6
11 10
Funkcje operujące na stosie (1)
Definicja kolejki:
Ciąg operacji wykonywanych na stosie:
Implementacje kolejki:
" Const Max=50;
" FUNCTION full(top: integer): boolean;
Kolejka to liniowa struktura danych,
" type ElType=integer;
" Begin
dostępna do zapisywania i odczytywania z
" StackType = array [1..Max] of ElType ;
" full := (top = Max+1);
obu końców. Kolejkę można zdefiniować
last first
" Var Top: integer;
" End;
za pomocą następujących operacji, które
8 4 2
Stack: stackType;
zmieniają lub sprawdzają jej stan:
enq(6)
" PROCEDURE push(el: ElType ; var top:
" Initialize (kolejka)  powoduje first last
integer; var stos: StackType );
opróżnienie kolejki
8 4 2 6
push 10 10
" Begin
" Empty (kolejka)  powoduje sprawdzenie, last first
" if (full(top)=TRUE) then
czy kolejka jest pusta 8 4 2
5
" write( Przepełnienie stosu )
push 5 10
" Full (kolejka)  powoduje sprawdzenie, enq(6)
last first
" else begin
czy kolejka jest zape łniona
6 8 4 2 6
pop 10
" stos[top] := el;
" enq (el, kolejka)  powoduje umieszczenie
" top := top + 1;
elementu el na końcu kolejki
15
" end
" deq (kolejka)  powoduje usuni ęcie
push 15 10
" End;
pierwszego elementu z kolejki
7
push 7 15
10
15
pop 10
Funkcje operujące na kolejce: Przykład Przykład
Implementacje kolejki:
first
Kolejki wykorzystywane są w różnych
" PROCEDURE initialize(Q: QType );
symulacjach. W procesach kolejkowych Liczba Procent Zakres
2
" Begin
mamy pewną liczbę klientów, klientów przedziałó
4
" Q[1].first := 0; Q[1].last := 0;
8 zgłaszających się do usługodawców na minutę w
last
" End; świadczących usługi. Możliwości jednominu
wykonania usługi są ograniczone, dlatego towych
" FUNCTION empty(Q: QType ):
enq(6)
klienci muszą czekać w kolejkach., zanim
0 15 1-15
first boolean;
zostaną obsłużeni. Rozważmy przykład
1 20 16-35
" Begin
2 Banku Głównego, który przez trzy
4 " empty := (Q[1].first = 0); 2 25 36-60
miesiące notował liczbę odwiedzających
8
go klientów i czas potrzeby do ich obsługi.
" End;
3 10 61-70
6
Obecnie zatrudnionych jest sześciu
last " FUNCTION full(Q: QType ):
4 30 71-100
urzędników i nie tworz ą się kolejki. Zarz ąd
boolean;
banku chciałby wiedzieć, czy sześ osób ć
" Type Qstorage = record
" Begin
to nie za dużo. Aby odpowiedzieć na to Liczba klientów przybywających w
" first, last: integer; " full := (Q[1].first = 1 AND Q[1].last = Max) pytanie, napisano program symulacyjny, przedziałach jednominutowych
" OR wykorzystujący nagromadzone dane i
" storage: array [1.. Max] of integer;
" (Q[1].first = Q[1].last+1);
sprawdzający różne scenariusze.
" End;
" End;
" Qtype =array [1..Max] of Qstorage;
" Var Q: Qtype ;
Funkcje operujące na kolejce: Funkcje operujące na kolejce Przykład
Przykład
Czas Procent Zakres
" FUNCTION deq(Q: QType ): integer;
" PROCEDURE enq(el: integer, Q: QType ); Liczba klientów zalezy od losowo
obsługi w klientów
" var tmp: integer;
" Begin wygenerowanej wartości zawartej mi ędzy
sekundach
" begin
1 a 100. Wyróżniono pię zakresów liczb ć
" if (full(Q)=TRUE) then write( Przepełniona )
0 0 -
od 1 do 100, odpowiadających liczbie
" if (empty(Q)=false) then begin
" else
klientów (0-4) przychodzących do banku w 10 0 -
" tmp := Q[1].storage[Q[1].first];
" BEGIN
przedziałach jednominutowych. Jeśli
" if (Q[1].first=Q[1].last) then 20 0 -
" if(Q[1].last=Max OR Q[1].last=0) then
wylosowana liczbą jest 21, to liczba
" begin
30 10 1-10
" begin
klientów wynosi 1; je śli 90, to liczba
" Q[1].last := 0;
" Q[1].storage[1] := el; 40 5 11-15
klientów wynosi 4. W ten spos ób symuluje
" Q[1].first = 0;
" Q[1].last := 1;
się szybkoś przybywania klientów do ć 50 10 16-25
" end
" if (Q[1].first = 0) then Q[1].first := 1; banku.
60 10 26-35
" else
" end
Oprócz tego analiza zgromadzonych
70 0 -
" if (Q[1].first = Max) then
" else begin danych wykazała, że w ciągu 10 lub 20
80 15 36-50
" Q[1].first := 1
" Q[1].last := Q[1].last + 1; sekund nie można obsłużyć żadnego
90 25 51-75
" else Q[1].first:= Q[1].first + 1;
klienta. 10% spraw za łatwia się w ciągu 30
" Q[1].storage[Q[1].last] := el;
" deq := tmp; sekund, itd.. 100 10 76-85
" end;
" end
110 15 86-100
" END
" else write( Kolejka jest pusta );
" End;
Czas obsługi klienta podany w
" End;
sekundach
Przykład Przykład
Function option(percents: tab1): integer;
Program korzysta z trzech tablic. W tablicy
Var
i: integer;
arrivals przechowuje się udziały okresów
choice: integer;
jednominutowych w zależności od liczby
perc: integer;
przybywających klientów. W tablicy
Begin
service jest zapamiętany rozkład czasu
i := 0;
obsługi. Czas otrzymuje si ę, mnoż c ą choice := random(100)+1;
perc = percent[1];
indeks danej komórki tablicy przez 10. Np.
while (percservice[3] wynosi 10, co oznacza, że w
begin
10% przypadków obsługa klientów
perc := perc + percents[i+1];
wymaga 3*10 sekund. W tablicy clerks i:= i+1;
end;
umieszcza się czas obsługi w sekundach.
option:=i;
End;
Przykład
Program bank;
Uses libQue;
Const clerksize = 5;
Type
tab1 = array[1..5] of integer;
tab2 = array[1..12] of integer;
Const
arrivals: tab1 = {15, 20, 25, 10, 30};
service: tab2 = {0, 0, 0, 10, 5, 10, 10, 0, 15, 25, 10, 15};
clerks: tab1 = {0, 0, 0, 0, 0};
Var
customers, i, t: integer;
Begin
for t:=1 to 100 do {symulacja 100 minut} begin
write(t);
for i:=1 to clerksize do
if clerks[i] < 60 then
clerks[i] := 0
else clerks[i]:=clerks[i]-60;
customers:=option(arrivals);
for i:=1 to customers do
enq(option(service)*10);
i:=1;
while (i< clerksize and empty=0) do
if clerks[i]<60 then
clerks[i] := clerks[i]+deq
else i:=i+1;
Scanq;
end;
End.