Corsi di Laurea

[Blackjack]

Implementazione di un heap basato su array, generico, con funzione di ordinamento heapsort generica (ho usato questo tag, e non l'altro, perchè dà un'anomalia sul newline)

void max_heapify(void *v, int size, int t_size, int j, int (* compare)(void*,void*))

{

     int k = j;

     

     if (2*j+2 < size && compare((v+(2*j+2)*t_size),(v+k*t_size)) > 0)

     {

               k = 2*j+2;

     }

     if (2*j+1 < size && compare((v+(2*j+1)*t_size),(v+k*t_size)) > 0)

     {

               k = 2*j+1;

     }

     if (k != j)

     {

        /*se il padre ha un figlio >, scambio padre e figlio max 

        e rieseguo ricorsivamente*/

        swap(v,j,k,t_size);

        max_heapify(v,size,t_size,k,compare);

     }

}



void max_heapifyR(void *v, int size, int t_size, int j, int (* compare)(void*,void*))

{

     int k;

     

     //CASO BASE 1: l'elemento è un elemento radice (j==0), l'algoritmo non fa niente

     if (j > 0)

     {

        k = j/2-1+j%2; //k = indice del nodo padre di j

        

        //CASO BASE 2: l'elemento è minore del padre (v[j] < v[k], l'algoritmo non fa niente)

        if (compare((v+j*t_size),(v+k*t_size)) > 0)

        {

           swap(v,j,k,t_size);

           max_heapifyR(v,size,t_size,k,compare);

        }

     }

}



void build_max_heap(void *v, int size, int t_size, int (* compare)(void*,void*))

{

     int i;

     

     for (i = size/2; i >= 0; i--)

     {

         max_heapify(v,size,t_size,i,compare);

     }

}



void heapsort(void *v, int size, int t_size, int (* compare)(void*,void*))

{

     int i;

     build_max_heap(v,size,t_size,compare);

     for (i = size-1; i >= 1; i--)

     {

         //swap tra prima e i-esima posizione

         swap(v,0,i,t_size);

         max_heapify(v,i,t_size,0,compare);

     } 

}



void swap (void* v, int i, int j, int t_size)

{

     char tmp; // byte di appoggio per lo swap

     int k;



     for (k = 0; k < t_size; k++)

     {

        tmp=*(char*)(v+i*t_size+k);

        *(char*)(v+i*t_size+k) = *(char*)(v+j*t_size+k);

        *(char*)(v+j*t_size+k)=tmp;

     }

}

Questo è del codice di test per l'heapsort:

struct ciao

{

       int key;

       int value;

};

typedef struct ciao TCiao;



void show(TCiao*,int);

int compare(TCiao *a, TCiao *b);



int main()

{

    TCiao* v;

    int DIM = 12;

    v = malloc(sizeof(TCiao)*DIM);

    v[0].key = 112; v[1].key = 213; v[2].key = 67; v[3].key = 18; v[4].key = 178; v[5].key = 202; 

    v[6].key = 139; v[7].key = 55; v[8].key = 345; v[9].key = 312; v[10].key = 3; v[11].key = 144;

    

    printf("vettore originale:\n");

    show(v,DIM);

    

    heapsort(v,DIM,sizeof(TCiao),compare);

    

    printf("\n\nvettore ordinato:\n");

    show(v,DIM);

    free(v);

    system("PAUSE");

    return 0;

}



void show(TCiao *v,int size)

{

    int i;

    for (i=0; i
        printf("V[%d].key = %d\n", i, v[i].key);

}



int compare(TCiao *a, TCiao *b)

{

    //printf("a: %d b: %d",a.key,b.key);

    if (a->key > b->key)

       return 1;

    else if (a->key < b->key)

       return -1;

    else

       return 0;

}