Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00285 004779 18972347 na godz. na dobę w sumie
C++. Struktury danych i algorytmy - książka
C++. Struktury danych i algorytmy - książka
Autor: Liczba stron: 264
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-283-5185-1 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> c++ - programowanie
Porównaj ceny (książka, ebook (-35%), audiobook).

C++ to dojrzały język programowania o wielu różnych zastosowaniach. Inżynier oprogramowania, który chce w pełni skorzystać z jego zalet, powinien płynnie posługiwać się dostępnymi w tym języku strukturami danych i algorytmami. W ten sposób łatwiej można rozwiązywać konkretne problemy. Zastosowanie odpowiedniej struktury danych oraz algorytmu jest również ważne z punktu widzenia wydajności działania kodu, co bezpośrednio przekłada się na szybkość pracy aplikacji. Bez dogłębnego zrozumienia tych zagadnień bardzo trudno nauczyć się biegle programować w C++.

Dzięki tej książce dowiesz się, na czym polega implementacja klasycznych struktur danych i algorytmów w C++. Znajdziesz tu również przystępne wprowadzenie do podstawowych konstrukcji językowych oraz do korzystania z zintegrowanego środowiska programistycznego (IDE). Ponadto dowiesz się, w jaki sposób przechowywać dane za pomocą list wiązanych, tablic, stosów i kolejek, a także jak zaimplementować algorytmy sortowania, takie jak sortowanie szybkie i sortowanie przez kopcowanie, oraz algorytmy wyszukiwania, takie jak wyszukiwanie liniowe czy binarne. Kolejnym ważnym zagadnieniem ujętym w książce jest wysoka wydajność algorytmów operujących na ciągach znakowych i strukturach mieszających, jak również analiza algorytmów siłowych, zachłannych i wielu innych.

Najciekawsze zagadnienia ujęte w książce:

C++. O jakości kodu decyduje algorytm i odpowiednia struktura danych!

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

Darmowy fragment publikacji:

Tytuł oryginału: C++ Data Structures and Algorithms Tłumaczenie: Maksymilian Gutowski ISBN: 978-83-283-5185-1 Copyright © Packt Publishing 2018. First published in the English language under the title ‘C++ Data Structures and Algorithms – (9781788835213)’ Polish edition copyright © 2019 by Helion SA All rights reserved. All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from the Publisher. Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje naruszenie praw autorskich niniejszej publikacji. Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich właścicieli. Autor oraz Helion SA dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Helion SA nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Helion SA ul. Kościuszki 1c, 44-100 Gliwice tel. 32 231 22 19, 32 230 98 63 e-mail: helion@helion.pl WWW: http://helion.pl (księgarnia internetowa, katalog książek) Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://helion.pl/user/opinie/cppstr Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. Printed in Poland. • Kup książkę • Poleć książkę • Oceń książkę • Księgarnia internetowa • Lubię to! » Nasza społeczność Spis tre(cid:258)ci O autorze O recenzencie Wst(cid:218)p Rozdzia(cid:239) 1. Struktury danych i algorytmy w C++ Wymagania techniczne Podstawy C++ Pierwszy kod w C++ Usprawnianie pracy nad kodem przy u(cid:285)yciu IDE Definiowanie zmiennych przy u(cid:285)yciu podstawowych typów danych Sterowanie przep(cid:239)ywem kodu Wykorzystanie zmiennych za po(cid:258)rednictwem zaawansowanych typów danych Tworzenie abstrakcyjnych typów danych Wykorzystanie klas C++ przy tworzeniu ADT zdefiniowanych przez u(cid:285)ytkownika Pos(cid:239)ugiwanie si(cid:218) szablonami Analiza algorytmów Analiza asymptotyczna Najgorsze, (cid:258)rednie i najlepsze przypadki Notacja(cid:3)(cid:710), (cid:50) i (cid:726)(cid:3) Metoda rekurencyjna Analiza kosztu zamortyzowanego Podsumowanie Pytania Dodatkowe materia(cid:239)y 9 10 11 15 15 16 16 17 19 20 28 33 33 39 44 44 47 48 49 49 50 50 50 Poleć książkęKup książkę Spis tre(cid:286)ci Rozdzia(cid:239) 2. Przechowywanie danych w listach i listach wi(cid:200)zanych Wymagania techniczne Tablice Tworzenie ADT listy Zwracanie elementu z listy Wstawianie elementu do listy Wyszukiwanie indeksu wybranego elementu w li(cid:258)cie Usuwanie elementu z listy Implementacja listy Wprowadzenie do w(cid:218)z(cid:239)ów Tworzenie ADT listy jednokierunkowej Zwracanie elementu z listy wi(cid:200)zanej Wstawianie elementu do listy wi(cid:200)zanej Wyszukiwanie indeksu wybranego elementu w li(cid:258)cie wi(cid:200)zanej Usuwanie elementu z listy wi(cid:200)zanej Implementacja listy wi(cid:200)zanej Tworzenie ADT listy dwukierunkowej Refaktoryzacja typu danych Node T Refaktoryzacja kilku operacji LinkedList Implementacja ADT listy dwukierunkowej Wykorzystanie typów List i LinkedList przy u(cid:285)yciu STL std::vector std::list Podsumowanie Pytania Dodatkowe materia(cid:239)y Rozdzia(cid:239) 3. Tworzenie stosów i kolejek Wymagania techniczne Tworzenie ADT stosu Pobieranie warto(cid:258)ci elementu z ADT stosu Umieszczanie elementów na ADT stosu Usuwanie elementów z ADT stosu Implementacja ADT stosu Tworzenie ADT kolejki jednokierunkowej Pobieranie warto(cid:258)ci elementu z ADT kolejki Wstawianie elementu do ADT kolejki Usuwanie elementu z ADT kolejki Implementacja ADT kolejki Tworzenie ADT kolejki dwukierunkowej Pobieranie warto(cid:258)ci elementu z ADT kolejki dwukierunkowej Dodawanie elementu do ADT kolejki dwukierunkowej Usuwanie elementu z ADT kolejki dwukierunkowej Implementacja ADT kolejki dwukierunkowej Podsumowanie Pytania Dodatkowe materia(cid:239)y 4 51 51 52 55 56 57 58 58 59 61 65 66 67 69 70 73 75 76 76 81 83 83 85 88 88 88 91 91 92 93 93 94 95 99 100 100 101 102 103 104 104 106 107 108 109 109 Poleć książkęKup książkę Spis tre(cid:286)ci Rozdzia(cid:239) 4. Porz(cid:200)dkowanie elementów przy u(cid:285)yciu algorytmów sortowania Wymagania techniczne Sortowanie b(cid:200)belkowe Sortowanie przez wybieranie Sortowanie przez wstawianie Sortowanie przez scalanie Sortowanie szybkie Sortowanie przez zliczanie Sortowanie pozycyjne Podsumowanie Pytania Dodatkowe materia(cid:239)y Rozdzia(cid:239) 5. Wyszukiwanie elementów przy u(cid:285)yciu algorytmów wyszukiwania Wymagania techniczne Wyszukiwanie liniowe Opracowanie algorytmu wyszukiwania liniowego Implementacja algorytmu wyszukiwania liniowego Wyszukiwanie binarne Opracowanie algorytmu wyszukiwania binarnego Implementacja algorytmu wyszukiwania binarnego Wyszukiwanie ternarne Opracowanie algorytmu wyszukiwania ternarnego Zastosowanie algorytmu wyszukiwania ternarnego Wyszukiwanie interpolacyjne Opracowanie algorytmu wyszukiwania interpolacyjnego Zastosowanie algorytmu wyszukiwania interpolacyjnego Wyszukiwanie skokowe Opracowanie algorytmu wyszukiwania skokowego Zastosowanie algorytmu wyszukiwania skokowego Wyszukiwanie wyk(cid:239)adnicze Opracowanie algorytmu wyszukiwania wyk(cid:239)adniczego Wywo(cid:239)anie funkcji ExponentialSearch() Wyszukiwanie podlisty Opracowanie algorytmu wyszukiwania podlisty Wykorzystanie algorytmu wyszukiwania podlisty Podsumowanie Pytania Dodatkowe materia(cid:239)y Rozdzia(cid:239) 6. U(cid:285)ywanie znakowego typu danych Wymagania techniczne Ci(cid:200)g znakowy C++ Tworzenie ci(cid:200)gu znaków przy u(cid:285)yciu tablicy znaków Dodatkowe funkcje std::string Zabawa s(cid:239)owami Tworzenie anagramów Wykrywanie palindromów 111 111 112 114 118 122 128 133 136 140 140 141 143 144 144 144 145 146 146 147 148 149 150 151 151 153 154 154 155 156 156 157 158 159 160 162 162 163 165 165 166 166 166 167 167 169 5 Poleć książkęKup książkę Spis tre(cid:286)ci Tworzenie ci(cid:200)gu z cyfr binarnych Konwertowanie liczb dziesi(cid:218)tnych na binarne Konwertowanie ci(cid:200)gu binarnego na dziesi(cid:218)tny Ci(cid:200)g podsekwencji Generowanie podsekwencji z ci(cid:200)gu Sprawdzanie, czy ci(cid:200)g jest podsekwencj(cid:200) innego ci(cid:200)gu Wyszukiwanie wzorca Podsumowanie Pytania Dodatkowe materia(cid:239)y Rozdzia(cid:239) 7. Tworzenie hierarchicznej struktury drzewa Wymagania techniczne Tworzenie ADT drzewa binarnego Tworzenie ADT binarnego drzewa poszukiwa(cid:241) Wstawianie nowego klucza do BST Przechodzenie po BST po kolei Sprawdzanie obecno(cid:258)ci klucza w BST Zwracanie minimalnych i maksymalnych warto(cid:258)ci kluczy Wyszukiwanie nast(cid:218)pnika klucza w BST Wyszukiwanie poprzednika klucza w BST Usuwanie w(cid:218)z(cid:239)a wed(cid:239)ug podanego klucza Implementacja ADT BST Tworzenie ADT zrównowa(cid:285)onego BST (AVL) Rotacja w(cid:218)z(cid:239)ów Wstawianie nowego klucza Usuwanie wskazanego klucza Implementacja ADT AVL Tworzenie ADT kopca binarnego Sprawdzanie, czy kopiec jest pusty Wstawianie nowego elementu do kopca Pobieranie elementu o najwi(cid:218)kszej warto(cid:258)ci Usuwanie elementu o najwi(cid:218)kszej warto(cid:258)ci Implementacja stosu binarnego jako kolejki priorytetowej Podsumowanie Pytania Dodatkowe materia(cid:239)y Rozdzia(cid:239) 8. Zestawianie warto(cid:258)ci z kluczem w tablicy mieszaj(cid:200)cej Wymagania techniczne Wprowadzenie do tablic mieszaj(cid:200)cych Du(cid:285)o danych w ma(cid:239)ych komórkach Przechowywanie danych w tablicy mieszaj(cid:200)cej Obs(cid:239)uga kolizji Implementacja metody (cid:239)a(cid:241)cuchowej Generowanie klucza mieszaj(cid:200)cego Opracowanie operacji Insert() Opracowanie operacji Search() 6 172 173 175 177 177 179 181 184 184 185 187 187 188 190 192 193 193 194 195 197 199 201 204 205 207 208 210 212 213 214 214 215 216 217 218 218 219 219 220 220 221 221 222 223 223 224 Poleć książkęKup książkę Spis tre(cid:286)ci Opracowanie operacji Remove() Opracowanie operacji IsEmpty() Zastosowanie ADT HashTable wykorzystuj(cid:200)cego metod(cid:218) (cid:239)a(cid:241)cuchow(cid:200) Implementacja techniki adresowania otwartego Opracowanie operacji Insert() Opracowanie operacji Search() Opracowanie operacji Remove() Opracowanie operacji IsEmpty() Opracowanie operacji PrintHashTable() Wdro(cid:285)enie ADT HashTable wykorzystuj(cid:200)cego technik(cid:218) szukania liniowego Podsumowanie Pytania Dodatkowe materia(cid:239)y Rozdzia(cid:239) 9. Implementacja algorytmów w praktyce Wymagania techniczne Algorytmy zach(cid:239)anne Rozwi(cid:200)zanie problemu wydawania reszty Zastosowanie kodowania Huffmana Algorytmy „dziel i zwyci(cid:218)(cid:285)aj” Rozwi(cid:200)zywanie problemów selekcyjnych Mno(cid:285)enie macierzy Programowanie dynamiczne Ci(cid:200)g Fibonacciego Programowanie dynamiczne i problem wydawania reszty Algorytmy si(cid:239)owe Wyszukiwanie i sortowanie si(cid:239)owe Wady i zalety algorytmów si(cid:239)owych Algorytmy zrandomizowane Klasyfikacja algorytmów zrandomizowanych Generatory liczb losowych Zastosowania algorytmów zrandomizowanych Algorytmy z nawrotami Meblowanie nowego mieszkania Kó(cid:239)ko i krzy(cid:285)yk Podsumowanie Pytania Dodatkowe materia(cid:239)y Skorowidz 224 225 226 228 230 231 232 233 233 234 237 237 237 239 239 240 240 242 246 248 249 250 250 251 252 252 253 253 255 255 257 257 258 258 259 260 260 261 7 Poleć książkęKup książkę Spis tre(cid:286)ci 8 Poleć książkęKup książkę 1 Struktury danych i algorytmy w C++ W pierwszym rozdziale po(cid:239)o(cid:285)ymy solidny fundament, który pozwoli Ci z (cid:239)atwo(cid:258)ci(cid:200) przej(cid:258)(cid:202) przez kolejne rozdzia(cid:239)y. Oto tematy, które omówimy w tym rozdziale: (cid:81) tworzenie, kompilowanie i uruchamianie prostego programu C++; (cid:81) konstruowanie abstrakcyjnego typu danych w celu utworzenia typu danych zdefiniowanego przez u(cid:285)ytkownika; (cid:81) wykorzystanie kodu za pomoc(cid:200) szablonów C++ i Standard Template Library (STL); (cid:81) analizowanie z(cid:239)o(cid:285)ono(cid:258)ci algorytmów w celu zmierzenia wydajno(cid:258)ci kodu. Wymagania techniczne Do przeczytania tego rozdzia(cid:239)u i pos(cid:239)u(cid:285)enia si(cid:218) przedstawionym w nim kodem (cid:283)ród(cid:239)owym konieczne s(cid:200) nast(cid:218)puj(cid:200)ce zasoby: (cid:81) komputer stacjonarny lub laptop z systemem Windows, Linux albo macOS; (cid:81) GNU GCC v5.4.0 lub nowsza; (cid:81) Code::Block IDE v17.12 (dla systemów Windows i Linux) lub Code::Block IDE v13.12 (dla macOS); (cid:81) pliki z kodem, które znajdziesz w archiwum pobranym ze strony ftp://ftp.helion.pl/przyklady/cppstr.zip. Poleć książkęKup książkę C++. Struktury danych i algorytmy Podstawy C++ Przed przej(cid:258)ciem do omówienia struktur danych i algorytmów w C++ musimy po(cid:258)wi(cid:218)ci(cid:202) nieco miejsca podstawom samego j(cid:218)zyka C++. W tym podrozdziale napiszemy prosty program, skompilujemy go, a nast(cid:218)pnie uruchomimy. Omówimy tak(cid:285)e podstawowe oraz zaawansowane typy danych i kontrol(cid:218) przep(cid:239)ywu, zanim zajmiemy si(cid:218) przep(cid:239)ywem sterowania. Pierwszy kod w C++ W C++ wykonywanie kodu rozpoczyna si(cid:218) od funkcji main(). Ta funkcja jest zbiorem instrukcji okre(cid:258)laj(cid:200)cych konkretne zadania do wykonania. W zwi(cid:200)zku z tym program w C++ musi sk(cid:239)ada(cid:202) si(cid:218) z przynajmniej jednej funkcji o nazwie main(). Poni(cid:285)szy kod jest najprostszym pro- gramem C++, jaki mo(cid:285)na z powodzeniem skompilowa(cid:202) i uruchomi(cid:202): int main() { return 0; } Za(cid:239)ó(cid:285)my, (cid:285)e powy(cid:285)szy kod zosta(cid:239) zapisany jako plik simple.cpp. Mo(cid:285)emy skompilowa(cid:202) kod przy u(cid:285)yciu kompilatora g++, wprowadzaj(cid:200)c poni(cid:285)sz(cid:200) komend(cid:218) kompilacji w konsoli w katalogu, w którym znajduje si(cid:218) plik simple.cpp: g++ simple.cpp Je(cid:258)li nie zobaczymy (cid:285)adnego komunikatu o b(cid:239)(cid:218)dzie, oznacza to, (cid:285)e plik wyj(cid:258)ciowy zosta(cid:239) auto- matycznie wygenerowany. Po wprowadzeniu komendy kompilacji w konsoli systemu Windows otrzymamy plik o nazwie a.exe, a wprowadzenie jej w pow(cid:239)oce Bash, na przyk(cid:239)ad w systemach Linux i macOS, spowoduje utworzenie pliku o nazwie a.out. Mo(cid:285)emy okre(cid:258)li(cid:202) nazw(cid:218) pliku wej(cid:258)ciowego, u(cid:285)ywaj(cid:200)c opcji -o i podaj(cid:200)c po(cid:285)(cid:200)dan(cid:200) nazw(cid:218) pliku. Poni(cid:285)sza komenda kompilacji spowodowa(cid:239)aby zatem zwrócenie pliku wyj(cid:258)ciowego o nazwie simple.out: g++ simple.cpp -o simple.out Po uruchomieniu pliku wyj(cid:258)ciowego (poprzez wprowadzenie nazwy a i naci(cid:258)ni(cid:218)cie klawisza Enter w konsoli systemu Windows lub wpisanie ./a.out i naci(cid:258)ni(cid:218)cie klawisza Enter w pow(cid:239)oce Bash) w oknie konsoli nic si(cid:218) nie pojawi. Jest tak, poniewa(cid:285) nie ka(cid:285)emy jeszcze niczego w niej wy(cid:258)wietla(cid:202). Aby nasz plik simple.cpp nabra(cid:239) sensu, zrefaktoryzujmy kod tak, by otrzymywa(cid:239) dane wej(cid:258)ciowe od u(cid:285)ytkownika i je wy(cid:258)wietla(cid:239). Kod powinien wygl(cid:200)da(cid:202) nast(cid:218)puj(cid:200)co: // in_out.cpp #include iostream int main () { int i; 16 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ std::cout Podaj liczb(cid:218) ca(cid:239)kowit(cid:200): ; std::cin i; std::cout Podana warto(cid:258)(cid:202) to i; std::cout \n ; return 0; } Jak wida(cid:202), w powy(cid:285)szym kodzie dodali(cid:258)my kilka linijek, tak aby program wy(cid:258)wietla(cid:239) informacje w konsoli i umo(cid:285)liwia(cid:239) u(cid:285)ytkownikowi wprowadzenie danych wej(cid:258)ciowych. Program wst(cid:218)pnie wy(cid:258)wietla tekst i prosi u(cid:285)ytkownika o podanie liczby ca(cid:239)kowitej. Po wpisaniu przez u(cid:285)ytkownika wybranej przez niego liczby i naci(cid:258)ni(cid:218)ciu Enter program wy(cid:258)wietla podan(cid:200) liczb(cid:218). Zdefinio- wali(cid:258)my te(cid:285) now(cid:200) zmienn(cid:200) i nale(cid:285)(cid:200)c(cid:200) do typu danych int. S(cid:239)u(cid:285)y ona do przechowywania danych w formacie liczby ca(cid:239)kowitej (temat zmiennych i typów danych zostanie poruszony w jednym z kolejnych punktów). Za(cid:239)ó(cid:285)my, (cid:285)e zapisali(cid:258)my powy(cid:285)szy kod w pliku in_out.cpp; mo(cid:285)emy go skompilowa(cid:202), u(cid:285)ywaj(cid:200)c nast(cid:218)puj(cid:200)cego polecenia: g++ in_out.cpp Je(cid:258)li uruchomimy nast(cid:218)pnie program, otrzymamy w konsoli poni(cid:285)szy wynik (na potrzeby przyk(cid:239)adu wprowadzi(cid:239)em liczb(cid:218) 3): Wiesz ju(cid:285), (cid:285)e do wy(cid:258)wietlenia tekstu w konsoli u(cid:285)ywamy instrukcji std::cout, a do wprowa- dzania danych wej(cid:258)ciowych do programu instrukcji std::cin. Na pocz(cid:200)tku pliku in_out.cpp znajduje si(cid:218) instrukcja #include iostream , która wskazuje kompilatorowi, gdzie szuka(cid:202) implementacji polece(cid:241) std::cout i std::cin, jako (cid:285)e s(cid:200) one okre(cid:258)lone w pliku nag(cid:239)ówkowym iostream. Na samym pocz(cid:200)tku pliku znajduje si(cid:218) jeszcze wiersz zaczynaj(cid:200)cy si(cid:218) od dwóch uko(cid:258)ników (//). Wskazuj(cid:200) one, (cid:285)e dany wiersz nie jest traktowany jako kod, ma on wi(cid:218)c zosta(cid:202) zignorowany przez kompilator. Wiersz ten s(cid:239)u(cid:285)y do zapisania komentarza lub oznaczenia okre(cid:258)lonego dzia(cid:239)a- nia w kodzie, tak aby u(cid:239)atwi(cid:202) innym programistom jego zrozumienie. Usprawnianie pracy nad kodem przy u(cid:285)yciu IDE Uda(cid:239)o nam si(cid:218) dot(cid:200)d napisa(cid:202) kod C++, skompilowa(cid:202) i uruchomi(cid:202) go. Ci(cid:200)g(cid:239)e kompilowanie kodu i wykonywanie go w linii polece(cid:241) by(cid:239)oby jednak nudne. Aby u(cid:239)atwi(cid:202) sobie prac(cid:218) z kodem, skorzystamy ze zintegrowanego (cid:258)rodowiska programistycznego (ang. integrated development environment — IDE), w którym b(cid:218)dziemy mogli kompilowa(cid:202) i uruchamia(cid:202) kod za jednym klikni(cid:218)ciem. Mo(cid:285)esz skorzysta(cid:202) z dowolnego dost(cid:218)pnego na rynku IDE C++, zarówno p(cid:239)atnego, 17 Poleć książkęKup książkę C++. Struktury danych i algorytmy jak i darmowego. Sam preferuj(cid:218) IDE Code::Blocks, poniewa(cid:285) jest darmowe, otwarte i wieloplat- formowe, wobec czego dzia(cid:239)a w systemach Windows, Linux i macOS. Wi(cid:218)cej informacji na temat tego IDE, w tym instrukcje dotycz(cid:200)ce pobierania go, instalacji oraz u(cid:285)ytkowania, znajdziesz na jego oficjalnej stronie internetowej pod adresem http://www.codeblocks.org/. Mogliby(cid:258)my zautomatyzowa(cid:202) proces kompilacji przy u(cid:285)yciu toolchaina takiego jak Make lub CMake, ale wymaga(cid:239)oby to dodatkowych wyja(cid:258)nie(cid:241). Poniewa(cid:285) tematem tej ksi(cid:200)(cid:285)ki s(cid:200) struktury danych i algorytmy, podj(cid:218)cie tego w(cid:200)tku zwi(cid:218)kszy(cid:239)oby d(cid:239)ugo(cid:258)(cid:202) tekstu — z tego wzgl(cid:218)du nie omówimy tego zagadnienia szerzej. Na nasze potrzeby IDE oferuje najlepsz(cid:200) mo(cid:285)liwo(cid:258)(cid:202) auto- matyzacji procesu kompilacyjnego, poniewa(cid:285) u(cid:285)ywa do tego toolchaina. Po zainstalowaniu IDE Code::Blocks mo(cid:285)emy utworzy(cid:202) nowy projekt, klikaj(cid:200)c menu File/New/ (cid:180)Project (plik/nowy/projekt). Na ekranie pojawi si(cid:218) nowe okno, w którym b(cid:218)dziemy mogli wy- bra(cid:202) po(cid:285)(cid:200)dany typ projektu. Dla wi(cid:218)kszo(cid:258)ci przyk(cid:239)adów w tej ksi(cid:200)(cid:285)ce b(cid:218)dziemy u(cid:285)ywa(cid:202) typu Console Application (aplikacja konsolowa). Naci(cid:258)nij przycisk Go (dalej), aby kontynuowa(cid:202). W kolejnym oknie wskazujemy j(cid:218)zyk, czyli C++, a nast(cid:218)pnie okre(cid:258)lamy nazw(cid:218) projektu i lokali- zacj(cid:218) docelow(cid:200) (swojemu projektowi nada(cid:239)em nazw(cid:218) FirstApp). Po zako(cid:241)czeniu pracy z kreato- rem otrzymujemy nowy projekt z plikiem main.cpp zawieraj(cid:200)cym nast(cid:218)puj(cid:200)cy kod: #include iostream using namespace std; int main() { cout Witaj, (cid:258)wiecie! endl; return 0; } Mo(cid:285)emy teraz skompilowa(cid:202) i uruchomi(cid:202) powy(cid:285)szy kod, klikaj(cid:200)c opcj(cid:218) Build and run (skompiluj i uruchom) w menu Build (kompilacja). Na ekranie pojawi si(cid:218) nast(cid:218)puj(cid:200)ce okno konsoli: Na powy(cid:285)szym rysunku widzimy, (cid:285)e konsola wykorzystuje namespace std z wiersza po wierszu #include iostream . Wiersz ten wskazuje kompilatorowi, (cid:285)e kod u(cid:285)ywa namespace (przestrzeni nazw) o nazwie std. Dzi(cid:218)ki temu nie musimy wskazywa(cid:202) std:: przy ka(cid:285)dym wywo(cid:239)aniu instrukcji cin i cout. Kod jest prostszy ni(cid:285) wcze(cid:258)niej. 18 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ Definiowanie zmiennych przy u(cid:285)yciu podstawowych typów danych W poprzednich przyk(cid:239)adowych kodach skorzystali(cid:258)my ze zmiennej (s(cid:239)u(cid:285)(cid:200)cej do przechowy- wania elementu danych), aby móc przetwarza(cid:202) zawarte w niej dane w ramach ró(cid:285)nych dzia(cid:239)a(cid:241). W C++ zmiennym przypisujemy konkretne typy danych; zmienna mo(cid:285)e przechowywa(cid:202) wy- (cid:239)(cid:200)cznie dane tego typu, który zosta(cid:239) jej uprzednio przypisany. Oto lista fundamentalnych typów danych w C++; niektórych z nich u(cid:285)yli(cid:258)my ju(cid:285) w poprzednim przyk(cid:239)adzie: (cid:81) Typ logiczny (bool), który s(cid:239)u(cid:285)y do przechowywania wy(cid:239)(cid:200)cznie dwóch elementów danych warunkowych — true i false. (cid:81) Typ znakowy (char, wchar_t, char16_t i char32_t), który s(cid:239)u(cid:285)y do przechowywania pojedynczych znaków ASCII. (cid:81) Typ zmiennoprzecinkowy (float, double i long double), który s(cid:239)u(cid:285)y do przechowywania u(cid:239)amków dziesi(cid:218)tnych. (cid:81) Typ ca(cid:239)kowity (short, int, long i long long), który s(cid:239)u(cid:285)y do przechowywania liczb ca(cid:239)kowitych. (cid:81) Typ pusty (void), który jest w zasadzie s(cid:239)owem kluczowym, umieszczanym tam, gdzie w innym przypadku znalaz(cid:239)by si(cid:218) typ danych, aby wskaza(cid:202) brak danych. Zmienne mo(cid:285)na tworzy(cid:202) na dwa sposoby: w drodze definiowania lub inicjalizacji. Zdefiniowanie zmiennej powoduje utworzenie zmiennej bez okre(cid:258)lenia jej pocz(cid:200)tkowej warto(cid:258)ci. Inicjalizacja zmiennej powoduje utworzenie zmiennej i przypisanie jej pocz(cid:200)tkowej warto(cid:258)ci. Oto przyk(cid:239)ady definiowania zmiennych: int iVar; char32_t cVar; long long llVar; bool boVar; Oto przyk(cid:239)ady inicjalizacji zmiennych: int iVar = 100; char32_t cVar = a ; long long llVar = 9223372036854775805; bool boVar = true; Powy(cid:285)szy kod ukazuje inicjalizowanie zmiennych poprzez u(cid:285)ycie techniki inicjalizacji kopi(cid:200). Polega ona na przypisaniu warto(cid:258)ci zmiennej za pomoc(cid:200) znaku równo(cid:258)ci (=). Innym sposobem jest inicjalizacja bezpo(cid:258)rednia, która polega na u(cid:285)yciu nawiasów do przypisania warto(cid:258)ci zmien- nej. Oto przyk(cid:239)ady inicjalizacji zmiennych z wykorzystaniem tej drugiej techniki: int iVar(100); char32_t cVar( a ); long long llVar(9223372036854775805); bool boVar(true); 19 Poleć książkęKup książkę C++. Struktury danych i algorytmy Poza technikami inicjalizacji kopi(cid:200) i inicjalizacji bezpo(cid:258)redniej mo(cid:285)emy pos(cid:239)u(cid:285)y(cid:202) si(cid:218) ini- cjalizacj(cid:200) jednolit(cid:200), wykorzystuj(cid:200)c(cid:200) nawiasy klamrowe. Poni(cid:285)szy kod ukazuje technik(cid:218) inicjali- zacji nawiasowej: int iVar{100}; char32_t cVar{ a }; long long llVar{9223372036854775805}; bool boVar{true}; Nie mo(cid:285)emy zdefiniowa(cid:202) zmiennej przy u(cid:285)yciu typu danych void, na przyk(cid:239)ad void vVar, poniewa(cid:285) przy definiowaniu zmiennej musimy wybra(cid:202) taki typ danych, aby(cid:258)my mogli prze- chowa(cid:202) dane w zmiennej. Kiedy definiujemy zmienn(cid:200) jako void, oznacza to, (cid:285)e niczego nie zamierzamy w niej przechowywa(cid:202). Sterowanie przep(cid:239)ywem kodu Jak ju(cid:285) wspomnia(cid:239)em, wykonywanie programu C++ zaczyna si(cid:218) od funkcji main(), w której in- strukcje wykonywane s(cid:200) po kolei. Mo(cid:285)na jednak zmieni(cid:202) t(cid:218) kolejno(cid:258)(cid:202), u(cid:285)ywaj(cid:200)c instrukcji stero- wania przep(cid:239)ywem. W C++ istniej(cid:200) ró(cid:285)ne instrukcje sterowania, ale omówimy jedynie kilka wybranych, które s(cid:200) najcz(cid:218)(cid:258)ciej wykorzystywane w projektowaniu algorytmów. Instrukcja warunkowa Instrukcja warunkowa jest jednym z elementów, które mog(cid:200) zmieni(cid:202) przep(cid:239)yw programu. Kiedy taka instrukcja zostaje u(cid:285)yta, wykonywane s(cid:200) jedynie te wiersze, które przypisane s(cid:200) do warunku o warto(cid:258)ci true. Do wprowadzenia takiej instrukcji u(cid:285)ywamy s(cid:239)ów kluczowych if i else. Przekszta(cid:239)(cid:202)my kod pliku in_out.cpp tak, aby wykorzystywa(cid:239) instrukcj(cid:218) warunkow(cid:200). Program b(cid:218)dzie musia(cid:239) jedynie okre(cid:258)li(cid:202), czy wprowadzona liczba jest wi(cid:218)ksza od 100. Kod ten wygl(cid:200)da nast(cid:218)puj(cid:200)co: // If.cbp #include iostream using namespace std; int main () { int i; cout Podaj liczb(cid:218) ca(cid:239)kowit(cid:200): ; cin i; cout Podana warto(cid:258)(cid:202) jest ; if(i 100) cout wi(cid:218)ksza ni(cid:285) 100. ; else cout równa lub mniejsza ni(cid:285) 100. ; cout endl; return 0; } 20 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ Jak widzimy, para s(cid:239)ów kluczowych if i else okre(cid:258)la, czy wprowadzona liczba jest wi(cid:218)ksza od 100. Z powy(cid:285)szego kodu wykonana zostanie tylko jedna z instrukcji zawartych w instrukcji warunkowej — albo przypisana s(cid:239)owu kluczowemu if, albo s(cid:239)owu kluczowemu else. Po skompilowaniu i uruchomieniu powy(cid:285)szego kodu otrzymamy nast(cid:218)puj(cid:200)cy wynik w oknie konsoli: Z powy(cid:285)szego rysunku widzimy, (cid:285)e wiersz std::cout równa lub mniejsza ni(cid:285) 100. ; nie zosta(cid:239) wykonany, poniewa(cid:285) wprowadzono liczb(cid:218) wi(cid:218)ksz(cid:200) ni(cid:285) 100. Ponadto instrukcja if…else mo(cid:285)e sk(cid:239)ada(cid:202) si(cid:218) z wi(cid:218)cej ni(cid:285) dwóch instrukcji warunkowych. Mo(cid:285)emy zrefaktoryzowa(cid:202) powy(cid:285)szy kod, tak aby znalaz(cid:239)o si(cid:218) w nim wi(cid:218)cej instrukcji warunko- wych, w sposób nast(cid:218)puj(cid:200)cy: // If_ElseIf.cbp #include iostream using namespace std; int main () { int i; cout Podaj liczb(cid:218) ca(cid:239)kowit(cid:200): ; cin i; cout Podana warto(cid:258)(cid:202) jest ; if(i 100) cout wi(cid:218)ksza ni(cid:285) 100. ; else if(i 100) cout mniejsza ni(cid:285) 100. ; else cout równa 100. ; cout endl; return 0; } Innym s(cid:239)owem kluczowym wykorzystywanym w instrukcjach warunkowych jest switch. Zanim je omówimy, napiszmy prosty kalkulator pozwalaj(cid:200)cy na dodawanie, odejmowanie, mno(cid:285)enie i dzielenie. Najpierw u(cid:285)yjemy s(cid:239)owa kluczowego if…else. Kod powinien wygl(cid:200)da(cid:202) nast(cid:218)puj(cid:200)co: // If_ElseIf_2.cbp #include iostream 21 Poleć książkęKup książkę C++. Struktury danych i algorytmy using namespace std; int main () { int i, a, b; cout Dzia(cid:239)anie: endl; cout 1. Dodawanie endl; cout 2. Odejmowanie endl; cout 3. Mno(cid:285)enie endl; cout 4. Dzielenie endl; cout Podaj numer dzia(cid:239)ania: ; cin i; cout Podaj pierwsz(cid:200) liczb(cid:218): ; cin a; cout Podaj drug(cid:200) liczb(cid:218): ; cin b; cout Wynik ; if(i == 1) cout a + b to a + b; else if(i == 2) cout a - b to a - b; else if(i == 3) cout a * b to a * b; else if(i == 4) cout a / b to a / b; cout endl; return 0; } Jak wida(cid:202) w powy(cid:285)szym kodzie, mamy do wyboru cztery opcje, do których obs(cid:239)ugi u(cid:285)ywamy instrukcji warunkowej if…else. Po wykonaniu kodu otrzymamy nast(cid:218)puj(cid:200)cy wynik: 22 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ Mo(cid:285)emy te(cid:285) skorzysta(cid:202) ze s(cid:239)owa kluczowego switch. Po refaktoryzacji kod powinien wygl(cid:200)da(cid:202) nast(cid:218)puj(cid:200)co: // Switch.cbp #include iostream using namespace std; int main () { int i, a, b; cout Dzia(cid:239)anie: endl; cout 1. Dodawanie endl; cout 2. Odejmowanie endl; cout 3. Mno(cid:285)enie endl; cout 4. Dzielenie endl; cout Podaj numer dzia(cid:239)ania: ; cin i; cout Podaj pierwsz(cid:200) liczb(cid:218): ; cin a; cout Podaj drug(cid:200) liczb(cid:218): ; cin b; cout Wynik ; switch(i) { case 1: cout a + b to a + b; break; case 2: cout a - b to a - b; break; case 3: cout a * b to a * b; break; case 4: cout a / b to a / b; break; } cout endl; return 0; } Po uruchomieniu powy(cid:285)szego kodu otrzymamy taki sam wynik jak w przypadku If_ElseIf_2.cbp. 23 Poleć książkęKup książkę C++. Struktury danych i algorytmy P(cid:218)tle W C++ istnieje kilka instrukcji p(cid:218)tli: for, while i do…while. P(cid:218)tli for zazwyczaj u(cid:285)ywa si(cid:218) wtedy, kiedy wiadomo, ile iteracji ma nast(cid:200)pi(cid:202), podczas gdy while i do…while powtarzaj(cid:200) instruk- cje a(cid:285) do momentu, w którym po(cid:285)(cid:200)dany warunek zostanie spe(cid:239)niony. Za(cid:239)ó(cid:285)my, (cid:285)e chcemy wygenerowa(cid:202) dziesi(cid:218)(cid:202) losowych liczb mi(cid:218)dzy 0 a 100; wykorzystanie p(cid:218)tli for jest w tym przypadku najlepszym rozwi(cid:200)zaniem, poniewa(cid:285) wiemy dok(cid:239)adnie, ile liczb chcemy uzyska(cid:202). W tym celu mo(cid:285)emy napisa(cid:202) poni(cid:285)szy kod: // For.cbp #include iostream #include cstdlib #include ctime using namespace std; int GenerateRandomNumber(int min, int max) { // U(cid:298)ywa zmiennej statycznej ze wzgl(cid:266)du na wydajno(cid:286)(cid:252), // tak aby obliczy(cid:252) t(cid:266) warto(cid:286)(cid:252) tylko jednokrotnie. static const double fraction = 1.0 / (static_cast double (RAND_MAX) + 1.0); // Równo rozk(cid:225)ada losowe liczby w wybranym zakresie. return min + static_cast int ( (max - min + 1) * (rand() * fraction)); } int main() { // Okre(cid:286)la wst(cid:266)pny seed (ziarno) na podstawie zegara systemowego. srand(static_cast unsigned int (time(0))); // Zap(cid:266)tla dziesi(cid:266)ciokrotnie. for (int i=0; i 10; ++i) { cout GenerateRandomNumber(0, 100) ; } cout \n ; return 0; } W powy(cid:285)szym kodzie tworzymy inn(cid:200) funkcj(cid:218) poza main(), czyli GenerateRandomNumber(). Kod wywo(cid:239)uje funkcj(cid:218) dziesi(cid:218)ciokrotnie przy u(cid:285)yciu p(cid:218)tli for, tak jak wida(cid:202) w kodzie powy(cid:285)ej. Powinni(cid:258)my uzyska(cid:202) nast(cid:218)puj(cid:200)cy wynik: 24 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ Wró(cid:202)my do pozosta(cid:239)ych instrukcji p(cid:218)tli, o których wspomnia(cid:239)em, czyli while i do…while. Ich dzia(cid:239)anie jest do(cid:258)(cid:202) podobne. Ró(cid:285)nica polega na tym, (cid:285)e kiedy u(cid:285)ywamy p(cid:218)tli while, istnieje mo(cid:285)- liwo(cid:258)(cid:202), (cid:285)e instrukcja zawarta w p(cid:218)tli w ogóle nie zostanie wykonana, podczas gdy instrukcja z p(cid:218)tli do…while musi zosta(cid:202) wykonana przynajmniej raz. Stwórzmy teraz prost(cid:200) gr(cid:218) opart(cid:200) na p(cid:218)tlach. Komputer b(cid:218)dzie generowa(cid:239) liczb(cid:218) od 1 do 100, a zadaniem u(cid:285)ytkownika b(cid:218)dzie jej odgadni(cid:218)cie. Program b(cid:218)dzie podawa(cid:239) u(cid:285)ytkownikowi wskazówki tu(cid:285) po wprowadzeniu zgadywanej liczby, informuj(cid:200)c go o tym, czy podana liczba jest wi(cid:218)ksza, czy mniejsza od wylosowanej przez komputer. Gra b(cid:218)dzie si(cid:218) ko(cid:241)czy(cid:202), kiedy liczba podana przez u(cid:285)ytkownika b(cid:218)dzie równa tej, któr(cid:200) wygenerowa(cid:239) komputer. Kod wygl(cid:200)da nast(cid:218)puj(cid:200)co: // While.cbp #include iostream #include cstdlib #include ctime using namespace std; int GenerateRandomNumber(int min, int max) { // U(cid:298)ywa zmiennej statycznej ze wzgl(cid:266)du na wydajno(cid:286)(cid:252), // tak aby obliczy(cid:252) t(cid:266) warto(cid:286)(cid:252) tylko jednokrotnie. static const double fraction = 1.0 / (static_cast double (RAND_MAX) + 1.0); // Równo rozk(cid:225)ada losowe liczby w wybranym zakresie. return min + static_cast int ( (max - min + 1) * (rand() * fraction)); } int main() { // Okre(cid:286)la wst(cid:266)pny seed (ziarno) na podstawie zegara systemowego. srand(static_cast unsigned int (time(0))); // Komputer generuje losow(cid:261) liczb(cid:266) od 1 do 100. int computerNumber = GenerateRandomNumber(1, 100); // U(cid:298)ytkownik zgaduje liczb(cid:266) i j(cid:261) wprowadza. int userNumber; cout Podaj liczb(cid:218) od 1 do 100: ; cin userNumber; 25 Poleć książkęKup książkę C++. Struktury danych i algorytmy // Uruchamia p(cid:266)tl(cid:266) WHILE. while(userNumber != computerNumber) { cout userNumber jest ; if(userNumber computerNumber) cout wi(cid:218)ksz(cid:200) ; else cout mniejsz(cid:200) ; cout liczb(cid:200) od wybranej przez komputer endl; cout Wybierz inn(cid:200) liczb(cid:218): ; cin userNumber; } cout Gratulacje! Odgad(cid:239)e(cid:258) liczb(cid:218)! endl; return 0; } W powy(cid:285)szym kodzie widzimy, (cid:285)e dwie zmienne — computerNumber i userNumber — obs(cid:239)uguj(cid:200) porównywane liczby. Istnieje pewne prawdopodobie(cid:241)stwo, (cid:285)e warto(cid:258)(cid:202) computerNumber od razu oka(cid:285)e si(cid:218) równa warto(cid:258)ci userNumber. Je(cid:258)li tak b(cid:218)dzie, instrukcja zawarta w p(cid:218)tli while w ogóle nie zostanie wykonana. Przep(cid:239)yw programu wida(cid:202) na poni(cid:285)szym zrzucie z konsoli: W powy(cid:285)szym kodzie uda(cid:239)o nam si(cid:218) zaimplementowa(cid:202) p(cid:218)tl(cid:218) while. Cho(cid:202) przypomina ona p(cid:218)tl(cid:218) do…while, nie mo(cid:285)emy zrefaktoryzowa(cid:202) tego kodu, zast(cid:218)puj(cid:200)c while p(cid:218)tl(cid:200) do…while. Mo(cid:285)emy jednak napisa(cid:202) inn(cid:200) gr(cid:218), która tak(cid:200) p(cid:218)tl(cid:218) wykorzystuje. W tym przypadku to u(cid:285)yt- kownik b(cid:218)dzie wybiera(cid:239) liczb(cid:218), a zadaniem komputera b(cid:218)dzie odgadni(cid:218)cie jej. Kod powinien wygl(cid:200)da(cid:202) nast(cid:218)puj(cid:200)co: // Do-While.cbp #include iostream #include cstdlib #include ctime using namespace std; int GenerateRandomNumber(int min, int max) { // U(cid:298)ywa zmiennej statycznej ze wzgl(cid:266)du na wydajno(cid:286)(cid:252), // tak aby obliczy(cid:252) t(cid:266) warto(cid:286)(cid:252) tylko jednokrotnie. 26 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ static const double fraction = 1.0 / (static_cast double (RAND_MAX) + 1.0); // Równo rozk(cid:225)ada losowe liczby w wybranym zakresie. return min + static_cast int ( (max - min + 1) * (rand() * fraction)); } int main() { // Okre(cid:286)la wst(cid:266)pny seed (ziarno) na podstawie zegara systemowego. srand(static_cast unsigned int (time(0))); char userChar; int iMin = 1; int iMax = 100; int iGuess; // Interfejs gry. cout Podaj liczb(cid:218) od 1 do 100, ; cout a ja spróbuj(cid:218) j(cid:200) odgadn(cid:200)(cid:202). endl; cout Naci(cid:258)nij L i ENTER, je(cid:258)li podana przeze mnie liczba jest mniejsza od (cid:180)Twojej ; cout endl; cout Naci(cid:258)nij G i ENTER, je(cid:258)li podana przeze mnie liczba jest wi(cid:218)ksza od (cid:180)Twojej ; cout endl; cout Naci(cid:258)nij Y i ENTER, je(cid:258)li uda(cid:239)o mi si(cid:218) odgadn(cid:200)(cid:202) Twoj(cid:200) liczb(cid:218)! ; cout endl endl; // Uruchamia p(cid:266)tl(cid:266) DO-WHILE. do { iGuess = GenerateRandomNumber(iMin, iMax); cout Zgaduj(cid:218), (cid:285)e Twoja liczba to iGuess endl; cout Co Ty na to? ; cin userChar; if(userChar == L || userChar == l ) iMin = iGuess + 1; else if(userChar == G || userChar == g ) iMax = iGuess - 1; } while(userChar != Y userChar != y ); cout Odgad(cid:239)em Twoj(cid:200) liczb(cid:218)! endl; return 0; } Jak widzimy powy(cid:285)ej, program musi odgadn(cid:200)(cid:202) liczb(cid:218) wybran(cid:200) przez u(cid:285)ytkownika przynajm- niej raz, przy czym mo(cid:285)e mu si(cid:218) uda(cid:202) trafi(cid:202) za pierwszym podej(cid:258)ciem. Mo(cid:285)emy wobec tego u(cid:285)y(cid:202) tutaj p(cid:218)tli do…while. Po skompilowaniu i uruchomieniu kodu otrzymamy rezultat przypomi- naj(cid:200)cy to, co wida(cid:202) na poni(cid:285)szym rysunku: 27 Poleć książkęKup książkę C++. Struktury danych i algorytmy Na powy(cid:285)szym zrzucie wida(cid:202), (cid:285)e wybra(cid:239)em liczb(cid:218) 52. Program poda(cid:239) liczb(cid:218) 11. Poniewa(cid:285) by(cid:239)a ona mniejsza od mojej, program poda(cid:239) kolejn(cid:200), czyli 24. Poda(cid:239) on nast(cid:218)pnie kolejn(cid:200) liczb(cid:218) w oparciu o wskazówk(cid:218), a(cid:285) wreszcie wskaza(cid:239) w(cid:239)a(cid:258)ciw(cid:200) liczb(cid:218). Program zako(cid:241)czy wykonywanie p(cid:218)tli do…while, je(cid:258)li u(cid:285)ytkownik naci(cid:258)nie klawisz y, co widzimy w kodzie. Wykorzystanie zmiennych za po(cid:258)rednictwem zaawansowanych typów danych W poprzednim punkcie omówili(cid:258)my podstawowe typy danych. S(cid:239)u(cid:285)(cid:200) one do definiowania lub inicjalizowania zmiennych, aby sprawi(cid:202), by zmienne mog(cid:239)y przechowywa(cid:202) okre(cid:258)lone typy danych. Do definiowania zmiennych mo(cid:285)na jednak u(cid:285)ywa(cid:202) tak(cid:285)e innych typów danych: enum (wyliczeniowego) i struct (strukturalnego). Typ wyliczeniowy mo(cid:285)e mie(cid:202) ró(cid:285)ne warto(cid:258)ci, które s(cid:200) zdefiniowane jako sta(cid:239)e zwane enume- ratorami. S(cid:239)u(cid:285)y on do tworzenia kolekcji sta(cid:239)ych. Przyjmijmy, (cid:285)e chcemy napisa(cid:202) gr(cid:218) karcian(cid:200) w C++. Jak wiadomo, talia kart do gry sk(cid:239)ada si(cid:218) z 52 kart, dziel(cid:200)cych si(cid:218) na cztery kolory (trefl, karo, kier i pik), z czego ka(cid:285)dy kolor ma 13 kart. Tak(cid:200) tali(cid:218) mo(cid:285)emy przedstawi(cid:202) nast(cid:218)puj(cid:200)co: enum CardSuits { Club, Diamond, Heart, Spade }; enum CardElements { Ace, Two, Three, 28 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ Four, Five, Six, Seven, Eight, Nine, Ten, Jack, Queen, King }; Aby skorzysta(cid:202) z powy(cid:285)szych typów danych enum (CardSuits i CardElements), mo(cid:285)emy dokona(cid:202) inicjalizacji zmiennych w sposób nast(cid:218)puj(cid:200)cy: CardSuits suit = Club; CardElements element = Ace; W rzeczywisto(cid:258)ci zmienne wyliczeniowe zawsze zawieraj(cid:200) sta(cid:239)e liczby ca(cid:239)kowite. (cid:146)a(cid:241)cuch zna- ków podany dla elementu enum jest jedynie nazw(cid:200) sta(cid:239)ej. Pierwszy element ma warto(cid:258)(cid:202) 0, z tym (cid:285)e sami wprost definiujemy inn(cid:200) warto(cid:258)(cid:202). Kolejne elementy maj(cid:200) przyrostowe warto(cid:258)ci liczbowe wzgl(cid:218)dem pierwszego. Co za tym idzie, w powy(cid:285)szym przyk(cid:239)adzie CardSuits element Club ma warto(cid:258)(cid:202) 0, a Diamond, Heart i Spade maj(cid:200) odpowiednio warto(cid:258)ci 1, 2 i 3. Napiszmy teraz program, który b(cid:218)dzie generowa(cid:239) losow(cid:200) kart(cid:218). Mo(cid:285)emy wykorzysta(cid:202) funkcj(cid:218) GenerateRandomNumber() z poprzedniego kodu. Oto gotowy kod: // Enum.cbp #include iostream #include cstdlib #include ctime using namespace std; enum CardSuits { Club, Diamond, Heart, Spade }; enum CardElements { Ace, Two, Three, Four, Five, Six, Seven, Eight, Nine, Ten, 29 Poleć książkęKup książkę C++. Struktury danych i algorytmy Jack, Queen, King }; string GetSuitString(CardSuits suit) { string s; switch(suit) { case Club: s = trefl ; break; case Diamond: s = karo ; break; case Heart: s = kier ; break; case Spade: s = pik ; break; } return s; } string GetElementString(CardElements element) { string e; switch(element) { case Ace: e = as ; break; case Two: e = dwa ; break; case Three: e = trzy ; break; case Four: e = cztery ; break; case Five: e = pi(cid:218)(cid:202) ; break; case Six: e = sze(cid:258)(cid:202) ; break; case Seven: e = siedem ; break; 30 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ case Eight: e = osiem ; break; case Nine: e = dziewi(cid:218)(cid:202) ; break; case Ten: e = dziesi(cid:218)(cid:202) ; break; case Jack: e = walet ; break; case Queen: e = dama ; break; case King: e = król ; break; } return e; } int GenerateRandomNumber(int min, int max) { // U(cid:298)ywa zmiennej statycznej ze wzgl(cid:266)du na wydajno(cid:286)(cid:252), // tak aby obliczy(cid:252) t(cid:266) warto(cid:286)(cid:252) tylko jednokrotnie. static const double fraction = 1.0 / (static_cast double (RAND_MAX) + 1.0); // Równo rozk(cid:225)ada losowe liczby w wybranym zakresie. return min + static_cast int ( (max - min + 1) * (rand() * fraction)); } int main() { // Okre(cid:286)la wst(cid:266)pny seed (ziarno) na podstawie zegara systemowego. srand(static_cast unsigned int (time(0))); // Generuje losowy kolor i kart(cid:266). int iSuit = GenerateRandomNumber(0, 3); int iElement = GenerateRandomNumber(0, 12); CardSuits suit = static_cast CardSuits (iSuit); CardElements element = static_cast CardElements (iElement); cout Twoja karta to ; cout GetElementString(element); cout koloru GetSuitString(suit) endl; return 0; } 31 Poleć książkęKup książkę C++. Struktury danych i algorytmy W powy(cid:285)szym kodzie wida(cid:202), (cid:285)e mo(cid:285)emy wykorzysta(cid:202) dane enum przy u(cid:285)yciu warto(cid:258)ci liczby ca(cid:239)kowitej. Musimy jednak rzutowa(cid:202) warto(cid:258)(cid:202) int, tak aby by(cid:239)a kompatybilna z enum, u(cid:285)ywaj(cid:200)c static_cast , tak jak poni(cid:285)ej: int iSuit = GenerateRandomNumber(0, 3); int iElement = GenerateRandomNumber(0, 12); CardSuits suit = static_cast CardSuits (iSuit); CardElements element = static_cast CardElements (iElement); Po skompilowaniu i uruchomieniu kodu otrzymamy nast(cid:218)puj(cid:200)cy wynik: Inny zaawansowany typ danych w C++ to struct. Jest to zagregowany typ danych, który gru- puje wiele indywidualnych zmiennych. Zmienne suit i element z powy(cid:285)szego kodu mo(cid:285)na zgrupowa(cid:202) nast(cid:218)puj(cid:200)co: struct Cards { CardSuits suit; CardElements element; }; Gdyby(cid:258)my dodali powy(cid:285)sz(cid:200) zmienn(cid:200) struct do kodu Enum.cbp, musieliby(cid:258)my tak zrefaktoryzo- wa(cid:202) funkcj(cid:218) main(): int main() { // Okre(cid:286)la wst(cid:266)pny seed (ziarno) na podstawie zegara systemowego. srand(static_cast unsigned int (time(0))); Cards card; card.suit = static_cast CardSuits ( GenerateRandomNumber(0, 3)); card.element = static_cast CardElements ( GenerateRandomNumber(0, 12)); cout Twoja karta to ; cout GetElementString(element); cout koloru GetSuitString(suit) endl; return 0; } 32 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ Po uruchomieniu powy(cid:285)szego kodu (który znajdziesz w repozytorium pod nazw(cid:200) Struct.cbp) uzyskaliby(cid:258)my taki sam wynik jak w przypadku Enum.cbp. Tworzenie abstrakcyjnych typów danych Abstrakcyjny typ danych (ang. abstract data type — ADT) sk(cid:239)ada si(cid:218) z kolekcji danych i wyko- nywanych na nich operacji. ADT odnosi si(cid:218) jedynie do listy operacji, które mo(cid:285)na wykona(cid:202), ale nie do implementacji. Sama implementacja jest ukryta i w(cid:239)a(cid:258)nie z tego wzgl(cid:218)du mówi si(cid:218) o abstrakcyjno(cid:258)ci. Wyobra(cid:283)my sobie, (cid:285)e mamy odtwarzacz DVD, który jest dla nas (cid:283)ród(cid:239)em rozrywki w wolnym czasie. Odtwarzacz ma te(cid:285) pilota. Na pilocie znajduj(cid:200) si(cid:218) ró(cid:285)ne przyciski, s(cid:239)u(cid:285)(cid:200)ce do wysuwania p(cid:239)yty, rozpoczynania i wstrzymywania odtwarzania, regulowania poziomu g(cid:239)o(cid:258)no(cid:258)ci i tak dalej. Podobnie jak w przypadku ADT, nie mamy najmniejszego poj(cid:218)cia, w jaki sposób odtwarzacz podg(cid:239)a(cid:258)nia d(cid:283)wi(cid:218)k, kiedy naciskamy przycisk podg(cid:239)a(cid:258)niania. Wykonujemy jedynie operacj(cid:218) podg(cid:239)a(cid:258)niania, a odtwarzacz robi wszystko za nas — nie musimy zna(cid:202) implementacji tej operacji. W odniesieniu do przep(cid:239)ywu procesów musimy uwzgl(cid:218)dni(cid:202) abstrakcj(cid:218) implementacji ADT, ukrywanie informacji i enkapsulacj(cid:218). Oto obja(cid:258)nienia tych trzech technik: (cid:81) Abstrakcja polega na ukrywaniu szczegó(cid:239)ów implementacji operacji dost(cid:218)pnych w ADT. (cid:81) Ukrywanie informacji to ukrywanie danych, na które implementacja ma wp(cid:239)yw. (cid:81) Enkapsulacja polega na grupowaniu wszystkich podobnych danych i funkcji. Wykorzystanie klas C++ przy tworzeniu ADT zdefiniowanych przez u(cid:285)ytkownika Klasy s(cid:200) kontenerami zmiennych i operacji (metod), które wp(cid:239)ywaj(cid:200) na te zmienne. Jak ju(cid:285) wspomnia(cid:239)em, skoro ADT wykorzystuj(cid:200) techniki enkapsulacji do grupowania wszystkich podob- nych do siebie danych i funkcji, do grupowania mo(cid:285)na tak(cid:285)e u(cid:285)y(cid:202) klas. Dane i metody klas znajduj(cid:200) si(cid:218) w trzech sekcjach o ró(cid:285)nej kontroli dost(cid:218)pu: (cid:81) Publiczna. Dowolny u(cid:285)ytkownik klasy ma dost(cid:218)p do danych i metod. (cid:81) Chroniona. Dost(cid:218)p do danych i metod maj(cid:200) jedynie metody klasy, klasy pochodne i zaprzyja(cid:283)nione. (cid:81) Prywatna. Dost(cid:218)p do danych i metod maj(cid:200) jedynie metody klasy i klasy zaprzyja(cid:283)nione. Powró(cid:202)my teraz do definicji abstrakcji i ukrywania informacji. Abstrakcj(cid:218) mo(cid:285)emy zaimplemento- wa(cid:202) przy u(cid:285)yciu s(cid:239)ów kluczowych protected lub private, aby ukry(cid:202) metody poza klas(cid:200), a ukry- wanie informacji za pomoc(cid:200) tych samych s(cid:239)ów kluczowych, by ukry(cid:202) dane poza klas(cid:200). 33 Poleć książkęKup książkę C++. Struktury danych i algorytmy Napiszmy teraz prost(cid:200) klas(cid:218) Animal: class Animal { private: string m_name; public: void GiveName(string name) { m_name = name; } string GetName() { return m_name; } }; Jak wida(cid:202) na przyk(cid:239)adzie powy(cid:285)szego kodu, nie mo(cid:285)emy bezpo(cid:258)rednio uzyska(cid:202) dost(cid:218)pu do zmiennej m_name, poniewa(cid:285) okre(cid:258)lili(cid:258)my j(cid:200) jako private. Mamy jednak dwie metody public, przy u(cid:285)yciu których mo(cid:285)emy skorzysta(cid:202) ze zmiennej znajduj(cid:200)cej si(cid:218) wewn(cid:200)trz klasy. Metoda GiveName() modyfikuje warto(cid:258)(cid:202) m_name, a GetName() zwraca warto(cid:258)(cid:202) tej zmiennej. Poni(cid:285)ej widnieje kod, który wykorzystuje klas(cid:218) Animal w taki sposób. // Simple_Class.cbp #include iostream using namespace std; class Animal { private: string m_name; public: void GiveName(string name) { m_name = name; } string GetName() { return m_name; } }; int main() { Animal dog = Animal(); dog.GiveName( pies ); 34 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ cout Cze(cid:258)(cid:202)! Nazywam si(cid:218) dog.GetName() endl; return 0; } W powy(cid:285)szym kodzie utworzyli(cid:258)my zmienn(cid:200) o nazwie dog typu Animal. Zmienna dog ma wobec tego wszystkie opcje w(cid:239)a(cid:258)ciwe dla Animal, takie jak wywo(cid:239)ywanie metod GiveName() i GetName(). Poni(cid:285)ej widnieje okno z wynikiem, jaki powinni(cid:258)my otrzyma(cid:202) po skompilowaniu i uruchomie- niu kodu: Mo(cid:285)emy powiedzie(cid:202), (cid:285)e ADT Animal ma dwie funkcje: GiveName(string name) i GetName(). Po omówieniu prostych klas by(cid:202) mo(cid:285)e dostrzegasz podobie(cid:241)stwa mi(cid:218)dzy typem struct a klasami. W rzeczy samej, maj(cid:200) one podobne zachowania. Ró(cid:285)nice s(cid:200) jednak takie, (cid:285)e struktura ma do- my(cid:258)lne sk(cid:239)adowe public, podczas gdy klasy maj(cid:200) domy(cid:258)lne sk(cid:239)adowe private. Sam zalecam korzystanie z typu struct wy(cid:239)(cid:200)cznie do tworzenia struktur danych (jako (cid:285)e nie ma on (cid:285)adnych metod) i u(cid:285)ywanie klas do tworzenia ADT. Jak wida(cid:202) w powy(cid:285)szym kodzie, przypisujemy zmienn(cid:200) do instancji klasy Animal przy u(cid:285)yciu jej konstruktora: Animal dog = Animal(); Mo(cid:285)emy jednak inicjalizowa(cid:202) dane sk(cid:239)adowe klasy przy u(cid:285)yciu konstruktora klasy. Nazwa kon- struktora jest taka sama jak nazwa klasy. Zrefaktoryzujmy klas(cid:218) Animal tak, aby mia(cid:239)a w(cid:239)asny konstruktor. Kod powinien docelowo wygl(cid:200)da(cid:202) nast(cid:218)puj(cid:200)co: // Constructor.cbp #include iostream using namespace std; class Animal { private: string m_name; public: Animal(string name) : m_name(name) { } 35 Poleć książkęKup książkę C++. Struktury danych i algorytmy string GetName() { return m_name; } }; int main() { Animal dog = Animal( pies ); cout Cze(cid:258)(cid:202)! Nazywam si(cid:218) dog.GetName() endl; return 0; } Jak wida(cid:202), przy definiowaniu zmiennej dog inicjalizujemy tak(cid:285)e zmienn(cid:200) prywatn(cid:200) klasy m_name. Nie potrzebujemy ju(cid:285) metody GiveName() do przypisywania zmiennej private. Po skompilo- waniu i uruchomieniu powy(cid:285)szego kodu otrzymamy taki sam wynik jak wcze(cid:258)niej. Zmiennej dog przypisali(cid:258)my typ danych Animal. Mo(cid:285)emy jednak równie(cid:285) wywie(cid:258)(cid:202) now(cid:200) klas(cid:218) z klasy bazowej. Uzyskana w ten sposób klasa pochodna b(cid:218)dzie mia(cid:239)a zachowania klasy bazowej. Zrefaktoryzujmy klas(cid:218) Animal ponownie, dodaj(cid:200)c metod(cid:218) wirtualn(cid:200) MakeSound(). Metoda wirtu- alna to metoda, która nie ma jeszcze implementacji, lecz sam(cid:200) definicj(cid:218) (znan(cid:200) te(cid:285) jako interfejs). Klasa pochodna musi doda(cid:202) implementacj(cid:218) do metody wirtualnej przy u(cid:285)yciu s(cid:239)owa kluczowego override — w przeciwnym przypadku kompilator b(cid:218)dzie marudzi(cid:239). Po uzyskaniu nowej klasy Animal utworzymy klas(cid:218) o nazwie Dog, która b(cid:218)dzie pochodn(cid:200) Animal. Kod powinien wygl(cid:200)da(cid:202) nast(cid:218)puj(cid:200)co: // Derived_Class.cbp #include iostream using namespace std; class Animal { private: string m_name; public: Animal(string name) : m_name(name) { } // Interfejs, który trzeba zaimplementowa(cid:252) w klasie pochodnej. virtual string MakeSound() = 0; string GetName() { return m_name; } }; 36 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ class Dog : public Animal { public: // Przekazuje argumenty konstruktora. Dog(string name) : Animal(name) {} // Implementuje interfejs. string MakeSound() override { return hau, hau! ; } }; int main() { Dog dog = Dog( buldog ); cout dog.GetName() szczeka: ; cout dog.MakeSound() endl; return 0; } Mamy teraz dwie klasy: Animal (klasa bazowa) i Dog (klasa pochodna). Jak wida(cid:202), klasa Dog musi zaimplementowa(cid:202) metod(cid:218) MakeSound(), poniewa(cid:285) zosta(cid:239)a ona zdefiniowana jako metoda wir- tualna w klasie Animal. Instancja klasy Dog mo(cid:285)e te(cid:285) wywo(cid:239)a(cid:202) metod(cid:218) GetName(), nawet je(cid:258)li nie zosta(cid:239)a ona zaimplementowana w obr(cid:218)bie klasy Dog, jako (cid:285)e klasa pochodna dziedziczy wszystkie zachowania klasy bazowej. Po wykonaniu powy(cid:285)szego kodu powinni(cid:258)my otrzyma(cid:202) nast(cid:218)puj(cid:200)cy wynik: Tutaj znów mo(cid:285)emy powiedzie(cid:202), (cid:285)e ADT Dog ma dwie funkcje: GetName() i MakeSound(). Kolejnym wymogiem ADT jest zapewnienie mo(cid:285)liwo(cid:258)ci kontrolowania wszystkich operacji przypisywania, aby mo(cid:285)liwe by(cid:239)o unikni(cid:218)cie problemów z aliasingiem, wynikaj(cid:200)cych z p(cid:239)ytkiego kopiowania (niektóre sk(cid:239)adowe kopii mog(cid:200) mie(cid:202) referencje odnosz(cid:200)ce si(cid:218) do tych samych obiektów co orygina(cid:239)). W tym celu mo(cid:285)emy zastosowa(cid:202) technik(cid:218) przeci(cid:200)(cid:285)ania operatora przypi- sania. Zrefaktoryzujemy teraz klas(cid:218) Dog, tak aby uzyska(cid:239)a kopiuj(cid:200)cy operator przypisania. Kod powinien wygl(cid:200)da(cid:202) nast(cid:218)puj(cid:200)co: 37 Poleć książkęKup książkę C++. Struktury danych i algorytmy // Assignment_Operator_Overload.cbp #include iostream using namespace std; class Animal { protected: string m_name; public: Animal(string name) : m_name(name) { } // Interfejs, który trzeba zaimplementowa(cid:252) w klasie pochodnej. virtual string MakeSound() = 0; string GetName() { return m_name; } }; class Dog : public Animal { public: // Przekazuje argumenty konstruktora. Dog(string name) : Animal(name) {} // Przeci(cid:261)(cid:298)a kopiuj(cid:261)cy operator przypisania. void operator = (const Dog D) { m_name = D.m_name; } // Implementuje interfejs. string MakeSound() override { return hau, hau! ; } }; int main() { Dog dog = Dog( buldog ); cout dog.GetName() szczeka: ; cout dog.MakeSound() endl; Dog dog2 = dog; cout dog2.GetName() szczeka: ; cout dog2.MakeSound() endl; return 0; } 38 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ Dodali(cid:258)my kopiuj(cid:200)cy operator przypisania, który przeci(cid:200)(cid:285)a klas(cid:218) Dog. Poniewa(cid:285) jednak próbujemy uzyska(cid:202) dost(cid:218)p do zmiennej m_name w klasie bazowej z klasy pochodnej, musimy sprawi(cid:202), aby zmienna m_name by(cid:239)a protected, a nie private. Gdy kopiujemy dog na dog2 w instrukcji Dog dog2 = dog; funkcji main(), mo(cid:285)emy dopilnowa(cid:202), aby nie by(cid:239)a to kopia p(cid:239)ytka. Pos(cid:239)ugiwanie si(cid:218) szablonami Pobawmy si(cid:218) teraz szablonami. Szablony umo(cid:285)liwiaj(cid:200) funkcjom i klasom wspó(cid:239)prac(cid:218) z typami generycznymi. Dzi(cid:218)ki nim funkcje i klasy mog(cid:200) operowa(cid:202) na wielu ró(cid:285)nych typach danych i nie trzeba pisa(cid:202) ich ponownie na potrzeby ka(cid:285)dego z typów. Przy u(cid:285)yciu szablonu mo(cid:285)emy tworzy(cid:202) ró(cid:285)ne typy danych, które omówimy w dalszej cz(cid:218)(cid:258)ci tej ksi(cid:200)(cid:285)ki. Szablony funkcji Za(cid:239)ó(cid:285)my, (cid:285)e mamy inn(cid:200) klas(cid:218) pochodn(cid:200) od klasy Animal — na przyk(cid:239)ad Cat. Stworzymy teraz funkcj(cid:218), która wywo(cid:239)uje metody GetName() i MakeSound() dla instancji Dog i Cat. Zamiast tworzy(cid:202) dwie osobne funkcje, mo(cid:285)emy skorzysta(cid:202) z szablonu nast(cid:218)puj(cid:200)co: // Function_Templates.cbp #include iostream using namespace std; class Animal { protected: string m_name; public: Animal(string name) : m_name(name) { } // Interfejs, który trzeba zaimplementowa(cid:252) w klasie pochodnej. virtual string MakeSound() = 0; string GetName() { return m_name; } }; class Dog : public Animal { public: // Przekazuje argumenty konstruktora. Dog(string name) : Animal(name) {} // Przeci(cid:261)(cid:298)a kopiuj(cid:261)cy operator przypisania. void operator = (const Dog D) 39 Poleć książkęKup książkę C++. Struktury danych i algorytmy { m_name = D.m_name; } // Implementuje interfejs. string MakeSound() override { return hau, hau! ; } }; class Cat : public Animal { public: // Przekazywanie argumentów konstruktora. Cat(string name) : Animal(name) {} // Przeci(cid:261)(cid:298)enie kopiuj(cid:261)cego operatora przypisania. void operator = (const Cat D) { m_name = D.m_name; } // Implementacja interfejsu. string MakeSound() override { return miau, miau! ; } }; template typename T void GetNameAndMakeSound(T theAnimal) { cout theAnimal.GetName() robi ; cout theAnimal.MakeSound() endl; } int main() { Dog dog = Dog( buldog ); GetNameAndMakeSound(dog); Cat cat = Cat( pers ); GetNameAndMakeSound(cat); return 0; } Widzimy, (cid:285)e funkcji GetNameAndMakeSound() mo(cid:285)emy przekaza(cid:202) typy danych Dog i Cat, poniewa(cid:285) zdefiniowali(cid:258)my szablon typename T przed zdefiniowaniem funkcji. W C++ typename jest s(cid:239)owem kluczowym s(cid:239)u(cid:285)(cid:200)cym do tworzenia szablonów. S(cid:239)owo kluczowe wskazuje, (cid:285)e symbol w definicji lub deklaracji szablonu jest typem (w tym przyk(cid:239)adzie symbol to T). W wyniku tego funkcja staje si(cid:218) generyczna i mo(cid:285)e przyjmowa(cid:202) ró(cid:285)ne typy danych. Po skompilowaniu i wykonaniu powy(cid:285)szego kodu powinni(cid:258)my otrzyma(cid:202) nast(cid:218)puj(cid:200)cy wynik w oknie konsoli: 40 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ Nale(cid:285)y si(cid:218) koniecznie upewni(cid:202), czy typ danych przekazywany funkcji generycznej ma mo(cid:285)li- wo(cid:258)(cid:202) wywo(cid:239)ania wszystkich jej operacji. Kompilator z powodzeniem skompiluje kod, nawet je(cid:258)li przekazany typ danych nie obs(cid:239)uguje oczekiwanej operacji. W powy(cid:285)szym przyk(cid:239)adzie sza- blonu funkcji nale(cid:285)y przekaza(cid:202) typ danych, który jest instancj(cid:200) klasy Animal, mo(cid:285)e to by(cid:202) wi(cid:218)c albo instancja klasy Animal, albo instancja klasy pochodnej. Szablony klas Podobnie jak szablon funkcji, szablon klasy s(cid:239)u(cid:285)y do tworzenia generycznych klas, które przyj- muj(cid:200) ró(cid:285)ne typy danych. Zrefaktoryzujmy kod Function_Template.cbp, dodaj(cid:200)c do niego nowy szablon klasy. Kod powinien wygl(cid:200)da(cid:202) nast(cid:218)puj(cid:200)co: // Class_Templates.cbp #include iostream using namespace std; class Animal { protected: string m_name; public: Animal(string name) : m_name(name) { } // Interfejs, który trzeba zaimplementowa(cid:252) w klasie pochodnej. virtual string MakeSound() = 0; string GetName() { return m_name; } }; class Dog : public Animal { public: // Przekazuje argumenty konstruktora. Dog(string name) : Animal(name) {} 41 Poleć książkęKup książkę C++. Struktury danych i algorytmy // Przeci(cid:261)(cid:298)a kopiuj(cid:261)cy operator przypisania. void operator = (const Dog D) { m_name = D.m_name; } // Implementuje interfejs. string MakeSound() override { return hau, hau! ; } }; class Cat : public Animal { public: // Przekazuje argumenty konstruktora. Cat(string name) : Animal(name) {} // Przeci(cid:261)(cid:298)a kopiuj(cid:261)cy operator przypisania. void operator = (const Cat D) { m_name = D.m_name; } // Implementuje interfejs. string MakeSound() override { return miau, miau! ; } }; template typename I void GetNameAndMakeSound(T theAnimal) { cout theAnimal.GetName() robi ; cout theAnimal.MakeSound() endl; } template typename T class AnimalTemplate { private: T m_animal; public: AnimalTemplate(T animal) : m_animal(animal) {} void GetNameAndMakeSound(T theAnimal) { cout m_animal.GetName() robi ; cout m_animal.MakeSound() endl; } }; 42 Poleć książkęKup książkę Rozdzia(cid:225) 1. • Struktury danych i algorytmy w C++ int main() { Dog dog = Dog( buldog ); AnimalTemplate Dog dogTemplate(dog); dogTemplate.GetNameAndMakeSound(dog); Cat cat = Cat( pers ); AnimalTemplate Cat catTemplate(cat); catTemplate.GetNameAndMakeSound(cat); return 0; } Utworzyli(cid:258)my now(cid:200) klas(cid:218) o nazwie AnimalTemplate. Jest to szablon klasy, którego mo(cid:285)na u(cid:285)y(cid:202) z dowolnym typem danych. Musimy jednak zdefiniowa(cid:202) typ danych w nawiasie ostrok(cid:200)tnym, kiedy korzystamy z instancji dogTemplate i catTemplate. Po skompilowaniu i uruchomieniu kodu otrzymamy taki sam wynik jak w przypadku kodu Function_Template.cbp. Biblioteka standardowych szablonów Programowanie w C++ wi(cid:200)(cid:285)e si(cid:218) z korzystaniem z innej przydatnej funkcji, zwi(cid:200)zanej ze sto- sowaniem szablonów klas — biblioteki standardowych szablonów (ang. Standard Template Library — STL). Jest to zbiór szablonów klas zapewniaj(cid:200)cych wszystkie funkcje, których u(cid:285)ywa si(cid:218) powszechnie przy operowaniu na ró(cid:285)nych strukturach danych. Na STL sk(cid:239)adaj(cid:200) si(cid:218) cztery komponenty: algorytmy, kontenery, iteratory i funkcje. Przyjrzyjmy si(cid:218) im bli(cid:285)ej. Algorytmy wykorzystywane s(cid:200) na zakresach elementów i s(cid:239)u(cid:285)(cid:200) m.in. do sortowania i wyszu- kiwania. Algorytm sortuj(cid:200)cy s(cid:239)u(cid:285)y do porz(cid:200)dkowania elementów w kolejno(cid:258)ci rosn(cid:200)cej lub malej(cid:200)cej. Algorytm wyszukiwania wykorzystuje si(cid:218) do odnajdowania konkretnych warto(cid:258)ci w zbiorach elementów. Kontenery s(cid:239)u(cid:285)(cid:200) do przechowywania obiektów i danych. Standardowym kontenerem, b(cid:218)d(cid:200)cym w powszechnym u(cid:285)yciu, jest wektor. Wektor przypomina tablic(cid:218), ale ma mo(cid:285)liwo(cid:258)(cid:202) automatycz- nej zmiany w(cid:239)asnego rozmiaru, kiedy element zostaje do niego dodany lub z niego usuni(cid:218)ty. Iteratory s(cid:239)u(cid:285)(cid:200) do pracy z sekwencjami warto(cid:258)ci. Ka(cid:285)dy kontener ma w(cid:239)asny iterator. Kontener wektora oferuje na przyk(cid:239)ad funkcje begin(), end(), rbegin() i rend(). Funkcje biblioteki s(cid:239)u(cid:285)(cid:200) do przeci(cid:200)(cid:285)ania istniej(cid:200)cych funkcji. Instancja tego komponentu to funk- tor, czy te(cid:285) obiekt funkcji. Funktor jest wska(cid:283)nikiem funkcji, parametryzuje istniej(cid:200)c(cid:200) ju(cid:285) funkcj(cid:218). W tym punkcie nie napiszemy (cid:285)adnego kodu przyk(cid:239)adowego, jako (cid:285)e chc(cid:218) jedynie zwróci(cid:202) Twoj(cid:200) uwag(cid:218) na to, (cid:285)e STL — na szcz(cid:218)(cid:258)cie — istnieje i jest przydatn(cid:200) bibliotek(cid:200) C++. Temat STL omówimy szerzej w kolejnych rozdzia(cid:239)ach przy obja(cid:258)nianiu tworzenia struktur danych. 43 Poleć książkęKup książkę C++. Struktury danych i algorytmy Analiza algorytmów Dobry algorytm musi mie(cid:202) jak najwi(cid:218)ksz(cid:200) wydajno(cid:258)(cid:202). W tym podrozdziale omówimy temat ana- lizy z(cid:239)o(cid:285)ono(cid:258)ci czasowej podstawowych
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

C++. Struktury danych i algorytmy
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ą: