B u d u j S t o g ( i n t n , i n t A[MAX] ) { f o r ( i = ( n − 2 ) / 2 ; i >=0; i −−) P r z e s i e w a n i e ( i , n −1 ,A ) ; }
S o r t o w a n i e S t o g o w e ( i n t n , i n t A[MAX] ) { BudujStog ( n ,A) ; f o r ( i =n −1; i >=1; i −−) { x=A [ 0 ] ; A[ 0 ] =A[ i ] ; A[ i ] = x ; P r z e s i e w a n i e ( 0 , i −1); }
4
Asymptotyczna pesymistyczna złoz˙ ono´sc´ czasowa
Liczba iteracji w funkcji Przesiewanie jest proporcjonalna do róz˙ nicy poziomów mi˛edzy elementami A[l] i A[p]. W najgorszym przypadku (gdy l = 0 oraz p = n − 1) ta róz˙ nica poziomów to wysoko´sc´ stogu h. Oczywi´scie, 1 + 2 + . . . + 2h−1 + 1 6 n 6 1 + 2 + 4 + . . . 2h . Stad, ˛ h = θ (log2 n).
Wniosek. Przesiewanie ma złoz˙ ono´sc´ pesymistyczna˛ θ (log2 n).
B u d u j S t o g ( i n t n , i n t A[MAX] ) { f o r ( i = ( n − 2 ) / 2 ; i >=0; i −−) P r z e s i e w a n i e ( i , n −1 ,A ) ; } Złoz˙ ono´sc´ BudujStog:
n · θ (log2 n) = θ (n log2 n) 2
. Uwaga. Moz˙ na nawet pokaza´c, z˙ e BudujStog ma złoz˙ ono´sc´ θ (n).
S o r t o w a n i e S t o g o w e ( i n t n , i n t A[MAX] ) { BudujStog ( n ,A) ; f o r ( i =n −1; i >=1; i −−) { x=A [ 0 ] ; A[ 0 ] =A[ i ] ; A[ i ] = x ; P r z e s i e w a n i e ( 0 , i −1); } SortowanieStogowe: θ (n log2 n) + n · θ (log2 n) = θ (n log2 n) FAKT. Pesymistyczna (i s´rednia) złoz˙ ono´sc´ czasowa sortowania stogowego jest równa T (n) = θ (n · log2 n). ZALETA˛ sortowania stogowego jest to, z˙ e w przeciwie´nstwie do sortowania przez scalanie nie uz˙ ywamy z˙ adnej dodatkowej tablicy.
5
SORTOWANIE METODA˛ ZLICZANIA Jest to metoda dogodna do sortowania tablicy liczb całkowitych z ustalonego (niezbyt duz˙ ego) przedziału. Główna idea algorytmu polega na wyznaczeniu dla kaz˙ dego elementu tablicy ile jest w tablicy elementów nie wi˛ekszych od niego. Zakładamy, z˙ e elementy tablicy maja˛ warto´sci całkowite ze zbioru {0, 1, 2, . . . , m − 1}. S o r t o w a n i e _ p r z e z _ z l i c z a n i e ( i n t A[MAX] , i n t n ) { i n t C [ max ] ; / / m<=max i n t D[MAX] ; f o r ( i = 0 ; i
6
Literatura: (1) B. Stroustrup "J˛ezyk C++" (2) H. Schildt "Programowanie C++" ´ (3) J. Gr˛ebosz Symfonia C++", t. II, I C++ rozszerza moz˙ liwo´sci j˛ezyka C pod katem: ˛ 1) bardziej rygorystycznej kontroli typów (nie wszystko co jest poprawne w C jest poprawne w C++); 2) uzupełnie´n (nieobiektowych): – mniej restrykcyjny porzadek ˛ definicji i instrukcji (np. deklaracja zmiennych nie musi si˛e znajdowa´c na poczatku ˛ programu) – wprowadzenie operatora zakresu, – nowy typ 00referencja do00; – moz˙ liwo´sc´ przecia˛z˙ ania identyfikatorów, – funkcje ze zmienna˛ liczba˛ parametrów; 3) programowania obiektowego (moz˙ liwo´sc´ tworzenia klas obiektów, które okre´slaja˛ zarówno zestaw danych, jak i operacje wykonywane na tych danych) Przykład. # include
/ / pola składowe
public : zespolona ( ) ; / / k o n s t r u k t o r bezparametrowy zespolona ( float x , float y ) ; / / konstruktor / / z dwoma p a r a m e t r a m i f l o a t modul ( ) ; f l o a t argument ( ) ; zespolona dodaj ( zespolona ) ; void wczytaj ( ) ; void wypisz ( ) ; }; zespolona : : zespolona () / / konstruktor { re = 0; / / bezparametrowy im = 0 ; }
7
zespolona : : zespolona ( float x , float y ) { re = x ; / / k o n s t r u k t o r z dwoma im = y ; / / parametrami } f l o a t z e s p o l o n a : : modul ( ) { r e t u r n s q r t ( r e ∗ r e +im∗im ) ; / / t r z e b a d o ł a˛ c z y c´ b i b l i o t e k e˛ / / m a t e m a t y c z n a˛ } void zespolona : : wczytaj ( ) { c o u t << " P o d a j c z e˛ s´ c´ r z e c z y w i s t a˛ i u r o j o n a˛ " << e n d l ; c i n >> r e >>im ; } void zespolona : : wypisz ( ) { c o u t << r e << " + i " <
main ( ) { z e s p o l o n a z1 , z2 ( 1 , 2 ) , z3 ; z1 . w c z y t a j ( ) ; c o u t << " Moduł z1 w y n o s i " << z1 . modul ( ) ; c o u t << " Moduł z2 w y n o s i " << z2 . modul ( ) ; / / 2 . 2 3 . . . c o u t << z1 + z2 ; / / z´ l e , bo c o u t n i e d z i a ł a d l a t y p u / / z e s p o l o n a a l e d z i a ł a t y l k o dla typów / / wbudowanych ( i n t , f l o a t , char , . . . ) ( z1 . d o d a j ( z2 ) ) . w y p i s z ( ) ; z3 = z1 . d o d a j ( z2 ) ; }
Definiowanie klas c l a s s nazwa_klasy { [ m o d y f i k a t o r _ p r a w _ d o s t e˛ p u : ] deklaracje_komponentów ; .. . [ m o d y f i k a t o r _ p r a w _ d o s t e˛ p u : ] deklaracje_komponentów ; };
Rodzaje komponentów (składowych): • pola danych (pola składowe) //np. re, im • funkcje składowe (funkcje i operacje na danych składowych)
Pod wzgl˛edem praw dost˛epu komponenty dzielimy na: 1) prywatne (modyfikator private) - dost˛ep jest moz˙ liwy tylko dla innych komponentów klasy oraz tzw. funkcji zaprzyja´znionych; P r z y k ł a d . main ( ) { c o u t << z1 . r e ; / / n i e z a d z i a ł a bo f u n k c j a main ( ) / / n i e ma d o s t e˛ p u do p r y w a t n y c h p ó l / / składowych kl as y zespolona } 2) publiczne (modyfikator public) - ogólnie dost˛epne (nawet przez inne funkcje niezwiazane ˛ z ta˛ klasa); ˛ 8
3) chronione/zabezpieczone (modyfikator protected) - dost˛epne dla funkcji składowych oraz dla klas wywodzacych ˛ si˛e od tej klasy (pochodnych tej klasy, zwiazane ˛ z dziedziczeniem).
Uwaga Zakres widzialno´sci komponentów obejmuje cały blok klasy (bez wzgl˛edu na miejsce deklaracji w klasie). Dopóki w definicji klasy nie pojawi si˛e z˙ adna z etykiet (public, protected) to przez domniemanie wszystkie komponenty maja˛ dost˛ep private.
Klasa moz˙ e by´c zadeklarowana: • na zewnatrz ˛ wszystkich funkcji programu (tzw. klasa zewn˛etrzna) - jest ona widoczna we wszystkich plikach programu; • wewnatrz ˛ jakiej´s funkcji (tzw. klasa lokalna) - jej zakres widoczno´sci nie wykracza poza zasi˛eg tej funkcji; • wewnatrz ˛ innej klasy (tzw. klasa zagniez˙ dz˙ ona) - jej zakres widoczno´sci nie wykracza poza zakres klasy zewn˛etrznej.
Definicja funkcji składowej wyst˛epujaca ˛ poza ciałem klasy: t y p _ z w r a c a n e j _ w a r t o s´ c i n a z w a _ k l a s y : : n a z w a _ f u n k c j i ( l i s t a _ a r g ) ↑ operator zakresu
Dwuargumentowy operator zakresu :: (podwójny dwukropek) poprzedzony nazwa˛ klasy okre´sla, z˙ e funkcja wyst˛epujaca ˛ po :: jest składowa˛ tejz˙ e klasy. np . f l o a t z e s p o l o n a : : modul ( ) { r e t u r n s q r t ( r e ∗ r e +im∗im ) ;
Definiowanie (deklarowanie) obiektów: nazwa_klasy l i s t a _ o b i e k t ó w ; np .
zespolona zespolona zespolona zespolona
z; z1 , z2 ( 1 , 2 ) ; tab [10]; ∗wsk ;
Uz˙ ycie w programie funkcji składowych dla obiektów: zm_obiekt . nazwa_funkcji_składowej ( l_parametrów ) Przykłady: z e s p o l o n a z , z1 ( 1 , 2 ) , z3 ; z . wczytaj ( ) ; z . wypisz ( ) ; ( z . d o d a j ( z1 ) ) . w y p i s z ( ) ; z3 = z . d o d a j ( z1 ) ;
Przeładowanie (przecia˛z˙ anie) nazw funkcji Moz˙ na w programie umie´sci´c wi˛ecej niz˙ jedna˛ funkcj˛e o tej samej nazwie, pod warunkiem, z˙ e te funkcje b˛eda˛ róz˙ niły si˛e argumentami (ich liczba˛ lub typem argumentów). Przykład. 9
z e s p o l o n a pomnoz ( z e s p o l o n a z ) / / m n o z˙ e n i e dwóch l i c z b z e s p o l o n y c h z e s p o l o n a pomnoz ( f l o a t x ) / / m n o z˙ e n i e l i c z b y z e s p o l o n e j / / p r z e z l i c z b e˛ r z e c z y w i s t a˛ Typ zwracany przez funkcj˛e NIE jest brany pod uwag˛e (przy sprawdzaniu czy te funkcje si˛e róz˙ nia). ˛ (Np. majac ˛ juz˙ funkcj˛e zespolona pomnoz(float) nie moz˙ na doda´c funkcji float pomnoz(float)). Przeładowanie nazw funkcji dotyczy nie tylko funkcji składowych, ale i pozostałych funkcji.
Funkcje z parametrami domniemanymi (funkcje z róz˙ na˛ liczba˛ argumentów) Przykład. zespolona : : zespolona () { r e = 0 ; im = 0} zespolona : : zespolona ( float x , float y ) { r e = x ; im = y } Chcieliby´smy, aby zespolona z(5) spowodowała, z˙ e z = 5 + i0.
Powyz˙ sze dwa konstruktory moz˙ na zastapi´ ˛ c jednym konstruktorem: z e s p o l o n a : : z e s p o l o n a ( f l o a t x =0 , f l o a t y = 0 ) { r e = x ; im = y } Wtedy
zespolona z ; zespolona z (1 ,2); zespolona z ( 5 ) ;
/ / z = 0 + i0 ; // z = 1 + 2i ; / / z = 5 + i0 ;
Funkcje z argumentami domniemanymi moz˙ na wywoła´c z mniejsza˛ liczba˛ parametrów niz˙ wynikałoby to z deklaracji funkcji. Brakujace ˛ w wywołaniu argumenty otrzymuja˛ warto´sci domniemane. Jez˙ eli warto´sc´ argumentu zostanie podana, to przesłania ona warto´sc´ domniemana.˛ Parametry domniemane musza˛ sta´c na ko´ncu listy parametrów. ´ np . z e s p o l o n a : : z e s p o l o n a ( f l o a t x =0 , f l o a t y ) ; / / ZLE zespolona : : zespolona ( float x , float y =0); / / d o b r z e a l e g o r z e j n i z˙ z e s p o l o n a : : z e s p o l o n a ( f l o a t x =0 , f l o a t y = 0 ) ; Zdefiniowanie obiektu jest w rzeczywisto´sci wywołaniem specjalnej funkcji - konstruktora. Konstruktory moz˙ emy definiowa´c sami, a je´sli tego nie uczynimy, to kompilator doda tzw. konstruktor domy´slny: nazwa_klasy ( ) {}; Je´sli nawet nie zdefiniowaliby´smy z˙ adnego konstruktora dla klasy zespolona, to i tak ta klasa b˛edzie działa´c. Po zadeklarowaniu obiektu: zespolona z ; 10
obiekt z istnieje (czyli ma przydzielona˛ pami˛ec´ na re i im ale te warto´sci sa˛ nieokre´slone (losowe)). Ale gdyby w klasie został zadeklarowany tylko konstruktor zespolona ( float x , float y ) ; to po zadeklarowaniu obiektu: zespolona z ; kompilator zgłosi bład. ˛ bo nie ma konstruktora bezparametrowego, a domy´slny (bezparametrowy) nie został utworzony (bo jest inny konstruktor z dwoma parametrami).
Funkcje operatorowe (przecia˛z˙ anie operatorów) Jest to szczególny przypadek przeładowywania nazw funkcji, w którym dodajemy nowe znaczenia operatorom juz˙ wyst˛epujacym ˛ w j˛ezyku C++. Chodzi o to, aby moz˙ na było np. napisa´c z1+z2 zamiast z1.dodaj(z2). W tym wypadku znany operator dodawania + (wykorzystywany dla typów int, float, ...) zyskuje dodatkowe nowe znaczenie, a mianowicie dodawania liczb zespolonych). Funkcje operatorowe moz˙ na tworzy´c dla wi˛ekszo´sci operatorów j˛ezyka C++ pod warunkiem, z˙ e cho´c jeden z argumentów jest typu obiektowego lub funkcja operatorowa jest cz˛es´cia˛ klasy. Prototyp funkcji operatorowej b˛edacej ˛ składowa˛ klasy: typ_wyniku operator @ ( void ) ← f u n k c j a jednoargumentowa ↑ symbol o p e r a t o r a
typ_wyniku operator @ ( typ_argu arg1 ) ← f u n k c j a ↑ dwuargumentowa symbol o p e r a t o r a Przykład class zespolona { .. . zespolona operator ∗( zespolona ) ; zespolona operator ∗( f l o a t ) / / z 1 ∗5 ⇔ z 1 . o p e r a t o r ∗ ( 5 ) }; / / a l e n i e 5∗ z 1 !
z e s p o l o n a z e s p o l o n a : : o p e r a t o r ∗ ( z e s p o l o n a z2 ) { z e s p o l o n a z1 ; / / z m i e n n a p o m o c n i c z a z1 . r e = r e ∗ z2 . r e −im∗ z2 . im ; z1 . im = r e ∗ z2 . im+im∗ z2 . r e ; r e t u r n z1 ; } zespolona zespolona : : operator ∗( f l o a t x ) { z e s p o l o n a z1 ; z1 . r e = r e ∗ x ; z1 . im = im∗ x ; r e t u r n z1 ; } Je´sli funkcja operatorowa nie jest funkcja˛ składowa˛ klasy, wtedy jej deklaracja jest nast˛epujaca: ˛ typ_wyniku operator@ ( typ_argumentu_1 ) ← f u n k c j a jednoargumentowa 11
typ_wyniku operator@ ( t y p _ a r g 1 arg1 , t y p _ a r g 2 arg2 ) ← f u n k c j a dwuargumentowa
c l a s s wektor3 { float x ,y , z ; public : wektor3 ( ) ; wektor3 ( f l o a t , f l o a t , f l o a t ) ; wektor3 operator ∗( wektor3 ) ; / / i l o c z y n wektorowy wektor3 operator ∗( f l o a t ) ; / / m n o z˙ e n i e p r z e z s k a l a r ´ f l o a t operator ∗( wektor3 ) ; / / i l o c z y n s k a l a r n y ZLE f l o a t operator ^( wektor3 ) ; / / iloczyn skalarny };
Uwagi o przeładowywaniu operatorów (1) Przeładowa´c moz˙ na prawie kaz˙ dy operator, tzn.: + , - , * , / , % , ^ , & , ~ , ! , = , < , > ,...,new, delete, (),[], ale nie moz˙ na .,.*,::,?: (2) Nie moz˙ na wymy´sla´c swoich operatorów i ich przecia˛z˙ a´c. (3) Operator jest przecia˛z˙ ony wzgl˛edem klasy, w której został zadeklarowany, ale nie traci z˙ adnego ze swoich dotychczasowych znacze´n. (4) Nie moz˙ na zmieni´c składni wyraz˙ enia dla danego operatora, priorytetu operatora i reguł łaczno´ ˛ sci. (5) Przecia˛z˙ one operatory nie moga˛ mie´c argumentów domniemanych. np . z e s p o l o n a o p e r a t o r ^ ( i n t n = 2 ) / / z 1=z ^ ; − z´ l e z e s p o l o n a p o t e g a ( i n t n =2) / / dobrze (6) Funkcje operatorowe nie sa˛ dziedziczone (z wyjatkiem ˛ operatora =). (7) Funkcja operatorowa, która jest funkcja˛ składowa˛ klasy wymaga, aby obiekt stojacy ˛ po lewej stronie operatora @ był obiektem jej klasy. (8) Jest kilka operatorów, które automatycznie sa˛ generowane dla kaz˙ dej klasy: = , & , , , new , delete. (9) Aktywowanie funkcji operatorowej na rzecz danego obiektu odbywa si˛e zgodnie ze schematem składniowym dla danego operatora w C++. W przypadku operatorów dwuargumentowych wyraz˙ enie pojawiajace ˛ si˛e po lewej stronie operatora jest obiektem, na rzecz którego funkcja operatorowa jest aktywowana.
Funkcje zaprzyja´znione Funkcje zaprzyja´znione z klasa˛ maja˛ dost˛ep do wszystkich (równiez˙ prywatnych) komponentów klasy, chociaz˙ same do tej klasy (jako funkcje składowe) nie nalez˙ a.˛
Definicja funkcji zaprzyja´znionej z klasa: ˛ 1) Je´sli funkcja nie jest funkcja˛ składowa˛ innej klasy, to umieszczamy w definicji klasy: friend typ_zwracany nazwa_funkcji ( argumenty_funkcji ) ;
12
2) Je´sli za´s funkcja byłaby składowa˛ klasy B, to umieszczamy w definicji klasy A: friend typ_zwracany B : : nazwa_funkcji ( argumenty_funkcji ) ; Przykład. zespolona operator ∗( f l o a t x , zespolona z ) { z e s p o l o n a z1 ; z1 . r e = x∗ z . r e ; z1 . im = x∗ z . im ; r e t u r n z1 ; } Wtedy w main() moz˙ na napisa´c np.: z2 =5∗ z1 ; Aby powyz˙ sza funkcja mogła poprawnie działa´c musi zosta´c zaprzyja´zniona˛ z klasa˛ zespolona tzn. class zespolona { .. . friend zespolona operator ∗( float , zespolona ) ; } Uwaga. Je´sli funkcja zaprzyja´zniona nie jest składowa˛ klasy (jak w p. 1), to nie moz˙ e by´c aktywowana na rzecz z˙ adnych obiektów.
Zaprzyja´znianie klas Moz˙ na zaprzyja´zni´c cała˛ klas˛e A z inna˛ klasa˛ B friend c l a s s nazwa_klasy ; Przykład. class A { .. . friend c l as s B; .. . }
/* Klasa A mówi, z˙ e klasa B jest jej przyjacielem i z˙ e B moz˙ e w niej korzysta´c ze wszystkich komponentów czyli wszystkie funkcje składowe klasy B maja˛ dost˛ep do wszystkich pól składowych i funkcji składowych klasy A. Uwaga. Relacja zaprzyja´zniania nie jest symetryczna. */
class B { .. . }
Operatory new i delete new typ_danej - operator new przydziela (alokuje) obszar pami˛eci potrzebny do przechowywania obiektu typu "typ-danej"i zwraca wska´znik do poczatku ˛ tego obszaru (new ⇔ malloc). Je´sli nie uda si˛e przydzieli´c tej pami˛eci, to zwraca wska´znik pusty NULL. delete wska´znik - zwalnia obszar pami˛eci wskazywanej przez ten "wska´znik"(delete ⇔ free)
Przykład. i n t ∗wsk , ∗ t a b ; wsk = new i n t ; 13
t a b = new i n t [ 1 0 ] tab [0] = 5; tab [2] = 7; d e l e t e wsk ; delete [] tab ;
/ / ∗ tab = 5; / / ∗ ( t a b +2) = 7 ;
Przykład. c l a s s wektor { int n ; f l o a t ∗wsk ; public : wektor ( ) { } ; wektor ( i n t ) ; friend wektor operator ∗( float , wektor ) ; f r i e n d f l o a t operator ∗( wektor , wektor ) ; }; w e k t o r : : w e k t o r ( i n t m) { n=m; wsp = new f l o a t [ n ] ; / / 0 . . . n−1 }
wektor operator ∗( f l o a t x , wektor v ) { wektor u ( v . n ) ; f o r ( i = 0 ; i
f l o a t operator ∗( wektor u , wektor v ) { f l o a t wart =0; i f ( u . n ! = v . n ) r e t u r n 0 ; / / umowa else { f o r ( i n t i = 0 ; i
14
Przykład. c l a s s punkt ; c l a s s wektor { .. . f r i e n d punkt operator +( punkt , wektor ) ; }; c l a s s punkt { int n ; f l o a t ∗wsp ; .. . f r i e n d punkt operator +( punkt , wektor ) ; };
punkt operator +( punkt P , wektor v ) { i f ( P . n != v . n ) return P ; else { p u n k t Q( P . n ) ; f o r ( i n t i = 0 ; i
Zmienna this Zmienna this jest dost˛epna w kaz˙ dej funkcji składowej klasy (zdefiniowana niejawnie przez kompilator), która jest wska´znikiem na obiekt na rzecz którego funkcja została aktywowana.
Przykład. c l a s s wektor { .. . wektor zwieksz ( f l o a t k ) ; };
wektor wektor : : zwieksz ( f l o a t k ) { f o r ( i n t i = 0 ; i
15
Destruktor Likwidowaniem obiektu zajmuje si˛e dekonstruktor (który moz˙ e by´c zdefiniowany w ciele klasy albo zostanie dodany automatycznie (wtedy ~nazwa_klasy() {};)).
Definicja destruktora ~nazwa_klasy ( ) { .. . } Destruktor, tak jak konstruktor, nie zwraca z˙ adnej warto´sci. Przed definicja˛ destruktora nie moz˙ na wpisa´c nawet void. Destruktor NIE ma z˙ adnych parametrów. Destruktor moz˙ e by´c tylko jeden.
class zespolona { f l o a t r e , im ; .. . }; W klasie zespolona destruktor nie jest konieczny, bo destruktor domy´slny zwolni pami˛ec´ zajmowana˛ przez re i im.
c l a s s wektor { int n ; f l o a t ∗wsp ; .. . ~wektor ( ) ; }; w e k t o r : : w e k t o r ( i n t m) . { .. wsp = new i n t [m ] ; } Gdyby´smy nie mieli destruktora, destruktor domy´slny zwolniłby tylko miejsce zajmowane przez zmienna˛ n i przez wska´znik wsp ale nie zwolniłby pami˛eci zajmowanej przez cała˛ tablic˛e. wektor : : ~ wektor ( ) { d e l e t e [ ] wsp ; }
Referencje jako argumenty funkcji Przykład 1. void zwieksz2razy ( i n t a ) / / przekazywanie parametru { a =2∗ a } / / p r z e z w a r t o s´ c´
16
main ( ) { i n t x =1; zwieksz2razy ( x ) ; c o u t <
Deklaracja referencji t y p _ z m i e n n e j &nazwa z m i e n n e j ; Przekazujac ˛ do funkcji argument przez referencj˛e unikamy kopiowania jego warto´sci. W rzeczywisto´sci przekazywany jest adres tego argumentu. Wszystkie operacje wewnatrz ˛ funkcji dotyczace ˛ referencji do tego argumentu dotycza˛ samego argumentu. Przekazana referencja do argumentu jest synonimem tego argumentu. Czyli tak jak w poprzednim przykładzie a jest synonimem x.
Pola i funkcje statyczne w klasie Pola statyczne to pola wspólne dla wszystkich obiektów danej klasy (w pami˛eci wyst˛epuje tylko jeden obszar dla pola statycznego niezalez˙ nie od liczby obiektów).
Deklaracja składnika pola statycznego: s t a t i c typ_zmiennej nazwa_pola_statycznego ; Wystapienie ˛ deklaracji takiej zmiennej nie jest równowaz˙ ne jego definicji, która powinna pojawi´c si˛e poza ciałem klasy.
17
Przykład. c l a s s wektor { int n ; f l o a t ∗wsp ; public : s t a t i c int liczba_wektorow ; .. . } main ( ) { i n t wektor : : liczba_wektorow ; / / d e f i n i c j a zmiennej / / liczba_wektorow wektor v ; ´ v . l i c z b a _ w e k t o r o w = 1 ; / / v . n =3; ZLE / ∗ a l b o mo z˙ na t e z˙ : int w e k t o r : : l i c z b a _ w e k t o r o w =0; ( gdy n i e j e s t z a d e k l a r o w a n y z˙ a d e n o b i e k t t y p u w e k t o r ) ∗ / Zastosowanie pól statycznych
• Gdy obiekty chca˛ si˛e porozumiewa´c mi˛edzy soba.˛ • Gdy wszystkie maja˛ t˛e sama˛ cech˛e, która moz˙ e si˛e zmienia´c. • Gdy zliczamy liczb˛e elementów danej klasy.
W tym ostatnim przypadku w konstruktorze moz˙ emy wtedy doda´c: wektor : : wektor ( ) // ( int n) {. . . l i c z b a _ w e k t o r o w ++; } Do modyfikacji i odczytu pól statycznych najlepiej uz˙ y´c statycznych funkcji składowych, przy czym pola statyczne powinny by´c prywatne.
Funkcje statyczne to takie funkcje, które moz˙ emy wywoła´c nawet gdy nie istnieje z˙ aden obiekt danej klasy. Funkcje te nie moga˛ si˛e odwoływa´c do niestatycznych składowych klasy bez jawnego wskazania obiektu (bo nie sa˛ aktywowane na rzecz z˙ adnego obiektu). Przykład. c l a s s wektor { private : .. . s t a t i c int liczba_wektorow ; public : s t a t i c v o i d u s t a l _ l _ w e k t o r o w ( i n t n ) { l i c z b a _ w e k t o r o w =n ; } s t a t i c i n t odczytaj_l_wektorow ( void ) { return liczba_wektorow ; } .. . }; main ( ) { i n t wektor : : liczba_wektorow ; 18
wektor : : ustal_l_wektorow ( 0 ) ; c o u t << w e k t o r : : o d c z y t a j _ l _ w e k t o r o w ( ) ; wektor u , v ; c o u t <
Klasa jako składowa klasy Majac ˛ zdefiniowane klasy moz˙ emy budowa´c klasy złoz˙ one z tych wcze´sniej zdefiniowanych klas. Przykład. class silnik { .. . }; c l a s s podwozie { .. . }; c l a s s nadwozie { int kolor ; .. . }; c l a s s samochod { s i l n i k nazwa_silnika ; p o d w o z i e nazwa_podwozia ; nadwozie nazwa_nadwozia ; .. . }; Przykład c l a s s wektor / / w R2 { float x ,y; public : wektor ( ) { } ; wektor ( float , f l o a t ) ; void wczytaj ( ) ; void wypisz ( ) ; }; wektor : : wektor ( f l o a t a , f l o a t b ) { x=a ; y=b ; } void wektor : : wczytaj ( ) 19
{ c o u t << " P o d a j w s p ó ł r z e˛ d n e w e k t o r a : " ; c i n >>x>>y ; } void wektor : : wypisz ( ) { c o u t << " [ " <
Dziedziczenie Mechanizm dziedziczenia polega na przyjmowaniu własno´sci jednej klasy (bazowej) przez inna˛ klas˛e (pochodna). ˛ W skład klasy pochodnej moga˛ wchodzi´c wybrane pola klasy bazowej uzupełnione w klasie pochodnej o nowe pola danych i nowe funkcje składowe. Mechanizm ten pozwala tworzy´c ciagi ˛ coraz bardziej rozbudowanych klas przejmujacych ˛ własno´sci innych klas. Definicja c l a s s n a z w a _ k l a s y _ p o c h o d n e j : m o d y f i k a t o r _ p r a w _ d o s t e˛ p u nazwa_kl_bazowej { .. . }; 20
Jez˙ eli w nagłówku klasy pochodnej uz˙ yto modyfikatora dost˛epu public to mamy do czynienia z tzw. dziedziczeniem publicznym, je´sli za´s uz˙ yto słowa private, to jest to tzw. dziedziczenie prywatne (rzadko uz˙ ywane).
W przypadku dziedziczenia publicznego wszystkie składowe publiczne klasy bazowej staja˛ si˛e jednocze´snie składowymi publicznymi klasy pochodnej. Uz˙ ytkownik klasy pochodnej b˛edzie mógł korzysta´c wtedy ze składowych publicznych klasy bazowej. Prywatne składowe klasy bazowej nie sa˛ dost˛epne dla funkcji składowych klasy pochodnej (o ile nie sa˛ zaprzyja´znione). Ale mamy dost˛ep do nich poprzez publiczne funkcje składowe klasy bazowej. Moz˙ na równiez˙ w klasie bazowej zadeklarowa´c, z˙ e pewne składowe sa˛ chronione, tzn. protected, zamiast prywatne. Wtedy składowe chronione sa˛ uwaz˙ ane za publiczne dla funkcji składowych klasy pochodnej (i prywatne dla uz˙ ytkownika klasy pochodnej.)
Nawet jez˙ eli jaka´s składowa (pole składowe lub funkcja składowa) klasy bazowej została predefiniowana w klasie pochodnej (tzn. nazwa pola lub funkcji składowej w klasie pochodnej jest taka sama jak w klasie bazowej) to i tak funkcje składowe i uz˙ ytkownik klasy pochodnej moga˛ w dalszym ciagu ˛ korzysta´c z niej. Dost˛ep do predefiniowanej składowej umoz˙ liwia operator zakresu (::). Przykład. c l a s s punkt { protected : f l o a t x , y ; public : punkt ( ) { } ; punkt ( float , f l o a t ) ; void wczytaj ( ) ; void wypisz ( ) ; }; c l a s s punkt_kolorowy : public punkt { int kolor ; public : punkt_kolorowy ( ) { } ; punkt_kolorowy ( float , float , i n t ) ; void wczytaj ( ) ; void wypisz ( ) ; }; punkt_kolorowy : : punkt_kolorowy ( f l o a t a , f l o a t b , i n t n ) : punkt ( a , b ) / / ! { k o l o r =n ; } void punkt_kolorowy : : wczytaj ( ) { punkt : : wczytaj ( ) ; c o u n t << " P o d a j k o l o r p u n k t u : " ; c i n >> k o l o r ; } void punkt_kolorowy : : wypisz ( ) { punkt : : wypisz ( ) ; c o u t << " k o l o r = " << k o l o r ; / / ( 1 , 5 ) k o l o r =5 }
21
Mo˙zliwe schematy dziedziczenia 1) proste k l a s a bazowa ↓ k l a s a pochodna 2) sekwencyjne (wielopokoleniowe) k l a s a bazowa ↓ k l a s a pochodna 1 ↓ k l a s a pochodna 2 ↓ .. . 3) wielostronne (wiele klas dziedziczy jedna˛ klas˛e bazowa) ˛ k l a s a bazowa .−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−. ↓ ↓ ↓ k l a s a pochodna 1 k l a s a pochodna 2 k l a s a pochodna 3 4) wielobazowe (klasa pochodna dziedziczy po wielu klasach bazowych) k l a s a bazowa 1 k l a s a bazowa 2 | ____________________ | ↓ k l a s a pochodna Przykład dziedziczenia wielobazowego. c l a s s punkt { .. . }; c l a s s wektor { .. . }; c l a s s w e k t o r z a c z e p i o n y 2 : p u b l i c wektor , p u b l i c punkt { .. . public : wektorzaczepiony2 ( ) { } ; wektorzaczepiony2 ( f l o a t a , f l o a t b , f l o a t c , f l o a t d ) ; void wczytaj ( ) ; void wypisz ( ) ; .. . }; wektorzaczepiony2 : : wektorzaczepiony2 ( f l o a t a , f l o a t b , float c , float d ): wektor ( a , b ) , punkt ( c , d ) { } wektorzaczepiony2 : : wczytaj ( ) { wektor : : wczytaj ( ) ; 22
punkt : : wczytaj ( ) ; } wektorzaczepiony2 : : wypisz ( ) { wektor : : wypisz ( ) ; punkt : : wypisz ( ) ; / / [1 ,2](3 ,4) }
23
Struktury danych Tworzymy je w celu lepszego gromadzenia i szybszego dost˛epu do danych. Strukturami danych sa˛ m.in. tablice i struktury (struct).
Stosy i kolejki Sa˛ to struktury danych, w których operacje wstaw i usu´n jednoznacznie okre´slaja˛ miejsce wstawienia i usuni˛ecia elementu.
Stos - struktura danych typu LIFO (last in, first out)
Kolejka - struktura danych typu FIFO (first in, first out)
Stos Wstawiamy element na szczyt stosu, usuwamy element równiez˙ ze szczytu stosu.
Implementacja tablicowa stosu class stos { int szczyt ; t y p _ k l u c z a t a b [ROZMIAR ] ; public : stos (); int pusty ( ) ; v o i d wstaw ( t y p _ k l u c z a x ) ; t y p _ k l u c z a zwroc ( ) ; / / z w r a c a w a r t o s´ c´ na s z c z y c i e void usun ( ) ; }; stos :: stos () { s z c z y t =−1; } int stos : : pusty () { i f ( s z c z y t ==−1) r e t u r n 1 ; e l s e return 0; } v o i d s t o s : : wstaw ( t y p _ k l u c z a x ) { i f ( s z c z y t < ROZMIAR−1) { s z c z y t ++; t a b [ s z c z y t ] = x ; / / t a b [++ s z c z y t ]= x ; } } t y p _ k l u c z a s t o s : : zwroc ( ) { i f ( pusty ()==0) return tab [ s z c z y t ] ; } void s t o s : : usun ( ) { i f ( pusty ()==0) { s z c z y t −−; } }
24
Implementacja wska´znikowa stosu struct el_stosu { typ_klucza klucz ; el_stosu ∗ nast ; }; class stos { el_stosu ∗ szczyt ; public : stos (); int pusty ( ) ; v o i d wstaw ( t y p _ k l u c z a x ) ; void usun ( ) ; t y p _ k l u c z a zwroc ( ) ; ~stos (); }; stos :: stos () { s z c z y t = NULL ; } int stos : : pusty () { i f ( s z c z y t ==NULL) r e t u r n 1 ; e l s e return 0; } v o i d s t o s : : wstaw ( t y p _ k l u c z a x ) { e l _ s t o s u ∗pom ; pom = new e l _ s t o s u ; i f ( pom ! = NULL) / / u d a ł o s i e˛ z a r e z e r w o w a c´ {pom−> k l u c z =x ; pom−> n a s t = s z c z y t ; s z c z y t =pom ; } } t y p _ k l u c z a s t o s : : zwroc ( ) { i f ( pusty ()==0) r e t u r n s z c z y t −> k l u c z ; } void s t o s : : usun ( ) { i f ( pusty ()==0) { e l _ s t o s u ∗pom ; pom= s z c z y t ; s z c z y t = s z c z y t −> n a s t ; d e l e t e pom ; } } stos ::~ stos () { while ( pusty ()==0) usun ( ) ; }
25
Kolejka Wstawiamy element na koniec kolejki, usuwamy element z poczatku ˛ kolejki.
Implementacja wska´znikowa kolejki
struct el_kolejki { typ_klucza klucz ; el_kolejki ∗ nast ; }; class kolejka { e l _ k o l e j k i ∗ poczatek , ∗ koniec ; public : kolejka ( ) ; int pusta ( ) ; v o i d wstaw ( t y p _ k l u c z a x ) ; void usun ( ) ; t y p _ k l u c z a zwroc ( ) ; / / z w r a c a z p o c z a˛ t k u ~kolejka ( ) ; }; kolejka : : kolejka () { p o c z a t e k = k o n i e c =NULL ; } int kolejka : : pusta () { i f ( p o c z a t e k ==NULL) r e t u r n 1 ; e l s e return 0; } v o i d k o l e j k a : : wstaw ( t y p _ k l u c z a x ) { e l _ k o l e j k i ∗pom ; pom = new e l _ k o l e j k i ; i f ( pom ! = NULL) {pom−> k l u c z =x ; i f ( pusta ()==1) p o c z a t e k = k o n i e c =pom ; else { k o n i e c −> n a s t =pom ; k o n i e c =pom ; } } } t y p _ k l u c z a k o l e j k a : : zwroc ( ) { i f ( pusta ()==0) r e t u r n p o c z a t e k −> k l u c z ; } void k o l e j k a : : usun ( ) { i f ( pusta ()==0) { e l _ k o l e j k i ∗pom ; pom= p o c z a t e k ; i f ( p o c z a t e k == k o n i e c ) p o c z a t e k = k o n i e c =NULL ; else / / p o c z a t e k 6= k o n i e c p o c z a t e k = p o c z a t e k −> n a s t ; 26
d e l e t e pom ; } } kolejka ::~ kolejka () { while ( pusta ()==0) usun ( ) ; } Implementacja tablicowa (cykliczna) kolejki class kolejka { int poczatek , koniec ; t y p _ k l u c z a t a b [ROZMIAR ] ; public : kolejka ( ) ; int pusta ( ) ; v o i d wstaw ( t y p _ k l u c z a x ) ; void usun ( ) ; t y p _ k l u c z a zwroc ( ) ; }; Kolejka jest pusta ⇔ poczatek ˛ = koniec. Kolejka jest pełna ⇔ poczatek ˛ = koniec + 1 (mod ROZMIAR). Poczatek ˛ wskazuje pierwszy element w kolejce, a koniec wskazuje komórk˛e za ostatnim elementem w kolejce. W kolejce moz˙ emy mie´c maksymalnie ROZMIAR-1 elementów. kolejka : : kolejka () { poczatek = koniec =0; } int kolejka : : pusta () { i f ( p o c z a t e k == k o n i e c ) r e t u r n 1 ; e l s e return 0; } v o i d k o l e j k a : : wstaw ( t y p _ k l u c z a x ) { i f ( k o n i e c +1)%ROZMIAR! = p o c z a t e k ) { t a b [ k o n i e c ]= x ; k o n i e c = ( k o n i e c +1)%ROZMIAR ; } } void k o l e j k a : : usun ( ) { i f ( pusta ()==0) { p o c z a t e k = ( p o c z a t e k +1)%ROZMIAR ; } } t y p _ k l u c z a k o l e j k a : : zwroc ( ) { i f ( pusta ()==0) return tab [ poczatek ] ; }
27
Lista (jednokierunkowa) → ciag ˛ elementów tego samego rodzaju Implementacja wska´znikowa listy
struct e l _ l i s t y { typ_klucza klucz ; e l _ l i s t y ∗ nast ; }; class l i s t a { e l _ l i s t y ∗ glowa ; public : lista (); int pusta ( ) ; v o i d wstaw ( e l _ l i s t y ∗ poz , t y p _ k l u c z a x ) ; void w y p i s z _ l i s t e ( ) ; e l _ l i s t y ∗ wyszukaj ( t yp _k lu cz a ) ; t y p _ k l u c z a zwroc ( e l _ l i s t y ∗wsk ) ; v o i d u s u n ( e l _ l i s t y ∗ poz ) ; e l _ l i s t y ∗ n a s t e p n i k ( e l _ l i s t y ∗wsk ) ; e l _ l i s t y ∗ p o p r z e d n i k ( e l _ l i s t y ∗wsk ) ; ~lista (); }; lista :: lista () { glowa =NULL ; } int l i s t a : : pusta () { i f ( glowa ==NULL) r e t u r n 1 ; e l s e return 0; } Pozycja˛ elementu na li´scie (jednokierunkowej) nazywamy wska´znik do elementu, który poprzedza ten element w li´scie. Je´sli element jest pierwszy w li´scie, to jego pozycja˛ jest wska´znik pusty NULL. v o i d l i s t a : : wstaw ( e l _ l i s t y ∗ poz , t y p _ k l u c z a x ) { e l _ l i s t y ∗pom ; pom = new e l _ l i s t y ; i f ( pom ! = NULL) {pom−> k l u c z =x ; i f ( poz ==NULL) / / w s t a w i a n i e na p o c z a˛ t k u {pom−> n a s t = glowa ; glowa =pom ; } else / / p o z != NULL {pom−> n a s t =poz −> n a s t ; poz −> n a s t =pom ; } } } t y p _ k l u c z a l i s t a : : zwroc ( e l _ l i s t y ∗wsk ) { i f ( p u s t a ( ) = = 0 && wsk ! = NULL) r e t u r n wsk−> k l u c z ; } void l i s t a : : w y p i s z _ l i s t e ( ) { e l _ l i s t y ∗pom ; 28
pom= glowa ; w h i l e ( pom ! =NULL) { c o u t <
lista ::~ lista () { while ( pusta ()==0) u s u n (NULL ) ; }
Implementacja tablicowa listy jednokierunkowej class l i s t a { int n ; / / indeks ostatniego elementu t y p _ k l u c z a t a b [ROZMIAR ] ; public : lista (); int pusta ( ) ; int pelna ( ) ; v o i d wstaw ( i n t i n d e k s , t y p _ k l u c z a x ) ; void w y p i s z _ l i s t e ( ) ; i n t wyszukaj ( ty p _k lu cz a ) ; t y p _ k l u c z a zwroc ( i n t i n d e k s ) ; void usun ( i n t i n d e k s ) ; int nastepnik ( int indeks ) ; int poprzednik ( int indeks ) ; }; lista :: lista () { n=−1; } int l i s t a : : pusta () { i f ( n==−1) r e t u r n 1 ; e l s e return 0; } int pelna () { i f ( n==ROZMIAR−1) r e t u r n 1 ; e l s e return 0; } v o i d l i s t a : : wstaw ( i n t i n d e k s , t y p _ k l u c z a x ) { i f ( pelna ()==0) { f o r ( i n t i =n ; i >= i n d e k s ; i −−) t a b [ i +1]= t a b [ i ] ; t a b [ i n d e k s ]= x ; n ++; } void l i s t a : : w y p i s z _ l i s t e ( ) { f o r ( i n t i = 0 ; i <=n ; i ++) c o u t << t a b [ i ] < < " , " ; } i n t l i s t a : : wyszukaj ( ty p_ kl uc z a x ) { f o r ( i n t i = 0 ; i <=n ; i ++) i f ( t a b [ i ]== x ) r e t u r n i ; r e t u r n −1; } t y p _ k l u c z a l i s t a : : zwroc ( i n t i n d e k s ) { i f ( p u s t a ( ) = = 0 && i n d e k s != −1) return tab [ indeks ] ; } 30
void l i s t a : : usun ( i n t i n d e k s ) { i f ( p u s t a ( ) = = 0 && i n d e k s != −1) { f o r ( i n t i = i n d e k s ; i
Porównanie efektywno´sci wstaw(. . .) usun(. . .) wyszukaj(. . .) nastepnik(. . .) poprzednik(. . .) wyszukaj(. . .) w posortowanej tablicy lub lis´cie
Implementacja tablicowa O(n) O(n) O(n) O(1) O(1) O(log2 n)
Implementacja wska´znikowa O(1) O(1) O(n) O(1) O(n) O(n)
Lista dwukierunkowa struct e l l i s t y 2 { typ_klucza klucz ; e l l i s t y 2 ∗ nast , ∗ poprz ; }; class lista2 { e l l i s t y 2 ∗ glowa , ∗ ogon ; public : lista2 (); int pusta ( ) ; t y p _ k l u c z a zwroc ( e l l i s t y 2 ∗ ) ; void wypisz_od_glowy ( ) ; void wypisz_od_ogona ( ) ; e l l i s t y 2 ∗ wyszukaj ( ty p _k lu cz a ) ; e l l i s t y 2 ∗ nastepnik ( e l l i s t y 2 ∗); e l l i s t y 2 ∗ poprzednik ( e l l i s t y 2 ∗); v o i d wstaw ( e l l i s t y 2 ∗ , t y p _ k l u c z a ) ; void usun ( e l l i s t y 2 ∗ ) ; ~lista2 (); }; lista2 :: lista2 () { glowa =ogon=NULL ; } int l i s t a 2 : : pusta () { i f ( glowa ==NULL) r e t u r n 1 ; 31
e l s e return 0; } t y p _ k l u c z a l i s t a 2 : : zwroc ( e l l i s t y 2 ∗wsk ) { i f ( wsk ! =NULL) r e t u r n wsk−> k l u c z ; } void l i s t a 2 : : wypisz_od_glowy ( ) { e l l i s t y 2 ∗pom ; i f ( pusta ()==0) {pom= glowa ; w h i l e ( pom ! = ogon ) { c o u t <
pom=new e l l i s t y 2 ; i f ( pom ! =NULL) {pom−> k l u c z =x ; i f ( wsk==NULL) / / wstawiamy na p o c z a t e k {pom−> n a s t = glowa ; glowa −>p o p r z =pom ; glowa =pom ; / / glowa−>p o p r z=NULL ; } else else { i f ( wsk== ogon ) / / wstawiamy na k o n i e c { ogon−> n a s t =pom ; pom−>p o p r z =ogon ; ogon=pom ; / / ogon−>n a s t =NULL ; } else else {pom−> n a s t =wsk−> n a s t ; wsk−> n a s t =pom ; pom−>n a s t −>p o p r z =pom ; pom−>p o p r z =wsk ; } } } } Je´sli zadbamy o to, z˙ eby pierwszy element w li´scie miał pole poprz równe NULL oraz ostatmi element miał pole nast równe NULL, to niektóre funkcje moz˙ na zrobi´c odrobin˛e pro´sciej. e l l i s t y 2 ∗ l i s t a 2 : : wyszukaj2 ( t y p _ k l u c z a x ) { e l l i s t y 2 ∗pom ; pom= glowa ; w h i l e ( pom ! =NULL) { i f ( pom−> k l u c z ==x ) r e t u r n pom ; pom=pom−> n a s t ; } r e t u r n pom ; / / r e t u r n NULL ; } v o i d l i s t a 2 : : u s u n ( e l l i s t y 2 ∗wsk ) / / wsk w s k a z u j e e l e m e n t { / / do u s u n i e˛ c i a i f ( wsk ! =NULL) { i f ( glowa ! = ogon ) / / j e s t w i e˛ c e j n i z˙ 1 e l e m e n t w l i s´ c i e { i f ( wsk== glowa ) { glowa =glowa −> n a s t ; } else { i f ( wsk== ogon ) { ogon=ogon−>p o p r z ; } else {wsk−>p o p r z −> n a s t =wsk−> n a s t ; wsk−>n a s t −>p o p r z =wsk−>p o p r z ; } 33
} } e l s e / / j e s t 1 e l e m e n t w l i s´ c i e / / wsk=glowa=ogon { glowa =ogon=NULL; } d e l e t e wsk ; } } v o i d l i s t a 2 : : u s u n 2 ( e l l i s t y 2 ∗wsk ) / / wsk w s k a z u j e e l e m e n t { / / do u s u n i e˛ c i a i f ( wsk ! =NULL) { i f ( wsk== glowa ) { glowa =glowa −> n a s t ; glowa −>p o p r z =NULL ; } else { i f ( wsk== ogon ) { ogon=ogon−>p o p r z ; ogon−> n a s t =NULL ; } else {wsk−>p o p r z −> n a s t =wsk−> n a s t ; wsk−>n a s t −>p o p r z =wsk−>p o p r z ; } } d e l e t e wsk ; } } Zad. Napisz funkcj˛e sortowania listy jednokierunkowej. Zastosuj metod˛e sortowania przez proste wybieranie. Aby upros´ci´c funkcj˛e zamiany elementów zastosuj list˛e z "pusta˛ głowa". ˛
Lista jednokierunkowa z pusta˛ głowa˛ struct e l l i s t y { typ_klucza klucz ; e l l i s t y ∗ nast ; }; class lista1 { e l l i s t y ∗ glowa ; public : lista1 (); void s or to wa ni e ( ) ; ... }; lista1 :: lista1 () { glowa =new e l l i s t y ; i f ( glowa ! =NULL) glowa −> n a s t =NULL ; }
34
Przypomnienie sortowania przez proste wybieranie w wersji tablicowej. f o r ( i n t i = 0 ; i
35
poz2 −> n a s t =pom3 ; pom3−> n a s t =pom4 ; } } }
36
![Su-24 [Przeglad Konstrukcji Lotniczych 14]](https://docer.tips/img/300x300/su-24-przeglad-konstrukcji-lotniczych-14_5a95f449d64ab2a653f57e74.jpg)
