Elementy Programowania Obiektowego



Pobieranie 1,3 Mb.
Strona1/15
Data20.11.2017
Rozmiar1,3 Mb.
  1   2   3   4   5   6   7   8   9   ...   15

Politechnika Warszawska

Instytut Informatyki

Andrzej Pająk



Elementy programowania obiektowego

w języku C++


Na prawach rękopisu


Warszawa 1999
Spis Treści

1. Podstawowe pojęcia programowania obiektowego 1

1.1. Ewolucja paradygmatów programowania 2

1.2. Programowanie proceduralne 2

1.3. Programowanie strukturalne 2

1.4. Programowanie modularne i ukrywanie szczegółów 7

1.5. Abstrakcyjne typy danych 12

1.6. Programowanie obiektowe 14

1.7. Obiekty, klasy, dziedziczenie, polimorfizm 16

1.8. Perspektywy 18

2. Język C++: mechanizmy pomocnicze 20

2.1. Przeciążanie funkcji, deklaracje extern "C" 20

2.2. Prototypy funkcji 24

2.3. Parametry funkcji 25



2.3.1. Funkcje z parametrami obowiązkowymi 26

2.3.2. Funkcje ze zmienną listą parametrów 26

2.3.3. Funkcje z parametrami domniemanymi 28

2.4. Funkcje otwarte 31



2.4.1. Uwagi dodatkowe i ograniczenia 32

2.5. Typ referencyjny 32



2.5.1. Ograniczenia 35

2.6. Operatory new i delete 35

2.7. Zakresy interpretacji nazw i operator odsłaniania :: 40

2.8. Deklaracje i definicje 45

2.9. Inne rozszerzenia i uzupełnienia 47

2.9.1. Kwalifikator const 47

2.9.2. Wskazanie void* 47

2.9.3. Operator sizeof 47

2.9.4. Inicjowanie tablic znakowych 48

2.9.5. Wejście i wyjście 48

3. Klasy 50

3.1. Definiowanie klas autonomicznych: składnia 50



3.1.1. Składowe klasy 55

3.1.2. Odwołania do składowych 56

3.2. Projektowanie klas autonomicznych 56

3.3. Konstruktory i destruktory 58

3.4. Funkcje składowe 61

3.5. Operatory 65

3.6. Wskazanie this 68

3.7. Funkcje i klasy zaprzyjaźnione 69

3.8. Klasa autonomiczna Fraction 72

3.9. Składowe statyczne 75

3.10. Efekty uboczne konstruktorów i destruktorów 80

3.11. Rozszerzanie języka: klasa SET 83

3.12. Klasy ze zmienną strukturą wewnętrzną 87

3.13. Klasy zagnieżdżone 94

3.14. Listy inicjacyjne 97

3.15. Tablice dynamiczne z kontrolą indeksów 98

3.16. Szablony 99

3.17. Szablony funkcji 102

3.18. Specjalzacje klas i funkcji szablonowych 105



4. Dziedziczenie i polimorfizm 107

4.1. Klasy pochodne: składnia 107

4.2. Dostęp do składowych 111

4.3. Dziedziczenie i zawieranie 113

4.4. Wskazania i referencje 116

4.5. Funkcje wirtualne i polimorfizm 116

4.6. Funkcje wirtualne czyste i klasy abstrakcyjne 118

5. Literatura 119

6. Dodatek 120



  1. Podstawowe pojęcia programowania obiektowego

Metoda programowania obiektowego stała się modnym hasłem w ostatnich latach. Przyczyną tej mody nie jest snobizm opiniotwórczych gremiów informatyków lecz autentyczna potrzeba znalezienia skutecznej metody projektowania oprogramowania dużej skali. Problemy związane z wielkimi przedsięwzięciami programistycznymi są znane od dawna. Już w latach 70-tych mówiło się dużo o kryzysie w dziedzinie oprogramowania komputerów objawiającym się małą niezawodnością produktów, trudnościami w konserwowaniu oprogramowania, ciągle rosnącymi kosztami i nagminnym przekraczaniem przez programistów terminów kończenia projektów. Rozwinięte w tamtych latach metody programowania strukturalnego, specyfikacji projektów, testowania, konserwacji, dokumentowania technicznego, kontroli wersji itp. dały podstawę nowej dziedzinie - inżynierii oprogramowania. Podejście obiektowe jest dziedzictwem lat 80-tych i będzie również w najbliższym dziesięcioleciu dominującą koncepcją w inżynierii programowania, a także w innych dziedzinach, np. w projektowaniu systemów baz danych.


Programowanie obiektowe nie zyskałoby szybko popularności jako metoda projektowania oprogramowania gdyby nie pojawiły się języki programowania wspierające ten paradygmat. Dominującą rolę odegrał tu, i nadal będzie odgrywać, język C++ opracowany przez Bjarne Stroustrupa na początku lat 80-tych w Bell Laboratories firmy AT&T. Popularność języka C, względem którego C++ jest rozszerzeniem, i dostępność stosunkowo tanich kompilatorów zapewniły szerokie upowszechnieni nowej metodyki. Inne języki, choć koncepcyjnie bardziej nowatorskie i ambitne (np. Smalltalk, Eiffel) mają znacznie mniejszy wpływ na promocję programowania obiektowego. Istotnym zjawiskiem w ostatnich paru latach jest niewątpliwie język Java. Język ten, choć wzorowany pod wieloma względami na C++, ujmuje koncepcje programowania obiektowego w nowy sposób i "czysto". Trzeba pamiętać, że decyzja o zachowaniu zasadniczej zgodności modelu programu w języku C++ z modelem wziętym ze standardu ANSI C ma zarówno dobre jak i złe konsekwencje. Dobre skutki to stosunkowo łatwe przejście do nowego paradygmatu dla programistów biegłych w C i (wynikające z tego) szybkie upowszechnienie się metodyki obiektowej. Negatywne - to konieczność zapewnienia w języku C++ zgodności, albo przynajmniej bezkonfliktowości, nowych koncepcji i mechanizmów z dziedzictwem C. W efekcie definicja języka jest skomplikowana, zawiera liczne zakazy i wyjątki, brak w niej "ortogonalności".
Po ponad 15 letnim okresie ewolucji i 8 latach prac standaryzacyjnych C++ uzyskał ststus języka znormaliziowanego. W dniu 14 listopada 1997r zatwierdzona została norma języka: ISO/IEC FDIS 14882 (FDIS oznacza Final Draft International Standard). Norma liczy około 700 stron formatu A4 i jest jednym z bardziej złożonych standardów ISO. Prawie połowę objętości normy stanowi opis bibliotek standardowych, między innymi biblioteki rodzajowej STL (Standard Template Library). Włączenie specyfikacji biblioteki do normy języka, mimo że formalnie biorąc biblioteki do języka nie należą, jest zgodne z tradycją przejętą z normalizacji języka C. Teraz, po zatwierdzeniu standardu rozpoczyna się nowy etap w historii języka. W najbliższym czasie będą powstawać kompilatory języka C++ normatywnie zgodne ze standardem wspierając przenośność (źródłową) oprogramowania.
Niniejsze opracowanie, ze względu na ograniczoną objętość, jest pomyślane jako przewodnik po mechanizmach C++ dla programisty znającego język ANSI C. Wiele aspektów szczegółowych pominięto.
    1. Ewolucja paradygmatów programowania


Istotę metodyki programowania obiektowego najłatwiej zrozumieć porównując cechy wcześniejszych paradygmatów programowania. Ewolucja zasadniczych koncepcji wiąże się z rozważaniami dotyczącymi współzależności struktur danych i algorytmów w programach. W retrospekcji okazuje się, że intuicyjnie oczywiste rozdzielenie programów na dane (część "bierną") i operacje (część "aktywną") miało decydujący wpływ na ewolucję metod programowania. Świetna książka N. Wirtha [Wirth 80] na temat technik programowania nosi tytuł "Algorytmy + Struktury Danych = Programy" syntetyzujący ten sposób myślenia. Metodyka programowania obiektowego nie podważa poprzednich paradygmatów, przesuwa jednak ich zastosowanie do zagadnień mniejszej skali.
    1. Programowanie proceduralne


Paradygmat ten ma tradycję równie długą jak historia języków programowania wysokiego poziomu. Wszystkie języki programowania wspierają go. Paradygmat wywodzi się z operacyjnego rozumienia zachowania programow: program jako całość realizuje pewną złożoną operację; tę operację próbujemy zdefiniować przy pomocy zbioru operacji prostszych (procedur) stosując odpowiednie kryteria dekompozycji; każdą z nowych operacji, jeśli jest zbyt złożona, dekomponujemy ponownie itd. aż do uzyskania poziomu złożoności wściwej dla rozwiązywanego problemu i stosowanego języka programowania. Taka dekompozycja zstępująca dotyczy zasadniczo warstwy algorytmicznej programu. Niejako w tle tego procesu definiuje się struktury danych niezbędne dla reprezentowania stanu obliczeń i uzyskania akceptowalnej efektywności programu.
Paradygmat programowania proceduralnego ma dobrze ugruntowane podstawy teoretyczne i jest powszechnie stosowany. Znane są metody dekompozycji i odpowiednie miary złożoności strukturalnej procedur; istnieje bardzo bogata literatura dokumentująca efektywne algorytmy i struktury danych, którymi można posłużyć się bezpośrednio przy dekompozycji; znane są metody testowania i kontroli poprawności.
    1. Programowanie strukturalne


Koncepcje leżące u podstaw tego paradygmatu wywodzą się z rozważań dotyczących złożoności testowania programów i analizy poprawności algorytmów. Paradygmat dotyczy zasadniczo struktur sterowania i w uproszczonej formie bywa formułowany jako zakaz swobodnego stosowania instrukcji goto. W praktyce przyjmuje się, że etykiety i skoki nie mogą być wykorzystywane do tworzenia strukur iterowanych i wyboru - do tego celu należy korzystać z odpowiednich instrukcji cyklu for, while, repeat, do, if...then...else, case, switch, itp. Instrukcje skoku dopuszczalne są tylko w przypadkach koniecznego przejścia (np. w wyniku wykrycia błędu) z wnętrza instrukcji strukruralnych do sekwencji obsługi sytuacji wyjątkowych. Nieco inaczej sformułowana (i słabsza) reguła głosi, że w programach strukturalnych skoki jawne do etykiet "wstecz" są zakazane.
Języki programowania takie jak Pascal, C, C++, Ada zachęcają do stosowania tego paradygmatu. Zawierają one zestaw instrukcji iteracyjnych i instrukcji wyboru (szczególnym przypadkiem jest instrukcja warunkowa: wybór jednej z dwu możliwości) pozwalający projektować większość struktur sterowania bez używania skoków jawnych. Repertuar struktur sterowania języka Pascal uznawany jest za podstawowy standard zwany strukturami klasy D (na cześć E.W. Dijkstry, głównego twórcy paradygmatu). Struktury sterowania języka C (i C++) są silniejsze niż klasa D, to znaczy istnieją takie struktury sterowania, których realizacja w języku Pascal wymaga zastosowania pomocniczych zmiennych logicznych albo powielenia fragmentu kodu, natomiast w języku C mogą być wyrażone bezpośrednio. Tę dodatkową "siłę" języka C zapewniają instrukcje sterujące break (wyjście z aktualnego poziomu iteracji for, while albo do lub wyjście z instrukcji wyboru switch) oraz continue (wymuszenie następnej próby reiteracji).
Paradygmaty programowania proceduralnego i strukturalnego są łącznie podstawą metody projektowania strukturalnego (ang. Structured System Design). Typowy przykład programu skonstruowanego według zasad programowania strukturalnego podano poniżej. W programie wykorzystuje się strukturę danych zwaną stertą (ang. heap) w algorytmie porządkowania zbioru liczb. Sterta jest to drzewo binarne spełniające 2 warunki:

  1. warunek strukturalny - sterta jest drzewem lewostronnie pełnym; oznacza to, że węzły terminalne (bez potomków) mogą występować co najwyżej na dwóch ostatnich poziomach drzewa (węzłów może "brakować" tylko z prawej strony ostatniego poziomu),

  2. warunek lokalnego porządku - informacja w każdym węźle nieterminalnym jest nie mniejsza (albo nie większa) od informacji w węzłach potomnych.

Ze względu na warunek (2) rozróżniamy dwa rodzaje stert: sterty z wartością maksymalną w korzeniu (MaxHeap) i sterty z wartością minimalną w korzeniu (MinHeap).


Rys.1.1. Drzewo binarne (a); drzewo binarne lewostronne pełne (b); tablica i odpowiadająca jej struktura sterty (c).




Niech będzie dana tablica T, n elementowa, z indeksmi 1..n. W konwencjach języka C oznacza to, że tablica T nie wykorzystuje elementu T[0]. Tablicę tę możemy myślowo interpretować jako reprezentację struktury sterty (Rys. 1.1 (c)) przyjmując, że element T[1] umeszczony jest w korzeniu drzewa, elementy T[2] i T[3] w węzłach następnego poziomu, itd. Tablicy odpowiada zatem drzewo binarne lewostronnie pełne, a więc spełniające warunek strukturalny sterty. Aby doprowadzić do spełnienia również warunku porządku trzeba dokonać przemieszczeń elementów w tablicy. Na Rys. 1.1(c) zacieniono węzeł, w którym lokalny warunek porządku (dla MaxHeap) nie jest spełniony.

Zauważmy, że przy założonym zakresie indeksów tablicy przejście od węzła k do jego bezpośrednich potomków (jeśli istnieją) wymaga po prostu obliczenia wyrażeń 2k (potomek lewostronny) i 2k+1 (potomek prawostronny); podobnie, indeks k węzła różnego od korzenia drzewa pozwala wyznaczyć indeks jego bezpośredniego przodka obliczając wyrażenie k/2 (dzielenie

całkowite). Funkcja AdjustHeap() służy do przestawiania elementów tablicy tak, aby ustanowić warunek porządku w zadanym węźle nieterminalnym, jeżeli podległe mu poddrzewa są już poprawnymi stertami (węzły terminalne są poprawnym podstertami z definicji). Iteracja:

for(i=n/2; i>=1; i--) AdjustHeap(T,i,n);

ustanawia zatem warunek porządku w całej stercie.


/* Sortowanie z wykorzystaniem sterty (HEAPSRT.C).

// ==============================================

// Sterta: drzewo binarne lewostronnie pełne, tzn. w drzewie k-poziomowym

// może brakować węzłów tylko na poziomie k z prawej strony drzewa.

// Sterta może być reprezentowana bez jawnego używania wskaźników przy

// pomocy tablicy elementów z indeksami 1..N. Jezeli element T[i] jest

// węzłem sterty, to związane z nim węzły potomne (jeśli istnieją) mają

// indeksy 2*i (lewy potomek) oraz 2*i+1 (prawy potomek). Korzeń drzewa

// odpowiada elementowi T[1].

//

// Oprócz powyższego warunku strukturalnego sterta spełnia warunek porządku:

// T[i]>=T[2*i] && T[i]>=T[2*i+1] ==> MaxHeap albo

// T[i]<=T[2*i] && T[i]<=T[2*i+1] ==> MinHeap

// (węzły potomne, jeśli istnieją, nie większe albo nie mniejsze od "ojca").

// W programie wykorzystujemy wersję MaxHeap.

*/

#include

#include /* int rand(void); generator liczb losowych */

#define MAXSIZE 1000 /* Maksymalna liczba elementów do sortowania */

typedef int ELEMENT; /* Przykładowy typ elementów sterty */

void AdjustHeap(ELEMENT *T, int k, int n);
void HeapSort(ELEMENT T[], int n)

{ int i;

ELEMENT e;

/* Tworzenie sterty w tablicy T[1..n]; element T[0] niewykorzystany */

for(i=n/2; i>=1; i--) AdjustHeap(T,i,n);

/* Sortowanie */

for(i=n; i>=2; i--)

{ /* Sterta i-elementowa; na szczycie element maksymalny */

e = T[i]; T[i] = T[1]; T[1] = e; /* Element max. na koniec sterty */

AdjustHeap(T,1,i-1); /* Przywróć stertę po przestawieniu */

}

}

void AdjustHeap(ELEMENT T[], int k, int n)

// Zakładając, że poddrzewa z korzeniami 2*k oraz 2*k+1 są prawidłowymi

// stertami, ustanowić prawidłową stertę z korzeniem k.

*/

{ int j=2*k; /* j = indeks lewego potomka węzła k */

ELEMENT e = T[k];

while(j<=n)

{ if(j

if( e > T[j]) break; /* Sterta z korzeniem k OK */

T[k] = T[j]; /* Zejście do następnego poziomu */

k = j;

j = 2*k;

}

T[k] = e;

}

/*==========*/

int main(void) /* Testowanie HeapSort */

{ ELEMENT T[MAXSIZE +1]; /* Element T[0] niewykorzystywany */

int i,n;
while(1)

{ printf("Liczba elementow generowanych losowo (<=%-d): n=",MAXSIZE);

scanf("%d",&n);

if(n<=0) break; /* Koniec testu */
for(i=1; i<=n; i++) T[i] = rand();
/* Wydruk tablicy do sortowania */

printf("Tablica przed sortowaniem\n\n");

for(i=1; i<=n; i++) printf("%5d%c",T[i],(i%10)?' ':'\n');

putchar('\n');
HeapSort(T,n);
/* Wydruk tablicy po sortowaniu */

printf("Tablica uporzadkowana\n\n");

for(i=1; i<=n; i++) printf("%5d%c",T[i],(i%10)?' ':'\n');

putchar('\n');

}

return 0;

}
Przykład wykonania:
Liczba elementow generowanych losowo (<=1000): n=20

Tablica przed sortowaniem
346 130 10982 1090 11656 7117 17595 6415 22948 31126

9004 14558 3571 22879 18492 1360 5412 26721 22463 25047
Tablica uporzadkowana
130 346 1090 1360 3571 5412 6415 7117 9004 10982

11656 14558 17595 18492 22463 22879 22948 25047 26721 31126
Liczba elementow generowanych losowo (<=1000): n=0
Uwaga 1: Ortodoksyjni zwolennicy ANSI-C nie muszą rezygnować ze standardowego zakresu indeksów tablic w algorytmie HeapSort(); jeżeli indeks należy do przedziału 0..n-1, to wystarczy zmienić wyrażenia wyznaczające bezpośrednich potomków i bezpośredniego przodka węzła k na odpowednio: 2k+1, 2(k+1); (k-1)/2.
Uwaga 2: Złożoność obliczeniowa algorytmu HeapSort() jest O(nlog(n)), a więc asymptotycznie jest to algorytm optymalny. Wadą algorytmu jest to, że czas porządkowania tablicy już uporządkowanej jest także proporcjonalny do nlog(n); istnieją metody szybsze, wrażliwe na stopień początkowego uporządkowania tablicy (np. metoda QuickSort, która jednak ma złożoność proporcjonalną do n2 w najgorszym przypadku).



  1   2   3   4   5   6   7   8   9   ...   15


©operacji.org 2017
wyślij wiadomość

    Strona główna