[c] Programma mergesort ricorsivo

[Anna87_m]

Ciao...Qualcuno sa speigarmi che cosa fa questo programma che ha fatto un mio professore e che a mio parere non va neanche?

#include <stdio.h>
#include <stdlib.h>
#define DIM  6
#define DIMT 7
typedef struct {long key; 
                char qc[9]; 
                long link; } ELE;
typedef ELE VET[DIMT];

ELE elPos(VET X, int pos, ELE dum)
 {
     if(pos != -2)
      return X[pos];
     else
      return dum; 
 }

void Scrivi(VET X, ELE el, int pos, ELE *dm)
{
     if (pos != -2)
       X[pos] = el;
     else
       *dm = el;  
 }


long RMERGE (VET X, long Sx, long Dx)
{  long i,j,z,d;
   ELE dum, ELi, ELj, ELz;
   
   d = -2; dum.link=-1;
   i = Sx; j = Dx; z = d;
   while (i != -1 && j != -1)
     { ELi = elPos(X,i,dum); ELj = elPos(X,j,dum);
     
       if(ELi.key <= ELj.key)
       { ELz = elPos(X,z,dum);
         ELz.link = i;  Scrivi(X, ELz, z, &dum); 
         z=i; i=ELi.link;}
       else 
       { ELz = elPos(X,z,dum);
         ELz.link = j; Scrivi(X, ELz, z, &dum); 
         z=j; j=ELj.link;}
     }
     
  if (i==-1)  ELz.link = j;
  else   ELz.link = i;
  Scrivi(X, ELz, z,&dum);
  return dum.link;
}


long RMSORT (VET X,long l,long u)
{  long meta,Sx, Dx,P;

   if (l >= u )  P = l;
   else { meta = (l+u)/2;
           Sx = RMSORT(X,l,meta);
           Dx = RMSORT(X,meta+1,u);
           P =  RMERGE(X,Sx,Dx);}
   return P;
}

int main()
{
    VET v={{8,"",-1},{16,"",-1},{-3,"",-1},
           {36,"",-1}, {27,"",-1},{36,"",-1}};
    long testa,i;
    
    testa = RMSORT(v,0,DIM-1);
    
    for(i=testa; i!=-1; )
      {
       printf("K=%ld L=%ld\n",v[i].key, v[i].link);
       i = v[i].link;
      }
    system("pause");return 0;       
}

[Stoicenko]

l'hai provato?

[Anna87_m]

si ed escono cose senza senso cioè mi esce L=3 L=5 L=345667 per tre volte e L=36

[xnavigator]

il codice per un mergesort (vero)di un array per esempio è questo:

void main() {
	char a[8]={'H','G','F','E','D','C','B','A'};
	char b[8];
	char i=0;

	es_12_02_1_mergesort_ricorsivo( a, b,0,7 );

	puts("Risultato algo mergesort ricorsivo: \n");
	for(;i<8;i++)
		printf("b[%d]=>[%c]\n",i,b[i]);
}

void es_12_02_1_mergesort_ricorsivo( char a[], char b[],short left, short right ) {
	short center;
	if (left<right) {
		center = (left+right)/2;
		es_12_02_1_mergesort_ricorsivo( a, b, left, center );
		es_12_02_1_mergesort_ricorsivo( a, b, center+1, right );
		es_12_02_1_merge( a, b, left, center, right );
	}
}

void es_12_02_1_merge(char a[], char b[], short left, short center, short right) {
	short i=left, j = center + 1, k = 0;

	while( (i <= center) && (j <= right) ) {
		if ( a[i] <= a[j] ) {
			b[k] = a[i];
			i++;
		} else {
			b[k] = a[j];
			j++;
		}
		k++;
	}

	while( i <= center ) {
		
		b[k] = a[i];
		i++;
		k++;
	}

	while( j <= right ) {
		
		b[k] = a[j];
		j++;
		k++;
	}

	for(k=left; k<=right; k++) {
		a[k] = b[k-left];
	}
}

quella printf stamperà l'array ordinato

[MacApp]

Originariamente inviato da xnavigator
il codice per un mergesort (vero)di un array per esempio è questo:

void main() {
...

il tuo codice (vero) genera un po' di warning:

$ gcc main.c 
main.c: In function 'main':
main.c:10: warning: incompatible implicit declaration of built-in function 'printf'
main.c:1: warning: return type of 'main' is not 'int'
main.c: At top level:
main.c:13: warning: conflicting types for 'es_12_02_1_mergesort_ricorsivo'
main.c:6: warning: previous implicit declaration of 'es_12_02_1_mergesort_ricorsivo' was here
main.c:23: warning: conflicting types for 'es_12_02_1_merge'
main.c:19: warning: previous implicit declaration of 'es_12_02_1_merge' was here

[xnavigator]

grazie mancano i prototipi e gli include delle librerie... non li ho messi perchè non sono molto difficili da ottenere lol

[MacApp]

Originariamente inviato da xnavigator
grazie mancano i prototipi e gli include delle librerie... non li ho messi perchè non sono molto difficili da ottenere lol

non basta: la main non restituisce un int :-p
;-)

[Anna87_m]

quindi il programma del mio prof è sbagliato e guardo quello che avevo postato qui?