C++ coda con priorità realizzata con albero binario

[pietrol83]

https://skydrive.live.com/redir.aspx...FE0D3E54198821!593&parid=root


ciao a tutti, sto implementando una coda con priorità mediante albero binario. nel test vengono inseriti nella coda 10 nodi ma arrivato all'inserimento del quarto elemento viene violata un'asserzione. in pratica ciò accade perchè per inserire il quarto nodo bisogna entrare nel blocco dell'ultimo else del metodo inserisci. l'asserzione violata è quella relativa al metodo binpadre(tmp), la quale mi dice che l'albero non deve essere vuoto e il nodo tmp non deve essere la radice. perchè viene violata l'asserzione se ultimo (che è il valore che assume tmp) non è la radice???

[pietrol83]

in pratica voglio inserire i seguenti nodi:

valore priorità
1........1
2........2
3........3
4........4
5........5
6........6
7........7
8........8
9........9
10......10

dopo ogni inserimento viene chiamato il metodo min() che restituisce il valore con la priorità più piccola, che si trova nella radice dell'albero, ma invece di ottenere sempre 1, ad ogni 3 inserimenti il metodo restituisce il valore dell'inserimento successivo, cioè dopo nell'inserimento dei nodi 1, 2, 3 il metodo restituisce 1, poi dal 4 al 6 restituisce 4, dal 7 al 9 restituisce 7 e quando inserisco il 10 restituisce 10 anzichè sempre 1. come mai???

[alka]

Originariamente inviato da pietrol83
ciao a tutti, sto implementando una coda con priorità mediante albero binario.

Il codice va pubblicato sul forum, usando il tag [CODE], limitatamente alle parti significative che riguardano il problema riscontrato.

Non è lecito postare problemi eccessivamente ampi e astratti e interi programmi da scaricare e compilare per diagnosticare gli errori e analizzare il codice per fornire responsi.

[pietrol83]

allora posto il codice che non va ma lascio comunque il link in caso si voglia consultare il resto del codice.

template<class tipoelem>
void pricodaab<tipoelem>::inserisci(tipoelem elem)
{
   nodoalberop<tipoelem> *tmp = NULL;
   int priority;
   cout << "inserire la priorita' del nodo con valore " << elem << ": ";
   cin >> priority;
   
   //INSERIMENTO DELLA FOGLIA (MODIFICA DELLA STRUTTURA
   if(this->pricodavuota())
   {
      pric.insbinradice(tmp);
      pric.binradice()->setetichetta(elem);
      pric.binradice()->setpri(priority);
      ultimo = pric.binradice();
      delete tmp;
   }
   else 
   {
      if(ultimo == pric.binradice())
      {
         pric.insfigliosx(pric.binradice());
         ultimo = pric.figliosx(pric.binradice());
         ultimo->setetichetta(elem);
         ultimo->setpri(priority);
      }
      else
      {
         if(ultimo == pric.figliosx(pric.binpadre(ultimo)))
         {
            tmp = pric.binpadre(ultimo);
            pric.insfigliodx(tmp);
            ultimo = pric.figliodx(tmp);
            ultimo->setetichetta(elem);
            ultimo->setpri(priority);
            delete tmp;
         }
         else
         {
            tmp = ultimo;
            while((tmp != pric.binradice()) && (tmp == pric.figliodx(pric.binpadre(tmp))))
               tmp = pric.binpadre(tmp);
            if(tmp != pric.binradice())
               tmp = pric.figliodx(pric.binpadre(tmp));
            while(!(pric.sxvuoto(tmp)/* && pric.dxvuoto(tmp)*/))
               tmp = pric.figliosx(tmp);
            pric.insfigliosx(tmp);
            ultimo = pric.figliosx(tmp);
            ultimo->setetichetta(elem);
            ultimo->setpri(priority);
            delete tmp;
         }
      }
   }
   
   //AGGIUSTAMENTO DELLA STRUTTURA
   bool finito = false;
   tmp = ultimo;
   while(!finito && (tmp != pric.binradice()))
   {
      if(tmp->getpri() < pric.binpadre(tmp)->getpri())
      {
         tipoelem elemtemp = tmp->getetichetta();
         int pritemp = tmp->getpri();
         tmp->setetichetta(pric.binpadre(tmp)->getetichetta());
         tmp->setpri(pric.binpadre(tmp)->getpri());
         pric.binpadre(tmp)->setetichetta(elemtemp);
         pric.binpadre(tmp)->setpri(pritemp);
         tmp = pric.binpadre(tmp);
      }
      else
         finito = true;
   }
}

chi mi aiuta a capire dov'è l'errore?

[pietrol83]

ho notato anche che gli inserimenti avengono solo sui primi tre nodi, cioè mentre inserisco i nodi da 4 a 6, questi vanno a sovrascrivere i primi 3 anzichè aggiungere nuove foglie. ma perchè fa questo??? a me sembra che il codica sia fatto bene. maledetti puntatori!!!

[webMontana]

ciao pietrol83, l'hai poi finita quest'implementazione dell'heap con albero binario??
xkè ank'io ci sto sbattendo la testa da un pò....
ma purtroppo il link ke hai postato inizialmente nn è + attivo....
potresti postarmi il codice finale gentilmente
te ne sarei davvero grato
grazie ciao