[ SuperC @ 26.09.2009. 21:42 ] @
situacija je ovakva: uradio sam zadatak koji radi separate chaining i nakon toga sortira na bazi shell sorta, tako je trazeno u zadatku kao i da nadje najmanji i najveci to je sortira opadajuce i rastuce, taj dio je prosao odgovarajuci program na web stranici od profa. ono sto on jos trazi je sljedece: 1. da program prodjeni odredjeni test performance bez timeouta (da bi bilo jasnije rijesio da radio bez greske do 10 na 5 no kod 10 na 6 javlja gresku) 2. i da unutar program optimizaciju dodam tako da radi caching od minimuma i maximuma kao i caching sortiranih vrijednosti Ispod je code zadatka koji je prosao prva dva dijela zadatka: implementaciju separate chaininga i shell sorta bez greske. Svaka pomoc je dobrodosla jer mi istice rok do kada ovo moram da predam odnosno testiram na internoj stranici. Code: #ifndef AHMETHT_H #define AHMETHT_H #include <iostream> #include "Container.h" // Glavna klasa template <typename E> class AhmetHT : public Container<E> { // separate chain element // sluzi kao nosac za podatke (E) class Node { public: E e; Node * prev ; Node * next ; Node( const E& e ) : e( e ), prev( 0 ), next( 0 ) {}; ~Node( ) { }; }; // hash table element u glavnom nizu istih // sadrzi hash_key vrednost i pokazivac na prvi i poslednji element u Separate Chain // osim konstruktora i destruktora sadrzi potrebne operacije za // dodavanje, trazenje (odredjenog elementa ili min ili max), brisanje jednog elementa, // racunanje duzine lanca i prikaz sadrzaja lanca // ako su first i last postavljeni na 0 onda je element prazan bez obzira na sadrzaj hash_key class HTelement { public: unsigned long hash_key; Node * first ; Node * last ; HTelement( unsigned long hash_key = 0 ) : hash_key( hash_key ), first( 0 ), last( 0 ) {} ; virtual ~HTelement( ) { delete_( first ); }; void add_( Node* node, const E& e ); void remove_( Node* node, const E& e ); bool member_( Node* node, const E& e ) const; size_t size_( Node* node ) const; std::ostream& print_( Node* node, std::ostream &o ) const; void delete_( Node* node ); E min( ) const; E max( ) const; size_t size( ) const; }; // niz hash elemenata HTelement * hashtablevalues; // ukupna duzina hash tabele size_t nmax; // iskoristena duzina hash tabele (uvek je <= od nmax) size_t currlength; // pomocna funkcija za dodavanje elementa u hash tabelu void add_( HTelement* htdata, const E& e ); // pomocna funkcija za brisanje elementa iz hash tabele void remove_( HTelement* htdata, const E& e ); // pomocna funkcija za ispitivanje postojanja elementa u hash tabeli bool member_( HTelement* htdata, const E& e ) const; // pomocna funkcija za ispitivanje postojanja elementa u hash tabeli bool empty_( HTelement* htdata ) const; // pomocna funkcija za nalazenje ukupnog broja elemenata u objektu size_t size_( HTelement* htdata ) const; // pomocna funkcija za stampanje elementa iz hash tabele std::ostream& print_( HTelement* htdata, std::ostream &o ) const; // pomocna funkcija za sortiranje elementa iz hash tabele i ispitivanje Functor-a size_t apply_( HTelement* htdata, const Functor<E>& f, Order order ) const ; // pomocna funkcija za brisanje hash tabele void delete_( HTelement* htdata ); // pomocna funkcija za razmenu sadrzaja elementa iz hash tabele void swap_( HTelement* htdata1, HTelement* htdata2 ) const ; public: AhmetHT<E>() : hashtablevalues( 0 ), nmax(0), currlength(0) { } virtual ~AhmetHT<E>( ) { delete_( hashtablevalues ); } using Container<E>::add; virtual void add( const E e[], size_t s ); using Container<E>::remove; virtual void remove( const E e[], size_t s ); virtual bool member( const E& e ) const { return member_( hashtablevalues, e ); } virtual size_t size( ) const { return size_( hashtablevalues ); } virtual bool empty( ) const { return empty_(hashtablevalues); } virtual size_t apply( const Functor<E>& f, Order order = dontcare ) const {size_t n=apply_( hashtablevalues, f, order ); return n; } virtual E min( ) const; virtual E max( ) const; virtual std::ostream& print( std::ostream &o ) const { return print_( hashtablevalues, o ); } }; // racuna se duzina Separate Chain lanca zakacenog za neki red u hash tabeli template <typename E> size_t AhmetHT<E>::HTelement::size( ) const { if (!first) { // ako je polje first 0 smatramo da je lanac prazan return 0; } return size_(first); } // dodaje se novi element u Separate Chain lanac zakacen za neki red u hash tabeli template <typename E> void AhmetHT<E>::HTelement::add_(AhmetHT<E>::Node* node, const E& e ) { Node * curr = node; if (!first) { // ako je polje first 0 novi element ubacujemo na pocetak lanca i podesavamo ogovarajuce pointere first = new Node( e ); first->next = 0; first->prev = 0; last = first; return; } while (curr != last) { if (e == curr->e) { // ako je novi element jednak nekom postojecem odustajemo od dodavanja return; } /* if (curr->e > e) { // ako je novi element manji od trenutno dostignutog elementa u Separate Chain dodajemo ga pre njega (interno sortiramo elemente u Separate Chain) if (curr == first) { // ako je dostignuti element u stvari onaj prvi, ubacujemo novi ispred njega. azuriraju se i pointeri first = new Node( e ); first->next = curr; curr->prev = first; } else { // u suprotnom ubacujemo novi element ispred dostignutog. azuriraju se i pointeri. pazi se samo da se ne prekine lanac. (curr->prev)->next = new Node( e ); ((curr->prev)->next)->prev = curr->prev; ((curr->prev)->next)->next = curr; curr->prev = (curr->prev)->next; } return; } */ curr = curr->next; } // ako je novi element jednak zadnjem odustajemo od dodavanja if (e == last->e) { return; } /* if (last->e > e) { // ako je novi element manji od zadnjeg elementa u Separate Chain dodajemo ga pre njega (interno sortiramo elemente u Separate Chain) if (last == first) { // ako je zadnji element u stvari onaj prvi, ubacujemo novi ispred njega. azuriraju se i pointeri first = new Node( e ); first->next = last; last->prev = first; } else { // u suprotnom ubacujemo novi element ispred zadnjeg. azuriraju se i pointeri. pazi se samo da se ne prekine lanac. (last->prev)->next = new Node( e ); ((last->prev)->next)->prev = last->prev; ((last->prev)->next)->next = last; last->prev = (last->prev)->next; } return; } */ // ostaje nam samo da novi element ubacimo na kraj liste. azuriraju se pointeri. last->next = new Node( e ); (last->next)->prev = last; (last->next)->next = 0; last = last->next; } // brise se element u Separate Chain zakacen za neki red u hash tabeli template <typename E> void AhmetHT<E>::HTelement::remove_( Node* node, const E& e ) { Node * curr = first; if (!node) return; if (!first) return; // ako su ulazni podatak i polje first prazni onda smo vec pobegli pre ove tacke. while (curr != last) { // u petlji trazimo element koji cemo brisati. petljom kruzimo dok ne izvrtimo ceo lanac ili dok ne nadjemo trazeni. if (e == curr->e) { // ako smo nasli taj element prepakujemo pointere koji uvezuju lanac da oslobodimo tekuci jer njega treba brisemo. Node * Cprev = curr->prev; Node * Cnext = curr->next; Cprev->next = Cnext; Cnext->prev = Cprev; delete curr; curr = 0; return; } curr = curr->next; } // izvrteli smo petlju i jos je ostalo da uradimo proveru da nije bas onaj zadnji taj kog treba obrisati. if (e == last->e) { // ako jeste pripreme se razlikuju ako je zadnji isto sto i prvi ili ako nije. if ( first == last ) { curr=last; first=0; last=0; } else { Node * Cprev = last->prev; Cprev->next = 0; last = Cprev; } // brisemo nadjeni element delete curr; curr = 0; return; } } // ispitivanje postojanja elementa u Separate Chain template <typename E> bool AhmetHT<E>::HTelement::member_(AhmetHT<E>::Node* node, const E& e) const { Node * curr = first; if (!node) { return false; } if (!first) { return false; } // ako su ulazni podatak i polje first prazni onda smo vec pobegli pre ove tacke. while (curr != last) { // u petlji trazimo zadati element. petljom kruzimo dok ne izvrtimo ceo lanac ili dok ne nadjemo trazeni. if (e == curr->e) { // ako smo ga nasli vrati true return true; } curr = curr->next; } // izvrteli smo petlju i jos je ostalo da uradimo proveru da nije bas onaj zadnji taj kog trazimo. if (e == last->e) { // ako smo ga nasli vrati true return true; } // ako smo ovde stigli vrati false jer trazeni element nije nadjen. return false; } // prebrojavanje elemenata u Separate Chain template <typename E> size_t AhmetHT<E>::HTelement::size_( AhmetHT<E>::Node* node ) const { Node * curr = first; size_t nodesize = 0; if (!node) { return nodesize; } if (!first) { return nodesize; } // ako su ulazni podatak i polje first prazni onda smo vec pobegli pre ove tacke. while (curr != 0) { // u petlji prebrojavamo elemente. petljom kruzimo dok ne izvrtimo ceo lanac. usput za svaki element uvecavamo brojac. curr = curr->next; nodesize++; } // vrati sadrzaj brojaca return nodesize; } // stampanje elemenata u Separate Chain template <typename E> std::ostream& AhmetHT<E>::HTelement::print_( AhmetHT<E>::Node* node, std::ostream &o ) const { if (node) { // ako ulazni podatak nije 0 odstampaj i rekurzivno pozovi da da odstampas sledeci o << node->e; o << ' '; print_( node->next, o ); } return o; } // brisanje Separate Chain vezanog za neki red u hash tabeli template <typename E> void AhmetHT<E>::HTelement::delete_( AhmetHT<E>::Node* node ) { if (node) { // ako ulazni podatak nije 0 rekurzivno pozovi da obrises sledeci delete_( node->next ); // brisi trenutno dostignuti element i azuriraj pointer delete node; node = 0; } } // trazenje najmanjeg elementa u Separate Chain template <typename E> E AhmetHT<E>::HTelement::min( ) const { if (!first) throw typename Container<E>::Exception( "HTelement::min(): empty" ); Node* current = first; Node* minnode = first; while (current != 0) { // u petlji ispitujemo da li ima neki manji element od prvog. petljom kruzimo dok ne izvrtimo ceo lanac. // zbog optimizacije add_ funkcije nismo ni morali da idemo u petlju. (add_ funkcija sortira elemente u Separate Chain u rastucem redosledu) // trebalo je samo proglasiti prvi za najmanji if (minnode->e > current->e) { // ako ima manji proglasi ga za najmanji minnode = current; } current = current->next; } // vrati nadjeni najmanji return minnode->e; } // trazenje najveceg elementa u Separate Chain template <typename E> E AhmetHT<E>::HTelement::max( ) const { if (!first) throw typename Container<E>::Exception( "HTelement::max(): empty" ); Node* current = first; Node* maxnode = first; while (current != 0) { // u petlji ispitujemo da li ima neki veci element od prvog. petljom kruzimo dok ne izvrtimo ceo lanac. // zbog optimizacije add_ funkcije nismo ni morali da idemo u petlju. (add_ funkcija sortira elemente u Separate Chain u rastucem redosledu) // trebalo je samo proglasiti zadnji za najveci if (current->e > maxnode->e) { // ako ima veci proglasi ga za najveci maxnode = current; } current = current->next; } return maxnode->e; } // brisanje hash tabele template <typename E> void AhmetHT<E>::delete_( AhmetHT<E>::HTelement* htdata ) { if (htdata) { // ako trazena tabela nije prazna brisemo redove. size_t i=0; while (i < nmax) { // za svaki red u tabeli proveravaj da li ima neki separate chain zakacen za njega i ako ima pozovi delete funkciju za taj lanac. if ((htdata[i].first)&&(htdata[i].last)) htdata[i].delete_(htdata[i].first); // posle brisanja azuriraj podatke htdata[i].first = 0; htdata[i].last = 0; htdata[i].hash_key = 0; i++; } // posto je sada tabela prazna pozovi DELETE delete[] htdata; htdata = 0; } } // izmena redova u hash tabeli template <typename E> void AhmetHT<E>::swap_( AhmetHT<E>::HTelement* htdata1, AhmetHT<E>::HTelement* htdata2 ) const { HTelement temp; if ((htdata1!=0) && (htdata2!=0)) { // ako predati pointeri nisu 0 razmeni njihov sadrzaj koristeci pomocnu velicinu temp. temp.hash_key = htdata2->hash_key ; temp.first = htdata2->first ; temp.last = htdata2->last ; htdata2->hash_key = htdata1->hash_key ; htdata2->first = htdata1->first ; htdata2->last = htdata1->last ; htdata1->hash_key = temp.hash_key ; htdata1->first = temp.first ; htdata1->last = temp.last ; temp.hash_key = 0 ; temp.first = 0 ; temp.last = 0 ; } } // dodaje se novi element u hash tabelu template <typename E> void AhmetHT<E>::add_( AhmetHT<E>::HTelement* htdata, const E& e ) { if (htdata == 0) { // pri kreiranju objekta hash tabela je prazna i bez elemenata. zato se inicijalno rezervise prostor za prvih 101 element. size_t newnmax = 101; HTelement * newvalues = 0; newvalues = new HTelement[newnmax]; hashtablevalues = newvalues; htdata = newvalues; nmax = newnmax; // inicijalizacija novih redova u hash tabeli for (size_t i = 0; i < nmax; ++i) { hashtablevalues[i].hash_key = 0; hashtablevalues[i].first = 0; hashtablevalues[i].last = 0; } } else if (currlength + 1 > nmax) { // ako je broj zeljenih elemenata premasio broj mogucih idemo na sirenje tabele. size_t newnmax , repacksize , currE ; HTelement * newvalues ; E *repackarr ; // pointer za niz svih unetih podataka kako bi se mogao uraditi ponovni add nad novonastalom tabelom. Node* node; newnmax = nmax; repacksize = this->size(); // ukupan broj elemenata za koje treba uraditi rehash. currE = 0; newvalues = 0; repackarr = 0; node = 0; while (currlength + 1 > newnmax) newnmax = (size_t)( newnmax * 1.2 + 2 ); // izracunaj novi nmax koji je dovoljno veliki da se smesti trazeni broj elemenata. // inicijalizacija nove hash tabele newvalues = new HTelement[newnmax]; for (size_t i = 0; i < newnmax; ++i) { newvalues[i].hash_key = 0; newvalues[i].first = 0; newvalues[i].last = 0; } // kreiramo niz za cuvanje do sada unetih podataka kako bi se uradio ponovo add za njih (radi regenerisanja hash_keys) repackarr = new E[repacksize]; // trazimo po postojecoj hash tabeli elemente i dodajemo ih u niz za cuvanje for (size_t i = 0; i < nmax; ++i) { if ( !hashtablevalues[i].first ) continue ; // ako je polje first prazno element hash tabele nije aktivan node = hashtablevalues[i].first ; while ( node ) { // vadimo jedan po jedan element iz Separate Chain vezanog za tekuci red u hash tabeli repackarr[currE] = (node->e) ; currE++; node = node->next; } } // brisemo staru hash tabelu i proglasavamo novu za tekucu, uz podesavanje duzina prema novoj tabeli delete[] hashtablevalues; hashtablevalues = newvalues; htdata = newvalues; nmax = newnmax; currlength = 0; this->add(repackarr, repacksize); // na kraju ovog dela ceo onaj niz vracamo u hash tabelu uz rehash. delete[] repackarr; repackarr = 0; } unsigned long currhashValue = hashValue(e); // racunamo hash elementa koji se dodaje. size_t i ; for (i = 0; i<currlength; i++) { // trazimo da li izracunati hash vec postoji u tabeli. if ( htdata[i].hash_key == currhashValue ) { break; }; }; bool didEexist = this->member( e ); // proveravamo da li slucajno element koji zelimo dodati vec postoji u hash tabeli. if ((!didEexist) && (i==currlength)) { // ako ne postoji ni hash ni sam element do sada zauzmi novo polje u tabeli za njegov smestaj. currlength++; htdata[currlength-1].hash_key = currhashValue; }; if (didEexist) return ; // ako element postoji vracamo se nazad bez generisanja duplikata for (i = 0; i<currlength; i++) { // nadji slot u kome je hash trenutnog elementa i ubaci ga u njegov Separate Chain if ( htdata[i].hash_key == currhashValue ) { if (!htdata[i].member_(htdata[i].first, e)) { htdata[i].add_(htdata[i].first, e); return; }; }; }; } // dodaj niz elemenata u hash tabelu template <typename E> void AhmetHT<E>::add( const E e[], size_t s ) { for (size_t i = 0; i < s; ++i) { add_( hashtablevalues , e[i] ); } } // brisanje trazenog elementa iz hash tabele template <typename E> void AhmetHT<E>::remove_( AhmetHT<E>::HTelement* htdata, const E& e ) { unsigned long currhashValue = 0; if (!htdata) return; // ako je tabela prazna idi nazad currhashValue = hashValue(e); // izracunaj hash vrednost elementa for (size_t index = 0; index < nmax ; index++ ) { // nadji odakle se brise trazeni element if ((!htdata[index].first)&&(!htdata[index].last)) continue; // ako su polja first ili last na 0 vrati se nazad na pocetak petlje. // if (currhashValue == htdata[index].hash_key) { if (htdata[index].member_(htdata[index].first, e)) { // ako je nadjen index u hash tabeli iz koje se brise element pozovi remove iz tog Separate Chain-a da izbrise isti. htdata[index].remove_(htdata[index].first, e); if (htdata[index].first == 0) { // ako je posle brisanja polje first postalo 0 znaci taj separate chain nije vise u upotrebi te se ostatak tabele prepakuje... htdata[index].hash_key = 0; htdata[index].first = 0; htdata[index].last = 0; for (size_t i=(index+1); i<currlength; i++) { // pomeri sve elemente posle njega za jedno mesto unazad HTelement *htdid = &htdata[i-1] ; HTelement *htdi = &htdata[i] ; swap_( htdid, htdi ); } // umanji brojac zauzetih elenata. currlength--; } return; } } } template <typename E> void AhmetHT<E>::remove( const E e[], size_t s ) { for (size_t i = 0; i < s; ++i) { AhmetHT<E>::remove_( hashtablevalues, e[i] ); } } template <typename E> bool AhmetHT<E>::member_( AhmetHT<E>::HTelement* htdata, const E& e ) const { unsigned long currhashValue = 0; if (!htdata) return false; size_t loccurrlength = currlength; currhashValue = hashValue(e); for (size_t index = 0; index < loccurrlength ; index++ ) { if (!htdata[index].first) continue; if (!htdata[index].last) continue; if (htdata[index].member_(htdata[index].first, e)) { return htdata[index].member_(htdata[index].first, e); } } return false; } template <typename E> size_t AhmetHT<E>::size_( AhmetHT<E>::HTelement* htdata ) const { size_t htelsize = 0; size_t nodesize = 0; if (!htdata) { return nodesize; } while (htelsize < nmax) { if (htdata[htelsize].first != 0) { nodesize += htdata[htelsize].size(); } htelsize++; } return nodesize; } template <typename E> bool AhmetHT<E>::empty_( AhmetHT<E>::HTelement* htdata ) const { size_t htelsize = 0; if (!htdata) { return true; } while (htelsize < nmax) { if (htdata[htelsize].first != 0) { return false; } htelsize++; } return true; } template <typename E> E AhmetHT<E>::min( ) const { size_t counterHT = 0; E mine ; if (!hashtablevalues) throw typename Container<E>::Exception( "Ahmet::min(): empty" ); while (hashtablevalues[counterHT].first == 0) { counterHT++; if ( counterHT > nmax ) throw typename Container<E>::Exception( "Ahmet::min(): empty" ); } mine = hashtablevalues[counterHT].first->e; for (counterHT=0;counterHT<nmax;counterHT++) { if ( ! hashtablevalues[counterHT].first ) { continue; } if (mine > hashtablevalues[counterHT].min()) { mine = hashtablevalues[counterHT].min(); } } return mine; } template <typename E> E AhmetHT<E>::max( ) const { size_t counterHT = 0; E maxe; if (!hashtablevalues) throw typename Container<E>::Exception( "Ahmet::max(): empty" ); while (hashtablevalues[counterHT].first == 0) { counterHT++; if ( counterHT > nmax ) throw typename Container<E>::Exception( "Ahmet::max(): empty" ); } maxe = hashtablevalues[counterHT].first->e; for (counterHT=0;counterHT<nmax;counterHT++) { if ( ! hashtablevalues[counterHT].first ) { continue; } if (hashtablevalues[counterHT].max() > maxe) { maxe = hashtablevalues[counterHT].max(); } } return maxe; } template <typename E> std::ostream& AhmetHT<E>::print_( AhmetHT<E>::HTelement* htdata , std::ostream &o ) const { size_t i = 0; if (htdata) { for (i=0;i<nmax;i++) { if ( ! htdata[i].first ) { continue; } htdata[i].print_(htdata[i].first, o); } } return o; } template <typename E> size_t AhmetHT<E>::apply_( AhmetHT<E>::HTelement* htdata, const Functor<E>& f, Order order) const { if(nmax==0) return 0; HTelement temp; Node *node; int counterETupple = 0; size_t repacksize, currE=0; if (order == dontcare) { bool apply=true; for (size_t i = 0;apply&& i < nmax; ++i) { if ( !htdata[i].first ) continue ; if ( !htdata[i].last ) continue ; node = htdata[i].first ; while ( node ) { counterETupple++; if(!f((node->e))){ apply=false; break; } node = node->next; } } return counterETupple; } E **repackarr ; repacksize = this->size(); repackarr = new E *[repacksize]; for (size_t i = 0; i < nmax; ++i) { if ( !htdata[i].first ) continue ; if ( !htdata[i].last ) continue ; node = htdata[i].first ; while ( node ) { repackarr[currE] = &(node->e) ; currE++; node = node->next; } } //shell sort int flag1 = 1; int d1 = repacksize; while( flag1 || (d1 > 1)) // boolean flag (true when not equal to 0) { flag1 = 0; // reset flag to 0 to check for future swaps d1 = (d1+1) / 2; for (size_t i = 0; i < (repacksize - d1); i++) { if (!(*repackarr[i + d1] > *repackarr[i])) { std::swap(*repackarr[i],*repackarr[i+d1]); flag1 = 1; // tells swap has occurred } } } if (order == descending) { for (int ii=(repacksize-1);ii>=0;ii--) { counterETupple++; if (!f(*repackarr[ii])) { break; } } } else { for (size_t i=0;i<repacksize;i++) { counterETupple++; if (!f(*repackarr[i])) { break; } } } delete[] repackarr; repackarr=NULL; return counterETupple; } #endif //AHMETHT_H |