Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00563 008486 10489550 na godz. na dobę w sumie
C++. Algorytmy i struktury danych - książka
C++. Algorytmy i struktury danych - książka
Autor: Liczba stron: 616
Wydawca: Helion Język publikacji: polski
ISBN: 83-7361-385-4 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> algorytmy - programowanie
Porównaj ceny (książka, ebook, audiobook).

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:

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.

Znajdź podobne książki Ostatnio czytane w tej kategorii

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 UKPVKFQWDNGF ] UVTER[ FCVC/GODGTU  FCVC/GODGTK FCVC/GODGTF _ XQKFOGODGT(WPEVKQP ] EQWVFCVC/GODGT  FCVC/GODGT  FCVC/GODGTGPFN _ XQKFOGODGT(WPEVKQP KPVKEJCT UPKG\PCPC ] FCVC/GODGTK EQWVKRQDTCPC\UGPFN _ 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: VGORNCVGENCUUIGP6[RG ENCUUIGP NCUU] IGP6[RGUVQTCIG=?  _ Dopiero potem decydujemy, jak inicjalizowany będzie ityp IGP6[RG: IGP NCUUKPV KPV1DLGEV IGP NCUUHNQCV 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 VGORNCVGENCUUIGP6[RGKPVUK\G ENCUUIGP NCUU] IGP6[RGUVQTCIG=UK\G?  _ Definicje obiektów będą teraz wyglądały następująco: IGP NCUUKPV KPV1DLGEVWľ[V[\QUVCPKGTQ\OKCTFQO[ħNP[ IGP NCUUKPV KPV1DLGEV IGP NCUUHNQCV 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: VGORNCVGENCUUIGP6[RG XQKFUYCR IGV6[RGGNIGP6[RGGN ] IGP6[RGVORGNGNGNGNVOR _ 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 UPKG\PCP[ ] EQWV(WPMELCH Y$CUG NCUUY[YQđCPC\UGPFN J  _ 20 1. PROGRAMOWANIE OBIEKTOWE W C++ RTQVGEVGF XQKFI EJCT UPKG\PCP[ ] EQWV(WPMELCI Y$CUG NCUUY[YQđCPC\UGPFN _ RTKXCVG XQKFJ ] EQWV(WPMELCJ Y$CUG NCUU P _ _ ENCUU GTKXGF.GXGNRWDNKEXKTVWCN$CUG NCUU] RWDNKE XQKFH EJCT UPKG\PCP[ ] EQWV(WPMELCH Y GTKXGF.GXGNY[YQđCPC\UGPFN I  GTKXGF.GXGN  J  GTKXGF.GXGN  _ XQKFJ EJCT UPKG\PCPC ] EQWV(WPMELCJ Y GTKXGF.GXGNY[YQđCPC\UGPFN _ _ ENCUU GTKXGF.GXGNRWDNKEXKTVWCN$CUG NCUU] RWDNKE XQKFH EJCT UPKG\PCP[ ] EQWV(WPMELCH Y GTKXGF.GXGNY[YQđCPC\UGPFN I  GTKXGF.GXGN  J DđæF$CUG NCUUJ PKGLGUVFQUVúRPC _ _ ENCUU GTKXGF.GXGNRWDNKE GTKXGF.GXGNRWDNKE GTKXGF.GXGN] RWDNKE XQKFH EJCT UPKG\PCP[ ] EQWV(WPMELCH Y GTKXGF.GXGNY[YQđCPC\UGPFN I  GTKXGF.GXGN   GTKXGF.GXGNJ  GTKXGF.GXGN  $CUG NCUUH  GTKXGF.GXGN  _ _ A oto przykładowy program: KPVOCKP ] $CUG NCUUDE  GTKXGF.GXGNFN  GTKXGF.GXGNFN  GTKXGF.GXGNFN DEH OCKP    DEI DđæF$CUG NCUUI LGUVPKGFQUVúRPC DEJ DđæF$CUG NCUUJ LGUVPKGFQUVúRPC FNH OCKP    FNI DđæF$CUG NCUUI LGUVPKGFQUVúRPC FNJ OCKP    FNH OCKP    1.3. DZIEDZICZENIE 21 FNI DđæF$CUG NCUUI LGUVPKGFQUVúRPC FNJ DđæF$CUG NCUUJ LGUVPKGFQUVúRPC FNH OCKP    FNI DđæF$CUG NCUUI 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 NCUUH 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 NCUUJ 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 NCUUI and $CUG NCUUI ”. 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.GXGNJ . 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.GXGNJ and $CUG NCUUJ ”. 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ę: KPVKL 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 RK (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 RK, 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: RPGYKPV 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ą SR. 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: CR 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 UWOC=?KKK UWO C=K? można zamienić na zapis wskaźnikowy tak: HQT UWO CKKK UWO  C K  lub tak: HQT UWO CRC RC 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: RPGYKPV=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 UWOR=?KKPK UWO R=K? Można zastosować też notację wskaźnikową normalnie: HQT UWO RKKPK UWO  R K  lub korzystając z dwóch wskaźników: HQT UWO RSR SR PS UWO  S R jest zmienną, więc można jej przypisać nową tablicę. Kiedy tablica wskazywana przez R prze- staj
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

C++. Algorytmy i struktury danych
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: