Download spa-skripta.pdf PDF

Titlespa-skripta.pdf
File Size509.6 KB
Total Pages68
Document Text Contents
Page 34

4.2. RJEČNIK 33

celltype *ac, *bc, *cc;
/* tekuće ćelije u listi za A i B, te zadnja ćelija u listi za C */
*chp = (celltype*)malloc(sizeof(celltype));
/* stvori header liste za C */
ac = ah->next;
bc = bh->next;
cc = *chp;
while ((ac!=NULL) && (bc!=NULL)) {
/* usporedi tekuće elemente liste A i B */
if ( (ac->element) == (bc->element) ) {
/* dodaj element u presjek C */
cc->next = (celltype*)malloc(sizeof(celltype));
cc = cc->next;
cc->element = ac->element;
ac = ac->next;
bc = bc->next;

}
else if ((ac->element)<(bc->element))
/* elementi su različiti, onaj iz A je manji */
ac = ac->next;

else
/* elementi su različiti, onaj iz B je manji */
bc = bc->next;

}
cc->next = NULL;

}

Funkcije UNION( ), DIFFERENCE( ) i SUBSET( ) su vrlo slične. Vrijeme izvršavanja je propor-
cionalno duljini jedne od listi.

4.2 Rječnik

Često nije potrebno obavljati složene operacije kao što su ∪,∩, \,⊆. Umjesto toga, pamti se jedan skup,
te se obavljaju povremena ubacivanja i izbacivanja elemenata. Takoder, povremeno treba ustanoviti
nalazi li se zadani element u skupu ili ne. Takav skup nazivamo rječnik (dictionary). Apstraktni
tip podataka DICTIONARY definiramo slično kao apstraktni tip podataka SET, s time da se popis
operacija reducira na MAKE NULL( ), INSERT( ), DELETE( ) i MEMBER( ). Slijede primjeri:

- Pravopis je popis ispravno napisanih riječi nekog jezika. Da bismo ustanovili da li je neka riječ
ispravno zapisana, gledamo postoji li ona u pravopisu. Povremeno u pravopis ubacujemo nove
izraze ili izbacujemo zastarjele.

- Neki tekst procesori imaju u sebi tzv. spelling checker, dakle popis ispravno napisanih engleskih
riječi i program koji usporeduje naš tekst s popisom.

- Vǐsekorisničko računalo prepoznaje korisnike na osnovu njihovih imena. Kod prijavljivanja, ko-
risnik upisuje ime, a stroj provjerava postoji li ime na popisu. Ovlaštena osoba ubacuje imena
novih korisnika, ili brǐse imena odsutnih.

4.2.1 Implementacija rječnika pomoću bit-vektora

Sasvim isto kao u poglavlju 4.1. Operacije INSERT( ), DELETE( ) i MEMBER( ) se obavljaju u vremenu
O(1). Implementacija postaje neupotrebljiva ako je elementtype velik.

4.2.2 Implementacija rječnika pomoću liste

Skup shvatimo kao listu, koja može biti sortirana (u skladu s <=) ili nesortirana, te prikazana pomoću
polja ili pointera (vidi potpoglavlje 2.1). Od četiri moguće varijante detaljnije promatramo sortiranu

Page 35

34 4. SKUPOVI

listu prikazanu kao polje. Ta varijanta je pogodna za “statične” skupove, dakle one za koje se često
obavlja funkcija MEMBER( ), a rjede INSERT( ) ili DELETE( ). Funkcija MEMBER( ) obavlja se u vre-
menu O(log2 n), gdje je n duljina liste. Služimo se algoritmom binarnog traženja. Uz pretpostavku
da je tip LIST definiran kao u potpoglavlju 2.1, te uz

typedef LIST SET;

imamo:

int MEMBER (elementtype x, SET A) {
int f, l; /* indeks prvog i zadnjeg elementa razmatrane pod-liste */
int m; /* indeks srednjeg elementa razmatrane pod-liste */
f = 0;
l = A.last;
while (f <= l) {
m = (f+l)/2;
if (A.elements[m] == x)
return 1;

else if (A.elements[m] < x)
f = m+1;

else /* A.elements[m] > x */
l = m-1;

}
return 0;

}

..........................

elements

..........................

..........................

..........................

last

l

m

f

Slika 4.2 Implementacija rječnika pomoću liste.

Da bi se čuvala sortiranost, INSERT( ) mora ubaciti novi element na “pravo” mjesto, što zahtjeva
u najgorem slučaju O(n) prepisivanja elemenata. Slično, DELETE( ) zahtijeva O(n) prepisivanja.

Ako se za naš rječnik često obavljaju INSERT( ) i DELETE( ), a rjede MEMBER( ), tada su pogodnije
ostale tri varijante implementacije pomoću liste. Kod sve tri varijante može se izbjeći prepisivanje

Page 67

66 5. OBLIKOVANJE ALGORITAMA

zahtjevi su posljedica naših pravila. Npr. u čvoru D se originalno zahtijeva da bridovi (a, b) i (a, c)
budu uključeni no onda nužno (a, d) i (a, e) moraju biti isključeni zbog pravila 2. Čvorovi su imenovani
u redoslijedu njihovog nastajanja. Taj redoslijed je posljedica naše heuristike da se prije razgraduje
onaj brat koji ima manju donju ogradu.

aaaaaaaaa

��
��

��
�� HHHHHHHH

HHHHHHHH





� S

S
S
S

#
#

#
##

T
T
T
T

��
��

��
�� HHHHHHHH

H

(b, c) (b, d)
(b, e) (c, e)
(d, e) (c, d)

Ham. cikl.
a b c e d a

cijena: 23

N

(b, c) (c, d)
(c, e) (b, d)
(d, e) (b, e)

Ham. cikl.
a c b e d a

cijena: 19

P

(b, c) (b, d)
(b, e) (c, e)
(d, e) (c, d)

Ham. cikl.
a c e b d a

cijena: 23

A 17.5

(bez zahtjeva)

F 18

(a, d) (a, e)

G 23

(a, d) (a, e)

L 18.5

(a, d) (a, e)

M 23.5

(a, d) (a, e)

D 20.5

(a, c) (a, d) (a, e)
reže se nakon otkrića I

J 18.5

(a, c)

K 21

(a, c) (a, d) (a, e)

C 18.5

(a, b)

I

(b, c) (c, d)
(c, e) (b, d)
(d, e) (b, e)

Ham. cikl.
a b e c d a

cijena: 21

B 17.5

(a, b)

E 18

(a, c)

zaboravlja se zbog I

zaboravlja se zbog I
reže se nakon otkrića I

‘najbolje do sada’ ukupno najbolje

Slika 5.12 Stablo generirano backtracking algoritmom za rješavanje problema trgovačkog putnika.

Similer Documents