Listy

 

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

 

Rozważmy następujące zadanie:

 

 

Zadanie

Dane:               a1,…,a­n,0, gdzie ai   dodatnimi liczbami całkowitymi.

Wynik:             an,…,a­1

 

 

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.