« Struktury, lekcja »
Rozdział 45. Struktury danych i struktury danych. (lekcja)
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!
Autor: pekfos
Kurs C++

Struktury

[lekcja] Rozdział 45. Struktury danych i struktury danych.

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.
C/C++
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:
C/C++
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
C/C++
Osoba osoby[ N ], jan;
Mając już jakiś egzemplarz struktury, wypadałoby wiedzieć jak się dostać do jego składowych. Służy do tego operator kropki
C/C++
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:
C/C++
Osoba * wsk = & jan;
wsk.imie; // ŹLE: wsk nie jest typem złożonym (bo jest wskaźnikiem) i w szczególności nie ma składowej `imie`
* wsk.imie; // ŹLE: jak wyżej, bo kropka ma wyższy priorytet. Ten zapis próbuje dokonać dereferencji wskaźnika `wsk.imie`, nie `wsk`
( * wsk ).imie; // DOBRZE: dereferencja na wskaźniku, kropka na strukturze
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ę":
C/C++
wsk->imie; // Dobrze.
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:
C/C++
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ę:
C/C++
struct A;

struct B
{
    A * a; // A jest znane (niekompletne)
};

struct A
{
    B * b; // B jest znane (kompletne)
};
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.
C/C++
struct Test
{
    int a;
} zmienna, zmienna2, * wskaznik, tablica[ 10 ];
Test zmienna, zmienna2, * wskaznik, tablica[ 10 ]; // Równoważne
Jest to pewna zaszłość z języka C. W C struktury nie były do końca pełnoprawnymi typami, więc użycie nazwy struktury trzeba było poprzedzić słowem struct, a mając
C/C++
struct Test zmienna, zmienna2, * wskaznik, tablica[ 10 ];
czemu nie przeskoczyć w ogóle do definiowania struktury w miejscu użycia? I można je definiować w miejscu użycia - można utworzyć strukturę lokalnie w funkcji, a jak od razu tworzysz wszystkie potrzebne Ci zmienne, to nawet nazwę samej struktury można pominąć.
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:
C/C++
#include <iostream>


struct Lista
{
    Lista * ogon;
    int liczba;
};

// Wypisz wszystkie elementy listy
void wypisz( Lista * lista )
{
    // Przechodzenie po liście *rekurencyjnie*
    if( lista )
    {
        std::cout << lista->liczba << ", ";
        wypisz( lista->ogon );
    }
}


// Zwróć: wskaźnik na ostatni element listy
Lista * ostatni( Lista * lista )
{
    // Przechodzenie po liście *iteracyjnie*
    if( lista )
    while( lista->ogon )
         lista = lista->ogon;
   
    return lista;
}


// Dodaj element na koniec listy
void dodajKoniec( Lista *& lista, int liczba )
{
    // Tworzymy nowy element listy
    Lista * nowy = new Lista;
    nowy->liczba = liczba;
    nowy->ogon = nullptr;
   
    // Dopisujemy na koniec
    if( lista )
         ostatni( lista )->ogon = nowy;
    else
         lista = nowy;
   
}


// Usuwa listę
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

  • Napisz funkcję
    C/C++
    void dodajPoczatek( Lista *& lista, int liczba )
    która dodaje liczby na początek listy, zamiast na koniec i użyj jej w przykładzie zamiast dodajKoniec(). Lista powinna wtedy zawierać liczby w przeciwnej kolejności i tak też je wypisać.
  • Zwróć uwagę, że dodajKoniec() używa funkcji ostatni(), a więc dodanie 1001. liczby wymaga przejścia przez 1000 węzłów tylko po to, by znaleźć koniec listy. Znajdź sposób na to, by dodawanie elementów na oba końce listy nie wymagało odwiedzania wszystkich węzłów.
    Podpowiedź: Możesz potrzebować drugiego struct.