PDA

Visualizza la versione completa : [C] Algoritmo di ordinamento "heapsort"


seatleon
05-07-2010, 17:26
Salve a tutti,
ho il seguente codice:



#include <stdio.h>
#define MAX 20

int sinistro(int i)
{
return 2*i+1;
}

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

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

stampavettore(int *vettore,int n)
{
int i;

for(i=0 ; i<=n ;
printf("%d ",vettore[i++]));
}

int riempivettore(int *vettore)
{
int i;

i=0;
do {
printf("%d\n", i);
printf("inserire l'elemento %d dell'array('-1' per terminare): ",i+1);
scanf("%d",vettore+i);
stampavettore(vettore,i);
printf("\n");
} while (vettore[i++] != -1);
return i-2;
}

void scambia(int *n1,int *n2)
{
int temp;

temp = *n1;
*n1 = *n2;
*n2 = temp;
}

void heapify(int *vettore, int i,int heapsize)
{
int l,r,maggiore;

l = sinistro(i);

r = destro(i);

if ((l <= heapsize) && (vettore[l] > vettore[i]))
{
maggiore = l;
}
else
{
maggiore = i;
}

if ((r <= heapsize) && (vettore[r]>vettore[maggiore]))
{
maggiore = r;
}
if (maggiore != i)
{
scambia(&vettore[i],&vettore[maggiore]);
heapify(vettore,maggiore,heapsize);
}
}



void buildheap(int *vettore,int heapsize,int n)
{
int i;

for (i=(int)(n/2) ; i>=0 ; i--)
{
heapify(vettore,i,heapsize);
}
}


heapsort(int *vettore,int n)
{

int i,heapsize;

heapsize=n;

buildheap(vettore,heapsize,n);
for (i=n ; i>0 ; i--)
{
scambia(&vettore[0],&vettore[i]);
heapsize--;
heapify(vettore,0,heapsize);
}
}

main()
{
int vettore[MAX];
int n; /*numero di elementi*/

n=riempivettore(vettore);

printf("Valore di n %d\n", n);

heapsort(vettore,n);

stampavettore(vettore,n);

}


non riesco a capire perchè in questa funzione:

void buildheap(int *vettore,int heapsize,int n)

vengono passati i valori heapsize ed n, che sono sempre uguali.

Credo che ci sarà un motivo, grazie a chiunque mi vuol dare una mano.

Ciao

simo_us
05-07-2010, 17:59
int foo(int *var1, int *var2, int *var3)
{
...
}

int main(void)
{
int var, var1, var2;

foo(&var1, &var2 &var3)

....
}

PS: il codice fra i tag code.. Regolamento del forum sezione nº 6.

seatleon
05-07-2010, 23:39
Chiedo scusa,
se gli amministratori possono correggere, visto che non posso modificare.
Grazie

simo_us
06-07-2010, 00:38
Beh ma hai capito come correggere il piccolo "errore"? :ciauz:

seatleon
06-07-2010, 09:37
Buon giorno a tutti,

non riesco a capire simo_us,
ho notato che se correggo la dichirazione della funzione buildheap, passando un solo parametro,
il programma funziona in modo corretto.

:master:

Ippo343
06-07-2010, 11:22
Uhm a me questa non sembra giusta:



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


Tu casti a int il valore [i - (1/2)], mentre se non sbaglio dovrebbe essere [(i - 1) / 2], no?
Infatti hai bisogno di mettere un cast esplicito, mentre [(i - 1) / 2] ritorna un int senza nessun cast...

infotechproximi
06-07-2010, 11:46
Un breve articolo per rendere disponibile a voi il materiale sviluppato per l’esame di Algoritmi e Strutture Dati. Esso consiste nell’implementazione (in linguaggio C) dei tre algoritmi di ordinamento, Counting, Bucket e Heap Sort. Inoltre nella relazione sono state analizzate le prestazioni dei tre algoritmi ed è stata effettuata un’analisi comparativa.

Il materiale è stato sviluppato in gruppo da me e i miei colleghi Vincenzo Ciriello e Vincenzo Di Paolo (il bragol che scrive di tanto in tanto anche sul mio blog).

<cut by mod>

alka
06-07-2010, 12:38
Originariamente inviato da infotechproximi
Un breve articolo per rendere disponibile a voi il materiale sviluppato per l’esame di Algoritmi e Strutture Dati. [...]

No SPAM, grazie...

simo_us
06-07-2010, 16:32
Quello che brevemente ho notato io è che tu dichiari la funzione es

void buildheap(int *vettore,int heapsize,int n)ma la richiami cosi

buildheap(vettore,heapsize,n)
non così, che mi sembrerebbe piú corretto
buildheap(&vettore,heapsize,n)perchè tu dicevi che i valori non cambiano...

Loading