PR
OGRAMO
W
ANIE
I
Notatki
do
wykadu
Pawe Klimczewski
Uniwersytet Warszawski
Instytut Fizyki Teoretycznej
1999
Notatki dostpne s take w wersji elektronicznej pod adresem
http://soliton.fuw.edu.pl/~pablo/p1.ps.gz
Programowanie I
Wykad 1
3
Rozpoczcie pracy.
Administrator systemu tworzy konta dla poszczeglnych uytkownikw. Kady uytkownik posiada znany
oglnie, niepowtarzalny identy kator skadajcy si maksymalnie z 8 znakw oraz znane wycznie jemu
haso (take do 8 znakw). Przed rozpoczciem pracy naley poda identy kator i haso, co przykadowo
moe wyglda nastpujco:
login: pablo
password:
Last login: Sat Feb 14 23:37:13 on ttyp0 from localhost.
No mail.
%
W systemie zde niowanych jest wiele grup (ktrych znaczenie zostanie omwione przy opisie systemu pli-
kw) uytkownikw. Polecenie
id
umoliwia wypisanie na ekranie monitora identy katora i grup aktualnie
pracujcego uytkownika.
%id
uid=1110(pablo) gid=20(user)
Zmiany hasa mona dokona w dowolnym momencie. Do tego celu suy polecenie
passwd
. Po jego wydaniu
naley wpisa aktualne haso (dziki temu, kiedy np. odejdziemy na chwil od komputera, inne osoby nie
mog za nas zmieni hasa), a nastpnie dwukrotnie poda nowe haso. Jest to podyktowane faktem, e
wprowadzane haso nie jest nigdy widoczne na ekranie monitora i moglimy popeni bd wpisujc inne
haso ni mylelimy.
%passwd
Old password:
New password:
Re-enter new password:
Password for user pablo changed.
Haso nie powinno by atwe do odgadnicia { w szczeglnoci naley unika inicjaw, wyrazw (ich permu-
tacji) wystpujcych w jzyku, itp. Wikszo programw
passwd
wykryje takie sytuacje i odmwi przyjcia
nowego hasa. Dobrze jest aby haso
a) oprcz liter zawierao take cyfry lub znaki interpunkcyjne,
b) skadao si z maych i wielkich liter,
c) byo trudne do odgadnicia a zarazem w miar atwe do zapamitania { mog to by pierwsze litery
wyrazw tworzcych zdanie, np. zdanie \Ile kilometrw jest std do Krakowa ?" odpowiada hasu
IkjsdK?
W systemie
unix
haso znane jest tylko uytkownikowi. Bezporednio po wprowadzeniu jest kodowane w
nieodwracalny sposb i dopiero ta wersja jest zapamitywana w systemie. Za kadym podaniem hasa jest
ono ponownie kodowane i rezultat porwnywany jest z zapamitan uprzednio wartoci.
Pliki.
Plik
jest jednym z podstawowych poj zwizanych z systemami komputerowymi, w szczeglnoci z syste-
mem operacyjnym unix, ktry zosta wybrany jako model do ilustracji poj i programw omawianych na
zajciach. Plik moemy opisa jako uporzdkowany, skoczony cig
bajtw
, tj. liczb cakowitych z zakresu
0
:
:
:
255. W zwizku z tym, plik w danej chwili ma okrelony rozmiar. Dodatkowo, z plikiem zwizane s
pewne informacje, ktre uatwiaj jego wykorzystanie, takie jak:
a) nazwa pliku. Zwyczajowo nazwa zwizana jest z zawartoci i sposobem wykorzystania. Jest to jednak
tylko konwencja i w rzeczywistoci nazwa pliku moe by cakowicie dowolna. System operacyjny gwa-
rantuje, e w danym
katalogu
nie bd istniay dwa pliki o tej samej nazwie { nazwa jednoznacznie
identy kuje plik w danym katalogu. Dugo nazwy jest zupenie dowolna i nie moe jedynie zawie-
ra znaku
/
(slash). Ponadto system rezerwuje nazwy
.
(kropka) i
..
(kropka kropka) dla wasnego
wykorzystania, i dlatego nie mona utworzy plikw o takich nazwach.
Nazw pliku przyjto dzieli na dwie czci: nazw waciw i przyrostek (odpowiadajcy typowi pliku)
rozdzielone kropk.
unix1.txt
jest nazw o czci waciwej
unix1
i przyrostku
txt
informujcym, e
zawartoci pliku jest tekst zrozumiay dla czowieka.
Programowanie I
Wykad 1
4
Pliki o nazwach rozpoczynajcych si od znaku
.
(kropka) nie s wypisywane przy uyciu polecenia
ls
.
Przewanie zawieraj dane dla innych programw (takich jak interpreter polece) i dostp do nich nie
jest potrzebny w codziennej pracy. Okrela si je jako
ukryte
(ang. hidden). Chcc wypisa nazwy
wszystkich plikw (razem z ukrytymi) musimy w poleceniu
ls
zastosowa opcj
-a
(ang. all)
%ls -a
.login .logout .tcshrc mail unix1.txt unix.txt
b) daty operacji zwizanych z danym plikiem. Jest to bardzo wygodna cecha. System unix zapamituje
trzy daty:
ostatniego odczytu caoci bd fragmentu pliku,
ostatniej zmiany (dopisanie, skrcenie, mody kacja) zawartoci pliku,
ostatniej zmiany informacji zwizanych z plikiem, takich jak daty, typ, waciciel, itp.
c) waciciela pliku. Kada osoba przed rozpoczciem pracy w systemie unix musi dokona odpowiedniej
autoryzacji, i od tej pory wszystkie polecenia (w tym take dostp do systemu plikw) s kontrolowane,
a prby zapisu lub odczytu plikw bez wymaganych uprawnie kocz si niepowodzeniem.
W szczeglnoci wszystkie nowo tworzone pliki s wasnoci aktualnie pracujcego uytkownika i pierw-
szej grupy, do ktrej naley.
d) typ okrelajcy rodzaj pliku i operacje jakie mona wykona w odniesieniu do tego pliku. Generalnie
najwaniejszymi s tutaj:
- moliwo dokonania odczytu z pliku, oznaczana liter
r
(ang. read),
- moliwo zapisu, oznaczana
w
(ang. write),
- moliwo interpretacji pliku jako polecenia dla systemu, i wykonania go przez podanie nazwy pliku
w interpretatorze polecen, litera
x
(ang. executable).
Polecenie
ls
umoliwia wypisanie nazw plikw w biecym katalogu.
%ls
unix1.txt unix2.txt
Polecenie to posiada niezwykle bogaty zestaw opcji, ktre mog zosta uyte do zmiany sposobu jego dzia-
ania. Opcje rozpoczynaj si od znaku
-
(minus). System
unix
kojarzy si zwykle nowym uytkownikom z
gszczem moliwych opcji niemal dla kadego polecenia (w przeciwiestwie do innych systemw operacyjnych
jak np. MS-DOS). Okazuje si jednak, e jest tak bogate zestawy opcji s cech bardzo poyteczn, a obawy
zwizane z moliwoci zapamitania tego wszystkiego cakowicie nieuzasadnione, poniewa powszechnym
zwyczajem jest istnienie (niemal dla kadego polecenia) opisu jego zastosowania (ang. manual page).
Programowanie I
Wykad 1
5
Dostp do opisu polecenia uzyskujemy przy pomocy polecenia
man
y
%man ls
LS(1L)
LS(1L)
NAME
ls - list contents of directories
SYNOPSIS
ls -abcdefgiklmnopqrstuxABCFGLNQRSUX178] -w cols] -T
cols] -I pattern] name...]
DESCRIPTION
OPTIONS
-a
List all files in directories, including all files
that start with `.'.
-b
Quote nongraphic characters in file names using
alphabetic and octal backslash sequences like those
used in C.
:
:
:
Wyraenia podane w nawiasach kwadratowych s opcjonalne. Opcja
a
nie wymaga podania adnego argu-
mentu, natomiast opcja
-w cols
wymaga podania liczby okrelajcej ilo kolumn.
name...]
oznacza, e
w poleceniu
ls
moemy poda nazw dowolnej iloci plikw.
I tak, polecenie
ls -a
wypisze nam wikszy zestaw plikw, a mianowicie doda pliki, ktrych nazwy rozpo-
czynaj si od znaku
.
(kropka).
%ls -a
.ukryty ....cztey_kropki unix1.txt unix2.txt
Wypisanie dodatkowych informacji zwizanych z plikiem unix1.txt uzyskamy podajc opcj
l
:
%ls -l unix1.txt
-rw-------
1 pablo
users
8495 Feb 11 13:33 unix1.txt
Pierwsze pole opisuje rodzaj pliku. Znak
-
oznacza, e dana cecha nie jest aktywna dla pliku. Znaczenie
poszczeglnych pozycji jest nastpujce:
-
d
r
u
w
u
x
u
r
g
w
g
x
g
r
o
w
o
x
o
Zawarto pliku
unix1.txt
moe by odczytywana i mody kowana przez uytkownika
pablo
. Jeeli chcieli-
bymy aby take inni uytkownicy nalecy do grupy
users
mogli dokonywa zmian naley zmieni atrybuty
pliku poleceniem:
%chmod g+rw unix1.txt
%ls -l unix1.txt
-rw-rw----
1 pablo users 8495 Feb 11 13:33 unix1.txt
Jeeli chcemy dodatkowo, aby kady uytkownik mia prawo do odczytania zawartoci pliku to musimy doda
jeszcze jeden atrybut:
%chmod o+r unix1.txt
%ls -l unix1.txt
y
polecenie
man
rwnie posiada swj opis (co moe wydawa si nieco paradoksalne), ktry moemy
uzyska poleceniem
man man
Programowanie I
Wykad 1
6
-rw-rw-r-- 1 pablo users 8495 Feb 11 13:33 unix1.txt
Ostatecznie po przygotowaniu caego wykadu moemy zablokowa moliwo dokonywania zmian w pliku
%chmod ug-w unix1.txt
%ls -l unix1.txt
-r--r--r-- 1 pablo users 8495 Feb 11 13:33 unix1.txt
Katalogi.
W systemie plikw wprowadzono hierarchi, a mianowicie pojcie
katalogu
(ang. directory). Katalog
posiada prawie takie same wasnoci jak plik, z jedn rnic { zawartoci jego s inne pliki lub katalogi.
Kady plik i katalog zawarty jest w jakim innym katalogu. Wyjtkiem jest najbardziej zewntrzny katalog
(zwany korzeniem systemu plikw), ktry nie jest w niczym zawarty (a tak naprawd to zawarty jest w
samym sobie). Poniszy rysunek przedstawia przykadowy system plikw.
/
!------ bin/
!
!----- ls
!------ etc/
!
!----- motd
!------ dev/
!
!----- tty1
!------ lib/
!
!----- libc.so
!------ usr/
!
!----- bin/
!
!
!----- pine
!
!----- lib/
!
!
!----- libc.a
!
!----- people/
!
!----- guest/
!
!----- pablo/
!
!----- ....cztery_kropki
!
!----- .ukryty
!
!----- unix1.txt
!
!----- unix2.txt
!------ var/
!----- log/
!----- spool/
!----- tmp/
W danym momencie jeden z katalogw jest wyrniony i nazywa si go
biecym katalogiem
(ang. current
directory). Po rozpoczciu pracy przez uytkownika biecym katalogiem staje si katalog domowy, tzn.
katalog stworzony przez administratora systemu dla danego uytkownika. Przykadowo biecym katalogiem
dla uytkownika
pablo
bezporednio po rozpoczciu pracy staje si katalog
/usr/people/pablo
.
Nazw biecego katalogu moemy uzyska po wydaniu polecenia
pwd
%pwd
/usr/people/pablo
Jeeli podamy sam nazw pliku (np.
unix1.txt
) to odnosi si ona do plikw w
biecym
katalogu.
%ls -l unix1.txt
-r--r--r-- 1 pablo users 8495 Feb 11 13:33 unix1.txt
Jeeli chcemy si odwoa do pliku nie znajdujcego si w biecym katalogu musimy
poda pen nazw. Nazwy katalogw rozdzielamy znakiem / (slash). Ponadto
.
(kropka) oznacza
aktualny
katalog, za
..
(kropka kropka)
.
katalog, w ktrym zawarty jest
aktualny
katalog. Jeeli
pierwszym znakiem w nazwie jest / (slash) do nazwa odnosi si do katalogu { korzenia, w przeciwnym
wypadku jest liczona wzgldem biecego katalogu,
Programowanie I
Wykad 1
7
%ls -l /usr/people/pablo/unix1.txt
-r--r--r-- 1 pablo users 8495 Feb 11 13:33 /usr/people/pablo/unix1.txt
albo zmieni katalog. Do tego celu posugujemy si poleceniem
cd
(ang. change directory). Polecenie jest
postaci
%cd nazwa_katalogu
. Wydanie samego polecenia
cd
powoduje uczynienie katalogu domowego
(ang. home directory) katalogiem biecym.
%pwd
/usr/people/pablo
%cd /usr/people
%pwd
/usr/people
%ls -l unix1.txt
ls: unix1.txt: No such file or directory
%cd ..
%pwd
/usr
%cd
%pwd
/usr/people/pablo
I tak, jeeli chcemy aby inni uytkownicy mogli zaglda do naszego katalogu jednak bez moliwoci jakich-
kolwiek zmian to nadajemy atrybuty
%cd
%chmod og=rx .
%ls -ld .
drwxr-xr-x 13 pablo users 1024 Feb 10 13:13 .
Zwykle program obsugujcy poczt zapisuje pliki w podkatalogu
zawartym w katalogu domowym. Nie
yczymy sobie aby ktokolwiek tam zaglda.
%ls -ld Mail
drwx------ 2 pablo users 1024 Feb 10 13:21 Mail
Katalogi tworzymy poleceniem
mkdir
(ang. make directory), za usuwamy poleceniem
rmdir
(ang. remove
directory). Katalog przed usuniciem musi by pusty, tzn. nie moe zawiera adnego pliku ani podkatalogu.
%cd
%mkdir test
%cd test
%mkdir test
%cd ..
%ls -l
drwx------ 2 pablo users 1024 Feb 10 13:21 test
%rmdir test
rmdir: test: Directory not empty
Pliki usuwamy poleceniem
rm
. Jest to polecenie niebezpieczne bowiem atwo przez pomyk usun wszystkie
pliki z biecego katalogu.
%rm unix1.txt
Nazw istniejcego pliku zmieniamy poleceniem
mv
(ang. move), np.
%ls
unix1.txt
%mv unix1.txt unix.txt
%ls
unix.txt
Z kolei kopi pliku moemy utworzy dziki poleceniu
cp
(ang. copy).
%ls
Programowanie I
Wykad 1
8
unix.txt
%cp unix.txt unix1.txt
%ls
unix.txt unix1.txt
W systemie unix istnieje polecenie
wc
(ang. word count), ktre zlicza i wypisuje na ekranie monitora liczb
znakw, sw i wierszy wystpujcych w plikach, ktrych nazwy podano jako argumenty programu.
%wc unix1.txt
498 2087 14969 unix1.txt
%wc unix.txt
498 2087 14969 unix.txt
Nie jest wymagane dwukrotne wywoanie omawianego polecenia. Ju przy pierwszym poleceniu moemy
poda dwie nazwy plikw:
%wc unix1.txt unix.txt
498 2087 14969 unix1.txt
498 2087 14969 unix.txt
996 4174 29938 total
Wzorce.
Jeeli chcemy dokona oblicze dla wszystkich plikw tekstowych (czyli zakoczone przyrostkiem
.txt
) nie
musimy wypisywa wszystkich nazw po kolei (tym bardziej, e moga by by to bardzo duga lista) lecz
posugujemy si
wzorcem
%ls
unix.txt unix1.txt
%wc *.txt
498 2087 14969 unix1.txt
498 2087 14969 unix.txt
996 4174 29938 total
Symbol
*
(gwiazdka) oznacza dowolny cig znakw,
?
(znak zapytania) dowolny
jeden
znak, za wyraenie
a-z^pqr]
oznacza dowoln ma liter alfabetu rn od
p
,
q
i
r
. Jeeli wzorzec jest argumentem polecenia
to zostanie on zastpiony nazwami wszystkich plikw o odpowiadajcych mu nazwach. Jako ilustracj
wykorzystamy polecenie
echo
, ktrego jedynym zadaniem jest wypisanie podanych argumentw na ekranie
monitora.
%echo witam i zapraszam do pracy
witam i zapraszam do pracy
%echo pliki tekstowe w katalogu: *.txt
pliki tekstowe w katalogu: unix1.txt unix.txt
Standardowe wejcie i wyjcie.
Wikszo polece jakie wydajemy w systemie komputerowym, a dokadniej w programie interpretatora po-
lece (ang. shell), jest programem, tzn. istnieje plik o takiej samej nazwie jak polecenie i zawiera instrukcje
dla komputera. Program taki wymaga zde niowania sposobu pobierania danych (jeeli wogle s potrzebne,
np. omawiane polecenie
id
nie wymaga adnych dodatkowych danych) i wypisywania rezultatw. W syste-
mie unix wprowadzono abstrakcyjne pojcia standardowego wejcia (tzn. miejsca, skd pobierane s dane
do programu) oraz standardowego wyjcia (czyli, dokd przesyane s rezultaty). Normalnie standardowe
wejcie odpowiada klawiaturze czyli program (tak jak interpreter polece) czeka na dane wprowadzane przez
uytkownika, natomiast standardowe wyjciem zwizane jest z monitorem, i tam wanie wypisywane s
rezultaty. Istnieje jednak moliwo dokonania zmian, np. dane wyjciowe mog zosta zapisane do pliku
%ls -la > wynik.txt
albo skierowane jako dane wejciowe dla innego programu
%ls -la |less
%ls -la |wc
Programowanie I
Wykad 1
9
W tym miejscu naley zaznaczy, e jeeli polecenie
wc
zostanie wydane bez adnego argumentu to bdzie
zlicza litery, wyrazy i sowa ze standardowego wejcia.
%wc
abc def
to jest drugi wiersz
ratunku! jak przerwa! prac" tego programu???
^D
4 12 75
Symbol
^
oznacza klawisz
Ctrl
, czyli
^D
jest znakiem wprowadzonym przez nacinicie klawisza
D
przy
wcinitym klawiszu
Ctrl
.
^D
oznacza koniec danych i std program
wc
wiedzia, e ju nie powinien czeka
na dalszy test i dokona sumarycznych oblicze.
Prac dowolnego programu mona przerwa standardowo sekwencj
^C
. Uytkownik moe przede niowa
znaczenie symbolo
^C
,
^D
itd, ale nie naley tego robi, gdy prowadzi zwykle do chaosu. Co wicej, poszcze-
glne programy mog rwnie przede niowa znaczenie
^C
zatem nie ma uniwersalnego sposobu zakoczenia
dziaania dowolnego programu.
Zadania
1.
Wytumaczy rezultat polecenia:
%wc |wc
^D
1 3 24
2.
Poleceniem
rm *
mona przez zwyczajn nieuwag usun wszystkie pliki z katalogu. Z drugiej strony
jeeli podamy dodatkowo opcj
i
, tzn.
rm -i *
, system zapyta o potwierdzenie usunicia dla kadego
pliku. W interpretatorze polece moemy stosowa skrty, przykadowo moemy da aby polecenie
rm
odpowiadao
rm -i
. Aby to uzyska naley wyda polecenie
%alias rm "rm -i"
Sama komenda
alias
bez argumentw wypisuje wszystkie zde niowane skrty. Aby unikn koniecz-
noci stosowania powyszego polecenia przy kadym rozpoczciu pracy, interpreter polece
tcsh
bezpo-
rednio po uruchomieniu wykonuje polecenia zawarte w pliku
.tcshrc
.
Utworzy plik
.tcshrc
zawierajcy wiersz
alias rm "rm -i"
a jeeli taki plik ju istnieje (sprawdzi poleceniem
ls
) dopisa powyszy wiersz na kocu.
Programowanie I
Wykad 2
10
Programy i procesy.
Program
to cig instrukcji dla procesora zapisany w pliku.
Proces
dotyczy wykonywanego programu {
odnosi si nie tylko do pliku, ktrego polecenia s realizowane, ale take opisuje rodowisko, tzn. elementy jak
aktualne wykorzystywane katalogi i pliki, miejsce, z ktrego pobierane s dane wejciowe, i gdzie wypisywane
s wyniki oblicze, itd. W danej chwili moe istnie wiele procesw tego samego programu, nalecych
do jednego lub kilku rnych uytkownikw. System operacyjny zapewnia cakowit izolacj pomidzy
poszczeglnymi procesami i stwarza wraenie wycznego dostpu do komputera. Aby umoliwi spjne
wykorzystanie wsplnych zasobw, takich jak system plikw, poszczeglne procesy nie odwouj si do nich
bezporednio, a za porednictwem specjalnego elementu
jdra systemu
, ktre kolejkuje i realizuje odwoania
poszczeglnych procesw.
Polecenie
ps
(ang. process status) wypisuje informacje na temat aktualnie realizowanych procesw.
%ps
PID TTY STAT TIME COMMAND
56
1 S
0:01 -tcsh
57
2 S
0:00 -tcsh
58
3 S
0:00 -tcsh
65
1 S
0:13 emacs unix2.txt
68
2 S
0:00 less s.txt
77
3 R
0:00 ps
Na ekranie monitora zostay wypisane wszystkie procesy pracujcego uytkownika. Widzimy, trzy kopie
interpretera polece
tcsh
, edytor tekstw
emacs
, program do przegldania zawartoci plikw
less
, i wreszcie
wydane przed chwil polecenie
ps
.
Z kadym procesem zwizany jest unikalny identy kator
PID
bdcy liczb cakowit. Dziki temu moemy
odwoa si do konkretnego procesu nawet wwczas, gdy istnieje wiele kopii tego samego programu. W
naszym przykadzie odpowiada to programowi
tcsh
, ktrego trzy kopie posiadaj identy katory 56, 57 i 58.
W kolejnej kolumnie
TTY
wypisany jest nazwa terminala, z ktrym zwizany jest proces. Terminal odnosi
si do miejsca (np. okienka), w ktrym wypisywane s wyniki pracy programu. Kolumna
STAT
opisuje
aktualny stan procesu, i tak wszystkie procesy oprcz
ps
nie robi nic, dokadniej znajduj si w fazie snu
(ang. sleep) w oczekiwaniu na dane wejciowe. Jedynie proces
ps
wykorzystuje procesor komputera i jest w
stanie wykonywania (ang. run). Proces moe znajdowa si take w innych stanach, np.
D
nieprzerywalnego
snu (ang. uninterruptible sleep) kiedy jdro systemu realizuje na rzecz danego procesu operacje krytyczne,
ktre dla zachowania spjnoci nie mog zosta przerwane,
T
{ proces zatrzymany (ang. terminated).
Generalnie, proces jest albo w fazie wykonywania (kiedy procesor realizuje odpowiadajce mu instrukcje)
albo w fazie snu, czyli oczekiwania na swj przydzia czasu, procesora, dane, itd.
Kolejno
TIME
podaje sumaryczny czas wykorzystania procesora dla danego procesu od pocztku jego istnie-
nia, a
COMMAND
nazw polecenia, ktrego realizacja utworzya proces.
Jak atwo zauway procesy 65, 68 i 77 zostay uruchomione poprzez wydanie polece
emacs unix2.txt
,
less s.txt
i
ps
odpowiednio z trzech interpretatorw polece
tcsh
. Z kolei procesy
tcsh
zostay utworzone
automatycznie w momencie rozpoczcia pracy (otworzenia okna terminala).
W unix'ie istnieje hierarchiczna zaleno midzy procesami, tzn. istniej procesy potomne (ang. child pro-
cess), jak rwnie mwimy o rodzicu procesu (ang. parent process). Polecenie
ps -j
podaje nam informacj
o tych zalenociach.
%ps -j
PPID
PID PGID
SID TTY TPGID STAT
UID
TIME COMMAND
1
56
56
56
1
59 S
1110
0:01 -tcsh
1
57
57
57
2
78 S
1110
0:00 -tcsh
1
58
58
58
3
80 S
1110
0:00 -tcsh
56
65
65
56
1
59 S
1110
0:13 emacs unix2.txt
57
68
68
57
2
78 S
1110
0:00 less s.txt
58
78
78
58
3
80 R
1110
0:00 ps
Programowanie I
Wykad 2
11
Kolumna
PPID
okrela proces rodzica (ang. parent process id). Zauwamy, e w systemie istnieje zawsze
proces o identy katorze 1 (przewanie
init
). Co wicej widzimy, e istniej take grupy procesw
PGID
(ang. process group id).
Ko czenie istnienia procesw.
Proces moe wykona czynnoci i zakoczy swoje istnienie automatycznie (np. porwnaj polecenia
ls
czy
ps
). W przypadku innych programw, takich jak interpretator polece
tcsh
, istniej sposoby zakocze-
nia jego pracy poleceniem
logout
lub przez podanie znaku koca danych
^D
. Moe jednak zaj potrzeba
bezwarunkowego usunicia procesu. (Wyobramy sobie bdny program zawierajcy nieskoczon ptle,
ktrego realizacja pochania moc komputera, i ktry nie reaguje na adne dane wejciowe). W systemie
unix istnieje moliwo bardzo prostej komunikacji midzy procesami, zwanej przysyaniem sygnaw. Sy-
gna posiada okrelony rodzaj i odbiorc (tj. konkretny proces). Istniej rne odmiany sygnaw:
TERM
{
prob o zakoczenie pracy ale jednoczenie z szans na realizacj kocowych porzdkw,
KILL
ktry d
natychmiastowego zakoczenia pracy. Pewne sygnay s automatycznie generowane przez jdro systemu i
zazwyczaj informuj o prbach niedozwolonych operacji w samym programie (np.
BUS
,
SEGV
).
Polecenie
kill
suy do przesania sygnau do wybranego procesu. Wymaga podania identy katorw adre-
satw i opcjonalne rodzaju sygnau. Standardowo przesyana jest proba o zakoczenie pracy procesu
TERM
(ang. terminate). I tak komenda
%kill 58
koczy prac interpretatora polece zwizanego z terminalem 3. Uytkownik ma jedynie moliwo prze-
syania sygnaw do wasnych procesw, dziki czemu nie moe np. zakoczy realizacji programw innych
osb.
Procesy pracujce w tle.
Do tej pory wydawalimy proste polecenia, ktre szybko realizoway swoje czynnoci i koczyy istnienie.
Jedynym dugo wykorzystywanym procesem by interpretator polece
tcsh
, towarzyszcy nam przez cay
czas. W praktyce spotkamy wiele programw (np. programy dokonujce oblicze zycznych czy te re-
alizujce przesyanie danych midzy odlegymi komputerami), ktrych czas realizacji bdzie rzdu godzin.
Oczekiwanie na zakoczenie realizacji tych programw (chociaby tylko dla zwolnienia terminala) jest nie
tylko nudne ale i cakowicie bezsensowne.
W zwizku z tym istnieje moliwo uruchomienia procesu \w tle" (ang. background) bez towarzcego
terminala. Nie jest wtedy moliwa bezporednia komunikacja przy pomocy klawiatury i ekranu, ale dane
wejciowe jak i argumenty moemy zawsze zapisywa do plikw. Omwimy to na najczciej spotykanym
problemie jakim jest { czsto wielogodzinna { transmisja danych pomidzy komputerami. Zadanie polega
na cigniciu pliku
a.ps
. Standardowo wyglda to nastpujco:
%ftp bardzo.odleg$y.komputer
Connected to bardzo.odleg$y.komputer.
220 bardzo FTP server ready.
Name (bardzo:pablo): pablo
331 Password required for pablo.
Password:
Remote system type is UNIX.
Using binary mode to transfer files.
ftp> bi
200 Type set to I.
ftp> get a.ps
local: a.ps remote a.ps
200 PORT command successful.
150 Opening BINARY mode data connection for a.ps (312 bytes).
:
:
:
tutaj mog by czasem i godziny oczekiwania
:
:
:
226 transfer complete.
312 bytes received in 0.00198 secs (1.5e+02 Kbytes/ses)
ftp> quit
Programowanie I
Wykad 2
12
221 Goodbye.
%
Program
ftp
umoliwia przesyanie danych zgodnie z protokoem File Transfer Protocol. Do komputera
docelowego, z ktrego chcemy odebra dane przesyane s polecenia zwizane z identy kacj, danym
sposobem transmisji i nazw pliku. Z kolei serwer informuje o wynikach kadej czynnoci. W powyszym
przykadzie skorzystalimy z udogodnie w postaci podania nazwy komputera jako argumentu polecenia,
oraz z automatycznego zapytania o nazw uytkownika i haso, dziki czemu program
ftp
mia szans
odpowiedniego przestawienia terminala na czas wprowadzania hasa, tak aby nie byo ono widoczne. Moemy
(i zrobimy to dla celw dydaktycznych) wykona t czynno jeszcze raz w bardziej \surowy" sposb, tzn.
bez wspomnianych udogodnie. Rezygnujemy z nich opcj
-n
%ftp -n
ftp> open bardzo.odleg$y.komputer
Connected to bardzo.odleg$y.komputer.
220 bardzo FTP server ready.
ftp> user pablo bumbum
Remote system type is UNIX.
Using binary mode to transfer files.
ftp> bi
200 Type set to I.
ftp> get a.ps
local: a.ps remote a.ps
200 PORT command successful.
150 Opening BINARY mode data connection for a.ps (312 bytes).
226 transfer complete.
312 bytes received in 0.00198 secs (1.5e+02 Kbytes/ses)
ftp> quit
221 Goodbye.
%
W transmisji ftp wydalimy
1. polecenie
open bardzo.odleg$y.komputer
w celu nawizania cznoci z podanym komputerem.
2. Identy kowalimy si podajc nasz nazw (
pablo
) i haso (
bumbum
).
y
3. Zadalimy aby dane przesyane byy jak binarne (
bi
).
4. Poprosilimy o przesanie zawartoci pliku
get a.ps
.
5. Zakoczylimy poczenie (
quit
).
Wszystkie polecenia wpisywalimy bezporednio z klawiatury. W praktyce oczekiwanie na zakoczenie re-
alizacji punktu 4 moe trwa bardzo dugo. Okazuje si, e polecenia mona zapisa w pliku i uruchomi
program
ftp
w taki sposb, aby standardowym wejciem bya zawarto tego pliku. Kolejne polecenia bd
sukcesywnie odczytywane i realizowane. Tworzymy nastpujcy plik
ftp.in
open bardzo.odleg$y.komputer
user pablo bumbum
bi
get a.ps
quit
i wydajemy polecenie
%ftp -n < ftp.in
Connected to bardzo.odleg$y.komputer.
220 bardzo FTP server ready.
Remote system type is UNIX.
Using binary mode to transfer files.
200 Type set to I.
y
Wikszo serwisw ftp posiada gocinne konta
ftp
, a jako haso naley poda wasny adres email'owy.
Programowanie I
Wykad 2
13
local: a.ps remote a.ps
200 PORT command successful.
150 Opening BINARY mode data connection for a.ps (312 bytes).
226 transfer complete.
312 bytes received in 0.00198 secs (1.5e+02 Kbytes/ses)
221 Goodbye.
%
Polecenia zostay odczytane z pliku
ftp.in
, natomiast informacje o ich wykonaniu wypisane na ekranie.
Zamiast tego, te ostatnie moemy rwnie skierowa do pliku, a poniewa w takim przypadku program
ftp
nie bdzie wymaga ani danych z klawiatury ani pisania na ekranie, moemy uruchomi go w tle i
:
:
:
i do
domu, a nastpnego dnia plik
a.ps
powinien znale si w naszym katalogu.
%ftp -n < ftp.in > ftp.out &
1] 292
%logout
Jeeli polecenie zostanie zakoczone znakiem
&
(ang. ampersand) to zostanie uruchomione w tle. Interpreter
polece zapamituje wszystkie procesy uruchomione w tle { wypisa o tym stosown informacj
1] 292
znaczc tyle, e proces o identy katorze 292 jest pierwszym procesem w tle. Uytkownik moe za pomoc
sekwencji
^Z
zatrzyma aktualnie wykonywany proces, uruchomi go w tle, uczyni z niego proces biecy,
itp.
%ftp -n
ftp> open bardzo.odleg$y.komputer.
Connected to bardzo.odleg$y.komputer.
220 bardzo FTP server ready.
ftp> ^Z
Suspended
%
Proces
ftp
zosta zatrzymany.
%jobs
1] + Suspended
ftp -n
%ps
PID TTY STAT TIME COMMAND
188
3 S
0:02 -tcsh
296
3 T
0:00 ftp -n
303
3 R
0:00 ps
Prac zatrzymanego procesu moemy realizowa zarwno bezporednio jak i w tle. Do sterowania tym su
polecenia
fg
, ktre uruchamia wskazany proces w trybie bezporednim, i
bg
przenoszce realizacj programu
w to.
%fg 1
ftp -n
quit
%
W przypadku przeniesienia realizacji w to proces
ftp
zostanie wstrzymany (poniewa oczekuje na podanie
polecenia lub chce wypisa rezultaty pracy) a odpowiednia informacja zostanie podana na terminalu.
%bg 1
1] + Suspended (tty output)
ftp -n
%
Kiedy proces pracujcy w tle koczy swoje istnienie interpreter polece take nas o tym poinformuje. Przy-
kadowo, po zakoczeniu procesu uruchomionego poleceniem
ftp -n < ftp.in > ftp.out &
na ekranie
zostanie wypisana wiadomo:
1]
Done
ftp -n < ftp.in > ftp.out
Programowanie I
Wykad 2
14
W obecnych czasach, kiedy mamy moliwo otwierania wielu kopii interpretatora polece (np. w poszcze-
glnych okienkach), mechanizm manipulowania wykonywaniem procesw (
jobs
,
bg
,
fg
) utraci nieco na
znaczeniu.
Programowanie I
Wykad 3
15
Sieci komputerowe.
Wymiana danych pomidzy rnymi (czsto odlegymi) komputerami bya zawsze wanym zadaniem dla
informatyki. Moliwoci technologiczne i zdobyte dowiadczenia umoliwiy praktyczy i atwy dostp do
wiatowej sieci Internet. W ramach tej sieci czy si ze sob rne komputery. Internet charakteryzuje
si zdecentralizowan architektur (co gwnie zawdziczamy historii, poniewa wywodzi si z rozwiza
wojskowych). Oznacza to, e nie ma komputerw, ktre sprawowayby funkcje zarzdzajce, niezbdne dla
sprawnego funkcjonowania caoci. W zwizku z tym, nie mona zaplanowa ataku na pewne fragmenty sieci
aby unieruchomi cao. Zniszczenie tylko pewnych fragmentw sieci skutkowa bdzie brakiem dziaania
pobliskich komputerw, a nie caego systemu.
Adresy.
W ramach sieci Internet kady komputer posiada unikalny
adres internetowy
. Jest on liczb 32-bitow i
zwykle zapisywany jest w konwencji
a.b.c.d
, gdzie
a
,
b
,
c
i
d
s liczbami z zakresu 0
:
:
:
255. I tak, studencki
komputer unixowy tempac ma adres
148.81.7.2
.
Praktyczny sposb czenia komputerw midzy sob wyznacza pewn hierarchi. Komputery znajdujce
si w pracowni studenckiej posiadaj midzy sob bezporednie poczenia. Podobnie jest z komputerami w
poszczeglnych zakadach (budynkach, ich czciach) caego wydziau. Dalej, pewne wyrnione komputery z
kadej grupy s poczone razem z komputerem, ktry w tym wypadku zapewnia przepyw danych pomidzy
poszczeglnymi grupami. Z kolei ten ostatni poczony jest ze wiatem zewntrzym (czyli sici obejmujc
miasto), itd. Schemat ten ma swoje odbicie take w adresach samych komputerw. Komputery studenckie
maj numery rozpoczynajce si od
148.81.7
, czci teoretycznej
148.81.3
, dowiadczalnej
148.81.4
i
148.81.6
, KMMF
148.81.5
, itd.
W zwizku z tym, daleki komputer w Stanach Zjednoczonych, ktrego uytkownik chce przesa list do
studenta zyki, posiadajcego konto na tempacu musi skierowa j tylko w rejon Polski, albowiem adres roz-
poczyna
148.
. Nastpnie ju polskie komputery odpowiednio zdecyduj o posaniu danych w kolejne rejony
148.81
(pewnie gdzie w okolice centralne), a tutaj ju wiadomo, e
148.81.34567]
to Wydzia Fizyki,
gdzie ju bdzie znane jak dotrze do komputera tempac
148.81.7.2
. Dokadn drog jak przebywaj dane
pomidzy rnymi komputerami mona przeledzi przy pomocy polecenia
traceroute
.
Z przykadu wida, e nie istnieje adna oglna baza danych o wszystkich komputerach w Internecie. Jeeli
podamy adres nieistniejcego komputera (np.
148.81.5.250
), to i tak nastpi prba przesania informacji, i
dopiero komputery naszego wydziau odel (a tak naprawd to niczego nie odel, i brak odzewu jest tutaj
znaczcy) odpowiedz o nieistnieniu (a moe tylko chwilowym) wyczeniu adresata. O tym czy komputer
\yje" moemy przekona si posugujc si poleceniem
ping
.
Domeny i nazwy komputerw.
Poniewa adresy skadajce si z numerw nie s wygodne w uyciu, poza tym trudno je zapamita, wpro-
wadzono dodatkow moliwo odwoywania si do komputerw za pomc nazw symbolicznych. I tak pena
nazwa internetowa komputera tempac to
tempac.okwf.fuw.edu.pl
. Skada si ona z unikalnej w ramach
domeny okwf nazwy komputera. Domeny moemy sobie wyobraa jako coraz wiksze zbiory wszystkich
komputerw o pewnych cechach. I tak
pl
odnosi si do komputerw znajdujcych si w naszym kraju,
edu.pl
to polskich komputerw zainstalowanych w orodkach edukacyjnych,
fuw.edu.pl
, to ju Wydzia
Fizyki Uniwersytetu Warszawskiego, za
okwf.fuw.edu.pl
to Orodek Komputerowy.
Ten sposb adresowania wydaje si duo bardziej naturalny. Ponadto, jeeli nawet zapomnimy fragmentu
adresu, np. nie jestemy pewni nazwy komputera, pamitamy jedynie, e rozpoczynaa si na
t
, to mo-
emy zawsze (np. poleceniem
host
) uzyska nazwy wszyskich komputerw w zadanej domenie (w naszym
przypadku
okwf.fuw.edu.pl
).
W ramach domeny (tzn. kiedy prbujemy przesyamy informacj midzy dwoma komputeraminalecymi tej
samej domeny) wystarczy poda nazw samego komputera. Pracujc na komputerze
albert4.fuw.edu.pl
i chcc sprawdzi czy komputer
albert3.fuw.edu.pl
pracuje wystarczy polecenie
%ping albert3
natomiast aby sprawdzi czy pracuje komputer
sunsite.icm.edu.pl
potrzeba poda
%ping sunsite.icm
Programowanie I
Wykad 3
16
Adres poczty elektronicznej.
Idea sieci komputerowych powinna zapewnia taki sam dostp do wasnych danych i programw z kadego
komputera. Dziki temu mona udanie realizowa pomys pracowni komputerowych, gdzie uytkownik sia-
dajc przy dowolnym komputerze ma zapewnione takie same usugi i dostp do wasnych danych. Z drugiej
strony, kady komputer posiada inny adres internetowy. Sytuacja ta nie jest korzystna przy pisaniu email'i,
ktre wysyane z rnych komputerw bd posiaday rne adresy zwrotne! Aby temu zapobiec
a) wybiera si jeden komputer dla obsugi poczty (wasnie tak jest na tempacu) i w celu wymiany poczty
kady uytkownik czy si zdalnie (np. poleceniem
telnet
) z wybranym komputerem, przy czym jego
adres email'owy jest typu
pablo@tempac.okwf.fuw.edu.pl
,
b) wprowadza si adresowanie na domen (i tak jest w ramach pozostaej czci wydziau), tzn. adresem
uytkownika jest
pablo@fuw.edu.pl
, a poszczeglne komputery w ramach wydziau odpowiednio udo-
stpni poczt adresatowi. W szczeglnoci skierowanie poczty na jeden konkretny komputer (np. na
ktrym ostatnio pracowaa dana osoba {
pablo@fizyk1.fuw.edu.pl
) jest rwnowane adresowi
pa-
blo@fuw.edu.pl
. Przy takim podejciu moemy obsugiwa poczt z komputera, na ktrym aktualnie
pracujemy.
Nieznany adresat lub niemono dostarczenia poczty.
Jeeli dysponujemy niepenym adresem emailowym, ktrego poprawnoci nie jestemy do koca pewni, to
nie oznacza to wcale niemonoci przesania listu. Przede wszystkim, le zaadresowane listy nie gin bez-
powrotnie. Zawsze otrzymamy odpowied informujc nas o fakcie niedostarczenia przesyki wraz z opisem
powodu zaistniaej sytuacji. Podobnie bdzie jeeli z jakiego kolwiek powodu (np. awari fragmentu sieci
komputerowej) nasz list nie zosta dostarczony w okrelonym czasie (przewanie 3 dni). Niektre jednostki
(np. CERN) przysyaj bardzo wyczerpujce odpowiedzi, i jeeli napiszemy list do nieistniejcego adresata
Ambroego Kowalskiego w Cernie (adres Ambrozy.Kowalskiern.ch), to otrzymamy nie tylko informacj o
nieistnieniu konta takiego uytkownika, ale take list osb o podobno brzmicych nazwiskach.
Troch wicej informacji o uytkownikach.
Innym sposobem uzyskania informacji o adresach emailowych jest polecenie
finger
. Podaje ono informacj
o uytkownikach systemu. Zakres dostpnych wiadomoci zaley od lokalnej kon guracji sieci komputerowej.
Komputery na Hozej udostpniaj informacj typu:
%finger -l pablo@fizyk1.fuw.edu.pl
fizyk1.fuw.edu.pl]
Pawel Klimczewski (pablo)
Home: /home/2/pablo
Shell: NOSHELL
Mail forwarded to pablo@fizyk.fuw.edu.pl
Pawel Klimczewski (pablo) is not presently logged in.
Last seen at albert4 on Tue Mar 3 14:03:38 1998
Adresaci poczty elektronicznej.
Tradycyjny list posiada jednego adresata (a dokadniej jedn skrzynk pocztow, do ktrej zostanie wrzu-
cony przez listonosza). W licie elektronicznym adresatowi temu odpowiada osoba wyszczeglniona w polu
To:
. Poniewa email jest informacj niematerialn, atwo wic umieci go w kilku emailowych skrzynkach
pocztowych, a zatem w licie mona poda kilku adresatw po sobie. Przesana w ten sposb wiadomo
zostanie dostarczona wszystkim osobom, i kada z nich bdzie moga odczyta pozostaych adresatw.
Istnieje take moliwo takiego przesania do wielu uytkownikw, aby aden z nich nie wiedzia o pozosta-
ych. Wtedy adresy naley umieci w polu
Bcc:
(ang. blind carbon copy). Program obsugujcy rozsyanie
poczty usunie ten wiersz w kadym egzemplarzu listu.
Automatyczne forwardowanie poczty.
Czsto zdarza si, e w pewnych okresach posiadalimy rne adresy emailowe. Np. przebywajc w innym
orodku badawczym, zaoono nam tam konto, a wraz z nim powsta adres emailowy. Istnieje moliwo
Programowanie I
Wykad 3
17
automatycznego przesyania nadchodzcej poczty pod inny adres. W tym celu naley w katalogu domowym
utworzy plik
.forward
, ktrego zawartoci jest wiersz zawierajcy nowy adres, np.
jasio@fuw.edu.pl
i odbierana poczta bdzie automatycznie odsyana dalej.
Programowanie I
Wykad 4
18
Wprowadzenie.
Program jako realizacja algorytmu, czyli uniwersalnego sposobu postpowania dla rnych danych wej-
ciowych.
W celu zrealizowania algorytmu posugujemy si okrelonym jzykiem programowania w zalenoci od
klasy zagadnienia. Nie ma uniwersalnego jzyka programowania.
Przykady:
1) jzyki oglne, przeznaczone do rnych zagadnie numerycznych, nadajce si do napisania pro-
gramu gra cznego, edytora czy bazy danych (np. Pascal, C++)
2) jzyki suce do skadania tekstw w celu uzyskania wydruku lub prezentacji na ekranie monitora
(np. TEX, HTML)
3) jzyki zwizane z obsug baz danych (np. SQL)
4) jzyki do oblicze symbolicznych (np. Mathematica, Maple)
W kadym z tych jzykw program zapisywany jest w postaci tekstu zrozumiaego dla czowieka.
Kompilacja {
tumaczenie
programu zrozumiaego dla czowieka na jzyk polece dla procesora. Nie
wszystkie jzyki wymagaj procesu kompilacji. W przypadku niektrych,
tumaczenie
realizuje si w
czasie wykonywania programu.
Jzyk C++
Jzyk C++ wywodzi si gwnie od jzyka C, w szczeglnoci jzyk C jest podzbiorem C++. Pocztki C++
sigaj roku 1980. Aktualnie posugujemy si propozycj standardu z 28 kwietnia 1995 roku.
Literatura.
1. Bjarne Stroustrup,
The C++ Programming Language
, Addison{Wesley, 1993
(polskie tumaczenie Bjarne Stroustrup,
Jzyk C++
, WNT 1994)
2.
Working Paper for Draft Proposed International Standard for Information Systems { Programming
Language C++
, AT&T Bell Laboratories.
Struktura programu.
Program w C++ jest analizowany w taki sam sposb jak czytany przez czowieka tekst, tzn. wiersz po
wierszu, a kady wiersz od lewej do prawej strony. Informacja uzyskana po przeanalizowaniu tekstu do
miejsca
x
jest wystarczajca aby zrozumie konstrukcj zawart w miejscu
x
. Innymi sowy wymagana jest
jednokrotna analiza programu.
Nazwy i wygld przydatnych znakw.
Raz na zawsze naley zapamita, e
/
to slash
\
backslash
#
hash
@
at (pol. mapa)
&
ampersand
Backslash na ko cu wiersza.
Wiersz w programie C++ moe by dowolnie dugi. Poniewa edytor ma skoczon szeroko wprowadzono
zasad, e pojedynczy wiersz programu mona zapisa w kilku wierszach edytora. Jeeli ostatnim znakiem
wiersza (tzn. bezporednio przed znakiem koca wiersza
\n
) jest
\
(backslash) to w czasie analizowania
programu dany wiersz jest czony z kolejnym tworzc jeden wiersz.
przykad:
Te_trzy_wie\
rsze_zost\
ana_polaczone
zostanie odczytane jako wiersz
Te_trzy_wiersze_zostana_polaczone
Komentarze czyli dodatkowe informacje w programie.
Programowanie I
Wykad 4
19
Podczas analizowania programu pewne jego fragmenty zwane komentarzami zostaj pominite i nie maj
adnego znaczenia. Stanowi one dodatkow informacj przydatn dla atwiejszego zrozumienia programu.
Mamy dwa sposoby zaznaczania komentarzy:
/* spos*b 1
komentarz rozpoczyna sekwencja /* (slash gwiazdka)
mo+e sk$ada! si" z wielu wierszy
wyst"puj,ce w nim kolejne sekwencje /* /* /* /*
i // (slash slash) // // // s, ignorowane
komentarzy nie mo+na zagnie+dza!
komentarz ko-czy lustrzana sekwencja (gwiazdka slash) */
lub
// spos*b 2
// komentarze rozpoczyna sekwencja // (slash slash)
// a ko-czy si" on wraz z ko-cem wiersza
// sekwencje /* */ nie s, tu rozpoznawane.
wiczenie:
/* a co tutaj jest komentarzem *\
// a co nie jest ?
Podczas analizy programu kady komentarz zastpowany jest znakiem spacji.
przykad:
a/**/b
7!
a b
Preprocesor.
Integraln czci jzyka C++ jest preprocesor, tj. mechanizm zastpowania pewnych partii tekstw innymi
(na og krtszymi), wczania lub wyczania caych czci programu, itp.
Polecenie preprocesora rozpoznajemy po tym, e pierwszym rnym od spacji znakiem wiersza jest
#
(hash). Polecenie preprocesora musi by zawarte w pojedynczym wierszu (i tu przydaje si
\
).
A. Zastpowanie pewnych fragmentw tekstu innymi.
W programowaniu naley pamita o unikaniu stosowania staych liczbowych. Jeeli chcemy obliczy dugo
okrgu to zamiast pisa
s = 2*3.14159*r.
duo wygodniej byoby napisa
s = 2*M_PI*r.
Co wicej, taki zapis jest od razu samodokumentujcy, podczas gdy poprzedni wzr moe budzi pewne
zastanowienie u osoby, ktra pragnie zrozumie co si dzieje w programie.
Preprocesor umoliwia de niowanie pewnych symboli, ktre po napotkaniu w tekcie programu s zastpo-
wane innymi. I tak w programie
#define M_PI 3.14159
s = 2*M_PI*r.
preprocesor jest instruowany w pierwszym wierszu o chci uytkownika aby kolejne wystpienia symbolu
M_PI
zamienia na
3.14159
.
Mona de niowa symbole zalene od parametru
#define SZESCIAN(a) a*a*a
oraz takie, ktre nie posiadaj adnej wartoci
#define PUSTY_SYMBOL
Wtedy program
#define PEWNA_LICZBA 123456
b = PUSTY_SYMBOL SZESCIAN(PEWNA_LICZBA).
zostanie przeksztacony do
b = 123456*123456*123456.
Polecenie
#define
suyo w C do de niowania staych. Np. typowy fragment programu, w ktrym otwierany
jest plik
nazwapliku
z moliwoci czytania i pisania (staa zde niowania jako
O_RDWR
od
read write
), z
Programowanie I
Wykad 4
20
utworzeniem pliku jeeli jeszcze nie istnia (
O_CREAT
od
create
) i skrceniem dugoci do zera (
O_TRUNC
od
truncate
).
f = open("nazwapliku",O RDWR |O CREAT |O TRUNC).
zostanie przeksztacony do
f = open("nazwapliku",0x4 |0x200 |0x100).
O ile atwiej zrozumie poprzedni zapis !
B. Do czanie zawartoci innych plikw.
Chcielibymy nie pisa de nicji takich staych jak
M_PI
w kadym programie, w ktrym mamy zamiar z niej
korzysta. Duo wygodniej jest mie takie de nicje w pliku i mc je wczyta do naszego programu. Do tego
celu suy polecenie
#include <nazwapliku>
lub
#include "nazwapliku"
Po przeanalizowaniu tego polecenia zostanie nastpnie odczytana i przeanalizowana zawarto pliku
na-
zwapliku
, a dopiero potem bdzie kontynuowana analiza tekstu programu. (Rnice pomidzy
#include
<nazwapliku>
i
#include "nazwapliku"
o ile s to zale od implementacji.)
C. Warunkowe w czanie pewnych fragmentw programu.
Pewne czci programu mog wymaga rnej implementacji w zalenoci od rodzaju komputera, na ktrym
program bdzie pracowa. Podczas kompilacji preprocesor de niuje pewne dodatkowe symbole (na og
puste, tzn. analogiczne do
PUSTY_SYMBOL
), np. w systemie MS DOS zde niowany jest symbol
__MSDOS__
, w
systemie Unix -
unix
, a podczas kompilacji na komputerach Silicon Graphics zde niowany jest symbol
sgi
,
itd.
przykad:
#ifdef __MSDOS__
tutaj program specy czny dla systemu MSDOS
#endif
#ifdef unix
tutaj program specy czny dla systemu unix
#endif
#ifdef sgi
a tutaj dla komputerw SGI
#else
i dla wszystkich innych
#endif
UNIKAMY KORZYSTANIA Z PREPROCESORA, A W SZCZEGLNOCI Z
#define
!
Preprocesor potrzebny by w C. Stanowi on jednak rdo czstych i bardzo trudnych do wykrycia bdw.
Gwnym powodem jest fakt, e preprocesor jest tylko \zamian pewnych cigw znakw innymi" i pod-
czas swego dziaania nie traktuje przetwarzanego tekstu jak programu. Programem jest wynik dziaania
preprocesora, ktry czasami okazuje si zupenie czym innym ni mia na myli autor.
W C++ wprowadzono inne mechanizmy umoliwiajce zarwno de niowanie staych jak i funkcji rozwija-
nych w punkcie wywoania (odpowiednik deklaracji
SZESCIAN
), ale z pen kontrol skadniow. Co wicej
DOBRE
kompilatory C++ przetwarzaj instrukcje warunkowe od staych (np.
if (1)
,
while (0)
, itp.)
w tak efektywny sposb, e jest to rwnowane dyrektywom
#if
:
:
:
#endif
.
Programowanie I
Wykad 4
21
Zadania
1.
Umiejtno rozpoczcia i zakoczenia pracy na koncie sieciowym z komputerem.
2.
Operacje na plikach i katalogach: tworzenie, przegldanie, mody kowanie, itp.
3.
Prosz samodzielnie przekona si co jest komentarzem w programie
/* co tu jest komentarzem *\
// a co nie jest ?
Jeeli uyjemy preprocesora cpp.exe rmy Borland (v. 3.1) to okae si co prawda, e nie jest to
najmdrzejszy preprocesor, ale przy okazji poinformuje on nas o innej wanej zasadzie.
4.
Czy autor tego poprawnego skadniowo programu osignie swj cel ?
b = a//* dziel" a przez 2*/ 2
+c /* i dodaj" jeszcze c */ .
5.
Prosz zde niowa symbol
SZESCIAN(a)
jako
a*a*a
, a nastpnie przekona si dowiadczalnie jak pre-
procesor rozwinie wyraenia
SZESCIAN(5)
SZESCIAN(a+1)
Czy nie nasuwaj si adne wtpliwoci ?
6.
Prosz w jednym pliku zde niowa jak sta, np.
SQRT_3
, a w drugim pliku wczyta ten pierwszy i
wpisa wzr na dugo wysokoci w trjkcie rwnobocznym
h = a*SQRT_3/2.
i zobaczy jaki jest rezultat pracy preprocesora.
7.
Prosz zapozna si z dodatkowymi symbolami preprocesora:
__TIME__
,
__DATE__
,
__LINE__
,
__FILE__
i odgadn co one oznaczaj.
8.
Prosz powiedzie co bdzie wynikiem pracy preprocesora dla pliku i porwna uzyskan odpowiedz z
rezultatem pracy preprocesora.
#define A a A
#define B A B
#define a A a
a A B
Programowanie I
Wykad 5
22
Elementy sk adniowe jzyka.
1) identy katory
2) liczby
3) napisy
4) wartoci
prawda
i
fa sz
5) operatory i znaki przystankowe
1. Identykatory
su do nazywania zmiennych, obiektw, funkcji, typw, itd.
skadaj si z liter alfabetu angielskiego, cyfr i znaku podkrelenia
_
, ktry jest traktowany jak litera
_ a b c d e f g h i j k l m
0 1 2 3 4 5 6 7 8 9
n o p q r s t u v w x y z
A B C D E F G H I J K L M
N O P Q R S T U V W X Y Z
pierwszym znakiem musi by litera
dugo identy katora jest nieograniczona
wielkie i mae litery s traktowane jako rne$
abc
i
Abc
to rne identy katory
pewne identy katory (
s owa kluczowe
) maj znaczenie pierwotne
nazwa identy katora
powinna
kojarzy si z rol jak spenia nazywana wielko. Naley unika iden-
ty katorw jednoliterowych jak i przesadnie dugich.
Przyk ady identykatorw.
bok_a
BokA
nazwa_pliku
NazwaPliku
Double_noded_list
TDoubleNodedList
x12
S owa kluczowe.
asm
do
inline
short
typeid
auto
double
int
signed
typename
bool
dynamic_cast
long
sizeof
union
break
else
mutable
static
unsigned
case
enum
namespace
static_cast
using
catch
explicit
new
struct
virtual
char
extern
operator
switch
void
class
false
private
template
volatile
const
float
protected
this
wchar_t
const_cast
for
public
throw
while
continue
friend
register
true
default
goto
reinterpret_cast
try
delete
if
return
typedef
2. Liczby.
a) cakowite
w systemie dziesitnym, semkowym, szesnastkowym
ze znakiem lub bez
normalnej precyzji lub dugie
b) rzeczywiste
pojedynczej, podwjnej precyzji lub dugie
z kropk dziesitn lub w zapisie wykadniczym
Programowanie I
Wykad 5
23
c) reprezentujce znaki
2.a Liczby ca kowite.
w systemie dziesitnym skadaj si z cyfr
0
,
:
:
:
,
9
. Pierwsza cyfra rna od zera, np.
1234
,
1000
w sytemie semkowym skadaj si z cyfr
0
,
:
:
:
,
7
. Pierwsz cyfr jest zero, np.
010
= 8
10
,
0100
= 64
10
,
0377
= 255
10
w systemie szesnastkowym skadaj si z cyfr
0
,
:
:
:
,
9
i liter
A
,
:
:
:
,
F
(wielkie i mae litery traktowane s
tak samo). Liczb rozpoczyna sekwencja
0x
lub
0X
, np.
0xf
= 017
8
= 15
10
,
0X10
= 020
8
= 16
10
,
0xabcd
=
0xABCD
= 0125715
8
= 43981
10
liczb mona zakoczy znakiem
u
lub
U
. Traktowana jest wtedy jak liczba bez znaku { odpowiadajcy
jej typ jest
unsigned
, np.
64000u
,
0311U
,
0x9ab0u
liczb mona zakoczy znakiem
l
lub
L
. Wtedy jest ona typu
long
, np.
64000L
,
0311l
,
0x9ab0L
mona jednoczenie poda specy kacj
unsigned
i
long
{ zakoczenia
ul
,
uL
,
Ul
,
UL
,
lu
,
lU
,
Lu
,
LU
,
np.
64000ul
,
0311LU
,
0x9ab0Lu
2.b Liczby rzeczywiste.
zapisujemy tylko w systemie dziesitnym
zawieraj kropk dziesitn, np.
1.
,
0.
,
.3
,
.0
,
1.3333
,
0.0
lub cz wykadnicz (10
n
), np.
1e5
=1
10
5
,
20E100
=20
10
100
=2
10
101
albo oba elementy jednoczenie, np.
.00004E6
=
:
00004
10
6
= 40,
3.14159e-2
moe by zakoczon liter
f
lub
F
i wtedy jest typu
float
, np.
1.0f
albo liter
l
lub
L
i jest typu
long double
, np.
1.0l
w przeciwnym przypadku jest typu
double
Sama kropka dziesitna
nie
jest liczb rzeczywist !
2.c Liczby reprezentujce znaki.
Literom i pozostaym znakom przyporzdkowano pewne liczby. I tak wedug standardu ASCII,
0
7!
48,
1
7!
49,
9
7!
57,
A
7!
65,
z
7!
122,
?
7!
63. Sekwencja
apostrof znak apostrof
reprezentuje liczb odpowiadajc
symbolowi
znak
, np.
'a'
,
Programowanie I
Wykad 5
24
'1'
,
'?'
znak
nie moe by dowolnym symbolem, np. apostrofem (dlaczego ?).
escape sequences
Pewne cigi znakw wystpujce w liczbach reprezentujcych znaki i napisach maj specjalne znaczenie,
i tak
\n
7!
koniec wiersza
\t
7!
tabulacja pozioma
\v
7!
tabulacja pionowa
\b
7!
backspace
\r
7!
powrt karetki
\f
7!
nowa strona
\a
7!
dzwonek
\\
7!
\
(backslash)
\?
7!
?
\"
7!
"
\'
7!
'
n
ooo
, gdzie
ooo
liczba semkowa
7!
symbol reprezentowany przez liczb
ooo
n
xhhh
, gdzie
hhh
liczba szesnastkowa
7!
symbol reprezentowany przez liczb
hhh
3. Napisy.
Napisy to cigi znakw ujtych w cudzysowy, np.
"Hello world"
,
"\x48ello world"
(niepewne),
"\x48" "ello world"
,
"\x48\x65llo world"
,
"Sygna$ dzwonka\a"
,
"cudzys$*w \""
4. Wartoci prawda i fa sz.
Warto logiczn
prawda
reprezentuje symbol
true
, a
fa sz
symbol
false
.
5. Operatory i znaki przystankowe.
Wyrnione kombinacje znakw posiadaj specjalne znaczenie. Nale one do grupy operatorw i znakw
przystankowych. Przykady
(
,
.
,
+
,
-
,
->
,
<<
,
&&
,
++
,
<<=
Zasada nastpnego symbolu.
Podczas analizowania programu, za nastpny symbol uznaje si najduszy cig znakw mogcych tworzy
symbol, nawet jeeli dalsza analiza programu zakoczy si bdem, np.
x+++++y
zostanie odczytane jako
x
++ ++ + y
, co jest konstrukcj bdn o ile typy
x
i
y
s zde niowane pierwotnie, a nie jak
x ++ + ++ y
, co
w takim wypadku moe by wyraeniem poprawnym.
Najprostszy program.
int main()
{
return 0.
}
Program skada si z nastpujcych symboli
int
{ identy kator, sowo kluczowe
main
{ identy kator
(
,
)
,
{
{ znaki przystankowe
Programowanie I
Wykad 5
25
return
{ identy kator, sowo kluczowe
0
{ liczba cakowita
.
,
}
{ znaki przystankowe
Program mona take zapisa w jednym wierszu
int main(){return 0.}
albo jeszcze inaczej
int
main
(
)
{
return
0
.
}
Pisanie na ekranie.
#include <iostream.h>
int main()
{
cout<<"Hello world\n".
return 0.
}
Identy kator
cout
reprezentuje obiekt umoliwiajcy pisanie na ekranie monitora, tzn. standardowy stru-
mie wyjciowy. Nie jest on elementem jzyka. Naley do biblioteki standardowej, tzn. zbioru oglnie
stosowanych funkcji i obiektw. Aby program by poprawny niezbdne jest zde niowanie
cout
przed uy-
ciem. W tym celu za pomoc polecenia preprocesora
#include
do programu doczono zawarto pliku
iostream.h
.
Operatory.
jednoargumentowe
+
14p
,
-
14p
(znak liczby),
+ 12
,
-1.3
!
14p
zaprzeczenie,
!7
7!
false
,
!0
7!
true
dwuargumentowe
+
12l
dodawanie,
4+5
-
12l
odejmowanie,
9-3
*
13l
mnoenie,
1*3
/
13l
dzielenie cakowite (jeeli oba argumenty s cakowite),
1/2
dzielenie rzeczywiste jeeli przynajmniej jeden argument rzeczywisty
1/2.
%
13l
reszta z dzielenia,
5%3
7!
2, argumenty musz by cakowite
<<
11l
, przy pisaniu na ekran,
cout<<2+3*4<<'\n'
,
>>
11l
, przy wczytywaniu danych,
cin>>WspA
=
2p
przypisanie,
delta=b*b-4*a*c
,
a=a+1
==
9l
rwno,
1+2==3
7!
true
,
1==2
7!
false
!=
9l
rne,
1+2!=3
7!
false
,
1!=2
7!
true
<
,
<=
,
>
,
>=
10l
porwnanie
1<2
7!
true
,
2<1
7!
false
Wizania i priorytety.
W pierwszej kolejnoci wykonuje si operacje o najwyszych priorytetach, a dla operatorw o tym samym
priorytecie o kolejnoci decyduje wizanie
Programowanie I
Wykad 5
26
lewe
a*b*c
7!
(a*b)*c
lub prawe
a=b=c
7!
a=(b=c)
cout<<2+3*4<<'\n'
jest rwnowane
(cout<<(2+(3*4)))<<'\n'
, a
a<b==c<d
odpowiada
(a<b)==(c<d)
Wizania i priorytety dobrano w taki sposb aby w typowych wyraeniach stosowa jak najmniej nawiasw.
Operatory dwuargumentowe
nie okrelaj
kolejnoci wartociowania argumentw, np.
int a=0.
cout<<++a/++a.
jest niejednoznaczne. Wyjtkiem s
||
i
&&
, ktre wartociuj od lewej do prawej, a drugi argument moe
nie by obliczony.
W
I ZANIA
I
PRIOR
YTETY
OPERA
TOR
W
priorytet
wi zanie
op erator
16
::
class
::
15
lewe
]
indeks.
. -> ()
wyw. funkcji
Type
()
14
prawe
sizeof
! ~ ++ -- +
znak
-
znak
&
wsk.
*
wsk.
(
Type
)
new delete
13
lewe
*
mno.
/ %
12
lewe
+
dod.
-
odej.
11
lewe
<< >>
10
lewe
< <= > >=
9
lewe
== !=
8
lewe
&
and
7
lewe
^
6
lewe
|
5
lewe
&&
4
lewe
||
3
prawe
?:
2
prawe
= *= /= %= += -= <<= >>= &= ^= |=
1
lewe
,
dla wizania lewego mamy
(ab)c
a dla prawego
a(bc)
Rne typy liczb.
Zapamitanie liczby (czy jakiejkolwiek innej wielkoci) wymaga miejsca i sposobu reprezentacji { i nazywane
jest
typem
. Istniej typy wbudowane, a bazujc na nich programista moe tworzy wasne.
Liczby cakowite mog by typu (zakresy odpowiadaj Borland C 3.1)
char
zajmuj 1 bajt (0
:
:
:
255 lub
;
128
:
:
:
127) i wystarczaj do reprezentowania znakw
short
, 2 bajty (0
:
:
:
65535 lub
;
32768
:
:
:
32767)
int
najbardziej naturalny dla danej implementacji sposb zapisu liczb cakowitych, tutaj odpowiednik
short
long
, 4 bajty (0
:
:
:
4294967295 lub
;
2147483648
:
:
:
2147483647)
a rzeczywiste typu
float
, 4 bajty (3
:
4
10
;38
:
:
:
3
:
4
10
38
, 7 cyfr znaczcych)
double
, 8 bajtw (1
:
7
10
;308
:
:
:
1
:
7
10
308
, 15 cyfr znaczcych)
long double
, 10 bajtw (3
:
4
10
;4932
:
:
:
3
:
4
10
4932
, 19 cyfr znaczcych)
Bity i bajty.
Bit to wielko zdolna reprezentowa dwa stany nazywane
0
i
1
. Bajt skada si z cigu 8 bitw { potra
reprezentowa 256 symboli. Traktujemy go jako liczb w zapisie dwjkowym.
Promocje i konwersje wstpne.
Generalnie, jeeli argumentami danego operatora s liczby rnych typw, to liczba typu mniej dokadnego
jest przeksztacana do typu drugiego argumentu. Typ wyniku jest typem argumentw.
Programowanie I
Wykad 5
27
100000/2
7!
50000
, drugi argument przeksztacony to typu
long
1/2.
7!
.5
, pierwszy argument przeksztacony do typu
double
Zadania
1.
Ktre z podanych cigw s identy katorami ?
a)
jezyk_c++
b)
Borland C
c)
bardzo-dlugi-identyfikator
d)
inny___identyfikator
e)
kwota_w_$
f)
6alfa
2.
Czym rni si symbole
1997
i
"1997"
?
3.
Czy liczby
0.0004E6
i
400
s identyczne ?
4.
Czy podane napisy
"wersja12"
i
"wersja 12"
s
a) oba poprawne,
b) oba identyczne ?
5.
Czy wykonanie poniszych instrukcji bdzie identyczne ?
a)
cout<<"\xAB".
b)
cout<<"\xA" "B".
6.
Czy podane wyraenia s poprawne ? Jeeli tak to podaj ich wynik.
a)
01997 + 0xFu
b)
11L + 011L
c)
xAB00 + 4
d)
.000001e6 + 010
7.
Symbol
'\''
a) oznacza liczb reprezentujc znak
'
b) jest bdny poniewa zawiera dwa znaki pomidzy skrajnymi apostrofami
8.
Ktre z podanych napisw s poprawne ?
a)
"ten napis ko-czy backslash \\\"
b)
"\gamma, delta, epsilon"
c)
"\81"
d)
"'Hello\040world!'"
e)
"\x podpunkt e)"
9.
Wskaza kolejno wartociowania wyrae. Jakie liczby zostan wypisane na ekranie monitora ?
a)
cout <<
+ - - - + + 10 << '\n'.
b)
cout << 1 + - - - + + 10 << '\n'.
10.
Wskaza kolejno wartociowania wyrae.
a)
x1=x2=-b/2/a.
b)
cout<<"4+2*3"<<4+2*3<<'\n'.
11.
Jakie s moliwe rezultaty nastpujcych polece ?
int a=0.
cout<<++a/++a.
Wskazwka. Operator przedrostkowy
++
14p
powoduje zwikszenie zmiennej o 1. Sprawdzi dziaanie
programu dla kompilatora Borland C 3.1, i w miar moliwoci dla GNU gcc.
12.
Uruchomi podany poniej program w rodowisku MS DOS, przy pomocy kompilatora Borland C bez
korzystania ze rodowiska IDE, tzn. posugujc si jedynie edytorem systemowym(
edit
) lub z programu
Norton Commander. Dokona kompilacji wydajc odpowiednie polecenie w systemie DOS. Jakie pliki
powstay w wyniku kompilacji i jakie jest ich znaczenie ? Uruchomi otrzymany program i wytumaczy
rezultaty uzyskane na ekranie monitora.
#include <iostream.h>
Programowanie I
Wykad 5
28
int main()
{
cout<<
"2+3*4 = 2+(3*4) = "<<2+3*4<<"\n"
"2/3*4 = (2/3)*4 = "<<2/3*4<<"\n"
"2/3*4. = (2/3)*4. = "<<2/3*4.<<"\n"
"2/3.*4 = (2/3.)*4 = "<<2/3.*4<<"\n"
"17000+17000 = "<<17000+17000<<"\n"
"17000u+17000 = "<<17000u+17000<<"\n"
"2e0*17000 = "<<2e0*17000<<"\n"
"5*22000 = "<<5*22000<<"\n"
"22000+22000+22000+22000+22000 = "<<22000+22000+22000+22000+22000<<"\n"
"22000u+22000+22000+22000+22000 = "<<22000u+22000+22000+22000+22000<<"\n"
"22000l+22000+22000+22000+22000 = "<<22000l+22000+22000+22000+22000<<'\n'.
return 0.
}
Tekst programu znajduje si take na dysku
i:
w pliku
i:\prog1\zad12.cpp
.
Programowanie I
Wykad 6
29
Pole trjkta.
#include <iostream.h>
#include <math.h>
int main()
{
cout<<"Podaj boki\n".
float a, b, c.
cin>>a>>b>>c.
float p=(a+b+c)/2.
cout<<"Pole = "<<
sqrt(p*(p-a)*(p-b)*(p-c))
<<'\n'.
return 0.
}
Nawiasy klamrowe
{
,
}
grupuj instrukcje w bloki
okrelaj czas ycia zmiennych i obiektw
okrelaj zakres widzialnoci zmiennych i obiektw
nie ma ogranicze w iloci stosowanych par
{
,
}
Deklaracje zmiennych automatycznych.
zmienne automatyczne s deklarowane w bloku
{
:
:
:
}
zmienne potra pamita wartoci okrelonego
typu
kada zmienna musi by zadeklarowana
deklaracja skada si z nazwy
typu
oraz nazwy zmiennej (lub kilku zmiennych oddzielonych przecinkami)
deklaracj koczy rednik
.
float a, b, c.
jest to deklaracja zmiennych
a
,
b
i
c
potra cych zapamitywa liczby rzeczywiste pojedynczej precyzji
kiedy realizacja programu dochodzi do punktu deklaracji zmiennych zaczynaj one
y
i mona si do
nich odwoywa
w podanym przykadzie w momencie rozpoczcia
ycia
przez zmienn
b
istnieje ju zmienna
a
, a nie
istnieje jeszcze zmienna
c
. Zatem poprawne jest wyraenie
float a=0, b=a+1, c=b+2.
za bdne
float a=b+2, b=c+1, c=0.
Bezporednio po deklaracji, np.
float a.
warto zmiennej
jest przypadkowa
int main()
{
cout<<"Podaj boki\n".
{
float a, b, c.
cin>>a>>b>>c.
{
float p=(a+b+c)/2.
}
cout<<"Pole = "<<
sqrt(p*(p-a)*(p-b)*(p-c))
<<'\n'.
}
Programowanie I
Wykad 6
30
return 0.
}
Jednokrotna deklaracja.
identy kator jednoznacznie okrela zmienn
nie mona uy tej samej nazwy dla nazwania dwch zmiennych istniejcych jednoczenie, np.
{
:
:
:
float x=(-b+pd)/2/a.
cout<<"x = "<<x<<'\n'.
// nie korzystam z x
// potrzebuj" jeszcze
int x=10*n+3.
b d
:
:
:
}
Powyszy program mona poprawi grupujc odpowiednie instrukcje w dodatkowy blok, ktry ogranicza
czas ycia pierwszej zmiennej
{
:
:
:
{
float x=(-b+pd)/2/a.
cout<<"x = "<<x<<'\n'.
} // x ju+ nie istnieje
int x=10*n+3.
:
:
:
}
Zas anianie nazw.
w bloku mona zadeklarowa zmienn o dowolnej nazwie, nawet jeeli istniej zmienne, obiekty, itd. o
tej samej nazwie w blokach poprzednich
{
int a=1.
cout<<a<<'\n'.
{
a=a+1.
int a=10.
cout<<a<<'\n'.
a=a+1.
}
cout<<a<<'\n'.
}
naley unika zasaniania nazw gdy jest ono rdem czstych bdw
jeeli zmienna zostaa zasonita to nie mona si do niej odwoa
Blokowa struktura programu.
Piszc program instrukcje nalece do kolejnych, zawartych w sobie blokw zaczynamy z wikszym wciciem
(np. po dwie spacje na kady zagniedzony blok).
{
int a=1, b.
b=(a+1)*(a+2)*(a+3).
{
int c=b-a.
Programowanie I
Wykad 6
31
cout<<c<<'\n'.
}
a++.
cout<<a<<'\n'.
}
Dziki temu atwo odnale odpowiadajce sobie pary nawiasw
{
,
}
.
Warunkowe wykonanie instrukcji.
W czasie realizacji programu pewne instrukcje wykonujemy tylko w okrelonych sytuacjach, np. rozwizy-
wanie rwnania kwadratowego bdzie miao sens tylko dla nieujemnej delty.
Konstrukcja
if
:
:
:
else
umoliwia wykonanie instrukcji przy spenieniu podanego warunku i jest postaci:
if (
warunek
)
instrukcja1
Jeeli warto wyraenia okrelajcego
warunek
jest rna od zera to zostanie wykonana
instrucja1
. W
przeciwnym przypadku wykonanie
instrukcji1
zostanie pominite. Przykad:
:
:
:
if (delta>=0)
{
float pd=sqrt(delta).
float x1=(-b+pd)/2/a.
:
:
:
}
:
:
:
Bardziej rozbudowana instrukcja warunkowa ma posta:
if (
warunek
)
instrukcja1
else
instrukcja2
W sytuacji kiedy
wyraenie
nie jest prawdziwe (tzn. warto wyraenia rwna si zero) jest wykonywana
instrukcja2
. Przykad:
:
:
:
if (delta>=0)
{
:
:
:
}
else
cout<<"delta < 0\n".
:
:
:
instrukcja2
moe by take kolejn instrukcj warunkow, np:
:
:
:
if (delta>0)
{
// dwa rozwi,zania
:
:
:
}
else if (delta==0)
{
// jedno rozwi,zanie
:
:
:
}
else
{
Programowanie I
Wykad 6
32
// brak rozwi,za-
:
:
:
}
:
:
:
Ptle.
Czsto potrzebne jest powtarzanie cigu instrukcji. Przykadowo aby wypisa na ekranie monitora 10 kolej-
nych liczb, poczwszy od liczby podanej przez uytkownika, moemy napisa
cout<<"Podaj liczb"\n".
int n.
cin>>n.
int j=0.
while (j<10)
{
cout<<n+j<<'\n'.
j++.
}
Instrukcja
while
jest postaci
while (
warunek
)
instrukcja
powoduje powtarzanie wykonywania
instrukcji
dopki prawdziwy jest
warunek
.
W instrukcjach iteracyjnych (tzw. ptlach) moemy uywa instrukcji
break
i
continue
. Pierwsza powo-
duje natychmiastowe przerwanie wykonywania ptli, natomiast druga natychmiastowe rozpoczcie kolejnego
wykonania ptli. Zachowanie to ilustruje program:
while (
warunek
)
{
:
:
:
continue.
:
:
:
break.
:
:
:
cont:
}
brk:
instrukcja
continue
powoduje natychmiastowe przejcie do miejsca oznaczonego
cont
bez wykonywania
instrukcji zawartych midzy
continue
a
cont
.
instrukcja
break
powoduje przerwanie wykonywania ptli i natychmiastowe przejcie do miejsca ozna-
czonego
brk
.
Innym przykadem instrukcji iteracyjnej jest konstrukcja
do
:
:
:
while
postaci:
do
instrukcja
while (
warunek
).
Po kadym wykonaniu
instrukcji
sprawdzany jest
warunek
i jeeli jest on speniony to ponownie wykonywana
jest
instrukcja
. Ptla
do
:
:
:
while
rni si od ptli
while
tym, e
instrukcja
zostanie wykonana przynajmniej
raz, podczas gdy w ptli
while
wykonanie
instrukcji
moe nie mie miejsca.
Znaczenie instrukcji
continue
i
break
wewntrz ptli
do
opisuje poniszy program.
do
{
:
:
:
continue.
:
:
:
break.
Programowanie I
Wykad 6
33
:
:
:
cont:
} while (
warunek
)
brk:
Najbardziej rozbudowan instrukcj iteracyjn jest
for
postaci
for (
w1
.
w2
.
w3
)
instrukcja
odpowiada ona nastpujcej ptli zbudowanej przy uyciu instrukcji
while
w1
.
while (
w2
)
{
:
:
:
continue.
:
:
:
break.
:
:
:
cont:
w3
.
}
brk:
w ptli
for
mona pomin wyraenia
w1
,
w2
,
w3
znaczenie instrukcji
continue
i
break
jest takie samo jak przedstawione dla ptli
while
Przykady ptli nieskoczonych
for (..).
while (1).
do . while (1).
Liczby Fibonacciego.
#include <iostream.h>
int main()
{
cout<<"Podaj numer wyrazu\n".
int i.
cin>>i.
int Poprzednia=1, Biezaca=1.
for ( . i>=2 . i-- )
{
int Nastepna=Poprzednia+Biezaca.
Poprzednia=Biezaca.
Biezaca=Nastepna.
}
cout<<"szukany wyraz ci,gu Fibonacciego to "<<Biezaca<<'\n'.
return 0.
}
Programowanie I
Wykad 6
34
Zadania
1.
Co bdzie rezultatem wykonania programu
#include <iostream.h>
int main()
{
int x = 5.
{
int x = x.
cout<<x<<'\n'.
}
return 0.
}
2.
Poniej przedstawiony jest program rozwizujcy rwnanie kwadratowe.
#include <iostream.h>
#include <math.h>
int main()
{
cout<<"Podaj wsp*$czynniki a,b,c r*wnania a x^2 + b x + c = 0\n".
float WspA, WspB, WspC.
cin>>WspA>>WspB>>WspC.
float Delta=WspB*WspB-4*WspA*WspC.
if (Delta>=0)
{
float SqrtDelta=sqrt(Delta).
cout<<"x1 = "<<(-WspB + SqrtDelta)/2/WspA<<"\n"
"x2 = "<<(-WspB - SqrtDelta)/2/WspA<<'\n'.
}
else
{
cout<<"r*wnanie nie ma pierwiastk*w rzeczywistych\n".
}
return 0.
}
a) uytkownik dwukrotnie prbowa obliczy rozwizania dla wspczynnikw
a
= 10
;30
,
b
= 10
20
,
c
= 1 oraz
a
= 10
;30
,
b
= 10
10
,
c
= 1. Obliczenia koczyy si bdem programu. Prosz zapozna
si z programem umoliwiajcym ledzenie wykonywania programu (ang. debugger) i przy jego
pomocy wskaza miejsce powstania bdw.
b) dla danych wejciowych
a
= 10
;20
,
b
= 10
10
i
c
= 1 program podaje rozwizania
x
1
= 0 i
x
2
=
;
10
30
, podczas gdy duo lepszym przyblieniem
x
1
jest warto
;
10
;10
, ktra moe by
reprezentowana w typie
float
uytym w programie do oblicze. Prosz poda powd powstania
bdu dla wartoci
x
1
.
c) W jaki sposb zmieni warunek
delta>=0
aby poprawi prac programu w sytuacji opisanej w
podpunkcie
a
?
3.
Napisa program ktry odczytuj dat (dzie, miesic i rok, zakadamy e dane podane przez uytkow-
nika s poprawne) i wypisuje odpowiadajcy dzie tygodnia.
Wskazwka. Wykorzysta metod Gaussa obliczania numeru kolejnego dnia naszej ery na podstawie
dnia, miesica i roku.
if (Miesiac<=2)
{
Miesiac+=10.
Rok--.
Programowanie I
Wykad 6
35
}
else
{
Miesiac-=2.
}
LiczbaDni = Rok/4 - Rok/100 + Rok/400 + 367*Miesiac/12 + Dzien + Rok*365.
4.
Zmody kowa powyszy program w taki sposb aby odczytywa dwie daty (zakadamy, e bd po-
prawne) i wypisywa odlego w dniach pomidzy nimi.
5.
Prosz napisa program znajdujcy najwiksz liczb w podanym cigu liczb dodatnich. Ostatnim
wyrazem cigu jest liczba 0. Prosz zastosowa nastpujcy algorytm.
1. odczytaj kolejn liczb
2. jeli koniec danych to wypisz najwiksz liczb i zakocz program
3. jeeli dana liczba jest wieksz od dotychczasowej najwikszej to zapamitaj j jako najwiksz
4. powtrz czynnoci od punktu 1.
6.
Zaprezentowany program do obliczania kolejnych liczb Fibonacciego oblicza
f
23
=
;
19168. Zmody ko-
wa program w taki sposb aby wykrywa bdne wyniki i informowa o tym uytkownika.
7.
Napisa program sprawdzajcy czy podana liczba naturalna jest pierwsza.
8.
Dodajc kolejn ptl zmody kowa powyszy program tak, aby oblicza wszystkie kolejne liczby pierw-
sze mniejsze od
n
, gdzie
n
jest dan podan przez uytkownika.
Programowanie I
Wykad 7
36
Funkcje.
Piszc program staramy si wyodrbni w nim mniejsze zagadnienia. Jednym ze sposobw realizacji tego
podziau w programie jest zapisanie danego zagadnienia w postaci funkcji.
Funkcja
stanowi pewn logiczn cao
jest rozwizaniem jakiego problemu, np. obliczenie wartoci pierwiastka kwadratowego
przypomina struktur funkcje matematyczne.
Wywo ujc
funkcj podajemy zbir argumentw (moe
by pusty), a rezultatem wykonania moe by dodatkowa warto.
sposb deklaracji decyduje o tym jakie argumenty s wymagane do wywoania funkcji i jaki otrzymamy
rezultat, np. funkcja
double sqrt(double).
musi by wywoana z jednym argumentem typu
double
, a jej rezultatem bdzie take warto typu
double
, np.
double sd=sqrt(d).
sowo kluczowe
void
(ang. pustka) suy do zaznaczenia, e funkcja nie wymaga podania argumentw
lub nie daje rezultatu, np.
void drzemka(int ile).
jeeli funkcja nie wymaga argumentw
f(void)
to w deklaracji moemy opuci sowo
void
, np.
long czas().
argumenty funkcji s
zmiennymi zadeklarowanymi
w najszerszym bloku funkcji, w momencie wywo-
ania rozpoczynaj swoje ycie i nadawane s im wartoci pocztkowe. Kocz istnienie wraz z kocem
dziaania funkcji, np.
void f(int a)
{
cout<<a<<'\n'.
a++.
}
int main()
{
int b=0.
f(b).
cout<<b<<'\n'.
return 0.
}
w wyniku wykonania programu na monitorze zostan wypisane liczby
0
,
0
. Dlaczego ?
Return.
sowo kluczowe
return
powoduje natychmiastowe przerwanie wykonania danej funkcji i powrt do miej-
sca wywoania tej funkcji.
jeeli typ
T
rezultatu funkcji jest rny od
void
, to po sowie
return
naley poda warto typu
T
, np.
int abs(int i)
{
if (i>=0) return i.
else return -i.
}
polecenie
return
musi by ostatnim poleceniem w funkcji, np.
float g()
{
:
:
:
return 0.
}
Programowanie I
Wykad 7
37
jeeli funkcja nie ma rezultatu to kocowe
return
mona pomin.
Przecienie nazwy funkcji.
Moe istnie wiele funkcji o tej samej nazwie, ale rnicych si midzy sob typami argumentw i rezultatw,
np.
int abs(int i).
long abs(long l).
double abs(double d).
double abs(complex c).
Dziki temu, wystarczy pamita, e z obliczaniem moduu zwizane s funkcje o nazwie
abs
. W zalenoci
od tego dla jakiej wielkoci chcemy obliczy modu kompilator dobierze odpowiedni funkcj.
Zadeklarowanie dwch funkcji o tej samej nazwie i argumentach, ale rnych wartociach jest bdem ponie-
wa prowadzi do niejednoznacznoci, np.
int f(int i).
short f(int i).
:
:
:
long l=f(10).
ktre
f
?
:
:
:
Przecienie operatora umoliwia tworzenie wyrae typu
cout<<"Hello"<<1<<'\n'.
,
ktre stosujemy powszechnie dla wypisania danych na ekranie monitora (wczytania z klawiatury). Niech
cout
reprezentuje obiekt typu
T
. Jeeli zde niujemy funkcje
T operator<<(T,char*).
T operator<<(T,char).
T operator<<(T,int).
to moemy je wywoa
operator<<( operator<<( operator<<( cout, "Hello" ), 1), '\n').
co mona zapisa skrtowo
((cout<<"Hello")<<1)<<'\n'.
pamitajc o wysokim priorytecie i lewym wizaniu operatora
<<
moemy opuci nawiasy.
Argumenty domylne.
Kocowe argumenty funkcji mona zadeklarowa z wartociami domylnymi. Dziki temu przy wywoaniu
funkcji moemy uywa skrtw notacyjnych. Przykadowo jeeli funkcj
f
zadeklarowano jako
int f(int
a,int b=2,int c=3)
to wywoanie
f(1)
odpowiada
f(1,2,3)
,
f(2,3)
odpowiada
f(2,3,3)
.
Zignorowanie rezultatu.
W C++ moemy woa dowolne funkcje tak jakby ich rezultatem byo
void
, tzn. nie uwzgldniajc ewen-
tualnych wartoci zwracanych przez funkcj, np.
:
:
:
sqrt(2).
:
:
:
Powyszy fragment programu jest poprawny, chocia o ile
sqrt
jest standardow funkcj obliczajc pier-
wiastek kwadratowy nie ma adnego znaczenia. Pomimo tego, kade (nawet nie posiadajce znaczenia)
wywoanie funkcji bdzie wykonane. Wynika to z faktu, e kompilator nie jest w stanie oceni znaczenia
wywoania funkcji, ktre bardzo czsto zwizane jest z dodaktowymi
efektami ubocznymi
.
Funkcja
main
.
Kada instrukcja w programie musi nalee do jakiej funkcji. W zwizku z tym niepusty program musi
si skada przynajmniej z jednej funkcji. Co wicej umwiono si, e kady program musi zawiera funk-
cj
main
, ktra dodatkowo zostanie automatycznie wywoana po uruchomieniu programu.
main
moe by
zadeklarowana jako
Programowanie I
Wykad 7
38
int main().
int main(int,char**).
Nasz najprostszy program
int main()
{
return 0.
}
jest deklaracj funkcji
main
. Rezultat tej funkcji jest rezultatem zakoczenia caego programu i jest przeka-
zywany do rodowiska w jakim uruchomiono program.
P aska struktura jzyka.
W jzyku C++ de nicje funkcji nie mog by zagniedzone, tzn. nie mona de niowa jednej funkcji w
drugiej. Poniszy fragment programu jest bdny.
int f(int i)
{
:
:
:
int g(int j)
{
:
:
:
}
:
:
:
}
Adres.
Zmienne i obiekty charakteryzuj si wasnoci ycia, tzn. w pewnych momentachpracy programuzaczynaj
istnie, a w innych przestaj y. Istnienie obiektu czy zmiennej zwizane jest m.in. z faktem umiejscowienia
w pamici. Moemy zatem mwi o
adresie
zmiennej lub obiektu.
Adres
uzyskujemy za pomoc operatora
&
, np.
int a=1.
cout<<"jestem a,"
"moja warto2! to"
<<a<<
", a adres "
<<&a<<'\n'.
moe by zapamitywany w zmiennych zwanych wska nikami. Wska nik do zmiennej
T a
deklarujemy
jako
T* pa
.
Sposb deklaracji opisuje sposb uycia
, tzn.
pa
reprezentuje wskazanie { warto typu
T*
*pa
reprezentuje warto wskazywanego obiektu czyli jest typu
T
wyraenie
*pa
zwizane jest z odczytaniem wartoci zmiennej o adresie
pa
, nazywa si
dereferencj
i
jest rwnowane
a
.
ponisze instrukcje maj te same znaczenie
a=2
i
*pa=2
.
int a=1.
int* pa=&a.
cout<<"jestem a,"
"moja warto2! to"
<<*pa<<
", a adres "
<<pa<<'\n'.
adres obiektu jest zawsze rny od zera. W zwizku z tym warto zero jest niewanym wskazaniem i
suy w programach do sygnalizacji braku wskazania.
Programowanie I
Wykad 7
39
dereferencja niewanego wska nika jest bdem niewykrywalnym przez kompilator, a w czasie realizacji
programu moe powodowa powane zakcenia w pracy programu.
ten sam adres moe by wielokrotnie wykorzystywany dla rnych zmiennych
w danej chwili adresy wszystkich istniejcych zmiennych
s rne
adres moe by
niewany
(kiedy zmienna przestaa ju istnie)
int* f()
{
int a=0.
return &a.
}
:
:
:
int* pa=f().
cout<<pa<<'\n'.
cout<<*pa<<'\n'.
b d
:
:
:
Tablice.
W C++ wska niki i tablice s ze sob cile powizane. Tablice, ktre deklarujemy za pomoc operatora
]
, np.
T t10]
, skada si z
n
(w naszym przypadku
n
= 10) egzemplarzy zmiennych typu
T
. Odwoujemy
si do nich take za pomoc
]
, np. niech
tab
bdzie tablic 10 liczb typu
int
, tzn. zostao zadeklarowane
jako
int tab10].
tab0]=2.
{ przypisanie pierwszemu elementowi tablicy wartoci 2
tab3]++.
{ zwikszenie czwartego elementu tablicy o 1
cout<<tab5].
{ wypisanie wartoci szstego elementu tablicy
elementy tablicy numerujemy liczbami cakowitymi
pierwszy element tablicy
ma numer 0
kompilator
nie sprawdza
zakresu indeksw, tzn. wyraenie
tab10]=0.
jest poprawne, ale moe
spowodowa powstanie bdu w programie podczas jego wykonania
kolejne elementy tablicy
s rozmieszczone bezporednio
po sobie
nazwa tablicy moe by uywana jako wska nik do pierwszego elementu tablicy, tzn. adresy
tab
i
&tab0]
s
identyczne
(co do wartoci i typu)
tablica moe by zadeklarowana bez okrelonego rozmiaru, np.
int tab]={1,0}.
{ tablica, ktrej elementami s liczby cakowite
Operacje na wskanikach.
Jeeli wska nik
T* p
wskazuje na
i
-ty element tablicy
T tabn]
, tzn.
p
&tabi-1]
tab+i-1
to
p+k
wskazuje na
i
+
k
-ty element tablicy, tzn.
p+k
&pk]
&tabi-1+k]
tab+i-1+k
.
Jeeli
p
jest wska nikiem, a
k
liczb cakowit to
*(p+k)
*(k+p)
pk]
Jeeli
p
i
q
s wska nikami tego samego typu
T*
to
p-q
jest odlegoci pomidzy
p
i
q
w tablicy, ktrej
elementy s typu
T
.
Napisy.
Pamitamy, e do reprezentacji pojedynczych znakw suy typ
char
. Kademu znakowi przyporzdkowano
liczb naturaln. Powstaje natychmiastowe pytanie ? Jak reprezentowany jest napis ?
Napisy s cigami znakw i reprezentowane s przez tablice elementw typu
char
. Koniec napisu jest
zaznaczony liczb
0
, ktra nie jest przyporzdkowana adnemu znakowi. Zatem
"abcde"
jest zapamitane
w 6{cio elementowej tablicy o elementach
char
kolejno rwnych
'a'
,
'b'
,
'c'
,
'd'
,
'e'
i
0
.
Typem napisu
jest
char*
.
Przyk ad.
Ponisza funkcja wypisuje na ekranie monitora wszystkie znaki napisu
p
void pisz(char* p)
{
Programowanie I
Wykad 7
40
for ( . *p . p++ )
{
cout<<*p<<'\n'.
}
}
:
:
:
pisz("Hello world!").
:
:
:
Druga posta
main
.
Jak pamitamy funkcja
main
moe by zadeklarowana jako
int main(int argc,char** argv)
gdzie
argv
jest tablic o elementach typu
char*
, a wic bdcych napisami { argumentami wywoania
programu, przy czym
argv0]
jest nazw programu$ natomiast
argc
rozmiarem tablicy.
Co wicej
argvargc] == 0
.
Poniszy program wypisuje na ekranie monitora argumenty z jakimi zosta wywoany.
int main(int,char** argv)
{
for ( . *argv. argv++ )
cout<<*argv<<'\n'.
return 0.
}
Zadania
1.
Czy rezultatem pracy programu bdzie wypisanie na ekranie monitora dwch identycznych wierszy ?
#include <iostream.h>
int* f()
{
int a=1.
cout<<&a<<" "<<a<<'\n'.
return &a.
}
int main()
{
int* pa=f().
cout<<pa<<" "<<*pa<<'\n'.
return 0.
}
2.
W programie rozwizujcym rwnanie kwadratowe korzystalimy ze standardowej funkcji
sqrt
oblicza-
jcej pierwiastek kwadratowy. Prosz zmody kowa program piszc wasn funkcj obliczania pierwia-
stka kwadratowego
double Sqrt(double).
.
a) Wskazwka. Zastosowa iteracyjny wzr Newtona obliczania pierwiastka kwadratowego:
p
x
= lim
n!1
a
n
gdzie cig (
a
n
) zde niowany jest nastpujco
a
0
= 1
a
n+1
= (
a
n
+
x
a
n
)
=
2
:
Wykorzysta monotoniczno cigu (
a
n
).
Programowanie I
Wykad 7
41
b) Zastanowi si nad szybkoci zbienoci powyszej procedury. Czy biorc pod uwag fakt, e liczby
s reprezentowane w postaci zmiennopozycyjnej mona polepszy zbieno.
3.
Napisa wasne odpowiedniki funkcji
a)
int StrLen(char*)
{ oblicza dugo napisu w znakach,
b)
int StrCmp(char* l,char* p)
{ porwnuje napis
l
z
p
. Jeeli napisy s jednakowe zwraca 0,
jeeli
l
jest przed
p
przy uporzdkowaniu alfabetycznym zwraca -1, jeeli po 1,
c)
void StrCpy(char* d,char* s)
{ kopiuje napis z tablicy
s
do
d
,
d)
void StrCat(char* d,char* s)
{ dopisuje napis
s
na kocu napisu
d
.
4.
Napisa funkcj
int Str2Double(char* s,double* d)
sprawdzajc czy napis przedstawia liczb rzeczywist postaci cyfry, kropka dziesitna, cyfry, przy
czym cz cakowit lub uamkow mona opuci. Jeeli napis przedstawia liczb, to reprezentowana
warto jest zapisywana do zmiennej o podanym adresie i rezultatem funkcji jest liczba 1. W przeciwnym
wypadku rezultatem jest liczba 0.
5.
W oparciu o funkcj
Str2Double
napisa prosty program kalkulatora (np. o nazwie
kalk
) liczcego w
Odwrotnej Notacji Polskiej, wykonujcego cztery podstawowe dziaania arytmetyczne
+
,
-
,
*
i
/
oraz
pierwiastkowanie
v
(w oparciu o rezultaty zadania 2), o przykadowym uyciu
kalk 1 1 +
7!
2
kalk 1 0 /
7!
b$,d - dzielenie przez zero
kalk 1 1 + 1 1 + * v
7!
2
Program powinien wykrywa
a) dzielenie przez zero
b) pierwiastkowanie liczby ujemnej
c) niewystarczajc liczb argumentw dla wykonania operacji
d) bdne argumenty dla wykonania operacji
Programowanie I
Wykad 8
42
Zmienne automatyczne vs dynamiczne.
Identy kator zmiennej automatycznej posiada nastpujce korzystne wasnoci
zawiera informacje o adresie obiektu (zmiennej),
zawiera informacje o rozmiarze i sposobie reprezentacji danych w obiekcie (zmiennej),
gwarantuje, e obiekt (zmienna) istnieje.
Oprcz tego posiada cechy, ktre na og s postrzegane jako wady (albo przynajmniej ograniczaj stosowanie
zmiennych automatycznych). Mianowicie
czas istnienia zmiennej jest ograniczony do bloku, w ktrym zadeklarowano identy kator,
liczba zmiennych jest okrelona w momencie pisania programu.
Zmienne dynamiczne przeamuj t barier { czas ich ycia oraz liczba nie s ograniczone przez struktur
programu a tylko przez tre. Jednak wymagao to wysokiej ceny albowiem
zmienne dynamiczne nie maj identy katorw. Korzysta z nich mona tylko przy pomocy wska nikw
lub referencji (o ktrych za chwil powiemy).
informacja o typie zmiennej jest zawarta w typie wska nika (referencji). Nie mamy jednak moliwoci
stwierdzenia podczas realizacji programu co tak naprawd kryje si pod adresem zapamitanym we
wska niku. W wyniku nieostronego pisania programu moe si zday, e typ wska nika nie ma adnego
zwizku z typem wskazywanego obiektu! Co wicej,
wska nik (referencja) moe zawiera odniesienie do obiektu, ktry ju nie istnieje. W przypadku wska-
nika moe to by dodatkowo wskazanie puste.
Tworzenie i usuwanie zmiennych dynamicznych.
Zmienne dynamiczne tworzymy za pomoc operatora
new
. Rezultatem operacji
new T.
jest wskazanie do
obiektu, tj. warto
T*
. Jeeli utworzenie zmiennej byo z jaki powodw niemoliwe (np. zbyt mao
dostpnej pamici operacyjnej) to rezultatem operacji
new
bdzie albo wskazanie puste
0
albo zgoszenie
sytuacji wyjtkowej. Wybr metody zaley od implementacji jak rwnie moe dodatkowo zosta okrelony
przez programist.
Aby utworzy
n
{elementow tablic elementw
T
naley posuy si instrukcj
new Tn].
. W tym wypadku
rezultatem jest wskazanie do pierwszego elementu tablicy. Prosz zwrci uwag, e zmienne dynamiczne (w
przeciwiestwie do automatycznych) umoliwiaj tworzenie tablic, ktrych wielko moe zosta okrelona
dopiero podczas realizacji programu.
W celu usunicia zmiennej dynamicznej suy operator
delete
. Jego argumentem jest rezultat wykonania
instrukcji
new
. Poniszy fragment programu ilustruje utworzenie zmiennej dynamicznej potra cej reprezen-
towa liczby cakowite (
int
), wykorzystanie jej w celu obliczenia wartoci wyraenia i wypisania rezultatu
na ekranie oraz usunicie.
int* pi = new int. // tworz" zmienn, i jej adres zapami"tuj" we wska3niku pi
*pi = (1 + 2) * 3 - 4.
cout<<"warto2! wyra+enia = "<<*pi<<"\n".
delete pi. // usuwam zmienn, dynamiczn,
Operator
delete
nie zmienia wartoci swego argumentu. Zatem bezporednio po wykonaniu instrukcji
delete pi.
warto
pi
jest taka sama jak przed wykonaniem tej instrukcji i zawiera
niewany
adres. Po-
suenie si tym wskazaniem (np.
*pi = 12.
) jest bdem i najczciej ma katastrofalne skutki dla programu,
ktre co gorsza mog zosta zauwaone dopiero po pewnym czasie.
Komputer nie jest w stanie odrni czy wska nik odnosi si do pojedynczego obiektu czy te jest wskaza-
niem pierwszego elementu tablicy. Dlatego przy usuwaniu tablic naley posuy si nieco zmienion form
operatora
delete
.
int* ti=new int10]. // tworz" 10-elementow, tablic" element*w int
// korzystam z niej
:
:
:
delete] ti. // i usuwam
W rzeczywistoci wska nik zawiera jedynie sam adres. Typ obiektu, do ktrego si odnosi jest zwizany z
typem samego wska nika. Istniej wska niki typu
void*
, ktre nie zawieraj adnej informacji o obiekcie
Programowanie I
Wykad 8
43
oprcz jego adresu (bowiem nie istniej obiekty typu
void
). Kade wskazanie moe by przeksztacone do
void*
int* pi=new int.
void* pv.
pv=pi.
ale przypisanie w odwrotnym kierunku jest ju bdem. Podobnie kompilator broni si przed przypisaniami
wskaza rnych typw.
int* pi=new int.
void* pv=pi.
float* pf=pi. // b$,d, argumenty s, wska3nikami do wielko2ci r*+nych typ*w
pf=pv.
// b$,d, pv nie zawiera informacji o typie - przypisanie mog$oby
// by! niepoprawne
Podobnie dereferencja wskazania
*pv
jest bdem. Na wska nikach
void*
nie mona take przeprowadza
operacji arytmetycznych jak
pv=pv+1.
.
Adres obiektu jest liczb cakowit. Co wicej, jeden z adresw jest wyrniony i odpowiada mu wskazanie
puste (
0
) { tzn. mamy gwarancj, e aden obiekt nie bdzie umieszczony pod tym adresem. Jeeli
p
jest
wskazaniem do
i
{tego elementu tablicy to
p+1
jest wskazaniem do nastpnego, tj.
i
+1 elementu. Tak samo
jeeli
p1
i
p2
s odpowiednio wskazaniami do pierwszego i drugiego elementu tablicy to wyraenie
p2-p1
ma warto 1. Jest to odlego pomidzy elementami tablicy wyraona w elementach tablicy i na og ma
zupenie inn warto ni rnica liczb odpowiadajcych
p1
i
p2
.
int tab2].
int* p1=&tab0].
// p1 = adres pierwszego elementu tablicy
int* p2=&tab1].
// p2 = adres drugiego elementu tablicy
cout<<p2-p1<<"\n".
// to b"dzie warto2! 1, p2 jest nast"pnikiem p1
cout<<long(p2)-long(p1)<<"\n". // a tutaj najcz"2ciej b"dzie 2 lub 4
Referencje.
Referencje s czsto okrelane jako inna nazwa obiektu. W swoim zachowaniu wykazuj podobiestwo do
wska nikw
bowiem odnosz si do innego obiektu (automatycznego lub dynamicznego),
nie s czue na fakt, e by moe obiekt przesta istnie
jak i do zmiennych automatycznych
gdy odwoujc si do referencji odwoujemy si tak jak do zmiennej automatycznej. Tylko inicjacja ma
w tym wypadku specjalne znaczenie.
int& ri=*new int.
ri=1. // referencji u+ywamy tak jak zmiennych automatycznych
cout<<"adres zmiennej i = "<<&ri<<"\n".
delete &ri.
// w tym miejscu referencja jest ju+ niewa+na
Deklaracja referencji wymaga zawsze inicjacji. Inaczej byaby ona cakowicie bezuyteczna. Dziki referen-
cjom moemy elegancko tworzy funkcje, ktre mog przekazywa swoje rezultaty przez argumenty.
void zwieksz(int& ri)
{
ri++.
}
:
:
:
int i=0.
zwieksz(i).
cout<<i<<"\n". // warto2! i wynosi teraz 1
Programowanie I
Wykad 8
44
Rekurencja.
W jzyku C++ funkcja moe (bezporednio lub porednio) wywoa sam siebie. Typowym zagadnieniem
ilustrujcym ten mechanizm jest obliczenie wartoci silni { jeeli
n
>
1 to
n
! =
n
(
n
;
1)!, ponadto pamitaj,
e 1! = 1. Realizacj tego postpowania moe by nastpujcy program
int silnia(int n)
{
return n>1 ? n * silnia(n-1) : 1.
}
:
:
:
// potrzebuj" obliczy! 4!
cout<<"4! = "<<silnia(4)<<"\n".
W momencie wywoania
silnia(4)
warto lokalnej zmiennej
n
wynosi 4. Ale za chwil funkcja silnia jest
wywoana jeszcze raz, teraz z argumentem rwnym 3, ktry te zostanie zapamitany w lokalnej zmiennej
n
. Ale przecie nie moe to by ta sama zmienna, gdy wtedy stracilibymy aktualn warto 4, ktra
jest jednym ze skadnikw iloczynu bdcego rezultatem. Zatem jak to si dzieje, e program realizuje si
poprawnie?
Wcielenie funkcji.
W momencie wywoania funkcji zostaje utworzone jej wcielenie (ang. instance). To wanie ono jest odpo-
wiedzialne za utworzenie zmiennych lokalnych i zapamitanie miejsca programu, z ktrego funkcja zostaa
wywoana, i do ktrego naley powrci po zakoczeniu jej realizacji. W omawianym przypadku
silnia(4)
tworzone s 4 wcielenia funkcji. Mamy zatem 4 zmienne lokalne
n
bdce argumentami mnoenia.
n=4
n=3
n=2
n=1
{
return n>1 ?
n*silnia(n-1):
1;
}
{
return n>1 ?
n*silnia(n-1):
1;
}
{
return n>1 ?
n*silnia(n-1):
1;
}
{
return n>1 ?
n*silnia(n-1):
1;
}
Mechanizm rekurencji naley stosowa w sposb przemylany. &atwo bowiem napisa poprawny logicznie
program, ktry bdzie praktycznie nieuyteczny ze wzgldu na bardzo dugi czas realizacji wynikajcy z
zastosowania rekurencyjnych wywoa procedur. W celu ilustracji tego zagadnienia sprbujmy przy pomocy
rekurencji rozwiza znany nam problem obliczania liczb Fibonacciego. Pamitamy, e
f
0
=
f
1
= 1
f
n
=
f
n;1
+
f
n;2
dla
n
2. Realizacja jest natychmiastowa.
int Fibonacci(int n)
{
return n<2 ? 1 : Fibonacci(n-1) + Fibonacci(n-2).
}
:
:
:
cout<<"f(4) = "<<Fibonacci(4)<<"\n".
W tym wypadku liczba tworzonych wciele ronie wykadniczo wraz z
n
i dla
n
= 4 wynosi 9, dla
n
= 10
177, dla
n
= 20 21
891, za dla
n
= 30 2
692
537. Z drugiej strony zaprezententowany podczas trzeciego
wykadu program, wymaga dla obliczenia wartoci
n
{tego wyrazu cigu Fibonacciego tylko
n
dodawa.
Programowanie I
Wykad 8
45
n=2
n=1
n=1
n=2
n=4
n=3
n=0
n=1
n=0
Obliczanie wartoci silni daje si take zrealizowa bez stosowania rekurencji. Czy zatem mechanizm ten jest
tylko zbdnym dodatkiem, ktrego uycie moe nam co najwyej sprawi kopot? Wydaje si, e taka ocena
jest niesuszna. Rekurencja umoliwia proste i przejrzyste zapisanie pewnej (by moe niezbyt szerokiej)
klasy zagadnie i warto o niej pamita.
Zastanwmy si nad nastpujcym zadaniem: napisa funkcj porwnujc dwa napisy. Rezultatem jej
powinna by najmniejsza liczba operacji (zmiany, dopisania lub usunicia znaku) jakich naley dokona w
pierwszym napisie aby sta si identyczny z drugim.
Pamitajc, e napisy w jzyku C++ reprezentowane s przez tablice elementw
char
oraz, e ostatnim
elementem jest liczba
0
piszemy.
int podobne( char* l, char* p )
{
while ( *l == *p )
{
if ( !*l ) return 0.
l++.
p++.
}
// sprawdzamy czy nie doszli2my do ko-ca kt*rego2 z napis*w
if ( !*l ) return 1 + podobne( l
, p + 1 ).
if ( !*p ) return 1 + podobne( l + 1, p
).
// pr*bujemy trzech mo+liwo2ci
// a) w jednym z napis*w zamieniamy bie+,cy znak tak aby zgadza$ si" z drugim
int p1 = podobne( l + 1, p + 1 ).
// b) z lewego napisu usuwamy bie+,cy znak (albo w prawym wstawiamy)
int p2 = podobne( l + 1, p
).
// c) to samo co b) ale dla drugiego argumentu
int p3 = podobne( l
, p + 1 ).
// obliczamy najmniejsz, z liczb p1, p2 i p3
if ( p2 < p1 ) p1 = p2.
if ( p3 < p1 ) p1 = p3.
return 1 + p1.
}
Zadania
6.
Zmody kowa funkcj
podobne
w taki sposb aby zamiana dwch kolejnych znakw (np.
zs
zamiast
sz
) bya traktowana jako 1 bd zamiast dotychczasowych 2.
Programowanie I
Wykad 9
46
Nieprzewidziane sytuacje.
Piszc program lub jego cz zakadamy, e bdzie uytkowany zgodnie z odpowiednimi zasadami. Przyka-
dowo, funkcja obliczajca pierwiastek kwadratowy (zadanie z wykadu 6) wymaga nieujemnego argumentu,
gdy tylko wtedy operacja ta ma sens. Co jednak zrobi jeeli w czasie pracy programu zostanie wywoana
z argumentem ujemnym? Wywoanie takie wiadczy o bdzie w samym programie albo o bdnych danych
(np. wspczynnikach rwnania kwadratowego, ktre nie ma rozwiza rzeczywistych).
Schowaj g ow w piasek.
Jednym ze sposobw rozwizania takiego problemu jest nie robienie niczego. Funkcja obliczajca pierwiastek
kwadratowy zwraca w przypadku ujemnego argumentu liczb przypadkow albo ustalon (np. 0). Wbrew
pozorom takie rozwizania wcale nie nale do rzadkoci. S niekorzystne z tego wzgldu, e realizacja
programu przebiega bez zakce ale otrzymane wyniki s bezwartociowe i nie mamy adnego ostrzeenia
przed tym faktem.
Przerwij prac programu.
Lepszym rozwizaniem jest natychmiastowe zakoczenie pracy programu, skoro i tak wyniki bd niepo-
prawne. Dodatkowo, na ekranie monitora mona wypisa stosowny komunikat, ktry bdzie pomocny przy
lokalizacji bdu. W jzyku C++ natychmiastowe zakoczenie pracy programu mona uzyska przez wywo-
anie jednej z dwch funkcji
exit(int i)
{ program koczy prac, a do rodowiska, z ktrego zosta uruchomiony przekazuje warto
argumentu
i
, ktra moe by dodatkowym sposobem identy kacji rodzaju bdu
abort()
{ uywana w przypadku powanych bdw, wiadczcych o wadach w konstrukcji programu.
W niektrych rodowiskach (np. systemie Unix) oprcz zakoczenia pracy programu zapamitywany jest
jego stan przed zakoczeniem co umoliwia pniejsze \podejrzenie" za pomoc specjalnych narzdzi
tzw. debuggerw.
W zwizku z tym funkcja obliczajca pierwiastek mogaby mie nastpujcy pocztek
double Sqrt(double d)
{
if (d<0)
{
cout<<"Sqrt : ujemny argument\n".
exit(1).
// z funkcji exit nie ma powrotu - program przesta$ istnie!
}
:
:
:
}
Informuj o b dzie ale nie przerywaj pracy.
Wstrzymanie pracy programu w odpowiedzi na pojawienie si sytuacji wyjtkowej jest czsto nie do przy-
jcia. Wyobramy sobie nieco zmody kowany program rozwizujcy rwnanie kwadratowe. Prbuje on
odczyta trzy liczby bdce wspczynnikami rwnania, a nastpnie wypisuje dwie liczby bdce rozwiza-
niami. Procedura jest powtarzana a do odczytania pierwszego wspczynnika rwnego 0. Dziki temu
moemy rozwiza wiele rwna jednym uruchomieniem programu. W tym celu naley zapamita wsp-
czynniki rwna w pliku i uruchomi program w taki sposb aby czyta dane z pliku zamiast z klawiatury,
a rezultaty zapisywa nie na ekran ale do innego, wskazanego pliku.
Wystarczy, e jedno z rwna nie ma rozwiza rzeczywistych i wstrzymanie pracy programu pozbawia
nas wielu (moe nawet wszystkich) wynikw. Wyjciem z tej sytuacji jest takie sygnalizowanie bdw,
ktre jednoczenie nie wstrzymuje pracy programu. Mona to osign przez wprowadzenie zmiennej (np.
wystapil_blad
) i umwienie si, e warto tej zmiennej rna od zera wiadczy o bdzie. Wtedy nasza
funkcja
Sqrt
przyjmie posta
double Sqrt(double d)
{
if (d<0)
Programowanie I
Wykad 9
47
{
cout<<"Sqrt : ujemny argument\n".
wystapil_blad = 1.
return 0. // musimy zwr*ci! jak,2 warto2!, np. 0
}
:
:
:
}
za w samym programie naley dopisa sprawdzanie stanu tej zmiennej
int main()
{
while (1)
{
double a,b,c.
cin>>a>>b>>c.
if (!a) break.
// pocz,tek nowych oblicze- - odpowiednio inicjujemy sygnalizator b$"d*w
wystapil_blad = 0.
// oblicz rozwi,zania
:
:
:
// sprawdzamy czy wszystko w porz,dku
if (wystapil_blad)
cout<<"niepoprawne dane, w czasie oblicze- wyst,pi$ b$,d\n".
else
cout<<"x1 = "<<x1<<", x2 = "<<x2<<"\n".
}
return 0.
}
Powyszy przykad ilustruje istotn zasad.
Sygnalizacja b dw wymaga wstpnego ustalenia spo-
sobu przekazywania informacji.
W systemie Unix w przypadku wywoa tzw. funkcji systemowych, ktre m.in. umoliwiaj odczytanie
czy zapisanie danych odpowiednio z lub do pliku, utworzenie nowego podkatalogu, uruchomienie innego
programu, wprowadzono specjaln zmienn cakowit
errno
(ang. error number), ktrej warto opisuje
ostatnio powstay bd. Liczba 0 odpowiada poprawnemu wykonaniu natomiast inne wartoci sygnalizuj
bd i identy kuj jego rodzaj, albowiem kadej liczbie rnej od 0 odpowiada konkretny powd niepo-
wodzenia. Programy pracujce pod kontrol tego systemu mog i powinny po kadym wywoaniu funkcji
systemowej sprawdza warto zmiennej
errno
.
Przyjcie podobnego mechanizmu w odniesieniu do wyrae arytmetycznych byoby conajmniej kopotliwe i
mogo powodowa dalsze bdy. Wyobramy sobie nastpujc sytuacj
double a=1.
double b=-2.
double c=a/Sqrt(b).
Nasza procedura
Sqrt
wykryje ujemn warto argumentu i w rezultacie zwrci 0 powodujc nastpny
bd dzielenia. Z kolei dzielenie jest operacj zapewnion przez jzyk i nie moemy go zmody kowa, a
sprawdzenia typu
double a=1.
double b=-2.
double c=Sqrt(b).
if (c==0)
{
cout<<"dzielenie przez zero\n".
wystapil_blad = 1.
Programowanie I
Wykad 9
48
}
else c=a/c.
zatracaj przejrzysto programu, atwo o nich zapomnie lub popeni przy ich pisaniu dodatkowy bd.
Ustalono zatem wartoci, ktre mog by reprezentowane przez zmienne typu
double
czy
float
, ale maj
specjalne znaczenie, m.in.
NaN
{
nie liczba
(ang.
not a number
),
+Inf
,
-Inf
(
niesko czono
, ang.
innity
)
{ przekroczenie zakresu oblicze.
Jeeli dany komputer stosuje powysze rozwizanie to rezultatem instrukcji
cout<<"sqrt(-2) = "<<sqrt(-2)<<"\n"
bdzie napis
sqrt(-2) = NaN
. Co wicej, warto ta moe by argumentem dla innych operacji, ktre w
wyniku take dadz
NaN
, czyli
cout<<"1/sqrt(-2) = "<<1/sqrt(-2)<<"\n"
wypisze na ekranie
1/sqrt(-2) = NaN
. Ten sposb obsugi sytuacji wyjtkowych nie wymaga od nas adnego
sprawdzania poprawnoci w omawianymprogramie rozwizywania rwnania kwadratowego. Po prostu, jeeli
dane wejciowe opisuj rwnanie bez rozwiza rzeczywistych to wynikiem bdzie wiersz postaci
x1 = NaN, x2 = NaN
W poszukiwaniu wsplnego jzyka.
Bardzo rzadko jestemy autorami caego programu. Zwykle korzystamy z wielu bibliotek (chociaby w celu
obliczenia pierwiastka czy wypisania informacji na ekranie), ktre na og pisane byy przez niezalene grupy
osb. Chcielibymy jednak mie moliwo wykrywania sytuacji wyjtkowych. Czy zatem istnieje moliwo
ustalenia wsplnego sposobu przekazywania takich informacji.
Wydaje si, e problemu tego nie mona rozwiza bez wprowadzenia specjalnych mechanizmw do samego
jzyka. Posugiwanie si metod wartoci ustalonych zmiennych jest bardzo nieefektywne poniewa
nowa wersja biblioteki moe stosowa inne (na og lepsze) mechanizmy powodujc, e poprawne i
uyteczne programy potrzebne do naszej pracy przestaj nagle dziaa,
atwo zapomnie o sprawdzeniu poprawnoci,
a w przypadku, kiedy korzystamy z kilku bibliotek, z ktrych kada przekazuje informacje o bdach w
inny sposb, atwo si pogubi.
Chcielibymy zatem aby sam jzyk umoliwia informowanie o sytuacjach wyjtkowych, ktre byoby
jednolite,
atwe w uyciu { abymy nie obawiali si, e zapomnielimy czego sprawdzi.
Przez pewien czas autorzy jzyka ignorowali ten problem. Nie byo to jednak dobre rozwizanie bowiem
twrcy bibliotek i tak wymylali wasne (na og nie przystajce do innych) sposoby informowania o bdach.
Ale to ju historia. Obecnie C++ umoliwia sygnalizowanie wystpienia sytuacji wyjtkowych w jednolity
sposb.
Jeeli jest b d to informuj o nim
:
:
:
Dowolna cz programu po napotkaniu bdu, z ktrym nie potra samodzielnie si upora i kontunuowa
dalsz prac moe
zg osi sytuacj wyjtkow
. Do tego celu suy sowo kluczowe
throw
. Jego argumen-
tem jest zmienna lub obiekt, ktra umoliwia hierarchiczn obsug takich sytuacji (co zostanie dokadniej
przedstawione przy omawianiu obiektw). Nasza procedura
Sqrt
moe jako argument opisujcy bd poda
napis informacyjny.
double Sqrt(double d)
{
if (d<0)
{
throw "Sqrt : ojej, m*j argument jest ujemny !".
}
:
:
:
}
Programowanie I
Wykad 9
49
Sposb dziaania
throw
jest zbliony do polecenia
return
. Oprcz zapamitania informacji o bdzie na-
stpuje natychmiastowy powrt z funkcji, ktra zgosia wyjtek. Mona nawet powiedzie, e to jest \bar-
dziej oglne"
return
, poniewa bd nastpowa natychmiastowe powroty ze wszystkich aktualnie wyko-
nywanych funkcji (tzn. z funkcji, ktra wywoaa
Sqrt
, i z funkcji, ktra wywoaa t funkcj, itd.), a do
momentu gdy, ktra z funkcji bdzie potra a i chciaa obsuy sytuacj wyjtkow. Jeeli tak si nie stanie
to praca programu zostanie przerwana. (Pierwsz funkcj wywoan w kadym programie jest
main
, powrt
z niej to zakoczenie pracy programu.)
:
:
:
w nadziei, e zostanie zauwaony.
Z obsug sytuacji wyjtkowych zwizane s sowa kluczowe
catch
i
try
. Sposb ich uycia ilustruje na-
stpujcy przykad.
int main()
{
while (1)
{
try
{
double a,b,c.
cin>>a>>b>>c.
if (!a) break.
// rozwi,zuj r*wnanie jak dla poprawnych danych
// je+eli wyst,pi b$,d to zostanie zg$oszony
:
:
:
// je+eli zg$oszono b$,d, to realizacja nie dojdzie tutaj
cout<<"x1 = "<<x1<<", x2 = "<<x2<<"\n".
}
// obs$u+ b$"dy, kt*rych argumenty s, napisami
catch (char* informacja)
{
cout<<"wyst,pi$ b$,d : "<<informacja<<"\n".
}
}
return 0.
}
Dziki parze
try
i
catch
mamy logiczne powizanie czynnoci ze sposobami reagowania na bdy powstae
podczas realizacji tych pierwszych. W powyszym programie wyapane zostan tylko sytuacje zgoszone z
argumentem bdcym napisem. Inne zgoszenia spowoduj natychmiastowe przerwanie pracy programu.
Zadania
7.
Uruchomi przedstawiony program rozwizywania rwnania kwadratowego w rodowisku Unix (np. na
komputerze studenckim
tempac
) i samodzielnie przetestowa wyniki oblicze wyrae typu \dzielenie
przez zero" oraz zgaszanie wyjtkw w C++.
1
1
Kompilator jzyka C++ uruchamiamy poleceniem
CC
. Jeeli program rdowy zosta zapisany w pliku
nazwa.cc
to chcc uzyska program wynikowy naley wyda polecenie
CC -o nazwa nazwa.cc
, w rezultacie
ktrego (o ile program jest poprawny) zostanie utworzony plik
nazwa
.
Programowanie I
Wykad 10
50
Klasy i obiekty.
Klasy su do przedstawiania poj, ktre nie maj bezporedniej reprezentacji w jzyku (np. liczby zespo-
lone). Z jednej strony umoliwiaj dostarczenie interfejsu opisujcego pojcie i sposb jego wykorzystania,
a z drugiej pozwalaj na ukrycie szczegw implementacyjnych przed uytkownikami. &cz w sobie repre-
zentacj poj ktre opisuj wraz z czynnociami jakie mona wykonywa w odniesieniu do tych poj.
W tym miejscu warto zwrci uwag na terminologi przyjt w jzyku C++. Sformuowanie
klasa
zwizane
jest z opisem danego pojcia, natomiast
obiekt
odnosi si do konkretnego egzemplarza klasy utworzonego
zgodnie z podan tam de nicj. Tak wic w programie wystpuje na og wiele obiektw tej samej klasy.
Prawie kady jzyk programowania umoliwia reprezentowanie liczb. W C++ mamy a kilka reprezentacji:
liczb cakowitych i rzeczywistych, o mniejszej lub wikszej dokadnoci. Jednak sama moliwo dekla-
rowania zmiennych bez zapewnienia operacji arytmetycznych byaby praktycznie bezwartociowa. Zatem
z moliwoci reprezentowania liczby czymy operacje jakimi moemy si posugiwa. To poczenie od-
powiada koncepcyjnie pojciu klasy. Co wicej, nikogo nie trzeba przekonywa, e dodanie dwch liczb
rzeczywistych (np.
double
) jest z punktu widzenia algorytmu dodawania zupenie czym innym ni suma
dwch liczb cakowitych (np.
int
). Dodawanie nie jest uniwersaln operacj { jest zwizane z konkretnym
obiektem. Przyjto je oznacza wsplnym symbolem
+
poniewa niezalenie od typu liczby odnosi si do
tego samego pojcia.
Liczby zespolone.
W jzyku C++ nie ma wbudowanej reprezentacji liczb zespolonych. Fakt ten nie stanowi jednak adnego
ograniczenia, poniewa uytkownik moe samodzielnie skonstruowa klas reprezentujc liczby zespolone.
1
Liczby zespolone mona zapisa w rny sposb, np. podajc cz rzeczywist i urojon, albo wykorzystujc
posta trygonometryczn. W dalszej czci posuymy si pierwszym sposobem zapisu. W zwizku z tym,
do przedstawienia liczby zespolonej potrzebujemy dwch liczb rzeczywistych. Mona to rozwiza deklarujc
zawsze pary zmiennych
double
, np.
// potrzebuj" zapami"ta! liczb" zespolon,
// deklaruj" dwie zmienne dla reprezentowania cz"2ci rzeczywistej i urojonej
double z_re, z_im.
ale takie rozwizanie jest bardzo prymitywne. Chcielibymy mc napisa co podobnego jak w przypadku
liczb cakowitych czy rzeczywistych
// potrzebuj" zapami"ta! liczb" zespolon,, wi"c deklaruj" j,
complex z.
Jednak kompilator nie zna pojcia
complex
. Musimy je zde niowa
class complex
{
public:
double re.
double im.
}.
Powysza de nicja opisuje klas
complex
, ktra skada si z dwch zmiennych typu
double
o nazwach
re
i
im
, do ktrych moemy si odwoywa za pomoc operatora
.
(kropka). Chcc zadeklarowa zmienn
z
i
nada jej warto 1 + 2
i
piszemy
complex z.
z.re=1.
z.im=2.
Jednak w dalszym cigu posugiwanie si liczbami zespolonymi jest nieco kopotliwe. Kompilator nie rozumie
wyrae typu
z3 = z1 + z2.
czy
z3 = z1 * z2.
. Oczywicie moemy rozwiza ten problem operujc
bezporednio na skadowych, co dla dodawania jest jeszcze w miar proste
1
Prawie kada implementacja jzyka C++ dostarcza klas
complex
umoliwiajc posugiwanie si licz-
bami zespolonymi.
Programowanie I
Wykad 10
51
// chc" obliczy! sum" liczb zespolonych z1 i z2, a wynik zapisa! w z3
complex z3.
z3.re = z1.re + z2.re.
z3.im = z1.im + z2.im.
w przypadku mnoenia atwo popeni bd
// obliczam iloczyn z3 = z1 * z2
complex z3.
z3.re = z1.re * z2.re - z1.im * z1.im.
z3.im = z1.re * z2.im + z1.im * z2.re.
dzielenie wyglda beznadziejnie
// z3 = z1 / z2
z3.re = ( z1.re * z2.re + z1.im * z2.im ) / ( z2.re * z2.re + z2.im * z2.im ).
z3.im = ( z2.re * z1.im - z1.re * z2.im ) / ( z2.re * z2.re + z2.im * z2.im ).
za zapisanie wyraenia
z
5
=
z
1
(z
4
+z
3
)
z
2
+z
3
jest praktycznie niewykonalne.
Funkcje sk adowe.
Rozwizaniem powyszego problemu jest zde niowanie operacji takich jak dodawanie dla klasy
complex
.
To co dla liczb rzeczywistych (np.
double
) byo z gry dane przez sam jzyk musi w tym wypadku zosta
napisane przez programist. Jest to oczywicie dodatkowy wysiek dla piszcego program, ale jednoczenie
stanowi bardzo du zalet. Aby reprezentowa potrzebne pojcia moemy je de niowa, a nie budowa
nieudolnie w oparciu o wski zestaw elementw wbudowanych w jzyk!
Pamitajc, e operatory
+
,
=
, itd. s skrconymi nazwami funkcji
operator+
,
operator=
,
:
:
:
de niujemy
class complex
{
public:
double re.
double im.
complex& operator=(complex& z)
{
re = z.re.
im = z.im.
return *this.
}
complex operator+(complex& z)
{
complex suma.
suma.re = re + z.re.
suma.im = im + z.im.
return suma.
}
complex operator*(complex& z).
complex operator/(complex& z).
}.
complex complex::operator*(complex& z)
{
complex iloczyn.
iloczyn.re = re * z.re - im * z.im.
iloczyn.im = re * z.im + im * z.re.
return iloczyn.
}
Programowanie I
Wykad 10
52
complex complex::operator/(complex& z)
{
complex iloraz.
iloraz.re = (
re * z.re + im * z.im ) / ( z.re * z.re + z.im * z.im ).
iloraz.im = ( z.re *
im - re * z.im ) / ( z.re * z.re + z.im * z.im ).
return iloraz.
}.
dziki temu wspomiane wyraenie
z
5
=
z
1
(z
4
+z
3
)
z
2
+z
3
zapisujemy w naturalny sposb
z5 = z1 * ( z4 + z3 ) / ( z2 + z3 ).
Wyjanimy teraz co i dlaczego dopisalimy w de nicji klasy
complex
.
Jako pierwsza zostaa zde niowana jednoargumentowa funkcja
operator=
. Ale dlaczego jednoargumentowa,
skoro z operacj przypisania zwizane s dwa obiekty { z pierwszego pobieramy warto i nadajemy j
drugiemu.
operator=
jest funkcj skadow (metod) obiektu. Moemy j stosowa tylko w odniesieniu do konkretnego
obiektu, ktry jest w tym wypadku drugim, brakujcym argumentem. Skrtowy zapis
z1=z2.
odpowiada
z1.operator=(z2)
i jest wywoaniem funkcji
operator=
z argumentem
z2
na rzecz
z1
. Terminologia uy-
wana w innym obiektowym jzyku programowania { Smalltalk'u { opisuje to jako przesanie do obiektu
z1
komunikatu
=
z argumentem
z2
, co jest bardziej przemawiajce.
Wewntrz kadej funkcji skadowej moemy si posugiwa zmienn
this
, ktra zawiera wskazanie obiektu na
rzecz ktrego wywoano t funkcj (do ktrego przesano komunikat). Jest to specjalna zmienna { nie wymaga
deklaracji, a jej typem jest wskazanie do biecej klasy, czyli w naszym wypadku
complex*
. Dziki temu
mona odwoywa si do zmiennych obiektu, np.
this->re = 1.
. Poniewa odwoania takie s naturalne
zrezygnowano z koniecznoci stosowania
this
, o ile nie powoduje to niejednoznacznoci (np. istnieje lokalna
zmienna o takiej samej nazwie). Dziki temu w metodzie
operator=
moglimynapisa
re=z.re.
co powoduje
nadanie wartoci pola
re
argumentu
z
polu
re
obiektu, do ktrego przesano komunikat.
Rezultatem
operator=
jest referencja
complex&
, ktra odnosi si do obiektu na rzecz ktrego wykonano przy-
pisanie. Dziki temu moliwe jest nadanie wartoci
z1
kilku obiektom jednoczenie, np.
z3=z2=z1.
co, biorc
pod uwag prawostronne wizanie operatora
=
, jest rwnowane kolejnemu wykonaniu
z2.operator=(z1).
z3.operator=(z2).
.
Zastosowanie referencji w argumencie zapobiega zbdnemu kopiowaniu obiektw. Pamitamy, e w jzyku
C++ argumenty s przekazywane przez warto i s lokalnymi zmiennymi funkcji.
Rezultatem metody
operator+
jest obiekt typu
complex
. Wynika to z faktu, e skadniki dodawania (tzn.
obiekt, do ktrego przesano komunikat i argument) nie ulegaj zmianie. W zwizku z tym zadeklarowano
lokaln zmienn
suma
, ktrej przypisano wynik operacji, i ktra jest rezultatem. Uwany czytelnik moe by
zaniepokojony poniewa wiadomo, e czas ycia zmiennych lokalnych koczy si wraz z dojciem realizacji do
koca bloku, w ktrym wystpia deklaracja, co w omawianym przypadku odpowiada powrotowi z metody.
Jednak w przypadku obiektu bdcego rezultatem kompilator przedua czas jego ycia i usunie go troch
pniej kiedy ju nie bdzie potrzebny. Wobec tego zapis
z3=z1+z2.
ma sens.
Funkcje
operator*
i
operator/
zostay zadeklarowane w de nicji klasy, tzn. podano tylko typy argumentw
i rezultatw. Ich tre (de nicj) zapisano poza klas. W takim wypadku naley posuy si pen nazw
metody, skadajcej si z nazwy klasy i nazwy samej metody oddzielonych podwjnym dwukropkiem (np.
complex::operator*
). Generalnie funkcje skadowe klasy de niujemy poza klas (tak jak
operator*
).
De nicje wewntrz klasy stosujemy tylko wobec metod krtkich i bardzo czsto uywanych w programie.
Realizacja funkcji zde niowanej wewntrz klasy jest nieco szybsza ale wydua program, zatem nie naley
stosowa tego mechanizmu zbyt pochopnie.
Kontruktory i destruktory.
Wrd funkcji skadowych wyrniamy dwie podgrupy: konstruktory i destruktory. S one automatycznie
wykonywane odpowiednio podczas tworzenia i usuwania obiektu. Dziki temu pocztkowa warto obiektu
nie musi by przypadkowa.
Programowanie I
Wykad 10
53
double d.
d=(d+1)*(d+2).
complex z.
z=z*z.
cout<<"d = "<<d<<", z = ("<<z.re<<","<<z.im<<")\n".
Wynik powyszej instrukcji jest przypadkowy, a chyba nie o to nam chodzio { zapomnielimy nada wartoci
pocztkowych. Rozsdniej byoby aby niezainicjowana explicite zmienna miaa warto 0, albo aby mc
poda warto pocztkow w miejscu deklaracji.
W przypadku obiektw jest to osigalne przez zde niowanie odpowiednich konstruktorw (moe ich by
wiele). Jako warto pocztkow liczby zespolonej chcielibymy mc poda
par liczb rzeczywistych, np.
1,2
co odpowiadaoby 1 + 2
i
,
pojedyncz liczb rzeczywist, np.
1
co odpowiadaoby 1 + 0
i
,
w przypadku braku argumentw warto pocztkowa powinna wynosi 0,
inn liczb zespolon.
Rozwizaniem jest dopisanie nastpujcych funkcji skadowych
complex(double r,double i) : re(r), im(i)
{
}
complex(double r)
{
re = r.
im = 0.
}
complex() : re(0), im(0)
{
}
Nazwa konstruktora jest taka sama jak nazwa klasy. W powyszych przykadach pokazano dwa sposoby
inicjowania wartoci pocztkowych. Znaczenie obydwu jest identyczne, jednak sposb wykorzystujcy list
inicjacyjn
re(r), im(i)
jest korzystniejszy ze wzgldu na obsug sytuacji wyjtkowych. Tak wic warto
od razu przyzwyczai si do niego i stosowa, pamitajc, e kolejno elementw na licie inicjacyjnej musi
odpowiada kolejnoci deklaracji zmiennych w klasie.
Wyposaeni w konstruktory moemy deklarowa zmienne zespolone
complex z1(1,2). // z1 = 1 + 2*i
complex z2(3).
// z2 = 3 + 0*i
complex z3.
// z3 = 0 + 0*i
complex z4(z1). // z4 = 1 + 2*i
Ostatnie wyraenie
complex z4(z1)
moe budzi pewne zdziwienie. Przecie nie zadeklarowalimy kon-
struktora o argumencie
complex
. Odpowiedz jest nastpujc. Kada klasa automatycznie de niuje dwa
konstruktory: pusty i kopiujcy. W naszym wypadku s to
complex()
{
}
complex(const complex& z) : re(z.re), im(z.im)
{
}
To wasnie dziki temu ju na samym pocztku moglimy deklarowa obiekty klasy
complex
(chocia wtedy
ich pocztkowa warto bya jeszcze przypadkowa). Jeeli jednak programista samodzielnie zde niuje ktry
ze standardowych konstruktorw to ta de nicja staje si obowizujca (tak postpilimy de niujc
com-
plex()
, ktry zerowa skadowe
re
i
im
).
Programowanie I
Wykad 10
54
Podobnie moglimy postpi w przypadku konstruktora kopiujcego. Byoby to konieczne jeeli konstrukcja
wymagaaby czego wicej ni tylko skopiowanie wartoci poszczeglnych skadowych (np. skadowa byaby
wska nikiem do zmiennej dynamicznej wykorzystywanej przez obiekt). Ale skoro i tak de nicja naszego
konstruktora kopiujcego pokrywa si ze standardow to moglimy j pomin.
Konstruktory umoliwiaj uzyskanie duej elastycznoci w posugiwaniu si obiektami. Rozwamy takie oto
instrukcje.
double d=1.
complex z1(d).
complex z2=d.
Deklarujemy zmienn
double d
nadajc jej warto pocztkow 1. Nastpnie posugujemy si t zmienn
w celu zainicjowania obiektu
z1
. Klasa
complex
zapewnia konstruktor o typie argumentu
double
, zatem
wszystko jest w porzdku. Tak samo deklaracja
z2
nie budzi adnych zastrzee bowiem mamy take
konstruktor bezargumentowy. Ale przypisanie
z=d
jest chyba bdne. Nasz
operator=(complex&)
wymaga
referencji do obiektu
complex
, a
d
jest typu
double
. Na szczcie kompilator wie jak na podstawie zmiennej
double
utworzy obiekt
complex
bowiem mamy odpowiedni konstruktor. I taki obiekt zostanie utworzony.
Jego istnienie bdzie bardzo krtkie { tylko dla wykonania metody
operator=
. Przedstawiony mechanizm
upraszcza konstrukcj klasy. Nie musimy de niowa dodatkowych funkcji
=
dla argumentw
double
,
float
,
long
,
int
. (Dlaczego ?)
Przeciwiestwem konstruktora jest destruktor. Jego nazwa jest nazw klasy poprzedzon znakiem tyldy
~
.
Jest dokadnie jeden. Jeeli uytkownik nie zde niuje go to kompilator doda pust de nicj
~complex()
{
}
I tak wanie uczyni w przypadku klasy
complex
.
Jeszcze wicej elegancji
:
:
:
Wysiek woony w konstrukcj klasy
complex
da ju cakiem spore rezultaty. Moemy deklarowa obiekty
complex
tak jak zwyke zmienne, wicej, mamy pewno e pocztkowa warto nie jest przypadkowa. W
naturalny sposb moemy zapisywa wyraenia i to takie, gdzie obok liczb zespolonych wystpuj wielkoci
typu
double
czy
int
. Wci jednak zapisanie wartoci liczby na ekranie, czy odczytanie jej z klawiatury,
nie jest oczywiste.
Przede wszystkim musimy zdecydowa w jaki sposb bdziemy reprezentowa liczby zespolone na ekranie.
Wypisanie kolejno dwch liczb rzeczywistych nie jest poprawne bowiem nie mamy pewnoci czy s to dwie
niezwizane z sob liczby rzeczywiste czy liczba zespolona. Ponadto zapis powinien by w miar prosty
poniewa chcielibymy aby tak samo podawa liczby jako dane wejciowe { w szczeglnoci, aby rezultaty
pracy jednego programu zapisane do pliku mogy by danymi dla innego programu. Standardowo przyjto
zapisywa liczb zespolon podajc cz rzeczywist i urojon w nawiasach okrgych odzielone dodatkowo
przecinkiem, np. 1 + 2
i
zapisujemy jako
(1,2)
.
Chcc uzyska warto
z
na ekranie moemy napisa
complex z(1,2).
cout<<"z = ("<<z.re<<","<<z.im<<")\n".
Sposb ten jest rozwleky i atwo si w nim pomyli. Przyzwyczailimy si ju do zapisw typu
cout<<"d =
"<<d<<"\n"
i chcielibymy mc zrobi to tak samo. Cay kopot polega na tym, e klasa
ostream
zostaa
napisana zanim wymylilimy nasz klas
complex
i jej autorzy nie mogli doda skadowej typu
ostream&
operator<<(complex&)
. Co wicej nie mamy wersji rdowej tej klasy, a nawet gdybymy takow dyspo-
nowali to musielibymy j zmody kowa, a jak oglnie wiadomo prawdopodobiestwo tego e poprawiajc
co zrobimy to le jest bliskie 1. Czy istnieje zatem inne rozwizanie? Na szczcie tak! Moemy zde niowa
funkcj postaci
ostream& operator<<(ostream& os,complex& z)
{
os<<"("<<z.re<<","<<z.im<<")".
Programowanie I
Wykad 10
55
return os.
}
i z przyjemnoci pisa instrukcje takie jak
cout<<"z1 = "<<z<<", z2 = "<<z2<<"\n".
. Pozostaje jeszcze
napisa funkcj odczytujc liczby zespolone z klawiatury, tj.
istream& operator>>(istream& os,complex& z)
:
:
:
i bezpiecze stwa.
Zauwamy, e w tej chwili nie mamy ju potrzeby bezporedniego odwoywania si do skadowych
re
i
im
. Co
wicej, takie odwoania s mniej eleganckie, dusze, atwo wic co przeoczy i popeni bd. Np. widzc
wyraenie
complex z. z.re=3.
nie wiemy czy autor zdawa sobie spraw, e
z
zostanie automatycznie
nadana pocztkowa warto 0, w zwizku z czym po wykonaniu przypisania warto
z
bdzie rwna 3, czy
moe po prostu zapomnia nada wartoci urojonej. Kopotw takich nie mamy z deklaracj
complex z=3.
lub
complex z(3).
.
Nie moemy usun pl
re
i
im
ale moemy je ukry przed uytkownikami klasy. Generalnie moemy ukry
nie tylko pola ale i metody. Kade z nich jest jednego z typw
prywatne
(ang.
private
) { pola i metody dostpne s tylko w innych metodach tej samej klasy. Nie s
za dostpne dla uytkownika, tzn. kogo kto deklaruje obiekty tej klasy i z nich korzysta,
zabezpieczone
(ang.
protected
) { tak samo jak prywatne. Rnica polega na tym, e pola i ska-
dowe dostpne s take w klasach pochodnych. Do zagadnienia tego powrcimy przy okazji omawiania
dziedziczenia,
publiczne
(ang.
public
) { nie ma adnych ogranicze.
Standardowo jeeli pominiemy okrelenie atrybutu klasy to przyjmuje si atrybut
prywatny
. Odpowiednio
wstawiajc sowa kluczowe
public
,
protected
i
private
moemy dowolnie ustala atrybuty pl i skado-
wych.
Ostateczna wersja naszej klasy implementujcej liczby zespolone wyglda nastpujco.
class complex
{
private:
double re.
double im.
public:
complex(double r,double i) : re(r), im(i)
{
}
complex(double r) : re(r), im(0)
{
}
complex() : re(0), im(0)
{
}
complex& operator=(complex& z).
complex operator+(complex& z).
complex operator*(complex& z).
complex operator/(complex& z).
friend ostream& operator<<(ostream&,complex&).
friend istream& operator>>(istream&,complex&).
}.
complex& complex::operator=(complex& z)
{
re = z.re.
Programowanie I
Wykad 10
56
im = z.im.
return *this.
}
complex complex::operator+(complex& z)
{
complex suma.
suma.re = re + z.re.
suma.im = im + z.im.
return suma.
}
complex complex::operator*(complex& z)
{
complex iloczyn.
iloczyn.re = re * z.re - im * z.im.
iloczyn.im = re * z.im + im * z.re.
return iloczyn.
}
complex complex::operator/(complex& z)
{
complex iloraz.
iloraz.re = (
re * z.re + im * z.im ) / ( z.re * z.re + z.im * z.im ).
iloraz.im = ( z.re *
im - re * z.im ) / ( z.re * z.re + z.im * z.im ).
return iloraz.
}
ostream& operator<<(ostream& os,complex& z)
{
os<<"("<<z.re<<","<<z.im<<")".
return os.
}
Skadowe
re
i
im
zostay zadeklarowane z atrybutem
prywatny
w zwizku z czym nastpujce odwoanie
spoza klasy jest bdne.
complex z.
z.re=1.
Jednak musimy zapewni taki dostp funkcjom realizujcym wypisanie wartoci liczby na ekranie i czytanie
z klawiatury. Jest to moliwe poprzez podanie nazwy takiej funkcji (albo klasy) wewntrz de nicji klasy
complex
poprzedzonej sowem kluczowym
friend
. Deklaracja taka nie jest traktowana jako skadowa, a
jedynie jako sygna aby wobec wymienionych funkcji (klas) nie stosowa zasad ograniczania dostpu do
skadowych.
Programowanie I
Wykad 10
57
Zadania
8.
Napisa brakujc funkcj
istream& operator>>(istream&,complex&)
.
9.
Prosz zapozna si ze standardow implementacj liczb zespolonych dostarczon wraz z kompilatorem
i przy jej wykorzystaniu zmody kowa program kalkulatora bdcego tematem zadania z wykadu 6, w
sposb umoliwiajcy dokonywanie oblicze na liczbach zespolonych.
10.
Zaprojektowa klas
mod100
operujcych na liczbach naturalnych bdcych reszt z dzielenia przez 100.
Klasa powinna zapewni operacje
=
,
+
,
-
,
*
, moliwo wypisania wartoci obiektu na ekran i odczytania
z klawiatury.
11.
Zaprojektowa klas
data
umoliwiajc reprezentowanie dat. W szczeglnoci naley zadba aby przy
deklaracji obiektu mona byo poda
dzie
,
miesic
i
rok
. Pominicie roku powinno odpowiada przy-
jciu wielkoci wynikajcej z aktualnej daty. Dodatkowe pominicie miesica i dnia powinno analogicznie
przyjmowa wartoci biece. Ponadto prosz zapewni operacje
int dzien_tygodnia().
, ktrej re-
zultatem jest liczba z zakresu 0
:
:
:
6 odpowiadajca kolejno niedzieli, poniedziakowi, itd. oraz
int
odleglosc(data&).
podajca odlego w dniach pomidzy dwiema datami.
Programowanie I
Wykad 11
58
Lista dwukierunkowa.
Lista dwukierunkowa to struktura skadajca si z uporzdkowanego cigu elementw. Dla kadego ele-
mentu moemy uzyska dostp do
poprzednika
i
nastpnika
. Ponadto lista umoliwia uzyskanie dostpu do
pierwszego
i
ostatniego
elementu. Moliwe operacje to
usunicie
dowolnego elementu oraz
wpisanie
nowego
elementu za wskazanym.
W porwnaniu z tablic lista posiada zalety
jest struktur dynamiczn. Nie jest wymagane pocztkowe okrelenie maksymalnej liczby elementw
tak jak w przypadku tablicy.
operacje usunicia i wstawienia nowego elementu s w przeciwiestwie do tablicy bardzo efektywne.
jak i wady
nie posiada moliwoci indeksowania { odwoanie si to
i
{tego elementu listy, jak rwnie obliczenie
numeru elementu na podstawie wskazania nie s naturalnymi operacjami.
W celu implementacji listy zde niujemy dwie klasy pomocnicze. Pierwsza
LNode
bdzie reprezentowa
abstrakcyjny element listy, tzn. zawierajcy tylko wskazanie do swego nastpnika i poprzednika.
class LNode
{
private:
friend class DoubleNodedList.
LNode* Prev.
LNode* Next.
public:
LNode() : Prev(0), Next(0) {}
LNode* GetNext() { return Next. }
LNode* GetPrev() { return Prev. }
}.
Skadowa
Prev
zawiera wskazanie do poprzedajcego elementu lub
0
jeeli element nie ma poprzednika lub
nie jest jeszcze na licie. Analogicznie
Next
wskazuje na nastpnik.
Poniewa operacje na wska nikach s najczstsz przyczyn bdw w programach, skadowe
Prev
i
Next
zostay zadeklarowane jako prywatne, tzn. dostpne tylko w funkcjach skadowych klasy
LNode
. Dostp do
poprzednika i nastpnika jest jednak zwykle potrzebny w programach operujcych na listach. Wobec tego
zapewniono dwie proste funkcje
GetPrev
i
GetNext
, ktrych rezultatem s odpowiednie wskazania. Dziki
temu mamy moliwo odczytywania skadowych
Prev
i
Next
, ale nie moemy ich zmienia.
Zapewnienie penego dostpu do skadowych jest jednak niezbdne w odniesieniu do klasy implementujcej
sam list tj.
DoubleNodedList
. W tym celu posuono si specy katorem
friend
powodujcym, e klasa
DoubleNodedList
nie ma adnych ogranicze w dostpie do skadowych klasy
LNode
.
Konstruktor zeruje pola
Prev
i
Next
, tak e bezporednio po utworzeniu obiektu jego warto nie jest
przypadkowa i zgodna ze stanem faktycznym { nie jest on elementem adnej listy.
Z kolei klasa
DoubleNodedList
reprezentuje waciw list.
class DoubleNodedList
{
LNode* First.
LNode* Last .
int
Count.
public:
DoubleNodedList() : First(0), Last(0), Count(0) {}
int
GetCount() { return Count. }
LNode* GetFirst() { return First. }
LNode* GetLast () { return Last . }
void Delete(LNode* ANode).
void InsertAfter(LNode* AnAfter,LNode* ANewNode).
Programowanie I
Wykad 11
59
}.
void DoubleNodedList::Delete(LNode* ANode)
{
ANode->Next ? ANode->Next->Prev : Last = ANode->Prev.
ANode->Prev ? ANode->Prev->Next : First = ANode->Next.
Count--.
ANode->Next=0.
ANode->Prev=0.
}
void DoubleNodedList::InsertAfter(LNode* AnAfter,LNode* ANewNode)
{
ANewNode->Next = AnAfter ? AnAfter->Next : First.
ANewNode->Prev = AnAfter.
AnAfter ? AnAfter->Next : First = ANewNode.
ANewNode->Next ? ANewNode->Next->Prev : Last = ANewNode.
Count++.
}
Skadowa
First
zawiera wskazanie do pierwszego elementu listy lub
0
jeeli lista jest pusta. Analogicznie
Last
wskazuje na ostatni element. Zmienna
Count
zawiera liczb elementw na licie. Operacja odczytania
liczby elementw listy jest na tyle powszechna, e warto wprowadzi dodatkow skadow specjalnie dla tego
celu i aktualizowa j (co jest niezwykle proste) podczas operacji dodania i usunicia elementu. W celu
umoliwienia tylko odczytu zmiennych
First
,
Last
i
Count
(tak jak w klasie
LNode
) zadeklarowano je jako
prywatne, jednoczenie de niujc dodatkowe funkcje
GetFirst
,
GetLast
i
GetCount
.
Konstruktor odpowiednio inicjuje list, tak e pocztkowo jest pusta.
Funkcja
Delete
usuwa z listy element
ANode
, ktry przed t operacj powinien znajdowa si na tej licie.
Nie nastpuje sprawdzenie czy jest to element listy, z ktrej jest usuwany i czy w ogle jest to element
jakiejkolwiek listy. Funkcja
InsertAfter
dopisuje element
ANewNode
bezporednio za elementem
AnAfter
.
Jeeli
AnAfter==0
to element jest wstawiany na pocztek listy.
Przyk ad zastosowania.
Wyobramy sobie urzdzenie pomiarowe mierzce pewn wielko. Wyniki pomiarw s liczbami cako-
witymi przy czym wynikiem ostatniego pomiaru jest liczba 0. Naszym zadaniem jest dokonanie analizy
pomiarw. Dla jej przeprowadzenia warto dysponowa wszystkimi pomiarami. Zapamitanie ich w tablicy
jest niewygodne poniewa nie znamy z gry liczby pomiarw. Moe si zatem zdarzy, e albo bdziemy
tworzy bardzo due tablice dla niewielkich serii pomiarowych, albo jeeli bdziemy przydziela pami
ostronie, bdziemy zmuszeni do cigego powikszania tablicy. Oba rozwizania s nieefektywne: pierwsze
co do zasobw komputera, a drugie czasu realizacji programu. Lista jest w tym wypadku bardzo korzystnym
sposobem zapamitania informacji.
Dziedziczenie.
Niestety klasa
LNode
, ktra reprezentuje element listy nie potra zapamita liczby cakowitej. Potrzebujemy
klasy, ktra posiada wszystkie cechy
LNode
i potra dodatkowo pamita liczb cakowit. De niujemy klas
Pomiar
.
class Pomiar : public LNode
{
public:
int w.
Pomiar(int ww) : w(ww) {}
}.
Programowanie I
Wykad 11
60
Klasa
Pomiar
jest pochodn klasy
LNode
(tzn. ma takie same cechy jak
LNode
, w szczeglnoci obiekty
Pomiar
mog by elementami listy
DoubleNodedList
) ale dodatkowo zawiera skadow
w
, potra c re-
prezentowa liczb cakowit. Zde niowany konstruktor umoliwia atwe nadawanie wartoci pocztkowej
podczas tworzenia obiektu.
W powyszym przypadku
LNode
jest publiczn klas podstawow dla
Pomiar
. Oznacza to, e publiczne,
zabezpieczone i prywatne skadowe klasy
LNode
s odpowiednio publicznymi, zabezpieczonymi i prywatnymi
skadowymi klasy
Pomiar
, oraz, e obiekty
Pomiar
bd automatycznie traktowane jako
LNode
(np. jako
argumenty do
InsertAfter
czy
Delete
). Klasa podstawowa moe by zabezpieczona (wtedy publiczne ska-
dowe klasy
LNode
traktowane byyby jako zabezpieczone skadowe
Pomiar
) albo prywatna (wtedy wszystkie
skadowe
LNode
byyby prywatnymi skadowymi
Pomiar
). Jednoczenie w obu tych przypadkach obiekt
Pomiar
nie mg by by traktowany jako
LNode
.
Zapamitujemy pomiary
:
:
:
Po takim przygotowaniu zapamitanie pomiarw jest bardzo proste.
DoubleNodedList l.
while (1)
{
int i.
cin>>i.
if (!i) break. // warto2! 0 oznacza koniec danych
l.InsertAfter( l.GetLast(), new Pomiar(i) ).
}
cout<<"wczyta$em "<<l.GetCount()<<" pomiar*w\n".
deklarujemy zmienn
l
reprezentujc list, a nastpnie dopisujemy na jej kocu kolejne elementy
Pomiar
odpowiadajce poszczeglnym pomiarom. Prosz zwrci uwag, e elementy listy (tzn. obiekty klasy
Pomiar
) tworzymy dynamicznie. Co wicej, mog one by argumentamidla funkcji
l.InsertAfter
poniewa
Pomiar
jest klas, ktra dziedziczy po
LNode
, i w zwizku z tym moe by take \postrzegana" jako obiekt
typu
LNode
.
:
:
:
i analizujemy je.
Zakadajc, e nasza lista nie jest pusta moemy sprbowa obliczy redni.
double avg=0.
for ( LNode* e=l.GetFirst(). e. e=e->GetNext() )
{
avg += ((Pomiar*)e)->w.
}
avg/=l.GetCount().
cout<<"2rednia = "<<avg<<"\n".
W tym celu przegldamy wszystkie elementy listy poczwszy od pierwszego (
e=l.GetFirst()
) oraz wyko-
rzystujc fakt, e kady element zna swj nastpnik (
e=e->GetNext()
). Niezrczno polega na tym, e
podstawowe operacje listy zostay stworzone w oparciu o klas
LNode
, zatem rezultatem
GetFirst
i
Get-
Next
jest wskazanie do obiektu
LNode
. Ale my wiemy, e tak naprawd elementami listy s obiekty
Pomiar
,
ktre potra zachowywa si tak jak
LNode
. Kopot polega na tym, e tej informacji nie potra limy pki
co przekaza komputerowi i wiemy na temat programu wicej ni on. Aby uzyska dostp do skadowej
w
elementu listy posuylimy si operacj rzutowania
((Pomiar*)e)
, ktra zmienia typ
e
na
Pomiar*
. Takie
operacje rzutowania s
bardzo niebezpieczne
poniewa nie zapewniaj adnej kontroli i naley ich unika,
a jeeli jest niemoliwe to stosowa bardzo ostronie.
Moemy teraz usun wszystkie pomiary poniej redniej.
for ( LNode* e=l.GetFirst(). e. )
{
Pomiar* p=(Pomiar*)e.
e=e->GetNext().
Programowanie I
Wykad 11
61
if ( p->w < avg )
{
l.Delete(p).
delete p.
}
}
I wypisa pozostae wyniki.
for ( LNode* e=l.GetFirst(). e. e=e->GetNext() )
{
cout<<((Pomiar*)e)->w<<"\n".
}
Zadania
12.
Napisa funkcj sortujc elementy
Pomiar
na licie. Zastosowa metod sortowania przez zamian, tzn.
porwnujemy kolejne pary i jeeli nie maj poprawnego uporzdkowania to zamieniamy ich kolejno.
13.
W przedstawionych przykadach nie wykorzystywalimy informacji o poprzedniki zawartej w elementach
listy. Prosz napisa klas
SingleNodedList
bdc odpowiednikiem funkcjonalnym
DoubleNodedList
ale operujc na elementach posiadajcych tylko jedno dowizanie.
a) Ktre dowizanie jest lepsze {
Prev
czy
Next
?
b) Ktre operacje listy
DoubleNodedList
s naturalne (atwe w implementacji) dla
SingleNodedList
,
a ktre nie ?
Programowanie I
Wykad 12
62
Rzutowanie.
W przykadzie z ostatniego wykadu prezentujcym wykorzystanie listy do zapamitania wynikw pomia-
rw musielimy zastosowa operacj rzutowania. Jest to jednak metoda niekorzystna i podatna na bdy.
Wyobramy sobie sytuacj, kiedy nasz poprawny i dobrze funkcjonujcy program obsugujcy urzdzenie
pomiarowe musi ulec drobnej mody kacji { oprcz wartoci pomiaru naley dodatkowo zapamita czas jego
rejestracji i wypisa na ekranie obok rezultatu samego pomiaru. Co wicej, zmiany tej ma dokona osoba
trzecia, ktra musi najpierw przeczyta nasz program, zrozumie go i dopisa dodatkowe elementy.
Postpujc analogicznie do nas programista de niuje nowy typ
NowyPomiar
, ktry bdzie reprezentowa
element listy i dopisuje go do programu.
class NowyPomiar : public LNode
{
public:
long czas. // czas pomiaru (w sekundach od 1 stycznia 1970 roku)
int w.
// warto2! pomiaru
NowyPomiar(int ww) : czas(time(0)), w(ww) {}
}.
Teraz elementamilisty bd obiekty typu
NowyPomiar
,zatem naley zmody kowa zapamitywanie wynikw:
:
:
:
l.InsertAfter( l.GetLast(), new NowyPomiar(i) ).
:
:
:
Podczas wypisywania rezultatw dodajemy drukowanie czasu pomiaru
cout<<((NowyPomiar*)e)->w<<", "<<((NowyPomiar*)e)->czas<<"\n"
Wydaje si, e caa zmiana bya dosy prosta. Prbujemy kompilowa { wszystko w porzdku. Uruchamiamy
program { dziaa. Ale wyniki wydaj si podejrzane. 'rednia nie ma zwizku z pomiarami. Dlaczego?
Ot, mody kujc program zapomnielimy \poprawi" rzutowania
Pomiar*
przy obliczaniu redniej i usu-
waniu elementw o mniejszych wartociach. Dowiadczony programista zauway, e zde niowanie klasy
NowyPomiar
jako pochodzcej od
Pomiar
uwolnioby nas od powyszych kopotw oraz byo rozwizaniem
bardziej logicznym { chcielimy rozszerzy informacj o pomiarze, zatem powinnimy wykorzysta ju ist-
niejc reprezentacj pomiaru zamiast tworzy now od podstaw.
Celem przedstawionego rozwizania byo pokazanie jak niebezpieczne s operacje typu rzutowania, tzn.
sytuacje kiedy nie potra my zapisa w jzyku caego problemu i opieramy si na zaoeniu, e programista
zrozumie program i bdzie wiedzia o co chodzi.
W naszym przykadzie lista operuje na abstrakcyjnych elementach
LNode
, ktre nie nadaj si do zapa-
mitywania informacji. Na ich podstawie konstruujemy waciwe elementy (jak
Pomiar
czy
NowyPomiar
)
ale sama lista postrzega je jako
LNode
, w zwizku z czym stosujemy rzutowanie, ktre z kolei nie jest w
stanie stwierdzi, jakiego typu jest przeksztacany argument i czy caa operacja ma sens. Aby rozwiza ten
problem zaproponowano
Nowy styl rzutowania.
Zakres stosowania standardowych operacji rzutowania jest bardzo szeroki. W zwizku z tym do jzyka wpro-
wadzono cztery nowe sowa kluczowe
dynamic_cast
,
static_cast
,
reinterpret_cast
oraz
const_cast
,
ktre wszystkie zwizane s z rzutowaniem ale odpowiadaj bardziej szczegowym sytuacjom. Dla upro-
szczenia przedstawimy tylko znaczenie operatora
dynamic_cast
1
, ktrego znaczenie odpowiada znacznej
wikszoci wystpujcych operacji rzutowania.
Poniej przedstawione zostay dwa odpowiadajce sobie rzutowania. Pierwsze zostao zapisane w starym a
drugie w nowym stylu.
1
operator
static_cast
jest \ubosz" wersj
dynamic_cast
i nie dokonuje dynamicznego sprawdzenia
typu swego argumentu w czasie pracy programu,
reinterpret_cast
suy do zaznaczania rzutowa bardzo
nietypowych (charakterystycznych dla danego modelu komputera, itp.), natomiast
const_cast
umoliwia
zniesienie atrybutu
const
Programowanie I
Wykad 12
63
LNode* e=l.GetFirst().
// lista l zawiera elementy typu Pomiar
:
:
:
Pomiar* p1=(Pomiar*)e.
// w starym stylu
Pomiar* p2=dynamic_cast<Pomiar*>(e). // i w nowym
Operator
dynamic_cast
sprawdza czy podane rzutowanie ma sens. Skoro obiekty
Pomiar
mog by postrze-
gane jako
LNode
to wskazanie do obiektu
LNode
moe (chocia nie musi) by wskazaniem do obiektu
Pomiar
.
Warto zwrci uwag, e w przypadku starego stylu to sprawdzenie nie byo wykonywane i przez to mona
byo rzutowa w cakowicie dowolny sposb, np. przeksztacajc wskazanie do listy
DoubleNodedList
na
wskazanie do elementu tej listy
LNode
, chocia s to zupenie rne wielkoci.
DoubleNodedList l.
// w starym stylu ze wskazania do listy mo+emy zrobi! wszystko,
// np. wskazanie do jej elementu
LNode* e1=(LNode*)&l. // to nie ma +adnego sensu, ale nie jest b$"dem
// w programie
LNode* e2=dynamic_cast<LNode*>(&l). // a tutaj mamy b$,d kompilacji
Sprawdzanie sensownoci rzutowania mona roztrzygn na etapie kompilacji programu. Eliminuje ono
trudno wykrywalne bdy (bowiem to ju nie uytkownik lecz komputer ocenia logiczn poprawno i spjno
programu) ale nie jest penym rozwizanie naszego problemu. W zaprezentowanym programie wystpuj dwie
klasy
Pomiar
i
NowyPomiar
, ktre pochodz od klasy
LNode
, zatem sensowna jest moliwo rzutowanie z
LNode
do obu tych klas.
Jednak element listy jest albo obiektem
Pomiar
albo
NowyPomiar
. Okazuje si, e
dynamic_cast
doko-
nuje take rzeczywistego sprawdzenia typu swego argumentu
2
w czasie pracy programu i sygnalizuje bdne
rzutowania.
// na li2cie l zapami"tali2my obiekty NowyPomiar
// je+eli przy liczeniu 2redniej zapomnieli2my poprawi! rzutowanie
// to jego rezultatem b"dzie wskazanie puste
LNode* e=l.GetFirst().
Pomiar* p=dynamic_cast<Pomiar*>(e).
if (!p)
{
cout<<"Na li2cie s, inne obiekty ni+ zak$adano,\n"
"b$"dnie skonstruowany program.\n"
abort().
}
// rzutowanie jest poprawne, mo+emy kontynuowa!
:
:
:
Dodatkowe kontrole uzyskane dziki uyciu nowego stylu rzutowania day nam moliwo takiego skonstruo-
wania programu, ktry w najgorszym wypadku poinformuje uytkownika (ktrym zazwyczaj nie bdzie ju
jego twrca) o bdach projektowania. Niewtpliwie jest to bardziej eleganckie, ni zawieszenie si programu
czy generowanie bdnych wynikw, ale cigle nie jest rozwizaniem zadawalajcym a jedynie prodkiem.
Klasy sparametryzowane.
Chcielibymy aby identy kator naszej listy \zna" typ swoich elementw tak jak w przypadku tablicy. Jeeli
zadeklarujemy tablic
double tab10].
to odwoujc si do jej elementw, np.
tab0]
wiemy, e jest to zmienna typu
double
. Analogicznie
chcielibymy deklarowa list, np.
2
Rzeczywiste sprawdzenie typu argumentu przez operator
dynamic_cast
dotyczy tylko obiektw poli-
mor cznych, i faktycznie nie bdzie miao miejsca dla obiektw
LNode
,
Pomiar
i
NowyPomiar
. Przyczyny tego
ograniczenia wynikaj wycznie z trudnoci implementacyjnych i chci zachowania zgodnoci z jzykiem C.
Programowanie I
Wykad 12
64
// potrzebuj" listy o elementach typu Pomiar
TDoubleNodedList<Pomiar> l.
chcielibymy aby rezultaty
GetFirst
i
GetLast
byy take wskazaniami do typu elementu listy, dziki czemu
nie potrzeba ju rzutowania
Pomiar* First=l.GetFirst().
Pomiar* Last =l.GetLast ().
z kolei dla elementw tej listy metody
GetPrev
i
GetNext
powinny dawa wskazania do typu samego elementu,
np.
for ( Pomiar* l=GetFirst(). p. p=p->GetNext() )
{
avg += p->w.
}
Ostatecznie operacje
Delete
i
InsertAfter
powinny kontrolowa typy swoich argumentw
l.InsertAfter( 0, new Pomiar(1) ). // w porz,dku
l.InsertAfter( 0, new NowyPomiar(2) ). // b$,d, element musi by! typu Pomiar
Rozwizaniem tego zadania s klasy sparametryzowane, dla ktrych podczas de nicji posugujemy si do-
datkowym parametrem, precyzowanym dopiero w momencie uycia (deklaracji) obiektu tej klasy.
Zaczniemy od zde niowania sparametryzowanego elementu listy.
template <class T>
class TLNode : public LNode
{
public:
T* GetPrev() { return static_cast<T*>(LNode::GetPrev()). }
T* GetNext() { return static_cast<T*>(LNode::GetNext()). }
}.
musimy jeszcze zmody kowa de nicj klasy
Pomiar
aby wykorzystywaa
TLNode
.
class Pomiar : public TLNode<Pomiar>
{
public:
int w.
Pomiar(int ww) : w(ww) {}
}.
Od tej pory rezultatami operacji
GetNext
i
GetPrev
dla obiektw
Pomiar
s wskazania do obiektw tej samej
klasy, tj.
Pomiar*
.
W podobny sposb tworzymy klas
TDoubleNodedList
.
template <class T>
class TDoubleNodedList : public DoubleNodedList
{
public:
T* GetFirst() { return static_cast<T*>(DoubleNodedList::GetFirst()). }
T* GetLast () { return static_cast<T*>(DoubleNodedList::GetLast ()). }
void Delete(T* AnItem)
{
DoubleNodedList::Delete(AnItem).
}
void InsertAfter(T* AnAfter,T* ANewItem)
{
DoubleNodedList::InsertAfter(AnAfter,ANewItem).
}
}.
Programowanie I
Wykad 12
65
Wykorzystujc powysze klasy moemy przepisa przykad z ostatniego wykadu bez adnego rzutowania.
TDoubleNodedList<Pomiar> l.
while (1)
{
int i.
cin>>i.
if (!i) break. // warto2! 0 oznacza koniec danych
l.InsertAfter( l.GetLast(), new Pomiar(i) ).
}
cout<<"wczyta$em "<<l.GetCount()<<" pomiar*w\n".
:
:
:
double avg=0.
for ( Pomiar* p=l.GetFirst(). p. p=p->GetNext() )
{
avg += p->w.
}
avg/=l.GetCount().
cout<<"2rednia = "<<avg<<"\n".
:
:
:
for ( Pomiar* p=l.GetFirst(). p. )
{
Pomiar* p2=p.
p=p->GetNext().
if ( p2->w < avg )
{
l.Delete(p2).
delete p2.
}
}
:
:
:
for ( Pomiar* p=l.GetFirst(). p. p=p->GetNext() )
{
cout<<p->w<<"\n".
}
Mody kacja programu zaprezentowana na pocztku zostanie przez kompilator wykryta jako niekompletna,
poniewa po zmianie deklaracji klasy na
TDoubleNodedList<NowyPomiar> l.
operacje typu
Pomiar* p=l.GetFirst().
s bdne.
Dziki wykorzystaniu klas sparametryzowanych udao si nam skonstruowa list dwukierunkow, ktra
dziaa na abstrakcyjnych elementach. Co wicej, w momencie zastosowania i deklaracji konkretnego eg-
zemplarza tej listy (np.
TDoubleNodedList<Pomiar> l.
) nastpuje dodatkowe przekazanie informacji, e
zadeklarowany obiekt
l
jest list o elementach
Pomiar
, dziki czemu mamy moliwo kontroli poprawnoci
uycia tej listy ju podczas kompilacjiprogramu, i w efekcie pewno, e dziaajcy program zosta poprawnie
skonstruowany.
Porzdkowanie listy.
Technika klas z parametrem umoliwia dodanie operacji, ktre bd miay rne znaczenie w zalenoci od
konkretnego obiektu. Rozwamy problem porzdkowania listy. Ma on sens jeeli dla elementw istnieje
operacja porzdkujca (np. mona porzdkowa elementy
Pomiar
lub
NowyPomiar
, np. wedug wartoci
pomiaru, ale w przypadku elementw pamitajcych wartoci zespolone trudno poda sensown relacj
porwnujc). Z drugiej strony, typ elementu jest podawany dopiero w momencie korzystania z klasy.
W zwizku z tym chcielibymy mc dopisa operacj porzdkowania niezalenie od tego czy konkretne
Programowanie I
Wykad 12
66
zastosowanie listy bdzie mogo z niej skorzysta. Ponadto rozwizanie powinno nie sortowa w przypadku
elementw bez uporzdkowania, a take by proste w uyciu.
Sortowanie bbelkowe.
W naszym przykadzie wykorzystamy tzw. sortowanie bbelkowe polegajce na wielokrotnym przegldaniu
cigu elementw i porwnywaniu ssiednich wyrazw, oraz jeeli wystpuj w zej kolejnoci, dokonywaniu
zamiany. Czynno powtarzana jest do uzyskania penego uporzdkowania.
Przedstawiony algorytm wymaga w najbardziej pesymistycznym przypadku
1
2
n
2
operacji porwnania i prze-
stawienia, i mwimy, e jego zoono obliczeniowa jest rzdu
n
2
.
Realizacj zapisujemy w metodzie
Sort
klasy
TDoubleNodedList
w nastpujcy sposb.
template <class T>
class TDoubleNodedList
{
:
:
:
void Sort().
}.
template <class T>
void TDoubleNodedList<T>::Sort()
{
if (GetCount()<2) return. // przynajmniej dwa elementy do sortowania
int Changes. // zlicza przestawienia
do
{
int Changes=0.
// rozpoczynamy jednokrotne przegl,danie listy
T* Prev=GetFirst().
T* Curr=Prev->GetNext().
while (Curr)
{
if (Prev->Comp(Curr)>0)
{
// z$e uporz,dkowanie s,siednich element*w, dokonujemy zamiany
Changes++.
Delete(Prev).
InsertAfter(Curr,Prev).
}
else Prev=Curr.
Curr=Curr->GetNext().
}
} while (Changes).
}
Dla kadego typu elementu listy musimy dopisa funkcj porwnujc. Rezultatem tej funkcji w przypadku
dobrego uporzdkowania argumentw jest 0, za zego 1.
class Pomiar : public TLNode<Pomiar>
{
:
:
:
int Comp(Pomiar* r)
{
return w < r->w ? 0 : 1.
}
}.
Programowanie I
Wykad 12
67
Aby nie de niowa metody porwnujcej dla kadego typu elementu mona w de nicji klasy
TLNode
doda
funkcj
Comp
o staym rezultacie 0, odpowiadajcej sytuacji, e kade uporzdkowanie listy jest prawidowe
(tzn. nie ma relacji porzdkujcej).
template <class T>
class TLNode<T> : public LNode
{
:
:
:
int Comp(TLNode<T>*) { return 0. }
}.
Programowanie I
Wykad 13
68
Polimorzm.
Dotychczas mechanizm dziedziczenia wykorzystywany by jako sposb konstrukcji nowych klas, ktre przej-
moway wasnoci od innych, ju istniejcych. Innymi sowy, dziedziczenie odpowiadao dalszej specjalizacji
obiektw. W samym programie korzystalimy ju z tych kocowych, najbardziej szczegowych.
Co wicej, staralimy si tak tworzy nowe obiekty, aby unikn odwoywania si do nich jako obiektw
reprezentujcych klasy, z ktrych dziedziczylimy (porwnaj problemy z klasami
Pomiar
i
NowyPomiar
z
poprzedniego wykadu).
Obiekty polimor czne zawieraj ukryt, dodatkow informacj identy kujc rzeczywisty typ. Dziki temu
moliwe jest takie zde niowanie metody klasy, e o jej wykonaniu decydowa bdzie rzeczywisty typ obiektu,
a nie sposb wywoania tej metody. Funkcje klasy, o ktrych wykonaniu decyduje rzeczywisty typ obiektu
nazywa si wirtualnymi i ich deklaracja poprzedzona jest dodatkowym sowem kluczowym
virtual
.
Typowym przykadem wykorzystania powyszego mechanizmu s systemy okienkowe, takie jak MS Win-
dows czy XWindows. Podczas pracy w rodowisku gra cznym korzystamy jednoczenie z wielu programw.
Dany program wykorzystuje najczciej kilka okien. O sukcesie tego sposobu komunikacji z komputerem
zadecydowa m.in. jednolity sposb obsugi programw, niezalenie od producenta. Podstawowe czynnoci,
takie jak zamknicie (zmniejszenie, przesunicie) okna czy wybr polecenia z menu, wykonujemy w ten sam
sposb. Za wykonanie tych czynnoci odpowiedzialny jest specjalny program zarzdzajcy okienkami (ang.
window manager). To co rni programy, to wypisywana w okienkach informacja oraz sposb reakcji na
nacinicie przycisku myszki czy klawisza klawiatury.
W zwizku z tym moemy sobie wyobraa, e wszystkie programy s klasami pochodzcymi od pewnej
abstrakcyjnej klasy
TWindow
, w ktrych za wypisanie informacji w okienku oraz obsug myszki i klawiatury
odpowiedzialne s polimor czne funkcje:
class TPewienProgram : public TWindow
{
:
:
:
virtual void Draw().
virtual void HandleMouseEvent(TMouseEvent&).
virtual void HandleKeyboardEvent(TKeyboardEvent&).
}.
Program window manager nie zna konkretnych klas odpowiadajcych poszczeglnym programom, ktre
zwykle s tworzone p niej ni sam manager. Zatem ten ostatni wie tylko tyle, e klasy reprezentujce
poszczeglne okna pochodz od
TWindow
i odwouje si do wszystkich okien jak do
TWindow
. Przykadowo,
jeeli uytkownik nacisn klawisz myszki w ktrym oknie, to window manager odnajdzie to okno (dla niego
jest to obiekt
TWindow* w
) i wywoa metod
w->HandleMouseEvent(e)
. Ale to wywoanie bdzie dotyczy
funkcji odpowiadajcej
temu konkretnemu
obiektowi.
Kalkulator.
Jako ilustracj polimor zmu wykorzystamy zadanie z kalkulatorem liczcym w Odwrotnej Notacji Polskiej.
Zapisanie rozwizania z wykorzystaniem polimor zmu moe nie wydawa si najbardziej naturalnym roz-
wizaniem ale prostota samego zadania eksponuje dziaanie funkcji wirtualnych.
Kalkulator odczytuje kolejne polecenia i wykonuje je. Naturalnym byoby nastpujce zapisanie rozwizania:
while (1)
{
TPolecenie* p=OdczytajPolecenie().
if (!p) break. // koniec pracy programu kalkulatora
p->Wykonaj().
delete p.
}
Z drugiej strony czym innym jest dodawanie, a czym innym mnoenie. Chcemy aby wszystkie polecenia
reprezentowane byy klasami pochodzcymi od
TPolecenie
, przy czym metoda
Wykonaj
powinna by poli-
mor czna.
Programowanie I
Wykad 13
69
Poniej przedstawiono przykadowe rozwizanie. Wykorzystuje ono klas
TStos
implementujc stos do
zapamitywania argumentw i wynikw oblicze. Polecenia odczytywane s caymi wierszami. Dodawaniu
odpowiada
+
, odejmowaniu
-
, mnoeniu
*
za dzieleniu
/
.
=
wypisuje dan znajdujc si na szczycie
stosu, natomiast
?
wszystkie elementy stosu. Z kolei
c
usuwa wszystkie elementy stosu, a
q
koczy prac
programu. Wpisana liczba jest zapamitywana na szczycie stosu. Ewentualne bdy oblicze s zgaszane w
standardowy sposb.
#include <iostream.h>
#include <stdlib.h>
#include <ctype.h>
class TStos
{
double Tab128]. // w tablicy pami"tamy argumenty i rezultaty oblicze-
int
Rozm.
// liczba zapami"tanych element*w
public:
TStos() : Rozm(0) {}
// Stos0] - referencja do elementu na szczycie stosu
// Stos-n] - referencja do elementu le+,cego o n poni+ej szczytu stosu
double& operator](int Indeks)
{
if (!Rozm) throw "stos jest pusty".
if (Indeks>0 -Indeks>=Rozm) throw "za ma$o argument*w na stosie".
return TabRozm-1+Indeks].
}
// usuni"cie elementu ze szczytu stosu
void Usun()
{
if (!Rozm) throw "stos jest pusty".
Rozm--.
}
// dopisanie elementu na szczyt stosu
void Dopisz(double ALiczba)
{
if (Rozm==sizeof(Tab)/sizeof(Tab0]))
throw "mo+liwo2ci kalkulatora zosta$y przekroczone".
TabRozm++]=ALiczba.
}
// usuni"cie wszystkich element*w ze stosu
void Wyczysc()
{
Rozm=0.
}
// wypisanie szczytowego (wszystkich) element*w stosu
void Wypisz(int Wszystkie)
{
if (!Rozm) cout<<"stos jest pusty\n".
else for ( int i=Rozm. i >= (Wszystkie ? 1 : Rozm). i-- )
{
cout<<Tabi-1]<<"\n".
}
}
}.
Programowanie I
Wykad 13
70
TStos Stos.
class TPolecenie
{
public:
virtual ~TPolecenie() {}
virtual void Wykonaj() {}
}.
class TDodawanie : public TPolecenie
{
public:
void Wykonaj()
{
Stos-1] += Stos0].
Stos.Usun().
}
}.
class TOdejmowanie : public TPolecenie
{
public:
void Wykonaj()
{
Stos-1] -= Stos0].
Stos.Usun().
}
}.
class TMnozenie : public TPolecenie
{
public:
void Wykonaj()
{
Stos-1] *= Stos0].
Stos.Usun().
}
}.
class TDzielenie : public TPolecenie
{
public:
void Wykonaj()
{
if (Stos0]==0) throw "pr*ba dzielenia przez zero".
Stos-1] /= Stos0].
Stos.Usun().
}
}.
Programowanie I
Wykad 13
71
class TRownaSie : public TPolecenie
{
public:
void Wykonaj()
{
Stos.Wypisz(0).
}
}.
class TWypisz : public TPolecenie
{
public:
void Wykonaj()
{
Stos.Wypisz(1).
}
}.
class TWyczysc : public TPolecenie
{
public:
void Wykonaj()
{
Stos.Wyczysc().
}
}.
class TLiczba : public TPolecenie
{
double Liczba.
public:
TLiczba(double ALiczba) : Liczba(ALiczba) {}
void Wykonaj()
{
Stos.Dopisz(Liczba).
}
}.
TPolecenie* OdczytajPolecenie()
{
int c.
do { c=cin.get(). } while (isspace(c)).
char Buf16].
int Cnt=1.
Buf0]=c.
while (1)
{
c=cin.get().
if (isspace(c)) break.
if (Cnt+1==sizeof(Buf))
{
cin.ignore(10000).
throw "podano b$"dne dane".
Programowanie I
Wykad 13
72
}
BufCnt++]=c.
}
BufCnt]=0.
if (Cnt==1)
{
switch (Buf0])
{
case '+' : return new TDodawanie().
case '-' : return new TOdejmowanie().
case '*' : return new TMnozenie().
case '/' : return new TDzielenie().
case '=' : return new TRownaSie().
case '?' : return new TWypisz().
case 'c' :
case 'C' : return new TWyczysc().
case 'q' :
case 'Q' : return 0.
}
}
char* EndPtr.
double wartosc=strtod(Buf,&EndPtr).
if (*EndPtr) throw "podano b$"dne dane".
return new TLiczba(wartosc).
}
int main()
{
while (1)
{
try
{
TPolecenie* p=OdczytajPolecenie().
if (!p) break.
p->Wykonaj().
delete p.
}
catch (const char* Info)
{
cout<<"B45D: "<<Info<<" !\n".
}
}
return 0.
}
Zadania
14.
Rozbudowa kalkulator o obliczanie pierwiastka kwadratowego.
Programowanie I
Wykad 14
73
Sortowanie.
Sortowanie jest jednym z najczstszych problemw wystpujcych w programach. Wynika to z faktu, e
posugiwanie si danymi uporzdkowanymi jest o wiele prostsze ni nieuporzdkowanymi.
Dane do posortowania zapisane s w cigu (
a
1
a
2
a
3
:
:
:
a
n
). Poprzez dokonanie odpowiednich przestawie
chcemy doprowadzi do cigu (
a
(1)
a
(2)
:
:
:
a
(n)
), tak e
a
(1)
a
(2)
:
:
:
a
(n)
. O efektywnoci
konkretnego sposobu decyduje liczba wymaganych porwna i przestawie elementw cigu.
Poniej opiszemy kilka prostych algorytmw realizujcych powysze zagadnienie.
1. Sortowanie bbelkowe (ang.
bubblesort
).
Polega ono na wielokrotnym przegldaniu cigu i porwnywaniu par kolejnych elementw (
a
n
a
n+1
). W
przypadku, gdy kolejno jest niepoprawna dokonujemy zamiany
a
n
$
a
n+1
. Operacje powtarzamy, a
do momentu gdy w wyniku przejrzenia caego cigu nie wykonamy adnej zamiany. Poniej przedstawiono
kolejne etapy sortowania cigu liczb (7
1
5
8
9
4
2). Podkreleniem zaznaczono pary elemementw, dla
ktrych dokonano zamiany.
1 przegldanie cigu
1
,
7
,5,8,9,4,2
1,
5
,
7
,8,9,4,2
1,5,7,8,
4
,
9
,2
1,5,7,8,4,
2
,
9
2 przegldanie cigu
1,5,7,
4
,
8
,2,9
1,5,7,4,
2
,
8
,9
3 przegldanie cigu
1,5,
4
,
7
,2,8,9
1,5,4,
2
,
7
,8,9
4 przegldanie cigu
1,
4
,
5
,2,7,8,9
1,4,
2
,
5
,7,8,9
5 przegldanie cigu
1,
2
,
4
,5,7,8,9
Dla
i
{tego przegldania cigu wykonujemy do
n
;
i
porwna i zamian. Maksymalnie musimy wykona
n
przejrze cigu. Zatem zoono obliczeniowa jest rzdu
1
2
n
2
.
2. Sortowanie przez selekcj (ang.
selectionsort
).
W cigu (
a
2
:
:
:
a
n
) naley wyznaczy najmniejszy element
a
k
, zamieni go z pierwszym elementem, tzn.
a
1
$
a
k
, a nastpnie zastosowa t sam procedur dla podcigu (
a
3
:
:
:
a
n
).
Poniej przedstawiono kolejne etapy sortowania dla cigu (7
1
5
8
9
4
2). Podkreleniem zaznaczono naj-
mniejszy element prawego podcigu.
(1](7,5,8,9,4,
2
]
(1,2](5,8,9,
4
,7]
(1,2,4](8,9,
5
,7]
(1,2,4,5](9,8,
7
]
(1,2,4,5,7](
8
,9]
(1,2,4,5,7,8](
9
]
3. Sortowanie przez wstawianie (ang.
insertionsort
).
Sortowanie przez wstawianie polega na powtarzaniu wstawiania elementu
a
k
w uporzdkowany podcig
(
a
1
a
2
:
:
:
a
k ;1
). Ilustruje to nastpujcy przykad. Podkreleniem zaznaczono elementy, ktre zostay
przesunite w prawo podczas wstawienia kolejnego elementu do uporzdkowanego podcigu.
(7](1,5,8,9,4,2]
(1,
7
](5,8,9,4,2]
(1,5,
7
](8,9,4,2]
(1,5,7,8](9,4,2]
Programowanie I
Wykad 14
74
(1,5,7,8,9](4,2]
(1,4,
5
,
7
,
8
,
9
](2]
(1,2,
4
,
5
,
7
,
8
,
9
]
Prosz zwrci uwag, e dla cigu uporzdkowanego czas dziaania jest liniowy. Zatem jest to bardzo
efektywna metoda dla sortowania danych czciowo uporzdkowanych.
4. Sortowanie szybkie (ang.
quicksort
).
Jeden z najczciej stosowanych algorytmw. Jest uwaany za najszybszy algorytm porzdkowania dla
losowych danych wejciowych, chocia w najbardziej pesymistycznym przypadku jego zoono obliczeniowa
jest rzdu
n
2
.
Jego dziaanie polega na podzieleniu cigu (
a
1
a
2
:
:
:
a
n
) na dwa podcigi (
b
1
:
:
:
b
k ;1
) i (
b
k +1
:
:
:
b
n
), w
taki sposb, e speniony jest warunek
(
b
1
:
:
:
b
k ;1
)
b
k
(
b
k +1
:
:
:
b
n
)
:
Nastpnie w ten sam sposb naley posortowa podcigi (
b
1
:
:
:
b
k ;1
) i (
b
k +1
:
:
:
b
n
). Warto zwrci uwag,
e po opisanym podziale element
b
k
znajduje si na ostatecznym miejscu, oraz e oba powstae podcigi
moemy sortowa niezalenie.
Decydujce znaczenie ma funkcja dokonujca podziau cigu (
a
l
:
:
:
a
r
) na dwa podcigi. Jako element
rozdzielajcy wybieramy
a
l
, a nastpnie przegldamy podcig (
a
l+1
:
:
:
a
r
) z lewej strony, a napotkamy
jego koniec lub element nie mniejszy ni
a
l
. Nastpnie przegldamy ten sam podcig z prawej strony w
poszukiwaniu pierwszego elementu nie wikszego od
a
l
. Dwa elementy, na ktrych si zatrzymalimy zamie-
niamy miejscami. Kiedy oba wska niki spotkaj si proces dzielenia jest zakoczony { element rozdzielajcy
a
l
zamieniamy z ostatnim elementem lewego podcigu.
Poniej przedstawiamy podzia cigu (7
1
5
8
9
6
4
2). Elementem rozdzielajcym jest w tym wypadku
7.
i
jest wska nikiem wykorzystywanym przy przegldaniu podcigu (1
5
8
9
6
4
2) z lewej strony, za
j
z
prawej.
7,1,5,
i
8
,9,6,4,
j
2
7,1,5,2,
i
9
,6,
j
4
,8
7,1,5,2,4,
ij
6
,9,8
Wska niki spotkay si { zamieniamy element rozdzielajcy 7 z ostatnim elementem lewego podcigu, tj. 6
i otrzymujemy podzia
(6
1
5
2
4)
7
(9
8)
:
W wyniku kolejnych podziaw podcigw otrzymujemy
(6,1,5,2,4],7,(9,8]
(4,1,5,2],6,7,8,9
(2,1],4,5,6,7,8,9
1,2,4,5,6,7,8,9
Okazuje si, e warto oczekiwana zoonoci obliczeniowej tego algorytmu wynosi w przyblieniu 1
:
4
n
log
n
.
Niestety, zaprezentowany sposb podziau jest nieefektywny dla danych cakowicie lub czciowo uporzd-
kowanych (czyli, z jakimi spotykamy si najczciej). Zoono obliczeniowa jest wtedy rzdu
n
2
. Prosz
samodzielnie zastosowa powysz metod dla cigu (1
2
4
5
6
7
8
9)! Aby usprawni algorytm proponuje
si inny wybr elementu podziau, np.
losowy wybr dowolnego elementu
a
k
, gdzie
l
k
r
,
wybr mediany z kilku elementw cigu, np. spord
fa
l
a
b(l+r )=2 c
a
r
g
.
Naturalnym sposobem realizacji omawianego algorytmu jest zastosowanie rekurencji. Niech
a
bdzie
n
{
elementow (
n
1) tablic liczb cakowitych
int
. Uporzdkowanie tej tablicy uzyskujemy przez wywoanie
funkcji
Programowanie I
Wykad 14
75
quicksort(a,0,n-1).
gdzie
quicksort
jest zde niowana nastpujco
void quicksort(int* a,int l,int r)
{
int k=partition(a,l,r).
if ( l
< k-1 ) quicksort(a, l,k-1).
if ( k+1 < r
) quicksort(a,k+1, r).
}
Funkcja
partition
dokonuje podziau cigu (
a
l
:
:
:
a
r
). Jej rezultatem jest indeks elementu podziau
a
k
.
Dolne ograniczenie na z oono problemu sortowania.
Zastanwny si nad najmniejsz wymagan liczb porwna dla uporzdkowania cigu
n
{elementowego.
a1<a2
a3<a2
a3<a2
a1<a3
(a1,a2,a3)
(a3,a2,a1)
a1<a3
(a3,a1,a2)
(a2,a1,a3)
(a2,a3,a1)
NIE
TAK
NIE
NIE
TAK
TAK
NIE
NIE
TAK
TAK
(a1,a3,a2)
Porzdkowanie 3{elementowego cigu
(
a
1
a
2
a
3
)
Mamy 3! = 6 moliwych cigw 3{elementowych. Aby posortowa dany cig wejciowy przesuwamy si od
korzenia drzewa a do napotkania licia. Dugo cieki jak przeszlimy jest proporcjonalna do zoonoci
obliczeniowej (w kadym w le dokonujemy porwnania). W drzewie mamy 6 lici, za sumaryczna dugo
wszystkich cieek wynosi 3 + 3 + 2 + 2 + 3 + 3 = 16, zatem oczekiwana zoono obliczeniowa wynosi
16
6
= 2
2
3
.
Okazuje si, e zoono obliczeniowa idealnego algorytmu sortowania n{elementowego cigu w przypadku
najbardziej pesymistycznych danych wynosi w przyblieniu
n
log
n
;
1
:
45
n
.
Widzimy, e metoda quicksort jest bardzo zbliona do tego dolnego ograniczenia.
Zadania
15.
Napisa funkcje
a)
void bubblesort(int* a,int n)
,
b)
void selectionsort(int* a,int n)
,
c)
void insertionsort(int* a,int n)
,
sortujce
n
{elementow tablic
a
liczb cakowitych
int
.
16.
Algorytm porzdkujcy nazywamy stabilnym jeeli zachowuje pocztkowe ustawienie wzgldem siebie
elementw rwnych. Zbada stabilno przedstawionych algorytmw.
17.
Oszacowa zoono obliczeniow metod porzdkowania przez selekcj i przez wstawianie.
18.
Napisa funkcj
void partition(int* a,int l,int r)
dokonujc podziau cigu (
a
l
:
:
:
a
r
) zgodnie
ze sposobem podanym w opisie algorytmu quicksort.
Programowanie I
Wykad 15
76
Drzewa binarne.
Drzewo binarne
to struktura danych reprezentujca zbir elementw. Kady element moe mie do dwch
potomkw
. Element, ktry ma przynajmniej jednego potomka nazywamy
wzem
, natomiast nie posiadajcy
adnego potomka
li ciem
. Kady element oprcz jednego, zwanego
korzeniem
posiada dokadnie jednego
poprzednika
. Korze drzewa nie posiada poprzednika.
15
10
3
8
5
1
4
2
Rysunek przedstawia przykadowe drzewo binarne. Element 15 jest korzeniem, 1, 2 i 4 s li ciami. Poprzednikiem
10 jest 15, natomiast nast pnikami s 8 i 5.
Jeeli dla kadego wza wartoci nastpnikw (o ile istniej) s nie wiksze (odpowiednio nie mniejsze) ni
warto wza to drzewo takie nazywamy
kopcem
.
15
10
5
9
6
1
2
8
3
4
Przykad kopca.
Jeeli dla kadego wza warto prawego nastpnika (o ile istnieje) jest wiksza (odpowiednio mniejsza) od
wartoci wza, natomiast warto lewego nastpnika (o ile istnieje) jest mniejsza (odpowiednio wiksza) od
wartoci wza, to drzewo takie nazywamy
drzewem wyszukiwa binarnych
.
Jeeli wszystkie poziomy drzewa s wypenione cakowicie, za wyjtkiem ostatniego { spjnie wypenionego
od lewej strony, to drzewo nazywamy
zupenym
.
Liczb
h
poziomw wystpujcych w drzewie nazywamy
wysoko ci drzewa
.
Drzewo zupene moe by atwo reprezentowane w tablicy. Jeeli korze drzewa zapiszemy w komrce o
indeksie 1, to nastpniki wza
k
maj indeksy 2
k
i 2
k
+1 (odpowiednio lewy i prawy), natomiast poprzednik
ma indeks
b
k
2
c
.
Programowanie I
Wykad 15
77
1
2
3
6
7
9
4
5
8
10
Numeracja elementw zupenego drzewa binarnego.
Podstawowe operacje na kopcu.
Wstawienie nowego elementu
x
do kopca zupenego polega na dopisaniu
x
w pierwszym wolnym miejscu
ostatniego poziomu (lub gdy ostatni poziom jest cakowicie zapeniony na pierwszym miejscu nastpnego
poziomu) i przywrceniu warunku kopca (tzn. aby warto poprzednika bya wiksza lub rwna wartoci
elementu) o ile zosta zaburzony.
Przywracanie warunku kopca polega na przechodzeniu od licia w stron korzenia i zamianie par (
ele-
ment
,
poprzednik
).
8
3
4
6
9
10
1
2
11
5
15
8
3
4
6
9
11
1
2
10
5
15
b)
8
3
4
11
9
6
1
2
10
5
15
nowy element
a)
c)
Przywracanie warunku kopca.
Jeeli
a
jest tablic liczb cakowitych
int
reprezentujc kopiec, a
n
okrela liczb elementw kopca to
dopisanie nowego elementu
v
moemy zapisa nastpujco.
// nowy element dopisujemy na pierwszym wolnym miejscu
a++n] = v.
// przywracamy warunek kopca
for ( . n/2 && an/2]<an]. n/=2 )
{
zamien( an], an/2] ).
}
Dla uproszczenia zapisu uyto funkcji
zamien
void zamien(int& a,int& b)
{
int c=a.
a=b.
b=c.
}
Dopisanie nowego elementu wymaga co najwyej
h
operacji porwnania i zamiany elementw, gdzie
h
jest
wysokoci drzewa, zoono obliczeniowa jest w najbardziej pesymistycznym przypadku rzdu log
n
.
Programowanie I
Wykad 15
78
Drug podstawow operacj jest usunicie elementu maksymalnego, ktry zawsze znajduje si w korzeniu tj.
w komrce
a1]
. Aby wykona t operacj po usuniciu korzenia, wstawiamy na jego miejsce prawy skrajny
li z ostatniego poziomu (po jego uprzednim usuniciu). Nastpnie przechodzc od korzenia w d drzewa
przywracamy warunek kopca dla trjek elementw (
wze
,
lewy nastpnik
,
prawy nastpnik
).
8
3
4
9
1
2
10
5
11
8
3
4
9
10
1
2
6
5
c)
8
3
4
9
10
1
2
5
6
b)
8
3
4
9
10
1
2
5
15
a)
11
6
11
11
d)
6
Usuni cie z kopca elementu 15.
Realizacja operacji usuni cia korzenia jest rwnie prosta.
void rownowaz_w_dol(int i)
{
for ( i*=2. i<=n. i*=2 )
{
if ( i<n && ai]<ai+1] ) i++.
if ( ai/2] >= ai] ) break.
zamien( ai], ai/2] ).
}
}
int usun_max()
{
int v = a1].
// na miejsce korzenia wpisujemy skrajny prawy li2!
a1] = an].
n--.
// przywracamy warunek kopca
rownowaz_w_dol(1).
return v.
}
Zoono obliczeniowa powyszej operacji jest take rz du
log
n
.
Sortowanie cigu
(
a
1
a
2
:
:
:
a
n
)
polega na utworzeniu pustego kopca i kolejnemu dopisywaniu wyrazw cigu (zoono
obliczeniowa
n
log
n
), a nast pnie na wielokrotnym usuni ciu korzenia (zoono take rz du
n
log
n
).
Okazuje si , e utworzenie kopca mona zrealizowa w czasie liniowym, tj. rz du
n
. Wystarczy konstrukcj kopca rozpocz
od dou drzewa, tworzy mae podkopce i czy je w wi ksze { a do powstania caego kopca. Aby poczy dwa podkopce
i wstawi kolejny element
x
w w le
i
naley dla tego w za wywoa funkcj
rownowaz_w_dol(i)
. Jeeli elementy cigu
(
a
1
a
2
:
:
:
a
n
)
zostay zapisane w komrkach tablicy
a1]
,
a2]
,
:
:
:
,
an]
to utworzenie kopca wykonujemy nast pujco
for ( int i=n/2. i>=1. i-- ) rownowaz_w_dol(i).
Wyszukiwanie.
Operacj powizan z porzdkowaniem jest wyszukiwanie zadanego elementu. Niech
a
b dzie uporzdkowan,
n
{elementow
tablic liczb cakowitych
int
. Zadaniem jest sprawdzenie czy dana liczba
v
znajduje si w tablicy, a jeeli tak, podanie jej
indeksu.
Fakt uporzdkowania elementw tablicy umoliwia nam zastosowanie algorytmu wyszukiwania binarnego. Polega on na porw-
naniu warto ci
v
ze rodkowym wyrazem tablicy, tj.
an/2]
i ograniczeniu si do dalszego szukania w lewej lub prawej cz ci
tablicy.
Programowanie I
Wykad 15
79
Realizacja jest natychmiastowa
int bsearch(int v,int* a,int l,int r)
{
while (l<=r)
{
int k=(l+r)/2.
if (ak]==v) return k.
else if (ak]>v) r=k-1.
else l=k+1.
}
return -1. // nie znaleziono elementu o warto2ci v
}
Zoono obliczeniowa (liczba porwna) powyszej metody jest rz du
log
n
.
Dziaanie wyszukiwania binarnego mona zobrazowa za pomoc drzewa binarnego, w wierzchokach ktrego znajduj si
elementy tablicy
a
, uoone w kolejno ci porwnywania ich z szukanym elementem
v
.
a[0]
a[2]
a[4]
a[6]
a[8]
a[10]
a[12]
a[14]
a[1]
a[5]
a[9]
a[13]
a[3]
a[11]
a[7]
Drzewo wyszukiwania binarnego odpowiadajcego 15{elementowej tablicy
Zadania
19.
Napisa funkcj
void heapsort(int* a,int n)
sortujca
n
{elementow tablic
a
liczb cakowitych
int
metod
kopcowania.
Wyszukiwarka
Podobne podstrony:
Program kola plastycznego id 39 Nieznany
Anatomia Kolokwium I p1 id 6275 Nieznany
programowanie c pl v1 id 395919 Nieznany
arkusz p1 id 68808 Nieznany (2)
PrAdmin program cw 2011 id 3845 Nieznany
Program Z D 1112 EK id 395574 Nieznany
Programowanie Od podstaw id 39 Nieznany
Program cwiczen 2013 id 395015 Nieznany
program sw 2010 id 395477 Nieznany
Program kola plastycznego id 39 Nieznany
3 p1 a2 id 33942 Nieznany
Program umiarkowany id 395519 Nieznany
Narodowy Program Zdrowia1 id 31 Nieznany
program praktyk informatyka id Nieznany
Narodowy Program Zdrowia id 314 Nieznany
więcej podobnych podstron