38

6. Typ wskaźnikowy.
Programowanie struktur dynamicznych.

p

* p *p

q

stos sterta
dla zmiennych (zmienne dynamiczne)

Rys. 24. Zmienna wskaźnikowa p, zmienna
wskazywana *p i wskazanie puste q

Pojęcia, których znajomość jest niezbędna:

• typ wskaźnikowy (wskazujący),

• zmienna wskaź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 wskaźnikowy ( inaczej wskazujący) jest typem danych,
przechowujących

wskazania

(adresy)

innych

danych.

Deklarując zmienną typu wskaźnikowego, np. char *p;
określamy jednocześnie na jakiego typu dane może
wskazywać ta zmienna. Tutaj zmienna wskaźnikowa p jest

39

typu char *, czyli mówiąc inaczej jest typu wskazanie danej
typu znakowego.
W szczególnym przypadku, deklarując zmienną wskaźnikową,
możemy nie określać typu zmiennej wskazywanej, pisząc np.
void *q; Tutaj zmienna wskaź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

wskaźnikowej wartość NULL (zero). Wskazanie puste można
przypisać zmiennej wskazującej dowolnego typu.
Zmiennych

wskaź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 wyraź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 wskaź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 wskaź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 wskaźnik p,

- usuwanie elementu.

8. Lista liniowa jednokierunkowa







a)

b)

Rys. 27. Lista liniowa jednokierunkowa:
a) lista zawierająca trzy elementy,
b) lista pusta

4

2

7

head

p

head

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 →

→

→

→ next = h; // dołączenie nowego

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 = p →

→

→

→ next;

p →

→

→

→ next = q;

Algorytm wstawiania drogą zamiany nowego elementu przed
element wskazywany przez p:

ELEM * q = new ELEM;
* q = * p;
p →

→

→

→ klucz = x; p →

→

→

→ next = q;

p = q;

8.1.Lista liniowa jednokierunkowa z wartownikiem







a)

b)

Rys. 28. Lista liniowa jednokierunkowa z wartownikiem:
a) lista jednoelementowa,
b) lista zawierająca więcej elementów.

4

2

7

head

p

head

rear

7

rear

45

8.2. Lista liniowa z dwoma „polującymi” wskaźnikami








Rys. 29. Lista liniowa z dwoma „polującymi” wskaźnikami:

8.3. Dynamiczne LIFO-stosy i FIFO-kolejki

top

a) b)

Rys. 30. Dynamiczny LIFO-stos: a) model stosu,

b) implementacja stosu w postaci listy

liniowej jednokierunkowej

4

2

7

head

p1

p2

top

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
}








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

6

1

7

front

rear

48

8.5. Samoorganizujące się listy.
Metody MoveToFront (MF), FrequencyCounter(FC)
(

zostaną szczegółowo omówione na wykładzie

)

8.6. Listy cykliczne












Rys. 32. Lista cykliczna jednokierunkowa

Rys. 33. Dwie różne interpretacje listy cyklicznej

jednoelementowej

13

9

7

name

7

7

name

name

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ą
wskaźników na listę ocen studentów, ocenionych z każdego
przedmiotu. Natomiast druga zawiera wskaź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, wskaźnik do następnej oceny w liście
studentów ocenionych z danego przedmiotu, oraz wskaźnik do
następnej oceny w liście ocen danego studenta.

50

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 wskaźników użyć list wskaź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.

1

2

…

3

1

…

2 3

7

6

5

4

6

5

4

4

3

3

+

-5

5

3

5

8

3+

tabl. wsk. na przedmioty

tabl. wsk. na studentów