sterta

[kamil.jack]

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)?

[N4RQ5]

Wydaje mi się że sterta to struktura oparta na drzewie a nie na liście. Tak więc lista dwukierunkowa jest tu zupełnie nietrafionym pomysłem.

[eloar]

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.

[kamil.jack]

dobra zrobilem za pomoca tablicy czy takie funkcje dobrze napisalem

• 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]

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]

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

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;
}

[kadiii]

Sterta w wersji tablicowej jest elementarnie opisana w książce Algorytmy struktury danych i techniki programowania Piotra Wróblewskiego. Polecam przeczytać

[kamil.jack]

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;
  }
 }
}