c aiuto heap

[Tony Hak]

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]

Ti dispiacerebbe utilizzare i tag code?:stordita:
Sarebbe molto più leggibile...

[Tony Hak]

Ti dispiacerebbe utilizzare i tag code?:stordita:
Sarebbe molto più leggibile...

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

[marko.fatto]

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

[Tony Hak]

guarda ci ho provato ma nn va :D .. .cmq ti ho allegato il file .. :) .. grazie della pazienza..ora pero' devo staccare perche' sto avendo problemi di occhi rossi :) .. grazie mille !

[Tony Hak]

#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 :D :D :D ... mettevo le parentesi graffe ( ah ,la stanchezza hihi! )

[marko.fatto]

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]

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]

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'è...:D

[qwerty86]

in C semplicemente non c'è...:D

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

[Tony Hak]

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]

niente... nn va ... help :( col dev c++ come posso vedere l'esecuzione del programma passo per passo ?

[qwerty86]

niente... nn va ... help :( col dev c++ come posso vedere l'esecuzione del programma passo per passo ?

Puoi utilizzare il metodo classico :D , ossia utilizzare le printf per vedere cosa contengono le variabili.

[Tony Hak]

Puoi utilizzare il metodo classico :D , ossia utilizzare le printf per vedere cosa contengono le variabili.


giusto :D è 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]

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

sono il prof aniello murano
ti ho sgamato furbacchione! :D :D :D

[Tony Hak]

sono il prof aniello murano
ti ho sgamato furbacchione! :D :D :D

hihi .. nn sapevo che Lei avesse 22 anni :D