r13.pdf

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

jej wartościami.

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

0: //Listing 13.1 - Tablice

1: #include <iostream>

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 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

4: #include <iostream>

5: using namespace std;

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.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: