Rozdział 13.
Tablice i listy połączone

W poprzednich rozdziałach deklarowaliśmy pojedyncze obiekty typu int, char, i tym podobne. Często chcemy jednak deklarować zbiory obiektów, takie jak 20 wartości typu int czy kilka obiektów typu CAT.

Z tego rozdziału dowiesz się:

• czym są tablice i jak się je deklaruje,

• czym są łańcuchy i jak je tworzyć za pomocą tablic znaków,

• jaki jest związek pomiędzy tablicami a wskaźnikami,

• w jaki sposób posługiwać się arytmetyką na wskaźnikach odnoszących się do tablic.

Czym jest tablica?

Tablica (ang. array) jest zbiorem miejsc przechowywania danych, w którym każde z tych miejsc zawiera dane tego samego typu. Każde miejsce przechowywania jest nazywane elementem tablicy.

Tablicę deklaruje się, zapisując typ, nazwę tablicy oraz jej rozmiar. Rozmiar tablicy jest zapisywany jako ujęta w nawiasy kwadratowe ilość elementów tablicy. Na przykład linia:

long LongArray[25];

deklaruje tablicę składającą się z dwudziestu pięciu wartości typu long, noszącą nazwę LongArray. Gdy kompilator natrafi na tę deklarację, zarezerwuje miejsce do przechowania wszystkich dwudziestu pięciu elementów. Ponieważ każda wartość typu long wymaga czterech bajtów pamięci, ta deklaracja rezerwuje sto bajtów ciągłego obszaru pamięci, tak jak pokazano na rysunku 13.1.

Rys. 13.1. Deklarowanie tablicy

Elementy tablicy

Do każdego z elementów tablicy możemy się odwołać, podając przesunięcie (ang. offset) względem nazwy tablicy. Elementy tablicy są liczone od zera. Tak więc pierwszym elementem tablicy jest arrayName[0]. W przykładzie z tablicą LongArray, pierwszym elementem jest LongArray[0], drugim LongArray[1], itd.

Może to być nieco mylące. Tablica SomeArray[3] zawiera trzy elementy. Są to: SomeArray[0], SomeArray[1] oraz SomeArray[2]. Tablica SomeArray[n] zawiera n elementów ponumerowanych od SomeArray[0] do SomeArray[n-1].

Elementy tablicy LongArray[25] są ponumerowane od LongArray[0] do LongArray[24]. Listing 13.1 przedstawia sposób zadeklarowania tablicy pięciu wartości całkowitych i wypełnienia[Author ID1: at Wed Oct 31 12:56:00 2001 ]u[Author ID1: at Wed Oct 31 12:56:00 2001 ] jej wartościami.

Listing 13.1. Użycie tablicy wartości całkowitych

0: //Listing 13.1 - Tablice

1: #include <iostream>

2:

3: int main()

4: {

5: int myArray[5];

6: int i;

7: for ( i=0; i<5; i++) // 0-4

8: {

9: std::cout << "Wartosc elementu myArray[" << i << "]: ";

10: std::cin >> myArray[i];

11: }

12: for (i = 0; i<5; i++)

13: std::cout << i << ": " << myArray[i] << "\n";

14: return 0;

15: }

Wynik

Wartosc elementu myArray[0]: 3

Wartosc elementu myArray[1]: 6

Wartosc elementu myArray[2]: 9

Wartosc elementu myArray[3]: 12

Wartosc elementu myArray[4]: 15

0: 3

1: 6

2: 9

3: 12

4: 15

Analiza

W linii 5. jest deklarowana tablica o nazwie myArray, zawierająca pięć zmiennych całkowitych. W linii 7. rozpoczyna się pętla zliczająca od 0 do 4, czyli przeznaczona dla wszystkich elementów pięcioelementowej tablicy. Użytkownik jest proszony o podanie kolejnych wartości, które są umieszczane w odpowiednich miejscach tablicy.

Pierwsza wartość jest umieszczana w elemencie myArray[0], druga w elemencie myArray[1] , i tak dalej. Druga pętla, for, służy do wypisania na ekranie wartości kolejnych elementów tablicy.

UWAGA Elementy tablic liczy się od 0, a nie od 1. Z tego powodu początkujący programiści języka C++ często popełniają błędy. Zawsze, gdy korzystasz z tablicy, pamiętaj, że tablica zawierająca 10 elementów jest liczona od ArrayName[0] do ArrayName[9]. Element ArrayName[10] nie jest używany.

Zapisywanie poza koniec tablicy

Gdy zapisujesz wartość do elementu tablicy, kompilator na podstawie rozmiaru elementu oraz jego indeksu oblicza miejsce, w którym powinien ją umieścić. Przypuśćmy, że chcesz zapisać wartość do elementu LongArray[5], który jest szóstym elementem tablicy. Kompilator mnoży indeks (5) przez rozmiar elementu, który w tym przypadku wynosi 4. Następnie przemieszcza się od początku tablicy o otrzymaną liczbę bajtów (20) i zapisuje wartość w tym miejscu.

Gdy poprosisz o zapisanie wartości do pięćdziesiątego elementu tablicy LongArray, kompilator zignoruje fakt, iż taki element nie istnieje. Obliczy miejsce wstawienia wartości (200 bajtów od początku tablicy) i zapisze ją w otrzymanym miejscu pamięci. Miejsce to może zawierać praktycznie dowolne dane i zapisanie tam nowej wartości może dać zupełnie nieoczekiwane wyniki. Jeśli masz szczęście, program natychmiast się załamie. Jeśli nie, dziwne wyniki pojawią się dużo później i będziesz miał problem z ustaleniem, co jest ich przyczyną.

Kompilator przypomina ślepca poruszającego się[Author ID1: at Wed Oct 31 13:08:00 2001 ] mijającego kolejne domy. Zaczyna od pierwszego domu, MainStreet[0]. Gdy poprosisz go o przejście do szóstego domu na Main Street, mówi sobie: „Muszę minąć jeszcze pięć domów. Każdy dom to cztery duże kroki. Muszę więc przejść jeszcze dwadzieścia kroków. Gdy poprosisz go o przejście do MainStreet[100], mimo iż przy Main Street stoi tylko 25 domów, przejdzie 400 kroków. Z pewnością, zanim przejdzie ten dystans, wpadnie pod ciężarówkę. Uważaj więc, gdzie go wysyłasz.

Listing 13.2 pokazuje, co się dzieje, gdy zapiszesz coś za końcem tablicy.

OSTRZEŻENIE Nie uruchamiaj tego programu, może on załamać system!

Listing 13.2. Zapis za końcem tablicy

0: //Listing 13.2

1: // Demonstruje, co się stanie, gdy zapiszesz

2: // wartość za końcem tablicy

3:

4: #include <iostream>

5: using namespace std;

6:

7: int main()

8: {

9: // wartownicy

10: long sentinelOne[3];

11: long TargetArray[25]; // tablica do wypełnienia

12: long sentinelTwo[3];

13: int i;

14: for (i=0; i<3; i++)

15: sentinelOne[i] = sentinelTwo[i] = 0;

16:

17: for (i=0; i<25; i++)

18: TargetArray[i] = 0;

19:

20: cout << "Test 1: \n"; // sprawdzamy bieżące wartości (powinny być 0)

21: cout << "TargetArray[0]: " << TargetArray[0] << "\n";

22: cout << "TargetArray[24]: " << TargetArray[24] << "\n\n";

23:

24: for (i = 0; i<3; i++)

25: {

26: cout << "sentinelOne[" << i << "]: ";

27: cout << sentinelOne[i] << "\n";

28: cout << "sentinelTwo[" << i << "]: ";

29: cout << sentinelTwo[i]<< "\n";

30: }

31:

32: cout << "\nPrzypisywanie...";

33: for (i = 0; i<=25; i++)

34: TargetArray[i] = 20;

35:

36: cout << "\nTest 2: \n";

37: cout << "TargetArray[0]: " << TargetArray[0] << "\n";

38: cout << "TargetArray[24]: " << TargetArray[24] << "\n";

39: cout << "TargetArray[25]: " << TargetArray[25] << "\n\n";

40: for (i = 0; i<3; i++)

41: {

42: cout << "sentinelOne[" << i << "]: ";

43: cout << sentinelOne[i]<< "\n";

44: cout << "sentinelTwo[" << i << "]: ";

45: cout << sentinelTwo[i]<< "\n";

46: }

47:

48: return 0;

49: }

Wynik

Test 1:

TargetArray[0]: 0

TargetArray[24]: 0

sentinelOne[0]: 0

sentinelTwo[0]: 0

sentinelOne[1]: 0

sentinelTwo[1]: 0

sentinelOne[2]: 0

sentinelTwo[2]: 0

Przypisywanie...

Test 2:

TargetArray[0]: 20

TargetArray[24]: 20

TargetArray[25]: 20

sentinelOne[0]: 20

sentinelTwo[0]: 0

sentinelOne[1]: 0

sentinelTwo[1]: 0

sentinelOne[2]: 0

sentinelTwo[2]: 0

Analiza

W liniach 10. i 12. deklarowane są dwie tablice, zawierające po trzy zmienne całkowite, które pełnią rolę wartowników (ang. sentinel) wokół docelowej tablicy (TargetArray). Tablice wartowników są wypełniane zerami. Gdy dokonamy zapisu do pamięci poza tablicą TargetArray, najprawdopodobniej zmodyfikujemy zawartość wartowników. Niektóre kompilatory zliczają pamięć do góry, inne w dół. Z tego powodu umieściliśmy wartowników po obu stronach tablicy.

Linie od 20. do 30. potwierdzają wartości wartowników w teście 1. W linii 34. elementy tablicy są wypełniane wartością 20, ale licznik zlicza aż do elementu 25, który nie istnieje w tablicy TargetArray.

Linie od 37. do 39. wypisują wartości elementów tablicy TargetArray w drugim teście. Zwróć uwagę, że element TargetArray[25] wypisuje wartość 20. Jednak gdy wypisujemy wartości wartowników sentinelOne i sentinelTwo, okazuje się, że wartość elementu sentinelOne[0] uległa zmianie. Stało się tak, ponieważ pamięć położona o 25 elementów dalej od elementu TargetArray[0] zajmuje to samo miejsce, co element sentinelOne[0]. Gdy odwołujemy się do nieistniejącego elementu TargetArray[0], w rzeczywistości odwołujemy się do elementu sentinelOne[0].

Taki błąd może być bardzo trudny do wykrycia, gdyż wartość elementu sentinelOne[0] zostaje zmieniona w miejscu programu, które pozornie nie jest związane z zapisem wartości do tej tablicy.

W tym programie użyto „magicznych liczb”, takich jak 3 dla rozmiarów tablic wartowników i 25 dla rozmiaru tablicy TargetArray. Bezpieczniej jednak jest używać stałych tak, aby można było zmieniać te wartości w jednym miejscu.

Pamiętaj, że ponieważ kompilatory różnią się od siebie, otrzymany przez ciebie wynik może być nieco inny.

Błąd słupka w płocie

Zapisanie wartości o jedną pozycję za końcem tablicy jest tak często popełnianym błędem, że otrzymał on nawet swoją własną nazwę. Nazywany jest błędem słupka w płocie. Nazwa ta nawiązuje do problemu, jaki wiele osób ma z obliczeniem ilości słupków potrzebnych do utrzymania dziesięciometrowego płotu, z słupkami rozmieszonymi co metr. Większość osób odpowie, że potrzeba dziesięciu słupków, ale oczywiście potrzebnych jest ich jedenaście. Wyjaśnia to rysunek 13.2.

Rys. 13.2. Błąd słupka w płocie

Typ zliczania „o jeden więcej” może być początkowo udręką programisty. Jednak z czasem przywykniesz do tego, że elementy w dwudziestopięcioelementowej tablicy zliczane są tylko do elementu numer dwadzieścia cztery, oraz do tego, że wszystko liczone jest począwszy od zera.

UWAGA Niektórzy programiści określają element ArrayName[0] jako element zerowy. Nie należy się na to zgadzać, gdyż jeśli ArrayName[0] jest elementem zerowym, to czym jest ArrayName[1]? Pierwszym? Jeśli tak, to czy będziesz pamiętał, gdy zobaczysz ArrayName[24], że nie jest to element dwudziesty czwarty, ale dwudziesty piąty? Lepiej jest powiedzieć, że element ArrayName[0] ma zerowy offset i jest pierwszym elementem.

Inicjalizowanie tablic

Deklarując po raz pierwszy prostą tablicę wbudowanych typów, takich jak int czy char, możesz ją zainicjalizować. Po nazwie tablicy umieść znak równości (=) oraz ujętą w nawiasy klamrowe listę rozdzielonych przecinkami wartości. Na przykład

int IntegerArray[5] = { 10, 20, 30, 40, 50 };

deklaruje IntegerArray jako tablicę pięciu wartości całkowitych. Przypisuje elementowi IntegerArray[0] wartość 10, elementowi IntegerArray[1] wartość 20, i tak dalej.

Gdy pominiesz rozmiar tablicy, zostanie stworzona tablica na tyle duża, by mogła pomieścić inicjalizujące je elementy. Jeśli napiszesz:

int IntegerArray[] = { 10, 20, 30, 40, 50 };

stworzysz taką samą tablicę, jak w poprzednim przykładzie.

Jeśli chcesz znać rozmiar tablicy, możesz poprosić kompilator, aby go dla ciebie obliczył. Na przykład

const USHORT IntegerArrayLength = sizeof(IntegerArray) /

sizeof(IntegerArray[0]);

przypisuje stałej IntegerArrayLength typu USHORT wynik dzielenia rozmiaru całej tablicy przez rozmiar pojedynczego jej elementu. Wynik ten odpowiada ilości elementów w tablicy.

Nie można inicjalizować więcej elementów niż wynosi rozmiar tablicy. Tak więc zapis

int IntegerArray[5] = { 10, 20, 30, 40, 50, 60 };

spowoduje błąd kompilacji, gdyż została zadeklarowana tablica pięcioelementowa, a my próbujemy zainicjalizować sześć elementów. Można natomiast napisać

int IntegerArray = {10, 20};

TAK	NIE
Pozwól, by kompilator sam określał rozmiar inicjalizowanych tablic. Nadawaj tablicom znaczące nazwy, tak jak wszystkim innym zmiennym. Pamiętaj, że pierwszy element tablicy ma offset (przesunięcie) wynoszący zero.	Nie dokonuj zapisów za końcem tablicy.

Deklarowanie tablic

Tablica może mieć dowolną nazwę, zgodną z zasadami nazywania zmiennych, ale nie może mieć takiej samej nazwy jak zmienna lub inna tablica wewnątrz danego zakresu. Dlatego nie można mieć jednocześnie tablicy o nazwie myCats[5] oraz zmiennej myCats.

Rozmiar tablicy można określić, używając stałej lub wyliczenia. Ilustruje to listing 13.3.

Listing 13.3. Użycie stałej i wyliczenia jako rozmiaru tablicy

0: // Listing 13.3

1: // Użycie stałej i wyliczenia jako rozmiaru tablicy

2:

3: #include <iostream>

4: int main()

5: {

6: enum WeekDays { Sun, Mon, Tue,

7: Wed, Thu, Fri, Sat, DaysInWeek };

8: int ArrayWeek[DaysInWeek] = { 10, 20, 30, 40, 50, 60, 70 };

9:

10: std::cout << "Wartoscia Wtorku jest: " << ArrayWeek[Tue];

11: return 0;

12: }

Wynik

Wartoscia Wtorku jest: 30

Analiza

Linia 6. tworzy typ [Author ID1: at Wed Oct 31 13:10:00 2001 ]wyliczeniowy[Author ID1: at Wed Oct 31 13:10:00 2001 ]e[Author ID1: at Wed Oct 31 13:10:00 2001 ] o nazwie WeekDays (dni tygodnia). Zawiera ono osiem składowych. Stałej Sun (od sunday — niedziela) odpowiada wartość 0, zaś stałej DaysInWeek (dni w tygodniu) odpowiada wartość 7.

W linii 10. wyliczeniowa stała Tue (od tuesday — wtorek) pełni rolę offsetu tablicy. Ponieważ stała Tue odpowiada wartości dwa, w linii 10. zwracany i wypisywany jest trzeci element tablicy, ArrayWeek[2].

Tablice

Aby zadeklarować tablicę, zapisz typ przechowywanego w niej obiektu, nazwę tablicy oraz jej rozmiar, określający ilość obiektów, które powinny być przechowane w tej tablicy.

Przykład 1

int MyIntegerArray[90];

Przykład 2

long * ArrayOfPointersToLong[8];

Aby odwołać się do elementów tablicy, użyj operatora indeksu.

Przykład 1

int theNinethInteger = MyIntegerArray[8];

Przykład 2

long * pLong = ArrayOfPointersToLongs[8];

Elementy tablic są liczone od zera. Tablica n elementów zawiera elementy liczone od zera do n-1.

Tablice obiektów

W tablicach można przechowywać dowolne obiekty, zarówno wbudowane, jak i te zdefiniowane przez użytkownika. Deklarując tablicę, informujesz kompilator o typie przechowywanych obiektów oraz ilości obiektów, dla jakiej ma zostać zaalokowane miejsce. Kompilator, na podstawie deklaracji klasy, zna ilość miejsca zajmowanego przez każdy z obiektów. Klasa musi posiadać domyślny konstruktor nie posiadający argumentów (aby obiekty mogły zostać stworzone podczas definiowania tablicy).

Na proces dostępu do danych składowych w tablicy obiektów składają się dwa kroki. Właściwy element tablicy jest wskazywany za pomocą operatora indeksu ([]), po czym dodawany jest operator składowej (.), wydzielający określoną zmienną składową obiektu. Listing 13.4 demonstruje sposób tworzenia i wykorzystania tablicy pięciu obiektów typu CAT.

Listing 13.4. Tworzenie tablicy obiektów

0: // Listing 13.4 - Tablica obiektów

1:

2: #include <iostream>

3: using namespace std;

4:

5: class CAT

6: {

7: public:

8: CAT() { itsAge = 1; itsWeight=5; }

9: ~CAT() {}

10: int GetAge() const { return itsAge; }

11: int GetWeight() const { return itsWeight; }

12: void SetAge(int age) { itsAge = age; }

13:

14: private:

15: int itsAge;

16: int itsWeight;

17: };

18:

19: int main()

20: {

21: CAT Litter[5];

22: int i;

23: for (i = 0; i < 5; i++)

24: Litter[i].SetAge(2*i +1);

25:

26: for (i = 0; i < 5; i++)

27: {

28: cout << "Kot nr " << i+1<< ": ";

29: cout << Litter[i].GetAge() << endl;

30: }

31: return 0;

32: }

Wynik

Kot nr 1: 1

Kot nr 2: 3

Kot nr 3: 5

Kot nr 4: 7

Kot nr 5: 9

Analiza

Linie od 5. do 17. deklarują klasę CAT. Klasa CAT musi posiadać domyślny konstruktor, aby w tablicy mogły być tworzone jej obiekty. Pamiętaj, że jeśli stworzysz jakikolwiek inny konstruktor, domyślny konstruktor nie zostanie dostarczany przez kompilator; będziesz musiał stworzyć go sam.

Pierwsza pętla for (linie 23. i 24.) ustawia wiek dla każdego z pięciu obiektów CAT w tablicy. Druga pętla for (linie od 26. do 30.) odwołuje się do każdego z obiektów i wywołuje jego funkcję składową GetAge().

Metoda GetAge() każdego z poszczególnych obiektów jest wywoływana poprzez określenie elementu tablicy, Litter[i], po którym następuje operator kropki (.) oraz nazwa funkcji składowej.

Tablice wielowymiarowe

Tablice mogą mieć więcej niż jeden wymiar. Każdy wymiar jest reprezentowany przez oddzielny indeks tablicy. Na przykład, tablica dwuwymiarowa posiada dwa indeksy; tablica trójwymiarowa posiada trzy indeksy, i tak dalej. Tablice mogą mieć dowolną ilość wymiarów, choć najprawdopodobniej większość tworzonych przez ciebie tablic będzie miała tylko jeden lub dwa wymiary.

Dobrym przykładem tablicy dwuwymiarowej jest szachownica. Jeden wymiar reprezentuje osiem rzędów, zaś drugi wymiar reprezentuje osiem kolumn. Ilustruje to rysunek 13.3.

Rys. 13.3. Szachownica oraz tablica dwuwymiarowa

Przypuśćmy że mamy klasę o nazwie SQUARE (kwadrat). Deklaracja tablicy o nazwie Board (plansza), która ją reprezentuje, mogłaby więc mieć postać:

SQUARE Board[8][8];

Te same dane moglibyśmy przechować w jednowymiarowej, 64-elementowej tablicy. Na przykład:

SQUARE Board[64];

Nie odpowiadałoby to jednak rzeczywistej, dwuwymiarowej planszy. Na początku gry król umieszczany jest na czwartej pozycji w pierwszym rzędzie; tej pozycji odpowiada:

Board[0][3];

przy założeniu, że pierwszy wymiar odnosi się do rzędów, a drugi do kolumn.

Inicjalizowanie tablic wielowymiarowych

Tablice wielowymiarowe także mogą być inicjalizowane. Kolejnym elementom tablicy przypisywane są wartości, przy czym gdy wcześniejsze wymiary pozostają stały,[Author ID1: at Wed Oct 31 13:13:00 2001 ]zmianie [Author ID1: at Wed Oct 31 13:13:00 2001 ]enia[Author ID1: at Wed Oct 31 13:13:00 2001 ]podlega[Author ID1: at Wed Oct 31 13:13:00 2001 ]ją[Author ID1: at Wed Oct 31 13:43:00 2001 ] [Author ID1: at Wed Oct 31 13:13:00 2001 ]się[Author ID1: at Wed Oct 31 13:13:00 2001 ]dane w [Author ID1: at Wed Oct 31 13:43:00 2001 ]ostatnim[Author ID1: at Wed Oct 31 13:43:00 2001 ] wymiarze[Author ID1: at Wed Oct 31 13:43:00 2001 ] tablicy (przy ustaleniu wszystkich poprzednich[Author ID1: at Wed Oct 31 13:14:00 2001 ]). Tak więc, gdy mamy tablicę:

int theArray[5][3];

pierwsze trzy elementy trafiają do theArray[0], następne trzy do theArray[1], i tak dalej.

Tablicę tę możemy zainicjalizować, pisząc:

int theArray[5][3] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };

W celu uzyskania lepszej przejrzystości, możesz pogrupować wartości, używając nawiasów klamrowych. Na przykład:

int theArray[5][3] = { { 1, 2, 3},

{ 4, 5, 6},

{ 7, 8, 9},

{10,11,12},

{13,14,15} };

Kompilator ignoruje wewnętrzne nawiasy klamrowe (choć ułatwiają one użytkownikowi zrozumienie sposobu ułożenia wartości).

Każda wartość musi być oddzielona przecinkiem, bez względu na stosowanie nawiasów klamrowych. Cały zestaw inicjalizacyjny musi być ujęty w nawiasy klamrowe i kończyć się średnikiem.

Listing 13.5 tworzy tablicę dwuwymiarową. Pierwszym[Author ID1: at Wed Oct 31 13:16:00 2001 ] wymiarem (czyli pierwszą kolumną) [Author ID1: at Wed Oct 31 13:16:00 2001 ]jest zestaw liczb od zera do cztery. Drugi wymiar (czyli drugą kolumnę) [Author ID1: at Wed Oct 31 13:17:00 2001 ]zawiera podwojoną[Author ID1: at Wed Oct 31 13:17:00 2001 ] stanowią liczby o [Author ID1: at Wed Oct 31 13:17:00 2001 ]wartości[Author ID1: at Wed Oct 31 13:18:00 2001 ]ach[Author ID1: at Wed Oct 31 13:19:00 2001 ] dwukrotnie[Author ID1: at Wed Oct 31 13:18:00 2001 ] większych [Author ID1: at Wed Oct 31 13:18:00 2001 ]niż wartości w kolumnie pierwszej.[Author ID1: at Wed Oct 31 13:18:00 2001 ]

ć każdej z wartości w pierwszym wymiarze.[Author ID1: at Wed Oct 31 13:18:00 2001 ]

Listing 13.5. Tworzenie tablicy wielowymiarowej

0: // Listing 13.5 - Tworzenie tablicy wielowymiarowej

1:

2: #include <iostream>

3: using namespace std;

4:

5: int main()

6: {

7: int SomeArray[5][2] = { {0,0}, {1,2}, {2,4}, {3,6}, {4,8}};

8: for (int i = 0; i<5; i++)

9: for (int j=0; j<2; j++)

10: {

11: cout << "SomeArray[" << i << "][" << j << "]: ";

12: cout << SomeArray[i][j]<< endl;

13: }

14:

15: return 0;

16: }

Wynik

SomeArray[0][0]: 0

SomeArray[0][1]: 0

SomeArray[1][0]: 1

SomeArray[1][1]: 2

SomeArray[2][0]: 2

SomeArray[2][1]: 4

SomeArray[3][0]: 3

SomeArray[3][1]: 6

SomeArray[4][0]: 4

SomeArray[4][1]: 8

Analiza

Linia 7. deklaruje SomeArray jako tablicę dwuwymiarową. Pierwszy wymiar składa się z pięciu liczb całkowitych, zaś drugi z [Author ID1: at Wed Oct 31 13:19:00 2001 ]dwóch liczb całkowitych. Powstaje więc siatka o rozmiarach 5×2, co ilustruje rysunek 13.4.

Rys. 13.4. Tablica 5 x 2

Wartości są inicjalizowane w parach, choć równie dobrze mogłyby zostać obliczone. Linie 8. i 9. tworzą zagnieżdżoną pętlę for. Pętla zewnętrzna „przechodzi” przez każdy element pierwszego wymiaru. Odpowiednio, dla każdego elementu w tym wymiarze, wewnętrzna pętla przechodzi przez każdy element drugiego wymiaru. Jest to zgodne z wydrukiem. Po elemencie SomeArray[0][0] następuje element SomeArray[0][1]. Pierwszy wymiar jest inkrementowany tylko wtedy, gdy drugi wymiar zostanie wcześniej [Author ID1: at Wed Oct 31 13:20:00 2001 ]zwiększony o jeden. Wtedy zaczyna się ponowne zliczanie drugiego wymiaru.

Kilka słów na temat pamięci

Gdy deklarujesz tablicę, dokładnie informujesz kompilator o tym, ile obiektów chcesz w niej przechować. Kompilator rezerwuje pamięć dla wszystkich tych obiektów, nawet jeśli nigdy z nich nie skorzystasz. Nie stanowi to problemu w przypadku tych tablic, w których dokładnie znasz ilość potrzebnych ci elementów. Na przykład, szachownica zawiera 64 pola, zaś koty rodzą od jednego do dziesięciu kociąt. Jeśli jednak nie masz pojęcia, ilu obiektów potrzebujesz, musisz skorzystać z bardziej zaawansowanych struktur danych.

W tej książce przedstawimy tablice wskaźników, tablice tworzone na stercie oraz różne inne kolekcje. Poznamy też kilka zaawansowanych struktur danych, jednak więcej informacji na ten temat możesz znaleźć w mojej książce C++ Unleashed, wydanej przez Sams Publishing. Dwie najlepsze rzeczy w programowaniu to możliwość ciągłego uczenia się i to, że zawsze pojawiają się kolejne książki, z których można się uczyć.

Tablice wskaźników

W przedstawianych dotąd tablicach wszystkie ich elementy były składowane na stosie. Zwykle pamięć stosu jest dość ograniczona, podczas gdy pamięć na stercie jest dużo bardziej obszerna. Istnieje możliwość zadeklarowania wszystkich obiektów na stercie i przechowania w tablicy tylko wskaźnika do każdego z obiektów. Powoduje to znaczne zmniejszenie ilości pamięci stosu zajmowanej przez tablicę. Listing 13.6 zawiera zmodyfikowaną wersję listingu 13.4, w której wszystkie obiekty przechowywane są na stercie. W celu podkreślenia faktu, że umożliwia ona lepsze wykorzystanie pamięci, rozmiar tablicy został zwiększony z pięciu do pięciuset elementów, zaś jej nazwa została zmieniona z Litter (miot) na Family (rodzina).

Listing 13.6. Tablica wskaźników do obiektów

0: // Listing 13.6 - Tablica wskaźników do obiektów

1:

2: #include <iostream>

3: using namespace std;

4:

5: class CAT

6: {

7: public:

8: CAT() { itsAge = 1; itsWeight=5; }

9: ~CAT() {} // destruktor

10: int GetAge() const { return itsAge; }

11: int GetWeight() const { return itsWeight; }

12: void SetAge(int age) { itsAge = age; }

13:

14: private:

15: int itsAge;

16: int itsWeight;

17: };

18:

19: int main()

20: {

21: CAT * Family[500];

22: int i;

23: CAT * pCat;

24: for (i = 0; i < 500; i++)

25: {

26: pCat = new CAT;

27: pCat->SetAge(2*i +1);

28: Family[i] = pCat;

29: }

30:

31: for (i = 0; i < 500; i++)

32: {

33: cout << "Kot nr " << i+1 << ": ";

34: cout << Family[i]->GetAge() << endl;

35: }

36: return 0;

37: }

Wynik

Kot nr 1: 1

Kot nr 2: 3

Kot nr 3: 5

...

Kot nr 499: 997

Kot nr 500: 999

Analiza

Obiekt CAT zadeklarowany w liniach od 5. do 17. jest identyczny z obiektem CAT zadeklarowanym na listingu 13.4. Tym razem jednak tablica zadeklarowana w linii 21. ma nazwę Family i zawiera 500 wskaźników do obiektów typu CAT.

W początkowej pętli for (linie od 24. do 29.) na stercie tworzonych jest pięćset nowych obiektów typu CAT; dla każdego z nich wiek jest ustawiany jako podwojony indeks plus jeden. Tak więc pierwszy CAT ma wiek 1, drugi ma wiek 3, trzeci ma 5, i tak dalej. Na zakończenie, w tablicy umieszczany jest wskaźnik kolejnego stworzonego obiektu.

Ponieważ tablica została zadeklarowana jako zawierająca wskaźniki, dodawany jest do niej wskaźnik — a nie obiekt wyłuskany z[Author ID1: at Wed Oct 31 13:20:00 2001 ]spod[Author ID1: at Wed Oct 31 13:20:00 2001 ] tego wskaźnika.

Druga pętla for (linie od 31. do 35.) wypisuje każdą z wartości. Dostęp do wskaźnika uzyskuje się przez użycie indeksu elementu, Family[i]. Otrzymany adres umożliwia dostęp do metody GetAge().

W tym przykładzie tablica Family i wszystkie zawarte w niej wskaźniki są przechowywane na stosie, ale pięćset stworzonych przedtem obiektów CAT znajduje się na stercie.

Deklarowane tablic na stercie

Istnieje możliwość umieszczenia na stercie całej tablicy. W tym celu należy wywołać new z operatorem indeksu. W rezultacie otrzymujemy wskaźnik do obszaru sterty zawierającego nowo utworzoną tablicę. Na przykład:

CAT *Family = new CAT[500];

deklaruje zmienną Family jako wskaźnik do pierwszego elementu w pięciusetelementowej tablicy obiektów typu CAT. Innymi słowy, Family wskazuje na — czyli zawiera adres — element Family[0].

Zaletą użycia zmiennej Family w ten sposób jest to, że możemy na wskaźnikach wykonać działania arytmetyczne odwołując się do elementów tablicy. Na przykład, możemy napisać:

CAT *Family = new CAT[500];

CAT *pCat = Family; // pCat wskazuje na Family[0]

pCat->SetAge(10); // ustawia Family[0] na 10

pCat++; // przechodzi do Family[1]

pCat->SetAge(20); // ustawia Family[1] na 20

Deklarujemy tu nową tablicę pięciuset obiektów typu CAT oraz wskaźnik wskazujący początek tej tablicy. Używając tego wskaźnika, wywołujemy funkcję SetAge() pierwszego obiektu, przekazując jej wartość 10. Następnie wskaźnik jest inkrementowany i automatycznie wskazuje następny obiekt w tablicy, po czym wywoływana jest metoda SetAge()następnego obiektu.

Wskaźnik do tablicy a tablica wskaźników

Przyjrzyjmy się trzem poniższym deklaracjom:

1: CAT FamilyOne[500];

2: CAT * FamilyTwo[500];

3: CAT * FamilyThree = new CAT[500];

FamilyOne jest tablicą pięciuset obiektów typu CAT. FamilyTwo jest tablicą pięciuset wskaźników do obiektów typu CAT. FamilyThree jest wskaźnikiem do tablicy pięciuset obiektów typu CAT.

Różnice pomiędzy tymi trzema liniami kodu zasadniczo wpływają na działanie tych tablic. Jeszcze bardziej dziwi fakt, iż FamilyThree jest po prostu wariantem deklaracji FamilyOne (i bardzo się różni od FamilyTwo).

Mamy tu do czynienia ze złożonym zagadnieniem powiązań tablic ze wskaźnikami. W trzecim przypadku, FamilyThree jest wskaźnikiem do tablicy, czyli adres w zmiennej FamilyThree jest adresem pierwszego elementu w tej tablicy, co dokładnie odpowiada przypadkowi ze zmienną FamilyOne.

Wskaźniki a nazwy tablic

W C++ nazwa tablicy jest stałym wskaźnikiem do pierwszego elementu tablicy. Tak więc, w deklaracji

CAT Family[50];

Family jest wskaźnikiem do &Family[0], które jest adresem pierwszego elementu w tablicy Family.

Używanie nazw tablic jako stałych wskaźników (i odwrotnie) jest dozwolone. Tak więc Family + 4 jest poprawnym sposobem odwołania się do danych w elemencie Family[4].

Podczas dodawania, inkrementowania lub dekrementowania wskaźników wszystkie działania arytmetyczne wykonuje kompilator. Adres, do którego odwołujemy się, pisząc Family + 4, nie jest adresem położonym o cztery bajty od adresu wskazywanego przez Family, lecz adresem położonym o cztery obiekty dalej. Gdyby każdy z obiektów zajmował cztery bajty, wtedy Family + 4 odnosiłoby się do miejsca położonego o szesnaście bajtów za początkiem tablicy. Gdyby każdy obiekt typu CAT zawierał cztery składowe typu long, zajmujące po cztery bajty każda, oraz dwie składowe typu short, po dwa bajty każda, wtedy każdy obiekt tego typu zajmowałby dwadzieścia bajtów, zaś Family + 4 odnosiłoby się do adresu położonego o osiemdziesiąt bajtów od początku tablicy.

Deklarowanie i wykorzystanie tablicy zadeklarowanej na stercie ilustruje listing 13.7.

Listing 13.7. Tworzenie tablicy za pomocą operatora new

0: // Listing 13.7 - Tablica utworzona na stercie

1:

2: #include <iostream>

3:

4: class CAT

5: {

6: public:

7: CAT() { itsAge = 1; itsWeight=5; }

8: ~CAT();

9: int GetAge() const { return itsAge; }

10: int GetWeight() const { return itsWeight; }

11: void SetAge(int age) { itsAge = age; }

12:

13: private:

14: int itsAge;

15: int itsWeight;

16: };

17:

18: CAT :: ~CAT()

19: {

20: // cout << "Wywolano destruktor!\n";

21: }

22:

23: int main()

24: {

25: CAT * Family = new CAT[500];

26: int i;

27:

28: for (i = 0; i < 500; i++)

29: {

30: Family[i].SetAge(2*i +1);

31: }

32:

33: for (i = 0; i < 500; i++)

34: {

35: std::cout << "Kot nr " << i+1 << ": ";

36: std::cout << Family[i].GetAge() << std::endl;

37: }

38:

39: delete [] Family;

40:

41: return 0;

42: }

Wynik

Kot nr 1: 1

Kot nr 2: 3

Kot nr 3: 5

...

Kot nr 499: 997

Kot nr 500: 999

Analiza

Linia 25. deklaruje tablicę Family zawierającą pięćset obiektów typu CAT. Cała tablica jest tworzona na stercie, za pomocą wywołania new CAT[500].

Usuwanie tablic ze sterty

Co się stanie z pamięcią zaalokowaną dla tych obiektów CAT, gdy tablica zostanie zniszczona? Czy istnieje możliwość wycieku pamięci? Usunięcie tablicy Family automatycznie zwróci całą pamięć przydzieloną tablicy wtedy, gdy użyjesz operatora delete[], pamiętając o nawiasach kwadratowych. Kompilator potrafi wtedy zniszczyć każdy z obiektów w tablicy i odpowiednio zwolnić pamięć sterty.

Aby to sprawdzić, zmień rozmiar tablicy z 500 na 10 w liniach 25., 28. oraz 36. Następnie usuń znak komentarza przy instrukcji cout w linii 20. Gdy program „dojedzie” do linii 39., w której tablica jest niszczona, zostanie wywołany destruktor każdego z obiektów CAT.

Gdy tworzysz element na stercie za pomocą operatora new, zawsze powinieneś usuwać go i zwalniać jego pamięć za pomocą operatora delete. Gdy tworzysz tablicę, używając operatora new <klasa>[rozmiar], do usunięcia tej tablicy i zwolnienia jej pamięci powinieneś użyć operatora delete[]. Nawiasy kwadratowe sygnalizują kompilatorowi, że chodzi o usunięcie tablicy.

Gdy pominiesz nawiasy kwadratowe, zostanie usunięty tylko pierwszy element w tablicy. Możesz to sprawdzić sam, usuwając nawiasy kwadratowe w linii 39. Jeśli zmodyfikowałeś linię 20. tak, by destruktor wypisywał komunikat, powinieneś zobaczyć na ekranie, że niszczony jest tylko jeden obiekt CAT. Gratulacje! Właśnie stworzyłeś wyciek pamięci!

TAK	NIE
Pamiętaj, że tablica n elementów zawiera elementy liczone od zera do n-1. W przypadku wskaźników wskazujących tablice, używaj indeksowania tablic.	Nie dokonuj zapisów ani odczytów poza końcem tablicy. Nie myl tablicy wskaźników ze wskaźnikiem do tablicy.

Tablice znaków

Łańcuch w języku C jest tablicą znaków, zakończoną znakiem null. Jedyne łańcuchy w stylu C, z jakimi mieliśmy dotąd do czynienia, to nienazwane stałe łańcuchowe, używane w instrukcjach cout, takie jak:

cout << "hello world.\n";

Łańcuchy w stylu C możesz deklarować i inicjalizować tak samo, jak wszystkie inne tablice. Na przykład:

char Greeting[] =

{ 'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd', '\0' };

Ostatni znak, '\0', jest znakiem null, który jest rozpoznawany przez wiele funkcji C++ jako znak kończący łańcuch w stylu C. Choć inicjalizowanie „znak po znaku” przynosi efekty, jest jednak dość żmudne i daje wiele okazji do błędów. C++ pozwala więc na używanie dla poprzedniej deklaracji formy skrótowej:

char Greeting[] = "Hello World";

Powinieneś zwrócić uwagę na dwa elementy w tej konstrukcji:

• zamiast pojedynczych znaków ujętych w apostrofy, oddzielonych przecinkami i ujętych w nawiasy klamrowe, wpisuje się ujęty w cudzysłowy łańcuch w stylu C, bez przecinków i bez nawiasów klamrowych,

• nie ma potrzeby dołączania znaku null, gdyż kompilator dołącza go automatycznie.

Łańcuch Hello World, przechowywany w stylu C, ma dwanaście znaków. Słowo Hello zajmuje pięć bajtów, spacja jeden bajt, słowo World pięć bajtów, zaś kończący znak null zajmuje jeden bajt.

Możesz także tworzyć nie zainicjalizowane tablice znaków. Tak jak w przypadku wszystkich tablic, należy upewnić się, czy w buforze nie zostanie umieszczone więcej znaków, niż jest miejsca.

Listing 13.8 demonstruje użycie nie zainicjalizowanego bufora.

Listing 13.8. Wypełnianie tablicy

0: //Listing 13.8 bufory znakowe

1:

2: #include <iostream>

3:

4: int main()

5: {

6: char buffer[80];

7: std::cout << "Wpisz lancuch: ";

8: std::cin >> buffer;

9: std::cout << "Oto zawartosc bufora: " << buffer << std::endl;

10: return 0;

11: }

Wynik

Wpisz lancuch: Hello World

Oto zawartosc bufora: Hello

Analiza

W linii 6. deklarowany jest bufor, mogący pomieścić osiemdziesiąt znaków. Wystarcza to do przechowania 79-znakowego łańcucha w stylu C oraz kończącego znaku null.

W linii 7. użytkownik jest proszony o wpisanie łańcucha w stylu C, który jest[Author ID1: at Wed Oct 31 13:21:00 2001 ]w linii 8. jest wprowadzany do bufora. Obiekt cin automatycznie dopisuje do łańcucha w buforze znak kończący null.

W przypadku programu z listingu 13.8 pojawiają się dwa problemy. Po pierwsze, jeśli użytkownik wpisze więcej niż 79 znaków, cin dokona zapisu poza końcem bufora. Po drugie, gdy użytkownik wpisze spację, cin potraktuje ją jako koniec łańcucha i przestanie zapisywać resztę znaków do bufora.

Aby rozwiązać te problemy, musisz wywołać specjalną metodę obiektu cin: metodę get(). Metoda cin.get() posiada trzy parametry:

• bufor do wypełnienia,

• maksymalną ilość znaków do pobrania,

• znak kończący wprowadzany łańcuch.

Domyślnym znakiem kończącym jest znak nowej linii. Użycie tej metody ilustruje listing 13.9.

Listing 13.9. Wypełnianie tablicy

0: //Listing 13.9 użycie cin.get()

1:

2: #include <iostream>

3: using namespace std;

4:

5: int main()

6: {

7: char buffer[80];

8: cout << "Wpisz lancuch: ";

9: cin.get(buffer, 79); // pobiera do 79 znaków lub do znaku nowej linii

10: cout << "Oto zawartosc bufora: " << buffer << endl;

11: return 0;

12: }

Wynik

Wpisz lancuch: Hello World

Oto zawartosc bufora: Hello World

Analiza

Linia 9. wywołuje metodę get() obiektu cin. Bufor zadeklarowany w linii 7. jest przekazywany jako jej pierwszy argument. Drugim argumentem jest maksymalna ilość znaków do pobrania, w tym przypadku musi nią być 79 (tak, aby bufor mógł pomieścić także kończący znak null). Nie ma potrzeby podawania także[Author ID1: at Wed Oct 31 13:21:00 2001 ] [Author ID1: at Wed Oct 31 13:22:00 2001 ]dodawania[Author ID1: at Wed Oct 31 13:22:00 2001 ] znaku kończącego wpis[Author ID1: at Wed Oct 31 13:22:00 2001 ], gdyż robi to[Author ID1: at Wed Oct 31 13:25:00 2001 ] [Author ID1: at Wed Oct 31 13:23:00 2001 ]wartość [Author ID1: at Wed Oct 31 13:22:00 2001 ]wystarczy[Author ID1: at Wed Oct 31 13:22:00 2001 ]domyślna [Author ID1: at Wed Oct 31 13:23:00 2001 ]ej[Author ID1: at Wed Oct 31 13:23:00 2001 ]dla [Author ID1: at Wed Oct 31 13:46:00 2001 ]przejścia [Author ID1: at Wed Oct 31 13:24:00 2001 ]d[Author ID1: at Wed Oct 31 13:23:00 2001 ]o[Author ID1: at Wed Oct 31 13:46:00 2001 ] [Author ID1: at Wed Oct 31 13:23:00 2001 ]nowej linii.

strcpy() oraz strncpy()

C++ odziedziczyło od języka C bibliotekę funkcji operujących na łańcuchach w stylu C. Wśród wielu funkcji tego typu znajdziemy dwie funkcje służące do kopiowania jednego łańcucha do drugiego: strcpy() oraz strncpy(). Funkcja strcpy() kopiuje całą zawartość jednego łańcucha do wskazanego bufora. Jej użycie ilustruje listing 13.10.

Listing 13.10. Użycie strcpy()

0: //Listing 13.10 Użycie strcpy()

1:

2: #include <iostream>

3: #include <string.h>

4: using namespace std;

5:

6: int main()

7: {

8: char String1[] = "Zaden czlowiek nie jest samoistna wyspa";

9: char String2[80];

10:

11: strcpy(String2,String1);

12:

13: cout << "String1: " << String1 << endl;

14: cout << "String2: " << String2 << endl;

15: return 0;

16: }

Wynik

String1: Zaden czlowiek nie jest samoistna wyspa

String2: Zaden czlowiek nie jest samoistna wyspa

Analiza

W linii 3. jest dołączany plik nagłówkowy string.h. Ten plik zawiera prototyp funkcji strcpy(). Funkcja otrzymuje dwie tablice znaków — docelową oraz źródłową. Gdyby tablica źródłowa była większa niż tablica docelowa, funkcja strcpy() dokonałaby zapisu poza koniec bufora.

Aby nas przed tym zabezpieczyć, biblioteka standardowa zawiera także funkcję strncpy(). Ta wersja funkcji posiada dodatkowy argument, określający maksymalną ilość znaków do skopiowania. Funkcja strncpy() kopiuje znaki, aż do napotkania pierwszego znaku null albo do osiągnięcia dozwolonej maksymalnej ilości znaków.

Listing 13.11 ilustruje użycie funkcji strncpy().

Listing 13.11. Użycie funkcji strncpy()

0: //Listing 13.11 Użycie strncpy()

1:

2: #include <iostream>

3: #include <string.h>

4:

5: int main()

6: {

7: const int MaxLength = 80;

8: char String1[] = "Zaden czlowiek nie jest samoistna wyspa";

9: char String2[MaxLength+1];

10:

11:

12: strncpy(String2,String1,MaxLength);

13:

14: std::cout << "String1: " << String1 << std::endl;

15: std::cout << "String2: " << String2 << std::endl;

16: return 0;

17: }

Wynik

String1: Zaden czlowiek nie jest samoistna wyspa

String2: Zaden czlowiek nie jest samoistna wyspa

Analiza

W linii 12. wywołanie funkcji strcpy() zostało zmienione na wywołanie funkcji strncpy(). Funkcja ta posiada także trzeci parametr, określający maksymalną ilość znaków do skopiowania. Bufor String2 ma długość MaxLength+1 (maksymalna długość + 1) znaków. Dodatkowy znak jest przeznaczony do przechowania znaku null, który jest automatycznie umieszczany na końcu łańcucha — zarówno przez funkcję strcpy(), jak i strncpy().

Klasy łańcuchów

C++ przejęło z języka C zakończone znakiem null łańcuchy oraz bibliotekę funkcji, zawierającą także funkcję strcpy(), ale funkcje tej biblioteki nie są zintegrowane z bibliotekami zorientowanymi obiektowo. Biblioteka standardowa zawiera klasę String, obejmującą zestaw danych i funkcji przeznaczonych do manipulowania łańcuchami, oraz zestaw akcesorów, dzięki którym same dane są ukryte przed klientami tej klasy.

W ramach ćwiczenia potwierdzającego właściwe zrozumienie omawianych zagadnień, spróbujemy teraz stworzyć własną klasę String. Nasza klasa String powinna likwidować podstawowe ograniczenia tablic znaków. Podobnie jak wszystkie tablice, tablice znaków są statyczne. Sami definiujemy, jaki mają rozmiar. Tablice te zawsze zajmują określoną ilość pamięci, bez względu na to, czy jest to naprawdę potrzebne. Z kolei dokonanie zapisu za końcem tablicy może mieć katastrofalne skutki.

UWAGA Przedstawiona tu klasa String jest bardzo ograniczona i w żadnym przypadku nie może być uważana za nadającą się do poważnych zastosowań. Wystarczy jednak na potrzeby naszego ćwiczenia, gdyż biblioteka standardowa zawiera pełną i stabilną klasę String.

Dobra klasa String alokuje tylko tyle pamięci, ile potrzebuje (aby zawsze wystarczało na przechowanie tego, co powinna zawierać). Jeśli nie może zaalokować wystarczającej ilości pamięci, powinna poprawnie to zgłosić.

Pierwszą próbę utworzenia naszej klasy String przedstawia listing 13.12.

Listing 13.12. Użycie klasy String

0: //Listing 13.12 Użycie klasy String

1:

2: #include <iostream>

3: #include <string.h>

4: using namespace std;

5:

6: // zasadnicza klasa łańcucha

7: class String

8: {

9: public:

10: // konstruktory

11: String();

12: String(const char *const);

13: String(const String &);

14: ~String();

15:

16: // przeciążone operatory

17: char & operator[](unsigned short offset);

18: char operator[](unsigned short offset) const;

19: String operator+(const String&);

20: void operator+=(const String&);

21: String & operator= (const String &);

22:

23: // ogólne akcesory

24: unsigned short GetLen()const { return itsLen; }

25: const char * GetString() const { return itsString; }

26:

27: private:

28: String (unsigned short); // prywatny konstruktor

29: char * itsString;

30: unsigned short itsLen;

31: };

32:

33: // domyślny konstruktor tworzy łańcuch o długości zera bajtów

34: String::String()

35: {

36: itsString = new char[1];

37: itsString[0] = '\0';

38: itsLen=0;

39: }

40:

41: // prywatny (pomocniczy) konstruktor, używany tylko przez

42: // metody klasy, do tworzenia nowego łańcucha o

43: // wymaganym rozmiarze, wypełnionym bajtami zerowymi

44: String::String(unsigned short len)

45: {

46: itsString = new char[len+1];

47: for (unsigned short i = 0; i<=len; i++)

48: itsString[i] = '\0';

49: itsLen=len;

50: }

51:

52: // zamienia tablicę znaków na String

53: String::String(const char * const cString)

54: {

55: itsLen = strlen(cString);

56: itsString = new char[itsLen+1];

57: for (unsigned short i = 0; i<itsLen; i++)

58: itsString[i] = cString[i];

59: itsString[itsLen]='\0';

60: }

61:

62: // konstruktor kopiujący[Author ID1: at Wed Oct 31 13:25:00 2001 ]i[Author ID1: at Wed Oct 31 13:25:00 2001 ]

63: String::String (const String & rhs)

64: {

65: itsLen=rhs.GetLen();

66: itsString = new char[itsLen+1];

67: for (unsigned short i = 0; i<itsLen;i++)

68: itsString[i] = rhs[i];

69: itsString[itsLen] = '\0';

70: }

71:

72: // destruktor, zwalnia zaalokowaną pamięć

73: String::~String ()

74: {

75: delete [] itsString;

76: itsLen = 0;

77: }

78:

79: // operator równości, zwalnia istniejącą pamięć,

80: // po czym kopiuje łańcuch i rozmiar

81: String& String::operator=(const String & rhs)

82: {

83: if (this == &rhs)

84: return *this;

85: delete [] itsString;

86: itsLen=rhs.GetLen();

87: itsString = new char[itsLen+1];

88: for (unsigned short i = 0; i<itsLen;i++)

89: itsString[i] = rhs[i];

90: itsString[itsLen] = '\0';

91: return *this;

92: }

93:

94: // nie stały operator indeksu, zwraca

95: // referencję do znaku, dzięki czemu może on

96: // być zmieniony!

97: char & String::operator[](unsigned short offset)

98: {

99: if (offset > itsLen)

100: return itsString[itsLen-1];

101: else

102: return itsString[offset];

103: }

104:

105: // stały operator offsetu do[Author ID1: at Wed Oct 31 13:26:00 2001 ]indeksu dla[Author ID1: at Wed Oct 31 13:26:00 2001 ] użycia dla

106: // stałych obiektów (patrz konstruktor kopiujący[Author ID1: at Wed Oct 31 13:26:00 2001 ]i[Author ID1: at Wed Oct 31 13:26:00 2001 ]!)

107: char String::operator[](unsigned short offset) const

108: {

109: if (offset > itsLen)

110: return itsString[itsLen-1];

111: else

112: return itsString[offset];

113: }

114:

115: // tworzy nowy łańcuch przez dodanie bieżącego

116: // łańcucha do rhs

117: String String::operator+(const String& rhs)

118: {

119: unsigned short totalLen = itsLen + rhs.GetLen();

120: String temp(totalLen);

121: unsigned short i;

122: for ( i= 0; i<itsLen; i++)

123: temp[i] = itsString[i];

124: for (unsigned short j = 0; j<rhs.GetLen(); j++, i++)

125: temp[i] = rhs[j];

126: temp[totalLen]='\0';

127: return temp;

128: }

129:

130: // zmienia bieżący łańcuch, nic nie zwraca

131: void String::operator+=(const String& rhs)

132: {

133: unsigned short rhsLen = rhs.GetLen();

134: unsigned short totalLen = itsLen + rhsLen;

135: String temp(totalLen);

136: unsigned short i;

137: for (i = 0; i<itsLen; i++)

138: temp[i] = itsString[i];

139: for (unsigned short j = 0; j<rhs.GetLen(); j++, i++)

140: temp[i] = rhs[i-itsLen];

141: temp[totalLen]='\0';

142: *this = temp;

143: }

144:

145: int main()

146: {

147: String s1("poczatkowy test");

148: cout << "S1:\t" << s1.GetString() << endl;

149:

150: char * temp = "Hello World";

151: s1 = temp;

152: cout << "S1:\t" << s1.GetString() << endl;

153:

154: char tempTwo[20];

155: strcpy(tempTwo,"; milo tu byc!");

156: s1 += tempTwo;

157: cout << "tempTwo:\t" << tempTwo << endl;

158: cout << "S1:\t" << s1.GetString() << endl;

159:

160: cout << "S1[4]:\t" << s1[4] << endl;

161: s1[4]='x';

162: cout << "S1:\t" << s1.GetString() << endl;

163:

164: cout << "S1[999]:\t" << s1[999] << endl;

165:

166: String s2(" Inny lancuch");

167: String s3;

168: s3 = s1+s2;

169: cout << "S3:\t" << s3.GetString() << endl;

170:

171: String s4;

172: s4 = "Dlaczego to dziala?";

173: cout << "S4:\t" << s4.GetString() << endl;

174: return 0;

175: }

Wynik

S1: poczatkowy test

S1: Hello World

tempTwo: ; milo tu byc!

S1: Hello World; milo tu byc!

S1[4]: o

S1: Hellx World; milo tu byc!

S1[999]: !

S3: Hellx World; milo tu byc! Inny lancuch

S4: Dlaczego to dziala?

Analiza

Linie od 7. do 31. zawierają deklarację prostej klasy String. Linie od 11. do 13. zawierają trzy konstruktory: konstruktor domyślny, konstruktor kopiujący[Author ID1: at Wed Oct 31 13:27:00 2001 ]i[Author ID1: at Wed Oct 31 13:27:00 2001 ] oraz konstruktor otrzymujący istniejący łańcuch, zakończony znakiem null (w stylu C).

Klasa String przeciąża operator indeksu ([]), operator plus (+) oraz operator plus-równa się (+=). Operator indeksu jest przeciążony dwukrotnie: raz jako funkcja const zwracająca znak; drugi raz jako funkcja nie const zwracająca referencję do znaku. Wersja nie const jest używana w wyrażeniach takich, jak:

SomeString[4] = 'x';

tak, jak widać [Author ID1: at Wed Oct 31 13:27:00 2001 ]zieliśmy[Author ID1: at Wed Oct 31 13:27:00 2001 ]w linii 161. Dzięki temu mamy bezpośredni dostęp do każdego znaku w łańcuchu. Zwracana jest referencja do znaku, dzięki czemu funkcja wywołująca może nim manipulować.

Wersja const jest używana w przypadkach, gdy następuje odwołanie do stałego obiektu typu [Author ID1: at Wed Oct 31 13:28:00 2001 ]String, na przykład w implementacji konstruktora kopiującego[Author ID1: at Wed Oct 31 13:28:00 2001 ]i[Author ID1: at Wed Oct 31 13:28:00 2001 ] (linia 63.). Zauważ,[Author ID1: at Wed Oct 31 13:48:00 2001 ] że następuje odwołanie do rhs[i],[Author ID1: at Wed Oct 31 13:28:00 2001 ]; jednakże[Author ID1: at Wed Oct 31 13:28:00 2001 ] choć[Author ID1: at Wed Oct 31 13:28:00 2001 ] rhs jest zadeklarowane jako const String &. Dostęp do tego obiektu za pomocą funkcji składowej, nie będącej funkcją const, jest zabroniony. Dlatego operator indeksu musi być przeciążony za pomocą akcesora const.

Jeśli zwracane obiekty byłyby bardzo duże, mógłbyś zechcieć zadeklarować zwracaną wartość jako referencję const. Jednak ponieważ znak zajmuje tylko jeden bajt, nie ma takiej potrzeby.

Domyślny konstruktor jest zaimplementowany w liniach od 33. do 39. Tworzy on łańcuch, którego długość wynosi zero znaków. Zgodnie z konwencją, klasa String zwraca długość łańcucha bez końcowego znaku null. Tworzony łańcuch domyślny zawiera więc jedynie końcowy znak null.

Konstruktor kopiujący[Author ID1: at Wed Oct 31 13:29:00 2001 ]i[Author ID1: at Wed Oct 31 13:29:00 2001 ] został zaimplementowany w liniach od 63. do 70. Ustawia on długość nowego łańcucha zgodnie z długością łańcucha istniejącego, plus jeden bajt dla końcowego znaku null. Kopiuje każdy znak z istniejącego łańcucha do nowego łańcucha, po czym kończy nowy łańcuch znakiem null.

W liniach od 53. do 60. znajduje się implementacja konstruktora otrzymującego istniejący łańcuch w stylu C. Ten konstruktor jest podobny do konstruktora kopiując[Author ID1: at Wed Oct 31 13:29:00 2001 ]ego[Author ID1: at Wed Oct 31 13:49:00 2001 ]i[Author ID1: at Wed Oct 31 13:29:00 2001 ]. Długość istniejącego łańcucha wyznaczana jest w wyniku wywołania standardowej funkcji bibliotecznej strlen().

W linii 28. został zadeklarowany jeszcze jeden konstruktor, String(unsigned short), stanowiący prywatną funkcję składową. Odpowiada on zamierzeniom projektanta, zgodnie z którymi, żaden z klientów klasy nigdy nie powinien tworzyć łańcuchów typu String o określonej długości. Ten konstruktor istnieje tylko po to, by pomóc przy wewnętrznym tworzeniu egzemplarzy łańcuchów, na przykład w funkcji operator+= w linii 130. Opiszemy to dokładniej przy okazji omawiania działania funkcji operator+=.

Konstruktor String(unsigned short) wypełnia każdy element swojej tablicy wartością NULL. Dlatego w pętli dokonujemy sprawdzenia i <= len, a nie i < len.

Destruktor, zaimplementowany w liniach od 73. do 77., usuwa łańcuch znaków przechowywany przez klasę. Musimy pamiętać o użyciu nawiasów kwadratowych w wywołaniu operatora delete (aby usunięte zostały wszystkie elementy tablicy, a nie tylko pierwszy).

Operator przypisania najpierw sprawdza, czy prawa strona przypisania jest taka sama, jak lewa strona. Jeśli tak nie jest, bieżący łańcuch jest usuwany, po czym w jego miejsce tworzony jest i kopiowany nowy łańcuch. W celu umożliwienia przypisań w rodzaju:

String1 = String2 = String3;

zwracana jest referencja. Operator indeksu jest przeciążany dwukrotnie. W obu przypadkach przeprowadzane jest podstawowe sprawdzanie zakresów. Jeśli użytkownik próbuje odwołać się do znaku położonego poza końcem tablicy, zwracany jest ostatni znak znak[Author ID1: at Wed Oct 31 13:30:00 2001 ] (znajdujący się na pozycji len-1).[Author ID1: at Wed Oct 31 13:30:00 2001 ]

Linie od 117. do 127. implementują operator plus (+) jako operator konkatenacji (łączenia łańcuchów). Dzięki temu możemy napisać:

String3 = String1 + String2;

przypisując łańcuchowi String3 połączenie dwóch pozostałych łańcuchów. W tym celu funkcja operatora plus oblicza połączoną długość obu łańcuchów i tworzy tymczasowy łańcuch temp. To powoduje wywołanie prywatnego konstruktora, który otrzymuje wartość całkowitą i tworzy łańcuch wypełniony znakami null. Następnie znaki null są zastępowane przez zawartość obu łańcuchów. Łańcuch po lewej stronie (*this) jest kopiowany jako pierwszy; łańcuch po prawej stronie (rhs) kopiowany jest później.

Pierwsza pętla for przechodzi przez łańcuch po lewej stronie i przenosi każdy jego znak do nowego łańcucha. Druga pętla for przetwarza łańcuch po prawej stronie. Zauważ, że zmienna i cały czas wskazuje miejsce w łańcuchu docelowym, nawet wtedy, gdy zmienna j zlicza znaki łańcucha rhs.

Operator plus zwraca łańcuch tymczasowy poprzez wartość, która jest przypisywana łańcuchowi po lewej stronie przypisania (string1). Operator += działa na istniejącym łańcuchu — tj. na łańcuchu po lewej stronie instrukcji string1 += string2. Działa on tak samo, jak operator plus, z tym, że wartość tymczasowa jest przypisywana do bieżącego łańcucha (*this = temp w linii 142.).

Funkcja main() (w liniach od 145. do 175.) służy jako program testujący tę klasę. Linia 147. tworzy obiekt String za pomocą konstruktora, otrzymującego łańcuch w stylu C zakończony znakiem null. Linia 148. wypisuje jego zawartość za pomocą funkcji akcesora GetString(). Linia 150. tworzy kolejny łańcuch w stylu C. Linia 151. sprawdza operator przypisania, zaś linia 152. wypisuje wyniki.

Linia 154. tworzy trzeci łańcuch w stylu C, tempTwo. Linia 155. wywołuje funkcję strcpy() (w celu wypełnienia bufora znakami ; milo tu byc!). Linia 156. wywołuje operator += i dołącza tempTwo do istniejącego łańcucha s1. Linia 158. wypisuje wyniki.

W linii 160. odczytywany jest i wypisywany piąty znak łańcucha s1. W linii 161. jest mu przypisywana nowa wartość. Powoduje to wywołanie operatora indeksu (operatora [];[Author ID1: at Wed Oct 31 13:30:00 2001 ] w wersji nie const). Linia 162. wypisuje wynik, który pokazuje, że wartość znaku rzeczywiście uległa zmianie.

Linia 164. próbuje odwołać się do znaku za końcem tablicy. Ostatni znak w tablicy jest zwracany, zgodnie z projektem klasy.

Linie 166. i 167. tworzą kolejne dwa obiekty String, zaś linia 168. wywołuje operator dodawania. Wynik jest wypisywany w linii 169.

Linia 171. tworzy nowy obiekt String o nazwie s4. Linia 172. wywołuje operator przypisania. Linia 173. wypisuje wyniki. Być może zastanawiasz się: „Skoro operator przypisania jest zdefiniowany w linii 21. jako otrzymujący stałą referencję do obiektu String, ale [Author ID1: at Wed Oct 31 13:31:00 2001 ]to dlaczego w tym miejscu program przekazuje łańcuch w stylu C. Jak to możliwe?”

A oto odpowiedź na to pytanie: kompilator oczekuje obiektu String, lecz otrzymuje tablicę znaków. W związku z tym sprawdza, czy może stworzyć obiekt String z tego, co otrzymał. W linii 12. zadeklarowaliśmy konstruktor, który tworzy obiekt String z tablicy znaków. Kompilator tworzy tymczasowy obiekt String z tablicy znaków i przekazuje go do operatora przypisania. Proces ten nazywa się rzutowaniem niejawnym lub promocją. Gdyby nie został zadeklarowany i zaimplementowany konstruktor przyjmujący tablicę znaków, to [Author ID1: at Wed Oct 31 13:31:00 2001 ]takie przypisanie spowodowałoby błąd kompilacji.

Listy połączone i inne struktury

Tablice przypominają kontenery służące do przeprowadzek. Są one bardzo przydatnymi pojemnikami, ale mają określony rozmiar. Jeśli wybierzesz zbyt duży pojemnik, niepotrzebnie zmarnujesz miejsce. Jeśli wybierze pojemnik zbyt mały, jego zawartość wysypie się i powstanie bałagan.

Jednym ze sposobów rozwiązania tego problemu jest użycie listy połączonej. Lista połączona jest to struktura danych składająca się z małych pojemników, przystosowanych do łączenia się ze sobą w miarę potrzeb. Naszym celem jest napisanie klasy zawierającej pojedynczy obiekt naszych danych — na przykład jeden obiekt CAT lub jeden obiekt Rectangle — która może wskazywać na następny pojemnik. Tworzymy jeden pojemnik dla każdego obiektu, który chcemy przechować i w miarę potrzeb łączymy je ze sobą.

Takie pojemniki są nazywane węzłami (ang. node). Pierwszy węzeł listy jest nazywany głową (ang. head), zaś ostatni — ogonem (ang. tail).

Listy występują w trzech podstawowych odmianach. W kolejności od najmniej do najbardziej złożonej, są to

• lista połączona pojedynczo,

• lista połączona podwójnie,

• drzewo.

W liście połączonej pojedynczo każdy węzeł wskazuje na węzeł następny (nie wskazuje poprzedniego). Aby odszukać określony węzeł, musimy zacząć od początku listy, tak jak w zabawie w poszukiwanie skarbów („Następny węzeł jest pod fotelem”). Lista połączona podwójnie umożliwia poruszenie się wzdłuż łańcucha węzłów do przodu i do tyłu. Drzewo jest złożoną strukturą zbudowaną z węzłów. Każdy węzeł może wskazywać w dwóch lub więcej kierunkach. Te trzy podstawowe struktury przedstawia rysunek 13.5.

Rys. 13.5. Listy połączone

Analiza listy połączonej

W tym podrozdziale omówimy działanie listy połączonej. Lista ta posłuży nam nie tylko jako przykład tworzenia złożonych struktur, ale przede wszystkim jako przykład użycia dziedziczenia, polimorfizmu i kapsułkowania w celu zarządzania większymi projektami.

Przeniesienie odpowiedzialności

Podstawowym celem programowania zorientowanego obiektowo jest to, by każdy obiekt wykonywał dobrze jedną rzecz, zaś wszystkie inne czynności przekazywał innym obiektom.

Doskonałym przykładem zastosowania tej idei w praktyce jest samochód: zadaniem silnika jest dostarczanie siły. Jej dystrybucja nie jest już zadaniem silnika, ale układu napędowego. Skręcanie nie jest zadaniem ani silnika, ani układu napędowego, tylko kół.

Dobrze zaprojektowana maszyna składa się z mnóstwa małych, dobrze określonych[Author ID1: at Wed Oct 31 13:32:00 2001 ]przemyślanych[Author ID1: at Wed Oct 31 13:32:00 2001 ] części, z których każda wykonuje swoje zadanie i współpracuje z innymi częściami w celu osiągnięcia wspólnego celu. Dobrze zaprojektowany program działa bardzo podobnie: każda klasa wykonuje swoje niewielkie operacje, ale w połączeniu z innymi może wykonać naprawdę skomplikowane zadanie.

Części składowe

Lista połączona składa się z węzłów. Pojęcie klasy węzła będzie abstrakcyjne; do wykonania zadania użyjemy trzech podtypów. Lista [Author ID1: at Wed Oct 31 13:33:00 2001 ]B[Author ID1: at Wed Oct 31 13:33:00 2001 ]b[Author ID1: at Wed Oct 31 13:33:00 2001 ]ędzie też[Author ID1: at Wed Oct 31 13:33:00 2001 ]o[Author ID1: at Wed Oct 31 13:33:00 2001 ] zawierała [Author ID1: at Wed Oct 31 13:33:00 2001 ]węzeł głowy[Author ID1: at Wed Oct 31 13:34:00 2001 ]czołowy[Author ID1: at Wed Oct 31 13:33:00 2001 ], którego zadaniem będzie zarządzanie głową listy, węzeł ogona (domyśl się, do czego posłuży!) oraz zero lub więcej węzłów wewnętrznych. Węzły wewnętrzne będą odpowiedzialne za dane przechowywane wewnątrz listy.

Zauważ, że dane i lista są od siebie zupełnie niezależne. Teoretycznie, możesz przechowywać w liście dane dowolnego rodzaju, ponieważ to nie dane są ze sobą połączone, ale węzły, które je przechowują.

Program sterujący nie wie niczego o węzłach, ponieważ operuje na liście. Jednak sama lista wykonuje niewiele pracy, delegując większość zadań na węzły.

Kod programu przedstawia listing 13.13; za moment omówimy jego szczegóły.

Listing 13.13. Lista połączona

0: // ***********************************************

1: // PLIK: Listing 13.13

2: //

3: // PRZEZNACZENIE: Demonstruje listę połączoną

4: // UWAGI:

5: //

6: // COPYRIGHT: Copyright (C) 1998 Liberty Associates, Inc.

7: // All Rights Reserved

8: //

9: // Demonstruje obiektowo zorientowane podejście do list

10: // połączonych. Lista deleguje pracę na węzły.

11: // Węzeł jest abstrakcyjnym typem danych. Używane są trzy

12: // typy węzłów: węzły głowy, węzły ogona oraz węzły

13: // wewnętrzne. Tylko węzły wewnętrzne przechowują dane.

14: //

15: // Klasa data została stworzona jako obiekt danych

16: // przechowywany na liście połączonej.

17: //

18: // ***********************************************

19:

20:

21: #include <iostream>

22: using namespace std;

23:

24: enum { kIsSmaller, kIsLarger, kIsSame};

25:

26: // Klasa danych do umieszczania w liście połączonej.

27: // Każda klasa w tej połączonej liście musi posiadać dwie metody:

28: // Show (wyświetla wartość) a[Author ID1: at Wed Oct 31 13:35:00 2001 ] [Author ID1: at Wed Oct 31 13:50:00 2001 ]oraz[Author ID1: at Wed Oct 31 13:35:00 2001 ]

29: // Compare (zwraca względną pozycję)

30: class Data

31: {

32: public:

33: Data(int val):myValue(val){}

34: ~Data(){}

35: int Compare(const Data &);

36: void Show() { cout << myValue << endl; }

37: private:

38: int myValue;

39: };

40:

41: // Compare jest używane do podjęcia decyzji, w którym

42: // miejscu listy powinien znaleźć się dany obiekt.

43: int Data::Compare(const Data & theOtherData)

44: {

45: if (myValue < theOtherData.myValue)

46: return kIsSmaller;

47: if (myValue > theOtherData.myValue)

48: return kIsLarger;

49: else

50: return kIsSame;

51: }

52:

53: // wstępne deklaracje

54: class Node;

55: class HeadNode;

56: class TailNode;

57: class InternalNode;

58:

59: // ADT reprezentuje obiekt węzła listy

60: // Każda klasa potomna musi przesłonić metody Insert i Show

61: class Node

62: {

63: public:

64: Node(){}

65: virtual ~Node(){}

66: virtual Node * Insert(Data * theData)=0;

67: virtual void Show() = 0;

68: private:

69: };

70:

71: // To jest węzeł przechowujący rzeczywisty obiekt.

72: // W tym przypadku obiekt jest typu Data.

73: // Gdy poznamy szablony, dowiemy się, jak można

74: // to uogólnić.

75: class InternalNode: public Node

76: {

77: public:

78: InternalNode(Data * theData, Node * next);

79: ~InternalNode(){ delete myNext; delete myData; }

80: virtual Node * Insert(Data * theData);

81: // delegujemy!

82: virtual void Show() { myData->Show(); myNext->Show(); }

83:

84: private:

85: Data * myData; // dane jako takie

86: Node * myNext; // wskazuje następny węzeł w liście połączonej

87: };

88:

89: // Konstruktor dokonuje jedynie inicjalizacji

90: InternalNode::InternalNode(Data * theData, Node * next):

91: myData(theData),myNext(next)

92: {

93: }

94:

95: // Esencja listy

96: // Gdy umieścisz nowy obiekt na liście, jest on[Author ID1: at Wed Oct 31 13:35:00 2001 ]

97: // przekazywany do węzła, który stwierdza, gdzie

98: // powinien on zostać umieszczony i wstawia go do listy

99: Node * InternalNode::Insert(Data * theData)

100: {

101:

102: // czy nowy element jest większy czy mniejszy niż ja?

103: int result = myData->Compare(*theData);

104:

105:

106: switch(result)

107: {

108: // konwencja: gdy jest taki sam jak ja, wstawiamy wcześniej

109: case kIsSame: // przechodzimy dalej

110: case kIsLarger: // nowe dane trafiają przede mnie

111: {

112: InternalNode * dataNode = new InternalNode(theData, this);

113: return dataNode;

114: }

115:

116: // gdy jest większy niż ja, przekazuję go do następnego węzła

117: // i niech ON się tym zajmie.

118: case kIsSmaller:

119: myNext = myNext->Insert(theData);

120: return this;

121: }

122: return this;

123: }

124:

125:

126: // Węzeł ogona jest tylko wartownikiem.

127:

128: class TailNode : public Node

129: {

130: public:

131: TailNode(){}

132: ~TailNode(){}

133: virtual Node * Insert(Data * theData);

134: virtual void Show() { }

135:

136: private:

137:

138: };

139:

140: // Gdy dane trafiają do mnie, muszą być wstawione wcześniej,

141: // gdyż jestem ogonem i za mną NIC nie ma.

142: Node * TailNode::Insert(Data * theData)

143: {

144: InternalNode * dataNode = new InternalNode(theData, this);

145: return dataNode;

146: }

147:

148: // Węzeł głowy nie zawiera danych; wskazuje jedynie

149: // na sam początek listy.

150: class HeadNode : public Node

151: {

152: public:

153: HeadNode();

154: ~HeadNode() { delete myNext; }

155: virtual Node * Insert(Data * theData);

156: virtual void Show() { myNext->Show(); }

157: private:

158: Node * myNext;

159: };

160:

161: // Gdy tylko głowa zostanie stworzona,

162: // natychmiast tworzy ogon.

163: HeadNode::HeadNode()

164: {

165: myNext = new TailNode;

166: }

167:

168: // Przed głowę nic nie wstawiamy nic, zatem

169: // po prostu przekazujemy dane do następnego węzła.

170: Node * HeadNode::Insert(Data * theData)

171: {

172: myNext = myNext->Insert(theData);

173: return this;

174: }

175:

176: // Odbieram słowa uznania, a sama nic nie robię.

177: class LinkedList

178: {

179: public:

180: LinkedList();

181: ~LinkedList() { delete myHead; }

182: void Insert(Data * theData);

183: void ShowAll() { myHead->Show(); }

184: private:

185: HeadNode * myHead;

186: };

187:

188: // Przy narodzinach tworzę węzeł głowy.

189: // Tworzy on węzeł ogona.

190: // Tak więc pusta lista wskazuje na głowę, która

191: // wskazuje na ogon; pomiędzy nimi nie ma nic innego.

192: LinkedList::LinkedList()

193: {

194: myHead = new HeadNode;

195: }

196:

197: // Delegujemy, delegujemy, delegujemy

198: void LinkedList::Insert(Data * pData)

199: {

200: myHead->Insert(pData);

201: }

202:

203: // testowy program sterujący

204: int main()

205: {

206: Data * pData;

207: int val;

208: LinkedList ll;

209:

210: // prosimy użytkownika o wpisanie kilku wartości

211: // i umieszczamy je na liście

212: for (;;)

213: {

214: cout << "Jaka wartosc? (0 aby zakonczyc): ";

215: cin >> val;

216: if (!val)

217: break;

218: pData = new Data(val);

219: ll.Insert(pData);

220: }

221:

222: // teraz przechodzimy listę i wyświetlamy wartości

223: ll.ShowAll();

224: return 0; // ll wychodzi poza zakres i zostaje zniszczone!

225: }

Wynik

Jaka wartosc? (0 aby zakonczyc): 5

Jaka wartosc? (0 aby zakonczyc): 8

Jaka wartosc? (0 aby zakonczyc): 3

Jaka wartosc? (0 aby zakonczyc): 9

Jaka wartosc? (0 aby zakonczyc): 2

Jaka wartosc? (0 aby zakonczyc): 10

Jaka wartosc? (0 aby zakonczyc): 0

2

3

5

8

9

10

Analiza

Pierwszą rzeczą, jaką należy zauważyć, jest instrukcja [Author ID1: at Wed Oct 31 13:35:00 2001 ]wyliczeniowa[Author ID1: at Wed Oct 31 13:35:00 2001 ]e[Author ID1: at Wed Oct 31 13:35:00 2001 ] definiująca [Author ID1: at Wed Oct 31 13:35:00 2001 ]zawierające[Author ID1: at Wed Oct 31 13:36:00 2001 ] trzy stałe: kIsSmaller (jest mniejsze), kIsLarger (jest większe) oraz kIsSame (jest takie same). Każdy obiekt, który może być przechowywany na tej liście połączonej, musi obsługiwać metodę Compare(). Te stałe są zwracane właśnie przez tę metodę.

Dla przykładu, w liniach od 30. do 39. została stworzona klasa Data (dane), zaś jej metoda Compare() została zaimplementowana w liniach od 41. do 51. Obiekt typu Data przechowuje wartość i może porównywać się z innymi obiektami Data. Oprócz tego obsługuje metodę Show(), która wyświetla wartość obiektu Data.

Najprostszym sposobem na zrozumienie działania listy połączonej jest przeanalizowanie ilustrującego ją przykładu. W linii 203. rozpoczyna się testowy program sterujący; w linii 206. deklarowany jest wskaźnik do obiektu Data, zaś w linii 208. definiowana jest lokalna lista połączona.

Gdy tworzona jest lista połączona, wywoływany jest jej konstruktor, zaczynający się w linii 192. Jedyną pracą wykonywaną w tym konstruktorze jest zaalokowanie obiektu HeadNode (węzeł głowy) i przypisanie mu[Author ID1: at Wed Oct 31 13:36:00 2001 ]jego[Author ID1: at Wed Oct 31 13:36:00 2001 ] adresu do wskaźnika przechowywanego w połączonej liście w linii 185.

Tworzenie obiektu HeadNode powoduje wywołanie konstruktora klasy HeadNode zawartego w liniach od 163. do 166. To z kolei powoduje zaalokowanie obiektu TailNode (węzeł głowy) i przypisanie jego adresu do wskaźnika myNext (mój następny) w węźle głowy. Tworzenie obiektu TailNode powoduje wywołanie konstruktora tej klasy zdefiniowanego w linii 131., który jest funkcją inline i nie robi nic.

Dzięki zwykłemu zaalokowaniu listy połączonej na stosie, tworzona jest sama lista, węzły głowy i ogona oraz ustanawiane są powiązania pomiędzy nimi. Ilustruje to rysunek 13.6.

Rys. 13.6. Lista połączona po jej utworzeniu

Linia 212. rozpoczyna pętlę nieskończoną. Użytkownik jest proszony o wpisanie wartości dodawanych do listy połączonej. Może on [Author ID1: at Wed Oct 31 13:51:00 2001 ]dodać dowolną ilość wartości [Author ID1: at Wed Oct 31 13:36:00 2001 ]t[Author ID1: at Wed Oct 31 13:36:00 2001 ]yle wartości, ile chce[Author ID1: at Wed Oct 31 13:37:00 2001 ]; wpisanie wartości 0 powoduje zakończenie pobierania danych. Kod w linii 216. sprawdza wprowadzaną wartość; po natrafianiu na wartość 0 powoduje on wyjście z pętli.

Jeśli wartość jest różna od zera, w linii 218. tworzony jest nowy obiekt typu Data, który w linii 219. jest wstawiany do listy. Dla zilustrowania tego przykładu załóżmy, że użytkownik wprowadził wartość 15. Powoduje to wywołanie metody Insert() (wstaw) w linii 198.

Lista połączona (klasa LinkedList) natychmiast przenosi odpowiedzialność za wstawienie obiektu na swój węzeł głowy. To wywołuje metodę Insert() z linii 170. Z kolei [Author ID1: at Wed Oct 31 13:37:00 2001 ]W[Author ID1: at Wed Oct 31 13:37:00 2001 ]w[Author ID1: at Wed Oct 31 13:37:00 2001 ]ęzeł głowy natychmiast przekazuje odpowiedzialność za wstawienie obiektu [Author ID1: at Wed Oct 31 13:37:00 2001 ]do węzła wskazywanego przez składową myNext (mój następny). W tym (pierwszym) przypadku, składowa ta[Author ID1: at Wed Oct 31 13:38:00 2001 ],[Author ID1: at Wed Oct 31 13:38:00 2001 ] wskazuje ona[Author ID1: at Wed Oct 31 13:38:00 2001 ] na węzeł ogona (pamiętajmy, że podczas tworzenia węzła głowy zostało stworzone łącze do węzła ogona). Tak więc zostaje wywołana metoda Insert() z linii 142.

Metoda TailNode::Insert() wie, że obiekt, który otrzymała, musi być wstawiony bezpośrednio przed jej obiektem — tj. nowy obiekt znajdzie się na liście tuż przed węzłem ogona. Zatem, w linii 144. tworzy ona [Author ID1: at Wed Oct 31 13:39:00 2001 ]nowy obiekt InternalNode (węzeł wewnętrzny), przekazując mu dane oraz wskaźnik do siebie. To powoduje wywołanie konstruktora klasy InternalNode, zdefiniowanego w linii 90.

Konstruktor klasy InternalNode inicjalizuje tylko swój wskaźnik Data za pomocą adresu otrzymanego obiektu Data oraz inicjaliz[Author ID1: at Wed Oct 31 13:39:00 2001 ]uje [Author ID1: at Wed Oct 31 13:39:00 2001 ]swój wskaźnik myNext za pomocą otrzymanego adresu węzła. W tym przypadku nowy węzeł wewnętrzny będzie wskazywał na węzeł ogona (pamiętajmy, że węzeł ogona przekazał mu swój wskaźnik this).

Gdy utworzony zostanie nowy węzeł InternalNode, w linii 144. jego adres jest przypisywany do wskaźnika dataNode i właśnie ten adres jest zwracany z metody[Author ID1: at Wed Oct 31 13:39:00 2001 ] TailNode::Insert(). Wracamy więc do metody HeadNode::Insert(), w której adres węzła InternalNode jest przypisywany do wskaźnika myNext węzła głowy (w linii 172.). Na zakończenie, adres węzła głowy jest zwracany do listy połączonej, gdzie w linii 200. jest odrzucany (nie robimy z nim nic, ponieważ lista połączona znała adres swojego węzła głowy już wcześniej).

Dlaczego zawracamy sobie głowę zwracaniem adresu, który nie jest używany? Metoda Insert jest zadeklarowana w klasie bazowej, Node. Zwracana wartość jest potrzebna w innych implementacjach. Gdy zmienisz zwracaną wartość metody HeadNode::Insert(), spowodujesz błąd kompilacji; prościej jest więc po prostu zwrócić adres węzła głowy i pozwolić, by lista połączona go zignorowała.

Co się więc stało? Dane zostały wstawione do listy. Lista przekazała je do głowy. Głowa, „na ślepo”, przekazała dane do pierwszego wskazywanego przez siebie elementu. W tym (pierwszym) przypadku, głowa wskazywała na ogon. Ogon natychmiast stworzył nowy węzeł wewnętrzny, inicjalizując go tak, by wskazywał na ogon. Następnie ogon zwrócił głowie adres nowego węzła, która zmodyfikowała swój wskaźnik myNext tak, aby wskazywał na nowy węzeł. Gotowe! Dane na liście znajdują się we właściwym miejscu, co ilustruje rysunek 13.7.

Rys. 13.7. Lista połączona po wstawieniu pierwszego węzła

Po wstawieniu pierwszego węzła, sterowanie programu powraca do linii 214., gdzie wprowadzane są kolejne dane. Dla przykładu załóżmy, że użytkownik wpisał wartość 3. Powoduje to stworzenie w linii 218. nowego obiektu typu Data, który jest wstawiany do listy w linii 219.

W linii 200. lista ponownie przekazuje dane do swojego węzła głowy. Z kolei metoda HeadNode::Insert() przekazuje nową wartość do węzła wskazywanego przez swój wskaźnik myNext. Jak wiemy, w tym momencie wskaźnik ten wskazuje węzeł zawierający obiekt Data o wartości 15. Powoduje to wywołanie metody InternalNode::Insert() z linii 99.

W linii 103. obiekt InternalNode używa wskaźnika myData, aby dla własnego obiektu Data (tego o wartości 15) wywołać za pomocą otrzymanego nowego obiektu Data (tego o wartości 3) metodę Compare(). To powoduje wywołanie metody InternalNode::Compare() zdefiniowanej w linii 43.

Obie wartości zostają porównane, a ponieważ myValue ma wartość 15, zaś theOtherData.myValue ma wartość 3, zwróconą wartością jest kIsLarger. To powoduje, że program przechodzi do linii 112.

Dla nowego obiektu Data tworzony jest nowy węzeł InternalNode. Nowy węzeł będzie wskazywał na bieżący obiekt InternalNode, a metoda InternalNode::Insert() zwróci do obiektu HeadNode adres nowego węzła. Zatem nowy węzeł, którego wartość obiektu danych jest mniejsza od wartości obiektu danych węzła bieżącego, zostanie wstawiony do listy przed węzłem bieżącym. Cała lista wygląda w tym momencie tak, jak na rysunku 13.8.

Rys. 13.8. Lista połączona po wstawieniu drugiego węzła

W trakcie trzeciego wykonania pętli użytkownik wpisał wartość 8. Jest ona większa od 3, ale mniejsza od 15, więc powinna być wstawiona pomiędzy dwa istniejące już węzły. Działanie programu będzie podobne do przedstawionego w poprzednim przykładzie, z tą różnicą, że gdy dojdzie do porównania wartości danych z wartością 3, zamiast zwrócić stałą kIsLarger, funkcja zwróci wartość kIsSmaller (co oznacza, że obiekt o wartości 3 jest mniejszy od nowego obiektu, którego wartość wynosi 8).

To spowoduje, że metoda InternalNode::Insert() przejdzie do linii 119. Zamiast tworzyć nowy węzeł i wstawiać go, obiekt InternalNode po prostu przekaże nowe dane do metody Insert tego węzła, na który wskazuje akurat jego zmienna myNext. W tym przypadku zostanie więc wywołana metoda Insert() tego obiektu InternalNode, którego obiektem danych jest wartość 15.

Ponownie odbywa się porównanie i tworzony jest nowy obiekt InternalNode. Będzie wskazywał on na węzeł, którego wartością danych jest 15, zaś jego adres zostanie przekazany wstecz do węzła, którego wartością danych jest 3 (w linii 119.).

Spowoduje to,[Author ID1: at Wed Oct 31 13:40:00 2001 ] że nowy węzeł zostanie wstawiony we właściwe miejsce na liście.

Jeśli to możliwe, powinieneś prześledzić w swoim debuggerze proces wstawiania kolejnych węzłów. Powinieneś zobaczyć, jak te metody wzajemnie się wywołują i odpowiednio dostosowują wskaźniki.

Czego się nauczyłaś, Dorotko?

„Jeśli kiedykolwiek pójdę za głosem serca, nie wyjdę poza swoje podwórko”. Nie ma to jak w domu i nie ma to jak programowanie proceduralne. W programowaniu proceduralnym metoda kontrolująca sprawdza dane i wywołuje funkcje.

W metodzie obiektowej każdy obiekt ma swoje ściśle określone zadanie. Lista połączona odpowiada za zarządzanie węzłem głowy. Węzeł głowy natychmiast przekazuje nowe dane do następnego wskazywanego przez siebie węzła, bez względu na to, czym jest ten węzeł.

Węzeł ogona tworzy nowy węzeł i wstawia go do listy za każdym razem, gdy otrzyma dane. Potrafi tylko jedno: jeśli coś do niego dotrze, wstawia to tuż przed sobą.

Węzły wewnętrzne są nieco bardziej skomplikowane; proszą swój istniejący obiekt o porównanie się z nowym obiektem. W zależności od wyniku tego porównania, wstawiają go przed sobą lub po prostu przekazują do następnego węzła na liście.

Zauważ, że węzeł InternalNode nie ma pojęcia o sposobie przeprowadzenia porównania; należy to wyłącznie do obiektu danych. InternalNode wie jedynie, że powinien poprosić obiekt danych o dokonanie porównania w celu otrzymania jednej z trzech odpowiedzi. Na podstawie otrzymanej odpowiedzi wstawia obiekt do listy; w przeciwnym razie przekazuje go dalej, nie dbając o to, gdzie w końcu dotrze.

Kto więc tu rządzi? W dobrze zaprojektowanym programie zorientowanym obiektowo nikt nie rządzi. Każdy obiekt wykonuje własną, ograniczoną pracę, zaś w ogólnym efekcie otrzymujemy sprawnie działającą maszynę.

Klasy tablic

Napisanie własnej klasy tablicowej[Author ID1: at Wed Oct 31 13:40:00 2001 ]y[Author ID1: at Wed Oct 31 13:40:00 2001 ] ma wiele zalet w porównaniem z korzystaniem z tablic wbudowanych. Jako początkujący programista, możesz zabezpieczyć program przed przepełnieniem tablicy. Możesz także wziąć pod uwagę stworzenie własnej klasy tablicowej[Author ID1: at Wed Oct 31 13:40:00 2001 ],y[Author ID1: at Wed Oct 31 13:40:00 2001 ] dynamicznie zmieniającej rozmiar: tuż po utworzeniu mogłaby ona zawierać tylko jeden element i zwiększać rozmiar w miarę potrzeb, podczas działania programu.

W przypadku, gdy zechcesz posortować lub uporządkować elementy tablicy w jakiś inny sposób, możesz wykorzystać kilka różnych przydatnych odmian tablic. Do najpopularniejszych z nich należą:

• zbiór uporządkowany (ordered collection): każdy element jest ułożony w odpowiedniej [Author ID1: at Wed Oct 31 13:41:00 2001 ]kolejności,

• zestaw (set): każdy element występuje tylko raz,

• słownik (dictionary): wykorzystuje on dopasowane do siebie pary, w których jedna wartość pełni rolę klucza służącego do pobierania drugiej wartości,

• rzadka tablica (sparse array): umożliwia używanie bardzo szerokiego zakresu indeksów, ale pamięć zajmują tylko te elementy, które rzeczywiście zostały dodane do tablicy. Możesz poprosić o element SparseArray[5] lub SparseArray[200], a mimo to pamięć zostanie zaalokowana tylko dla niewielkiej ilości elementów,

• torba (bag): nieuporządkowany zbiór, którego elementy są dodawane i zwracane w przypadkowej kolejności.

Przeciążając operator indeksu ([]), możesz zamienić listę połączoną w zbiór uporządkowany. Odrzucając duplikaty, możesz zamienić zbiór w zestaw. Jeśli każdy obiekt na liście posiada parę dopasowanych wartości, możesz użyć listy połączonej do zbudowania słownika lub rzadkiej tablicy.

2 Część I ♦ Podstawy obsługi systemu WhizBang (Nagłówek strony)

2 F:\korekta\r13-06.doc

---