@demon_01
Pravo da ti kazem, kada sam video zadatak i procitao da je profa rekao kako je ovo dovoljno, pomislio sam da ja u stvari ne znam sta je hash. Ali dobro, onda sam malo razmislio.
Ovde ima nekoliko mogucih i dovoljno dobrih resenja, a prva podela medju resenjima zavisi od toga da li koristimo C ili C++. Delovi koda koji se ovde vide uglavnom upucuju na C, osim koriscenja "cout <<" sto upucuje na C++.
Nego, da analiziramo problem.
1. struct Cvor nam govori da se radi o jednostruko ulancanoj listi. Ovo je vrlo bitno da se uzme u obzir jer od toga zavisi algoritam izbacivanja elemenata iz liste, a isto tako i algoritam ubacivanja u hash listu kao i definicija na sta pokazuje atribut pok u strukturi HashZapis. Da pojasnim: da bi se uspesno izbacio element iz jednostruko ulancane liste, potrebno je imati pokazivac na prethodni element u listi; da bi to bilo moguce, HashZapis za dati kljuc mora da pokazuje na element koji prethodi elementu na koji se odnosi taj hash zapis.
Ovo ima jos jednu posledicu: prvi element u listi mora bit tzv. head, dakle Cvor kojem je jedina uloga da predstavlja vrh liste, ali ne i da nosi korisan podatak (broj). Ili to, ili da se NULL pointeri koriste kao nekakvi indikatori, sto nije bas najzdravije resenje.
2. Hash tabela, kao i hash funkcija nisu definisani postavkom zadatka. To znaci da cemo napisati resenje koje podrazumeva da su negde tabela i funkcija definisani, a kasnije mozemo da predlozimo jedno razumno resenje za te dve stvari.
3. Brisanje elemenata iz liste koji su prethodno dinamicki alocirani moze se vrsiti ili:
a) samo pozivom funkcije free(), ukoliko je u pitanju jezik C;
b) pozivom funkcije free(), ako je objekat alociran sa malloc, calloc itd, a brisace se operatorom delete ukoliko je predhodno alociran sa new, u slucaju da koristimo C++.
Da predjemo na resenje:
Prvo cemo napisati funkciju koja brise element iz jednostruko ulancane liste. Kao sto je gore napomenuto, da bi to uradili kako treba, potrebno je da imamo pokazivac na prethodni Cvor u listi, tj. Cvor koji sadrzi pokazivac na element koji zelimo da obrisemo. Razlog za to je jednostavan: kada budemo izbrisali Cvor koji zelimo, moramo Cvor koji dolazi posle njega da povezemo na Cvor koji mu je prethodio.
Code:
/*
prethodnik[in] - pokazivac na element u listi koji je prethodnik elementu koji zelimo da obrisemo
*/
void obrisiElementIzListe(Cvor *prethodnik) {
if(prethodnik == 0) return;//Ne zelimo da ispadnemo budale, te ako je argument NULL pointer, sa prezirom cemo izignorisati celu operaciju.
Cvor *zaBrisanje = prethodnik->sljedeci;
if(zaBrisanje == 0) return; //ovo je kraj liste, trazeni element ni ne postoji ili je u pitanju neka greska.
prethodnik->sljedeci = zaBrisanje->sljedeci;//prevezujemo elemente liste
free(zaBrisanje);//ili delete zaBrisanje - vidi 3. b)
return;// moze, a i ne mora da stoji
}
Napomena: ova funkcija je mogla da vraca neki rezultat, npr. tipa int, koji bi predstavljao kod greske u slucajevima da je argument funkcije 0 (NULL), ili da je zaBrisanje == 0. Priroda ovog problema je takva da se moze reci da su te situacije nemoguce, te da su one dve provere na NULL suvisne. Medjutim, dobra praksa defanzivnog programiranja, a posebno rada na projektima koje razvija citav tim (ili nekoliko timova), nalaze da se ovakve provere uredno vrse, jer nikad ne znas sta neko moze da prosledi tvojoj funkciji.
Da se sada pozabavimo nalazenjem odgovarajuceg hash zapisa, izbacivanjem tog zapisa iz tabele i uklanjanjem elementa na koji se taj hash zapis odnosi. Kao sto je ranije receno, ovaj hash zapis ce pokazivati na prethodnika elementa u glavnoj listi, na kojeg se zapis odnosi.
Hash tabela je zapravo niz mini-lista koje sadrze elemente za koje hash funkcija daje isti rezultat. Deklarisacemo funkciju koja nam daje pokazivac na prvi element jedne takve mini-liste (reda) u hash tabeli.
Code:
HashZapis *dajRedIzHashTabele(int kljuc);
U postavci zadatka postoji jedan problem, a to je da HashZapis ne sadrzi vrednost podatka na koji se odnosi, a to je nesto sto ce nam biti potrebno. Napisacemo jednu malu funkciju koja ce vratiti taj podatak za dati HashZapis. Napomena: razne provere na NULL koje su mozda i suvisne u ovom zadatku, ipak cemo pisati iz navedenih razloga kao i u gornjem kodu. Zbog prirode int-a i nedefinisanog opsega vrednosti za podatke, imamo problem da prijavimo gresku u ovim slucajevima. Ukoliko bi ovo bio C++, imali bismo mogucnost da bacimo exception, ali sada to necemo raditi, vec cemo se samo braniti od nedozvoljenih pristupa memoriji.
Code:
int dajVrednostPodatka(HashZapis *zapis) {
if(zapis == 0) return 0;
Cvor *prethodnik = zapis->sljedeci;
if(prethodnik == 0) return 0;
if(prethodnik->sljedeci == 0) return 0;
//ok, sada mozemo da dohvatimo podatak
return prethodnik->sljedeci->broj;
}
Sada cemo napisati funkciju koja ce na osnovu reda u hash tabeli da pronadje nase duplikate i da izbaci, cuvajuci samo jedan element sa zadatim kljucem. Iz fazona cemo dati da ta funkcija kao rezultat vrati broj obrisanih elemenata.
Code:
/*
kljuc[in] - kljuc koji se odnosi na elemente cije duplikate valja izbaciti
return broj obrisanih elemenata
*/
unsigned int izbaciDuplikate(int kljuc) {
unsigned int rezultat = 0;
HashZapis *redUHashTabeli = dajRedIzTabele(kljuc);
if(redUHashTabeli == 0) return 0;
//trazimo original
while(redUHashTabeli) {
if(kljuc == dajVrednostPodatka(redUHashTabeli)) break;//nasli smo ga
redUHashTabeli = redUHashTabeli->sljedeci;
}
if(redUHashTabeli == 0) return 0;//nismo nasli ni original
HashZapis *prethodni = redUHashTabeli;//trebace nam za brisanje duplikata iz Hash tabele
redUHashTabeli = redUHashTabeli->sljedeci;//prvi posle originala
while(redUHashTabeli) {
if(kljuc == dajVrednostPodatka(redUHashTabeli)) {
//duplikat - obrisacemo ga
obrisiElementIzListe(redUHashTabeli->pok);
//sada da izbacimo i ovaj hash zapis
prethodni->sljedeci = redUHashTabeli->sljedeci;
free(redUHashTabeli);//ili delete redUHashTabeli;
++rezultat;
} else {
prethodni = redUHashTabeli;
}
redUHashTabeli = prethodni->sljedeci;
}
return rezultat;
To bi sada trebalo da bude to.
Hajde da vidimo i neki predlog za realizaciju ove hash tabele i hash funkciju.
U principu, potreban nam je neki vektor ovih mini lista ciji elementi imaju istu vrednost hash funkcije.
Sama vrednost "broj" koja se javlja u strukturi Cvor, nepodesna je iz dva razloga: int moze biti i negativan, a to nije dozvoljena vrednost indeksa za vektore; int pokriva ogroman broj vrednosti i toliki vektor nam nije realan za implementaciju. Dakle, potreban nam je vektor ogranicene velicine, neka to bude neka vrednost VELICINA_TABELE.
Takodje, potrebna nam je i nekakva hash funkcija koja bi odgovarala int-u. U tom smislu, potrebna nam je takva funkcija koja ce dati dobru raspodelu kljuceva, ali i koja ce biti jednostavna za racunanje da ne bismo izgubili na smislu hashiranja. Rezultat funkcije mora biti ulaz u tabelu, dakle nenegativan broj. Dovoljno dobro resenje za postavku ovog zadatka bi bila sledeca hash funkcija:
Code:
#define VELICINA_TABELE 100
unsigned int hash(int vrednost) {
return abs(vrednost) % VELICINA_TABELE;
}
(Kompajler ce ovde verovatno da izbaci beznacajno upozrenje).
Na ovaj nacin, sama tabela se konstruise sa:
Code:
HashZapis *hashTabela[VELICINA_TABELE];
E sada, ja ovo nisam ni kompajlirao, a kamo li testirao. Bez obzira sto bih da licim na C, ima ovde nekih momenata koji su rezervisani za C++.
Ako i ima neka greska, jbg. ali ovo razumi i kao neke guide lines.
[Ovu poruku je menjao Mihajlo Cvetanović dana 05.09.2010. u 12:26 GMT+1]
izbacivanje duplikata iz liste uz pomoc hash tabele
