ho provato ha impelntarlo nel seguente modo:
hea.h
hea.cppcodice:typedef int A[]; //length=(int)(sizeof(A[]); //size=length-1; int parent(int i); int left(int i); int right(int i); /* int PARENT(int i); int LEFT(int i); int RIGHT(int i); */ void Scambia(int Heap, int ind1, int ind2); void MinHEAPIFY(int Heap, int i,int heapsize_A); int HEAP_estrai_min(int A[],int l); void min_heap_insert(int A[], int key,int heapsize_A); void Diminuisci_chiave(int A[],int i,int k); void Build_Min_HEAP(int A[],int l); int MINIMUM(int A[]);
codice:#include "hea.h" #include <stdlib.h> #include <iostream> using namespace std; int NumElementi_Array(int A[]){ return (sizeof(A)/sizeof(A[0])); } int NumElementi_Heap(int A[]){ return NumElementi_Array( A) -1; } //cout<<"Numero di elementi dell'array: " NumElementi()); int length_array(int A[]){ NumElementi_Array( A); } int size_heap(int A[]){ NumElementi_Heap( A); } int length(int A[]){ return sizeof A; } int heapsize(int A[]){ return length(A) - 1; } int length_A; int heapsiza_A; int parent(int i){ return i/2; } int left(int i){ return 2*i; } int right(int i){ return 2*i+1;} void scambia(int HEAP[], int ind1, int ind2){ int appo; appo = HEAP[ind1]; HEAP[ind1]=HEAP[ind2]; HEAP[ind2]=appo; } void MinHEAPIFY(int HEAP[], int i,int heapsize_A){ int smallest; int l = left(i); int r = right(i); if ((l <= heapsize_A) && (HEAP[l] < HEAP[i])) smallest = l; else smallest = i; if ((r <= heapsize_A) && (HEAP[r] < HEAP[smallest])) smallest = r; if (smallest != i) { scambia(HEAP,i,smallest); MinHEAPIFY(HEAP,smallest,heapsize_A); } } int HEAP_estrai_min(int A[],int l){ int min; int length_A=l; int heapsize_A=length_A-1; if (heapsize_A < 1){ fprintf(stderr,"heap underflow\n"); exit(1); } min = A[1]; A[1] = A[heapsize_A]; heapsize_A = (heapsize_A-1); // size_heap(A)=size; MinHEAPIFY(A, 1,heapsize_A); return min; } void min_heap_insert(int A[], int key,int heapsize_A){ //int length_A=l; //int heapsize_A=0; heapsize_A = (heapsize_A+1); //cout<< " heapsize : "<< length_A << " \n"; cout<< " heapsize : "<< heapsize_A << " \n"; system("PAUSE"); //size_heap(A)=size; A[(heapsize_A-1)]=INT_MAX; Diminuisci_chiave(A,heapsize_A-1, key); } int MINIMUM(int A[]) { return A[1]; } void Diminuisci_chiave(int A[],int i,int k) { if(k > A[i]){ fprintf(stderr, "la nuova chiave è più grande di quella corrente.\n"); exit(1); } A[i] = k; while ((i > 1) && (A[parent(i)] > A[i])){ scambia (A,i,parent(i)); i = parent(i); } //return i; } void Build_Min_HEAP(int A[],int l){ int i; int length_A=l; int heapsize_A=length_A; //size=length_array(A); // size_heap(A)=size; for (i =(length_A/2);i>0;i--) cout<<"heapsize è: " << heapsize_A; system("PAUSE"); MinHEAPIFY(A, i,heapsize_A); } void HEAP_SORT(int A[],int l) { int i; int length_A=l; int heapsize_A=length_A-1; Build_Min_HEAP(A,l); for(i=length_A;i>1;i--) { scambia(A,1,i); heapsize_A =( heapsize_A-1); // size_heap(A) = size; MinHEAPIFY(A,1,heapsize_A); } }
main.cpp
nn mi da errori in fase di compilazionecodice:#include "hea.h" #include <iostream> #include <stdlib.h> #include <ctime> #include <cstdlib> using namespace std; int main() { int* found=NULL; time_t t1,t2; clock_t clk1,clk2; double media=0; int dim; int l; int scelta; int k; int length_A,heapsize_A; do{ cout<<"\n SCEGLI LA FUNZIONE DI CUI VUOI TESTARE LA COMPLESSITA'"; cout<<"\n digita 1 per INSERT"; cout<<"\n digita 2 per SEARCH_min "; cout<<"\n digita 3 per SEARCH_min "; cout<<"\n digita 4 per uscire dal programma"; cout<<"\n ->"; cin>>scelta; switch(scelta){ case 1: cout<<"\n TEST INSERT"; cout<<"\n test di complessita' "; cout<<"\n inserisci la dimensione dell'input ->"; cin>>l; length_A=l; heapsize_A=length_A-1; int H[length_A]; //Build_Min_HEAP( H); media=0; cout<<"\n"; for(int h=0;h<10;h++){ //Crea il vettore di l elementi for (int i=0;i<l;i++){ //x=new heap_element; //x->key=rand(); H[i]=rand(); cout<< " la nuova chiave : "<< H[i] << " \n"; cout<< " la vecchia chiave : "<< H[i-1] << " \n"; if(i==0) { clk1 = clock(); } min_heap_insert(H, H[i],heapsize_A); } clk2 = clock(); cout<<"tempo della "<<h+1<<" prova: "; double tempo_trascorso = (double)(clk2-clk1)/CLOCKS_PER_SEC; cout<<tempo_trascorso; cout<<"\n"; media=media+tempo_trascorso; } cout<<"\n media dei tempi -> "<<media/10<<"\n\n"; cout<<"\n\n"; break; case 2: cout<<"\n TEST Build_min_heap"; cout<<"\n test di complessita' "; cout<<"\n inserisci la dimensione dell'input ->"; cin>>l; length_A=l; heapsize_A=length_A-1; H[length_A]; //Crea il vettore di l elementi for (int i=0;i<l;i++){ H[i]=rand(); cout<< " la nuova chiave : "<< H[i] << " \n"; cout<< " la vecchia chiave : "<< H[i-1] << " \n"; system("PAUSE"); } // media=0; cout<<"\n"; // for(int h=0;h<10;h++){ clk1 = clock(); Build_Min_HEAP( H,l); //HEAP_SORT( H); clk2 = clock(); // cout<<"tempo della "<<h+1<<" prova: "; cout<<"tempo della prova: "; double tempo_trascorso; tempo_trascorso = (double)(clk2-clk1)/CLOCKS_PER_SEC; cout<<tempo_trascorso; cout<<"\n"; // media=media+tempo_trascorso; // } //cout<<"\n media dei tempi -> "<<media/10<<"\n\n"; cout<<"\n\n"; break; case 3: cout<<"\n TEST SEARCH_min"; cout<<"\n test di complessita' "; cout<<"\n inserisci la dimensione dell'input ->"; cin>>l; length_A=l; heapsize_A=length_A-1; H[length_A]; //Crea il vettore di l elementi for (int i=0;i<l;i++){ H[i]=rand(); // min_heap_insert(H, H->h[i].key); } Build_Min_HEAP( H,l); media=0; for(int h=0;h<10;h++){ clk1 = clock(); int min=MINIMUM(H); clk2 = clock(); cout<<"tempo della "<<h+1<<" prova: "; double tempo_trascorso = (double)(clk2-clk1)/CLOCKS_PER_SEC; cout<<tempo_trascorso; cout<<"\n"; media=media+tempo_trascorso; } cout<<"\n media dei tempi -> "<<media/10<<"\n\n"; cout<<"\n\n"; break; case 4: exit(0); break; } }while((scelta>0)&&(scelta<5)); cout<<"\n Errore di digitazione \n"; cout<<"\n\n\n\n\n"; system("PAUSE"); }
ma qnd mando in escuzione il programma e selezione uno dei test (per eseguirlo) nn riesco ad fare nulla pochè si kiude il programma (esce dal programma in esecuzione)
nn capisco cm mai
Rispondi quotando