Strona główna » Kursy » Kurs C++ » Dynamiczne Tablice w C++
new
 

Dynamiczne Tablice w C++

Wstęp

Dane programów wykonywanych w komputerze są przechowywane w pamięci RAM (ang. Random Access Memory). Dotychczas napisane programy, choć w sposób ukryty, korzystały z niej podczas deklaracji funkcji, a później odwoływały się tam w celu odczytania lub modyfikacji zapisanych danych. Jednak programy nie wiedziałyby gdzie zapisać lub skąd odczytać jeśli nie będą wiedziały gdzie dane zostały zapisane.

Podczas uruchomienia napisanej aplikacji program deklaruje miejsce w pamięci pod adresy wykorzystywanych w programie zmiennych. W praktyce oznacza to, że w celu zadeklarowania zmiennej wysyła do systemu żądanie o adres wolnego miejsca w pamięci podając przy tym jak dużo pamięci potrzebuje i w wyniku tego otrzymuje adres. Odwołując się do tego adresu program może tam przechowywać dowolne informacje. Należy tu zauważyć, że wszystkie dane są przechowywane tak samo, ale to program decyduje jak je interpretować.

Na zakończenie działania program zwalania użyte zasoby poprzez wyrejestrowanie danego adresu z systemu. W ten sposób system wie, że daną część pamięci może przydzielić innemu programowi. Jednak w przypadku, gdy program zadeklaruje użycie pewnej części pamięci, ale jej nie zwolni to powstają tzw. wycieki pamięci. Z pozoru niegroźne, ponieważ po ponownym uruchomieniu komputera nie ma po nich śladu. Jednak powodują, że komputer ma mniej dostępnej pamięci, a to w rezultacie prowadzi do niestabilnej pracy całego systemu.

Tablica

Tworzenie

Dynamiczna tablica to zarezerwowane miejsce w pamięci, które pozwala przechowywać określoną ilość danych konkretnego typu. Jest ona stosowana ze względu na to, że bardzo często nie ma potrzeby, aby program od samego początku wykorzystywał bardzo dużo pamięci. W celu zadeklarowania nowej tablicy dynamicznego należy użyć słowa kluczowego new:

  1. typ* nazwa = new typ[ile];

W celu zadeklarowania tablic dynamicznej należy podać najpierw typ przechowywanej zmiennej, potem postawić gwiazdkę. Oznacza to, że tablica przechowuje wskaźniki. Potem należy wpisać nazwę tablicy i przypisać do niej wartość wygenerowaną przez słowo kluczowe new, które wie, że ma zadeklarować dla podanego typu ile miejsc.

Warto tutaj zwrócić uwagę na fakt, że deklarowana tablica jest tablicą wskaźników (tj. adresów pamięci). Oznacza to, że wartości niekoniecznie muszą być zapisane jedna po drugiej w pamięci to wskaźniki tak. Wynika to z faktu, że każdy typ wymaga innego rozmiaru pamięci.

Pobieranie elementu

Zmienna, którą od tej pory można operować w programie też jest wskaźnikiem na inne wskaźniki. W praktyce oznacza to, że odwołując się do danej tablicy pytamy o jej miejsce w pamięci, które wskaże gdzie zapisany jest dany element. Aby odwołać się do wybranego elementu wystarczy:

  1. nazwa[ktory]

W celu odczytania elementu o indeksie ktory wystarczy podać nazwę funkcji i w nawiasach kwadratowych podać żądany indeks. W tym momencie program odczyta pozycję tablicy w pamięci przesunie się o ktory pozycji dalej i odczytać wartość wskaźnika, który już wskaże konkretne miejsce w pamięci z danymi.

W tym momencie można sobie zadać pytanie czy wskaźnik jest liczbą? Odpowiedź brzmi tak każdy obiekt w pamięci jest adresowany liczbą, który reprezentuje stała ilość bitów. W ten sposób program odwołując się do konkretnego miejsca w pamięci wie, że żaden inny program nie zapisuje danych w tym miejscu. No chyba, że innym programem jest wirus, który stara się zakłócić działanie programów.

Zwalnianie zasobów

Bardzo ważne jest, aby pamiętać, że ile jest słów new tyle powinno być również delete. Jest to ten moment kiedy program wyrejestruje zasoby i pozwoli systemu na przydzielenie ich innemu programowi.

  1. delete nazwa;

Jak wspomniałem we wstępie nie zwolnienie zasobów powoduje tzw. wycieki pamięci. W dzisiejszych językach programowania wysokiego poziomu programista jest zwolniony z używania słówka delete dzięki kolektorowi śmieci GC. Jednak nie zawsze działa on perfekcyjnie, a dobry programista C++ potrafi sam zarządzać zasobami w sposób bardziej efektywny.

Implementacja

Przypuśćmy, że użytkownik potrzebuje programu, który będzie losował n liczb z przedziału [0, 100] (niekoniecznie różnych), a następnie wczyta od użytkownika liczbę i pokaże komunikat, że liczba znajduje się na liście, a w przypadku nietrafienia, którą liczbę prawie trafił (tj. liczbę z listy której wartość absolutna różnicy wczytanej liczby i liczby z listy jest najmniejsza). Program ma zakończyć działanie kiedy wczytana wartość n wyniesie -1. Użytkownik chce losować listę wiele razy o różnej długości bez potrzeby wychodzenia z programu. Program powinien wykorzystywać tak mało pamięci jak to tylko możliwe.

Spostrzeżenia

W podanym zadaniu nie należy skorzystać z tablicy statycznej, ponieważ nie wiadomo z góry ile liczb użytkownik będzie chciał wprowadzić. Ponadto warto zauważyć, że można sprawdzić czy element jest na liście poprzez wyznaczenie minimalnej różnicy pomiędzy wprowadzonym elementem, a najbliższym elementem na liście.

Funkcja główna

  1. int main () {
  2.   srand(time(0));
  3.   int n;
  4.   do {
  5.     cout << "Podaj dlugosc listy do wylosowania:";
  6.     cin >> n;
  7.     if (n != -1)
  8.       zadanie(n);
  9.   } while (n != -1);
  10.   system("pause");
  11.   return 0;
  12. }

W funkcji głównej (2.) inicjalizowany jest generator liczb losowych oraz (3.) zmienna do wprowadzania długości losowanej tablicy. Następnie (6.) wczytywana jest długość i (8.) wykonywane zadanie o ile (7.) nie ma być przerwany. Pętla jest powtarzana, aż do (9.) wprowadzenia wartości -1.

Losowanie listy

  1. void zadanie(int n) {
  2.   int* dane = new int[n];
  3.   for (int i = 0; i < n; i++)
  4.     dane[i] = rand() % 101;
  5.   int liczba;
  6.   cout << "Lista gotowa, wprowadz liczbe: ";
  7.   cin >> liczba;
  8.   int min = minOdleglosc(dane, n, liczba);
  9.   if (min == 0) {
  10.     cout << "Gratulacje! Liczba jest na liscie\n\n";
  11.   } else {
  12.     cout << "Pudlo, pomylka o " << min << "\n\n";
  13.   }
  14.   delete dane;
  15. }

Na podstawie przekazanego parametru n (2.) alokowana jest przestrzeń w pamięci pod n liczb typu int. Potem tablica (3. - 4.) jest uzupełniana liczbami z zakresu [0, 100]. Potem program (5.) przygotowuje miejsce w pamięci i (7.) wczytuje od użytkownika liczbę i (8.) wylicza najmniejszą różnicę. Warto tutaj zwrócić uwagę, że w celu przekazania tablicy wystarczy wpisać jej nazwę. Potem (10. - 15.) wynik jest odpowiednio interpretowany i (16.) pamięć zostaje zwolniona poprzez dealokację słowem kluczowym delete.

Szukanie minimalnej różnicy

  1. int minOdleglosc(int* dane, int n, int el) {
  2.   int min = abs(dane[0] - el);
  3.   for (int i = 1; i < n; i++) {
  4.     int t = abs(dane[i] - el);
  5.     if (t < min)
  6.       min = t;
  7.   }
  8.   return min;
  9. }

(1.) Funkcja przyjmuje tablice jako typ int* w ten sposób wie, że wartość zapisaną pod tym adresem należy traktować jak wskaźnik na inne miejsce w pamięci, a nie jako konkretną wartość liczbową jaką jest adres w pamięci. (2.) Początkowo za minimum należy przyjąć wartość absolutną różnicy i-tego elementu oraz wpisanej liczby, a potem (3. - 7.) poszukać mniejszej różnicy. Na koniec (8.) zwracana jest konkretna wartość.

W tej funkcji nie należy usuwać tablicy, ponieważ jest ona usuwana w innym miejscu. W tym przypadku przekazany wskaźnik jest jedynie skopiowaną wartości, ale nie nową tablicę, którą też należy usunąć.

Zadania

Zadanie 1

Napisz program, który wczyta od użytkownika liczbę n, a następnie n liczb rzeczywistych. Potem program powinien wypisać wczytane liczby wspak na ekran i wykonywać ten zestaw instrukcji tak długo, aż wczytana liczba n wyniesie 0.

Przykładowo, gdy użytkownik poda:

  1. 5
  2. 1 3 5 7 9

program wypisze na ekran:

  1. {9, 7, 5, 3, 1}

i ponownie wróci do wczytywania danych.