smalldragon ha scritto:
posta la main
Eccoti l'intero programma =)
#include<iostream>
using namespace std;
typedef struct S *stackL;
typedef struct S
{
int low;
int up;
int visite;
stackL link;
}
stack;
void Push (stackL &head, int low, int up, int vis);
void Pop (stackL &head, int *low, int *up, int *vis);
void MergeSort (float *A, int low, int up);
void Merge (float *A,int low,int mid,int up);
int main(){
float *a;
int n, i;
cout<< "Inserire dimensione array: ";
cin>> n;
a=new float[n];
for (i=0; i<n;i++){
cout<<"Inserire "<<i+1<<"° valore dell'array: ";
cin>>a[i];
}
MergeSort(a,0,n-1);
cout<<"L'array ordinato è: ";
for (i=0; i<n ; i++)
cout<< a[i] << " " ;
cout<<endl;
delete [] a;
system("pause");
return 0;
}
void MergeSort (float *A, int low, int up){
stackL head;
int vis;
head=new stack;
// Inserire dimensione totale dell'array (0...n).
Push(head, low, up, 0);
// Ripetere il ciclo fin quando lo stack non è vuoto.
while (head!=NULL){
Pop (head, &low, &up, &vis);
Push (head, low, up, vis+1);
int mid=(low+up)/2;
//Se la dimensione dell'array è 1 eliminare l'ultimo pezzo di stack.
if(low>=up)
Pop(head, &low, &mid, &vis);
//Se è la 1° volta che si prende in considerazione la porzione di array, si crea un nuovo pezzo di stack con la sua parte sx.
else if (vis==0)
Push(head, low, mid, 0);
//Se è la 2° volta che si prende in considerazione la porzione di array, si crea un nuovo pezzo di stack con la sua parte dx.
else if(vis==1)
Push(head, mid+1, up, 0);
//Se la parte di array è già stata divisi in 2 porzioni, la si mette in ordine e la si elimina.
else{
Merge(A, low, mid, up);
Pop(head, &low, &up, &vis);
}
}
delete head;
}
void Merge (float *A,int low,int mid,int up){
float *B;
int f, newlow=0, newup=(up-low+1), c=0, newmid=(newup+newlow)/2;
B= new float[newup];
for(f=low;f<=up;f++){
B[c]=A[f];
c++;
}
int i=0, k=low, j=newmid;
while (i<newmid && j<newup){
if(B[i]<B[j]){
A[k]=B[i];
i++;
}
else{
A[k]=B[j];
j++;
}
k++;
}
if (i>=newmid)
for (f=j;f<newup;f++){
A[k]=B[f];
k++;
}
else
for (f=i;f<newmid;f++){
A[k]=B[f];
k++;
}
delete [] B;
}
void Push (stackL &head, int low, int up, int vis){
stackL app;
app= new stack;
app->low=low;
app->up=up;
app->visite=vis;
app->link=new stack;
app->link=head;
head=app;
}
void Pop (stackL &head, int *low, int *up, int *vis){
if(head!=NULL){
stackL app=head->link;
*low=head->low;
*up=head->up;
*vis=head->visite;
delete head;
head=app;
}
}