Standardowa biblioteka szablonów –

podstawowe cechy i elementy

WYKŁAD 2

WAT 2006

Andrzej Walczak

PRZYKŁADY ZBIORÓW I

WIELOZBIORÓW

• #include <iostrem>
• #include <set>
•  
• int main()
• {
• typedef std::set<int> IntSet; //definicja typu

IntSet

• IntSet coll; //kontener na wartosci integer
• //*wstawi elementy od 1 do 6 w tym 1

dwukrotnie

PRZYKŁADY ZBIORÓW I

WIELOZBIORÓW

• coll.insert(3); //funkcja skladowa kontenerów

asocjacyjnych.Nowy element otrzymuje pozycje zgodnie
z wbudowanym kryterium sortowania.

Typ IntSet ma

kryterinm sortowania operatorem <.

Nie musimy

stosować funkcji push_back lub push_front.

• coll.insert(1);
• coll.insert(5);
• coll.insert(4);
• coll.insert(2);
• coll.insert(1);
• coll.insert(6);

PRZYKŁADY ZBIORÓW I

WIELOZBIORÓW

• //wypisz elementy
•  
• IntSet::const_iterator pos;
• for(pos=coll.begin();pos!=coll.end();++pos)

{std::cout<<*pos<<’’;}

• std::cout<<std::endl;
•  
• }
•  
• Elementy będą posortowane tak, że utworzą strukturę

drzewa. Zastosowany iterator pos automatycznie posortuje

drzewo. Ponieważ zastosowaliśmy zbiór (set) to

powtarzającego się elementu po posortowaniu nie będzie.

Jeśli zastosujemy multiset to będzie.

PRZYKŁADY ZBIORÓW I

WIELOZBIORÓW – tablica

asocjacyjna

• #include <iostream>
• #include <string>
• #include <

map

>

• using namespace std;

• int main()
• {
• typedef map<string, float> StringFloatMap; //definicja typu

IntStringMMap

• StringFloatMap coll; //kontener na wartosci integer-string

• coll["VAT"]=0.22;
• coll["PI"]=3.1415;
• coll["liczba"]=0.224466;
• coll["zero"]=0.0;

PRZYKŁADY ZBIORÓW I

WIELOZBIORÓW

• //wypisz elementy

• StringFloatMap::iterator pos;

• for(pos=coll.begin();pos!=coll.end();++pos) {
•

cout<<"klucz:\" "<<pos->first<<"\" "

• <<"wartosc:"<<pos->second<<endl;}

• return 0;
• }
• Deklaracja typu kontenerowego zawiera klucz i jego

wartosc

• Taka tablica ma indeks dowolnego typu niekoniecznie

integer

Definicja struktury danych

Definicja 2.1:

Strukturą danych nazywamy trójkę uporządkowaną

S=(D, R, e)

,

gdzie:

 D

– oznacza zbiór danych elementarnych

d

i, i = 1,..,|D|

(i – jest

indeksem poszczególnych danych),

 R={r

we

, N}

– jest zbiorem dwóch relacji określonych na

strukturze danych:

 – relacja wejścia do struktury danych S,
 – relacja następstwa (porządkująca)

strukturę S,

 e

– jest elementem wejściowym do struktury danych S (nie jest

to dana wchodząca w skład struktury danych S).

D

e

r

we





D

D

N





Zbiór danych elementarnych D

• Jak widać z definicji struktury danych, zbiór danych

elementarnych jest skończony i dla wygody operowania

oznaczeniem jego elementów poszczególne dane są indeksowane

od wartości 1 w kierunku wartości większych.

• Weźmy zatem dla przykładu pięcioelementową strukturę danych

S

. Zapis zbioru jej danych elementarnych może wyglądać

następująco:

• Liczność zbioru danych elementarnych wynosi 5, co zapisujemy:

• |D|=5





5

4

3

2

1

,

,

,

,

d

d

d

d

d

D 

Dana elementarna, zmienna

programowa

• Dana elementarna

d

i

jest pojęciem abstrakcyjnym, rozumianym

jako tzw. „nazwana wartość”. Jest ona określana jako

uporządkowana dwójka elementów:

• , gdzie:

– n

i

– nazwa danej,

– w

i

– aktualna wartość danej z określonej dziedziny wartości.

• Zmienna programowa jest pojęciem związanym z realizacją danej

w konkretnym środowisku programistycznym. Posiada ona

zdefiniowaną etykietę (nazwę zmiennej), wraz z określeniem

dziedziny wartości, którą może przyjmować dana

reprezentowana przez zmienną, a także zdefiniowaną dla tej

dziedziny wartości dziedziną algorytmiczną.

i

i

i

w

n

d

,



Relacja r

we

– wskazanie korzenia

struktury S

• Relacja

r

we

, jest opisywana poprzez jedno- lub wieloelementowy

zbiór dwójek uporządkowanych elementów, z których pierwszym
jest zawsze element wejściowy

e

, natomiast drugim elementem

jest jedna z danych elementarnych ze zbioru

D

.

• W sytuacji opisanej powyżej mówimy, że

– „element

e

należy do dziedziny relacji

r

we

” -

Dz(r

we

),

– „dana

d

i

należy do przeciwdziedziny

r

we

” –

PDz(r

we

)

• Element (elementy) należące do

PDz(r

we

)

są nazywane

korzeniem (korzeniami) struktury danych S. Struktura musi mieć
zdefiniowany co najmniej jeden korzeń.

Przykład: Załóżmy, że struktura S posiada dwa korzenie, według

opisu:





5

2

,

,

,

d

e

d

e

r

we



Relacja

N

– ustalenie porządku

struktury S

• Relacja następstwa N opisuje wzajemne uporządkowanie

elementów w strukturze danych S. Porządek struktury
opisujemy w postaci zestawów dwójek uporządkowanych
elementów.

Przykład: Opiszmy porządek naszej pięcioelementowej struktury

danych S:





3

5

4

3

4

1

3

1

1

2

,

,

,

,

,

,

,

,

,

d

d

d

d

d

d

d

d

d

d

N 

poprzedn

ik

następni

k

Model grafowy struktury danych

• Aby łatwiej zobrazować strukturę danych i w ten sposób

lepiej ją zrozumieć, można zbudować dla niej model grafowy.
W modelu tym:

– węzły (kółka) oznaczają poszczególne dane elementarne,
– łuki (strzałki) służą do odwzorowania następstw

poszczególnych danych elementarnych w strukturze S.

Przykład: Model grafowy dla opisywanej do tej pory struktury S:





5

4

3

2

1

,

,

,

,

d

d

d

d

d

D 





5

2

,

,

,

d

e

d

e

r

we







3

5

4

3

4

1

3

1

1

2

,

,

,

,

,

,

,

,

,

d

d

d

d

d

d

d

d

d

d

N 

e

d

2

d

5

d

1

d

3

d

4

liść

korzeń

korzeń

Drzewiaste struktury danych

Definicja 2.4:

Drzewiastą strukturą danych nazywamy strukturę danych

S=(D, R,

e)

, w której relacja porządkująca

N

opisuje kolejne, rekurencyjne

powiązania pomiędzy danymi elementarnymi drzewa, tworzącymi
kolejne „poddrzewa”.

Wniosek: Drzewo ze swojej natury jest strukturą hierarchiczną
(rekurencyjną). Niezwykle istotne jest tutaj odpowiednie
przypisanie danych elementarnych ze zbioru

D

do

kolejnych
poziomów drzewa i opisanie porządku w relacji

N

.

Drzewiaste struktury danych – kilka

pojęć podstawowych

• Korzeń drzewa – jest tylko i wyłącznie jeden korzeń dla drzewa.

Jest to dana wskazywana przez element wejściowy

e

,

• Liść drzewa – jest to dana elementarna, która nie posiada swojego

następnika w w sensie relacji

N

,

• Stopień drzewa – maksymalna liczba możliwych następników dla

dowolnego elementu drzewa. Najczęściej przyjmuje się,

że stopień drzewa jest potęgą liczby 2 (drzewa dwójkowe,

czwórkowe, ósemkowe, szesnastkowe),

• Droga w drzewie – kolejne łuki pomiędzy wskazanymi dwoma

elementami drzewa, które trzeba pokonać, aby dojść od

jednego elementu drzewa do innego

• Poziom drzewa – elementy ułożone w tej samej odległości

(długości drogi) od korzenia drzewa,

• Drzewo zupełne – takie drzewo, którego wszystkie elementy

(oprócz liści) mają taką liczbę następników, ile wynosi stopień

drzewa

Przykład modelu grafowego drzewa

dwójkowego

(binarnego)

e

d1

d2

d3

d4

d5

d6

d7

d8

poziom 1

poziom 2

poziom 3

poziom 4

Dla powyższego drzewa: wskaż korzeń, liście, opisz zbiór D, relacje r

we

i N

Realizacje struktur danych

• Realizacje sekwencyjne (statyczne) - wtedy, gdy z góry

znamy maksymalny rozmiar przetwarzanej struktury liniowej i z

góry chcemy zarezerwować dla niej określony zasób (pamięć

operacyjne, pamięć zewnętrzna). W czasie wytwarzania

programów komputerowych bazujemy wtedy na zmiennych

statycznych,

• Realizacje łącznikowe (dynamiczne) - wtedy, gdy rozmiar

struktury nie jest z góry znany i w czasie jej przetwarzania

może istnieć konieczność dodawania do niej nowych elementów

lub ich usuwania. W czasie wytwarzania programów

komputerowych bazujemy wtedy na zmiennych dynamicznych

(wskaźnikowych),

• Realizacje łącznikowo-sekwencyjne (hybrydowe) -

połączenie obu powyższych metod - wtedy gdy konieczny jest

odpowiedni balans pomiędzy zmiennymi statycznymi i

dynamicznymi

Statyczna a dynamiczna struktura

danych

Statyczna struktura danych:

– Posiada z góry ustalony rozmiar (bez

możliwości jego zmiany);

– Jej deklaracja poprzedza uruchomienie

głównej procedury programu;

– Liczba zmiennych o typie statycznych musi

być z góry znana;

– Pamięć jest przydzielana na wstępie a

oddawana po zakończeniu programu;

Dynamiczne realizacje struktur

drzewiastych

• Zupełne drzewo binarne (dwójkowe):

– Każdy węzeł, z wyjątkiem liści, ma dokładnie dwóch potomków;

• Drzewo poszukiwań binarnych (BST):

– Dla każdego węzła (nie liścia) wszystkie wartości

przechowywane w lewym poddrzewie są mniejsze od jego

wartości oraz przeciwnie dla drzewa prawego;

• Drzewo AVL (1962 – Adelson-Velskii, Landis)

– Drzewo BST jest drzewem AVL wtedy, kiedy dla każdego

wierzchołka wysokości dwóch jego poddrzew różnią się o co

najwyżej 1 poziom;

• Kopiec

– Wartości przechowywane w potomkach każdego węzła są

mniejsze od wartości węźle;

– Drzewo jest szczelnie wypełniane od lewego poddrzewa;
– Liście leżą na co najwyżej dwóch sąsiednich poziomach;