Listy
Celem tej notatki jest wprowadzenie Was w tematykę struktur dynamicznych.
Rozważmy następujące zadanie:
Zadanie
Dane: a1,…,an,0, gdzie ai są dodatnimi liczbami całkowitymi.
Wynik: an,…,a1
Rozwiązanie tego zadania przy pomocy znanych nam struktur danych (a znamy praktycznie tylko tablice) napotyka na zasadniczy problem: nie znamy długości ciągu (tj. wartości n). Zadeklarowanie w programie tablicy o maksymalnie dużym rozmiarze nie zawsze jest dobrym pomysłem.
Podamy rozwiązanie tego zadania, które korzysta z list. Niekoniecznie jest to najlepsze rozwiązanie - podajemy je jednak ze względów dydaktycznych.
Aby operować listami musimy poznać parę nowych pojęć. Przedstawimy je tylko w takim zakresie, jaki jest potrzebny dla naszych celów.
Struktury
Struktura jest złożonym typem. Podobnie jak tablica może przechowywać wiele wartości. Różni ją jednak od tablicy to, że:
1. Przykład: definicja struktury i deklaracja zmiennych strukturowych
struct node { string nazwisko;
int wzrost, waga;
bool zonaty;
}
Zdefiniowaliśmy strukturę o nazwie node. Ta definicja jest opisem typu, tak jak opisem typu jest słowo int.
Gdy chcemy mieć zmienne typu int musimy zadeklarować
je pisząc np. int x, y;. Podobnie chcąc mieć zmienne typu struct node, musimy w programie umieścić ich deklaracje, np.
struct node x,y;
2. Odwołania do elementów struktury
W powyższej strukturze mogą być przechowywane cztery
wartości (nazywamy je polami struktury): jedna wartość typu string (uczestnicy obozu już o tym typie słyszeli), dwie
wartości typu int oraz jedna
wartość typu bool. Do tych
wartości odwołujemy się poprzez nazwy pól. Przykładowo do pól zmiennej x
zadeklarowanej jako
struct node x;
odwołujemy się pisząc odpowiednio:
x.nazwisko, x.wzrost,
x.waga oraz x.zonaty.
Czyli piszemy nazwę zmiennej strukturowej,
potem kropkę i nazwę pola.
Ważne: elementy
struktury są traktowane jak
zmienne odpowiednich typów. W szczególności x.waga jest
zmienną typu int, a więc może w
programie występować dokładnie w takim samym kontekście jak dowolna zmienna
typu int. Poprawne są więc zapisy:
cin>>x.waga;
cout<<x.nazwisko;
x.waga=2*x.waga+k (o ile k jest typu int)
Adresy
W programach w C++ możemy posługiwać się adresami zmiennych.
Zmienną adresową deklarujemy pisząc gwiazdkę przed jej nazwą, np.
int *x;
oznacza deklarację zmiennej x, która jako swe wartości będzie mogła przybierać adresy zmiennych typu int.
W C++ istnieje jedna stała adresowa, odpowiadająca adresowi pustemu, czyli takiemu, który nie wskazuje na żaden obiekt. Stałą tą jest NULL.
Obiekty dynamiczne
Deklarując
struct node *q;
mamy zmienną adresową q, która będzie przechowywać adresy (inaczej będziemy mówić: „wskazywać” na struktury. Początkowo nie istnieje żadna struktura, na którą mogłaby wskazywać q. Nową strukturę możemy utworzyć stosując funkcję new:
q=new node();
Nowa struktura tworzona jest w obszarze pamięci przydzielonej programowi, który nazywa się stertą. Adres tej struktur zapamiętywany jest w zmiennej q.
Odwołania do pól
wskazywanej struktury.
Do pól struktury wskazywanej przez q odwołujemy się pisząc odpowiednio:
q->nazwisko,
q->wzrost,
q->waga
oraz q->zonaty
Czyli po nazwie zmiennej adresowej piszemy -> a następnie nazwę pola.
Listy
Jeśli wśród pól struktury umieścimy pola typu adresowego (wskazującego na inne egzemplarze tej struktury) będziemy mogli w trakcie działania programu tworzyć skomplikowane struktury danych wskazywane prze pojedyncze zmienne.
Przykład
Powyższy fragment czyta ciąg liczb (aż do wystąpienia zera) i każdą z tych liczb zapamiętuje w nowej strukturze. Każda struktura posiada pole adresowe nast., w którym zapamiętywany jest adres wcześniejszej struktury. Pierwszy element tak utworzonej listy wskazywany jest przez zmienną lista. Graficznie można przedstawić tę listę następująco:
Ćwiczenie. (wypisywanie elementów listy)
Oczywiście chodzi nam tu o wypisywanie liczb zapamiętanych w liście. Liczbę zapamiętaną w pierwszym elemencie listy możemy wypisać instrukcją cout<<lista->info; liczbę z drugiego elementu możemy wypisać instrukcją: cout<<lista->nast->info; itd… Oczywiście do wypisania wszystkich liczb zastosujemy pętlę, np. taką:
Usuwanie obiektów ze
sterty
Niepotrzebne obiekty można usuwać ze sterty funkcją free:
free(q);
instrukcja ta zwalnia pamięć zajmowaną przez obiekt (np. strukturę) wskazywaną przez zmienną q.
Uwaga: wykonanie tej instrukcji nie zmienia wartości zmiennej q. Jeśli w dalszym ciągu swego działania program przydzieli zwolnioną pamięć innemu obiektowi, niefrasobliwe użycie zmiennej q może prowadzić do przykrego błędu.