Struktury
Rozważmy przykład prostej bazy danych, przechowującej imiona i nazwiska osób. Można to zrealizować dwoma tablicami napisów, jedna tablica dla imion, druga dla nazwisk.
std::string imiona[ N ], nazwiska[ N ];
Takie rozwiązanie nie jest bez wad, aby dane w takiej bazie miały sens, wszystkie tablice muszą być spójne. Nie chcemy przecież żeby imiona się pomieszały z nazwiskami, jeśli coś pójdzie nie tak przy usuwaniu kogoś. Problem jest tym gorszy, im więcej chcemy przechowywać informacji o danej osobie. Dorzuć do tego numer telefonu, adres zamieszkania, numer PESEL i dowodu osobistego i nagle robi się z tego nieprzyjemny w utrzymaniu bałagan (tzn. kod jest nieprzyjemny w utrzymaniu, nie bałagan). Gdyby tak tylko można było powiedzieć
chcę mieć tablicę osób.
I da się. Tylko trzeba jakoś zdefiniować "osobę", bo w końcu zmienna, czy tablica, musi być jakiegoś typu. Od tego jest
struktura - pozwala zdefiniować
złożony typ, czyli taki który ma jakieś
składowe w środku. Osoba w tym przykładzie składa się z imienia i nazwiska:
struct Osoba
{
std::string imie, nazwisko;
};
Taka składnia definiuje nowy typ złożony
Osoba, o składowych
imie i
nazwisko typu
std::string. Zwróć szczególną uwagę na średnik po zamykającym nawiasie klamrowym. Definicja typu musi być zakończona średnikiem.
Teraz można utworzyć tablicę osób, lub zmienną, jak dla każdego innego typu
Mając już jakiś egzemplarz struktury, wypadałoby wiedzieć jak się dostać do jego składowych. Służy do tego operator kropki
jan.imie = "Jan";
jan.nazwisko = "Kowalski";
osoby[ 0 ].imie = "Adam";
Składową można posługiwać się jak normalną zmienną, bo to jest zmienna, tylko tyle że znajduje się w środku innej zmiennej.
Struktury i wskaźniki
W przypadku, gdy dysponujemy wskaźnikiem na obiekt struktury, dostęp do składowych się delikatnie komplikuje. Operator kropki ma wyższy priorytet od gwiazdki (dereferencji) więc wydobycie składowej spod wskaźnika wymaga użycia nawiasu:
Osoba * wsk = & jan;
wsk.imie;
* wsk.imie;
( * wsk ).imie;
Problem tylko w tym, że taki zapis jest bolesny. Trochę bardziej złożony przypadek i kod mógłby zacząć wyglądać jak napisany w Lispie. Całe szczęście, że ten przypadek ma też swój własny operator, "strzałkę":
Ten zapis jest szczególnie przydatny, gdy trzymamy w strukturze wskaźniki na struktury. W szczególności możemy trzymać w strukturze wskaźnik, na obiekt tego samego typu:
struct Test
{
Test * inny;
};
Można tak napisać, ponieważ można utworzyć wskaźnik na
typ niekompletny. Znaczenie tego terminu powinno być w miarę intuicyjne. Kompilator przetwarza kod od góry do dołu, więc widząc
struct Test wie już, że jest taki typ, tylko że jest on niekompletny - nie wiadomo ile potrzeba zarezerwować pamięci, kiedy już przyjdzie do utworzenia faktycznego obiektu. Dopiero w momencie przetworzenia zamykającej klamry
} typ zostaje uznany za kompletny. Typ można zadeklarować, czyli napisać
struct Nazwa i postawić od razu średnik. Typ można potem 'skompletować' dopisując jego definicję:
struct A;
struct B
{
A * a;
};
struct A
{
B * b;
};
Wewnątrz ciała struktury
X można więc utworzyć wskaźnik
X*, ale już nie obiekt
X, bo
X jest wtedy niekompletnym typem. Gdyby się dało, typ
X miałby nieskończenie wielki rozmiar, co sprawiałoby trudności raczej skończenie wielkim zasobom pamięciowym komputera.
Struktura staje się kompletna już w momencie przetworzenia zamykającej klamry, więc.. skoro kompilator wie gdzie kończy się definicja typu, to po co ten obowiązkowy średnik? Otóż zaraz po zdefiniowaniu struktury można zacząć tworzyć zmienne o takim typie.
struct Test
{
int a;
} zmienna, zmienna2, * wskaznik, tablica[ 10 ];
Test zmienna, zmienna2, * wskaznik, tablica[ 10 ];
struct Test zmienna, zmienna2, * wskaznik, tablica[ 10 ];
Wiedząc to, może będziesz w stanie lepiej zrozumieć treść błędu, jaki wyrzuci Ci kompilator, gdy kiedyś niechybnie zapomnisz napisać ten średnik ;) |
Struktury danych
Struktura służy do przechowywania danych, więc "struktura danych", bo przecież nie kartofli. Jest tu lekko niefortunna zbieżność nazw. Struktura w C i C++ to konstrukcja językowa, realizowana przez słowo kluczowe
struct. Struktura danych to termin w informatyce, niezależny od konkretnego języka programowania. Jest to
pewien sposób organizowania danych, by móc na nich szybciej wykonywać
pewne operacje. To, czym jest struktura w C++, w informatycznej teorii nazywa się
rekordem, o czym można myśleć jak o tabeli. Nasza tablica osób z początku lekcji to są wiersze w tabeli, a kolumny są zatytułowane "imię", "nazwisko" itd. Bardziej ciekawe jest to, co można uzyskać z pomocą dynamicznej alokacji oraz wskaźników w tych rekordach.
Pomyśl tylko, co było najbardziej złożoną, cóż, strukturą danych, jaką można było osiągnąć samą dynamiczną alokacją? Była to zwykła w świecie N-wymiarowa tablica. No może nie taka zwykła - wskaźnik może być pusty, więc nie wszystkie kombinacje indeksów musiały prowadzić do istniejących elementów. Poza tym, nic szczególnego. Ilość wymiarów N była stała, wynikała z ilości gwiazdek przy wskaźniku na cały ten twór. Mam nadzieję, że wyobrażenie sobie tego nie sprawia problemów, bo to praktycznie najprostsza struktura danych. Złożone rekordy zmieniają
wszystko. Dla zilustrowania, przechowajmy zbiór liczb bez użycia ani jednej tablicy. Demonstrowana struktura danych nazywa się
listą jednokierunkową i jest jedną z najprostszych:
#include <iostream>
struct Lista
{
Lista * ogon;
int liczba;
};
void wypisz( Lista * lista )
{
if( lista )
{
std::cout << lista->liczba << ", ";
wypisz( lista->ogon );
}
}
Lista * ostatni( Lista * lista )
{
if( lista )
while( lista->ogon )
lista = lista->ogon;
return lista;
}
void dodajKoniec( Lista *& lista, int liczba )
{
Lista * nowy = new Lista;
nowy->liczba = liczba;
nowy->ogon = nullptr;
if( lista )
ostatni( lista )->ogon = nowy;
else
lista = nowy;
}
void zniszcz( Lista *& lista )
{
while( lista )
{
Lista * tmp = lista;
lista = lista->ogon;
delete tmp;
}
lista = nullptr;
}
int main()
{
int liczba;
Lista * lista = nullptr;
std::cout << "Podaj liczby, 0 lub blad konczy:\n";
while( std::cin >> liczba && liczba )
dodajKoniec( lista, liczba );
std::cout << "Koniec, oto liczby:\n";
wypisz( lista );
zniszcz( lista );
}
Lista w skrócie to
liczba i reszta listy i takie pola ma struktura
Lista. Zwróć szczególną uwagę na to, że nasz egzemplarz listy zaczyna swoje życie jako pusty wskaźnik i to jest poprawny przypadek dla wszystkich tych funkcji. Każdy węzeł listy zawiera tu liczbę, więc pusta lista - brak liczb, to również brak węzłów. Przypisanie pustego wskaźnika to może nie być wiele, ale musisz
zawsze pamiętać przy implementacji własnych struktur danych, żeby struktura miała swój początek (inicjalizację) i koniec (zniszczenie i zwolnienie pamięci). Początek jest szczególnie ważny. Operacje na strukturze danych realizują, w gruncie rzeczy, przejście z jednego poprawnego stanu na drugi i pisze się je, umyślnie lub nie, w założeniu że na wejściu struktura jest właśnie w poprawnym stanie. Zapomnienie o inicjalizacji łamie takie założenie.
To co w sumie osiągnęliśmy całym tym zachodem, czego nie można było rozwiązać prostą tablicą? Jak wspomniałem wcześniej, różne struktury danych są po to, by różne operacje były szybsze. Dodając nowe elementy do tablicy, w pewnym momencie całość będziesz musiał przenieść w nowe miejsce. W przypadku listy, nigdy nie będziesz musiał tego zrobić. Są też i inne zalety i wady względem tablic. Element można wstawić w dowolne miejsce i nigdy niczego nie przesuwać, czego nie można zrobić w tablicy. W tablicy dostęp do elementów jest swobodny, po indeksie, a w liście dostęp jest sekwencyjny - trzeba przejść przez N elementów, by znaleźć N-ty element.
Zadania domowe