Dynamiczne struktury danych 1

Dotychczas poznane struktury danych, takie jak 

tablice i rekordy są nazywane 

statycznymi 

strukturami danych

. Struktury takie mają 

stałe

 wymiary i strukturę przez cały czas 

swojego istnienia.

W wielu zastosowaniach dogodnie jest stosować 

struktury, które 

zmieniają skład, wymiary i 

strukturę podczas wykonywania programu

.

Typowymi przykładami są 

listy

 i 

drzewa

, które 

rosną i kurczą się 

dynamicznie

 tzn. podczas 

wykonywania programu.

 

 

Dynamiczne struktury danych 2

Definicja.

 Dynamiczna struktura danych jest 

zespołem elementów, najczęściej nazywanych 

węzłami

, które w ogólnym przypadku 

reprezentowane są przez rekordy.

Do konstrukcji dynamicznych struktur danych 

stosuje się 

wskaźniki

 (

pointers

).

Mówimy więc, że wskaźniki są 

typu 

wskaźnikowego

.

Typy wskaźnikowe 

nie są strukturalne

, a 

więc należą do typów skalarnych.

 

 

Dynamiczne struktury danych 3

W Adzie mamy dwa rodzaje typów wskaźnikowych:

•

typy wskaźnikowe ograniczone

•

typy wskaźnikowe ogólne

Typy wskaźnikowe są w Adzie nazywane po angielsku 

access types

, co oddaje istotę wskaźnika, czyli 

zmiennej dającej 

dostęp

 (

access

) do wskazywanych 

danych.

Zmienne typów wskaźnikowych ograniczonych mogą 

wskazywać 

tylko 

na obiekty utworzone dynamicznie.

Zmienne typów wskaźnikowych ogólnych 

wskazują na

 

zadeklarowane obiekty, podprogramy, albo do 
danych utworzonych przez alokatory.

 

 

Dynamiczne struktury danych 4

Typy wskaźnikowe ograniczone

Zmienne do których odwołujemy się przez wskaźniki 

są 

anonimowe

 i nazywane są 

zmiennymi dynamicznymi

.

Zmienna dynamiczna jest tworzona przez użycie alokatora 

przydzielającego pamięć dla tej zmiennej:

Zmienna_Wskaznikowa := new Typ_Wskazywany;
Wskaźniki ograniczone 

nie mogą wskazywać na 

dowolne zmienne

. Typ zmiennej wskazywanej musi być 

podany w deklaracji typu wskaźnikowego.

Typ wskaźnikowy ograniczony 

jest związany

 ze 

wskazywanym typem

, nazywanym czasami 

typem 

bazowym

. 

 

 

Dynamiczne struktury danych 5

type Wezel;
type Wskaznik is access Wezel;
type Wezel is 

record
Klucz : Typ_Klucz;
Nastepny : Wskaznik;
Dane : Informacje:
end record;

 

Wskaznik jest typem 

wskaźnikowym związanym z 

typem Wezel.

Każdy typ wskaźnikowy zawiera 

wartość null, która nic nie 

wskazuje.

Klucz

null

Dane

 

 

Dynamiczne struktury danych 6

Wsk_Listy : Wskaznik;

Jest to definicja zmiennej wskaźnikowej związanej 

z typem Wezel. Zmienna ta ma domyślną 
wartość null, co oznacza, że nie wskazuje na 
żaden obszar pamięci.

Dopiero wywołanie alokatora

 Wsk_Listy := new Wezel;

powoduje, że zmienna ta wskazuje na obszar 

pamięci odpowiadający danej typu Wezel.

Jeżeli chcemy nadać wartości przechowywane w 

tym obszarze, to możemy napisać instrukcje:
Wsk_Listy.Klucz := Wartosc_Klucz;
Wsk_Listy.Dane := Wartosc_Dane;

 

 

Dynamiczne struktury danych 7

Wartości można też nadać w instrukcji 

wywołującej 

alokator

.

Wsk_Listy := new Wezel'(Wartosc_Klucz, 

null, Wartosc_Dane);

Jest to agregat kwalifikowany i nadawane są 

wartości 

wszystkim

 składowym rekordu, 

nawet wtedy, gdy niektóre mają wartości 
domyślne.

Można również nadać wartość przy deklaracji 

zmiennej wskaźnikowej
Wsk_Listy : Wskaznik := new

 

Wezel' 

(Wartosc_Klucz, null, Wartosc_Dane);

 

 

Dynamiczne struktury danych 8

Wsk_Listy

Klucz

null

Dane

Q

W

E

R

Wsk_Listy

Y

null

Y

null

T

Lista 
liniowa

 

 

Dynamiczne struktury danych 9

Program.

 Lista_Liniowa

Wstawianie nowego węzła po wybranym 

węźle

 

 

Dynamiczne struktury danych 10

Aktualny = 

null

Poprzedni = 

null

Nowy = 

null

Sytuacja po wejściu do procedury

Q

W

E

R

Wsk

Y

null

Y

null

T

 

 

Dynamiczne struktury danych 11

Q

W

E

R

Wsk

Y

null

Y

null

T

O

Nowy

Poprzedni = 

null

Aktualny

Sytuacja po wykonaniu instrukcji

Nowy_Nastepny := Aktualny_Nastepny

 

 

Dynamiczne struktury danych 12

Q

W

E

R

Wsk

Y

null

Y

null

T

O

Nowy

Poprzedni = 

null

Aktualny

Sytuacja przed wyjściem z procedury

 

 

Dynamiczne struktury danych 13

A

C

B

A

C

B

Definicja.

 

Struktura drzewiasta

, albo 

drzewo

 o 

typie podstawowym T jest

1. Strukturą pustą, albo
2. Węzłem typu T ze skończoną ilością dowiązanych, 

rozłącznych struktur drzewiastych o tym samym 
typie podstawowym, które nazywamy 

poddrzewami

.

A jest 

przodkiem

 (bezpośrednim) B, natomiast B jest 

potomkiem

 (bezpośrednim) A.

Definicja.

 

Drzewem uporządkowanym

 jest drzewo, 

w którym gałęzie są uporządkowane.

 

 

Dynamiczne struktury danych 14

Definicja.

 

Korzeń

 jest węzłem, który nie ma 

przodków.

Definicja.

 

Liściem

 nazywamy węzeł, który nie ma 

potomków.

Definicja.

 

Węzły, które nie są korzeniami ani liśćmi 

nazywamy 

węzłami pośrednimi

.

Definicja.

 

Uporządkowanym drzewem binarnym

 

nazywamy drzewo uporządkowane składające się 

ze skończonej liczby węzłów, przy czym może być 

puste, albo posiada korzeń z dwoma rozłącznymi 

poddrzewami binarnymi, nazywanymi 

lewym

 i 

prawym

 poddrzewem.

Definicja.

 

Drzewem dokładnie wyważonym

 

nazywamy drzewo, w którym na każdym poziomie 

utworzono maksymalną możliwą liczbę węzłów.

 

 

Dynamiczne struktury danych 15

Klucz

Dane

L

P

Wsk_Drzewa

Klucz

Dane

L

P

Klucz

Dane

L

P

Klucz

Dane

null null

Klucz

Dane

null null

Klucz

Dane

null null

Klucz

Dane

null null

Klucz

Dane

P

null

Klucz

Dane

P

null

Poziom 1

Poziom 2

Poziom 3

Poziom 4

Korzeń

Węzeł wewnętrzny

Liść

 

 

Dynamiczne struktury danych 16

Program.

 Drzewo_Binarne

Program.

 Wskazniki_Integer

Program.

 

Wsk_Ograniczone