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