1
PS/TP
TI
TI
TI
TI----PS
PS
PS
PS----0
0
0
0----
WST
Ę
P
PROGRAMOWANIE STRUKTURALNE
PROGRAMOWANIE STRUKTURALNE
PROGRAMOWANIE STRUKTURALNE
PROGRAMOWANIE STRUKTURALNE
2
PS/TP
000 -
PROGRAMOWANIE STRUKTURALNE
TECHNIK INFORMATYK 312[01]
PROGRAM NAUCZANIA: 312[01]/T,SP/MENIS/2004.06.14
Przedmiot: Programowanie strukturalne i obiektowe
dla technikum 4-letniego
3
PS/TP
PROGRAMOWANIE STRUKTURALNE
LITERATURA POMOCNICZA:
•Wiesław Por
ę
bski. PASCAL. Wprowadzenie do programowania. Wyd. 5. HELP.
•Andrzej Marciniak. Turbo Pascal 5.5. wyd. II poprawione i uzupeł. Nakom Pozna
ń
1993.
•Gra
ż
yna Koba. Informatyka dla liceum ogólnokształc
ą
cych. Cz. 1. Wydawnictwo MIGRA
•Gra
ż
yna Koba. Informatyka dla liceum ogólnokształc
ą
cych. Cz. 2. Wydawnictwo MIGRA
•Borland TP7 “User’s Guide”
•Borland TP7 “Language Guide”
•Borland TP7 “Programmer’s Reference”
•N. Wirth „Algorytmy + struktury danych = Programy”, WNT
4
PS/TP
PROGRAMOWANIE STRUKTURALNE
Polecane
ś
rodowiska programowania j
ę
zyków Pascal, C++, Java:
Free Pascal Compiler
Borland Delphi 7.0
Borland C++ Builder 6.0 Personal Edition
Borland JBuilder
5
PS/TP
PROGRAMOWANIE STRUKTURALNE
Nauka tego przedmiotu, oprócz poznawania technik programowania,
doskonali znajomo
ść
j
ę
zyka angielskiego poprzez korzystanie z wersji
angielskiej oprogramowania oraz z dokumentacji technicznej napisanej w
j
ę
zyku angielskim.
Podczas projektowania programów b
ę
dziesz:
o uczył si
ę
odczytywania ze zrozumieniem instrukcji,
o wydawania polece
ń
w j
ę
zyku angielskim,
o tłumaczenia na j
ę
zyk polski angielskich tekstów
Programowanie jest umiej
ę
tno
ś
ci
ą
przede wszystkim
praktyczn
ą
, dlatego
zdecydowan
ą
wi
ę
kszo
ść
czasu musisz po
ś
wieci
ć
na samodzielne
programowanie na zaj
ę
ciach i w domu.
Niezb
ę
dne informacje znajdziesz w plikach w formacie PDF.
6
PS/TP
PROGRAMOWANIE STRUKTURALNE
BEZ MATEMATYKI
NIE MA
INFORMATYKI
7
PS/TP
PROGRAMOWANIE STRUKTURALNE
Cele kształcenia – ucze
ń
powinien umie
ć
:
1. scharakteryzowa
ć
budow
ę
i zasad
ę
działania programu
2. komputerowego,
3. wyja
ś
ni
ć
podstawowe poj
ę
cia zwi
ą
zane z programowaniem,
4. zastosowa
ć
podstawowe algorytmy i sposoby ich zapisu,
5. posłu
ż
y
ć
si
ę
edytorem, kompilatorem, debugerem oraz dokumentacj
ą
6. j
ę
zyka programowania,
7. zastosowa
ć
czytelny styl programowania i opracowa
ć
dokumentacj
ę
8. programu,
9. zlokalizowa
ć
i usun
ąć
bł
ę
dy w programach, przetestowa
ć
programy,
10. zastosowa
ć
podstawowe typy danych, stałe, zmienne i funkcje,
11. zaprojektowa
ć
wyra
ż
enia z operatorami arytmetycznymi, logicznymi
12. oraz relacji,
13. zastosowa
ć
w programach instrukcje: proste, zło
ż
one, steruj
ą
ce oraz
14. iteracyjne,
15. posłu
ż
y
ć
si
ę
podprogramami: własnymi i standardowymi z biblioteki,
8
PS/TP
PROGRAMOWANIE STRUKTURALNE
16. zaplanowa
ć
podział zadania/problemu na moduły,
17. zastosowa
ć
strukturalne typy danych: tablice, pliki, zbiory, rekordy,
18. posłu
ż
y
ć
si
ę
wska
ź
nikami do budowy dynamicznych struktur danych:
stosów, kolejek, list, drzew, grafów,
16. wykorzysta
ć
w programach d
ź
wi
ę
ki, grafik
ę
, animacje,
17. zaprojektowa
ć
programy współpracuj
ą
ce z systemem operacyjnym,
18. zaprojektowa
ć
programy odporne na bł
ę
dne dane,
19. wyja
ś
ni
ć
ró
ż
nice pomi
ę
dzy programowaniem strukturalnym
i obiektowym,
16. scharakteryzowa
ć
poj
ę
cia dotycz
ą
ce programowania obiektowego:
obiekt, klasa, metoda, atrybut,
16. zastosowa
ć
podstawowe konstrukcje j
ę
zyka obiektowego,
17. zaprojektowa
ć
klasy i moduły, zastosowa
ć
hermetyzacje,
18. posłu
ż
y
ć
si
ę
konstruktorem i destruktorem,
19. zastosowa
ć
dziedziczenie, funkcje wirtualne, zaprzyja
ź
nione,
operatorowe,
20. zaprojektowa
ć
aplikacj
ę
typu SDI oraz MDI,
9
PS/TP
PROGRAMOWANIE STRUKTURALNE
21. zaprojektowa
ć
program o charakterze obliczeniowym, graficznym,
22. zaprojektowa
ć
aplikacje sieciowe, bazodanowe,
23. wyja
ś
ni
ć
przeznaczenie i wła
ś
ciwo
ś
ci apletów,
24. zaprojektowa
ć
aplikacje współbie
ż
ne, wielow
ą
tkowe,
25. wykona
ć
zło
ż
ony system informatyczny pracuj
ą
c w zespole,
26. zmodyfikowa
ć
kod
ź
ródłowy zapisany w j
ę
zyku programowania,
27. zaprojektowa
ć
programy dla
ś
rodowiska Windows,
28. skorzysta
ć
z informacji na temat programowania, zgromadzonych
29. w sieci Internet oraz w innych
ź
ródłach,
30. posłu
ż
y
ć
si
ę
angielsk
ą
terminologi
ą
dotycz
ą
c
ą
tematyki zawodowej.
10
PS/TP
PROGRAMOWANIE STRUKTURALNE
1. WPROWADZENIE DO PROGRAMOWANIA STRUKTURALNEGO
W PASCALU
Podstawowe poj
ę
cia dotycz
ą
ce programowania:
•program komputerowy,
•j
ę
zyki programowania,
•kompilator,
•interpretator,
•konsolidator.
Algorytmy i sposoby ich zapisu.
Etapy tworzenia programu:
•planowanie,
•pisanie,
•kompilacja,
•konsolidacja,
•testowanie
•optymalizacja.
11
PS/TP
PROGRAMOWANIE STRUKTURALNE
Zasady programowania strukturalnego.
Edytor
ś
rodowiska systemu Pascal.
Podstawy zapisywania programu w j
ę
zyku Pascal:
•słowa kluczowe,
•identyfikatory,
•liczby,
•symbole podstawowe,
•komentarze,
•stałe logiczne.
12
PS/TP
PROGRAMOWANIE STRUKTURALNE
Typy danych:
•całkowity,
•rzeczywisty,
•znakowy,
•ła
ń
cuchowy,
•logiczny,
•okrojony,
•wyliczeniowy.
Struktura programu w j
ę
zyku Pascal.
Instrukcje wej
ś
cia/wyj
ś
cia.
Deklaracje zmiennych i stałych.
13
PS/TP
PROGRAMOWANIE STRUKTURALNE
Instrukcja przypisania.
Wyra
ż
enia i operatory.
Standardowe funkcje i procedury.
Instrukcje:
•warunkowe,
•iteracyjne,
•zło
ż
one.
14
PS/TP
PROGRAMOWANIE STRUKTURALNE
2. PODPROGRAMY
Ogólna posta
ć
funkcji i procedury.
Zmienne lokalne i globalne.
Parametry formalne i aktualne.
Przekazywanie parametrów przez warto
ść
i przez zmienn
ą
.
Wywoływanie funkcji i procedur.
Rekurencja.
Stosowanie algorytmów interacyjnych i rekurencyjnych, algorytmu
Euklidesa, obliczania pot
ę
gi, wyznaczania liczb Fibonacciego.
Funkcje i procedury obsługi ekranu.
Moduły u
ż
ytkownika - zasady budowy i korzystania z modułów.
15
PS/TP
PROGRAMOWANIE STRUKTURALNE
3. TYPY STRUKTURALNE
Tablice.
Pliki tekstowe i operacje na tekstach.
Pliki elementowe.
Operacje na plikach.
Zbiory.
Rekordy.
Ogólne zasady budowy systemów informatycznych.
16
PS/TP
PROGRAMOWANIE STRUKTURALNE
• Stosowanie tablic i wykonywanie podstawowych operacji na tablicach:
sortowanie, wyszukiwanie.
• Zamiana liczb dziesi
ę
tnych na binarne.
• Znajdowanie zera funkcji metod
ą
połowienia przedziału.
• Operowanie plikami tekstowymi i elementowymi.
• Wykonywanie operacji na tekstach.
• Korzystanie z podstawowych algorytmów umo
ż
liwiaj
ą
cych wykonywanie
operacji na zbiorach.
• Wykorzystywanie rekordów do projektowania baz danych.
• Wykorzystywanie plików do projektowania systemu informatycznego typu
baza danych.
17
PS/TP
PROGRAMOWANIE STRUKTURALNE
4. DYNAMICZNE STRUKTURY DANYCH
Wska
ź
niki.
Funkcje i procedury dynamicznego przydziału pami
ę
ci.
Tworzenie i przetwarzanie dynamicznych struktur danych:
•stos,
•kolejka,
•listy,
•drzewa.
18
PS/TP
PROGRAMOWANIE STRUKTURALNE
5. ELEMENTY ZAAWANSOWANEGO
PROGRAMOWANIA W PASCALU
Dyrektywy kompilatora.
Obsługa urz
ą
dze
ń
peryferyjnych.
Rejestry procesora.
Wbudowany asembler.
Lokalizacja i usuwanie usterek w programie za pomoc
ą
debuggera.
19
PS/TP
PROGRAMOWANIE STRUKTURALNE
Poprawno
ść
i zło
ż
ono
ść
obliczeniowa algorytmów.
Optymalizacja działania programu.
Dokumentacja programu.
20
PS/TP
PROGRAMOWANIE STRUKTURALNE
1. Wprowadzenie do programowania strukturalnego w Pascalu
(pliki
TI_PS_CZESC_1A.pdf, TI_PS_CZESC_1B.pdf,
TI_PS_CZESC_1C.pdf, TI_PS_CZESC_1D.pdf
)
2. Podprogramy
(plik
TI_PS_CZESC_2.pdf
)
3. Typy strukturalne
(plik
TI_PS_CZESC_3.pdf
)
4. Dynamiczne struktury danych
(plik
TI_PS_CZESC_4A.pdf
)
5. Elementy zaawansowanego programowania w Pascalu
(plik
TI_PS_CZESC_4B.pdf
)
SPIS TRE
Ś
CI
21
PS/TP
Wst
ę
p
do
programowania
001
Gdańsk 2002
INPUT
PROGRAM
OUTPUT
22
PS/TP
CO TO JEST PROGRAMOWANIE ?
Programowaniem nazywamy zakodowanie danego
algorytmu za pomoc
ą
ci
ą
gu rozkazów napisanych w jakim
ś
j
ę
zyku programowania – j
ę
zyk programowania to stworzony
przez ludzi sztuczny j
ę
zyk słu
żą
cy do sterowania
komputerem.
BEGIN
READ
IF
END
WRITE
PROGRAM
KODOWANIE
23
PS/TP
Algorytm obliczania średniej arytmetycznej
N
10
SUMA
0
I
1
I
I + 1
CZYTAJ X
SUMA
SUMA + X
START
I <= N
T
N
STOP
WYPISZ SREDNIA
SREDNIA
SUMA / N
24
PS/TP
KODOWANIE
25
PS/TP
Program obliczający średnią arytmetyczną
Program przyklad;
(* obliczanie średniej z n liczb *)
const n = 10;
var i: integer;
x, suma, srednia: real;
begin
for i:=1 to n do
begin
readln(x);
suma:=suma+x;
end;
srednia:=suma/n;
writeln(srednia);
end.
26
PS/TP
GENERACJE J
Ę
ZYKÓW PROGRAMOWANIA
I GENERACJA
II GENERACJA
III GENERACJA
IV GENERACJA
27
PS/TP
I GENERACJA
Pierwszym językiem był kod binarny, składający się z ciągu
rozkazów w postaci zer i jedynek.
Dlatego język taki nazywamy językiem binarnym. Jak wiadomo
sercem każdego komputera jest procesor, który dysponuje swoim
zestawem rozkazów. Dlatego dla każdego typu procesora musiały
istnieć inne zestawy rozkazów. Języki binarne były więc
całkowicie uzależnione od procesora, czyli konkretnego
komputera. Dlatego nazwano je językami maszynowymi lub
wewnętrznymi.
Główną wadą takiego programowania jest po prostu uciążliwość
polegająca na pamiętaniu wszystkich kodów w postaci binarnej,
która nie jest dogodna dla człowieka wychowanego w świecie
liczb dziesiętnych.
28
PS/TP
00011110
01010010
01010000
10001110 11011001
10100000 00001001
01001101 00010101
01110000
01110010
00111110
PROGRAM BINARNY (MASZYNOWY)
Programowanie binarne komputera odbywało się za pomocą
przełączników oraz specjalnych kart lub taśm dziurkowanych.
Dlatego takie programowanie można nazwać ręcznym.
29
PS/TP
II GENERACJA
Aby ułatwić programowanie wprowadzono języki symboliczne
zwane asemblerami. W asemblerze każdy pojedynczy rozkaz
procesora zastąpiono symbolami które były łatwiejsze do
zapamiętania. Jednak nadal każdy asembler był związany z danym
typem komputera (procesora).
PUSH DS
PUSH DX
PUSH AX
MOV DX, OFFSET Msg
MOV AH,09H
INT 21H
POP AX
POP DX
POP DS
30
PS/TP
Początkowo każdy rozkaz asemblera był kodowany ręcznie na
zera i jedynki, lecz znacznym ułatwieniem były tzw.
translatory – programy tłumaczące symbole języka asemblera
na kody binarne. Programy te nazwano asemblerami a później
makroasemblerami, ponieważ sekwencje rozkazów często
używanych nazwano makrami.
P r o g r a m
s y m b o l ic z n y
( w ję z y k u
a s e m b le r a )
M O V A X , 0 1
A D D H L
R E T
P r o g r a m
b in a r n y
( m a s z y n o w y )
1 0 0 1 0 0 1
0 1 0 0 1 0 1
1 1 1 1 0 0 0
0 0 0 1 1 0 1
A S E M B L E R
( t r a n s la t o r )
31
PS/TP
III GENERACJA
Później powstały języki tzw. “wysokiego poziomu”. W językach
wysokiego poziomu symbole asemblera zastąpiono kodem
zbliżonym do języka naturalnego (angielskiego) i matematycznego.
10 START
20 PRINT ”WITAM”
30 STOP
Języki te były już w małym stopniu zależne od konkretnego
typu komputera.
32
PS/TP
Program w języku
wysokiego poziomu
10 START
20 PRINT „WITAJ”
30 STOP
Program
symboliczny
(w języku
asemblera)
MOV AX,01
ADD HL
RET
Program binarny
(wykonywalny)
00011101
01010100
11001001
10001111
00001111
Translacja na asembler
Translacja na kod binarny
Wysoki poziom
→
Asembler
→
Kod binarny
33
PS/TP
Ponieważ stworzone języki wysokiego poziomu były zrozumiałe
jedynie przez człowieka to musiano stworzyć specjalne programy
tłumaczące zwane kompilatorami i konsolidatorami (ang.
linkerami).
Oprócz kompilatorów stworzono również interpretery.
W ogólności można powiedzieć, że translatory dzielimy na
kompilatory i interpretery – o których bliżej w następnym
rozdziale.
PAMIĘTAJ:
TYLKO PROGRAM BINARNY MOśE BYĆ
WYKONYWANY PRZEZ PROCESOR.
34
PS/TP
IV GENERACJA
Właściwie to trudno powiedzieć do której generacji należą
języki strukturalne oraz obiektowe.
Najpierw były języki strukturalne, za pomocą których pisano
programy składające się z wielu modułów – jeden moduł był
zawsze głównym t.j. sterował pozostałymi.
P r o g r a m m a i n ;
b e g in
r e a d ( x ) ;
y : = fu n ( x ) ;
d is p ( y ) ;
e n d .
m o d u le fi r s t ;
fu n c t i o n fu n ( a ): r e a l;
fu n : = a + 1 0 0 ;
e n d ;
m o d u le s e c o n d ;
fu n c t io n d is p ( b ) ;
w r i t e ln ( b ) ;
e n d ;
35
PS/TP
Z tego okresu pozostało znane programistom określenie
prof. Niklausa Wirtha :
“Struktury danych + Algorytmy = Programy” (patrz rysunek).
Program przykład;
var
x: array[1..100] of integer;
i: integer;
y: integer;
begin
for i := 1 to 100 do
begin
readln(y);
x[i] := y;
end;
end.
Dane
Algorytm
Później powstały, a właściwie wytworzono nową filozofię podejścia
do programowania a mianowicie programowanie zorientowane
obiektowo bazujące na językach strukturalnych.
36
PS/TP
V GENERACJA
Języki V generacji to grupa języków stosowana do tworzenia
programów ekspertowych lub t.z.w. aplikacji wykorzystujących
“sztuczną inteligencję”. Ich zastosowanie odnosi się na razie
głównie do sfery badawczej i dlatego nie będą omawiane.
KLASYFIKACJA TRANSLATORÓW
CO TO JEST TRANSLACJA?
Translacją nazywamy proces tłumaczenia kodu jednego
języka na kod innego języka.
37
PS/TP
Postać źródłowa
X:=X+21;
Postać wynikowa
MOV AX,X
ADD AX,21
MOV BX,AX
TRANSLATOR
Słownictwo
Gramatyka
Interpretacja
Słownictwo
Gramatyka
Interpretacja
Program lub grupa programów służąca do translacji
nazywamy translatorem. Język z którego dokonuje się
translacji nazywamy postacią źródłową a język na który
translator tłumaczy nazywamy postacią wynikową.
38
PS/TP
Jak wiadomo każdy język naturalny (angielski, polski, niemiecki
i.t.d.) ma swoje słownictwo, gramatykę oraz interpretację.
Translator musi więc znać słownictwo, gramatykę i interpretację
obu języków.
Zbiór reguł obowiązujących w danym języku (słownictwo
i gramatyka) nazywamy składnią danego języka, a sposób
interpretacji zdań zapisanych w danym języku nazywamy
semantyką.
SKŁADNIA – czyli odpowiedź na pytanie:
JAK PISAĆ
POPRAWNY PROGRAM?
SEMANTYKA – czyli odpowiedź na pytanie:
CO POWODUJE
WYKONANIE PROGRAMU?
39
PS/TP
Translatory dzielimy na asemblery, kompilatory i interpretery
Języki programowania można więc także podzielić na języki
symboliczne asemblera, kompilowane oraz interpretowane.
Asembler tłumaczy każdy jeden rozkaz kodu asemblera na jeden
rozkaz binarny, a kompilator i interpreter tłumaczy jeden rozkaz
języka wysokiego poziomu na wiele rozkazów w kodzie
binarnym.
Translatory
Kompilatory
Interpretery
Asemblery
40
PS/TP
JAK DZIAŁA KOMPILATOR ?
I Faza. Kompilowanie (tłumaczenie rozkazów programu źródłowego na rozkazy binarne)
II Faza. Wykonywanie (procesor komputera wykonuje rozkazy binarne)
Program źródłowy
np. test.pas
Program wynikowy
np. test.exe
KOMPILATOR
Program wynikowy
np. test.exe
41
PS/TP
JAK DZIAŁA INTERPRETER?
Działanie interpretera jest odmienne w porównaniu z
kompilatorem. Interpreter nie tłumaczy całego programu
ź
ródłowego, lecz wykonuje go krok po kroku to znaczy rozkaz po
rozkazie.
Jego działanie dla każdej linii programu przebiega w
następujących fazach:
I Faza. Pobranie linii zaw
ierającej rozkaz. Interpreter sprawdza
poprawność (składnię) rozkazu.
II Faza. Kompilowanie rozkazu (
tłumaczenie rozkazu na
postać binarną)
III Faza. Wykonywanie rozkazu binarnego przez procesor
komputera.
42
PS/TP
UWAGA: jeśli interpreter stwierdzi błąd w składni rozkazu, to
natychmiast przerywa działanie programu i wyświetla komunikat
informujący o rodzaju błędu i numerze linii w której stwierdził błąd.
INTERPRETER
Program źródłowy
np. test.js
SPRAWDZENIE
SKŁADNI
ROZKAZU
Pobranie kolejnego
rozkazu
WYGENEROWANIE
ROZKAZU BINARNEGO
Skok do następnego
rozkazu
WYKONANIE ROZKAZU
BINARNEGO
43
PS/TP
Języki interpretowane są łatwiejsze do
opanowania przez początkujących
programistów, lecz programy w nich
pisane działają na ogół wolniej.
Programy pisane w językach
kompilowanych są szybsze i lepiej
wykorzystują pamięć komputera.
44
PS/TP
CO TO JEST KONSOLIDACJA ?
P r og r a m g łów n y
w jęz yk u
w y sok ie g o
p oz io m u
M od uł M 1 w
ję z yk u w y sok ieg o
p oz io m u
M od u ł M 2 w
ję z yk u w y sok ieg o
p oz io m u
K O M P IL A C JA
K O M P IL A C JA
K O M P IL A C JA
K O D
A S E M B L E R O W Y
P R O G R A M U
G Ł Ó W N E G O
K O D
A S E M B L E R O W Y
M O D U Ł U M 1
K O D
A S E M B L E R O W Y
M O D U Ł U M 2
P
R
O
G
R
A
M
B
IN
A
R
N
Y
(
W
Y
N
IK
O
W
Y
)
k on solid a cja
C JA
k on solid a cja
C JA
k on solid a cja
C JA
F A Z A 1
F A Z A 2
45
PS/TP
PODSUMOWANIE:
W chwili obecnej pod pojęciem “kompilacji” środowisko programistów
rozumie fazę kompilacji i konsolidacji.
W uproszczeniu możemy powiedzieć że kompilowanie programu
ź
ródłowego to tłumaczenie instrukcji kodu źródłowego (plik o
rozszerzeniu n.p. PAS) na kod wynikowy (wykonywalny przez procesor
danej maszyny) w pliku o rozszerzeniu EXE.
Natomiast interpretowanie to pobieranie i wykonywanie przez maszynę
“od razu” kolejnych instrukcji kodu źródłowego. Dlatego w przypadku
języków interpretowanych nie powstaje plik o rozszerzeniu EXE.
Jednym z pierwszych translatorów który zrobił karierę był TURBO
PASCAL firmy Borland, bowiem potrafił w bardzo krótkim czasie
wykonać fazę kompilacji i fazę konsolidacji.
46
PS/TP
Program w języku PASCAL – oblicza średnią arytmetyczną
Program przyklad;
(* obliczanie średniej z n liczb *)
const n = 10;
var i: integer;
x, suma, srednia: real;
begin
for i:=1 to n do
begin
readln(x);
suma:=suma+x;
end;
srednia:=suma/n;
writeln(srednia);
end.