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