Ragazzi ho un dubbio atroce, spero qualcuno mi sappia dare una risposta esaustiva. Allora ho realizzato un programma che gestisce la coda a priorità e cioè un heap implementandolo con un array. Come guarderete stesso voi nella libreria heap ho realizzato le funzioni costruisci_heap e heapify dichiarandole di tipo void. Adesso il mio dubbio è proprio su questo, dato che heapify innanzitutto è ricorsiva come funzione e inoltre modifica il vettore puntato dal campo first presente nella struttura heap, è corretto fare in questo modo ? O il ritorno di queste due funzioni deve essere un puntatore alla struttura heap ? e cioè sosituire void heapify(----) con heap *heapify(----) ???
Come codice vi posto solo parte interessata al mio dubbio. Credo che basti per farvi capire.
main.c
codice:
int main(){
srand(time(NULL));
elem *vet,*m,*val;
heap *A;
int n,i,tipo,scelta,pos;
void *inf;
funzioni *funz;
A=(heap *)malloc(sizeof(heap));
A->size=0;
printf("\n SCEGLIERE IL TIPO DI ALBERO SU CUI VOLER OPERARE ");
printf("\n\n (1) Interi");
printf("\n (2) Float");
printf("\n (3) Stringhe");
printf("\n (4) Persone\n");
printf("\n Tasto digitato : ");
scanf("%d", &tipo);
getchar();
switch(tipo){
case 1 : {
funz=Init_funzioni_interi();
break;
}
case 2 : {
funz=Init_funzioni_float();
break;
}
case 3 : {
funz=Init_funzioni_char();
break;
}
case 4 : {
funz=Init_funzioni_pers();
break;
}
}
system("cls");
printf("\n\n COME REALIZZARE L'HEAP ");
printf("\n (1) Inserisci un vettore di valori ");
printf("\n (2) Inserisci un solo elemento ");
printf("\n\n Tasto digitato : ");
scanf("%d",&scelta);
getchar();
switch(scelta){
case 1 :{
insert_vet(A,funz);
break;
}
case 2 : {
val=(elem *)malloc(sizeof(elem));
val->prior=random(0,30);
val->dato=funz->input();
A->buf=1;
A->first=(elem *)malloc(sizeof(elem));
(A->first)->dato=val->dato;
(A->first)->prior=val->prior;
A->size++;
break;
}
}
do {
system("cls");
printf("\n\n Scegliere il tipo di operazione da effettuare ");
printf("\n (1) Inserire un nuovo elemento ");
printf("\n (2) Stampa il valore massimo della coda a priorita' ");
printf("\n (3) Estrai il valore massimo della coda a priorita' ");
printf("\n (4) Stampa il contenuto della coda a priorita' ");
printf("\n (5) Cancella un elemento dalla coda a priorita' ");
printf("\n (0) Esci dall'esecuzione del programma ");
printf("\n\n Tasto digitato : ");
scanf("%d",&scelta);
getchar();
switch(scelta){
case 1 : {
val=(elem *)malloc(sizeof(elem));
printf("\n\n Inserisci elemento da inserire \n");
printf("\n Priorita' : ");
scanf("%d",&(val->prior));
getchar();
printf(" Dato : ");
val->dato=funz->input();
if((A->size)>=(A->buf)){
A->buf=(A->buf)*2;
A->first=(elem *)realloc(A->first,A->buf*sizeof(elem));
}
insert_key(A,val);
break;
}
case 2 : {
m=max(A);
printf("\n\n Elemento massimo : ");
printf(" Dato= ");
funz->output(m->dato);
printf(" Priorita'= ");
printf("%d",m->prior);
break;
}
case 3 : {
m=estrai_max(A);
printf("\n\n Elemento estratto : ");
printf(" Dato= ");
funz->output(m->dato);
printf(" Priorita'= ");
printf("%d",m->prior);
break;
}
case 4 : {
for(i=0;i<(A->size);i++){
printf("\n\n A[%d] Priorita': %d ",i,(A->first+i)->prior);
printf(" Dato: ");
funz->output((A->first+i)->dato);
}
break;
}
case 5 : {
printf("\n\n Inserisci elemento da cancellare \n");
printf("\n Dato : ");
inf=funz->input();
getchar();
do{
pos=search(A,inf,funz);
if(pos==-1)
printf("\n\n L'elemento da te richiesto non esiste nella coda ");
else
del_heap(A,pos);
}while(pos!=-1);
break;
}
}
printf("\n\n");
system("PAUSE");
}while(scelta!=0);
free(A);
return 0;
}
Heap.c
codice:
#include<stdio.h>
#include<stdlib.h>
#include"heap.h"
int left(int i){
if(i==0)
return 1;
else
return (2*i)+1;
}
int right(int i){
if(i==0)
return 2;
else
return (2*i)+2;
}
int padre(int i){
if(i==0)
return 0;
else if((i%2)==0)
return (i/2)-1;
else
return (i/2);
}
void heapify(heap *A, int i){
int l,r,max;
l=left(i);
r=right(i);
if((l<(A->size)) && ((A->first+l)->prior>(A->first+i)->prior))
max=l;
else
max=i;
if((r<(A->size)) && ((A->first+r)->prior>(A->first+max)->prior))
max=r;
if(max!=i){
swap(A->first+max,A->first+i);
heapify(A,max);
}
return;
}
elem *max(heap *A){
if((A->size)<1){
printf("\n\n Error : Non ci sono elementi nell'array \n\n");
return NULL;
}
else
return A->first;
}
elem *estrai_max(heap *A){
elem *max=NULL;
max=(elem *)malloc(sizeof(elem));
if((A->size)<1)
printf("\n\n Error : Non ci sono elementi nell'array \n\n");
max->dato=(A->first)->dato;
max->prior=(A->first)->prior;
(A->first)->dato=(A->first+(A->size-1))->dato;
(A->first)->prior=(A->first+(A->size-1))->prior;
A->size--;
heapify(A,0);
return max;
}
void costruisci_heap(heap *A){
int i,n;
n=A->size;
for(i=((n-1)/2);i>=0;i--)
heapify(A,i);
return;
}
int search(heap *A, void *val,funzioni *funz){
int i,pos=0;
i=(A->size)-1;
while((funz->confronto((A->first+i)->dato,val)!=0) && (i>=0))
i--;
if(i>-1)
pos=i;
else
pos=-1;
return pos;
}
void del_heap(heap *A,int i){
//(A->first+i)->dato=(A->first+(A->size-1))->dato;
//(A->first+i)->prior=(A->first+(A->size-1))->prior;
if(((A->first+(A->size-1))->prior)>((A->first+i)->prior))
increase_key(A,i,(A->first+(A->size-1)));
else
decrease_key(A,i,(A->first+(A->size-1)));
A->size--;
return;
}
void increase_key(heap *A, int i,elem *val){
if(val->prior<((A->first+i)->prior))
printf("\n\n ERROR : Nuova chiave piu' piccola ");
else{
(A->first+i)->dato=val->dato;
(A->first+i)->prior=val->prior;
while((i>0) && ((A->first+padre(i))->prior<((A->first+i)->prior))){
swap(A->first+1,A->first+padre(i));
i=padre(i);
}
}
return;
}
void decrease_key(heap *A,int i,elem *val){
if(val->prior>((A->first+i)->prior))
printf("\n\n ERROR : Nuova chiave piu' grande ");
else{
(A->first+i)->dato=val->dato;
(A->first+i)->prior=val->prior;
heapify(A,i);
}
return;
}
void insert_vet(heap *A,funzioni *funz){
elem *vet;
int n,i;
void *inf;
printf("\n\n Digita il numero di elementi che vuoi inserire : ");
scanf("%d",&n);
getchar();
vet=(elem *)malloc(n*sizeof(elem));
for(i=0;i<n;i++){
(vet+i)->prior=random(0,30);
printf("\n\n Inserisci Dato %d : ",i);
inf=funz->input();
(vet+i)->dato=inf;
}
A->first=vet;
A->size=n;
A->buf=n;
costruisci_heap(A);
return;
}
void insert_key(heap *A,elem *val){
A->size++;
(A->first+(A->size-1))->prior=-32700;
increase_key(A,(A->size-1),val);
return;
}
void swap(elem *a, elem *b){
elem *app=(elem *)malloc(sizeof(elem));
app->prior=a->prior;
app->dato=a->dato;
a->prior=b->prior;
a->dato=b->dato;
b->prior=app->prior;
b->dato=app->dato;
free(app);
return;
}