Algoritmi i strukture podataka
dr.sc. Edin Pjanić
Fakultet elektrotehnike Univerziteta u Tuzli
1/24
Pregled predavanja

Apstraktni tip podatka (ATP) niz

Apstraktni tip podatka (ATP) lista

Implementacija ATP liste pomoću niza sukcesiv-


nih memorijskih lokacija
Implementacija ATP liste pomoću povezanih
memorijskih lokacija (jednostruko povezanih)
Usporedba navedenih implementacija ATP liste
Fakultet elektrotehnike Univerziteta u Tuzli
2/24
Strukture podataka



Način organizacije podataka koji se obrađuju u
računarskim programima.
Apstraktni tip podatka (ATP), engl. Abstract Data
Type (ADT)
 apstraktni model podataka

dozvoljene operacije nad tim tipom

ne definiše konkretnu implementaciju
Primjeri ATP:

lista (list),

stog (stack),

red (queue),

stablo (tree) itd.
Fakultet elektrotehnike Univerziteta u Tuzli
3/24
Niz (ATP)

Standardni C++ niz (array):
 pristup elementima preko indeksa

za n elemenata, indeksi idu od 0 do n-1

nije moguće mijenjati veličinu niza


implementiran preko (niza) sukcesivnih
memorijskih lokacija istog tipa
Niz kao apstraktni tip podatka (ATP) – postavljamo
zahtjeve koji nam trebaju. Npr.:
 pristup elementima preko indeksa

indeksi elemenata u proizvoljnom opsegu

promjena veličine niza prema potrebi
Fakultet elektrotehnike Univerziteta u Tuzli
4/24
Niz (ATP)
ATP niz:
Elementi niza: < a1, a2, a3, a4, ..., an-1, an >

Indeksi:
d
d+1
d+2
g-1
g
gdje su:
d – donja granica indeksa (najmanji indeks)
g – gornja granica indeksa (najveći indeks)

Kako implementirati ovakav niz?

Možemo dinamički alocirati potrebnu količinu
memorije i tu memoriju posmatrati kao
standardni C++ niz.
Fakultet elektrotehnike Univerziteta u Tuzli
5/24
Niz (ATP)
ATP niz:
Elementi niza: < a1, a2, a3, a4, ..., an-1, an >

Indeksi:
d
d+1
d+2
g-1
g
...
Indeksi C++ niza:
0
1
2
3
Fakultet elektrotehnike Univerziteta u Tuzli
n-2
n-1
6/24
Niz (ATP) – primjer niza cijelih brojeva

ATP niz:
gornji indeks
donji indeks
Indeksi ATP niza:
10
11
12
21
22
Elementi niza: < 5, 8, -32, 0, ... , 53, 44 >
...
5
8
-32
0
Indeksi C++ niza:
0
1
2
3
niz elemenata
veličina niza = gornji indeks – donji indeks + 1
Fakultet elektrotehnike Univerziteta u Tuzli
53
44
11
12
7/24
Niz ATP - implementacija
template <typename Elem>
class Niz
{
public:
Niz(int d, int g);
~Niz();
Elem & operator[](int index);
void realociraj(int d, int g);
private:
int donja, gornja; // donja i gorna granica (indeksi)
Elem * elementi; // pokazivač na dinam. alocirani niz
...
};
Fakultet elektrotehnike Univerziteta u Tuzli
8/24
Niz ATP – implementacija nekih metoda
template <typename Elem>
Niz<Elem>::Niz(int d, int g)
{
if(g < d)
throw invalid_argument("Donja granica mora ne smije biti veca od "
"gornje.");
elementi = new Elem[g - d + 1];
donja = d;
gornja = g;
}
template <typename Elem>
Niz<Elem>::~Niz()
{
delete [] elementi;
}
template <typename Elem>
Elem & Niz<Elem>::operator[](int index)
{
return elementi[index - donja];
}
Fakultet elektrotehnike Univerziteta u Tuzli
9/24
Niz ATP – realociranje
template <typename Elem>
void realociraj(int d, int g)
{
if(g < d)
throw invalid_argument("Donja granica mora ne smije biti veca od gornje.");
Elem * novi_niz = new Elem[g - d + 1];
if(d <= gornja && g >= donja)
{
int d_prenos, g_prenos;
if(donja < d)
d_prenos = d;
else
d_prenos = donja;
if(gornja > g)
g_prenos = g;
else
g_prenos = gornja;
for(int i=d_prenos; i<=g_prenos; i++)
novi_niz[i-d] = elementi[i-donja];
}
delete[] elementi;
elementi = novi_niz;
donja = d;
gornja = g;
}
Fakultet elektrotehnike Univerziteta u Tuzli
10/24
Lista (ATP)


Kolekcija elemenata istog tipa sa definisanim
Bingo brojevi
poretkom.
Bolić
27 73
Misimović
64 82
Primjeri:
Lista za kupovinu
mlijeko
hljeb
jaja
voda
kafa
čokolada
neka igračkica
89
23
5
63
79
28
45
8
66
20
22
55
57
9
16
32
81
60
35
59
11
90
6
21
56
25
48
87
4
49
37
54
39
24
62
46
53
51
38
50
83
5
Fakultet elektrotehnike Univerziteta u Tuzli
Lista strijelaca
Barbarez reprezentacije BiH
Džeko
Baljić
Muslimović
Ibišević
Muharemović
Salihamidžić
Bešlija
Pjanić
Salihović
Ibričić
Medunjanin
Konjić
11/24
Lista (ATP)



Neke operacije koje se mogu definisati nad listom:
 kreiranje liste (prazne),

dodavanje elementa u listu,

uklanjanje elementa iz liste,

dobijanje vrijednosti elementa u listi,

dobijanje veličine liste itd.
Apstraktni prikaz liste:
< a1, a2, a3, a4, ..., an > ili ( a1, a2, a3, a4, ..., an )
Neki načini implementacije:
 povezane memorijske lokacije (linked memory)


niz (array)
Performanse zavise od načina implementacije
Fakultet elektrotehnike Univerziteta u Tuzli
12/24
Lista (ATP) – kretanje po listi
Elementi liste: < a1, a2, a3, a4, ..., an-1, an >
pokazivač aktuelnog elementa
Neke operacije sa aktuelnim (trenutnim) elementom:

čitanje/mijenjanje vrijednosti

brisanje elementa

dodavanje novog elementa na tu poziciju
Fakultet elektrotehnike Univerziteta u Tuzli
13/24
Lista (ATP) – dodavanje novog elementa
ax
Elementi liste: < a1, a2, a3, a4, ..., an-1, an >
pokazivač aktuelnog elementa
Dodavati možemo:

iza trenutnog elementa

ispred trenutnog elementa
Fakultet elektrotehnike Univerziteta u Tuzli
14/24
Lista (ATP) – uklanjanje elementa
Elementi liste: < 5, 8 -7, 22, 53, 19 >
pokazivač aktuelnog elementa
Nakon uklanjanja trenutnog elementa:
Elementi liste: < 5, 8 -7, 53, 19 >
pokazivač aktuelnog elementa
Fakultet elektrotehnike Univerziteta u Tuzli
15/24
Lista (ATP) – neki metodi

Na osnovu prethodnog razmatranja možemo navesti
neke metode koje će imati naša ATP Lista bez obzira
na implementaciju:
 dodaj(X) ili dodaj_ispred(X) ili dodaj_iza(X)
 ukloni()
 trenutni()
 naredni()
 prethodni()
 velicina()
 itd.
Fakultet elektrotehnike Univerziteta u Tuzli
16/24
Lista – implementacija pomoću niza

Elemente liste možemo smjestiti u niz, obično
dinamički alociran. Primjer:
trenutni: 3
velicina: 6
58
9
22
-6
10
12
0
1
2
3
4
5
(1
2
3
4
5
6)


Fakultet elektrotehnike Univerziteta u Tuzli
17/24
Lista – dodavanje elementa

Novi element u list možemo dodati ispred ili iza
trenutne pozicije. Primjer dodavanja ispred:
7
trenutni (indeks): 3
velicina: 6
trenutni (indeks): 3
velicina: 7
58
9
22
-6
10
12
0
1
2
3
4
5
58
9
22
0
1
2
3
-6
10
4
5
58
9
22
7
-6
10
0
1
2
3
4
5
Fakultet elektrotehnike Univerziteta u Tuzli
12
6
12
6
18/24
Lista – uklanjanje elementa
trenutni (indeks): 3
velicina: 7
trenutni (indeks): 3
velicina: 6
58
9
22
7
-6
10
0
1
2
3
4
5
-6
10
58
9
22
0
1
2
3
4
5
58
9
22
-6
10
12
0
1
2
3
4
5
Fakultet elektrotehnike Univerziteta u Tuzli
12
6
12
6
19/24
Lista – složenost nekih operacija




Pristup elementu: O(1)
Dodavanje novog elementa: O(n)
Uklanjanje elementa: O(n)
Traženje elementa: O(n)
Fakultet elektrotehnike Univerziteta u Tuzli
20/24
Download

Algoritmi i strukture podataka