sterta
- kamil.jack
- Użytkownik
- Posty: 86
- Rejestracja: 10 lut 2008, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 27 razy
sterta
witam
mam do zaimplementowania
Rozpoczynając od klasy bazowej reprezentującej zbiór elementów dowolnego
typu, utwórz hierarchię klas umożliwiającą tworzenie stert (ang. heap)
elementów dowolnego typu ze zdefiniowaną relacją liniowego porządku.
i chce zaimplementowac ta sterte za pomoca listy dwukeirunkowej, majac dwa wskazniki poczatek i koniec
na czym ma polegac dodawanie/usuwanie elementu do/ze sterty (za pomoca listy dwukierunkowej)?
mam do zaimplementowania
Rozpoczynając od klasy bazowej reprezentującej zbiór elementów dowolnego
typu, utwórz hierarchię klas umożliwiającą tworzenie stert (ang. heap)
elementów dowolnego typu ze zdefiniowaną relacją liniowego porządku.
i chce zaimplementowac ta sterte za pomoca listy dwukeirunkowej, majac dwa wskazniki poczatek i koniec
na czym ma polegac dodawanie/usuwanie elementu do/ze sterty (za pomoca listy dwukierunkowej)?
- eloar
- Użytkownik
- Posty: 106
- Rejestracja: 18 cze 2007, o 16:59
- Płeć: Mężczyzna
- Lokalizacja: Kobyłka
- Podziękował: 8 razy
- Pomógł: 12 razy
sterta
Sterta jest strukturą drzewiastą. Nie jest to jednak rodzaj drzewa binarnego, czy innego. Porządek istnieje jedynie w pionie. Oznacza to, że wszystkie elementy na poziomie n+1 wg. zdefiniowanego porządku następują po elementach z poziomu n.
Lista nie nada się do implementacji. W zależności od tego ile chcesz mieć następników musisz stworzyć strukturę podobną do wierzchołka w drzewie.
Lista nie nada się do implementacji. W zależności od tego ile chcesz mieć następników musisz stworzyć strukturę podobną do wierzchołka w drzewie.
- kamil.jack
- Użytkownik
- Posty: 86
- Rejestracja: 10 lut 2008, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 27 razy
sterta
dobra zrobilem za pomoca tablicy czy takie funkcje dobrze napisalem
[ Dodano: 1 Czerwca 2008, 12:11 ]
jest źle, bo przesunięcie w dół wybiera większy z 2 synów, a ja rozważam tutaj tylko lewego syna)
moglby ktos poprawic?
- void push_up(int a); //Przesuniecie elementu w gore sterty
void push_down(int b); //Przesuniecie elementu w dol sterty
(typ *elements; //Tablica elementow
void swap(int a, int b); //Zamienienie miejscami elementow o indeksach a i b)
Kod: Zaznacz cały
template<class typ>
void sterta<typ>::push_up(int x) {
while(x>0) {
if((elements[x])>(elements[x/2])) {
swap(x, x/2);
x/=2;
}
else return;
}
}
template<class typ>
void sterta<typ>::push_down(int x) {
while(2*x<size) {
if(x==0) {
if(elements[0]<elements[1]) { swap(0,1); x=1; }
else return;
}
else {
if(elements[x]<elements[2*x]) { swap(x, 2*x); x*=2; }
else return;
}
}
}
[ Dodano: 1 Czerwca 2008, 12:11 ]
jest źle, bo przesunięcie w dół wybiera większy z 2 synów, a ja rozważam tutaj tylko lewego syna)
moglby ktos poprawic?
- eloar
- Użytkownik
- Posty: 106
- Rejestracja: 18 cze 2007, o 16:59
- Płeć: Mężczyzna
- Lokalizacja: Kobyłka
- Podziękował: 8 razy
- Pomógł: 12 razy
sterta
po co uzywasz template'a skoro nie ma on zadnego wplywu na klase, na metody? Template powinien wskazywac na typ przechowywanego elementu, tymczasem Twoje metody w klasie wskazuja, ze zawsze przechowujesz int. To taki podstawowy blad.
- kamil.jack
- Użytkownik
- Posty: 86
- Rejestracja: 10 lut 2008, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 27 razy
sterta
no chyba sie mylisz bo te funkcje dostaja jako argument numer indeksu tablicy wiec dlatego jest int
[ Dodano: 2 Czerwca 2008, 13:55 ]
dodawanie elementu wyglada tak
[ Dodano: 2 Czerwca 2008, 13:55 ]
dodawanie elementu wyglada tak
Kod: Zaznacz cały
/***** DODANIE ELEMENTU *****/
template <class typ>
sterta<typ> & sterta<typ>::dodaj_e(const typ & elem)
{
typ * pom = &(sterta<typ>::lista += elem); //statyczna lista zapobiegajaca redundancji
if ( !(*this > (elem))) //jesli sterta zawiera jzu ten element to nei dodawaj
{
inflate(); //powieksza tablice o jeden
elements[size-1] = *pom;
push_up(size-1);
}
return *this;
}
Kod: Zaznacz cały
/***** USUNIECIE ELEMENTU *****/
template <class typ>
sterta<typ> & sterta<typ>::usun_e (const typ & elem)
{
try {
if ((*this > elem) == 0) //jesli sterta nie zawiera danego elementu to nie ma czego usuwac
throw -1;
sterta<typ>::lista -= elem; //usun z listy statycznej element(zapobiega redundancji)
int i = find(elem); //znajduje element i zwraca indeks w tablicy
if(i != size-1) swap(i, size-1);
deflate(); //zmniejsza tablice o jeden
push_down(0);
}
catch(int x){
if (x == -1)
std::cout << "Nie ma takiego elementu na stercie." << std::endl;
}
return *this;
}
- kamil.jack
- Użytkownik
- Posty: 86
- Rejestracja: 10 lut 2008, o 14:27
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 27 razy
sterta
ja indeksowanei msuze zrobic od 0 czy tak jest dobrze zrobiona funckja:
Kod: Zaznacz cały
template<class typ>
void sterta<typ>::push_up(int x)
{
while(x>0)
{
if(x%2==1)
{
if((elements[x])>(elements[x/2]))
{
swap(x, x/2);
x/=2;
}
else return;
}
else
{
if((elements[x])>(elements[x/2 -1]))
{
swap(x, ((x/2) - 1));
x=x/2 -1;
}
else return;
}
}
}