Matematyka.pl

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

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.

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.

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?

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.

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

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

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