Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00295 016525 17207110 na godz. na dobę w sumie
Myśl jak programista. Techniki kreatywnego rozwiązywania problemów - książka
Myśl jak programista. Techniki kreatywnego rozwiązywania problemów - książka
Autor: Liczba stron: 280
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-246-7284-4 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> inne - programowanie
Porównaj ceny (książka, ebook, audiobook).

Znajdź wyjście z najtrudniejszych sytuacji!

Nauka programowania to tak naprawdę nauka sposobu myślenia. Jako programista musisz biegle analizować problemy, dzielić je na części oraz starać się je rozwiązać w optymalny sposób. Składnia języka i środowisko programistyczne to tylko podstawowe narzędzia, których obsługi nauczyć się może każdy. Jednak nie każdy potrafi myśleć jak programista.

Dzięki tej książce masz szansę zostać profesjonalistą! W trakcie lektury poznasz najlepsze sposoby rozwiązywania problemów, opanujesz rekurencję i przekonasz się, że wcale nie jest ona taka straszna. Zobaczysz również, jak tworzyć kod nadający się do ponownego użycia, i opanujesz zagadnienia z obszaru programowania obiektowego. Przykłady w tej książce zostały napisane w języku C++, ale nie stanowi to bariery, żeby przenieść te idee na inne języki programowania. Warto poświęcić tej książce parę wieczorów i zmienić swój sposób patrzenia na programowanie!

Poznaj:

Opanuj sztukę myślenia jak programista!

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

Darmowy fragment publikacji:

Tytuł oryginału: Think Like a Programmer: An Introduction to Creative Problem Solving Tłumaczenie: Jacek Janusz ISBN: 978-83-246-7284-4 Original edition copyright © 2012 by V. Anton Spraul. All rights reserved. Published by arrangement with No Starch Press, Inc. Polish edition copyright © 2013 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 Wydawnictwo HELION 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 Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Wydawnictwo HELION 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/myprog Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. Pliki z przykładami omawianymi w książce można znaleźć pod adresem: ftp://ftp.helion.pl/przyklady/myprog.zip Printed in Poland. • Kup książkę • Poleć książkę • Oceń książkę • Księgarnia internetowa • Lubię to! » Nasza społeczność Spis treĂci PODZI}KOWANIA ..................................................................................... 7 WST}P ........................................................................................................ 9 O ksiÈĝce ................................................................................................................................11 Wymagania wstÚpne ..........................................................................................................11 Wybrane zagadnienia .........................................................................................................12 Styl programowania ...........................................................................................................12 mwiczenia ...........................................................................................................................12 Dlaczego C++? .................................................................................................................13 1 STRATEGIE ROZWIkZYWANIA PROBLEMÓW ......................................... 15 Klasyczne ïamigïówki .............................................................................................................17 Lis, gÚĂ i kukurydza ............................................................................................................17 ’amigïówki z przesuwanymi elementami ..........................................................................22 Sudoku ...............................................................................................................................26 Zamek Quarrasi .................................................................................................................30 Ogólne techniki rozwiÈzywania problemów ..........................................................................32 Miej zawsze jakiĂ plan ........................................................................................................32 Ponownie zaprezentuj problem .........................................................................................33 Podziel problem .................................................................................................................34 Rozpocznij z wiedzÈ, którÈ posiadasz ................................................................................35 UproĂÊ problem .................................................................................................................36 Szukaj analogii ....................................................................................................................37 Eksperymentuj ...................................................................................................................38 Nie popadaj we frustracjÚ ..................................................................................................38 mwiczenia ...............................................................................................................................40 Poleć książkęKup książkę 2 PRAWDZIWE ’AMIG’ÓWKI ..................................................................... 41 Elementy jÚzyka C++ wykorzystywane w tym rozdziale .................................................... 42 Tworzenie wzorów na wyjĂciu ............................................................................................. 42 Przetwarzanie danych wejĂciowych ...................................................................................... 48 Analiza problemu ............................................................................................................... 49 ’Èczenie wszystkich elementów w caïoĂÊ ......................................................................... 58 ¥ledzenie stanu ...................................................................................................................... 60 Podsumowanie ...................................................................................................................... 73 mwiczenia .............................................................................................................................. 74 3 ROZWIkZYWANIE PROBLEMÓW ZA POMOCk TABLIC .......................... 77 Podstawowe informacje o tablicach ...................................................................................... 78 Przechowywanie danych ................................................................................................... 79 Kopiowanie ........................................................................................................................ 79 Odczytywanie i przeszukiwanie ........................................................................................ 80 Sortowanie ........................................................................................................................ 81 Obliczenia statystyczne ..................................................................................................... 84 RozwiÈzywanie problemów za pomocÈ tablic ....................................................................... 85 Optymalizacja .................................................................................................................... 89 Tablice ze staïymi wartoĂciami .............................................................................................. 91 Tablice z wartoĂciami nieskalarnymi ..................................................................................... 94 Tablice wielowymiarowe ...................................................................................................... 96 Kiedy naleĝy uĝywaÊ tablic .................................................................................................... 99 mwiczenia ............................................................................................................................ 104 4 ROZWIkZYWANIE PROBLEMÓW ZA POMOCk WSKA½NIKÓW I PAMI}CI DYNAMICZNEJ ....................... 107 Podstawowe informacje o wskaěnikach .............................................................................. 108 KorzyĂci z uĝywania wskaěników ........................................................................................ 109 Struktury danych o wielkoĂci definiowanej w trakcie dziaïania programu ...................... 109 Struktury danych o zmiennych rozmiarach ..................................................................... 110 Wspóïdzielenie pamiÚci ................................................................................................... 110 Kiedy naleĝy uĝywaÊ wskaěników? ...................................................................................... 111 PamiÚÊ ma znaczenie ........................................................................................................... 112 Stos i sterta ...................................................................................................................... 113 Rozmiar pamiÚci .............................................................................................................. 116 Czas ĝycia ........................................................................................................................ 118 RozwiÈzywanie problemów za pomocÈ wskaěników ......................................................... 119 ’añcuchy o zmiennej dïugoĂci ......................................................................................... 119 Listy powiÈzane ............................................................................................................... 130 Wnioski i nastÚpne dziaïania ................................................................................................ 139 mwiczenia ............................................................................................................................ 139 4 S p i s t r e Ă c i Poleć książkęKup książkę 5 ROZWIkZYWANIE PROBLEMÓW ZA POMOCk KLAS ............................ 143 PrzeglÈd podstawowych informacji o klasach ......................................................................144 Cele uĝycia klas ....................................................................................................................146 Enkapsulacja .....................................................................................................................146 Ponowne uĝycie kodu ......................................................................................................147 Dzielenie problemu ..........................................................................................................147 Hermetyzacja ...................................................................................................................148 CzytelnoĂÊ ........................................................................................................................150 WyrazistoĂÊ ......................................................................................................................150 Tworzenie przykïadowej klasy .............................................................................................151 Podstawowy schemat klasy ..............................................................................................152 Metody wspierajÈce .........................................................................................................156 Klasy z danymi dynamicznymi ..............................................................................................160 Dodawanie wÚzïa .............................................................................................................162 Reorganizacja listy ............................................................................................................165 Destruktor .......................................................................................................................169 Kopiowanie gïÚbokie ........................................................................................................170 Obraz caïoĂci dla klas z pamiÚciÈ dynamicznÈ .................................................................175 BïÚdy, jakich naleĝy unikaÊ ...................................................................................................176 Klasa fikcyjna ....................................................................................................................176 Jednozadaniowce .............................................................................................................177 mwiczenia .............................................................................................................................178 6 ROZWIkZYWANIE PROBLEMÓW ZA POMOCk REKURENCJI ................ 181 PrzeglÈd podstawowych informacji o rekurencji .................................................................182 Rekurencja nieogonowa i ogonowa .....................................................................................182 Wielki Pomysï Rekurencyjny ................................................................................................191 CzÚsto popeïniane bïÚdy ......................................................................................................194 Zbyt wiele parametrów ...................................................................................................195 Zmienne globalne .............................................................................................................196 Uĝywanie rekurencji w dynamicznych strukturach danych .................................................198 Rekurencja i listy powiÈzane ............................................................................................198 Rekurencja i drzewa binarne ............................................................................................201 Funkcje opakowujÈce ...........................................................................................................204 Kiedy naleĝy wybieraÊ rekurencjÚ? ......................................................................................207 Argumenty przeciwko rekurencji ....................................................................................207 mwiczenia .............................................................................................................................211 7 ROZWIkZYWANIE PROBLEMÓW ZA POMOCk PONOWNEGO WYKORZYSTANIA KODU ......................... 213 Poprawne i niewïaĂciwe wykorzystanie kodu ......................................................................214 PrzeglÈd podstawowych informacji o komponentach .........................................................215 S p i s t r e Ă c i 5 Poleć książkęKup książkę Blok kodu ........................................................................................................................ 215 Algorytmy ........................................................................................................................ 216 Wzorce ............................................................................................................................ 216 Abstrakcyjne typy danych ................................................................................................ 217 Biblioteki .......................................................................................................................... 218 Zdobywanie wiedzy o komponentach ................................................................................ 219 Eksploracyjne zdobywanie wiedzy .................................................................................. 219 Zdobywanie wiedzy w razie potrzeby ............................................................................ 223 Wybór typu komponentu .................................................................................................... 232 Wybór komponentu w praktyce ..................................................................................... 234 Porównanie wyników ...................................................................................................... 238 mwiczenia ............................................................................................................................ 239 8 MY¥LENIE JAK PROGRAMISTA ............................................................. 241 Tworzenie wïasnego planu gïównego ................................................................................. 242 UwzglÚdnienie mocnych i sïabych stron ......................................................................... 242 Budowanie planu gïównego ............................................................................................. 248 RozwiÈzywanie kaĝdego problemu ..................................................................................... 250 Opracowywanie metody oszukiwania ............................................................................. 252 Wymagane podzadania dla metody oszukiwania w grze wisielec ................................... 254 WstÚpny projekt .............................................................................................................. 256 Kodowanie wstÚpne ........................................................................................................ 257 Analiza wstÚpnych wyników ............................................................................................ 266 Sztuka rozwiÈzywania problemów .................................................................................. 267 Zdobywanie nowych umiejÚtnoĂci programistycznych ....................................................... 268 Nowe jÚzyki .................................................................................................................... 269 Zdobywanie nowych umiejÚtnoĂci w jÚzyku, który juĝ znasz ......................................... 271 Nowe biblioteki ............................................................................................................... 272 Bierz udziaï w szkoleniach ............................................................................................... 273 Podsumowanie .................................................................................................................... 274 mwiczenia ............................................................................................................................ 275 SKOROWIDZ .......................................................................................... 276 6 S p i s t r e Ă c i Poleć książkęKup książkę 4 RozwiÈzywanie problemów za pomocÈ wskaěników i pamiÚci dynamicznej W TYM ROZDZIALE NAUCZYMY SI} ROZWIkZYWANIA PROBLEMÓW ZA POMOCk WSKA½NIKÓW I PAMI}CI DYNAMICZNEJ, CO POZWOLI NAM NA PISANIE UNIWER- SALNYCH PROGRAMÓW ZARZkDZAJkCYCH DANYMI, KTÓRYCH ROZMIARY nie sÈ znane przed uruchomieniem kodu. Wskaěniki i dynamiczne przydzielanie pamiÚci sÈ programowaniem ekstremalnym. Gdy piszesz programy, które rezerwujÈ pamiÚÊ w locie, przypisujÈ jÈ do przydatnych struktur, a nastÚpnie przed zakoñczeniem dziaïania sprzÈtajÈ po sobie w taki sposób, by nic nie pozostaïo, nie jesteĂ po prostu kimĂ, kto potrafi trochÚ kodowaÊ — jesteĂ pro- gramistÈ. Poniewaĝ wskaěniki sÈ trudnym zagadnieniem, a wiele popularnych jÚzyków programowania, na przykïad Java, obywa siÚ bez nich, niektórzy poczÈtkujÈcy programiĂci starajÈ siÚ przekonaÊ samych siebie, ĝe ten obszar wiedzy mogÈ zu- peïnie pominÈÊ. Jest to bïÈd. Wskaěniki i niebezpoĂredni dostÚp do pamiÚci bÚdÈ Poleć książkęKup książkę zawsze uĝywane w mechanizmach jÚzyków wysokiego poziomu. Aby wiÚc rze- czywiĂcie myĂleÊ jak programista, musisz umieÊ swobodnie poruszaÊ siÚ wĂród wskaěników oraz problemów wymagajÈcych ich uĝycia. Zanim jednak zajmiemy siÚ rozwiÈzywaniem problemów ze wskaěnikami, dokïadnie przeanalizujemy wszystkie pierwszo- i drugoplanowe aspekty zwiÈzane z ich dziaïaniem. DziÚki temu osiÈgniemy dwie korzyĂci. Po pierwsze, zdobyta wiedza pozwoli wykorzystaÊ wskaěniki w najbardziej wydajny sposób. Po dru- gie, poprzez ujawnienie tajemnic zwiÈzanych ze wskaěnikami bÚdziemy mogli ich bezpiecznie uĝywaÊ. Podstawowe informacje o wskaěnikach Podobnie jak w przypadku zagadnieñ omawianych w poprzednich rozdziaïach, równieĝ tutaj zakïadam, ĝe masz juĝ pewnÈ podstawowÈ wiedzÚ o wskaěnikach. Aby siÚ jednak upewniÊ, ĝe „nadajemy na tej samej fali”, przedstawiÚ poniĝej krótki przeglÈd ich moĝliwoĂci. Wskaěniki w jÚzyku C++ sÈ reprezentowane przez znak gwiazdki (*). W za- leĝnoĂci od kontekstu gwiazdka oznacza deklaracjÚ wskaěnika lub pamiÚÊ, do któ- rej siÚ on odwoïuje, a nie sam wskaěnik. Aby zadeklarowaÊ wskaěnik, umiesz- czamy znak gwiazdki miÚdzy nazwÈ typu i identyfikatorem: int *intPointer; Powyĝszy kod zawiera deklaracjÚ zmiennej intPointer, bÚdÈcej wskaěnikiem do typu int. ZwróÊ uwagÚ na to, ĝe gwiazdka ïÈczy siÚ z identyfikatorem, a nie typem. W poniĝszej deklaracji zmienna variable1 jest wskaěnikiem do typu int, a variable2 po prostu zmiennÈ typu int: int *variable1, variable2; Znak przed zmiennÈ dziaïa jak operator adresu. Za pomocÈ poniĝszej in- strukcji moglibyĂmy wiÚc przypisaÊ adres zmiennej variable2 do variable1: variable1 = variable2; Moĝemy takĝe bezpoĂrednio przypisaÊ wartoĂÊ jednej zmiennej wskaěniko- wej do drugiej: intPointer = variable1; 108 R o z d z i a ï 4 Poleć książkęKup książkę ByÊ moĝe najwaĝniejsze jest to, ĝe w trakcie dziaïania programu moĝemy przydzielaÊ pamiÚÊ, która jest dostÚpna jedynie poprzez wskaěnik. Jest to moĝ- liwe przy uĝyciu operatora new: double *doublePointer = new double; DostÚp do pamiÚci wskazywanej przez wskaěnik jest zwany wyïuskiwaniem (dereferencjÈ). Uzyskuje siÚ go za pomocÈ gwiazdki umieszczonej po lewej stro- nie identyfikatora wskaěnika. Jak juĝ wspomniaïem, jest to ten sam sposób umiesz- czania znaku gwiazdki, jaki stosuje siÚ podczas deklaracji wskaěnika, jednakĝe inny kontekst sprawia, ĝe obie operacje róĝniÈ siÚ od siebie. Oto przykïad: ™ *doublePointer = 35.4; š double localDouble = *doublePointer; Do obszaru pamiÚci typu double przydzielonego we wczeĂniejszym przykïadzie przypisujemy wartoĂÊ ™, a nastÚpnie kopiujemy jÈ do zmiennej localDouble š. Aby zwolniÊ niepotrzebnÈ pamiÚÊ przydzielonÈ za pomocÈ operatora new, stosujemy sïowo kluczowe delete: delete doublePointer; Sposób dziaïania tego procesu zostaï dokïadnie przedstawiony w dalszej czÚĂci rozdziaïu, w podrozdziale „PamiÚÊ ma znaczenie”. KorzyĂci z uĝywania wskaěników Wskaěniki dajÈ moĝliwoĂci niedostÚpne przy uĝyciu statycznego przydzielania pamiÚci, a takĝe pozwalajÈ na jej efektywne wykorzystanie. Trzy gïówne korzyĂci wynikajÈce z uĝywania wskaěników sÈ nastÚpujÈce: „ Struktury danych o wielkoĂci definiowanej w trakcie dziaïania programu. „ Struktury danych o zmiennych rozmiarach. „ Wspóïdzielenie pamiÚci. Przyjrzyjmy siÚ kaĝdej z nich bardziej szczegóïowo. Struktury danych o wielkoĂci definiowanej w trakcie dziaïania programu DziÚki uĝyciu wskaěników moĝemy utworzyÊ tablicÚ o rozmiarze ustalonym w trakcie dziaïania programu, a nie definiowaÊ go jeszcze przed kompilacjÈ aplikacji. DziÚki temu unikamy sytuacji ewentualnego braku miejsca w tablicy R o z w i È z y wa n i e p r ob l e m ó w z a p o m o c È w s k a ě n i k ó w i pa m i Ú c i d y n a m i c z n e j 109 Poleć książkęKup książkę oraz definiowania jej zbyt duĝego rozmiaru, a przez to najczÚĂciej niewykorzy- stania wiÚkszoĂci przydzielonej pamiÚci. Z dynamicznym ustalaniem rozmiaru struktury danych mieliĂmy juĝ do czynienia w rozdziale 3., w podrozdziale „Kiedy naleĝy uĝywaÊ tablic”. Ta idea zostanie równieĝ wykorzystana w dalszej czÚĂci niniejszego rozdziaïu, w podrozdziale „’añcuchy o zmiennej dïugoĂci”. Struktury danych o zmiennych rozmiarach Moĝemy takĝe stworzyÊ wskaěnikowe struktury danych, które w razie koniecz- noĂci powiÚkszajÈ siÚ lub zmniejszajÈ w trakcie dziaïania programu. NajprostszÈ strukturÈ danych o zmiennych rozmiarach jest lista powiÈzana, o której juĝ wspo- minaliĂmy. Do jej danych moĝna uzyskaÊ dostÚp jedynie w sposób sekwencyjny. Rezerwuje ona jednak tylko tyle miejsca, ile wynosi rozmiar samych danych, bez ĝadnego marnowania pamiÚci. Jak zobaczysz w dalszej czÚĂci ksiÈĝki, inne, bardziej zïoĝone wskaěnikowe struktury danych zawierajÈ opcje porzÈdkowania i „profile”, które umoĝliwiajÈ lepsze zarzÈdzanie powiÈzaniami miÚdzy zapa- miÚtanymi danymi, niĝ ma to miejsce w przypadku tablic. Z tego powodu, mimo ĝe tablica umoĝliwia uzyskanie peïnego dostÚpu swobodnego, operacja wyszu- kiwania (podczas której w strukturze wyszukujemy element najlepiej speïniajÈ- cy okreĂlone kryterium) moĝe byÊ szybciej zrealizowana w strukturze opartej na wskaěnikach. Z tej wïaĂciwoĂci skorzystamy w dalszej czÚĂci tego rozdziaïu, aby stworzyÊ strukturÚ danych do przechowywania informacji o studentach, która powiÚksza siÚ w razie koniecznoĂci. Wspóïdzielenie pamiÚci Wskaěniki mogÈ poprawiÊ wydajnoĂÊ programu poprzez umoĝliwienie wspóï- dzielenia bloków pamiÚci. Na przykïad jeĂli wywoïujemy funkcjÚ, za pomocÈ parametrów referencji moĝemy przekazaÊ tylko wskaěnik do obszaru pamiÚci, zamiast kopiowaÊ caïy blok. Najprawdopodobniej widziaïeĂ juĝ takÈ operacjÚ w praktyce. Referencje majÈ umieszczony znak miÚdzy typem i nazwÈ na liĂcie parametrów formalnych: void refParamFunction (int ™ x) { š x = 10; } int number = 5; refParamFunction(› number); cout œ number \n ; UWAGA Spacje przed i po znaku nie sÈ wymagane. UmieĂciïem je wyïÈcznie ze wzglÚdów estetycznych. W kodach innych programistów bÚdziesz mógï zauwaĝyÊ takie za- pisy, jak int x, int x, a byÊ moĝe nawet int x. 110 R o z d z i a ï 4 Poleć książkęKup książkę W powyĝszym kodzie formalny parametr x ™ nie jest kopiÈ argumentu num- ber ›, lecz odwoïaniem do miejsca w pamiÚci, w którym przechowywana jest zmienna number. Dlatego teĝ po zmianie x š pamiÚÊ zajmowana przez zmiennÈ number zostaje zmodyfikowana, a w wyniku tego program wyĂwietla wartoĂÊ 10 œ. Jak przedstawiono w powyĝszym przykïadzie, parametry referencyjne mogÈ byÊ uĝywane w mechanizmach umoĝliwiajÈcych zwracanie wartoĂci z funkcji. MówiÈc ogólniej, pozwalajÈ one wspóïdzieliÊ ten sam obszar pamiÚci zarówno przez funkcjÚ wywoïywanÈ, jak i wywoïujÈcÈ, a przez to zmniejszaÊ narzut. JeĂli zmienna bÚdÈca parametrem zajmuje 1 kilobajt pamiÚci, przekazanie jej jako referencji wymaga skopiowania tylko 32- lub 64-bitowego wskaěnika zamiast caïego kilo- bajta. Poprzez zastosowanie sïowa kluczowego const moĝemy poinformowaÊ, ĝe uĝywamy parametru referencyjnego w celu poprawy wydajnoĂci, a nie zwracania wartoĂci: int anotherFunction(const int x); DziÚki umieszczeniu sïowa const przed deklaracjÈ parametru referencyjne- go x funkcja anotherFunction otrzyma referencjÚ do przekazanego argumentu, lecz nie bÚdzie mogïa go zmodyfikowaÊ, podobnie jak dzieje siÚ w przypadku kaĝ- dego innego parametru zdefiniowanego jako const. MówiÈc ogólnie, moĝemy uĝywaÊ wskaěników w powyĝszy sposób, aby po- zwoliÊ róĝnym czÚĂciom programu lub strukturom znajdujÈcym siÚ w nim na dostÚp do tego samego obszaru danych bez potrzeby jego kopiowania. Kiedy naleĝy uĝywaÊ wskaěników? Podobnie jak tablice, równieĝ wskaěniki majÈ potencjalne wady i powinny byÊ uĝywane jedynie w odpowiednich sytuacjach. W jaki sposób moĝemy wiedzieÊ, kiedy uĝycie wskaěnika jest odpowiednie? ZnajÈc juĝ zalety stosowania wskaě- ników, moĝemy stwierdziÊ, ĝe powinny byÊ one uĝywane jedynie wówczas, gdy naleĝy wziÈÊ pod uwagÚ co najmniej jednÈ z korzyĂci przez nie oferowanych. JeĂli Twój program wymaga zïoĝonej struktury w celu przechowywania danych, lecz przed jego uruchomieniem nie moĝesz dokïadnie oszacowaÊ, ile miejsca ona zajmie; jeĂli potrzebujesz struktury, która moĝe siÚ powiÚkszaÊ i zmniejszaÊ w trakcie dziaïania aplikacji; jeĂli obsïugujesz duĝe obiekty lub inne bloki danych, które sÈ przekazywane w róĝnych miejscach programu — wówczas powinieneĂ zastosowaÊ wskaěniki. W przypadku gdy nie masz do czynienia z którÈĂ z wy- mienionych sytuacji, naleĝy jednak unikaÊ uĝycia wskaěników i dynamicznego przydzielania pamiÚci. ZnajÈc zïÈ sïawÚ wskaěników, uwaĝanych za jednÈ z najtrudniejszych cech jÚzyka C++, mógïbyĂ stwierdziÊ, ĝe ĝaden z programistów nie spróbuje nawet ich uĝyÊ, gdy nie bÚdzie to niezbÚdne. Byïem jednak wielokrotnie zaskoczony sytuacjÈ zupeïnie odwrotnÈ. Czasem programiĂci po prostu oszukujÈ samych R o z w i È z y wa n i e p r ob l e m ó w z a p o m o c È w s k a ě n i k ó w i pa m i Ú c i d y n a m i c z n e j 111 Poleć książkęKup książkę siebie, starajÈc siÚ udowodniÊ, ĝe uĝycie wskaěników jest konieczne. Wyobraě sobie, ĝe wywoïujesz funkcjÚ napisanÈ przez kogoĂ innego, na przykïad znajdu- jÈcÈ siÚ w bibliotece lub interfejsie programowania aplikacji. Uĝywasz w tym celu nastÚpujÈcego prototypu: void compute(int input, int *output); MoglibyĂmy zaïoĝyÊ, ĝe ta funkcja zostaïa napisana w jÚzyku C, a nie C++, dlatego uĝywa wskaěnika zamiast referencji ( ), by zdefiniowaÊ parametr wyj- Ăciowy. Nierozwaĝny programista mógïby wywoïaÊ tÚ funkcjÚ w poniĝszy sposób: int num1 = 10; int *num2 = new int; compute(num1, num2); Powyĝszy kod jest niewydajny pamiÚciowo, poniewaĝ tworzy wskaěnik, mi- mo ĝe nie jest to wymagane. Oprócz dwóch zmiennych caïkowitych rezerwuje on miejsce na dodatkowy wskaěnik. Kod jest takĝe niewydajny czasowo, poniewaĝ zbÚdna alokacja pamiÚci zajmuje czas procesora (jak wyjaĂniono w nastÚpnym podrozdziale). Tego wszystkiego moĝna uniknÈÊ poprzez zastosowanie innego aspektu operatora , który pozwoli na uzyskanie adresu dla statycznie zadekla- rowanej zmiennej, na przykïad: int num1 = 10; int num2; compute(num1, num2); MówiÈc dokïadniej, mimo ĝe w kolejnej wersji naszego kodu wciÈĝ stosuje- my wskaěnik, uĝywamy go jednak w sposób domyĂlny, nie tworzÈc nowej zmiennej wskaěnikowej ani nie deklarujÈc dynamicznej pamiÚci. PamiÚÊ ma znaczenie Aby zrozumieÊ, w jaki sposób dynamiczne przydzielanie pamiÚci pozwala nam na powiÚkszanie i zmniejszanie zasobów w czasie dziaïania programu, powinni- Ămy dowiedzieÊ siÚ wiÚcej o tym, jak ogólnie dziaïa alokacja pamiÚci. Wedïug mnie jest to jedno z zagadnieñ, z których mogÈ skorzystaÊ poczÈtkujÈcy pro- gramiĂci uczÈcy siÚ jÚzyka C++. Wszyscy programiĂci muszÈ w koñcu zrozu- mieÊ, jak dziaïajÈ systemy pamiÚci w nowoczesnym komputerze, a jÚzyk C++ po prostu zmusza CiÚ do staniÚcia twarzÈ w twarz z tym zagadnieniem. Inne jÚ- zyki tak dokïadnie ukrywajÈ szczegóïy zarzÈdzania pamiÚciÈ, ĝe nowicjusze przekonujÈ samych siebie, iĝ ta wiedza ich nie dotyczy, co jednak nie jest prawdÈ. 112 R o z d z i a ï 4 Poleć książkęKup książkę Szczegóïy moĝe nie sÈ waĝne, dopóki wszystko dziaïa prawidïowo. Gdy jednak tylko pojawiajÈ siÚ kïopoty, ignorowanie niskopoziomowych modeli pamiÚci po- woduje powstanie pomiÚdzy programistÈ i rozwiÈzaniem problemu przeszkód nie do pokonania. Stos i sterta JÚzyk C++ alokuje pamiÚÊ w dwóch miejscach: na stosie (ang. stack) i na stercie (ang. heap). Jak wynika z samych nazw, stos jest uporzÈdkowany i schludny, a sterta chaotyczna i niechlujna. Nazwa „stos” jest szczególnie opisowa, poniewaĝ pozwala wyobraziÊ sobie metodÚ zwartego przydzielania pamiÚci. Zaïóĝmy, ĝe masz do czynienia ze stosem skrzyñ przedstawionym na rysunku 4.1 (a). Gdy musisz przechowaÊ nowÈ skrzyniÚ w magazynie, umieszczasz jÈ na samej górze stosu. Aby usunÈÊ okreĂlonÈ skrzyniÚ, zdejmujesz najpierw te, które sÈ nad niÈ. W praktycznej terminologii programowania oznacza to, ĝe po przydzieleniu bloku pamiÚci (skrzyni) na stosie nie moĝna zmieniÊ jego rozmiaru, poniewaĝ w dowolnym momencie mogÈ istnieÊ inne obszary, znajdujÈce siÚ bezpoĂrednio za nim (inne skrzynie nad niÈ). Rysunek 4.1. Stos skrzyñ i stos wywoïañ funkcji W jÚzyku C++ moĝesz jawnie stworzyÊ wïasny stos, by uĝyÊ go w okreĂlo- nym algorytmie, lecz bez wzglÚdu na to w systemie istnieje jeden stos, który zawsze bÚdzie uĝywany przez Twój program. Jest on zwany stosem wywoïañ (ang. runtime stack). Za kaĝdym razem gdy wywoïana zostaje funkcja (oznacza to tak- ĝe funkcjÚ main), na szczycie stosu wywoïañ zarezerwowany zostaje blok pamiÚci. Jest on zwany rekordem aktywacji (ang. activation record). Peïna analiza jego R o z w i È z y wa n i e p r ob l e m ó w z a p o m o c È w s k a ě n i k ó w i pa m i Ú c i d y n a m i c z n e j 113 Poleć książkęKup książkę zawartoĂci wykracza poza ramy tej ksiÈĝki, lecz bÚdÈc osobÈ zajmujÈcÈ siÚ roz- wiÈzywaniem problemów, powinieneĂ wiedzieÊ, ĝe podstawowym zadaniem re- kordu aktywacji jest udostÚpnianie miejsca do przechowywania zmiennych. Jest w nim przydzielana pamiÚÊ dla wszystkich zmiennych lokalnych, wïÈcznie z pa- rametrami funkcji. Przyjrzyjmy siÚ nastÚpujÈcemu przykïadowi: int functionB(int inputValue) { ™ return inputValue - 10; } int functionA(int num) { int localVariable = functionB(num * 10); return localVariable; } int main() { int x = 12; int y = functionA(x); return 0; } W powyĝszym kodzie funkcja main wywoïuje functionA, która z kolei wy- woïuje functionB. Na rysunku 4.1 (b) przedstawiono uproszczonÈ wersjÚ stanu stosu wywoïañ zaraz przed wykonaniem instrukcji powrotu z funkcji functionB ™. Rekordy aktywacji dla wszystkich trzech funkcji zostaïy umieszczone na stosie zwartej pamiÚci, przy czym funkcja main znajduje siÚ na jego samym dole (aby jeszcze bardziej skomplikowaÊ zagadnienie, chciaïbym dodaÊ, ĝe moĝliwe jest, by — przeciwnie do naturalnego zachowania — stos zaczynaï siÚ od najwyĝsze- go moĝliwego adresu w pamiÚci, a nastÚpnie rósï w kierunku niĝszych adresów. Nic nie stoi jednak na przeszkodzie, by zignorowaÊ tÚ moĝliwoĂÊ). Logicznie rozumujÈc, rekord aktywacji funkcji main znajduje siÚ na dole stosu, rekord ak- tywacji funkcji functionA nad nim, a rekord aktywacji funkcji functionB na sa- mej górze stosu. ¿aden z dwóch niĝszych rekordów aktywacji nie moĝe zostaÊ usuniÚty, zanim nie zlikwidujemy rekordu aktywacji dla funkcji functionB. Stos jest dokïadnie uporzÈdkowany, lecz w przeciwieñstwie do niego sterta jest doĂÊ chaotyczna. Wyobraě sobie, ĝe znów musisz przechowywaÊ skrzynie, lecz tym razem sÈ one delikatne i nie moĝesz ukïadaÊ jednej na drugiej. Na po- czÈtku dysponujesz duĝym, pustym pomieszczeniem i moĝesz w nim ukïadaÊ skrzynie w dowolnym miejscu na podïodze. SÈ one jednak ciÚĝkie, wiÚc po ich uïoĝeniu na podïodze pozostajÈ tam aĝ do momentu, gdy trzeba siÚ bÚdzie ich pozbyÊ. W porównaniu ze stosem, taki system ma pewne zalety i wady. Z jednej strony jest uniwersalny i pozwala w dowolnym momencie uzyskaÊ dostÚp do zawartoĂci kaĝdej ze skrzyñ. Z drugiej strony jednak w pomieszczeniu szybko zapanuje nieporzÈdek. JeĂli skrzynie majÈ róĝne rozmiary, szczególnie trudno bÚdzie wykorzystaÊ kaĝdÈ wolnÈ przestrzeñ dostÚpnÈ na podïodze. W koñcu 114 R o z d z i a ï 4 Poleć książkęKup książkę miÚdzy skrzyniami bÚdzie istnieÊ mnóstwo wolnych miejsc, które bÚdÈ jednak miaïy zbyt maïÈ powierzchniÚ, by umieĂciÊ na nich kolejny element. Poniewaĝ skrzynie nie mogÈ byÊ w prosty sposób przemieszczane, usuwanie niektórych z nich spowoduje, ĝe pojawiÈ siÚ raczej kolejne, trudne do zlikwidowania wolne przestrzenie, a nie obszar, który byïby uporzÈdkowany i zbliĝony wyglÈdem do naszej poczÈtkowej pustej podïogi. W praktycznej terminologii programowania nasza sterta jest jak podïoga w opisanym wïaĂnie pomieszczeniu. Blok pamiÚci jest zwartym ciÈgiem adresów. W trakcie dziaïania programu, który wykonuje wiele rezerwacji i zwolnieñ pamiÚci, pojawia siÚ mnóstwo wolnych przestrzeni miÚdzy zaalokowanymi obszarami. Problem ten jest znany jako fragmentacja pamiÚci (ang. memory fragmentation). Kaĝdy program ma wïasnÈ stertÚ, w której moĝna dynamicznie przydzielaÊ pamiÚÊ. W jÚzyku C++ oznacza to zazwyczaj uĝycie sïowa kluczowego new, lecz moĝesz takĝe stosowaÊ standardowe funkcje jÚzyka C sïuĝÈce do alokowania pamiÚci, takie jak malloc. Kaĝde wywoïanie new (lub malloc) rezerwuje odpo- wiedni obszar na stercie i zwraca wskaěnik do niego, natomiast kaĝde wywoïanie delete (lub free w przypadku, gdy do alokacji uĝyto malloc) powoduje, ĝe jest on zwalniany do puli dostÚpnej pamiÚci. Z powodu fragmentacji nie wszystkie obszary pamiÚci na stercie sÈ równie uĝyteczne. JeĂli nasz program rozpoczyna swoje dziaïanie od przydzielenia pamiÚci na stercie dla zmiennych A, B i C, moĝemy siÚ spodziewaÊ, ĝe te trzy bloki bÚdÈ zwarte. JeĂli jednak zwolnimy pamiÚÊ dla zmiennej B, pojawi siÚ wolne miejsce, które moĝe zostaÊ uĝyte je- dynie przez ĝÈdanie wymagajÈce rezerwacji obszaru o rozmiarze B lub mniej- szym, chyba ĝe zostanie równieĝ zwolniona pamiÚÊ dla zmiennej A lub C. OmawianÈ sytuacjÚ wyjaĂniono na rysunku 4.2. W czÚĂci (a) widzimy podïo- gÚ naszego pomieszczenia z chaotycznie umieszczonymi skrzyniami. W pew- nym momencie pomieszczenie byïo prawdopodobnie uporzÈdkowane, lecz z upïywem czasu skrzynie byïy umieszczane w sposób przypadkowy. Obecnie mamy niewielkÈ skrzyniÚ (b), która jednak nie moĝe zmieĂciÊ siÚ na ĝadnym wolnym miejscu na podïodze, mimo ĝe caïkowita nieuĝywana powierzchnia jest duĝo wiÚksza od powierzchni samej skrzyni. W czÚĂci (c) przedstawiliĂmy nie- wielkÈ stertÚ. Linie przerywane oznaczajÈ najmniejsze (niepodzielne) fragmenty pamiÚci, które w zaleĝnoĂci od rodzaju menedĝera sterty mogïyby byÊ pojedyn- czym bajtem, sïowem lub jeszcze czymĂ wiÚkszym. Obszary zacienione repre- zentujÈ rezerwacje zwartej pamiÚci. Jeden z nich w celu lepszej klarownoĂci zawiera pewne fragmenty, które zostaïy ponumerowane. Podobnie jak nieupo- rzÈdkowana podïoga, równieĝ stos z fragmentacjÈ zawiera wiele oddzielnych fragmentów nieprzydzielonej pamiÚci, co zmniejsza ich przydatnoĂÊ. Mamy 85 nieuĝywanych fragmentów pamiÚci, lecz najwiÚkszy zwarty obszar, wskazywa- ny przez symbol strzaïki, skïada siÚ tylko z 17 elementów. Inaczej mówiÈc, jeĂli kaĝdy z fragmentów byïby bajtem, ta sterta nie mogïaby pozwoliÊ na wykonanie polecenia new przydzielajÈcego obszar pamiÚci wiÚkszy od 17 bajtów, mimo ĝe caïkowita iloĂÊ wolnego miejsca wynosi 85 bajtów. R o z w i È z y wa n i e p r ob l e m ó w z a p o m o c È w s k a ě n i k ó w i pa m i Ú c i d y n a m i c z n e j 115 Poleć książkęKup książkę Rysunek 4.2. NieuporzÈdkowana podïoga, skrzynia, której nie moĝna na niej umieĂciÊ, a takĝe pamiÚÊ z fragmentacjÈ Rozmiar pamiÚci Pierwszym praktycznym zagadnieniem zwiÈzanym z pamiÚciÈ jest ograniczanie jej uĝycia tylko do tego, co niezbÚdne. Nowoczesne systemy komputerowe majÈ tak duĝo pamiÚci, ĝe ïatwo moĝna zaïoĝyÊ, iĝ jej pojemnoĂÊ jest nieskoñczona, lecz w rzeczywistoĂci kaĝdy z programów ma dostÚp do jej ograniczonej iloĂci. Programy równieĝ muszÈ uĝywaÊ pamiÚci w sposób efektywny, aby uniknÈÊ spowolnienia dziaïania caïego systemu. W wielozadaniowym systemie opera- cyjnym (co oznacza praktycznie kaĝdy nowoczesny system) kaĝdy bajt pamiÚci zmarnowany przez dany program zwiÚksza prawdopodobieñstwo pojawienia siÚ sytuacji, w której zestaw dziaïajÈcych aplikacji nie ma juĝ wystarczajÈcej iloĂci pamiÚci do poprawnej pracy. W tym momencie system operacyjny zaczyna w spo- sób ciÈgïy kopiowaÊ fragmenty pamiÚci z jednego programu do drugiego, powo- dujÈc znaczÈce spowolnienie dziaïania aplikacji. Taka sytuacja zwana jest szamo- taniem (ang. thrashing). Zauwaĝ, ĝe poza koniecznoĂciÈ utrzymania jak najmniejszego rozmiaru dla caïego programu naleĝy równieĝ dÈĝyÊ do tego, by stos i sterta byïy jak najwiÚk- sze. Aby to udowodniÊ, zacznijmy rezerwowaÊ pamiÚÊ na stercie po jednym ki- lobajcie za kaĝdym razem, aĝ do momentu gdy coĂ przestanie dziaïaÊ: const int intsPerKilobyte = 1024 / sizeof(int); while (true) { int *oneKilobyteArray = new int[intsPerKilobyte]; } Chciaïbym zaznaczyÊ, ĝe jest to okropny kod, napisany wyïÈcznie w celu za- demonstrowania problemu. JeĂli chciaïbyĂ sprawdziÊ go w swoim systemie, su- gerujÚ, abyĂ wczeĂniej — po prostu dla bezpieczeñstwa — zapisaï wszystkie dane, na których pracujesz. Program zawiesi siÚ, a Twój system operacyjny po- informuje, ĝe kod wywoïaï wyjÈtek bad_alloc, lecz nie mógï go obsïuĝyÊ. Jest on 116 R o z d z i a ï 4 Poleć książkęKup książkę zgïaszany przez instrukcjÚ new, gdy ĝaden blok nieprzydzielonej pamiÚci na stercie nie jest na tyle duĝy, by moĝna byïo poprawnie obsïuĝyÊ ĝÈdanie. Brak miejsca na stercie jest zwany przepeïnieniem sterty (ang. heap overflow). W nie- których systemach taka sytuacja moĝe siÚ zdarzaÊ czÚsto, a w innych bïÚdne dzia- ïanie programu moĝe spowodowaÊ pojawienie siÚ dïugotrwaïego stanu szamo- tania, zanim zostanie zgïoszony wyjÈtek bad_alloc (w moim systemie uĝycie instrukcji new nie powiodïo siÚ dopiero wówczas, gdy za pomocÈ wczeĂniejszych wywoïañ zaalokowaïem 2 gigabajty pamiÚci). Podobna sytuacja zdarza siÚ w przypadku stosu wywoïañ. Kaĝde wywoïanie funkcji rezerwuje miejsce na stosie, a oprócz tego dla kaĝdego rekordu aktywacji istnieje staïy narzut, nawet w przypadku funkcji nieposiadajÈcej parametrów lub lokalnych zmiennych. Najprostszym sposobem zademonstrowania takiej sytuacji jest niekontrolowane wywoïanie funkcji rekurencyjnej: ™ int count = 0; void stackOverflow() { š count++; › stackOverflow(); } int main() { œ stackOverflow(); return 0; } Powyĝszy kod zawiera zmiennÈ globalnÈ ™, co w wiÚkszoĂci przypadków Ăwiadczy o zïym stylu programowania. W tej sytuacji potrzebujmy jednak zmiennej, która bÚdzie istnieÊ podczas wszystkich wywoïañ rekurencyjnych. Poniewaĝ jest ona zadeklarowana poza funkcjÈ, nie ma potrzeby rezerwowania dla niej miejsca w rekordzie aktywacji. Nie istniejÈ równieĝ ĝadne inne lokalne zmienne ani parametry. Funkcja tylko zwiÚksza licznik š, a nastÚpnie wykonuje wywoïanie rekurencyjne ›. Rekurencja zostanie dokïadnie omówiona w roz- dziale 6., lecz w tym przykïadzie jest ona uĝywana tylko w celu stworzenia moĝliwie najdïuĝszego ïañcucha wywoïañ funkcji. Rekord aktywacji funkcji po- zostaje na stosie do momentu jej zakoñczenia. Gdy wiÚc z funkcji main zostaje po raz pierwszy wywoïana funkcja stackOverflow œ, rekord aktywacji jest umiesz- czany na stosie wywoïañ i nie moĝe zostaÊ usuniÚty, dopóki nie zakoñczy siÚ jej dziaïanie. Nie zdarzy siÚ to jednak nigdy, poniewaĝ funkcja wykonuje kolejne wywoïanie stackOverflow, umieszczajÈc nastÚpny rekord aktywacji na stosie, nastÚpnie tworzy trzecie wywoïanie itd. Liczba rekordów aktywacji roĂnie na stosie aĝ do momentu, gdy zaczyna brakowaÊ na nim miejsca. W moim systemie wartoĂÊ count wynosiïa okoïo 4900, gdy program przestaï dziaïaÊ. ¥rodowisko projektowe Visual Studio, w którym pracujÚ, domyĂlnie przydziela programowi 1 MB pamiÚci na stosie, co oznacza, ĝe kaĝde wywoïanie funkcji, nawet takiej, która nie ma lokalnych zmiennych ani parametrów, tworzy rekord aktywacji o wielkoĂci ponad 200 bajtów. R o z w i È z y wa n i e p r ob l e m ó w z a p o m o c È w s k a ě n i k ó w i pa m i Ú c i d y n a m i c z n e j 117 Poleć książkęKup książkę Czas ĝycia Czas ĝycia (ang. lifetime) zmiennej to okres miÚdzy jej alokacjÈ a zwolnieniem pamiÚci. W przypadku zmiennej korzystajÈcej ze stosu, czyli zmiennej lokalnej lub parametru, czas ĝycia jest zarzÈdzany w sposób domyĂlny. Zmienna zostaje zaalokowana podczas wywoïania funkcji, a usuniÚta po jej zakoñczeniu. W przy- padku zmiennej korzystajÈcej ze sterty, czyli dynamicznie zaalokowanej przy uĝyciu instrukcji new, czas jej ĝycia jest w naszych rÚkach. ZarzÈdzanie czasem ĝycia dynamicznie alokowanych zmiennych jest zmorÈ kaĝdego programisty C++. NajczÚĂciej znanym problemem jest groěny wyciek pamiÚci, czyli sytu- acja, w której pamiÚÊ zostaje przydzielona na stercie, lecz nigdy nie jest zwol- niona ani wykorzystana przez ĝaden wskaěnik. Oto prosty przykïad: ™ int *intPtr = new int; š intPtr = NULL; W powyĝszym kodzie deklarujemy wskaěnik do liczby caïkowitej ™, inicjali- zujÈc go poprzez przydzielenie odpowiedniego miejsca na stercie. NastÚpnie w drugim wierszu do tego wskaěnika przypisujemy wartoĂÊ NULL š (która jest po prostu innym identyfikatorem liczby zero). WartoĂÊ caïkowita, którÈ zaalokowali- Ămy za pomocÈ instrukcji new, wciÈĝ jednak istnieje. Samotna i porzucona znaj- duje siÚ na swoim miejscu na stercie, czekajÈc na operacjÚ zwolnienia pamiÚci, która nigdy nie wystÈpi. Nie moĝemy zwolniÊ pamiÚci dla zaalokowanej zmien- nej caïkowitej, poniewaĝ taka operacja wymaga uĝycia sïowa kluczowego delete z parametrem bÚdÈcym wskaěnikiem do usuwanego bloku, a my juĝ nim nie dysponujemy. JeĂli chcielibyĂmy jednak wykonaÊ polecenie delete intPtr, za- koñczyïoby siÚ ono bïÚdem, poniewaĝ wartoĂÊ intPrt jest równa zeru. Czasem zamiast problemu z pamiÚciÈ, której nie moĝna zwolniÊ, mamy do czynienia z czymĂ odwrotnym. Jest to próba zwolnienia tej samej pamiÚci dwu- krotnie, co powoduje powstanie bïÚdu czasu wykonania. Wydaje siÚ, ĝe takiej sytuacji moĝna ïatwo uniknÈÊ: wystarczy nie wywoïywaÊ dwukrotnie instrukcji delete dla tej samej zmiennej. Jest to jednak bardziej skomplikowane, poniewaĝ moĝemy mieÊ wiele zmiennych wskazujÈcych na ten sam obszar pamiÚci. JeĂli wiele zmiennych wskazuje na ten sam blok pamiÚci i zostanie wykonane pole- cenie delete dla jednej z nich, wówczas w rzeczywistoĂci zwolnimy pamiÚÊ dla wszystkich. JeĂli nie przypiszemy im jawnie wartoĂci NULL, wówczas bÚdziemy mieli do czynienia ze wskaěnikami zawieszonymi, dla których wywoïanie delete bÚdzie powodowaÊ pojawienie siÚ bïÚdu czasu wykonania. 118 R o z d z i a ï 4 Poleć książkęKup książkę RozwiÈzywanie problemów za pomocÈ wskaěników W tym momencie jesteĂ juĝ gotowy do rozwiÈzywania problemów, dlatego przyjrzyjmy siÚ kilku z nich i spróbujmy uĝyÊ wskaěników oraz dynamicznego przydzielania pamiÚci, by je rozwiÈzaÊ. Najpierw zajmiemy siÚ dynamicznie alokowanymi tablicami, co pozwoli na zaprezentowanie metody kontrolowania pamiÚci sterty podczas ich uĝywania. NastÚpnie zanurzymy siÚ w prawdziwie dynamicznej strukturze. ’añcuchy o zmiennej dïugoĂci W pierwszym problemie zamierzamy stworzyÊ funkcje do obsïugi ïañcuchów tekstowych. Ten termin jest tu uĝyty w najbardziej ogólnym znaczeniu — jako sekwencja znaków, bez wzglÚdu na sposób ich przechowywania. Zaïóĝmy, ĝe nasz typ ïañcuchowy powinien byÊ wspierany przez trzy funkcje. PROBLEM: OBS’UGA ’A”CUCHÓW O ZMIENNEJ D’UGO¥CI Stwórz implementacjÚ opartÈ na stercie dla trzech funkcji obsïugujÈcych ïañ- cuchy:  append — funkcja wymaga podania ïañcucha i znaku, a w wyniku swojego dziaïania doïÈcza ten znak do koñca ïañcucha.  concatenate — funkcja uĝywa dwóch ïañcuchów i doïÈcza znaki z drugiego do pierwszego.  characterAt — funkcja wymaga uĝycia ïañcucha oraz odpowiedniej liczby, zwracajÈc znak znajdujÈcy siÚ na wskazywanej przez niÈ pozycji w ïañcuchu (pierwszy znak ïañcucha ma indeks równy zeru). Napisz kod, zakïadajÈc, ĝe funkcja characterAt bÚdzie wywoïywana czÚsto, a dwie pozostaïe stosunkowo rzadko. WzglÚdna wydajnoĂÊ operacji powinna odzwierciedlaÊ czÚstotliwoĂÊ ich stosowania. W tym przypadku powinniĂmy zaprojektowaÊ takÈ reprezentacjÚ ïañcucha, która pozwoli na szybkie wykonywanie funkcji characterAt, co oznacza, ĝe musimy wymyĂleÊ szybki sposób na uzyskanie dostÚpu do dowolnego znaku. Jak praw- dopodobnie pamiÚtasz z poprzedniego rozdziaïu, to jest wïaĂnie najlepsza zaleta tablic — dostÚp swobodny. RozwiÈĝmy wiÚc nasz problem przy uĝyciu tablic typu char. Funkcje append i concatenate zmieniajÈ rozmiar ïañcucha, co ozna- cza, ĝe napotkamy tu wszystkie rodzaje problemów dotyczÈcych tablic, o których juĝ wspominaliĂmy. Poniewaĝ w problemie nie zdefiniowano ograniczenia doty- czÈcego wielkoĂci ïañcucha, nie moĝemy okreĂliÊ poczÈtkowego rozmiaru dla naszych tablic i mieÊ nastÚpnie nadziejÚ, ĝe wszystko bÚdzie dziaïaÊ. Zamiast tego musimy zmieniaÊ go w trakcie dziaïania programu. R o z w i È z y wa n i e p r ob l e m ó w z a p o m o c È w s k a ě n i k ó w i pa m i Ú c i d y n a m i c z n e j 119 Poleć książkęKup książkę Aby rozpoczÈÊ, zdefiniujmy nazwÚ typu dla naszego ïañcucha za pomocÈ sïo- wa kluczowego typedef. Wiemy, ĝe tablice bÚdziemy tworzyÊ w sposób dyna- miczny, wiÚc musimy zaprojektowaÊ nasz typ ïañcuchowy jako wskaěnik do char: typedef char * arrayString; MajÈc gotowy typ, zajmijmy siÚ funkcjami. WykorzystujÈc zasadÚ rozpoczy- nania od tego, co juĝ potrafimy zrobiÊ, napiszmy szybko funkcjÚ characterAt: char characterAt(arrayString s, int position) { ™ return s[position]; } Jak pamiÚtasz z rozdziaïu 3., gdy wskaěnikowi zostaï przypisany adres tabli- cy, moĝemy uzyskaÊ dostÚp do jej elementów, wykorzystujÈc w tym celu zwykïÈ notacjÚ tablicowÈ ™. Zauwaĝ jednak, ĝe w przypadku gdy wartoĂÊ position nie bÚdzie poprawnym indeksem tablicy s, mogÈ pojawiÊ siÚ problemy. Dodatkowo powyĝszy kod przerzuca odpowiedzialnoĂÊ za kontrolowanie poprawnoĂci dru- giego parametru na funkcjÚ wywoïujÈcÈ. Inne rozwiÈzania tego zagadnienia zo- stanÈ przedstawione w Êwiczeniach. W chwili obecnej zajmijmy siÚ funkcjÈ append. Moĝemy sobie ogólnie wyobraziÊ, co powinna ona wykonywaÊ, lecz aby poznaÊ szczegóïy, powinniĂmy rozwaĝyÊ uĝycie przykïadu. Jest to technika, któ- rÈ nazywam rozwiÈzywaniem poprzez przykïad. Rozpocznij od zdefiniowania nietrywialnego zestawu danych wejĂciowych dla funkcji lub programu. Zapisz wszystkie szczegóïy zwiÈzane z danymi wejĂciowymi, a takĝe te, które dotyczÈ wyników. Gdy bÚdziesz tworzyï kod, zajmiesz siÚ ogólnym przypadkiem, a takĝe dokïadnie sprawdzisz, w jaki sposób na kaĝdym etapie dziaïania programu zmody- fikowane zostajÈ dane wejĂciowe, aby upewniÊ siÚ, ĝe osiÈgasz wymagany stan wyjĂciowy. Ta metoda jest szczególnie przydatna podczas pracy ze wskaěnikami i dynamicznie przydzielanÈ pamiÚciÈ, poniewaĝ w takich przypadkach program dziaïa w wiÚkszoĂci poza bezpoĂredniÈ kontrolÈ. ¥ledzenie stanu na papierze zmusza CiÚ do obserwowania wszystkich zmieniajÈcych siÚ wartoĂci w pamiÚci — nie tylko tych, które sÈ bezpoĂrednio reprezentowane przez zmienne, lecz takĝe samej sterty. Zaïóĝmy, ĝe rozpoczniemy od ïañcucha test, co oznacza, ĝe na stercie mamy tablicÚ zawierajÈcÈ znaki t, e, s i t — w tej wïaĂnie kolejnoĂci, a przy uĝyciu funkcji append chcielibyĂmy dodaÊ do niej znak wykrzyknika. Na rysunku 4.3 zaprezentowano stan pamiÚci przed (a) i po (b) wykonaniu tej operacji. To, co znajduje siÚ po lewej stronie pionowej, kropkowanej linii, jest pamiÚciÈ stosu (lokalnymi zmiennymi lub parametrami). Wszystko po jej prawej stronie dotyczy pamiÚci na stercie, dynamicznie przydzielonej za pomocÈ sïowa kluczowego new. 120 R o z d z i a ï 4 Poleć książkęKup książkę Rysunek 4.3. Proponowane stany pamiÚci przed i po wywoïaniu funkcji append SpoglÈdajÈc na rysunek, od razu widzÚ ewentualny problem, który moĝe siÚ pojawiÊ w naszej funkcji. WykorzystujÈc zdefiniowanÈ przez nas implementacjÚ ïañcuchów tekstowych, funkcja zamierza stworzyÊ nowÈ tablicÚ, majÈcÈ liczbÚ elementów wiÚkszÈ o jeden od pierwotnej, a nastÚpnie skopiowaÊ wszystkie znaki z pierwszej tablicy do drugiej. Lecz w jaki sposób bÚdziemy wiedzieÊ, jaki rozmiar ma pierwsza tablica? Z poprzedniego rozdziaïu wiemy, ĝe powinniĂmy sami ĂledziÊ wielkoĂÊ naszych tablic. Tak wiÚc czegoĂ tu brakuje. JeĂli mamy jakieĂ doĂwiadczenie w pracy z ïañcuchami ze standardowej bi- blioteki jÚzyków C i C++, wiemy juĝ, czym jest brakujÈcy element. JeĂli nie, moĝemy go szybko znaleěÊ. PamiÚtaj, ĝe jednÈ z naszych technik rozwiÈzywania problemów jest poszukiwanie analogii. ByÊ moĝe powinniĂmy siÚ zastanowiÊ nad innymi problemami, w których wiedza o wielkoĂci jakiegoĂ skïadnika jest nie- znana. W rozdziale 2. podczas rozwiÈzywania problemu walidacji sumy kontrol- nej Luhna przetwarzaliĂmy numery identyfikacyjne o dowolnej liczbie cyfr. Nie wiedzieliĂmy wówczas, ile cyfr wprowadzi uĝytkownik, jednak napisaliĂmy pÚ- tlÚ while dziaïajÈcÈ aĝ do momentu, w którym nie zostaï wczytany ostatni znak, czyli koniec wiersza. Niestety, na koñcu naszych tablic nie ma znaku koñca wiersza. Ale dlaczego nie moglibyĂmy umieĂciÊ tego znaku jako ostatniego elementu we wszystkich naszych tablicach znakowych? Wówczas bÚdziemy mogli wyznaczyÊ dïugoĂÊ ïañcucha w taki sam sposób, jak ustalaliĂmy liczbÚ cyfr w numerze identyfika- cyjnym. JedynÈ wadÈ tej metody jest to, ĝe w naszych ïañcuchach, z wyjÈtkiem ich zakoñczenia, nie moglibyĂmy juĝ uĝywaÊ znaków koñca wiersza. Nie jest to zbyt wielkie ograniczenie i zaleĝy od sytuacji, w której wykorzystamy nasze ïañ- cuchy. Dla uzyskania maksymalnej uniwersalnoĂci powinniĂmy jednak wybraÊ takÈ wartoĂÊ, która nie bÚdzie kolidowaÊ z ĝadnym znakiem moĝliwym do zasto- sowania przez uĝytkownika. Do oznaczania koñca naszych ïañcuchów wybie- rzemy wiÚc zero, poniewaĝ reprezentuje ono wartoĂÊ pustÈ w ASCII i innych systemach kodowania znaków. Jest to dokïadnie taka sama metoda, którÈ zasto- sowano w standardowej bibliotece dla jÚzyków C i C++. Po rozwiÈzaniu powyĝszego problemu moĝemy siÚ bardziej skoncentrowaÊ na tym, co powinna robiÊ funkcja append z naszymi przykïadowymi danymi. Wiemy, ĝe bÚdzie ona miaïa dwa parametry: pierwszy typu arrayString ma byÊ wskaěnikiem do ïañcucha znaków na stercie, a drugi typu char powinien byÊ znakiem doïÈczanym do niego. Aby zbytnio nie komplikowaÊ, weěmy siÚ do pracy i stwórzmy szkic funkcji append, a takĝe kod, który powinien jÈ testowaÊ: R o z w i È z y wa n i e p r ob l e m ó w z a p o m o c È w s k a ě n i k ó w i pa m i Ú c i d y n a m i c z n e j 121 Poleć książkęKup książkę void append(™ arrayString s, char c) { } void appendTester() { š arrayString a = new char[5]; › a[0] = t ; a[1] = e ; a[2] = s ; a[3] = t ; a[4] = 0; œ append(a, ! )  cout a \n ; } Funkcja appendTester przydziela pamiÚÊ na stercie dla naszego ïañcucha š. ZwróÊ uwagÚ na to, ĝe rozmiar tablicy wynosi 5, co jest niezbÚdne, poniewaĝ musimy przypisaÊ cztery litery sïowa test oraz koñczÈcy ïañcuch znak pusty ›. NastÚpnie wywoïujemy funkcjÚ append œ, która w tym momencie nie zawiera ĝadnej logiki. Podczas pisania nagïówka funkcji zdaïem sobie sprawÚ, ĝe para- metr typu arrayString powinien byÊ referencjÈ ( ) ™, poniewaĝ funkcja zamierza utworzyÊ na stercie nowÈ tablicÚ. Wynika stÈd, ĝe wartoĂÊ zmiennej a, która jest przekazywana do funkcji append, zostanie zmieniona po jej zakoñczeniu, gdyĝ musi wskazywaÊ na nowy ïañcuch. Zauwaĝ, ĝe ze wzglÚdu na to, iĝ nasze tablice uĝywajÈ koñczÈcego znaku pustego stosowanego w bibliotekach standardowych, moĝemy przekazaÊ tablicÚ poprzez wskaěnik bezpoĂrednio do strumienia wyj- Ăciowego, aby sprawdziÊ jej wartoĂÊ . Na rysunku 4.4 pokazano analizÚ tego, co powinna zrobiÊ funkcja z danymi testowymi. Znaki koñczÈce tablicÚ znajdujÈ siÚ we wïaĂciwych miejscach; dla wiÚkszej czytelnoĂci oznaczono je jako NULL. W stanie (b) oczywiste jest, ĝe zmienna s wskazuje na nowy blok pamiÚci. Poprzednia tablica jest obecnie przed- stawiona w kolorze szarym. W tego typu rysunkach stosujÚ taki kolor w celu poin- formowania, ĝe dany obszar pamiÚci zostaï zwolniony. Umieszczanie pamiÚci przydzielonej w naszych diagramach pozwala nie zapomnieÊ o jej zwalnianiu. Rysunek 4.4. Zaktualizowane i uzupeïnione stany pamiÚci przed (a) i po (b) wywoïaniu funkcji append 122 R o z d z i a ï 4 Poleć książkęKup książkę MajÈc wszystko wïaĂciwie narysowane, moĝemy napisaÊ samÈ funkcjÚ: void append(arrayString s, char c) { int oldLength = 0; ™ while (s[oldLength] != 0) { oldLength++; } š arrayString newS = new char[oldLength + 2]; › for (int i = 0; i oldLength; i++) { newS[i] = s[i]; } œ newS[oldLength] = c;  newS[oldLength + 1] = 0; ž delete[] s; Ÿ s = newS; } W kodzie dzieje siÚ wiele rzeczy, wiÚc przeanalizujmy go krok po kroku. Na poczÈtku funkcji mamy pÚtlÚ, która odszukuje znak NULL koñczÈcy tablicÚ ™. Po jej zakoñczeniu zmienna oldLength bÚdzie zawieraÊ liczbÚ wïaĂciwych znaków w naszej tablicy (to znaczy bez koñczÈcego jÈ znaku pustego). Na stercie przy- dzielamy miejsce dla nowej tablicy, która bÚdzie miaïa rozmiar oldLength + 2 š. Jest to jeden ze szczegóïów, którego nie moĝna ïatwo zrozumieÊ, gdy starasz siÚ to zrobiÊ tylko w swoim umyĂle, lecz staje siÚ to proste po przedstawieniu na rysunku. PodÈĝajÈc za kodem i korzystajÈc z przykïadu przedstawionego na ry- sunku 4.5, moĝemy zauwaĝyÊ, ĝe wartoĂÊ oldLength powinna byÊ równa 4. Wiemy, ĝe tak ma byÊ, poniewaĝ sïowo test skïada siÚ z czterech znaków. Nowa tablica, przedstawiona w czÚĂci (b), wymaga alokacji szeĂciu znaków, gdyĝ musimy mieÊ dodatkowe miejsce na doïÈczany wykrzyknik oraz koñczÈcy znak pusty. Rysunek 4.5. ZaleĝnoĂci miÚdzy zmiennÈ lokalnÈ, parametrami i przydzielonÈ pamiÚciÈ przed i po wykonaniu funkcji append R o z w i È z y wa n i e p r ob l e m ó w z a p o m o c È w s k a ě n i k ó w i pa m i Ú c i d y n a m i c z n e j 123 Poleć książkęKup książkę MajÈc juĝ przydzielonÈ pamiÚÊ, kopiujemy wszystkie znaki wïaĂciwe ze sta- rej tablicy do nowej ›, a nastÚpnie w odpowiednich miejscach umieszczamy doïÈczany œ oraz koñczÈcy znak NULL . PrzypomnÚ jeszcze raz, ĝe stosowanie diagramu pozwala na zachowanie porzÈdku. Aby wszystko wyglÈdaïo jeszcze pro- Ăciej, na rysunku 4.5 zaprezentowano sposób wyznaczania wartoĂci oldLength, a takĝe pozycjÚ, którÈ wskazuje ta zmienna w nowej tablicy. DziÚki tej metodzie moĝna ïatwo okreĂliÊ poprawne indeksy dla obu instrukcji przypisania. Ostatnie trzy wiersze w funkcji append dotyczÈ szarego prostokÈta znajdujÈ- cego siÚ na rysunku w czÚĂci (b). Aby uniknÈÊ wycieku pamiÚci, musimy zwol- niÊ pamiÚÊ na stercie dla tablicy, na którÈ pierwotnie wskazywaï parametr s ž. NastÚpnie przypisujemy mu adres nowej, wiÚkszej tablicy Ÿ. Niestety, jednym z powodów tego, ĝe sytuacje wycieku pamiÚci sÈ tak czÚsto spotykane podczas programowania w jÚzyku C++, jest to, iĝ dopóki caïkowita wielkoĂÊ takiej pa- miÚci nie jest duĝa, system nie zgïasza ĝadnych problemów. Wynika stÈd, ĝe wyciek pamiÚci moĝe zostaÊ zupeïnie niezauwaĝony przez programistÚ podczas przeprowadzania testów programu. Jako programiĂci musimy wiÚc byÊ staranni i zawsze braÊ pod uwagÚ czas ĝycia bloków pamiÚci przydzielonych na stercie. Za kaĝdym razem gdy uĝywasz sïowa kluczowego new, pomyĂl o tym, gdzie i kiedy pojawi siÚ odpowiednie sïowo delete. Zauwaĝ, ĝe wszystko, co zawarliĂmy w funkcji, wynika bezpoĂrednio z naszych diagramów. Skomplikowane programowanie staje siÚ duĝo prostsze przy uĝyciu dobrze zaprojektowanych rysunków. Chciaïbym, aby poczÈtkujÈcy programiĂci poĂwiÚcali trochÚ czasu na ich stworzenie przed rozpoczynaniem wïaĂciwego kodowania. Jest to zwiÈzane z naszÈ najwaĝniejszÈ zasadÈ rozwiÈzywania pro- blemów: zawsze naleĝy mieÊ jakiĂ plan. Dobrze zdefiniowany diagram dla przy- kïadowego problemu jest czymĂ w rodzaju dokïadnie zaplanowanej trasy pro- wadzÈcej do punktu docelowego przed rozpoczÚciem wyjazdu na wakacje. Na poczÈtku wymagane jest poĂwiÚcenie dodatkowego czasu, by na koñcu uniknÈÊ niepotrzebnego wysiïku i frustracji. TWORZENIE DIAGRAMÓW Wszystko, czego potrzebujesz do narysowania diagramu, to oïówek i papier. JeĂli jednak masz wiÚcej czasu, sugerujÚ uĝycie odpowiedniego programu graficznego. Zawiera on narzÚdzia do rysowania oraz szablony dedykowane specjalnie dla potrzeb rozwiÈzywania problemów programistycznych. Jed- nakĝe kaĝdy program obsïugujÈcy grafikÚ wektorowÈ bÚdzie odpowiedni (uĝyty tu termin wektor oznacza, ĝe aplikacja pozwala na tworzenie linii pro- stych i krzywych, a nie przetwarza grafiki rastrowej, tak jak Photoshop). Ilu- stracje do tej ksiÈĝki wykonaïem za pomocÈ darmowego programu Inkscape. Tworzenie diagramów w komputerze pozwala na ich uporzÈdkowanie i prze- chowywanie w tym samym miejscu, w którym znajduje siÚ odpowiedni kod. SÈ one zazwyczaj takĝe bardziej staranne, dziÚki czemu moĝna je ïatwiej zro- zumieÊ, gdy po jakimĂ czasie do nich wrócisz. Wreszcie diagram stworzony na komputerze moĝna ïatwo skopiowaÊ i zmodyfikowaÊ, podobnie jak zro- biïem to w przypadku tworzenia rysunku 4.5 na podstawie poprzedniego. JeĂli chcesz umieĂciÊ na nim jakÈĂ tymczasowÈ uwagÚ, moĝesz to ïatwo zrobiÊ na wydrukowanej kopii. 124 R o z d z i a ï 4 Poleć książkęKup książkę WracajÈc do naszej funkcji append — kod wyglÈda na godny zaufania, lecz pamiÚtaj, ĝe stworzyliĂmy go na podstawie okreĂlonego przykïadu. Nie moĝemy wiÚc byÊ zbyt pewni siebie i zakïadaÊ, ĝe bÚdzie dziaïaï w kaĝdym przypadku. W szczególnoĂci naleĝy przetestowaÊ przypadki specjalne. Przypadkiem specjal- nym w programowaniu nazywana jest sytuacja, w której poprawne dane spowo- dujÈ typowe dziaïanie kodu dajÈcego bïÚdne wyniki. Zauwaĝ, ĝe nasz problem nie dotyczy niepoprawnych danych, takich jak wartoĂci spoza zakresu. W przypadku kodu zawartego w tej ksiÈĝce zaïoĝyliĂmy, ĝe programy i funkcje bÚdÈ otrzymywaÊ poprawne dane. Na przykïad jeĂli pro- gram oczekuje podania szeregu liczb caïkowitych oddzielonych przecinkami, zakïadamy, ĝe je otrzyma, a nie pojawiÈ siÚ ĝadne dodatkowe znaki, wartoĂci nie- liczbowe itp. Takie zaïoĝenie jest niezbÚdne w celu uzyskania programu o sen- sownej dïugoĂci, a takĝe unikniÚcia powtarzania tego samego kodu sprawdzajÈcego poprawnoĂÊ danych. W Ăwiecie rzeczywistym powinniĂmy jednak stosowaÊ od- powiednie zabezpieczenia przeciwko bïÚdnym danym wejĂciowym. Taka wïa- ĂciwoĂÊ programu jest zwana odpornoĂciÈ. Odporna aplikacja dziaïa poprawnie nawet w przypadku zïych danych wejĂciowych. Na przykïad tego typu program mógïby wyĂwietliÊ komunikat bïÚdu, zamiast spowodowaÊ awariÚ dziaïania. Testowanie przypadków specjalnych Przyjrzyjmy siÚ ponownie funkcji append, sprawdzajÈc jÈ pod wzglÚdem przy- padków specjalnych; inaczej mówiÈc, upewniajÈc siÚ, ĝe dla poprawnych wartoĂci wejĂciowych nie pojawiÈ siÚ ĝadne dziwne zachowania programu. Najleps
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Myśl jak programista. Techniki kreatywnego rozwiązywania problemów
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ą: