38
6. Typ wskaz
nikowy.
Programowanie struktur dynamicznych.
p
* p *p
q
stos sterta
dla zmiennych (zmienne dynamiczne)
Rys. 24. Zmienna wskaz
nikowa p, zmienna
wskazywana *p i wskazanie puste q
Pojęcia, których znajomość jest niezbędna:
" typ wskaz
nikowy (wskazujący),
" zmienna wskaz
nikowa (wskazująca),
" wskazanie puste,
" zmienna wskazywana,
" alokacja niedynamiczna i dynamiczna zmiennych,
" czas życia zmiennych,
" gospodarka pamięcią na stosie i na stercie dla
zmiennych (rys. poniżej)
Typ wskaz
nikowy ( inaczej wskazujący) jest typem danych,
przechowujących wskazania (adresy) innych danych.
Deklarując zmienną typu wskaz
nikowego, np. char *p;
określamy jednocześnie na jakiego typu dane może
wskazywać ta zmienna. Tutaj zmienna wskaz
nikowa p jest
39
typu char *, czyli mówiąc inaczej jest typu wskazanie danej
typu znakowego.
W szczególnym przypadku, deklarując zmienną wskaz
nikową,
możemy nie określać typu zmiennej wskazywanej, pisząc np.
void *q; Tutaj zmienna wskaz
nikowa q jest typu wskazanie
adresowe i może wskazywać na daną dowolnego typu.
Operator * jest w wyrażeniach operatorem wyłuskania. Jeśli p
przypisano wskazanie danej, to *p identyfikuje obszar
pamięci, wskazywany w danej chwili przez p.
Wskazanie puste uzyskujemy przypisując zmiennej
wskaz
nikowej wartość NULL (zero). Wskazanie puste można
przypisać zmiennej wskazującej dowolnego typu.
Zmiennych wskaz
nikowych używamy zwykle do
wskazywania danych alokowanych w obszarze zmiennych
dynamicznych programu (na stercie). Zmienne te, w
odróżnieniu od alokowanych na stosie zmiennych
niedynamicznych, nie są identyfikowane przez nazwę.
Czas życia zmiennych niedynamicznych zależy od struktury
programu, a ich powołanie do życia może zależeć od tego, czy
w danej chwili wykonuje się blok programu, w którym zostały
zadeklarowane. Taki rodzaj alokacji zmiennych nazywamy
alokacją statyczną.
Alokacja dynamiczna odbywa się na stercie. Przydział
pamięci na alokowane tam zmienne dynamiczne odbywa się
na wyraz
ne życzenie z programu (zwykle za pomocą
operatora dynamicznego przydziału pamięci), na przykład
p=new char;
Czas życia zmiennych dynamicznych rozciąga się od
momentu ich dynamicznego powołania do życia za pomocą
operatora new do momentu zwolnienia zajmowanej przez nich
pamięci za pomocą operatora delete, na przykład delete p; dla
zmiennej wskazywanej przez p, i nie zależy od struktury
programu.
40
stos sterta
Rys. 25. Gospodarka pamięcią na stosie i na stercie
Poniżej przedstawiono definicję zapisanej w języku C/C++,
rekurencyjnej funkcji, wykorzystującej wskaz
niki:
void reverse(char *p)
{
if(*p!=0) reverse(p+1);
cout<<*p;
}
Komentarz:
Zadaniem funkcji jest wypisanie w odwrotnej kolejności
znaków ciągu znakowego, zakończonego znakiem o kodzie 0.
Funkcja otrzymuje poprzez parametr p wskazanie pierwszego
bajtu ciągu znakowego. Została tu wykorzystana rekurencja
nie ogonowa.
7. Rekurencyjne typy danych. Struktury dynamiczne.
Typowe struktury dynamiczne to:
" listy,
" drzewa i lasy,
" grafy.
41
Cechy struktur dynamicznych:
" są zwykle alokowane w obszarze zmiennych
dynamicznych pamięci operacyjnej (na stercie),
" zajmują dokładnie tyle pamięci, ile jest w danej
chwili niezbędne do ich przechowania (ich
rozmiary i postać ulegają zmianie w trakcie
przetwarzania),
" posiadają dostęp sekwencyjny.
o Elementy struktur dynamicznych są definiowane w
sposób rekurencyjny
Rekurencyjna definicja elementu listy liniowej
jednokierunkowej:
struct ELEM
{
int klucz; klucz
ELEM * next;
....................... next
};
Rys. 26. Element listy liniowej jednokierunkowej
Podział list ze względu na rodzaj elementów:
" jednokierunkowe,
" dwukierunkowe.
Podział list ze względu na ich organizację:
" listy liniowe jednokierunkowe,
" listy liniowe jednokierunkowe z wartownikiem,
" listy z dwoma polującymi wskaz
nikami,
42
" listy uporządkowane,
" listy z priorytetem (HPO-kolejki),
" samoorganizujące się listy (metody MF i FC),
" listy cykliczne.
Przykłady struktur dynamicznych, wykorzystujące listy:
" dynamiczne LIFO-stosy,
" dynamiczne FIFO-kolejki.
Podstawowe operacje na listach:
- inicjalizacja listy,
- wstawianie elementu na początek i na koniec listy,
- wyszukiwanie elementu,
- wstawianie za i przed element wskazywany przez
dowolny wskaz
nik p,
- usuwanie elementu.
8. Lista liniowa jednokierunkowa
head p
head
7 2 4
a) b)
Rys. 27. Lista liniowa jednokierunkowa:
a) lista zawierająca trzy elementy,
b) lista pusta
43
Algorytm wstawiania nowego elementu na początek listy
liniowej jednokierunkowej:
ELEM * h = NULL; // inicjalizacja listy
.......................
ELEM *p = new ELEM; // dynamiczne
przydzielenie pamięci
na nowy element
p // dołączenie nowego
next = h;


elementu do początku
listy
h = p; // przesunięcie głowy listy
do faktycznego początku
listy
Poniżej przykładowa funkcja, której zadaniem jest wyszukanie
w liście liniowej jednokierunkowej elementu o podanym
kluczu x, zapisana w języku C++. Zasadnicze elementy
algorytmu wytłuszczono.
ELEM * szukaj( int x )
// funkcja zwraca wskazanie wyszukanego elementu,
// lub wskazanie puste, gdy szukany element w liście
// nie występuje
{ int jest=0;
ELEM *p=h;
while( p && not jest )
if( p
klucz = x )jest=1;


else p= p
next;


if( jest ) return p; else return NULL; }
44
Poniżej algorytm wstawiania nowego elementu za dowolny
element wskazywany przez p:
ELEM * q = new ELEM;
q next;
next = p


p
next = q;


Algorytm wstawiania drogą zamiany nowego elementu przed
element wskazywany przez p:
ELEM * q = new ELEM;
* q = * p;
p next = q;
klucz = x; p


p = q;
8.1.Lista liniowa jednokierunkowa z wartownikiem
head rear head p rear
7 2 4
7
a) b)
Rys. 28. Lista liniowa jednokierunkowa z wartownikiem:
a) lista jednoelementowa,
b) lista zawierająca więcej elementów.
45
8.2. Lista liniowa z dwoma  polującymi wskaz
nikami
p2
head p1
7 2 4
Rys. 29. Lista liniowa z dwoma  polującymi wskaz
nikami:
8.3. Dynamiczne LIFO-stosy i FIFO-kolejki
top
top
a) b)
Rys. 30. Dynamiczny LIFO-stos: a) model stosu,
b) implementacja stosu w postaci listy
liniowej jednokierunkowej
46
Algorytmy obsługi LIFO-stosu:
struct LIFO {
char klucz;
LIFO * next;
}; // definicja elementu stosu
.............................................
// inicjalizacja stosu
LIFO * top = NULL;
.............................................
// położenie na stos
int push(char c)
{
LIFO *ptr = new LIFO;
if(ptr) {
ptr
klucz = c;


ptr
next= top;


top = ptr;
return sizeof(LIFO);
}else return 0; // nie można przydzielić pamięci
}
// zdjęcie ze stosu
char pop( void)
{
if(top) {
char c = top
klucz;


LIFO *p = top;
top = top
next;


47
delete p;
return c;
} else return 0; // stos jest pusty
}
front rear
7 1 6
Rys. 31. Implementacja FIFO  kolejki w postaci listy
liniowej z dwoma wartownikami:
8.4. Lista uporządkowana i kolejka z priorytetem
(HPO-kolejka)
struct HPO {
int prio;
char * process;
HPO *next; };
Przykładowe deklaracje funkcje obsługi HPO-kolejki:
int into( char *p, int prio);
// wstawia proces wskazywany przez p do kolejki
nadając mu prioritet prio
char * pop( void );
// odczytuje wskazanie procesu o najwyższy priorytecie
void delete( void );
// usuwa element o najwyższym priorytecie
void set( HPO *ref, int prio);
// zmienia priorytet procesu wskazywanego przez ref na prio
48
8.5. Samoorganizujące się listy.
Metody MoveToFront (MF), FrequencyCounter(FC)
(zostaną szczegółowo omówione na wykładzie)
8.6. Listy cykliczne
name
13
9
7
Rys. 32. Lista cykliczna jednokierunkowa
name name
7 7
Rys. 33. Dwie różne interpretacje listy cyklicznej
jednoelementowej
49
9. Tablice rzadkie
Są to tablice (zwykle wielowymiarowe o dużych rozmiarach),
których tylko niewielka część jest wykorzystywana z powodu
rzadkiego występowania wartości.
Jako przykład rozważmy tablicę przechowującą oceny
studentów w szkole wyższej, w której jest 8 000 studentów i
300 różnego rodzaju przedmiotów. Aby pomieścić w jednej
tablicy oceny wszystkich studentów ze wszystkich
przedmiotów, używając do zapisu oceny tylko 1 bajta,
potrzeba 2,4 Mb pamięci, przy czym tylko niewielki procent
elementów tablicy byłby wykorzystany (przedmioty
studentów różnych kierunków tylko w niewielkim stopniu
pokrywają się). Tego rodzaju tablice nazywamy tablicami
rzadkimi.
Przykład rozwiązania tego problemu z użyciem list
przedstawia rys. 34. Wykorzystuje się tu dwie
jednowymiarowe tablice, z których pierwsza jest tablicą
wskaz
ników na listę ocen studentów, ocenionych z każdego
przedmiotu. Natomiast druga zawiera wskaz
niki do listy ocen
każdego indywidualnego studenta. Wszystkie elementy,
reprezentujące oceny, wchodzą w skład obu rodzajów list i są
tego samego typu, zawierając pięć pól: nr studenta, nr
przedmiotu, ocena, wskaz
nik do następnej oceny w liście
studentów ocenionych z danego przedmiotu, oraz wskaz
nik do
następnej oceny w liście ocen danego studenta.
50
tabl. wsk. na przedmioty tabl. wsk. na studentów
1 2 3 4 5 6 7 &
1
2 4
5
3 3
3
4 3+
5
-5
5
8
6
3+
&
Rys. 34. Reprezentacja listowa tablicy rzadkiej
Zalety tej reprezentacji są niewątpliwe:
" struktura zajmuje dokładnie tyle pamięci, ile potrzeba,
aby w danym momencie zapamiętać wszystkie oceny,
" strukturę można łatwo modyfikować dodając nowe
oceny, usuwając inne, itd..,
" gdyby zamiast tablic wskaz
ników użyć list wskaz
ników,
nie byłoby żadnych ograniczeń ani na liczbę
przedmiotów, ani na liczbę studentów,
" można natychmiast pokazać listę ocen studentów z
danego przedmiotu, jak również listę ocen danego
studenta z różnych przedmiotów.