KI tablice dynamiczne, obiekty, klasy

Tablice dynamiczne, podejście funkcyjne

Rozwiążmy następujący problem: w pewnym programie chcemy posiadać tablicę dynamiczną, która będzie się dopasowywała do przechowywanych danych. Jak to zrealizować? Rozwiązanie może być następujące:

Tworzymy tablicę dynamiczną T o pewnym początkowym rozmiarze n. Jednocześnie w innej zmiennej zapamiętujemy liczbę danych przechowywanych w tej tablicy. Niech zmienna ta nosi nazwę c (ang. counter = licznik). Początkowo c zawiera wartość 0.

Dane dodajemy do tablicy za pomocą wybranej funkcji. Dodanie danych polega zawsze na zwiększeniu o 1 wartości c. Dlatego przed dodaniem nowego elementu sprawdzamy, czy c jest mniejsze od n. Jeśli tak, to w tablicy jest miejsce na dodatkowy element. Wstawiamy go i zwiększamy c o 1.

Jeśli natomiast c jest równe n, to tablica została już w całości zapełniona. W takim przypadku należy utworzyć nową tablicę, np. o rozmiarze n + DT (gdzie DT oznacza pewien zapas komórek, np. 5, 10, 100 – zależy to od przewidywanej intensywności dodawania elementów do tablicy), przepisać do niej zawartość starej tablicy, starą tablicę usunąć z pamięci i adres nowej tablicy zapamiętać w T, zwiększając równocześnie n o DT. Po tych operacjach T wskazuje nową, większą tablicę, która zawiera informację przechowywaną przez poprzednią tablicę dynamiczną. Możemy zatem dodać dane do tablicy.

Dane możemy również usuwać z tablicy. W tym przypadku maleje jej rozmiar c. Możemy się umówić, że jeśli po wykonaniem operacji zmniejszenia c = n - 2DT, to, podobnie jak przy zwiększaniu, tworzymy nową tablicę o rozmiarze n - DT, przepisujemy do niej starą, starą usuwamy, a za n przyjmujemy n - DT. W ten sposób tablica będzie przechowywała zawsze co najwyżej DT elementów więcej niż wynosi liczba wprowadzonych do niej danych.

W podejściu funkcyjnym problem ten rozwiązujemy przy pomocy kilku funkcji. Funkcje te muszą posiadać dostęp do T, n i c. Najlepiej zatem będzie umieścić te dane w strukturze, a do funkcji przekazywać referencję do tej struktury. Umówmy się, że referencja ta będzie przekazywana w pierwszym parametrze każdej funkcji. Oto elementy, które będą nam potrzebne (nazwy zostały dobrane w specjalny sposób, co zrozumiesz później – nie zmieniaj ich):

struct Vector { int * T,n,c; };	–	struktura zawierająca tablicę dynamiczną T, jej rozmiar n oraz aktualnie przechowywaną liczbę elementów c.
V_init(Vector & v)	–	funkcja inicjuje strukturę v. Tworzy tablicę dynamiczną T o DT elementach, wpisuje DT do n i 0 do c.
V_empty(Vector & v)	–	zwraca true, jeśli tablica T jest pusta, czyli nie zawiera żadnego elementu.
V_size(Vector & v)	–	zwraca c.
V_enlarge(Vector & v)	–	zwiększa o DT aktualny rozmiar tablicy T, jeśli c = n.
V_shrink(Vector & v)	–	zmniejsza o DT aktualny rozmiar tablicy T, jeśli c = n - 2DT.
V_push_back(Vector & v, int x)	–	dodaje do końca tablicy wartość x.
V_push_front(Vector & v, int x)	–	dodaje x na początku tablicy.
V_pop_back(Vector & v)	–	usuwa ostatni element tablicy.
V_pop_front(Vector & v)	–	usuwa pierwszy element tablicy.
V_back(Vector & v)	–	zwraca referencję do ostatniego elementu tablicy.
V_front(Vector & v)	–	zwraca referencję do pierwszego elementu tablicy.
V_at(Vector & v, int i)	–	zwraca referencję do elementu T[i].
V_erase(Vector & v, int i)	–	usuwa element na pozycji i-tej.
V_insert(Vector & v, int i, int x)	–	wstawia element x na pozycję i-tą.
V_print(Vector & v)	–	wypisuje aktualną zawartość tablicy w czytelny sposób.
V_destroy(Vector & v)	–	usuwa tablicę dynamiczną T.

Program jest następujący:

// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// Tablica o dynamicznym rozmiarze
// PRG_001
//-----------------------------------

#include <iostream>

using namespace std;

// Struktura tablicy dynamicznej
//------------------------------

struct Vector
{
  int *T,n,c;
};

// Funkcje obsługujące strukturę Vector
//-------------------------------------

const int DT = 5;     // Zapas elementów w tablicy

// Inicjuje strukturę Vector
//--------------------------

void V_init(Vector & v)
{
  v.n = DT;           // Początkowy rozmiar
  v.c = 0;            // Początkowa liczba elementów
  v.T = new int[v.n]; // Tworzymy dynamicznie tablicę
}

// Zwraca true, jeśli tablica jest pusta
//--------------------------------------

bool V_empty(Vector & v)
{
  return !v.c;
}

// Zwraca liczbę elementów w tablicy
//----------------------------------

int V_size(Vector & v)
{
  return v.c;
}

// Zwiększa o DT rozmiar tablicy T
//--------------------------------

void V_enlarge(Vector & v)
{
  if(v.c == v.n)
  {
    int *p,i;

    v.n += DT;               // Zwiększamy rozmiar o DT

    p = new int [v.n];       // Tworzymy nową tablicę o zwiększonym rozmiarze

    for(i = 0; i < v.c; i++) // Starą tablicę przenosimy do nowej
      p[i] = v.T[i];

    delete [] v.T;           // Usuwamy starą tablicę

    v.T = p;                 // Nowa tablica staje się tablicą T
  }
}

// Zmniejsza o DT rozmiar tablict T
//---------------------------------

void V_shrink(Vector & v)
{
  if(v.c == v.n - DT - DT)
  {
    int * p,i;

    v.n -= DT;               // Zmniejszamy rozmiar o DT

    p = new int [v.n];       // Tworzymy nową tablicę o zmniejszonym rozmiarze

    for(i = 0; i < v.c; i++) // Starą tablicę przenosimy do nowej
      p[i] = v.T[i];

    delete [] v.T;           // Usuwamy starą tablicę

    v.T = p;                 // Nowa tablica staje się tablicą T
  }
}

// Dodaje element na koniec tablicy
//---------------------------------

void V_push_back(Vector & v, int x)
{
  V_enlarge(v);    // W razie potrzeby zwiększamy rozmiar T
  v.T[v.c++] = x;  // x umieszczamy w tablicy
}

// Dodaje element na początek tablicy
//-----------------------------------

void V_push_front(Vector & v, int x)
{
  V_enlarge(v);                // W razie potrzeby zwiększamy rozmiar T
  for(int i = v.c; i > 0; i--)
    v.T[i] = v.T[i-1];         // Przesuwamy elementy
  v.T[0] = x;                  // W zwolnione miejsce wstawiamy x
  v.c++;                       // Tablica zawiera więcej elementów
}

// Usuwa z tablicy T ostatni element
//----------------------------------

void V_pop_back(Vector & v)
{
  if(v.c)        // Jeśli w tablicy T są jakieś elementy
  {
    v.c--;       // Usuwamy ostatni
    V_shrink(v); // W razie potrzeby zmniejszamy rozmiar T
  }
}

// Usuwa z tablicy T pierwszy element
//-----------------------------------

void V_pop_front(Vector & v)
{
  if(v.c)        // Jeśli w tablicy T są jakieś elementy
  {
    v.c--;       // Usuwamy pierwszy
    for(int i = 0; i < v.c; i++) v.T[i] = v.T[i + 1];
    V_shrink(v); // W razie potrzeby zmniejszamy rozmiar T
  }
}

// Zwraca referencję do pierwszego elementu tablicy
//-------------------------------------------------

int & V_front(Vector & v)
{
   return v.T[0];
}

// Zwraca referencję do ostatniego elementu tablicy
//-------------------------------------------------

int & V_back(Vector & v)
{
   return v.T[v.c-1];
}

// Zwraca referencję do i-tego elementu tablicy
//---------------------------------------------

int & V_at(Vector & v, int i)
{
   return v.T[i];
}

// Usuwa i-ty element tablicy T
//-----------------------------

void V_erase(Vector & v, int i)
{
  if(v.c && (i < v.c))
  {
    v.c--;     // Zmniejszamy rozmiar T

    for(int j = i; j < v.c; j++) v.T[j] = v.T[j + 1];

    V_shrink(v);
  }
}

// Wstawia x na pozycję i-tą
//--------------------------

void V_insert(Vector & v, int i, int x)
{
  if(i < v.c)
  {
    V_enlarge(v);

    for(int j = v.c; j > i; j--) v.T[j] = v.T[j - 1];

    v.T[i] = x;

    v.c++;
  }
}

// Wyświetla zawartość tablicy T
//------------------------------

void V_print(Vector & v)
{
  for(int i = 0; i < v.c; i++)
    cout << "T[" << i << "] = " << v.T[i] << endl;
  cout << endl;
}

// Usuwa tablicę dynamiczną
//-------------------------

void V_destroy(Vector & v)
{
  delete [] v.T;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  Vector a;              // Tworzymy strukturę tablicy

  V_init(a);             // Inicjujemy tę strukturę

  for(int i = 0; i < 5; i++)
    V_push_back(a,i+1);  // Wstawiamy 5 elementów

  V_print(a);            // Wyświetlamy tablicę

  V_push_back(a,10);     // Na koniec wstawiamy 10
  V_push_front(a,20);    // Na początek wstawiamy 20

  V_print(a);

  V_pop_back(a);         // Usuwamy ostatni element
  V_pop_front(a);        // Usuwamy pierwszy element
  V_insert(a,3,100);     // Na pozycję 3 wstawiamy kolejno 100, 200 i 300
  V_insert(a,3,200);
  V_insert(a,3,300);

  V_print(a);

  V_erase(a,4);          // Usuwamy elementy 4 i 1
  V_erase(a,1);

  V_print(a);

  V_destroy(a);          // Usuwamy tablicę dynamiczną

  system("pause");
  return 0;
}

Zwróć uwagę na to, że funkcje obsługujące strukturę Vector otrzymują referencję do niej w pierwszym parametrze. Dzięki temu mają pełny dostęp do pól tej struktury. Zamiast referencji można również przekazywać wskaźnik do struktury. Wtedy dostęp do jej pól odbywa się poprzez operator strzałki ->.

Tablice dynamiczne, podejście obiektowe

Teraz to samo zaprogramujemy, wykorzystując programowanie obiektowe.

// Koło Informatyczne I LO w Tarnowie
// (C)2013 mgr Jerzy Wałaszek
// Tablica o dynamicznym rozmiarze
// PRG_002
//-----------------------------------

#include <iostream>

using namespace std;

// Definicja klasy
//----------------

class Vector
{
  protected:
    int *T,n,c;
    void enlarge();
    void shrink();

  public:
    Vector();
    ~Vector() { delete [] T; }

    bool empty()    { return !c; }
    int  size()     { return c; }
    void push_back(int x);
    void push_front(int x);
    void pop_back();
    void pop_front();
    int & back()    { return T[c-1]; }
    int & front()   { return T[0]; }
    int & at(int i) { return T[i]; }
    void erase(int i);
    void insert(int i, int x);
    void print();
};

// Metody klasy Vector
//-------------------------------------

const int DT = 5;     // Zapas elementów w tablicy

// Konstruktor
//------------

Vector::Vector()
{
  n = DT;           // Początkowy rozmiar
  c = 0;            // Początkowa liczba elementów
  T = new int[n];   // Tworzymy dynamicznie tablicę
}

// Zwiększa o DT rozmiar tablicy T
//--------------------------------

void Vector::enlarge()
{
  if(c == n)
  {
    int *p,i;

    n += DT;               // Zwiększamy rozmiar o DT

    p = new int [n];       // Tworzymy nową tablicę o zwiększonym rozmiarze

    for(i = 0; i < c; i++) // Starą tablicę przenosimy do nowej
      p[i] = T[i];

    delete [] T;           // Usuwamy starą tablicę

    T = p;                 // Nowa tablica staje się tablicą T
  }
}

// Zmniejsza o DT rozmiar tablict T
//---------------------------------

void Vector::shrink()
{
  if(c == n - DT - DT)
  {
    int * p,i;

    n -= DT;               // Zmniejszamy rozmiar o DT

    p = new int [n];       // Tworzymy nową tablicę o zmniejszonym rozmiarze

    for(i = 0; i < c; i++) // Starą tablicę przenosimy do nowej
      p[i] = T[i];

    delete [] T;           // Usuwamy starą tablicę

    T = p;                 // Nowa tablica staje się tablicą T
  }
}

// Dodaje element na koniec tablicy
//---------------------------------

void Vector::push_back(int x)
{
  enlarge();   // W razie potrzeby zwiększamy rozmiar T
  T[c++] = x;  // x umieszczamy w tablicy
}

// Dodaje element na początek tablicy
//-----------------------------------

void Vector::push_front(int x)
{
  enlarge();       // W razie potrzeby zwiększamy rozmiar T
  for(int i = c; i > 0; i--)
    T[i] = T[i-1]; // Przesuwamy elementy
  T[0] = x;        // W zwolnione miejsce wstawiamy x
  c++;             // Tablica zawiera więcej elementów
}

// Usuwa z tablicy T ostatni element
//----------------------------------

void Vector::pop_back()
{
  if(c)       // Jeśli w tablicy T są jakieś elementy
  {
    c--;      // Usuwamy ostatni
    shrink(); // W razie potrzeby zmniejszamy rozmiar T
  }
}

// Usuwa z tablicy T pierwszy element
//-----------------------------------

void Vector::pop_front()
{
  if(c)       // Jeśli w tablicy T są jakieś elementy
  {
    c--;      // Usuwamy pierwszy
    for(int i = 0; i < c; i++) T[i] = T[i + 1];
    shrink(); // W razie potrzeby zmniejszamy rozmiar T
  }
}

// Usuwa i-ty element tablicy T
//-----------------------------

void Vector::erase(int i)
{
  if(c && (i < c))
  {
    c--;     // Zmniejszamy rozmiar T

    for(int j = i; j < c; j++) T[j] = T[j + 1];

    shrink();
  }
}

// Wstawia x na pozycję i-tą
//--------------------------

void Vector::insert(int i, int x)
{
  if(i < c)
  {
    enlarge();

    for(int j = c; j > i; j--) T[j] = T[j - 1];

    T[i] = x;

    c++;
  }
}

// Wyświetla zawartość tablicy T
//------------------------------

void Vector::print()
{
  for(int i = 0; i < c; i++)
    cout << "T[" << i << "] = " << T[i] << endl;
  cout << endl;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  Vector a;            // Tworzymy klasę

  for(int i = 0; i < 5; i++)
    a.push_back(i+1);  // Wstawiamy 5 elementów

  a.print();           // Wyświetlamy tablicę

  a.push_back(10);     // Na koniec wstawiamy 10
  a.push_front(20);    // Na początek wstawiamy 20

  a.print();

  a.pop_back();        // Usuwamy ostatni element
  a.pop_front();       // Usuwamy pierwszy element
  a.insert(3,100);     // Na pozycję 3 wstawiamy kolejno 100, 200 i 300
  a.insert(3,200);
  a.insert(3,300);

  a.print();

  a.erase(4);          // Usuwamy elementy 4 i 1
  a.erase(1);

  a.print();

  a.front() = a.back();
  a.at(1) = a.at(a.size()-2);

  a.print();
  
  system("pause");
  return 0;
}

Różnice pomiędzy podejściem funkcyjnym a obiektowym

Przyglądnijmy się różnicom w obu programach.

Wersja funkcyjna

Wersja obiektowa

// Struktura tablicy dynamicznej
//------------------------------

struct Vector
{
  int *T,n,c;
};

// Definicja klasy
//----------------

class Vector
{
  protected:
    int *T,n,c;
    void enlarge();
    void shrink();

  public:
    Vector();
    ~Vector() { delete [] T; }

    bool empty()    { return !c; }
    int  size()     { return c; }
    void push_back(int x);
    void push_front(int x);
    void pop_back();
    void pop_front();
    int & back()    { return T[c-1]; }
    int & front()   { return T[0]; }
    int & at(int i) { return T[i]; }
    void erase(int i);
    void insert(int i, int x);
    void print();
};

W strukturze Vector mamy jedynie pola danych. W klasie Vector, oprócz pól danych, mamy również definicje funkcji, które z tą klasą współpracują. Funkcje takie nazywamy metodami (ang. methods) lub funkcjami składowymi (ang. member functions).

Dalej widzimy w klasie Vector dwa słowa kluczowe:

protected – rozpoczyna sekcję elementów chronionych klasy. Elementy te (dane oraz metody) będą dostępne tylko dla innych metod tej klasy oraz klas pochodnych (o tym później). Chodzi tutaj o ukrycie szczegółów implementacyjnych, które dla programu głównego są zbędne. Tak samo postępuje się w świecie rzeczywistym. Np. przy obsłudze telewizora nie zdejmujesz przecież obudowy i nie manipulujesz elementami, które są w środku, bo możesz coś przypadkowo zepsuć, albo sam zostać porażony prądem.
public – rozpoczyna sekcję publiczną. Elementy umieszczone w tej sekcji staną się widoczne dla pozostałych funkcji w programie. Jest to odpowiednik przycisków na obudowie telewizora, za pomocą których sterujemy jego działaniem. Często sekcję public nazywa się interfejsem klasy (ang. class interface).

Jeśli metoda klasy jest krótka, to jej część wykonawczą możemy umieścić bezpośrednio w definicji klasy. U nas zrobiliśmy tak z metodami:

~Vector() { delete [] T;}
bool empty() { return !c; }
int size() { return c; }
int & front() { return T[0]; }
int & back() { return T[c-1]; }
int & at(int i) {return T[i]; }

Tak zdefiniowane metody tworzą tzw. funkcje inline. Różnią się one tym od innych funkcji, że kompilator przy każdym odwołaniu do nich wstawia do programu ich kod. Dzięki temu wykonują się szybciej, ale program zajmuje oczywiście więcej miejsca. Z tego powodu funkcje inline powinny być krótkie.

Klasa posiada dwie metody specjalne, które nazywamy konstruktorem i destruktorem. Cechą charakterystyczną tych metod jest to, iż mają one taką samą nazwę jak nazwa klasy.

Zadaniem konstruktora jest budowa klasy. Jest on zawsze wywoływany przez program wtedy, gdy klasa jest tworzona w pamięci, gdy rozpoczyna swoje istnienie. W przypadku naszej klasy konstruktor inicjuje jej pola n i c oraz przydziela wstępnie DT komórek tablicy dynamicznej T:

// Konstruktor
//------------

Vector::Vector()
{
  n = DT;           // Początkowy rozmiar
  c = 0;            // Początkowa liczba elementów
  T = new int[n];   // Tworzymy dynamicznie tablicę
}

W wersji funkcyjnej musieliśmy osobiście wywołać funkcję V_init() do zainicjowania pól struktury Vector. W wersji obiektowej klasa sama dba o swoją inicjalizację – jeśli zdefiniujesz dla niej odpowiedni konstruktor, to użyje go ona na początku swojego życia w pamięci.

Destruktor ma z kolei za zadanie czysto usunąć klasę z pamięci, gdy przestaje ona istnieć. Ponieważ nasza klasa rezerwuje obszar dla tablicy dynamicznej T, to destruktor zwraca ten obszar z powrotem do systemu. Gdyby tego nie robił, to mógłby powstać wyciek pamięci (ang. memory leak) (jeśli program się kończy, jak w tym przypadku, to cała zarezerwowana przez niego pamięć i tak trafia do systemu, jednakże przy tworzeniu klas lokalnych w funkcjach zawsze należy zwracać zarezerwowane zasoby, a destruktory dbają o to automatycznie).

~Vector() { delete [] T;}

Kolejna różnica dotyczy samych funkcji i metod. Weźmy dla przykładu funkcję wstawiającą element na początek tablicy:

Wersja funkcyjna

Wersja obiektowa

// Dodaje element na początek tablicy
//-----------------------------------

void V_push_front(Vector & v, int x)
{
  V_enlarge(v);
  for(int i = v.c; i > 0; i--)
    v.T[i] = v.T[i-1];
  v.T[0] = x;
  v.c++;
}

// Dodaje element na początek tablicy
//-----------------------------------

void Vector::push_front(int x)
{
  enlarge();
  for(int i = c; i > 0; i--)
    T[i] = T[i-1];
  T[0] = x;
  c++;
}

Nazwa metody jest poprzedzona nazwą klasy Vector oraz operatorem :: (operator czterokropek, operator zakresu). Informuje to kompilator, że definicja dotyczy metody należącej do klasy Vector.

Kolejna różnica, to brak na liście parametrów metody referencji do obiektu zmiennej. W wersji funkcyjnej parametr ten musi zostać jawnie podany, aby funkcja miała dostęp do pól struktury, na których ma przeprowadzić jakieś działania. W przypadku klasy wszystkie jej metody dostają automatycznie tę referencję w ukrytym pierwszym parametrze. Parametr ten nazywa się this i jest wskaźnikiem aktualnej zmiennej klasy, na której operuje metoda. Zwykle nie musimy z niego jawnie korzystać.

W wersji funkcyjnej dostęp do pól struktury odbywa się zawsze poprzez parametr, który funkcja otrzymała przy wywołaniu. U nas parametr ten nazywa się v. W wersji obiektowej zmienna klasy jest domyślna i pól oraz funkcji składowych nie musimy jawnie niczym poprzedzać. Oczywiście, na upartego moglibyśmy skorzystać z tego ukrytego parametru this w sposób następujący:

void Vector::push_front(int x)
{
  if(this->c == this->n) enlarge(); // W razie potrzeby zwiększamy rozmiar T
  for(int i = this->c; i > 0; i--)
    this->T[i] = this->T[i-1];      // Przesuwamy elementy
  this->T[0] = x;                   // W zwolnione miejsce wstawiamy x
  this->c++;                        // Tablica zawiera więcej elementów
}

Ale i tak robi to automatycznie kompilator, więc tutaj nie ma to specjalnie sensu.

Koło informatyczne

Tablice dynamiczne, podejście funkcyjne

Tablice dynamiczne, podejście obiektowe

Różnice pomiędzy podejściem funkcyjnym a obiektowym