Listy

Celem tej notatki jest wprowadzenie Was w tematykę struktur dynamicznych.

Rozważmy następujące zadanie:

Zadanie

Dane: a₁,…,a_n,0, gdzie a_i są dodatnimi liczbami całkowitymi.

Wynik: a_n,…,a₁

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:

• Wartości przechowywane w strukturze mogą być różnych typów - w tablicy wszystkie elementy są jednakowego typu.
• Do elementów przechowywanych w strukturze odwołujemy się przy pomocy nazw – do elementów tablicy odwołujemy się poprzez indeksy.

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.

3. Deklaracje

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.

4. Stała adresowa

W C++ istnieje jedna stała adresowa, odpowiadająca adresowi pustemu, czyli takiemu, który nie wskazuje na żaden obiekt. Stałą tą jest NULL.

5. Najważniejsze operacje na adresach
• podstawienie, np. x=NULL; x=y (o ile y jest zmienną adresową tego samego co x typu), x=&z (o ile zmienna z jest typu int; operator & w wyniku daje adres zmiennej z)
• porównanie adresów, np. if (x==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.