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:
•	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

struct node {int info;
             struct node *nast;};             
struct node *lista, *q;
int k;
………..
  lista=NULL;
  cin>>k;
  while (k!=0)
  { q=new node();
    q->info=k;
    q->nast=lista;
    lista=q;
    cin>>k;
  }       

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:

4

3

1

9

lista

Ć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ą:

q=lista;
 while (q!=NULL)
 { cout<<q->info<<" ";
   q=q->nast;
 }

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.