Cerco disperatamente aiuto

di il
3 risposte

Cerco disperatamente aiuto

Ragazzi sono nuovo..avrei bisogno di un immenso favore...qualcuno saprebbe risolvermi questo esercizio assegnatomi??

dato un heap e un elemento, implementare una funzione che mi restituisca l indice dell'elemento se lo stesso e presente,oppure -1 se non e presente.(da fare sfruttando le proprieta degli heap).

vi prego aiutatemi.. grazie e complimenti per il forum

3 Risposte

  • Re: Cerco disperatamente aiuto

    Ciao,

    Hai chiaro come è strutturato uno heap? La funzione di ricerca non è molto complicata da effettuare...

    Parti dalla radice e visita ricorsivamente (i figli del nodo in posizione i sono sempre in posizione 2i e 2i+1). Quando entri in un nodo che contiene un valore maggiore di quello che stai cercando interrompi la ricorsione, altrimenti prosegui su entrambi i figli (ovviamente se esistono).
    Quando entri in un nodo che ha il valore che cerchi puoi uscire dalla funzione e ritornarne l'indice. Se arrivi al termine delle chiamate ricorsive restituisci -1 poiché quello che cerchi non si trova nello heap.

    Uno scheletro può essere il seguente:
    int cercaHeap(int* heap,int indice,int valore){
      //controlli heap[indice]
      //Se è quello che ti interessa ritorni indice
      //Se è maggiore ritorni -1
    
      //Se è minore
      //Cerchi nel primo figlio
      int risultato=cercaHeap(heap,indice*2,valore);
      //Se risultato è -1 cerchi nell'altro
      risultato=cercaHeap(heap,indice*2+1,valore);
      //Torni il risultato. Sarà -1 o l'indice trovato
    }
    La cosa può anche essere fatta in maniera non ricorsiva, oppure mantenendo la ricorsione e controllando subito il nodo corrente ed i due figli per risparmiare un passaggio.

    Ciaociao
  • Re: Cerco disperatamente aiuto

    Io avevo gia fatto una mezza cosa, ma il valore che mi restituisce e sempre 0. posso mandartela cosi magari gli dai uno sguardo?? io intanto cerco di fare buon uso delle cose che mi hai detto..sei stato gentilissimo..grazie

    //la funzione che avevo fatto e questa//
    int Ricerca(int A[MAX],int el,int i,int Arraysize)
    {
    if (i<ArraySize/2) /* non e una foglia*/
    {
    if (A==el) return i;
    else

    if ((el<=A[2*i+1]) && (el<=A[2*i+2])) /*controllo su entrambi i figli*/
    {
    if (Ricerca(A,el,(2*i+1),Arraysize) == -1)
    return (Ricerca(A,el,(2*i+2),Arraysize));
    else
    return 2*i+1 ;


    }
    else
    if (el<=A[2*i+1]) return Ricerca(A,el,(2*i+1),Arraysize);
    else
    if (el<=A[2*i+2]) return Ricerca(A,el,(2*i+2),Arraysize);
    else
    return -1;
    }
    else /* e una foglia*/
    if (A==el)
    return i;
    else return -1;
  • Re: Cerco disperatamente aiuto

    L ho aggiustata come dicevi tu... ho fatto vari test..sembra funzionare bene ...grazie:):):)

    /////////////////////////////////////////

    int Ricerca(int A[MAX],int el,int i,int Arraysize)
    {
    if (i<ArraySize/2) /* non e una foglia*/
    {
    if (A==el) return i;
    else

    if ((el<=A[2*i+1]) && (el<=A[2*i+2])) /*controllo su entrambi i figli*/
    {
    int risultato=(Ricerca(A,el,(2*i+1),Arraysize));
    if (risultato==-1)
    risultato=(Ricerca(A,el,(2*i+2),Arraysize));

    return risultato ;


    }
    else
    if (el<=A[2*i+1]) return Ricerca(A,el,(2*i+1),Arraysize);
    else
    if (el<=A[2*i+2]) return Ricerca(A,el,(2*i+2),Arraysize);
    else
    return -1;
    }
    else /* e una foglia*/
    if (A==el)
    return i;
    else return -1;
Devi accedere o registrarti per scrivere nel forum
3 risposte