Warsztat.GDCompo!ProjektyMediaArtykułyQ&AForumOferty pracyPobieranie

Opisz napotkaną sytuację, a redakcja niezwłocznie znajdzie rozwiązanie!

wyślij anuluj

Struktury danych i formaty plików

Tekst został importowany z Warsztatowych artykułów. Jego oryginalnym autorem jest Adam Sawicki. Jeżeli został importowany poprawnie, usuń ten szablon!

Spis treści

  1. Wstęp
  2. Struktury danych
  3. Formaty plików
  4. Zakończenie

Wstęp

Uczy się programowania. Poznaje język i różne biblioteki. Ma dużo pomysłów i nawet sporo potrafi napisać. Ma tylko jeden problem - jak przechowywać obiekty? Do wszystkiego używa pojedynczych zmiennych, zwykłych statycznych tablic albo różnych najdziwniejszych sposobów. Tak wygląda sylwetka niejednego początkującego programisty. Podczas mojej praktyki zawsze spotykałem się z takimi osobami. Pamiętam, jak jedna z nich postawiła nawet w Delphi na okienku pole listy (taką normalną kontrolkę Windows) i uczyniła ją niewidzialną używając jej tylko do przechowywania wewnętrznych danych w swoim programie. Oczywiście w postaci łańcuchów tekstowych, bo tylko takie lista mogła przechowywać.

Przychodzi podczas nauki programowania taka chwila, że niezbędne jest poznanie dziedziny, której nazwa to struktury danych. Trzeba nauczyć się, jak pisać własną kolekcję obiektów danego rodzaju (np. linijek tekstu w twoim edytorze czy potworków w twojej grze), jak przechowywać ją w pamięci, jak operować na niej i jak przechowywać ją na dysku (serializować).

Dostępnych jest wiele książek, które w tytule mają "algorytmy" i "struktury danych". Jednak ich poziom może odstraszać powodując mylną opinię, jakoby ta dziedzina była bardzo trudna. W niniejszym artykule postaram się przystępnie opisać jedynie najważniejsze i najużyteczniejsze struktury danych koncentrując się na nich od strony praktycznej, ponieważ wierzę, że algorytmy są tylko dodatkiem do nich.

Do zrozumienia artykułu wymagana jest znajomość:

  1. języka C++
  2. wskaźników

Artykuł obejmuje:

  1. podstawy struktur danych
  2. podstawy STL
  3. tworzenie własnych formatów plików
  4. operacje na plikach

Wstęp do STL

Zanim przejdziemy do omawiania pierwszych struktur danych, chciałbym napisać ogólnie o STL, którego będziemy później używali.

Biblioteka standardowa C++ to zbiór funkcji i innych elementów napisanych w C++, które wchodzą w skład standardu. Oznacza to, są sprawdzone, dobre, szybkie, a także przenośne. Można ich używać na dowolnej platformie (np. Windows, Linux), bo biblioteka standardowa jest dołączana do kompilatorów C++.

STL (ang. Standard Template Library) to najważniejsza część biblioteki standardowej. Zawiera zbiór użytecznych szablonów klas, zwłaszcza uniwersalnych struktur danych. Warto ich używać, bo nie ma sensu pisać wszystkiego samemu i wyważać otwartych drzwi. Lepiej skupić się na pisaniu właściwego programu.

Oto przykład kodu używającego biblioteki standardowej:

#include <iostream>
#include <vector>

int main()
{
  std::vector<int> v;
  v.push_back(10);
  std::cout << v[0] << std::endl;
  return 0;
}

Można tu zauważyć kilka rzeczy:

  • Włączone zostały pewne pliki nagłówkowe, które nie mają rozszerzenia H.
  • Każdy element biblioteki standardowej jest zawarty w przestrzeni nazw std. W praktyce oznacza to, że zawsze trzeba go poprzedzać przedrostkiem std::.
  • Użyty został szablon, który można rozpoznać po nawiasach kątowych <>.

Jeśli niewiele z tego rozumiesz, nie przejmuj się. Wszystko wyjaśni się w dalszej części.

Notacja dużego O (notacja asymptotyczna)

Każdą rzecz można zrobić na różne sposoby. Nas szczególnie będą interesowały algorytmy operujące na strukturach danych, np. sortujące pewne elementy czy wyszukujące w zbiorze dany element. Jedne sposoby są gorsze, inne lepsze. Dlatego wymyślono pewien sposób ich oceniania.

Ilość operacji potrzebnych do wykonania naszego zadania jest zależna od ilości danych, na jakich ma operować. Jeśli liczbę elementów oznaczymy przez n, możemy powiedzieć, że złożoność algorytmu jest jakąś funkcją f(n). Ponieważ taka funkcja może być bardzo skomplikowana, warto wprowadzić pewne ogólne oznaczenie klasy złożoności. Właśnie do tego służy notacja dużego O.

Oto niektóre najpopularniejsze klasy złożoności ułożone w kolejności od najlepszych (wymagających najmniej operacji) do najgorszych (wymagających najwięcej operacji):

Złożoność stała
O(1) Oznacza, że ilość operacji jest stała i nie zależy od ilości danych, na jakich operujemy.
Złożoność logarytmiczna
O(log n) Występuje wtedy, gdy zbiór jest dzielony na coraz to mniejsze części.
Złożoność liniowa
O(n) Oznacza, że ilość operacji do wykonania jest wprost proporcjonalna do ilości danych, np. kiedy trzeba przebiegnąć po wszystkich elementach zbioru.
Złożoność kwadratowa
O(n2) Oznacza, że ze wzrostem ilości elementów ilość potrzebnych operacji wzrasta bardzo szybko, np. kiedy trzeba przebiegnąć po wszystkich elementach, a dla każdego z nich jeszcze raz przebiegać po wszystkich.

Wykresy różnych funkcji

Struktury danych

Rozpoczynamy omawianie najważniejszych struktur danych. Dzięki nim będziesz mógł w swoich programach przechowywać w pamięci kolekcje obiektów dowolnego rodzaju. Dzięki dobraniu struktury odpowiedniej do konkretnych potrzeb operacje na niej będą proste i wydajne (szybkie). Pokażę sposoby pisania własnych struktur danych, jak również używania tych wbudowanych w STL.

Tablica jednowymiarowa (wektor)

Tablica jednowymiarowa to zbiór umieszczonych kolejno po sobie w pamięci elementów tego samego rodzaju i tej samej wielkości (np. liter). Spójrz na poniższy rysunek. Nie przejmuj się ilością różnych szczegółów na nim - będziemy do niego wracali i po kolei omawiali te szczegóły.

Wektor

Wektor to inna nazwa tablicy jednowymiarowej. To prawda, że wektor znany z lekcji matematyki to taka strzałka na wykresie. Jednak w zapisie liczbowym wektor wygląda tak: [3, 7]. Jak widać, jest to ciąg kilku (tutaj - dwóch) elementów jakiegoś rodzaju (tutaj - liczb), a więc wszystko się zgadza.

Tablica statyczna, indeksowanie

Najprostszą implementacją wektora jest zwykła, statyczna tablica. Jeśli znasz choć trochę język C++, nie powinieneś mieć problemów ze zrozumieniem takiego kodu:

// stały rozmiar tablicy
const int SIZE = 16;
// tablica
char tab[SIZE];
// wypełnienie jej kolejnym literami
for (int i = 0; i < SIZE; i++)
  tab[i] = 'A' + i;
// wypisanie środkowego elementu
std::cout << tab[SIZE/2] << std::endl;

Rozmiar tablicy warto zawsze przechowywać pod jakąś nazwą - w stałej, a nie wpisywać za każdym razem liczbę. Dzięki temu wystarczy go zmienić tylko w jednym miejscu.

Tablica przechowuje znaki (typ char), ale równie dobrze mogą to być obiekty dowolnego typu - liczbowego, wskaźnikowego czy nawet zdefiniowanego przez ciebie typu strukturalnego albo klasy, wskaźniki na klasę itd.

Indeks to liczba zapisywana w nawiasie kwadratowym [], dzięki której odwołujemy się do danego elementu tablicy. Elementy są ponumerowane po kolei od 0 do SIZE-1. W takim też zakresie zmienia się w pętli wypełniającej zmienna i. Indeksy kolejnych elementów są napisane nad elementami na rysunku powyżej.

Dlaczego indeksuje się od 0, a nie od 1? Ponieważ taki sposób jest najbardziej naturalny. Żeby dostać się do któregoś elementu, komputer bierze miejsce w pamięci, gdzie znajduje się tablica i dodaje do niego indeks pomnożony przez rozmiar pojedynczego elementu:

pozycja = pozycja_tablicy + (indeks * rozmiar_elementu)

Kiedy pierwszy element ma indeks 0, wynikiem będzie:

pozycja = pozycja_tablicy + (0 * rozmiar_elementu) = pozycja_tablicy

Tak więc pierwszy element zaczyna się od miejsca, gdzie zaczyna się sama zmienna tablicowa, a każdy następny jest o rozmiar elementu dalej - wszystko się zgadza!

W powyższym przykładzie ostatnia instrukcja wypisuje element o indeksie SIZE/2 = 16/2 = 8, czyli element dziewiąty. Dziewiątą literą jest I.

Tablica dynamiczna

Zwykła, statyczna tablica musi mieć rozmiar znany już podczas kompilacji, czyli podany w postaci liczby lub stałej. Nie może to być zmienna, dlatego nie można np. poprosić użytkownika o podanie rozmiaru tablicy i utworzyć tablicy o takim rozmiarze. To wymaga użycia tablicy dynamicznej opartej na wskaźnikach:

// zmienna na rozmiar
int size;
// użytkownik podaje rozmiar
std::cin >> size;
// UTWORZENIE TABLICY
char *tab = new char[size];
// wypełnienie jej kolejnym literami
for (int i = 0; i < size; i++)
  tab[i] = 'A' + i;
// wypisanie ostatniego elementu
std::cout << tab[size-1] << std::endl;
// USUNIęCIE TABLICY
delete [] tab;

Jak widać, jej używanie nie różni się od używania zwykłej tablicy statycznej z wyjątkiem tego, że trzeba ją przed użyciem utworzyć, a po użyciu usunąć. Szczegóły tych czynności należą już do dziedziny zwanej wskaźnikami i nie będę ich tutaj opisywał.

Dodawanie i usuwanie, capacity

Dotychczas tablica zawsze miała pewien rozmiar (liczbę elementów) niezmienny podczas swojego istnienia. Nietrudno się domyślić, że potrzeba czasem dodać do istniejącej tablicy jakiś element albo jakiś z niej usunąć. Zastanówmy się, jak możnaby to napisać...

Pomysł polega na tym, aby nie zawsze używane były wszystkie elementy tablicy, a jedynie pewna ilość początkowych. Taki prawdziwy rozmiar tablicy (ilość zarezerwowanych elementów, a zarazem maksymalną ilość elementów, czyli maksymalny rozmiar) nazywamy pojemnością (ang. capacity). Oprócz niej, trzeba będzie zapamiętać także aktualny rozmiar, czyli ile początkowych elementów jest wykorzystywane. Na rysunku powyżej pojemność tablicy wynosi 9 elementów, natomiast używanych jest tylko 6. Elementy używane są zaznaczone na zielono, a nieużywane na szaro.

// pojemność tablicy
const int CAPACITY = 16;
// aktualny rozmiar (na początku pusta)
int size = 0;
// tablica
char tab[CAPACITY];

Jeśli rozumiesz ten pomysł, możemy przejść do obmyślania samego dodawania i usuwania elementów. Najprościej wyobrazić sobie dodawanie elementu na końcu tablicy. Wystarczy wpisać go na swoje miejsce. Tak się składa, że jego indeks przechowuje zmienna size z aktualnym rozmiarem tablicy, bo dotychczasowe elementy miały indeksy od 0 do size-1. Potem trzeba zwiększyć tą zmienną o jeden. Nie można też zapomnieć o sprawdzeniu, czy przypadkiem nie próbujemy przekroczyć maksymalnego rozmiaru tablicy!

Dodawanie do wektora

// Funkcja dodaje podany element na końcu tablicy
// Jeśli nie można dodać, zwraca false
bool Add(char element)
{
  // jeśli tablica jest pełna
  if (size == CAPACITY) return false;
  else {
    // wpisanie nowego elementu na swoje miejsce
    tab[size] = element;
    // zwiększenie rozmiaru
    size++;
    return true;
  }
}

Kolejność elementów w kolekcji nie zawsze ma znaczenie, ale w niektórych zastosowaniach ma. Czasami trzeba wstawić element gdzieś w środku wektora. Żeby to zrobić, trzeba będzie przesunąć wszystkie dalsze elementy o jedną pozycję w prawo, by zrobić miejsce dla nowego.

Wstawianie do wektora

// Funkcja wstawia podany element w podane miejsce
// Jeśli nie można wstawić, zwraca false
bool Insert(char element, int index)
{
  // jeśli tablica jest pełna
  if (size == CAPACITY) return false;
  else {
    // jeśli indeks jest prawidłowy
    if (index >= 0 && index <= size) {
      // przepisanie dalszych elementów o jedno miejsce w prawo
      // od ostatniego do tego w podanym miejscu
      for (int i = size-1; i >= index; i--)
        tab[i+1] = tab[i];
      // wstawienie podanego elementu
      tab[index] = element;
      // zwiększenie rozmiaru
      size++;
      return true;
    }
    else return false;
  }
}

Najgorszym przypadkiem jest wstawianie na początek. Trzeba wtedy przepisać wszystkie elementy. Można też zauważyć, że dodawanie na koniec jest szczególnym przypadkiem wstawiania, w którym niczego nie trzeba przepisywać. Średnio jednak ilość operacji potrzebnych do wstawienia elementu wewnątrz wektora jest wprost proporcjonalna do jego rozmiaru, a więc wstawianie do wektora ma złożoność rzędu O(n).

Podobnie będzie z usuwaniem. Trzeba przestawić wszystkie dalsze elementy o jedno miejsce wcześniej.

Usuwanie z wektora

// Funkcja usuwa element z podanego miejsca
// Jeśli nie można usunąć, zwraca false
bool Delete(int index)
{
  // jeśli indeks jest prawidłowy
  if (index >= 0 && index < size) {
    // przepisanie dalszych elementów o jedno miejsce w lewo
    // od następnego do ostatniego
    for (int i = index+1; i < size; i++)
      tab[i-1] = tab[i];
    // zmniejszenie rozmiaru
    size--;
    return true;
  }
  else return false;
}

Usunięcie polega na tym, że podczas przepisywania elementów o jedno miejsce wcześniej element usuwany zostaje zamazany następnym.

Realokacja

Do powyższego wektora nie można było dodać więcej, niż 16 elementów. Co zrobić, żeby był pojemniejszy? Nie ma sensu alokować całych megabajtów pamięci na zapas, a szukanie kompromisowej, stałej pojemności (capacity) zwykle nie jest dobrym rozwiązaniem. Dobrze byłoby, gdyby wektor potrafił sam zwiększyć swój rozmiar w razie potrzeby. Tylko jak to zrobić?

Realokacja to ponowne przydzielenie pamięci, zazwyczaj o większym (albo mniejszym) rozmiarze od poprzedniej. Składa się z takich etapów:

  1. Utworzenie nowego bloku pamięci
  2. Przepisanie wszystkich elementów ze starego do nowego
  3. Usunięcie starego bloku

W ten sposób możemy napisać wektor, który sam będzie się zwiększał wedle potrzeb! Tylko że nie ma sensu realokować pamięci i przepisywać całej tablicy podczas dodania albo usunięcia każdego elementu. Trzeba to robić tylko co jakiś czas - np. kiedy aktualnie przydzielona pamięć jest już pełna, a my chcemy dodać kolejny elementy.

Jak pamiętamy, taką możliwość przechowywania pamięci na zapas daje nam idea pojemności (capacity). Można wtedy przydzielić pamięć o kilka elementów większą od dotychczasowej albo np. 2 razy większą. Warto też realokować wektor zmniejszając go, kiedy zawiera bardzo mało elementów w stosunku do ilości tych "rezerwowych". W takiej sytuacji zmiana w stosunku do poprzedniego przykładu polega na tym, że także capacity stanie się zmienną, a nie stałą.

// o ile elementów zwiększać lub zmniejszać podczas realokacji
const int DELTA = 10;
// pojemność tablicy
int capacity = 0;
// aktualny rozmiar
int size = 0;
// tablica
char *tab = 0;

// Funkcja wstawia podany element w podane miejsce
// Jeśli nie można wstawić, zwraca false
bool Insert(char element, int index)
{
  // jeśli indeks jest prawidłowy
  if (index >= 0 && index <= size) {
    // jeśli tablica jest pełna - realokacja
    if (size == capacity) {
      // nowe capacity
      capacity += DELTA;
      // 1. Utworzenie nowej
      char *newTab = new char[capacity];
      // 2. Przepisanie ze starej do nowej
      for (int i = 0; i < size; i++)
        newTab[i] = tab[i];
      // 3. Usunięcie starej
      if (tab) delete [] tab;
      tab = newTab;
    }
    // przepisanie dalszych elementów o jedno miejsce w prawo
    // od ostatniego do tego w podanym miejscu
    for (int i = size-1; i >= index; i--)
      tab[i+1] = tab[i];
    // wstawienie podanego elementu
    tab[index] = element;
    // zwiększenie rozmiaru
    size++;
    return true;
  }
  else return false;
}

// Funkcja dodaje podany element na końcu tablicy
// Dodawanie to tylko szczególny przypadek wstawiania!
bool Add(char element)
{
  return Insert(element, size);
}

// Funkcja usuwa element z podanego miejsca
// Jeśli nie można usunąć, zwraca false
bool Delete(int index)
{
  // jeśli indeks jest prawidłowy
  if (index >= 0 && index < size) {
    // przepisanie dalszych elementów o jedno miejsce w lewo
    // od następnego do ostatniego
    for (int i = index+1; i < size; i++)
      tab[i-1] = tab[i];
    // zmniejszenie rozmiaru
    size--;
    // jeśli tablica jest za duża - realokacja
    if (size > DELTA && size < capacity-DELTA) {
      // nowe capacity
      capacity -= DELTA;
      // 1. Utworzenie nowej
      char *newTab = new char[capacity];
      // 2. Przepisanie ze starej do nowej
      for (int i = 0; i < size; i++)
        newTab[i] = tab[i];
      // 3. Usunięcie starej
      delete [] tab;
      tab = newTab;
    }
    return true;
  }
  else return false;
}

Dziury

W konkretnych zastosowaniach występują różne potrzeby i należy wymyślić stosowne do tego algorytmy i struktury danych. Kiedy tylko można, lepiej jest dodawać elementy na końcu wektora - nie trzeba wtedy rozsuwać wszystkich następnych (chyba, że następuje realokacja - wówczas trzeba przepisać cały wektor). Rozpatrzmy teraz przypadek, kiedy kolejność elementów nie ma znaczenia, a nam zależy, by przyspieszyć usuwanie z wektora.

Pomysł polega na tym, żeby nie usuwać elementów w taki sposób, jak to napisałem wyżej - z przesuwaniem wszystkich następnych elementów. Czasami wystarczy wpisanie do danej komórki tablicy jakiejś specjalnej wartości, która oznacza, że to miejsce jest puste. Jeśli elementami wektora są liczby całkowite, ale zawsze dodatnie, za wartość pustą można przyjąć np. -1.

Teraz już wiesz, dlaczego na rysunkach w tym podrozdziale nie we wszystkich elementach jest litera. To są właśnie te "dziury" - ostatnia rzecz, którą w nich ukryłem. Takie dziury można potem wykorzystywać, by przyspieszyć wstawianie elementów - nie trzeba przesuwać wszystkich. Jeśli zaś kolejność nie ma znaczenia, można wstawiać w pierwszej napotkanej dziurze!

Wektor STL

Napisałem, jak utworzyć własny wektor, bo są to wiadomości podstawowe i przydatne. Czasami warto taki napisać. STL oferuje nam jednak gotową implementację wektora, którą można wykorzystywać w swoich programach w C++. Sposób jego użycia najlepiej zilustruje przykład:

#include <iostream>
#include <vector>

int main()
{
  // deklaruję wektor
  std::vector<char> v;
  // dodaję 10 pierwszych liter
  for (int i = 0; i < 10; i++)
    v.push_back('A' + i);
  // czy wektor jest pusty?
  if ( v.empty() )
    std::cout << "Wektor jest pusty!" << std::endl;
  // wypisuję ostatni element
  std::cout << v[ v.size()-1 ] << std::endl;
  return 0;
}

Powyższy przykład wpiszę literę J, a po dodaniu 10 elementów wektor oczywiście nie jest pusty. Wektor STL jest bardzo dobry, szybki i sam się realokuje. Jest wygodny w użyciu i posiada wiele użytecznych funkcji składowych. Oto krótkie omówienie wektora STL:

  • #include <vector> - taki nagłówek trzeba włączyć, aby skorzystać z wektora STL.
  • std::vector<char> - tak deklaruje się wektor. Cały ten łańcuch to typ deklarowanej zmiennej v. W nawiasach kątowych pisze się typ elementów wektora.
  • Funkcja push_back() dodaje podany element na końcu wektora.
  • Funkcja empty() zwraca true, jeśli wektor jest pusty (nie zawiera żadnych elementów) i false, jeśli nie jest pusty (zawiera przynajmniej jeden element).
  • Funkcja size() zwraca rozmiar wektora, czyli aktualną liczbę elementów.
  • Do poszczególnych elementów można odwoływać się za pomocą operatora nawiasu kwadratowego, tak jak w zwyczajnej tablicy: v[indeks]. Trzeba tylko uważać, by indeks zawsze był w zakresie od 0 do v.size()-1 - wektor sam tego nie sprawdza!

Kolejne elementy wektora, jak również każdego innego kontenera STL można też przechodzić z użyciem tzw. iteratorów:

// wypisuje wszystkie elementy
std::vector<char>::iterator it;
for (it = v.begin(); it != v.end(); ++it)
  std::cout << *it << ' ';

std::vector<char>::iterator jest nazwą typu, która oznacza iterator dla wektora znaków takiego, jak w poprzednim przykładzie. Deklarujemy zmienną it tego typu i używamy jej w pętli. Iterator zachowuje się podobnie do wskaźnika. Jest to taki jakby specjalny wskaźnik do pokazywania na elementy kontenera STL.

  • Funkcja begin() zwraca iterator pokazujący na pierwszy element wektora. Taką wartością inicjujemy go w pętli.
  • Funkcja end() zwraca iterator pusty - niepokazujący na żaden z elementów, a oznaczający błąd. Mówi się też czasem, że pokazuje na element następny za ostatnim. Właśnie z tą wartością porównujemy nasz iterator by dowiedzieć się, czy nie przekroczył już końca wektora.
  • ++it przesuwa iterator tak, że pokazuje na następny element. Użyłem preinkrementacji, a nie postinkrementacji, bo w przypadku iteratorów ta pierwsza może działać szybciej.
  • Do elementów wektora odwołuję się wyłuskując je z iteratora za pomocą gwiazdki * tak, jakby iterator był zwykłym wskaźnikiem.

Oczywiście za pomocą nawiasów kwadratowych [] użytych na wektorze oraz gwiazdki * użytej na iteratorze można nie tylko odczytywać, ale także zapisywać (zmieniać) istniejące już elementy wektora.

Podsumowanie

Wektor to jednowymiarowa tablica umieszczonych kolejno po sobie elementów jakiegoś typu. Jego największą zaletą jest to, że do elementów można natychmiast odwoływać się podając ich indeksy. Może nie zwracaliśmy na to szczególnej uwagi uznając tą cechę za coś oczywistego, ale jak przekonamy się w następnych podrozdziałach, wcale nie musi tak być.

Wektory mają też to do siebie, że są proste w implementacji. Jednak wstawianie i usuwanie elementów jest powolne i ma złożoność klasy O(n). Na koniec rozdziału o taliach będzie okazja, by więcej powiedzieć o szybkości działania wektora i porównać go z innymi strukturami danych.

£ańcuch znaków (string)

£ańcuch (ang. string) to tablica znaków traktowana jako pewien tekst. £ańcuchy mają szczególne znaczenie, ponieważ przechowuje się w nich wszelkie napisy pokazywane użytkownikowi i polecenia odbierane od użytkownika. Są dwa podstawowe sposoby używania łańcuchów w C++.

£ańcuch tradycyjny

Tradycyjny łańcuch to zwyczajna, statyczna lub dynamiczna tablica znaków. Przyjęło się, że jego zakończenie oznacza znak o kodzie 0. Dzięki temu nie trzeba osobno pamiętać jego długości. Oczywiście chodzi o faktyczną ilość znaków napisu, a ilość zarezerwowanych elementów tablicy może być większa. Takie podejście powoduje też dodatkowe ogranicznie, że w treści łańcucha nie mogą się znajdować znaki o kodzie 0.

£ańcuch

To jest najbardziej naturalny i najoszczędniejszy, ale nie najszybszy ani nie najwygodniejszy sposób implementacji łańcuchów. Jednak właśnie tego typu łańcuchami są w C++ wszystkie napisy objęte w cudzysłowy, np. "Jakiś tekst". Tego typu łańcuchów oczekują również funkcje Windows API. Rozpatrzmy przykład:

#include <iostream>
#include <windows.h>

int main()
{
  // tworzę łańcuch
  char *s = new char[256];
  // wpisuję tekst
  strcpy(s, "Ala");
  // dopisuję tekst
  strcat(s, " ma kota");
  // wypisuję na ekran
  std::cout << s << std::endl;
  // wypisuję długość
  std::cout << strlen(s) << std::endl;
  // wypisuję pierwszy znak
  std::cout << s[0] << std::endl;
  // pobieram od użytkownika
  std::cin >> s;
  // porównuję
  if ( strcmp(s, "spadaj") == 0 ) return 0;
  else MessageBox(0, s, "Wpisałeś:", MB_OK);
  // usuwam łańcuch
  delete [] s;
  return 0;
}

Oto krótki komentarz do powyższego kodu:

  • Jak widać, łańcuch jest zwykłą tablicą elementów typu char.
  • Funkcja strcpy() kopiuje łańcuch podany w drugim parametrze (jak widać, może to być stała dosłowna) do łańcucha podanego w pierwszym parametrze. Po tym wywołaniu s zawiera znaki: Ala oraz kończące zero.
  • Funkcja strcat() dołącza na koniec łańcucha podanego w pierwszym parametrze łańcuch podany w drugim. Po tym wywołaniu s zawiera znaki: Ala ma kota oraz zero kończące cały ten ciąg.
  • C++ potrafi poprawnie wypisać na ekran podany łańcuch, bo wypisuje po prostu kolejne znaki aż do napotkania zera.
  • Ilość znaków łańcucha (nie licząc kończącego zera) zwraca funkcja strlen().
  • Funkcja strcmp() zwraca 0, jeśli podane dwa łańcuchy są identyczne i wartość różną od zera, jeśli są różne.
  • Funkcja Windows API MessageBox() pobiera dwa parametry łańcuchowe. Jako tytuł okna z komunikatem podana została stała dosłowna "Wpisałeś:", a jako treść komunikatu zmienna s.

Jak widać, w przeciwieństwie do wszelkich języków skryptowych (jak PHP, TCL, LUA, Python itd.) w C++ łańcuchy znaków nie są typem wbudowanym, ale tablicą. Nie można tak po prostu stosować na nich, jak to się robi na liczbach, przypisania, porównania itp. Służą do tego specjalne funkcje.

Bardzo częstym błędem jest porównywanie łańcuchów w taki sposób:

if (s == "spadaj") return 0; // B£¡D !

Kompilator nie sygnalizuje problemów, ale kod nie działa prawidłowo. Problem polega na tym, że w rzeczywistości porównujemy wskaźniki typu char* - adres łańcucha s z adresem, pod którym umieszczona jest w pamięci podana stała dosłowna "spadaj". Dlatego nawet, jeśli obydwie tablice zawierają te same elementy, wynik porównania będzie fałszywy - bo są to dwie różne tablice. Porównywać trzeba zawartość tych tablic (kolejne znaki) i służy do tego opisana wyżej funkcja strcmp().

£ańcuch STL

Biblioteka standardowa C++ przychodzi nam z pomocą oferując alternatywną, wygodniejszą implementację łańcuchów. Oto ten sam przykład napisany z jej użyciem:

#include <iostream>
#include <string>
#include <windows.h>

int main()
{
  // deklaruję łańcuch
  std::string s;
  // wpisuję tekst
  s = "Ala";
  // dopisuję tekst
  s += " ma kota";
  // wypisuję na ekran
  std::cout << s << std::endl;
  // wypisuję długość
  std::cout << s.size() << std::endl;
  // wypisuję pierwszy znak
  std::cout << s[0] << std::endl;
  // pobieram od użytkownika
  std::cin >> s;
  // porównuję
  if (s == "spadaj") return 0;
  else MessageBox(0, s.c_str(), "Wpisałeś:", MB_OK);
  return 0;
}

£ańcuch STL najlepiej będzie omówić porównując go z łańcuchami tradycyjnymi.

Cecha Tradycyjny STL
Nagłówek (brak) #include <string>
Typ char* std::string
Pamięć Trzeba samemu alokować Sam się realokuje
Ograniczenia Nie może zawierać znaku 0 Może zawierać dowolne znaki
Przypisanie Funkcja strcpy() Operator przypisania =
Konkatenacja (łączenie) Funkcja strcat() Operator zwiększania += lub dodawania +
Długość Funkcja strlen() Funkcja s.size()
Odwołanie do znaku Operator s[indeks] Operator s[indeks]
Porównanie Funkcja strcmp() Operator porównania == lub !=
Kompatybilność z funkcjami Windows API (jest) Funkcja s.c_str() zwraca łańcuch STL "przerobiony" na tradycyjny (nie trzeba go zwalniać!)

Często trzeba przekazywać łańcuchy jako parametry do funkcji. Żeby uniknąć przy tym ich kopiowania, warto zawsze robić to w taki sposób:

void MyMessage(const std::string &msg)
{
  MessageBox(0, msg.c_str(), "Komunikat", MB_OK);
}

Konstrukcja const std::string &msg oznacza przekazywanie parametru przez referencję do stałej. Dzięki temu zagwarantowane jest, że:

  1. Podczas przekazywania parametru nie zostanie wykonana kopia łańcucha.
  2. Nie będzie można wewnątrz funkcji zmieniać oryginalnej treści podanego łańcucha.
  3. Można podawać do funkcji stałą dosłowną, np.: MyMessage("Nastąpił straszny błąd");.

Tablica dwuwymiarowa (macierz)

Tablica dwuwymiarowa to taka tablica, do której elementów odwołujemy się za pomocą dwóch indeksów. Można ją sobie wyobrazić jako obszar pokryty kwadratami albo jako wektor wektorów. Macierz ma szerokość i wysokość. To, który indeks potraktujemy jako numer kolumny, a który jako numer wiersza, to kwestia umowna. Dlatego w tym artykule często jest to pomieszane. Istnieje kilka sposobów, na jakie można napisać tablicę dwuwymiarową.

Tablica dwuwymiarowa

Statyczna tablica dwuwymiarowa

Najprościej jest zadeklarować tablicę statyczną. Ma ona wszystkie te ograniczenia, co statyczna tablica jednowymiarowa (wektor).

// szerokość i wysokość
const int WIDTH = 3;
const int HEIGHT = 2;
// tablica
char tab[WIDTH][HEIGHT];
// wypełnienie tablicy różnymi znakami
int x, y;
for (y = 0; y < HEIGHT; y++) {
  for (x = 0; x < WIDTH; x++) {
    tab[x][y] = 'A' + x + y;
  }
}

Możnaby zastanawiać się, w jakiej kolejności elementy takiej tablicy umieszczone są w - jednowymiarowej przecież - pamięci? Otóż zasada jest taka, że najszybciej zmienia się ostatni indeks. Kolejnymi elementami tej tablicy są więc:

tab[0][0]
tab[0][1]
tab[1][0]
tab[1][1]
tab[2][0]
tab[2][1]

Dynamiczna tablica dwuwymiarowa

Pomysł na realizację dynamicznej tablicy dwuwymiarowej polega na utworzeniu tablicy tablic. Będziemy więc musieli użyć wskaźnika do wskaźnika.

Tablica tablic

Przyjrzyj się powyższemu rysunkowi oraz poniższemu kodowi i postaraj się je zrozumieć.

// zmienne do pętli
int x, y;
// szerokość i wysokość
int width = 3;
int height = 2;
// UTWORZENIE TABLICY
// - tej żółtej
char **tab = new char*[width];
// - tych zielonych
for (x = 0; x < width; x++) {
  tab[x] = new char[height];
}
// wypełnienie tablicy różnymi znakami
for (y = 0; y < height; y++) {
  for (x = 0; x < width; x++) {
    tab[x][y] = 'A' + x + y;
  }
}
// USUNIęCIE TABLICY
// - tych zielonych
for (x = 0; x < width; x++) {
  delete [] tab[x];
}
// - tej żółtej
delete [] tab;

Tablica dwuwymiarowa zlinearyzowana

Drugim możliwym sposobem na napisanie dynamicznej tablicy dwuwymiarowej (i moim ulubionym) jest jej zlinearyzowanie, czyli przedstawienie w postaci jednowymiarowej tablicy o długości równej szerokość*wysokość. Żeby to zrobić, potrzebny nam będzie wzór zamieniający indeksy tablicy dwuwymiarowej x i y na indeks tablicy jednowymiarowej i. Spójrzmy najpierw na poniższy rysunek:

Linearyzujemy macierz

Wyobraź sobie, że ta macierz jest rozłożona do jednowymiarowej tak, że po kolei następują po sobie kolejne wiersze. Chcemy dostać się do komórki zawierającej znak gwiazdki * o indeksie [3][2]. Policzywszy ciemniejsze pola wiemy, że musimy w tym celu przejść 16 komórek - naszym poszukiwanym indeksem jednowymiarowym jest 15.

Żeby go otrzymać, trzeba przejść przez tyle szerokości tablicy, ile wynosi numer wiersza (2) i dodać do tego numer kolumny (3). Oto gotowy wzór (warto go zapamiętać!):

i = y * width + x

W naszym przypadku mamy: 2*6+3 = 12+3 = 15. Po raz kolejny okazuje się, że indeksowanie od zera przynosi doskonałe efekty! Najwyższy czas na implementację:

// szerokość i wysokość
int width, height;
// tablica
char *tab;

// Funkcja tworzy tablicę o podanych wymiarach
void Create(int a_width, int a_height)
{
  width = a_width;
  height = a_height;
  tab = new char[width*height];
}

// Funkcja usuwa tablicę
void Destroy()
{
  delete [] tab;
}

// Funkcja zamienia indeksy x,y na indeks jednowymiarowy i
inline xy2i(int x, int y)
{
  return (y * width + x);
}

// Funkcja zapisuje znak do podanej komórki
inline void Set(int x, int y, char c)
{
  tab[ xy2i(x, y) ] = c;
}

// Funkcja odczytuje i zwraca znak z podanej komórki
inline char Get(int x, int y)
{
  return tab[ xy2i(x, y) ];
}

Różne macierze

Macierz kwadratowa to macierz, która ma taką samą szerokość, jak wysokość.

Macierz trójkątna to taka macierz, która ma istotne wartości tylko po jednej stronie przekątnej. Przykładem może być tabela odległości między miastami. Jeśli odległość z Częstochowy do Siedlec wynosi 320 km, to nie ma sensu zapisywać odległości z Siedlec do Częstochowy.

Macierz trójkątna

Gdyby do przechowywania macierzy trójkątnej używać standardowej prostokątnej tablicy dwuwymiarowej, połowa pamięci marnowałaby się. To niedopuszczalne. Można ją zrealizować lepiej albo w postaci zlinearyzowanej (trzeba wtedy wymyślić odpowiedni wzór do indeksowania), albo w postaci tablicy tablic, z których każda z tych tablic ma inną długość.

Macierz nieregularna to taka, w której każdy wiersz ma inną liczbę kolumn (albo odwrotnie). Ją także można bardzo dobrze napisać używając tablicy przechowującej wskaźniki do tablic o różnej długości.

Macierz nieregularna

Lista łączona

Lista to druga po wektorze najważniejsza struktura danych i w pewnym sensie jego przeciwieństwo. Jej idea jest zupełnie inna, niż omawianych dotychczas tablic.

Lista łączona jest zbudowana tak: mamy wskaźnik do pierwszego elementu, a każdy element oprócz swojej wartości przechowuje wskaźnik do następnego elementu. Ostatni element ma wskaźnik do następnego ustawiony na 0 (adres pusty).

Lista łączona

Jak działa lista?

Nie będziemy pisali własnej listy. Omówimy tylko ogólnie zasadę jej działania. W kodzie lista byłaby zapewne zdefiniowana w taki sposób:

struct Element
{
  char value;
  Element *next;
}

// to jest nasza lista
Element *first;

Mając wskaźnik do pierwszego elementu i odczytując wskaźniki do kolejnych można przejść wszystkie elementy list. Gorzej, jeśli potrzebne byłoby dostać się do konkretnego elementu, np. piątego. W przeciwieństwie do wektorów, tutaj trzeba przejść przez wszystkie poprzednie (pierwszy, drugi, trzeci, czwarty) odczytując wskaźniki do następnych. Indeksowanie listy ma więc złożoność liniową - rzędu O(n).

Ale lista ma też zalety. Bardzo proste jest wstawianie nowego elementu w konkretne miejsce. Wystarczy odpowiednio powiązać wskaźniki z poprzednim i następnym. Nie trzeba przepisywać żadnych elementów, jak to było w wektorze. Osobnymi blokami pamięci rezerwowanymi dla pojedynczych elementów zarządza sam system.

Dodawanie do listy

Usuwanie elementów jest równie proste. Wystarczy usunąć z pamięci dany element, a wskaźnik w poprzednim ustawić na następny.

Usuwanie z listy

Podsumowując, powinieneś zapamiętać następujące wiadomości na temat listy:

  • Nie ma dostępu swobodnego - elementy trzeba przechodzić po kolei.
  • Wstawianie i usuwanie elementów jest bardzo proste i szybkie.

Lista STL

Implementacji tak ważnej struktury danych nie mogło oczywiście zabraknąć pośród gotowych do wykorzystania, standardowych kontenerów STL. Zobaczmy, jak wygląda jej wykorzystanie:

#include <iostream>
#include <list>

int main()
{
  // deklaracja listy
  std::list<char> l;
  // dodanie elementu na koniec
  l.push_back('A');
  // wstawienie elementu na początek
  l.insert(l.begin(), 'B');
  // usunięcie wszystkich elementów 'A'
  std::list<char>::iterator it;
  for (it = l.begin(); it != l.end(); ++it) {
    if ( *it == 'A' ) {
      it = l.erase(it);
    }
  }
  return 0;
}
  • #include <list> - taki nagłówek trzeba włączyć, aby skorzystać z listy STL.
  • std::list<char> - tak deklaruje się listę. Cały ten łańcuch to typ deklarowanej zmiennej l. W nawiasach kątowych pisze się typ elementów listy. Wskaźnik na następny element STL realizuje sobie sam.
  • Funkcja push_back() dodaje podany element na końcu listy.
  • Funkcja insert() wstawia podany element w miejscu określonym przez podany iterator. Funkcja begin() zwraca iterator do pierwszego elementu.
  • Funkcja erase() usuwa element, na który wskazuje podany iterator i zwraca iterator do następnego elementu (tamten już nie byłby poprawny i nie wolno byłoby go używać!).

Jak widać, używanie listy STL jest bardzo podobne do używania wektora STL. W szczególności warto zwrócić uwagę na użycie iteratorów - lista nie oferuje innego rodzaju dostępu do elementów. Iteratory były szerzej opisane przy okazji opisu wektora.

Różne listy

Lista dwukierunkowa to taka lista, w której przechowujemy wskaźnik na pierwszy i ostatni element, a każdy element przechowuje wskaźnik na poprzedni i następny. Taką listę można przechodzić w obydwie strony. Lista STL jest tak naprawdę listą dwukierunkową.

Lista dwukierunkowa

Lista z wartownikiem to taka lista, do której dołączamy poszukiwany element. Dzięki temu podczas przeszukiwania nie musimy sprawdzać dwóch warunków - czy element odnaleziono i czy osiągnięto koniec listy - tylko ten pierwszy. Potem wystarczy sprawdzić: jeśli odnaleziony element to wartownik, to znaczy, że we właściwej kolekcji szukanego elementu nie było.

Lista cykliczna to taka lista, w której ostatni element nie pokazuje na adres pusty (0), tylko na pierwszy i tak powstaje zamknięty obieg.

Lista wielowątkowa to lista, której elementy mają po kilka wskaźników na następny element. Każdy z nich tworzy osobną listę i dzięki temu te same elementy mogą być w różnych listach umieszczone w różnej kolejności, np. posortowane wg różnych kryteriów.

Macierz rzadka to taka macierz, w której tylko nieliczne elementy posiadają jakąś znaczącą wartość (np. różną od 0).

Macierz rzadka

Wspominam o niej dopiero teraz, bo jej najoszczędniejszą implementacją jest właśnie lista (na poniższym przykładzie widać, że sama kolekcja wierszy (ta żółta) też jest macierzą rzadką i została zrealizowana w postaci listy).

Macierz rzadka jako lista

Talia

Lista była jakby przeciwieństwem wektora, a podobno wszelkie skrajności są niedobre. Dlatego czas na omówienie struktury danych, która w pewnym sensie łączy wektor i listę, a w pewnym sensie jest czymś pośrednim.

Talia (ang. deque) to, najprościej mówiąc, lista wektorów. Nie pojedynczy wektor, tylko ich lista i nie lista pojedynczych elementów, tylko całych wektorów.

Talia

Można sobie wyobrazić przechodzenie kolejnych elementów takiej struktury. Rozpatruje się kolejne elementy wektora, a na końcu skacze się po wskaźniku do następnego.

Także bezpośrednie indeksowanie któregoś elementu nie jest tak czasochłonne, jak w przypadku listy (choć nie tak szybkie, jak w przypadku wektora). Trzeba skakać po kolejnych wektorach, ale tych skoków będzie wielokrotnie mniej, niż pojedynczych elementów.

Dodawanie nie wymaga przesuwania wszystkich elementów. Wystarczy przesunąć elementy danego wektora, a jeśli się nie mieszczą - przealokować go lub wstawić do listy nowy wektor. Analogicznie można sobie wyobrazić usuwanie.

Charakterystyczne dla talii jest również to, że dodawanie i usuwanie elementów na jej początku jest równie szybkie, co na końcu. Dlatego nazywana bywa też kolejką o dwóch końcach.

Talia STL

Żeby używać talii STL, trzeba włączyć taki nagłówek: #include <deque>. Stosowny typ nazywa się natomiast deque, np. std::deque<char> MyDeque;.

To w zasadzie wszystko, co trzeba wiedzieć o talii STL. Używa się jej dokładnie tak samo, jak listy czy wektora - łącznie z wykorzystaniem iteratorów, funkcjami składowymi, a także możliwością indeksowania za pomocą operatora nawiasów kwadratowych [].

Zestawienie

Cecha Wektor Talia Lista
Nagłówek #include <vector> #include <deque> #include <list>
Typ std::vector<> std::deque<> std::list<>
Przechodzenie po kolei (iterowanie) + Szybkie + Szybkie + Szybkie
Dostęp swobodny (indeksowanie) + Szybkie * Średnie - Wolne
Wstawianie i usuwanie na końcu + Szybkie + Szybkie + Szybkie
Wstawianie i usuwanie na początku - Wolne + Szybkie + Szybkie
Wstawianie i usuwanie w środku - Wolne * Średnie + Szybkie

Podsumowując:

  1. Wektora należy używać, kiedy najważniejszy jest szybki dostęp do dowolnych elementów przez indeksy.
  2. Listy należy używać, kiedy najważniejsze jest szybkie wstawianie i usuwanie elementów w dowolnym miejscu.
  3. Talii należy używać, kiedy potrzebne są obydwie te cechy na raz.

Przez "najważniejsze" należy rozumieć, że dana operacja jest wykonywana bardzo często.

Stos i kolejka

Nie zawsze potrzebna jest pełna funkcjonalność kontenera. Niekiedy wystarczy ograniczyć się do niektórych operacji, szczególnie jeśli chodzi o miejsce dodawania i usuwania elementów. Stos i kolejka to właśnie nazwy takich ograniczeń, a nie nowe struktury danych.

Stos

Stos (ang. stack), inaczej kolejka LIFO (ang. last in first out - ostatni wejdzie pierwszy wyjdzie) to taka struktura danych, w której mamy dostęp tylko do pojedynczego elementu na jednym końcu zwanym wierzchołkiem stosu (ang. top).

Stos można sobie wyobrazić jako stos brudnych talerzy po obiedzie. Talerze odkłada się na wierzchu, a potem do zmywania zdejmuje się je z wierzchu w odwrotnej kolejności. Nie wyjmujemy talerzy gdzieś z środka, bo cały stos by się zawalił, a talerze by się potłukły.

Stos

Stos w STL

STL oferuje otoczkę na wybrany kontener (adaptator) realizującą stos. Domyślnie używana jest w tym celu talia. Stos jest tak prosty, że poniższy przykład prezentuje wszystkie jego funkcje składowe:

#include <iostream>
#include <stack>

int main()
{
  // deklaruję stos
  std::stack<char> s;
  // odkładam element
  s.push('A');
  // wypisuję liczbę elementów
  std::cout << s.size() << std::endl;
  // wypisuję element z wierzchu
  std::cout << s.top() << std::endl;
  // usuwam element z wierzchu
  s.pop();
  // sprawdzam, czy stos jest pusty
  if ( s.empty() )
    std::cout << "Stos jest pusty" << std::endl;
  return 0;
}

Push i pop to zwyczajowo przyjęte nazwy dla czynności odkładania elementu na stos i zdejmowania elementu ze stosu. Czasami uznaje się, że odczytanie elementu ze szczytu stosu i jego usunięcie to jedna i nierozłączna czynność. Na szczęście STL daje większą swobodę zapewniając osobno dostęp do elementu z wierzchu bez jego usuwania (funkcja top()) oraz usuwanie elementu z wierzchu bez jego odczytywania (funkcja pop()).

Kolejka

Kolejka (ang. queue), inaczej kolejka FIFO (ang. first in first out - pierwszy wejdzie pierwszy wyjdzie) to taka struktura danych, w której elementy można dodawać tylko z jednej strony, a usuwać tylko z drugiej.

Można sobie ją wyobrazić jako kolejkę ludzi przy kasie w supermarkecie. Jeden koniec kolejki, nazywany koniec (ang. back) to jedyne miejsce, do którego nowi klienci mogą dochodzić. Drugi, nazywany początek (ang. front) to jedyne miejsce, z którego klienci mogą odchodzić z zakupami. Nie można wepchnąć się w środek kolejki, bo ludzie się zdenerwują.

Kolejka

Mimo zbieżności angielskich nazw kolejka (ang. queue) nie ma niczego wspólnego z talią (ang. deque). Talia to, obok wektora i listy, jedna z podstawowych struktur danych a kolejka to, obok stosu, jeden z rodzajów ograniczeń, jakie często nakłada się na struktury.

Kolejka w STL

Kolejka STL jest podobna do stosu. Jedyną różnicą jest to, że elementy dodawane są na końcu, a usuwane na początku. Mamy dostęp zarówno do pierwszego, jak i do ostatniego. Poniższy przykład wypisuje litery B i A.

#include <iostream>
#include <queue>

int main()
{
  // deklaruję kolejkę
  std::queue<char> q;
  // dodaję elementy na końcu
  q.push('A');
  q.push('B');
  // wypisuję element z końca
  std::cout << q.back() << std::endl;
  // wypisuję element z początku
  std::cout << q.front() << std::endl;
  // usuwam element z początku
  q.pop();
  return 0;
}

Drzewo

Na wektorze, liście i talii zakończyliśmy poznawanie sekwencyjnych struktur danych - czyli takich, w których elementy są umieszczone kolejno jeden za drugim. Można wyobrazić sobie inny układ elementów, np. hierarchię. Właśnie taką budowę mają drzewa.

Drzewo (ang. tree) to hierarchiczna struktura danych, w której każdy element może mieć swoje podelementy. Można go porównać do:

  • struktury katalogów i plików na dysku - na każdym dysku zaczyna się od katalogu głównego i każdy katalog może zawierać pliki oraz następne katalogi
  • drzewa jako rośliny - główny pień rozdziela się na szereg gałęzi, z nich wyrastają kolejne gałęzie itd. aż do liści, z których nic już nie wyrasta
  • drzewa genealogicznego - każdy członek rodziny może mieć dzieci, te dzieci mogą mieć swoje dzieci itd.

Drzewo

Drzewa to bardzo obszerny i niełatwy temat. Nie będę go omawiał dokładnie, ale warto znać pewne podstawy. Oto najważniejsze związane z nimi pojęcia:

Węzeł
to element drzewa.
Korzeń
to element na pierwszym poziomie - ten główny.
Węzeł potomny
to pod-węzeł danego węzła - tak jak podkatalog na dysku.
Liść
to węzeł nie posiadający węzłów potomnych - na rysunku zaznaczone są ciemnym kolorem.
Gałąź
to pewna ścieżka połączeń w drzewie.

Zastanówmy się teraz przez chwilę, jak możnaby napisać drzewo? Z pewnością byłoby to coś podobnego do listy łączonej z tym, że każdy element musiałby przechowywać listę (a może wektor?) wskaźników na swoje węzły potomne. Ale gdyby maksymalna liczba węzłów potomnych była ograniczona, wtedy możnaby zamiast tego użyć po prostu kilku pól wskazujących na te węzły potomne lub na adres pusty.

struct Element
{
  char value;
  Element *sub1;
  Element *sub2;
}

// to jest nasze drzewo
Element *root;

Można też wymyślić sposób na zlinearyzowanie drzewa, czyli przechowywanie go w zwykłej jednowymiarowej tablicy.

Drzewa bywają różne - stosownie do potrzeb. Często nakłada się na nie specjalne wymagania i ograniczenia, np. w sprawie pewnego posortowania (ułożenia węzłów w pewnym porządku). Natomiast według maksymalnej ilości węzłów potomnych możemy wyróżnić:

Drzewa binarne
każdy węzeł może mieć maksymalnie 2 węzły potomne.
Drzewa czwórkowe
każdy węzeł może mieć maksymalnie 4 węzły potomne.

Przejdźmy teraz to metod przechodzenia drzewa. Drzewa są tak trudne, że nawet ten proces bywa przedmiotem obszernych opisów. Najważniejsze jest to, że nie wystarczy już przechodzić w pętli kolejnych elementów (iteracyjnie). Pierwszym nasuwającym się sposobem przechodzenia drzewa jest wyjście od korzenia i dla każdego węzła przeglądanie wszystkich jego pod-węzłów (rekurencyjnie). Są też różne inne sposoby.

Z drzewami związana jest pewna bardzo ważna właściwość. Wyobraźmy sobie dla przykładu drzewo binarne tak posortowane, że węzeł potomny z lewej strony każdego węzła i wszystkie jego węzły potomne mają wartość mniejszą od niego, a węzeł potomny każdego węzła z prawej strony i wszystkie jego podwęzły mają wartość większą od niego. Szukając konkretnej wartości w takim drzewie wymieramy stale drogę w prawo lub w lewo, a tym samym ograniczamy ilość potencjalnych możliwości o około połowę. Taki algorytm ma złożoność logarytmiczną, a więc bardzo dobrą! Do przeszukania ok. 1000 elementów wystarcza 10 kroków.

Dlatego drzewa są bardzo dobrym rozwiązaniem skomplikowanych problemów. Niestety, nie są proste w implementacji. STL nie dostarcza też żadnych uogólnionych mechanizmów do pisania drzew. Istnieje jednak kilka kontenerów STL o bardzo ciekawych właściwościach, których wewnętrzna budowa oparta jest na drzewach. Zajmijmy się nimi.

Zbiory i wielozbiory STL

Zbiór STL to kontener, który przechowuje swoje elementy w posortowanym drzewie. Dzięki temu zapewnia bardzo szybkie wyszukiwanie. Wiążą się z tym jednak trzy ograniczenia:

  1. Elementów nie można modyfikować - żeby to zrobić trzeba usunąć stary, a potem dodać nowy.
  2. Elementy muszą być takiego typu, żeby kontener mógł je porównywać (czyli stwierdzić, czy jeden jest większy od drugiego), co jest potrzebne podczas sortowania - np. liczby, znaki albo typy własne, w których specjalnie postaramy się o możliwość ich porównywania.
  3. Elementy nie mogą się powtarzać - nie może być kilku takich samych.

Oto przykład użycia zbioru i jego zwięzłe omówienie:

#include <iostream>
#include <set>

int main()
{
  // deklaruję zbiór
  std::set<char> s;
  // dodaję elementy
  s.insert('A');
  s.insert('B');
  // znajduję literkę A
  std::set<char>::iterator it = s.find('A');
  // jeśli się znalazła
  if ( it != s.end() )
    // usuwam ją
    s.erase(it);
  // wypisuję wszystkie elementy
  for (it = s.begin(); it != s.end(); ++it)
    std::cout << *it << std::endl;
  return 0;
}
  • #include <set> - taki nagłówek trzeba włączyć, aby skorzystać ze zbioru STL.
  • std::set<char> - tak deklaruje się zbiór. Cały ten ciąg to typ deklarowanej zmiennej s. W nawiasach kątowych pisze się typ elementów zbioru.
  • Funkcja insert() dodaje element do zbioru. Pamiętamy, że kolejność nie jest zachowana - zbiór sortuje sobie te elementy.
  • std::set<char>::iterator - takiego typu są iteratory pokazujące na elementy zbiorów.
  • Funkcja find() szuka elementu o podanej wartości i zwraca iterator wskazujący na niego. Jeśli element się nie znajdzie, zwraca iterator pusty - równy wartości zwracanej przez funkcję end().
  • Funkcja erase() usuwa ze zbioru element, na który pokazuje podany iterator.
  • Jak widać, mimo skomplikowanej budowy wewnętrznej, zbiór STL pozwala też przechodzić kolejno w pętli wszystkie swoje elementy za pomocą iteratorów dokładnie tak samo, jak poznane wcześniej kontenery sekwencyjne.

Istnieje także drugi typ - std::multiset<char>. Wymaga włączenia tego samego nagłówka, a od zwykłego zbioru różni się tym, że wartości mogą się w nim powtarzać - ta sama wartość może być w zbiorze kilka razy.

Mapy i multimapy STL

Problem polega na tym, że najczęściej chcielibyśmy przechowywać w zbiorze elementy jakiegoś bardziej złożonego typu, których on nie będzie potrafił bezpośrednio porównywać (stwierdzać, że jeden jest większy od drugiego), a przez to sortować. Zwykle jest tak, że element posiada szereg pól, z których jeden powinien stanowić kryterium sortowania i wyszukiwania. Tutaj z pomocą przychodzi kolejny kontener STL - mapa.

Mapa jest bardzo podobna do zbioru, ale przechowuje kolekcję elementów - tzw. par, z których każda posiada klucz i wartość. Elementy sortuje sobie według klucza i według niego pozwala szybko je wyszukiwać. Rozważmy przykład bazy danych dla firmy, w której mają być przechowywane informacje o klientach w postaci par: jakiś numer identyfikacyjny (liczba) -> opis (łańcuch).

#include <iostream>
#include <string>
#include <map>

int main()
{
  // deklaruję mapę
  std::map<int, std::string> m;
  // dodaję elementy
  m.insert( std::make_pair(7, "Jan Kowalski - bardzo solidny klient") );
  m.insert( std::make_pair(666, "Maciej Nowak - Klient bardzo niesolidny") );
  // znajduję osobę o numerze 7
  std::map<int, std::string>::iterator it = m.find(7);
  // jeśli się znalazła
  if ( it != m.end() ) {
    // wypisuję jej opis
    std::pair<int, std::string> p = *it;
    std::cout << p.second << std::endl;
  }
  return 0;
}

Cała trudność w nauczeniu się używania mapy polega na zrozumieniu, jak należy używać par STL.

  • #include <map> - taki nagłówek trzeba włączyć, żeby skorzystać z mapy STL.
  • std::map<int, std::string> - takiego typu jest zadeklarowana w przykładzie mapa m. Jak widać, w nawiasie kątowym podaje się dwa typy - typ klucza i typ wartości. Elementami mapy będą nierozłącznie związane pary - w tym przypadku pary liczba - łańcuch.
  • Funkcja insert() wstawia do mapy parę. Żeby ją utworzyć, używamy funkcji make_pair(), która pobiera dwie niezależne wartości i zwraca parę, która je zawiera zestawione razem.
  • Funkcja find() wymaga tylko podania klucza, a zwraca iterator pokazujący na odnaleziony element (czyli na parę). Jeśli element się nie znajdzie, zwrócony zostaje błędny iterator - równy wartości zwracanej przez funkcję end().
  • std::pair<int, std::string> - takiego typu jest tak naprawdę każda para w naszym przykładzie, czyli element naszej mapy. Deklarujemy osobną zmienną tego typu i przepisujemy do niej parę, na którą pokazuje otrzymany iterator.
  • Na ekran wypisana zostaje wartość, czyli drugi spośród składników pary. Znajduje się on w polu o nazwie second i jest łańcuchem. Pierwszy składnik pary, który w mapie pełni rolę klucza, znajduje się w polu o nazwie first i w tym przykładzie jest liczbą.

W normalnej mapie nie może istnieć kilka elementów o takim samym kluczu. Analogicznie, jak to było ze zbiorami, mapa posiada także specjalną odmianę pozwalającą na to. Wymaga ona włączenia tego samego nagłówka, a odpowiedni typ nazywa się multimap<>.

Teraz, po omówieniu map, chciałbym jeszcze raz przypomnieć i podsumować, która struktura do czego się nadaje.

Wektor
jest dobry, kiedy najważniejszy jest szybki, swobodny dostęp do dowolnych elementów przez indeksowanie.
Lista
jest dobra, kiedy najważniejsze jest szybkie wstawianie i usuwanie elementów w dowolnym miejscu.
Mapa
jest dobra, kiedy najważniejsze jest szybkie znajdowanie elementów.

Graf

Drzewo wyglądało na dość swobodną organizację danych, jednak nie do końca. Połączenia między elementami nie mogły tworzyć cykli. Grafy to struktury pozbawione jakichkolwiek ograniczeń. Jednocześnie są

Tekst dodał:
Adam Sawicki
15.02.2006 20:07

Ostatnia edycja:
Adam Sawicki
15.02.2006 20:07

Kategorie:

Aby edytować tekst, musisz się zalogować.

# Edytuj Porównaj Czas Autor Rozmiar
#1 edytuj 15.02.2006 20:07 Adam Sawicki 64 KB
Zwykły
Do sprawdzenia
Do akceptacji
  • ~zerlo 21 czerwca 2007 17:10
    Bardzo pomocne. Gdyby nie ten artykul ciagle, do przechowywania wiekszych zbiorow danych, uzywalbym zwyklych tablic. Dziekuje...
  • ~RedHot 08 lipca 2007 16:16
    Echhh , artykuł nie bardzo. Za duży temat by go opracować w ten sposób . Zdarzają się błędy merytoryczne ,a jak chce się coś wytłumaczyć dobrze to zapomnijmy o ogółach ogółów. Dodatkowo widać ,że wiedzę masz ,ale niektóre rzeczy traktujesz jako zbyt oczywiste przez co czytelnik nie rozumie działania niektórych funkcji (chodzi konkretnie o operowanie na pliku w windos.h)

    1) sprawda pojemników a)Od kiedy wektor to to samo co tablica jednowymiarowa? Wektor ma wbudowane funkcje i prawie zawsze przechowuje tablicę, co nie czyni go tablicą b) Napisałes lista łączona, a znasz inne? Trzeba było napisać lista łączona pojedynczo (jednokier.) oraz lista łączona podwójnie (dwukier.)

    2. Typy plików Z tej dziedziny jestem gorszy czyli artykuł się przydał. Niestety brakuje często pliku z zasosowaniem i nie wiem dlaczego funkcja MyRead nie może wczytać znaku z pliku do pamięci (otwarcie pliku jak i ustawienie wskaźnika udało się). Podobnie w definicji wlasnego typu przydałby się kod źródłowy jak i definicja klasy Potwor.

    Jeśli chciałoby Ci się poświęcić czas na rozszerzenie artykułu o typach plików ,kompresji etc. i napisanie specjalnego arta o tym, byłbym więcej niż zadowolony. ;)

    P.S Są to oczywiście moje subiektywne odczucia, nie każdy musi się z nimi zgodzić.
  • nameczanin (@nameczanin) 27 grudnia 2007 23:18
    Grzesiek: (23:15) obejrzałem 40 odcinek a teraz oglądne 41 Ja: (23:17) nie lepiej od 0? -_-
  • ~Liseeeek 14 marca 2008 13:52
    Supeeer Dziekuje bardzo :)
  • ~Paweł 20 marca 2008 00:59
    Jestem starym PIERDZIELEM który dalej się uczy. Elektronikiem który zaczynał od ASEMBLERA 8080. Ale zauważam że asembler w Windowsie, nieróżni się bardzo od "C++". I tak wszystko polega na zapamiętaniu (lub znalezieniu) odpowiednich procedur Windowsa. Nie mogę ę się przekonać do KLAS. Za moich czasów oszczędność pamięci i procesora była zaletą. Zauważam że ELEKTRONIKA bez informatyki to już powoli się kończy. Wielokrotnie obiecywałem sobie że nauczę sie pisać programy pod te BLONDYNKOWE OKIENKA. Aż wreszcie przyszła kryska na ELEKTRONIKA. Niestety nie wie jeszcze czego nie wiem. Skaczę po tutorialach artykułach i brakuje mi narzędzi, sprawdzonych funkcji, algorytmów.Najgorsze jest to że języków to parę znam ale po łebkach, łącznie z angielskim. Ale niema że boli. Dziękuję za już i proszę o jeszcze. Proszę nie przejmować się głosami "WIELCE FACHOWEJ" krytyki, zapomniał wół jak zaczynał od ośmiobitowca.
  • ar3le5n (@ar3le5n) 18 kwietnia 2014 19:40
    Czy mógłbym prosić o ponowne zaimportowanie artykułu ? ( brak formatów plików )
  • Napisz komentarz:
    Aby dodać swój komentarz, musisz się zalogować.
Licencja Creative Commons

Warsztat używa plików cookies. | Copyright © 2006-2017 Warsztat · Kontakt · Regulamin i polityka prywatności
build #ff080b4740 (Tue Mar 25 11:39:28 CET 2014)