Darmowy fragment publikacji:
IDZ DO
IDZ DO
PRZYK£ADOWY ROZDZIA£
PRZYK£ADOWY ROZDZIA£
SPIS TREĎCI
SPIS TREĎCI
KATALOG KSI¥¯EK
KATALOG KSI¥¯EK
KATALOG ONLINE
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
TWÓJ KOSZYK
DODAJ DO KOSZYKA
DODAJ DO KOSZYKA
CENNIK I INFORMACJE
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
ZAMÓW INFORMACJE
O NOWOĎCIACH
O NOWOĎCIACH
ZAMÓW CENNIK
ZAMÓW CENNIK
CZYTELNIA
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
FRAGMENTY KSI¥¯EK ONLINE
C++. Algorytmy
i struktury danych
Autor: Adam Drozdek
T³umaczenie: Piotr Rajca, Tomasz ¯mijewski
ISBN: 83-7361-385-4
Tytu³ orygina³u: Data Structures and Algorithms
in C++, Second Edition
Format: B5, stron: 616
Badanie struktur danych, elementarnych sk³adników wykorzystywanych w informatyce,
jest podstaw¹, w oparciu o któr¹ mo¿esz zdobywaæ cenne umiejêtnoġci. Znajomoġæ
struktur danych jest niezbêdna studentom, którzy chc¹ programowaæ czy te¿ testowaæ
oprogramowanie.
W niniejszej ksi¹¿ce zwrócono uwagê na trzy wa¿ne aspekty struktur danych: po
pierwsze, na zwi¹zek struktur danych z algorytmami, miêdzy innymi na z³o¿onoġæ
obliczeniow¹ algorytmów. Po drugie, struktury te prezentowane s¹ w sposób zgodny
z zasadami projektowania obiektowego i obiektowym paradygmatem programowania.
Po trzecie, wa¿n¹ czêġci¹ ksi¹¿ki s¹ implementacje struktur danych w jêzyku C++.
Ksi¹¿ka prezentuje:
• Podstawy projektowania obiektowego w C++
• Analizê z³o¿onoġci
• Listy powi¹zane
• Stosy i kolejki
• Rekurencjê
• Drzewa binarne
• Sterty
• Drzewa wielokrotne
• Grafy
• Sortowanie i mieszanie
• Kompresja danych
• Zarz¹dzanie pamiêci¹
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Ksi¹¿ka ta dostarcza studentom informatyki nie tylko niezbêdnej wiedzy na temat
algorytmów i struktur danych, ale prezentuje jednoczeġnie sposoby ich implementacji
w jêzyku C++, obecnie jednym z wiod¹cych jêzyków programowania. Dostarcza ona
wiêc nie tylko wiedzy teoretycznej, ale równie¿ pozwala rozwin¹æ praktyczne
umiejêtnoġci przydatnych w przysz³ej pracy zawodowej.
Spis treści
Wstęp ...................................................o...................................................o...............11
1.
Programowanie obiektowe w C++ ...................................................o.....................15
1.1. Abstrakcyjne typy danych ...................................................c.................................................................... 15
1.2. Enkapsulacja ...................................................c...................................................c...................................... 15
1.3. Dziedziczenie...................................................c...................................................c..................................... 19
1.4. Wskaźniki ...................................................c...................................................c.......................................... 22
1.4.1. Wskaźniki a tablice ...................................................c................................................................... 24
1.4.2. Wskaźniki a konstruktory kopiujące...................................................c......................................... 26
1.4.3. Wskaźniki i destruktory ...................................................c............................................................ 29
1.4.4. Wskaźniki a referencje...................................................c.............................................................. 29
1.4.5. Wskaźniki na funkcje...................................................c................................................................ 32
1.5. Polimorfizm ...................................................c...................................................c....................................... 33
1.6. C++ a programowanie obiektowe...................................................c......................................................... 35
1.7. Standardowa biblioteka szablonów ...................................................c...................................................... 36
1.7.1. Kontenery...................................................c...................................................c............................... 36
1.7.2. Iteratory...................................................c...................................................c.................................. 37
1.7.3. Algorytmy...................................................c...................................................c.............................. 37
1.7.4. Funktory...................................................c...................................................c................................. 38
1.8. Wektory w standardowej bibliotece szablonów ...................................................c................................... 40
1.9. Struktury danych a programowanie obiektowe ...................................................c.................................... 46
1.10. Przykład zastosowania: plik z dostępem swobodnym...................................................c.......................... 47
1.11. Ćwiczenia ...................................................c...................................................c.......................................... 56
1.12. Zadania programistyczne...................................................c...................................................................... 58
Bibliografia ...................................................c...................................................c....................................... 60
2.
Analiza złożoności ...................................................o..............................................61
2.1. Złożoność obliczeniowa i asymptotyczna ...................................................c............................................ 61
2.2. O-notacja...................................................c...................................................c............................................ 62
2.3. Właściwości O-notacji...................................................c...................................................c....................... 64
6
SPIS TREŚCI
2.4. Notacje Ω i Θ...................................................c...................................................c..................................... 66
2.5. Możliwe problemy...................................................c...................................................c............................. 67
2.6. Przykłady złożoności ...................................................c...................................................c......................... 67
2.7. Określanie złożoności asymptotycznej. Przykłady...................................................c............................... 68
2.8. Złożoność optymistyczna, średnia i pesymistyczna ...................................................c............................. 71
2.9. Złożoność zamortyzowana ...................................................c................................................................... 73
2.10. Ćwiczenia ...................................................c...................................................c.......................................... 77
Bibliografia ...................................................c...................................................c....................................... 80
3.
Listy ...................................................o...................................................o.................81
3.1. Listy jednokierunkowe ...................................................c...................................................c...................... 81
3.1.1. Wstawianie...................................................c...................................................c............................. 86
3.1.2. Usuwanie ...................................................c...................................................c............................... 88
3.1.3. Wyszukiwanie...................................................c...................................................c........................ 93
3.2. Listy dwukierunkowe ...................................................c...................................................c........................ 93
3.3. Listy cykliczne...................................................c...................................................c................................... 97
3.4. Listy z przeskokami...................................................c...................................................c........................... 99
3.5. Listy samoorganizujące się...................................................c................................................................. 104
3.6. Tablice rzadkie...................................................c...................................................c................................. 107
3.7. Listy w bibliotece STL ...................................................c....................................................................... 110
3.8. Kolejki dwustronne w bibliotece STL...................................................c................................................ 113
3.9. Podsumowanie...................................................c...................................................c................................. 117
3.10. Przykład zastosowania. Biblioteka ...................................................c..................................................... 118
3.11. Ćwiczenia ...................................................c...................................................c........................................ 126
3.12. Zadania programistyczne...................................................c.................................................................... 128
Bibliografia ...................................................c...................................................c..................................... 131
4.
Stosy i kolejki ...................................................o...................................................o133
4.1. Stosy ...................................................c...................................................c................................................ 133
4.2. Kolejki ...................................................c...................................................c............................................. 140
4.3. Kolejki priorytetowe...................................................c...................................................c........................ 147
4.4. Stosy w bibliotece STL...................................................c....................................................................... 148
4.5. Kolejki w bibliotece STL...................................................c.................................................................... 148
4.6. Kolejki priorytetowe w bibliotece STL ...................................................c.............................................. 149
4.7. Przykład zastosowania. Szukanie wyjścia z labiryntu...................................................c........................ 152
4.8. Ćwiczenia ...................................................c...................................................c........................................ 156
4.9. Zadania programistyczne...................................................c.................................................................... 159
Bibliografia ...................................................c...................................................c..................................... 160
5.
Rekurencja ...................................................o...................................................o.....161
5.1. Definicje rekurencyjne...................................................c........................................................................ 161
5.2. Wywołania funkcji a implementacja rekurencji ...................................................c................................. 164
5.3. Anatomia wywołania rekurencyjnego ...................................................c................................................ 165
5.4. Rekurencja ogonowa ...................................................c...................................................c....................... 169
5.5. Rekurencja inna niż ogonowa...................................................c............................................................. 170
SPIS TREŚCI
7
5.6. Rekurencja pośrednia...................................................c...................................................c....................... 174
5.7. Rekurencja zagnieżdżona ...................................................c................................................................... 176
5.8. Nadużywanie rekurencji ...................................................c..................................................................... 177
5.9. Algorytmy z powrotami...................................................c...................................................c................... 180
5.10. Wnioski końcowe ...................................................c...................................................c............................ 186
5.11. Przykład zastosowania. Rekurencyjny interpreter...................................................c.............................. 187
5.12. Ćwiczenia ...................................................c...................................................c........................................ 194
5.13. Zadania programistyczne...................................................c.................................................................... 197
Bibliografia ...................................................c...................................................c..................................... 199
6.
Drzewa binarne ...................................................o.................................................201
6.1. Drzewa, drzewa binarne i binarne drzewa poszukiwania...................................................c................... 201
6.2. Implementacja drzew binarnych...................................................c......................................................... 205
6.3. Wyszukiwanie w drzewie binarnym...................................................c................................................... 207
6.4. Przechodzenie po drzewie ...................................................c.................................................................. 210
6.4.1. Przechodzenie wszerz ...................................................c............................................................. 210
6.4.2. Przechodzenie w głąb ...................................................c............................................................. 211
6.4.3. Przechodzenie po drzewie w głąb bez stosu ...................................................c........................... 217
6.5. Wstawianie ...................................................c...................................................c...................................... 223
6.6. Usuwanie ...................................................c...................................................c......................................... 225
6.6.1. Usuwanie przez złączanie ...................................................c....................................................... 226
6.6.2. Usuwanie przez kopiowanie ...................................................c................................................... 229
6.7. Równoważenie drzewa ...................................................c...................................................c.................... 231
6.7.1. Algorytm DSW ...................................................c...................................................c.................... 234
6.7.2. Drzewa AVL...................................................c...................................................c........................ 236
6.8. Drzewa samoorganizujące się...................................................c............................................................. 241
6.8.1. Drzewa samonaprawiające się ...................................................c................................................ 241
6.8.2. Ukosowanie ...................................................c...................................................c......................... 243
6.9. Sterty...................................................c...................................................c................................................ 247
6.9.1. Sterty jako kolejki priorytetowe.................c...................................................c............................. 249
6.9.2. Organizowanie tablic w sterty ...................................................c................................................ 251
6.10. Notacja polska i drzewa wyrażeń ...................................................c....................................................... 255
6.10.1. Operacje na drzewach wyrażeń ...................................................c.............................................. 256
6.11. Przykład zastosowania. Zliczanie częstości występowania słów ...................................................c....... 259
6.12. Ćwiczenia ...................................................c...................................................c........................................ 265
6.13. Zadania programistyczne...................................................c.................................................................... 268
Bibliografia ...................................................c...................................................c..................................... 272
7.
Drzewa wielokierunkowe ...................................................o.................................275
7.1. Rodzina B-drzew ...................................................c...................................................c............................. 276
7.1.1. B-drzewa...................................................c...................................................c.............................. 277
7.1.2. B*-drzewa...................................................c...................................................c............................ 286
7.1.3. B+-drzewa...................................................c...................................................c............................ 288
7.1.4. B+-drzewa przedrostkowe ...................................................c...................................................... 289
7.1.5. Drzewa bitowe ...................................................c...................................................c..................... 291
7.1.6. R-drzewa...................................................c...................................................c.............................. 294
7.1.7. 2-4-drzewa ...................................................c...................................................c........................... 296
7.1.8. Zbiory i wielozbiory w bibliotece STL...................................................c................................... 303
7.1.9. Mapy i multimapy w bibliotece STL...................................................c...................................... 309
8
SPIS TREŚCI
7.2. Drzewa słownikowe...................................................c...................................................c......................... 313
7.3. Uwagi końcowe ...................................................c...................................................c............................... 321
7.4. Przykład zastosowania. Sprawdzanie pisowni ...................................................c................................... 321
7.5. Ćwiczenia ...................................................c...................................................c........................................ 330
7.6. Zadania programistyczne...................................................c.................................................................... 331
Bibliografia ...................................................c...................................................c..................................... 334
8.
Grafy ...................................................o...................................................o..............337
8.1. Reprezentacje grafów...................................................c...................................................c....................... 338
8.2. Przechodzenie po grafach...................................................c.................................................................... 340
8.3. Najkrótsza droga ...................................................c...................................................c.............................. 344
8.3.1. Problem najkrótszych dróg typu „wszystkie-do-wszystkich” ...................................................c 351
8.4. Wykrywanie cykli ...................................................c...................................................c............................ 353
8.4.1. Problem znajdowania sumy zbiorów rozłącznych...................................................c.................. 354
8.5. Drzewa rozpinające ...................................................c...................................................c.......................... 356
8.5.1. Algorytm Borůvki...................................................c...................................................c................ 357
8.5.2. Algorytm Kruskala ...................................................c...................................................c.............. 358
8.5.3. Algorytm Jarníka-Prima ...................................................c......................................................... 360
8.5.4. Metoda Dijkstry ...................................................c...................................................c................... 361
8.6. Spójność ...................................................c...................................................c........................................... 361
8.6.1. Spójność w grafach nieskierowanych...................................................c..................................... 361
8.6.2. Spójność w grafach skierowanych...................................................c.......................................... 364
8.7. Sortowanie topologiczne ...................................................c..................................................................... 365
8.8. Sieci...................................................c...................................................c.................................................. 368
8.8.1. Przepływy maksymalne ...................................................c.......................................................... 368
8.8.2. Maksymalne przepływy o minimalnym koszcie..................................................c...................... 378
8.9. Kojarzenie ...................................................c...................................................c........................................ 383
8.9.1. Problem przypisania............................c...................................................c.................................... 387
8.9.2. Skojarzenia w grafach, które nie są dwudzielne...................................................c..................... 390
8.10. Grafy eulerowskie i hamiltonowskie..................c...................................................c................................. 392
8.10.1. Grafy eulerowskie...................................................c...................................................c................ 392
8.10.2. Grafy hamiltonowskie............................c...................................................c................................. 393
8.11. Przykład zastosowania. Unikalni reprezentanci...................................................c.................................. 396
8.12. Ćwiczenia...................................................c...................................................c......................................... 406
8.13. Zadania programistyczne ...................................................c.................................................................... 409
Bibliografia ...................................................c...................................................c..................................... 411
9.
Sortowanie ...................................................o...................................................o.....413
9.1. Podstawowe algorytmy sortowania ...................................................c.................................................... 414
9.1.1. Sortowanie przez wstawianie...................................................c.................................................. 414
9.1.2. Sortowanie przez wybieranie...................................................c.................................................. 417
9.1.3. Sortowanie bąbelkowe...................................................c............................................................ 419
9.2. Drzewa decyzyjne...................................................c...................................................c............................ 422
9.3. Efektywne algorytmy sortowania ...................................................c....................................................... 425
9.3.1. Sortowanie Shella ...................................................c...................................................c................ 425
9.3.2. Sortowanie przez kopcowanie ...................................................c................................................ 429
9.3.3. Sortowanie szybkie (quicksort)...................c...................................................c............................ 433
9.3.4. Sortowanie poprzez scalanie...................................................c................................................... 440
9.3.5. Sortowanie pozycyjne...................................................c............................................................. 443
SPIS TREŚCI
9
9.4. Sortowanie przy wykorzystaniu STL ...................................................c................................................. 448
9.5. Uwagi końcowe ...................................................c...................................................c............................... 452
9.6. Przykład zastosowania. Dodawanie wielomianów...................................................c............................. 452
9.7. Ćwiczenia ...................................................c...................................................c........................................ 459
9.8. Zadania programistyczne...................................................c.................................................................... 461
Bibliografia ...................................................c...................................................c..................................... 463
10.
Mieszanie ...................................................o...................................................o.......465
10.1. Funkcje mieszające...................................................c...................................................c.......................... 466
10.1.1. Dzielenie ...................................................c...................................................c.............................. 466
10.1.2. Składanie...................................................c...................................................c.............................. 466
10.1.3. Funkcja „środek kwadratu” ...................................................c.................................................... 467
10.1.4. Wycinanie ...................................................c...................................................c............................ 468
10.1.5. Zmiana podstawy...................................................c...................................................c................. 468
10.2. Rozwiązywanie problemu kolizji ...................................................c....................................................... 468
10.2.1. Adresowanie otwarte ...................................................c.............................................................. 469
10.2.2. Metoda łańcuchowa ...................................................c...................................................c............. 475
10.2.3. Adresowanie kubełkowe...................................................c......................................................... 476
10.3. Usuwanie ...................................................c...................................................c......................................... 477
10.4. Doskonałe funkcje mieszające...................................................c............................................................ 479
10.4.1. Metoda Cichelliego...................................................c................................................................. 479
10.4.2. Algorytm FHCD ...................................................c...................................................c.................. 482
10.5. Funkcje mieszające dla plików rozszerzalnych...................................................c.................................. 484
10.5.1. Mieszanie przedłużalne........................c...................................................c................................... 485
10.5.2. Mieszanie liniowe...................................................c...................................................c................ 487
10.6. Przykład zastosowania. Mieszanie z użyciem kubełków ...................................................c................... 490
10.7. Ćwiczenia ...................................................c...................................................c........................................ 498
10.8. Zadania programistyczne...................................................c.................................................................... 500
Bibliografia ...................................................c...................................................c..................................... 501
11.
Kompresja danych ...................................................o............................................503
11.1. Warunki kompresji danych...................................................c................................................................. 503
11.2. Kodowanie Huffmana...................................................c...................................................c...................... 505
11.2.1. Adaptacyjne kodowanie Huffmana ...................................................c........................................ 514
11.3. Metoda Shannona-Fano ...................................................c...................................................c................... 519
11.4. Kodowanie długości serii ...................................................c................................................................... 520
11.5. Metoda Ziva-Lempela ...................................................c...................................................c..................... 521
11.6. Przykład zastosowania. Metoda Huffmana z kodowaniem długości serii ............................................ 524
11.7. Ćwiczenia ...................................................c...................................................c........................................ 535
11.8. Zadania programistyczne...................................................c.................................................................... 536
Bibliografia ...................................................c...................................................c..................................... 537
12.
Zarządzanie pamięcią ...................................................o.......................................539
12.1. Metody dopasowywania sekwencyjnego ...................................................c........................................... 540
12.2. Metody niesekwencyjne ...................................................c..................................................................... 542
12.2.1. System bliźniaków...................................................c...................................................c............... 543
10
SPIS TREŚCI
12.3. Odśmiecanie ...................................................c...................................................c.................................... 551
12.3.1. Metoda „zaznacz-i-zamiataj”...................................................c.................................................. 551
12.3.2. Metody kopiowania ...................................................c...................................................c............. 559
12.3.3. Krokowe metody odśmiecania.......................c...................................................c......................... 560
12.4. Uwagi końcowe ...................................................c...................................................c............................... 567
12.5. Przykład zastosowania. Odśmiecanie „w miejscu” ...................................................c............................ 568
12.6. Ćwiczenia ...................................................c...................................................c........................................ 576
12.7. Zadania programistyczne...................................................c.................................................................... 577
Bibliografia ...................................................c...................................................c..................................... 579
A
Obliczanie złożoności ...................................................o.......................................583
A.1. Szereg harmoniczny...................................................c...................................................c......................... 583
A.2. Przybliżenie funkcji lg(n!)...................................................c.................................................................. 583
A.3. Przybliżona średnia złożoność sortowania szybkiego...................................................c........................ 585
A.4. Średnia długość ścieżki w losowych drzewach binarnych ...................................................c................. 587
B
Algorytmy dostępne w STL...................................................o..............................589
B.1. Algorytmy standardowe...................................................c...................................................c................... 589
Skorowidz ...................................................o...................................................o......597
1
Programowanie obiektowe w C++
1.1. Abstrakcyjne typy danych
Przed napisaniem jakiegokolwiek programu trzeba wiedzieć dość dokładnie, jak powinno być re-
alizowane zadanie wykonywane przez ten program. Wobec tego przed początkiem kodowania
powinien powstać szkic programu opisujący wszystkie wymagania. Im większy i bardziej złożony
jest projekt, tym bardziej szczegółowy powinien być ten szkic. Szczegóły implementacyjne po-
winny zostać odłożone do późniejszego etapu prac. W szczególności na później powinny zostać
odłożone wszelkie szczegółowe ustalenia dotyczące stiruktur danych nieokreślone na samym początku.
Od samego początku trzeba określić każde zadanie za pomocą jego danych wejściowych
i wyjściowych. Na wstępie bardziej powinno nas interesować to, co program ma robić, a nie jak
ma to robić. Zachowanie się programu jest ważniejsze od tego, dlaczego program tak właśnie
działa. Jeśli, na przykład, realizacja pewnego zadania wymaga jakiegoś narzędzia, narzędzie to
opisuje się jako zestaw możliwych operacji, a nie podaje się jego wewnętrznej struktury. Operacje
takie mogą modyfikować narzędzie, wyszukiwać dotyczące go szczegóły lub zapisywać w nim
dodatkowe dane. Kiedy wszystkie te operacje zostaną dokładnie opisane, można rozpocząć kodo-
wanie. Na tym etapie decyduje się o tym, które struktury danych będą najlepsze z punktu widzenia
czasu wykonania i zajętości pamięci. Takie narzędzie opisane przez jego operacje nazywamy abs-
trakcyjnym typem danych. Abstrakcyjny typ danych nie jest częścią programu, gdyż program napi-
sany w pewnym języku programowania wymaga zdefiniowania struktury danych, a nie tylko ope-
racji na tej strukturze. Jednak języki obiektowe, takie jak C++, bezpośrednio wiążą abstrakcyjne
typy danych z kodem w formie klas.
1.2. Enkapsulacja
Programowanie obiektowe obraca się wokół pojęcia obiektu. Obiekty tworzone są zgodnie z defi-
nicją klasy. Klasa to szablon, według którego tworzy się obiekty. Klasa to fragment kodu, który
zawiera opis danych oraz funkcje przetwarzające te dane i, ewentualnie, także dane z innych klas.
Funkcje definiowane w ramach klasy nazywamy metodami lub funkcjami składowymi, zaś zmienne
używane w klasach to dane składowe lub po prostu pola. Takie łączenie danych i związanych
z nimi operacji nazywamy enkapsulacją danych. Obiekt to instancja klasy — coś, co jest tworzone
zgodnie z definicją tej klasy.
16
1. PROGRAMOWANIE OBIEKTOWE W C++
W przeciwieństwie do funkcji z języków nieobiektowych, w obiektach połączenie między
danymi a metodami jest ścisłe i ma istotne znaczenie. W językach nieobiektowych deklaracje da-
nych i definicje funkcji mogą przeplatać się w całym programie, a jedynie z dokumentacji wynika,
jak dane z funkcjami są powiązane. W językach obiektowych związek ten jest ustalany już na
wstępie; cała struktura programu opiera się na tym powiązaniu. Obiekt jest opisany przez powią-
zane dane i operacje, a jako że w tym samym programie używanych może być wiele obiektów,
obiekty komunikują się, wymieniając komunikaty, którie o ich strukturze wewnętrznej mówią tylko
tyle, ile jest niezbędne. Podział programu na obiekity pozwala osiągnąć kilka celów.
Po pierwsze, silnie powiązane dane i operacje mogą znacznie lepiej opisywać modelowany
fragment świata, co jest szczególnie istotne w przypadku inżynierii oprogramowania. Nie powinno
zaskakiwać, że programowanie obiektowe ma swoje korzenie w symulacjach, czyli modelowaniu
rzeczywistych obiektów. Pierwszym językiem obiektowym była Simula, która powstała w latach
60-tych w Norwegii.
Po drugie, użycie obiektów ułatwia szukanie błędów, gdyż operacje są wiązane od razu ze
„swoimi” obiektami. Nawet jeśli pojawiają się efekty uiboczne, łatwiej jest je wyśledzić.
Po trzecie, użycie obiektów pozwala ukryć pewne szczegóły operacji przed innymi obiekta-
mi, dzięki czemu operacje te nie ulegają tak łatwo zmianom w przypadku zmieniania innych
obiektów. Jest to zasada ukrywania informacji. W językach nieobiektowych zasada ta w pewnym
zakresie jest realizowana przez stosowanie zmiennych lokalnych, a (na przykład w Pascalu) także
przez stosowanie lokalnych funkcji i procedur, które są dostępne jedynie w funkcjach je zawiera-
jących. Jednak jest to zawsze albo bardzo dokładne ukrywanie, albo ukrywania nie ma w ogóle.
Czasami (na przykład w Pascalu) funkcja f2 zdefiniowana w f1 może być potrzebna poza f1, ale
poza f1 jest ona całkowicie niewidoczna. Czasami potrzebne jest sięgnięcie do pewnych danych
lokalnych f1 bez dokładnej znajomości struktury tych danych, ale to też jest niemożliwe. Dlatego
też w programowaniu obiektowym nieco zmieniają się ziasady dostępności danych.
Użytkowników interesuje działanie zegarka, ale jego budowa wewnętrzna nie ma już znacze-
nia. Wiadomo, że wewnątrz są tryby i sprężyny, ale zwykle niewiele wiadomo o sposobie ich
działania, wobec czego dostęp do nich jest zbędny, gdyż mógłby prowadzić do uszkodzenia me-
chanizmu. Mechanizm jest przed użytkownikiem ukryty, nie ma do niego bezpośredniego dostępu,
dzięki czemu zegarek nie jest narażony na zniszczenie bardziej, niż gdyby mechanizm był cały
czas otwarty.
Obiekt to czarna skrzynka o dokładnie opisanym działaniu; obiektu używa się dlatego, że
wiadomo, co on robi, ale nie ma się dostępu do jego wnętrza. Owa nieprzezroczystość obiektów jest
wyjątkowo przydatna do serwisowania jednych obiektów niezależnie od innych. Jeśli dobrze zo-
staną określone kanały komunikacyjne między obiektami, zmiany w jednym obiekcie będą wpły-
wały na inne obiekty tylko wtedy, gdy będą dotyczyły tych kanałów. Wiedząc, jakie informacje są
wysyłane i odbierane przez obiekt, można łatwiej zastąpić jeden obiekt innym — nowy obiekt mo-
że realizować te same zadania inaczej, na przykład szybciej w danym środowisku. Obiekt ujawnia
tylko tyle informacji o sobie, ile jest potrzebnych użytkownikowi, aby tego obiektu użyć. Obiekt
ma część publiczną, która jest dostępna dla wszystkich, którzy prześlą do obiektu komunikat
w formie jednej z funkcji przez obiekt udostępnianych. Do części publicznej należą przyciski po-
kazywane użytkownikowi; wciśnięcie każdego z tych przycisków powoduje wykonanie operacji
obiektu. Użytkownik zna jedynie nazwy operacji i wiei, co te operacje robią.
Ukrywanie informacji prowadzi do zacierania się rozgraniczenia między danymi a operacjami.
W językach programowania takich jak Pascal podział na dane i funkcje jest prosty i stały. Inaczej
definiuje się jedne i drugie, inne jest ich zastosowanie. W programowaniu obiektowym dane
i metody są zestawione razem, zaś dla użytkownika obiektu podział jest znacznie mniej wyraźny.
1.2. ENKAPSULACJA
17
W pewnym zakresie jest to też cecha języków funkcyjnych. LISP, jeden z najstarszych języków
programowania, pozwala traktować dane i funkcje tak samo, gdyż struktura jednych i drugich jest
identyczna.
Dokonaliśmy już podziału między konkretne obiekty a typy obiektów czyli klasy. Funkcje pi-
szemy tak, aby używały różnych zmiennych, nie chcemy jeidnak być zmuszani do zapisywania tylu
deklaracji obiektów, ilu obiektów potrzebujemy w całym programie. Pewne obiekty są tego samego
typu i chcielibyśmy używać pojedynczego typu jako ogólnej definicji takiego typu. W przypadku
pojedynczych zmiennych odróżniamy deklarację typu od deklaracji zmiennej. W przypadku
obiektów mamy deklarację klasy i deklarację obiektu. Poniżej pokazano przykład klasy i obiek-
tów QDLGEV, QDLGEV i QDLGEV:
ENCUU ]
RWDNKE
EJCT U KPVK FQWDNGF ]
UVTER[
FCVC/GODGTU
FCVC/GODGT K
FCVC/GODGT F
_
XQKFOGODGT(WPEVKQP
]
EQWV FCVC/GODGT FCVC/GODGT
FCVC/GODGT GPFN
_
XQKFOGODGT(WPEVKQP
KPVKEJCT U PKG\PCPC ]
FCVC/GODGT K
EQWV K RQDTCPC\ U GPFN
_
RTQVGEVGF
EJCTFCVC/GODGT=?
KPVFCVC/GODGT
FQWDNGFCVC/GODGT
_
QDLGEV
QDKGMV QDLGEV
QDKGMV QDLGEV
Przekazywanie komunikatów jest odpowiednikiem wywoływania funkcji w tradycyjnych ję-
zykach programowania, jednak ważne jest, że w przypadku programowania obiektowego metody
są powiązane z obiektami — stąd właśnie używany jest nowy termin. Przykładowo, wywołanie
publicznej metody OGODGT(WPEVKQP
obiektu QDLGEV:
QDLGEVOGODGT(WPEVKQP
jest widziane jako wysłanie do obiektu QDLGEV komunikatu OGODGT(WPEVKQP
. Po otrzymaniu
takiego komunikatu obiekt wywołuje swoją metodę i wyświetla wszystkie odpowiednie w danej
sytuacji informacje. Komunikaty mogą zawierać parameitry:
QDLGEVOGODGT(WPEVKQP
Powyższy zapis to wywołanie komunikatu OGODGT(WPEVKQP
obiektu QDLGEV z parametrem .
18
1. PROGRAMOWANIE OBIEKTOWE W C++
Wiersze zawierające takie komunikaty mogą być umieszczone albo w głównym programie,
albo w funkcji, albo w metodzie innego obiektu. Wobec tego odbiorca komunikatu może zostać
zidentyfikowany, ale nie dotyczy to wywołującego. Jeśli QDLGEV otrzyma komunikat OGODGT(WPE
VKQP
, nie wie, skąd ten komunikat pochodzi. Odpowiada na komunikat, pokazując dane za-
kodowane w metodzie OGODGT(WPEVKQP
, to samo dotyczy metody OGODGT(WPEVKQP
. Wobec
tego nadawca komunikatu może do komunikatu dołączyć informacje umożliwiające jego zi-
dentyfikowanie:
QDLGEVOGODGT(WPEVKQP
QDKGMV
Istotną cechą C++ jest możliwość deklarowania ogólnych klas dzięki użyciu parametrów typu
w deklaracji klasy. Jeśli, na przykład, trzeba zadeklarować klasę, która będzie coś przechowywała
w tablicy, można zadeklarować ją następująco:
ENCUUKPV NCUU]
KPVUVQTCIG=?
_
jednak w ten sposób ogranicza się przydatność takiej klasy jedynie do liczb całkowitych; jeśli po-
trzebna będzie analogiczna klasa z liczbami zmiennoprzecinkowymi, konieczna będzie nowa de-
klaracja:
ENCUUHNQCV NCUU]
HNQCVUVQTCIG=?
_
Jeśli UVQTCIG ma zawierać struktury lub wskaźniki do znaków, konieczne byłoby zadeklaro-
wanie kolejnych dwóch klas. Znacznie lepiej byłoby zadeklarować ogólną klasę i dopiero podczas
definiowania obiektów decydować, jakiego typu dane będą w obiekcie przechowywane. Język
C++ umożliwia takie deklarowanie klasy, na przykład:
VGORNCVG ENCUUIGP6[RG
ENCUUIGP NCUU]
IGP6[RGUVQTCIG=?
_
Dopiero potem decydujemy, jak inicjalizowany będzie ityp IGP6[RG:
IGP NCUU KPV KPV1DLGEV
IGP NCUU HNQCV HNQCV1DLGEV
Taka klasa ogólna przybiera różne postacie w zależności od konkretnej deklaracji. Jedna
ogólna deklaracja może udostępnić wszystkie te postaciie.
Możemy pójść jeszcze dalej i decyzję o wielkości bufora, obecnie 50 komórek, odłożyć na
później, do czasu tworzenia obiektu. Jednak na wszelki wypadek możemy też zostawić wartość
domyślną:
1.3. DZIEDZICZENIE
19
VGORNCVG ENCUUIGP6[RGKPVUK\G
ENCUUIGP NCUU]
IGP6[RGUVQTCIG=UK\G?
_
Definicje obiektów będą teraz wyglądały następująco:
IGP NCUU KPV KPV1DLGEV Wľ[V[\QUVCPKGTQ\OKCTFQO[ħNP[
IGP NCUU KPV KPV1DLGEV
IGP NCUU HNQCV HNQCV1DLGEV
Pokazana metoda używania typów ogólnych nie ogranicza się jedynie do klas; można używać
jej też w deklaracjach funkcji. Przykładowo, standardowa operacja zamiany miejscami dwóch
wartości może być zdefiniowana następująco:
VGORNCVG ENCUUIGP6[RG
XQKFUYCR
IGV6[RGGNIGP6[RGGN ]
IGP6[RGVOR GN GN GN GN VOR
_
Przykład ten pokazuje konieczność dostosowania operatorów wbudowanych do konkretnych
sytuacji. Jeśli IGP6[RG jest liczbą, znakiem lub strukturą, operator przypisania zadziała prawidło-
wo. Jeśli jednak IGP6[RG jest tablicą, należy się spodziewać kłopotów ze strony funkcji UYCR
.
Problem ten można rozwiązać, przeciążając operator przypisania tak, aby rozszerzyć jego możli-
wości w stosunku do określonych typów danych.
Po zadeklarowaniu funkcji ogólnej w czasie kompilacji programu można wygenerować kon-
kretne funkcje. Jeśli, na przykład, kompilator „zobacizy” następujące dwa wywołania:
UYCR
PO \COKCPCFYÎEJNKE\DECđMQYKV[EJ
UYCR
Z[ \COKCPCFYÎEJNKE\D\OKGPPQRT\GEKPMQY[EJ
wygeneruje dwie funkcje UYCR
, które będą używane w programie.
1.3. Dziedziczenie
Programowanie obiektowe pozwala tworzyć własne hierarchie klas tak, że obiekty nie muszą nale-
żeć tylko do pojedynczych klas. Zanim przejdziemy do omówienia dziedziczenia, przyjrzyjmy się
następującym definicjom klas:
ENCUU$CUG NCUU]
RWDNKE
$CUG NCUU
]_
XQKFH
EJCT U PKG\PCP[ ]
EQWV (WPMELCH
Y$CUG NCUUY[YQđCPC\ U GPFN
J
_
20
1. PROGRAMOWANIE OBIEKTOWE W C++
RTQVGEVGF
XQKFI
EJCT U PKG\PCP[ ]
EQWV (WPMELCI
Y$CUG NCUUY[YQđCPC\ U GPFN
_
RTKXCVG
XQKFJ
]
EQWV (WPMELCJ
Y$CUG NCUU P
_
_
ENCUU GTKXGF.GXGN RWDNKEXKTVWCN$CUG NCUU]
RWDNKE
XQKFH
EJCT U PKG\PCP[ ]
EQWV (WPMELCH
Y GTKXGF.GXGNY[YQđCPC\ U GPFN
I
GTKXGF.GXGN
J
GTKXGF.GXGN
_
XQKFJ
EJCT U PKG\PCPC ]
EQWV (WPMELCJ
Y GTKXGF.GXGNY[YQđCPC\ U GPFN
_
_
ENCUU GTKXGF.GXGN RWDNKEXKTVWCN$CUG NCUU]
RWDNKE
XQKFH
EJCT U PKG\PCP[ ]
EQWV (WPMELCH
Y GTKXGF.GXGNY[YQđCPC\ U GPFN
I
GTKXGF.GXGN
J
DđæF $CUG NCUU J
PKGLGUVFQUVúRPC
_
_
ENCUU GTKXGF.GXGN RWDNKE GTKXGF.GXGNRWDNKE GTKXGF.GXGN]
RWDNKE
XQKFH
EJCT U PKG\PCP[ ]
EQWV (WPMELCH
Y GTKXGF.GXGNY[YQđCPC\ U GPFN
I
GTKXGF.GXGN
GTKXGF.GXGN J
GTKXGF.GXGN
$CUG NCUU H
GTKXGF.GXGN
_
_
A oto przykładowy program:
KPVOCKP
]
$CUG NCUUDE
GTKXGF.GXGNFN
GTKXGF.GXGNFN
GTKXGF.GXGNFN
DEH
OCKP
DEI
DđæF $CUG NCUU I
LGUVPKGFQUVúRPC
DEJ
DđæF $CUG NCUU J
LGUVPKGFQUVúRPC
FNH
OCKP
FNI
DđæF $CUG NCUU I
LGUVPKGFQUVúRPC
FNJ
OCKP
FNH
OCKP
1.3. DZIEDZICZENIE
21
FNI
DđæF $CUG NCUU I
LGUVPKGFQUVúRPC
FNJ
DđæF $CUG NCUU J
LGUVPKGFQUVúRPC
FNH
OCKP
FNI
DđæF $CUG NCUU I
LGUVPKGFQUVúRPC
FNJ
TGVWTP
_
Program powyższy da następujące wyniki:
(WPMELCH
Y$CUG NCUUY[YQđCPC\OCKP
(WPMELCJ
Y$CUG NCUU
(WPMELCH
Y GTKXGF.GXGNY[YQđCPC\OCKP
(WPMELCI
Y$CUG NCUUY[YQđCPC\ GTKXGF.GXGN
(WPMELCJ
Y GTKXGF.GXGNY[YQđCPC\ GTKXGF.GXGN
(WPMELCJ
Y GTKXGF.GXGNY[YQđCPC\OCKP
(WPMELCH
Y GTKXGF.GXGNY[YQđCPC\OCKP
(WPMELCI
Y$CUG NCUUY[YQđCPC\ GTKXGF.GXGN
(WPMELCH
Y GTKXGF.GXGNY[YQđCPC\OCKP
(WPMELCI
Y$CUG NCUUY[YQđCPC\ GTKXGF.GXGN
(WPMELCJ
Y GTKXGF.GXGNY[YQđCPC\ GTKXGF.GXGN
(WPMELCH
Y$CUG NCUUY[YQđCPC\ GTKXGF.GXGN
(WPMELCJ
Y$CUG NCUU
(WPMELCJ
Y GTKXGF.GXGNY[YQđCPC\PKG\PCP[
Klasa $CUG NCUU jest nazywana klasą bazową, zaś pozostałe klasy to klasy pochodne, gdyż po-
chodzą od klasy bazowej w tym sensie, że mogą korzystać z pól i metod $CUG NCUU oznaczonych jako
chronione (słowo kluczowe RTQVGEVGF) lub publiczne (RWDNKE). Klasy te dziedziczą wszystkie takie
pola po klasie bazowej, dzięki czemu zbędne jest powtarzanie w nich tych samych definicji. Jednak
klasa pochodna może przykryć definicję z klasy bazowej, podając własną definicję tej samej składowej.
W ten sposób zarówno klasa bazowa, jak i klasy pochodine mogą zapanować nad swoimi składowymi.
Klasa bazowa może decydować, które metody i które pola mogą zostać ujawnione klasom
pochodnym, wobec czego zasada ukrywania informacji jest zachowana nie tylko względem użytkow-
ników klasy bazowej, ale także klas pochodnych. Co więcej, klasa pochodna może zdecydować,
które części metod i pól publicznych i chronionych zostaną zachowane, a które będą modyfikowane.
Przykładowo, w obu klasach pochodnych pierwszego poziomu, GTKXGF.GXGN i GTKXGF.GXGN,
zdefiniowane są lokalne wersje metody H
. Jednak nadal można skorzystać z tak samo nazwanej
metody z wyższych poziomów hierarchii; w tym celu nazwę metody należy poprzedzić nazwą klasy
i operatorem zakresu, jak pokazano to w przypadku wywołania $CUG NCUU H
z metody H
w klasie
GTKXGF.GXGN.
Klasa pochodna sama też może zawierać dodatkowe pola danych. Klasa taka może stać się
z kolei klasą bazową dla innej klasy i tak dalej; hierarchię dziedziczenia można dowolnie rozsze-
rzać. Przykładowo, klasa GTKXGF.GXGN pochodzi od $CUG NCUU, ale jednocześnie jest klasą bazową
dla GTKXGF.GXGN.
W pokazanych przykładach dziedziczenie jest publiczne — po dwukropku w nagłówku defi-
nicji klasy pochodnej występuje słowo RWDNKE. Dziedziczenie publiczne oznacza, że pola publicz-
ne klasy bazowej będą w klasie pochodnej także publiczne, zaś chronione też będą chronione.
W przypadku dziedziczenia chronionego (w nagłówku klasy po dwukropku pojawia się słowo klu-
czowe RTQVGEVGF) pola i metody publiczne i chronione klasy bazowej w klasie pochodnej będą
chronione. W końcu, jeśli dziedziczenie jest prywatne (słowo kluczowe RTKXCVG), pola publiczne
i chronione klasy bazowej stają się prywatnymi polami klasy pochodnej. We wszystkich rodzajach
22
1. PROGRAMOWANIE OBIEKTOWE W C++
dziedziczenia metody i pola prywatne klasy bazowej we wszystkich klasach pochodnych są niedo-
stępne. Przykładowo, próba wywołania J
z metody H
w klasie GTKXGF.GXGN powoduje błąd
kompilacji „$CUG NCUU J
is not accessible”. Jednak wywołanie z H
metody J
w klasie G
TKXGF.GXGN nie sprawia żadnych kłopotów, gdyż jest ono interpretowane jako wywołanie metody
J
zdefiniowanej w klasie GTKXGF.GXGN.
Pola i metody chronione klasy bazowej dostępne są jedynie dla klasy pochodnej tej klasy.
Z tego powodu klasy GTKXGF.GXGN i GTKXGF.GXGN mogą wywołać metodę chronioną I
klasy
$CUG NCUU
, ale wywołanie tej metody w funkcji OCKP
jest już niedopuszczalne.
Klasa pochodna nie musi pochodzić od jednej tylko klasy bazowej. Przykładowo, klasa G
TKXGF.GXGN pochodzi od klas GTKXGF.GXGN i GTKXGF.GXGN, dziedzicząc w ten sposób wszystkie
metody obu tych klas. GTKXGF.GXGN dziedziczy jednak te same metody z $CUG NCUU dwukrotnie,
gdyż obie klasy pochodne poziomu pierwszego pochodzą od klasy $CUG NCUU. Jest to w najlep-
szym razie nadmiarowe i jako takie zbędne, a w najgorszym razie może spowodować błąd kompi-
lacji „member is ambiguous $CUG NCUU I
and $CUG NCUU I
”. Aby to się nie zdarzyło, definicje
obu klas bazowych zawierają modyfikator XKTVWCN, który oznacza, że klasa GTKXGF.GXGN zawiera
jedną tylko kopię każdej metody klasy $CUG NCUU. Analogiczny problem pojawi się, jeśli H
z G
TKXGF.GXGN wywoła J
bez podania operatora zakresu i nazwy klasy, tutaj GTKXGF.GXGN J
.
Nie ma znaczenia fakt, że metoda J
w $CUG NCUU jest prywatna i przez to niedostępna w GTKXG
F.GXGN — opisana sytuacja spowodowałaby wystąpienie błędu „member is ambiguous GTKXG
F.GXGN J
and $CUG NCUU J
”.
1.4. Wskaźniki
Zmienne używane w programie można traktować jako pojemniki, które nigdy nie są puste — zawsze
coś jest w środku, albo wstawione przez programistę, albo, w przypadku braku inicjalizacji, przez
system operacyjny. Każda taka zmienna ma co najmniej dwa atrybuty: zawartość czyli wartość
oraz położenie pojemnika w pamięci komputera. Zawartość może być liczbą, znakiem lub wielko-
ścią złożoną, jak struktura czy unia. Jednak wartość ta może być też położeniem innej zmiennej;
zmienna z taką wartością nazywane są wskaźnikami. Wskaźniki to zwykle zmienne pomocnicze,
które umożliwiają nam pośrednie sięganie do innych wartości. Wskaźnik jest analogią do znaku
drogowego, który wskazuje pewne miejsce, lub fiszki, na której zanotowano adres. Są to zmienne
prowadzące do zmiennych; pomocnicze zmienne wskazująice wartości, które są naprawdę istotne.
Jeśli mamy następującą deklarację:
KPVK L R S
K i L są zmiennymi liczbowymi, zaś R i S są wskaźnikami na te zmienne liczbowe; o ich roli decy-
duje poprzedzająca je gwiazdka. Zakładając, że adresy zmiennych K, L, R i S to, odpowiednio,
1080, 1082, 1084 i 1086, po przypisaniu zmiennej K wartości 15, uzyskamy w pamięci komputera
obraz taki, jak na rysunku 1.1a.
Moglibyśmy teraz wykonać przypisanie R K (lub R
KPV K, gdyby kompilator nie chciał
uznać pierwszej wersji), ale zmienna R została stworzona po to, aby przechowywać adres zmiennej
liczbowej, a nie jej wartość. Wobec tego prawidłowe przypisanie to R K, gdzie symbol wystę-
pujący przed K oznacza, że chodzi o adres zmiennej K, a nie o jej wartość. Pokazano to na rysunku
1.1b. Na rysunku 1.1c strzałka z R do K wskazuje, że R jest wskaźnikiem zawierającym adres K.
1.4. WSKAŹNIKI
23
RYSUNEK 1.1.
Zmiany wartości
po przypisaniach realizowane
są przy użyciu wskaźników.
Przypadki (b) i (c) opisują tę
samą sytuację, tak samo (d)
i (e), (g) i (h), (i) i (j), (k) i (l)
oraz (m) i (n)
Musimy być w stanie odróżniać wartość R — adres — od wartości umieszczonej pod tym adre-
sem. Aby na przykład przypisać wartość 20 zmiennej wsikazywanej przez R trzeba użyć wyrażenia:
R
Gwiazdka to operator dereferencji, który wymusza najpierw pobranie wartości R, potem się-
gnięcie do wskazywanego przez tę wartość miejsca i wpisanie tam liczby 20 (rysunek 1.1d). Ry-
sunki 1.1e do 1.1n to dalsze przykłady instrukcji przypisania, na których pokazano sposób umiesz-
czania wartości w pamięci komputera.
24
1. PROGRAMOWANIE OBIEKTOWE W C++
Tak naprawdę wskaźniki, tak samo jak inne zmienne, mają dwa atrybuty: zawartość i położe-
nie. Położenie można zapisać w innej zmiennej, która istaje się wskaźnikiem na wskaźnik.
Na rysunku 1.1 adresy zmiennych są przypisywane wskaźnikom, jednak wskaźniki mogą od-
nosić się do anonimowych lokalizacji w pamięci dostępnych jedynie przez adres, a niemających
nazw. Lokalizacje takie muszą być dynamicznie określane przez proces zarządzający pamięcią
podczas wykonywania programu, podczas gdy położenie zmiennych określane jest już na etapie
kompilacji.
Aby dynamicznie alokować i zwalniać pamięć, używa się dwóch funkcji. Jedna to PGY; pobiera
ona z pamięci taki fragment, jaki jest potrzebny na zapisanie danej typu, który zostanie podany za
słowem PGY. Przykładowo, instrukcja:
R PGYKPV
spowoduje zażądanie przez program pamięci potrzebnej na zamieszczenie jednej liczby całkowi-
tej, zaś adres tej pamięci zostanie umieszczony w zmiennej R. Teraz można blokowi wskazywa-
nemu przez R przypisywać wartości; trzeba to robić pośrednio, przez wskaźnik R lub dowolny inny
wskaźnik S, któremu przypiszemy adres z R instrukcją S R.
Kiedy pamięć zajmowana przez liczbę wskazywaną przez R przestaje być potrzebna, można
ją zwolnić do puli obsługiwanej przez system operaciyjny instrukcją:
FGNGVGR
Jednak nawet po wykonaniu tej instrukcji zmienna R nadal zawiera adres zwolnionego bloku, choć
blok ten przestaje być w programie dostępny. To tak, jakby traktować adres zburzonego domu jako
adres możliwego zamieszkania. Każda próba znalezienia kogoś pod takim adresem jest z góry
skazana na niepowodzenie. Analogicznie, jeśli po wywołaniu instrukcji FGNGVG nie usuniemy ze
zmiennej wskaźnikowej adresu, narażamy się na ryzyko błędów; program może przestać działać
podczas prób dostępu do nienależącej już do niego pamięci. Jest to szczególnie niebezpieczne
w przypadku sięgania do obiektów bardziej złożonych niż liczby. Aby uniknąć opisanego problemu,
należy wskaźnikowi przypisać nowy adres; jeśli nie ma żadnego prawidłowego adresu na podorędziu,
należy użyć adresu pustego, o wartości . Po wykonaniu przypisania:
R
nie mówimy, że R wskazuje zero czy 07.., lecz że R ma wartość 07.. (pustą).
1.4.1. Wskaźniki a tablice
W pokazanym powyżej przykładzie wskaźnik R wskazywał blok pamięci zawierający jedną liczbę
całkowitą. Znacznie ciekawsza jest sytuacja, kiedy wskaźnik wskazuje strukturę danych tworzoną
i modyfikowaną dynamicznie. Pozwala to obejść ograniczenia dotyczące tablic. W C++, podobnie
jak większości innych języków programowania, tablice trzeba zawczasu zadeklarować. Wobec te-
go ich rozmiar musi być znany przed uruchomieniem programu, a zatem programista musi dość
dużo wiedzieć o oprogramowanym problemie, gdyż jest to warunkiem poprawnego określenia
wielkości tablicy. Jeśli tablica będzie zbyt duża, niepotrzebnie zajmowana przez nią pamięć będzie
zmarnowana. Jeśli tablica będzie zbyt mała, dane będą umieszczane za jej końcem, co powoduje
poważną awarię programu. Czasami jednak rozmiaru tablicy po prostu nie da się przewidzieć —
w takiej sytuacji decyzję o wielkości tablicy i przez to alokowanej pamięci odkłada się do czasu
wykonywania programu.
1.4. WSKAŹNIKI
25
Do rozwiązania opisanego problemu używa się wskaźników. Spójrzmy na rysunek 1.1b.
Wskaźnik R wskazuje adres 1080, ale można za jego pośrednictwem sięgnąć też pod adresy 1082,
1084 i tak dalej — jest to możliwe dzięki temu, że kolejne dane przesuwane są o taką samą wiel-
kość. Aby, na przykład, sięgnąć do wartości zmiennej L sąsiadującej z K, wystarczy dodać do adresu
K trzymanego w R rozmiar wartości zmiennej L; wtedy wskaźnik R będzie wskazywał adres zmien-
nej L. Tak właśnie w C++ obsługiwane są tablice.
Przyjrzyjmy się następującym deklaracjom:
KPVC=? R
Deklaracje te mówią, że C jest wskaźnikiem bloku pamięci, który może zawierać pięć liczb
całkowitych. Wskaźnik jest stały, to znaczy należy go traktować jako stały; wobec tego każda próba
przypisania zmiennej C wartości, na przykład:
C R
lub:
C
traktowana jest jako błąd kompilacji. Zmienna C jest wskaźnikiem, więc do sięgnięcia do poszcze-
gólnych komórek tablicy C można używać zapisu wskaźnikowego. Tak oto pętlę dodającą wszystkie
wartości z tej tablicy:
HQT
UWO C=?K K K
UWO
C=K?
można zamienić na zapis wskaźnikowy tak:
HQT
UWO CK K K
UWO
C
K
lub tak:
HQT
UWO CR C
R C
R
UWO
R
Zauważmy, że skoro C
oznacza położenie następnej komórki tablicy C, to C
jest odpowiednikiem
C=?. Wobec tego, jeśli C wskazuje adres 1020, to C
nie zawiera adresu 1021, lecz 1022, gdyż sto-
sowana jest arytmetyka wskaźników zależna od typu wskiazywanych danych. Jeśli dane są deklaracje:
EJCTD=?
NQPIE=?
i wiadomo, że D równe jest 1050, E równe jest 1055, to D
równe jest 1051, gdyż jeden znak zaj-
muje jeden bajt, zaś E
równe jest 1059, gdyż liczba typu NQPI zajmuje cztery bajty. Jest to wyni-
kiem faktu, że w arytmetyce wskaźników wyrażenie E
K oznacza adres E
K UK\GQH
NQPI .
Dotąd tablica C była deklarowana statycznie i zawierała pięć komórek. Rozmiar takiej tablicy
jest ustalony na cały czas działania programu. Tablice można deklarować także dynamicznie; wtedy
używane są zmienne wskaźnikowe. Przykładowo, przypisianie:
R PGYKPV=P?
26
1. PROGRAMOWANIE OBIEKTOWE W C++
powoduje zaalokowanie pamięci na P liczb całkowitych. Wskaźnik R można traktować jako
zmienną tablicową i można stosować doń notację tablicową. Sumę liczb z tablicy R można wyzna-
czyć tak:
HQT
UWO R=?K K P K
UWO
R=K?
Można zastosować też notację wskaźnikową normalnie:
HQT
UWO RK K P K
UWO
R
K
lub korzystając z dwóch wskaźników:
HQT
UWO RS R
S R
P S
UWO
S
R jest zmienną, więc można jej przypisać nową tablicę. Kiedy tablica wskazywana przez R prze-
staj
Pobierz darmowy fragment (pdf)
