Algorytmy i złożoność cz III

[ Pobierz całość w formacie PDF ]
38
z
p
stos sterta
dla zmiennych (zmienne dynamiczne)
Rys. 24. Zmienna wskaÅ…nikowa , zmienna
wskazywana i wskazanie puste
zz:
• 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)
( inaczej z) jest typem danych,
przechowujĢcych wskazania (adresy) innych danych.
DeklarujĢc z , np.
okreĻlamy jednoczeĻnie na jakiego typu dane moŇe
wskazywaÄ™ ta zmienna. Tutaj zmienna wskaÅ…nikowa jest
* p *p
q
39
typu , czyli mwiĢc inaczej jest typu wskazanie danej
typu znakowego.
W szczeglnym przypadku, deklarujĢc zmiennĢ wskaŅnikowĢ,
moŇemy nie okreĻlaę typu zmiennej wskazywanej, piszĢc np.
Tutaj zmienna wskaÅ…nikowa jest typu z
i moŇe wskazywaę na danĢ dowolnego typu.
Operator jest w wyraŇeniach . JeĻli
przypisano wskazanie danej, to identyfikuje obszar
pamiħci, wskazywany w danej chwili przez .
z uzyskujemy przypisujĢc zmiennej
wskaŅnikowej wartoĻę (z). Wskazanie puste moŇna
przypisaę zmiennej wskazujĢcej dowolnego typu.
Zmiennych wskaŅnikowych uŇywamy zwykle do
wskazywania danych alokowanych w obszarze z
z (na ). Zmienne te, w
odrŇnieniu od alokowanych na stosie z
z, nie sĢ identyfikowane przez nazwħ.
z z z 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 ktrym zostaþy
zadeklarowane. Taki rodzaj alokacji zmiennych nazywamy
z.
z 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
z z z 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 dla
zmiennej wskazywanej przez , 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:
Komentarz:
Zadaniem funkcji jest wypisanie w odwrotnej kolejnoĻci
znakw ciĢgu znakowego, zakoıczonego znakiem o kodzie .
Funkcja otrzymuje poprzez parametr wskazanie pierwszego
bajtu ciĢgu znakowego. Zostaþa tu wykorzystana rekurencja
nie ogonowa.
z
Typowe z 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Ģ .
o
Elementy struktur dynamicznych sĢ definiowane w
sposb rekurencyjny
Rekurencyjna definicja elementu listy liniowej
jednokierunkowej:
zklucz
next
Rys. 26. Element listy liniowej jednokierunkowej
Podziaþ list ze wzglħdu na rodzaj elementw:
• 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 ,
- usuwanie elementu.
head
p
7
2
4
head
a)
b)
Rys. 27. Lista liniowa jednokierunkowa:
a) lista zawierajĢca trzy elementy,
b) lista pusta
[ Pobierz całość w formacie PDF ]