Podręcznik

1.2. Tablice dynamiczne

Na kursie Programowania dowiedzieliście się w jaki sposób zadeklarować tablicę. Były to jednak tablice statyczne, których rozmiar musiał być określony na etapie kompilacji aplikacji. Możliwa więc była deklaracja tablicy w następujący sposób:

const int n=10;
int tab[n];

Rozmiar tablicy n jest w naszym przypadku stały. Jeśli jednak nie wiemy z góry, ile elementów będziemy umieszczać w tablicy, musimy ją rezerwować niepotrzebnie dużą, na zapas (podając dużą wartość stałej n) - niekiedy nam się to przyda, ale często elementy tablicy zajmą w niej mały fragment i cały duży obszar pamięci pozostanie niepotrzebnie zarezerwowany. Aby temu zaradzić, aż się prosi, by najpierw dowiedzieć się od użytkownika, ile elementów ma mieć tablica, a potem dopiero przydzielić jej pamięć. To oznacza jednak, że taką rezerwację należy przeprowadzić w trakcie działania programu - będzie to więc dynamiczna rezerwacja pamięci. Nie możemy jej jednak wykonać w taki sposób:

int n;
cin >> n;
int tab[n];  // TAK NIE WOLNO !!!  taki zapis oznacza tablicę statyczną

W celu zadeklarowania tablicy o określonym w trakcie działania aplikacji rozmiarze należy dokonać dynamicznej alokacji pamięci oraz deklaracji tablicy dynamicznej. Poniżej przedstawiono kod aplikacji, który umożliwia deklarację tablicy dynamicznej jednowymiarowej o rozmiarze n.

int n;
cout << "Podaj rozmiar tablicy" << endl; 
cin >> n;

int* tab = new int[n];

for (int i=0;i<n;i++){
     cin >> tab[i]; // Wczytywanie danych do tablicy dynamicznej o rozmiarze n
}

delete []tab;

Jak widzimy na podanym przykładzie do tablicy dynamicznej możemy odwoływać się jak do tablicy statycznej tzn. za pośrednictwem indeksów. Na końcu musimy także zadbać o usunięcie tablicy alokowanej dynamicznie za pomocą operatora [].
W przypadku usuwania tablicy nalezy pamietać o podaniu nawiasów [] po słowie kluczowym delete. Dzięki temu usunięte zostaną wszystkie elementy tablicy dynamicznej. Wywołanie operatora bez nawiasów spowoduje usunięcie jedynie pierwszego elementu tablicy. We wskaźniku w przypadku tablicy przechowywany jest adres pierwszego elementu tablicy.

Tablica jest przechowywana w sposób ciągły. Każdy kolejny element znajduje się zaraz za poprzednim. Tablica int tab[5] zawiera 5 elementów. Typ int zajmuje 4 bajty (zależy od architektury, ale na większości współczesnych systemów jest to prawdziwe). Adres początkowy tablicy to 0x1000.  tab[0] ma adres 0x1000, a wartość 10. tab[1] ma adres 0x1004 (0x1000 + 1 * 4), a wartość 20.

Jeśli int* ptr = tab;, to:

• ptr wskazuje na 0x1000 (adres tab[0]),
  
• ptr + 1 wskazuje na 0x1004 (adres tab[1]).
  

Możliwe jest więc odwołanie do poszczególnych wartości w tablicy za pośrednictwem zmiany adresu wskazującego na początek tablicy.

Dodanie wartości 1 do adresu T oznacza powiększenie adresu o rozmiar elementu pamiętanego w tablicy, czyli wyznaczenie adresu elementu następnego w tablicy - wiemy przecież, że są one poukładane za sobą w spójnym obszarze pamięci.

Mozliwe jest także deklarowanie tablic dynamicznych z większą liczbą wymiarów. Poniżej przedsatwiono kod aplikacji, który umożliwia deklarację tablicy dwuwymiarowej dynamicznej.

int w,k;
cout << "Podaj rozmiar tablicy w i k" << endl; 
cin >> w >> k;

// Deklaracja tablicy dwuwymiarowej w x k

int** tab = new int*[w];

for (int i=0;i<w;i++){
     tab[i]=new int[k]
}

// Odwołanie do elementów tablicy - wczytywanie danych

for (int i=0;i<w;i++){
     for (int i=0;i<k;i++){
          cin >> tab[i][j];
     }
}

// Usuwanie tablicy w x k
for (int i=0;i<w;i++){
     delete []tab[i];
}
delete []tab;

Przy deklarowaniu tablicy dynamicznej dwuwymiarowej Najpierw alokujemy pamięć na wskaźnik do wskaźników (int** tab). Następnie, dla każdego wiersza (pierwszy wymiar), alokujemy pamięć na poszczególne elementy (drugi wymiar). Odwołanie do poszczególnych elementów tablicy możemy zademonstrować na rysunku.

Oczywiście możliwe jest także odwołanie do poszczególnych elementów za pomoca indeksów.  Aby zwolnić pamięć, musimy wykonać delete[] dla każdego wiersza (alokowanego za pomocą new int[k]), a potem usunąć samą tablicę wskaźników (delete[] tab).  Dotychczasowa wiedza to jedynie podstawy operowania wskaźnikami. Wskaźniki oraz bezpośredni dostęp do pamięci w języku C++ oferują ogromne możliwości i znajdują szerokie zastosowanie. Przedstawiliśmy ich użycie na przykładzie tablic, lecz ponieważ nasz materiał nie obejmuje pełnego kursu C++, temat ten pozostawiamy na tym etapie. W kolejnym rozdziale poruszymy zagadnienia związane z jedną z podstawowych struktur danych jakim jest lista jednokierunkowa.