Algorytmy i struktury danych

Algorytmy i struktury danych, temat 2

Definicja struktury danych

Definicja 2.1:

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

S=(D, R,

gdzie:



– oznacza zbiór danych elementarnych

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

(i –

jest indeksem poszczególnych danych),



R={r

, 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,



– jest elementem wejściowym do struktury danych S

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









Algorytmy i struktury danych, temat 2

Zbiór danych elementarnych



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

. Zapis zbioru jej danych elementarnych może

wyglądać następująco:



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



|D|=5





D 

Algorytmy i struktury danych, temat 2

Dana elementarna, zmienna

programowa



Dana elementarna

jest pojęciem abstrakcyjnym, rozumianym jako

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

dwójka elementów:



, gdzie:



– nazwa danej,



– 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ą. Czyli np. Float jako typ wskazujący

dziedzinę wartości i przypisana mu dziedzina algorytmiczna.



Dziedzina wartości i dziedzina algorytmiczna to pojęcia podane na

1szym wykładzie



Algorytmy i struktury danych, temat 2

Relacja

– wskazanie korzenia

struktury S



Relacja

, jest opisywana poprzez jedno- lub wieloelementowy

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

, natomiast drugim elementem

jest jedna z danych elementarnych ze zbioru



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



„element

należy do dziedziny relacji

” -

Dz(r



„dana

należy do przeciwdziedziny

” –

PDz(r

)



Element (elementy) należące do

PDz(r

)

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:







Algorytmy i struktury danych, temat 2

Relacja

– 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:

UWAGA: Korzenie struktury S nie mogą być elementami należącymi do

PDz(N)





N 

poprzedn

następni

Algorytmy i struktury danych, temat 2

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:





D 











N 

liść

korzeń

Algorytmy i struktury danych, temat 2

Definicja liniowej struktury danych

Definicja 2.2:

Liniową strukturą danych nazywamy strukturę danych

S=(D, R,

, w której relacja porządkująca

opisuje powiązania pomiędzy

elementami odpowiednio dla poszczególnych rodzajów list.

Wyróżniamy cztery rodzaje list (jednopoziomowych):

• jednokierunkowe listy niecykliczne

• dwukierunkowe listy niecykliczne

• jednokierunkowe listy cykliczne (pierścienie
jednokierunkowe)

• dwukierunkowe listy cykliczne (pierścienie
dwukierunkowe)

Algorytmy i struktury danych, temat 2

Jednokierunkowe listy niecykliczne



Model grafowy listy jednokierunkowej:



Relacja następstwa dla listy jednokierunkowej L:





...











Algorytmy i struktury danych, temat 2

Dwukierunkowe listy niecykliczne



Model grafowy listy dwukierunkowej:



Relacja następstwa dla listy dwukierunkowej Ld:





...

















Algorytmy i struktury danych, temat 2

Pierścień jednokierunkowy



Model grafowy pierścienia jednokierunkowego:



Relacja następstwa dla pierścienia jednokierunkowego P:













Algorytmy i struktury danych, temat 2

Złożoność obliczeniowa algorytmów

sortowania, cd.



Sortowanie przez zamianę (bąbelkowe)



n - ilość elementów w tablicy,



- liczba porównań klucza,



- liczba przesunięć elementów w tablicy

= 0.5 (n

- n)

Rmin

= 0

Rśr

= 0.75 (n

- n)

Rmax

= 1.5 (n

- n)

Algorytmy i struktury danych, temat 2

Pierścienie dwukierunkowe



Model grafowy pierścienia dwukierunkowego:



Relacja następstwa dla pierścienia dwukierunkowego Pd:









Algorytmy i struktury danych, temat 2

Przykłady liniowych struktur danych



Definicja listy stanowi podstawę dla zdefiniowania
struktury liniowej. Wszystkie przypadki struktur
liniowych można zdefiniować bazując na ich
odpowiednich reprezentacjach listowych



Bazując na pojęciu listy powiemy sobie o innych
liniowych strukturach danych, będą to:



kolejki,



stosy,



napisy,



tablice sekwencyjne



tablice rzadkie



tablice rozproszone (z haszowaniem).

Algorytmy i struktury danych, temat 2

Kolejki



Kolejka (queue) jest strukturą danych wykorzystywaną
najczęściej jako bufor przechowujący dane określonych
typów.



Dyscypliny kolejek:



FIFO (First In First Out) - pierwszy element
wchodzący staje się pierwszym wychodzącym



Round-Robin - cykliczna kolejka z dyscypliną czasu
obsługi komunikatu przechowywanego w kolejce (w
systemach operacyjnych, sieciach komputerowych)



LIFO (Last In First Out) - ostatni wchodzący staje się
pierwszym wychodzącym (tak działa stos)



kolejki priorytetowe - dodatkowo w
standardowym mechanizmie kolejki uwzględnia się
wartości priorytetów przechowywanych danych

Algorytmy i struktury danych, temat 2

Kolejki FIFO



Dyscyplina First In First Out:

Algorytmy i struktury danych, temat 2

Kolejki FIFO



template <class TypPodst> class FIFO



{



TypPodst *t;



int glowa,ogon,MaxElt;



public:



FIFO(int n)



{



MaxElt=n;



glowa=ogon=0;



t=new TypPodst[MaxElt+1];



}



void wstaw(TypPodst x)



{



t[ogon++]=x;



if(ogon>MaxElt) ogon=0;



}



Algorytmy i struktury danych, temat 2

Kolejki FIFO



int obsluz(TypPodst &w)



{



if (glowa==ogon) return -1; // informacja o błędzie

operacji



w=t[glowa++];



if(glowa>MaxElt) glowa=0;



return 1;



}



int pusta() // czy kolejka jest pusta?



{



if (glowa==ogon)



return 1; // kolejka pusta



else



return 0;

}



};

Algorytmy i struktury danych, temat 2

Kolejki FIFO



#include <iostream.h>



#include "kolejka.h"

static char *tab[]={"Kowalska","Fronczak","Becki","Pigwa"};
void main() {



FIFO<char*> kolejka(5); // kolejka 5-osobowa

for(int i=0; i<4;i++)



kolejka.wstaw(tab[i]);

char *s;
for(i=0; i<5;i++) {



int res=kolejka.obsluz(s);



if (res==1)



cout << "Obsluzony zostal klient: "<<s<<endl;



else



cout << "Kolejka pusta!\n"; }

Algorytmy i struktury danych, temat 2

Stos (kolejka LIFO)



Dyscyplina Last In First Out:

Algorytmy i struktury danych, temat 2

Stos (kolejka LIFO)



Do odkładania danych na wierzchołek stosu służy
zwyczajowo funkcja push(x) lokująca element x na
wierzchołku stosu.Zmienna x może być przy tym
dowolnego typu wbudowanego lub może być obiektem



Pobieranie elementu ze stosu realizuje także
zwyczajowo funkcja pop(x). Pobiera ona element z
wierzchołka stosu.



Każda z tych funkcja zawiera także obsługę błędu
sygnalizującego stos pusty lub brak miejsca na stosie.



W języku C++ ułatwieniem jest stosowanie tych funkcji
w bibliotece szablonów STL. Zaprezentowany zostanie
kod korzystający z tej biblioteki.



Stos realizuje się zwykle w formie tablicy z jednym
miejscem zarezerwowanym na pole wskazujące liczbę
elementów tablicy.

Algorytmy i struktury danych, temat 2

Stos (kolejka LIFO) – definicja klasy

stos w C++



const int DLUGOSC_MAX=300;



const int STOS_PELNY=3;



const int STOS_PUSTY=2;



const int OK=1;



template <class TypPodst> class STOS {



TypPodst t[DLUGOSC_MAX+1];

stos=t[0]...t[DLUGOSC_MAX]



int szczyt;



public:

// szczyt = pierwsza WOLNA komórka



STOS() { szczyt=0;} // konstruktor



void clear() { szczyt=0;} // zerowanie stosu



int push(TypPodst x);



int pop (TypPodst &w);



int StanStosu();



}; // koniec definicji klasy STOS

Algorytmy i struktury danych, temat 2

Stos (kolejka LIFO) – definicja klasy

stos w C++



template <class TypPodst> int
STOS<TypPodst>::push(TypPodst x)



{



if ( szczyt<=DLUGOSC_MAX)



{



t[szczyt++]=x;



return (OK);



}else



return (STOS_PELNY);



}

Algorytmy i struktury danych, temat 2

Stos (kolejka LIFO) – definicja klasy

stos w C++



template <class TypPodst> int STOS<TypPodst>::pop(TypPodst

&w)



// "w" zostanie "załadowane wartościa zdjętą ze stosu



{

if (szczyt>0)

{



w=t[--szczyt];



return (OK);



}else



return (STOS_PUSTY); }



template <class TypPodst> int STOS<TypPodst>::StanStosu()



{

// zwraca informacje o stanie stosu



switch(szczyt) {



case 0 :return (STOS_PUSTY);



case DLUGOSC_MAX+1

:return (STOS_PELNY);



default :return (OK);



}



}

Algorytmy i struktury danych, temat 2

Drzewiaste struktury danych

Definicja 2.4:

Drzewiastą strukturą danych nazywamy strukturę danych

S=(D, R, e)

, w której relacja porządkująca

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

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

Algorytmy i struktury danych, temat 2

Drzewiaste struktury danych – kilka

pojęć podstawowych



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

to dana wskazywana przez element wejściowy



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

swojego

następnika w w sensie relacji



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ść

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

Algorytmy i struktury danych, temat 2

Przykład modelu grafowego drzewa

dwójkowego

(binarnego)

poziom 1

poziom 2

poziom 3

poziom 4

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

i N

Algorytmy i struktury danych, temat 2

Rekurencja w drzewie

prawe

podrzewo

prawe

podrzewo

prawego

podrzewa

prawe

podrzewo

prawego

podrzewa

prawego

podrzewa

lewe

podrzewo

lewe

podrzewo

prawego

podrzewa

Algorytmy i struktury danych, temat 2

Drzewiaste struktury danych



danym wierzchołkiem, a leżące na następnym poziomie są
nazywane dziećmi tego węzła (np. dziećmi wierzchołka D są
G i H, wierzchołka H: J, K oraz L). Wierzchołek może mieć
dowolną liczbę dzieci, jeśli nie ma ich wcale nazywany jest
liściem; na rysunku liście zaznaczone są kolorem niebieskim.



Wierzchołek jest rodzicem dla każdego swojego dziecka;
każdy węzeł ma dokładnie jednego rodzica. Wyjątkiem jest
korzeń drzewa, który nie ma rodzica.



W drzewie istnieje dokładnie jedna ścieżka pomiędzy węzłem
a korzeniem; przez ścieżkę rozumie się ciąg krawędzi, na
rys. przykładowa ścieżka do węzła J jest zaznaczona na
czerwono. Liczba krawędzi w ścieżce jest nazywana
długością (lub głębokością) – liczba o jeden większa określa
poziom węzła. Z kolei wysokość drzewa to największy
poziom istniejący w drzewie (przykładowe drzewo ma
wysokość 4).

Algorytmy i struktury danych, temat 2

Drzewiaste struktury danych



Podstawowe operacje na
drzewach to:



* wyliczenie wszystkich
elementów drzewa,



* wyszukanie
konkretnego elementu,



* dodanie nowego
elementu w określonym
miejscu drzewa,



* usunięcie elementu.

Algorytmy i struktury danych, temat 2

Drzewiaste struktury danych



Pod pojęciem przechodzenia
drzewa rozumie się
odwiedzanie kolejnych
wierzchołków, zgodnie z
zależnościami rodzic-dziecko.
Jeśli przy przechodzeniu drzewa
na wierzchołkach są
wykonywane pewne działania,
to mówi się wówczas o
przechodzeniu:



* preorder - gdy działanie jest
wykonywane najpierw na
rodzicu, następnie na dzieciach;



* postorder - gdy działanie
jest wykonywane najpierw na
wszystkich dzieciach, na końcu
na rodzicu.



Algorytmy i struktury danych, temat 2

Drzewiaste struktury danych



W przypadku drzew

binarnych istnieje jeszcze

metoda inorder, gdzie

najpierw wykonywane jest

działanie na jednym z dzieci,

następnie na rodzicu i na

końcu na drugim dziecku.



Jeśli działaniem byłoby

wypisanie liter

przechowywanych w węzłach

przykładowego drzewa, to

przy przechodzeniu drzewa

metodą preorder otrzymamy

ABEFCDGIHJKL, natomiast

przy przechodzeniu drzewa

metodą postorder:

EFBCIGJKLHDA.

Algorytmy i struktury danych, temat 2

Drzewo binarne



w teorii grafów to drzewo, w którym stopień każdego
wierzchołka jest nie większy od 3.



Ukorzenione drzewo binarne to drzewo binarne o
stopniu nie większym niż 2, w którym wyróżniono jeden
z wierzchołków (zwany korzeniem).



W informatyce drzewo binarne to jeden z rodzajów
drzewa (struktury danych), w którym liczba synów
każdego wierzchołka wynosi nie więcej niż dwa.
Wyróżnia się wtedy lewego syna i prawego syna danego
wierzchołka.



Drzewo binarne, w którym liczba synów każdego
wierzchołka wynosi albo zero albo dwa, nazywane jest
drzewem regularnym.



Szczególnymi odmianami drzew binarnych są drzewa
BST oraz kopce.

Algorytmy i struktury danych, temat 2

Drzewo AVL



to zrównoważone binarne drzewo poszukiwań (BST), czyli

takie w którym wysokość lewego i prawego poddrzewa

każdego węzła różni się co najwyżej o jeden. Nazwa AVL

pochodzi od nazwisk rosyjskich matematyków: Adelsona-

Velskii oraz Landisa (właściwie: Grigorij Adelson-Wielskij i

Jewgienij Ładnis), którzy zaproponowali rozwiązanie problemu

utrzymania dobrego drzewa wyszukiwań w roku 1962 [1].



Drzewo AVL pozostaje drzewem BST, co oznacza, że

wierzchołki są uporządkowane w określony sposób. Zazwyczaj

przyjmuje się, iż elementy w lewym poddrzewie są mniejsze

od wierzchołka, zaś w prawym - większe. Zrównoważenie

drzewa osiąga się przypisując każdemu węzłowi współczynnik

wyważenia, który jest równy różnicy wysokości lewego i

prawego poddrzewa. Może wynosić 0, +1 lub -1. Wstawiając

lub usuwając elementy drzewa (tak aby zachować własności

drzewa BST) modyfikuje się też współczynnik wyważenia, a

gdy przyjmie on niedozwoloną wartość wykonuje specjalną

operację rotacji węzłów, która przywraca zrównoważenie.

Algorytmy i struktury danych, temat 2

Drzewo AVL



Koszt modyfikacji drzewa jest nieco większy niż dla
zwykłego drzewa BST, ale za to własności drzewa AVL
gwarantują, że pesymistyczny czas wyszukiwania
elementu w drzewie o n węzłach wynosi (log

n)/2,

podczas gdy dla niezrównoważonego BST (w postaci
listy) czas ten wynosi n.



Drzewa AVL są często porównywane z czerwono-
czarnymi drzewami, ponieważ pozwalają na wykonanie
tych samych operacji (dodawanie, usuwanie oraz
wyszukiwanie elementów) o równej co do rzędu
pesymistycznej złożoności czasowej O(log n). Przy
powtarzających się wyszukiwaniach drzewa AVL są
jednak wydajniejsze. [2]

Algorytmy i struktury danych, temat 2

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

O statycznych (sekwencyjnych) realizacjach struktur danych mówiliśmy już na

wykładzie wprowadzającym z WdP. Więcej realizacjach dynamicznych (łacznikowych)

będziemy mówić na obecnym wykładzie podczas omawiamia tematu nr 3.

Algorytmy i struktury danych, temat 2

Definicja tablicy rozproszonej (z

haszowaniem)

Definicja 2.3:



Tablicą rozproszoną nazywamy trójkę uporządkowaną







, gdzie

K = {k

, k

,..., k

} - zbiór kluczy,

D = {d

, d

,..., d

} - zbiór adresów,

h - funkcja mieszająca (haszująca)

zdefiniowana następująco:



Tradycyjnym obszarem zastosowań tablic
rozproszonych są zagadnienia związane z
przetwarzaniem danych.

Algorytmy i struktury danych, temat 2

Tablice rozproszone, funkcja

haszująca



Zadaniem funkcji haszującej h jest w miarę
równomierne obciążanie tablicy rozproszonej (jej
komórek). Zagadnienie definiowania funkcji
mieszającej jest istotne dla efektywności obliczeń
realizowanych na bazie tablic rozproszonych.



Ma to szczególnie duże znaczenie dla tablic
rozproszonych przetwarzanych bezpośrednio w
nośnikach zewnętrznych (taśmach, dyskach)



Nie można jednak wykluczyć powstawania tzw.
konfliktów w tablicach rozproszonych.

Algorytmy i struktury danych, temat 2

Konflikty w tablicach rozproszonych



Kolizją (konfliktem) w tablicy rozproszonej nazywamy
sytuację powstałą wtedy, gdy:

 

















Elementy k

, k

biorące udział w kolizji nazywamy synonimami.

Dużo więcej o listach i tablicach rozproszonych będziemy mówić na wykładzie 3 i 4

Algorytmy i struktury danych, temat 2

Podsumowanie:



poznaliśmy już przykłady struktur danych



wiemy w jaki sposób można realizować struktury danych



dalsze szczegóły poznamy na kolejnych wykładach



Następny wykład:



zajmiemy się implementacjami dynamicznych struktur danych

dziękuję za uwagę

Document Outline