c aiuto heap

Tony Hak · 05-10-2007, 17:51

ciao .
Ho il seguente problema...
inserisco una serie di numeri in un array la cui dimensione la stabilisco io. Dopo di che da questo Array mi creo un Heap binario. Vado a cercare nell'array modificato come fosse un heap l'elemento che voglio cancellare. Se esiste allora lo cancello andando a sostituire l'elemento stesso con l'ultimo elemento dell'array e ridimensionando l'arraysize (arraysize -= 1). Quindi ordino gli elementi con l'heapsort e stampo i numeri contenuti tranne naturalmente l'ultimo elemento che è quello individuato e cancellato..ma ..la funzione per cancellare nn funziona.. dove sbaglio ? sono nuovo in C e nn riesco ancora ad entrare nella logica. Potete aiutarmi anche magari dandomi delle dritte su questo programma ? grazie mille ..

codice

#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int arraysize,heapsize,tot;
int left(int i)
{
return 2*i+1;
}

int right(int i)
{
return 2*i+2;
}

int p(int i)
{
return (i-1)/2;
}

void swap(int A[MAX], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}

void heapfy (int A[MAX], int i);
void buildheap(int A[MAX]);
int ricerca (int A[MAX],int el);
void cancella (int A[MAX],int ind);
void heapsort(int A[MAX]);

void heapfy(int A[MAX], int i)
{
int l,r,largest;
l=left(i);
r=right(i);
if (l<heapsize && A[l]>A[i])
largest=l;
else
largest=i;
if (r<heapsize && A[r] > A[largest])
largest=r;
if (largest != i )
{
swap (A,i,largest);
heapfy(A,largest);
}
}

void buildheap(int A[MAX])
{
int i,el;
heapsize=arraysize;
for (i=arraysize/2;i>=0;i--)
heapfy(A,i);
printf("\n inserisci l'elemento da cancellare: ");
scanf ("%d",&el);
ricerca(A,el);

}

int ricerca (int A[MAX],int el)
{
int i,x ;
i=x=0;
while ((i<= MAX) && (x=0))
{
if (el <= A[i])
{
if (A[i] = el)
{
cancella (A,i);
x=1;
}
else
i+=1;
}
else
x=1;
}
}

void cancella (int A[MAX],int ind)
{

swap (A,ind,arraysize);
arraysize -=1;

}

void heapsort(int A[MAX])
{
int i;
buildheap(A);
for (i=arraysize-1;i>=1; i--)
{
swap (A,0,i);
heapsize--;
heapfy(A,0);
}
}

main()
{
int A[MAX],k;
printf("\n quanti elementi deve contenere l'array?");
scanf("%d",&tot);
while (tot>MAX)
{
printf("\n max 20 elementi: ");
scanf ("%d",&tot);
}
for (k=0; k<tot; k++)
{
printf("\n inserire il %d° elemento: ",k+1);
scanf("%d",&A[k]);
}
heapsize=arraysize=tot;

heapsort(A);
printf("\n array ordinato:");
for (k=0;k<arraysize;k++)
printf("%d",A[k]);
scanf("%d");
system ("\n pause");
}

marko.fatto · 05-10-2007, 20:34

Ti dispiacerebbe utilizzare i tag code?

Sarebbe molto più leggibile...

Tony Hak · 05-10-2007, 20:41

Quote:

Originariamente inviato da marko.fatto

Ti dispiacerebbe utilizzare i tag code?

Sarebbe molto più leggibile...

cos'e' il tag code ?cosi' ? (vedi allegato)

marko.fatto · 05-10-2007, 20:46

Basta scrivere il codice all'interno di {CODE}{/CODE} (con le parentesi quadre al posto delle graffe)
Es:

Codice:

questo è del codice

Tony Hak · 05-10-2007, 20:57

guarda ci ho provato ma nn va

.. .cmq ti ho allegato il file ..

.. grazie della pazienza..ora pero' devo staccare perche' sto avendo problemi di occhi rossi

.. grazie mille !

Tony Hak · 05-10-2007, 21:19

Codice:

#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int arraysize,heapsize,tot;
int left(int i) 
{
    return 2*i+1;
}

int right(int i) 
{
    return 2*i+2;
}

int p(int i) 
{
    return (i-1)/2;
}

void swap(int A[MAX], int i, int j)
     {
              int temp = A[i];
              A[i] = A[j];
              A[j] = temp;
     }

void heapfy (int A[MAX], int i);
void buildheap(int A[MAX]);
int ricerca (int A[MAX],int el);
void cancella (int A[MAX],int ind);
void heapsort(int A[MAX]);

void heapfy(int A[MAX], int i)
{
     int l,r,largest;
     l=left(i);
     r=right(i);
     if (l<heapsize && A[l]>A[i])
     largest=l;
     else
     largest=i;
     if (r<heapsize && A[r] > A[largest])
     largest=r;
     if (largest != i )
     {
                 swap (A,i,largest);
                 heapfy(A,largest);
     }
}


void buildheap(int A[MAX])
{
   int i,el;
   heapsize=arraysize;
   for (i=arraysize/2;i>=0;i--)
   heapfy(A,i);
   printf("\n inserisci l'elemento da cancellare: ");
      scanf ("%d",&el);
   ricerca(A,el);

}

int ricerca (int A[MAX],int el)
{
    int i,x ;
    i=x=0;
    while  ((i<= MAX) && (x=0))
    {
           if (el <= A[i])
           {
                  if (A[i] = el) 
                  {
                          cancella (A,i);
                          x=1;
                  }
                  else
                      i+=1;
           }
           else
               x=1;
    }
}

void cancella (int A[MAX],int ind)
{
   
   swap (A,ind,arraysize);
  arraysize -=1;

} 
           
    
    
    

void heapsort(int A[MAX])
{
     int i;
     buildheap(A);
     for (i=arraysize-1;i>=1; i--)
     {
         swap (A,0,i);
         heapsize--;
         heapfy(A,0);
     }
}

main()
{
      int A[MAX],k;
      printf("\n quanti elementi deve contenere l'array?");
      scanf("%d",&tot);
      while (tot>MAX)
            {
                     printf("\n max 20 elementi: ");
                     scanf ("%d",&tot);
            }
      for (k=0; k<tot; k++)
      {
          printf("\n inserire il %d° elemento: ",k+1);
          scanf("%d",&A[k]);
      }
      heapsize=arraysize=tot;
 
      heapsort(A);
      printf("\n array ordinato:");
      for (k=0;k<arraysize;k++)
      printf("%d",A[k]);
      scanf("%d");
      system ("\n pause");
}

ci sono riuscito

... mettevo le parentesi graffe ( ah ,la stanchezza hihi! )

marko.fatto · 05-10-2007, 21:38

Codice:

int ricerca (int A[MAX],int el)
{
    int i,x ;
    i=x=0;
    while  ((i<= MAX) && (x=0))
    {
           if (el <= A[i])
           {
                  if (A[i] = el) 
                  {
                          cancella (A,i);
                          x=1;
                  }
                  else
                      i+=1;
           }
           else
               x=1;
    }
}

Intanto due errori sono qui... nella condizione del while è x==0 e non x=0 ... Idem nell'if A[i]==el

Tony Hak · 05-10-2007, 22:38

ok .. dmn li correggo e provo a farlo girare...

.. il fatto è che ho sempre programmato in pascal :P

ps ... la x inzialmente doveva essere una flag booleana..ma nn so come si dichiara il tipo boolean in C .. .

marko.fatto · 05-10-2007, 22:52

Quote:

Originariamente inviato da Tony Hak

ps ... la x inzialmente doveva essere una flag booleana..ma nn so come si dichiara il tipo boolean in C .. .

in C semplicemente non c'è...

qwerty86 · 05-10-2007, 23:22

Quote:

Originariamente inviato da marko.fatto

in C semplicemente non c'è...

puoi ovviare dichiarando una variabile di tipo intero , e assegnarli 0 o 1, rispettivamente per False e True.

Tony Hak · 06-10-2007, 07:39

eheh .. come avevo pensato di fare...ua ma davvero nn si possono dichiarare boolean ? ...cacchio ! cmq ora provo il programma cambiando quelle cose ...

Tony Hak · 06-10-2007, 07:42

niente... nn va ... help

col dev c++ come posso vedere l'esecuzione del programma passo per passo ?

qwerty86 · 06-10-2007, 08:01

Quote:

Originariamente inviato da Tony Hak

niente... nn va ... help

col dev c++ come posso vedere l'esecuzione del programma passo per passo ?

Puoi utilizzare il metodo classico

, ossia utilizzare le printf per vedere cosa contengono le variabili.

Tony Hak · 06-10-2007, 08:04

Quote:

Originariamente inviato da qwerty86

Puoi utilizzare il metodo classico

, ossia utilizzare le printf per vedere cosa contengono le variabili.

giusto

è tutto molto "fai da te"

.. secondo me cmq l'errore è nella funzione cancella.. io scambio l'elemento trovato con l'ultimo elemento dell'array e pongo l'arraysize a arraysize-1 .

Tony Hak · 06-10-2007, 09:16

Codice:

#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int arraysize,heapsize,tot;
int left(int i) 
{
    return 2*i+1;
}

int right(int i) 
{
    return 2*i+2;
}

int p(int i) 
{
    return (i-1)/2;
}

void swap(int A[MAX], int i, int j)
     {
              int temp = A[i];
              printf ("A[i] = %d", A[i]);
              printf ("A[j] = %d", A[j]);
              A[i] = A[j];
              A[j] = temp;
     }

void heapfy (int A[MAX], int i);
void buildheap(int A[MAX]);
int ricerca (int A[MAX],int el);
void cancella (int A[MAX],int ind);
void heapsort(int A[MAX]);

void heapfy(int A[MAX], int i)
{
     int l,r,largest;
     l=left(i);
     r=right(i);
     if (l<heapsize && A[l]>A[i])
     largest=l;
     else
     largest=i;
     if (r<heapsize && A[r] > A[largest])
     largest=r;
     if (largest != i )
     {
                 swap (A,i,largest);
                 heapfy(A,largest);
     }
}


void buildheap(int A[MAX])
{
   int i,el;
   heapsize=arraysize;
   for (i=arraysize/2;i>=0;i--)
   heapfy(A,i);
   printf("\n inserisci l'elemento da cancellare: ");
      scanf ("%d",&el);
   ricerca(A,el);

}

int ricerca (int A[MAX],int el)
{
    int i,x ;
    i=x=0;
    while  ((i<= arraysize) && (x==0))
    {
           if (el <= A[i])
           {
                  if (A[i] == el) 
                  {
                          cancella (A,i);
                          
                          x=1;
                          return arraysize-=1;
                  }
                  else
                      i+=1;
           }
           else
               x=1;
    }
}

void cancella (int A[MAX],int ind)
{
   int k=0;
   swap (A,ind,arraysize);
   for (k=0;k<arraysize;k++)
      printf("%d",A[k]);

} 
           
    
    
    

void heapsort(int A[MAX])
{
     int i;
     buildheap(A);
     for (i=arraysize-1;i>=1; i--)
     {
         swap (A,0,i);
         heapsize--;
         heapfy(A,0);
     }
}

main()
{
      int A[MAX],k;
      printf("\n quanti elementi deve contenere l'array?");
      scanf("%d",&tot);
      while (tot>MAX)
            {
                     printf("\n max 20 elementi: ");
                     scanf ("%d",&tot);
            }
      for (k=0; k<tot; k++)
      {
          printf("\n inserire il %d° elemento: ",k+1);
          scanf("%d",&A[k]);
      }
      heapsize=arraysize=tot;
      printf ("l'arrayzizze e' %d",arraysize);
      heapsort(A);
      printf ("l'arrayzizze e' %d",arraysize);
      printf("\n array ordinato:");
      for (k=0;k<arraysize;k++)
      printf("%d",A[k]);
      scanf("%d");
      system ("\n pause");
}

ho modificato ancora il codice .. ma continua a nn fungere..stavolta l'arraysize -=1 l'ho messo nella procedura di ricerca..in quanto nel VOID nn mi restituiva il valore... help vi prego..sto perdendo la testa ...

ps i vari printf sono come test

rozpo · 06-10-2007, 09:57

sono il prof aniello murano
ti ho sgamato furbacchione!

Tony Hak · 06-10-2007, 10:10

Quote:

Originariamente inviato da rozpo

sono il prof aniello murano
ti ho sgamato furbacchione!

hihi .. nn sapevo che Lei avesse 22 anni

05-10-2007, 17:51	#1
Tony Hak Senior Member Iscritto dal: Jun 2005 Città: Napoli Messaggi: 1661	c aiuto heap ciao . Ho il seguente problema... inserisco una serie di numeri in un array la cui dimensione la stabilisco io. Dopo di che da questo Array mi creo un Heap binario. Vado a cercare nell'array modificato come fosse un heap l'elemento che voglio cancellare. Se esiste allora lo cancello andando a sostituire l'elemento stesso con l'ultimo elemento dell'array e ridimensionando l'arraysize (arraysize -= 1). Quindi ordino gli elementi con l'heapsort e stampo i numeri contenuti tranne naturalmente l'ultimo elemento che è quello individuato e cancellato..ma ..la funzione per cancellare nn funziona.. dove sbaglio ? sono nuovo in C e nn riesco ancora ad entrare nella logica. Potete aiutarmi anche magari dandomi delle dritte su questo programma ? grazie mille .. codice #include <stdio.h> #include <stdlib.h> #define MAX 20 int arraysize,heapsize,tot; int left(int i) { return 2i+1; } int right(int i) { return 2i+2; } int p(int i) { return (i-1)/2; } void swap(int A[MAX], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } void heapfy (int A[MAX], int i); void buildheap(int A[MAX]); int ricerca (int A[MAX],int el); void cancella (int A[MAX],int ind); void heapsort(int A[MAX]); void heapfy(int A[MAX], int i) { int l,r,largest; l=left(i); r=right(i); if (l<heapsize && A[l]>A[i]) largest=l; else largest=i; if (r<heapsize && A[r] > A[largest]) largest=r; if (largest != i ) { swap (A,i,largest); heapfy(A,largest); } } void buildheap(int A[MAX]) { int i,el; heapsize=arraysize; for (i=arraysize/2;i>=0;i--) heapfy(A,i); printf("\n inserisci l'elemento da cancellare: "); scanf ("%d",&el); ricerca(A,el); } int ricerca (int A[MAX],int el) { int i,x ; i=x=0; while ((i<= MAX) && (x=0)) { if (el <= A[i]) { if (A[i] = el) { cancella (A,i); x=1; } else i+=1; } else x=1; } } void cancella (int A[MAX],int ind) { swap (A,ind,arraysize); arraysize -=1; } void heapsort(int A[MAX]) { int i; buildheap(A); for (i=arraysize-1;i>=1; i--) { swap (A,0,i); heapsize--; heapfy(A,0); } } main() { int A[MAX],k; printf("\n quanti elementi deve contenere l'array?"); scanf("%d",&tot); while (tot>MAX) { printf("\n max 20 elementi: "); scanf ("%d",&tot); } for (k=0; k<tot; k++) { printf("\n inserire il %d° elemento: ",k+1); scanf("%d",&A[k]); } heapsize=arraysize=tot; heapsort(A); printf("\n array ordinato:"); for (k=0;k<arraysize;k++) printf("%d",A[k]); scanf("%d"); system ("\n pause"); } __________________

05-10-2007, 20:34	#2
marko.fatto Senior Member Iscritto dal: Jul 2007 Messaggi: 499	Ti dispiacerebbe utilizzare i tag code? Sarebbe molto più leggibile... __________________

05-10-2007, 20:46	#4
marko.fatto Senior Member Iscritto dal: Jul 2007 Messaggi: 499	Basta scrivere il codice all'interno di {CODE}{/CODE} (con le parentesi quadre al posto delle graffe) Es: Codice: questo è del codice __________________

05-10-2007, 20:57	#5
Tony Hak Senior Member Iscritto dal: Jun 2005 Città: Napoli Messaggi: 1661	guarda ci ho provato ma nn va .. .cmq ti ho allegato il file .. .. grazie della pazienza..ora pero' devo staccare perche' sto avendo problemi di occhi rossi .. grazie mille ! __________________ Ultima modifica di Tony Hak : 05-10-2007 alle 21:03.

05-10-2007, 21:38	#7
marko.fatto Senior Member Iscritto dal: Jul 2007 Messaggi: 499	Codice: int ricerca (int A[MAX],int el) { int i,x ; i=x=0; while ((i<= MAX) && (x=0)) { if (el <= A[i]) { if (A[i] = el) { cancella (A,i); x=1; } else i+=1; } else x=1; } } Intanto due errori sono qui... nella condizione del while è x==0 e non x=0 ... Idem nell'if A[i]==el __________________

05-10-2007, 22:38	#8
Tony Hak Senior Member Iscritto dal: Jun 2005 Città: Napoli Messaggi: 1661	ok .. dmn li correggo e provo a farlo girare... .. il fatto è che ho sempre programmato in pascal :P ps ... la x inzialmente doveva essere una flag booleana..ma nn so come si dichiara il tipo boolean in C .. . __________________

06-10-2007, 07:39	#11
Tony Hak Senior Member Iscritto dal: Jun 2005 Città: Napoli Messaggi: 1661	eheh .. come avevo pensato di fare...ua ma davvero nn si possono dichiarare boolean ? ...cacchio ! cmq ora provo il programma cambiando quelle cose ... __________________

06-10-2007, 07:42	#12
Tony Hak Senior Member Iscritto dal: Jun 2005 Città: Napoli Messaggi: 1661	niente... nn va ... help col dev c++ come posso vedere l'esecuzione del programma passo per passo ? __________________ Ultima modifica di Tony Hak : 06-10-2007 alle 07:45.

06-10-2007, 09:57	#16
rozpo Senior Member Iscritto dal: Feb 2006 Città: Villa di Briano (CE) Messaggi: 408	sono il prof aniello murano ti ho sgamato furbacchione! __________________ Ho acquistato da: battalion75, [Riot]-kyashan, Tedio, silentmodena, dorcon, Damianoo, lantony, evl, max7_4, elpampa19, fa, Sclergio, maui_, Vastx, no_side_fx, jokervero e... dimentico sempre qualcuno. Ho venduto a TNOTB, Ryujimihira, marcus24 e schumyFast per ora.

Strumenti
Mostra una versione stampabile Invia questa pagina per email