[C] problema funzionamento - Radix Sort -

[nalsk]

Salve a tutti,

Sono nuovo del forum hardware upgrade, e colgo l'occasione di fare il mio primo post chiedendovi disperatamente aiuto sul funzionamento del radix sort!
Vorrei implementare l'algoritmo di ordinamento su un vettore di liste riempite random da numeri interi.
Il mio problema è il seguente: quando richiamo la funzione radix, se la utilizzo nel seguente modo:

rad=radix_sort(rad);

il compilatore mi da un errore sull'argomento che passo alla funzione, mentre sia nella mask sia nella dichiarativa ho usato list_pointer radix_sort(list_pointer ptr), che a mio avviso è compatibile con la chiamata che uso.

Se potreste mettermi almeno sulla giusta strada ve ne sarei grato, in quanto non sono sicuro di aver eseguito tutti i passaggi alla perfezione.
grazie in anticipo..

riporto il codice che ho buttato giù fino ad ora:

#include <stdio.h>
#include <stdlib.h>

#define RADICE_SIZE 10  //GRANDEZZA RADIX
#define MAX_CIFRE 4 

#define MAX_ELEM 10   



typedef struct list_node *list_pointer;
typedef struct list_node {
        int chiave[MAX_CIFRE];
        list_pointer link;
        }lista;

void random (void);
void visrad(list_pointer ptr);
list_pointer radix_sort(list_pointer);

list_pointer rad[RADICE_SIZE];

int vettore[MAX_ELEM];

main()
{
      int i;
      
      printf("\tCreazione:\n\n");
      random();
      for(i=0;i<RADICE_SIZE;i++) {
                                 printf("\t%d",i);
                                 visrad(rad[i]);
                                 printf("\n");
                                 }
      printf("\n");
      
      for(i=0;i<MAX_ELEM;i++) printf("%5d",vettore[i]);
      
      printf("\n\n\tOrdinamento:\n\n");
      
      for(i=0;i<RADICE_SIZE;i++) rad[i]=radix_sort(rad[i]);
      
      printf("x");
      
            for(i=0;i<RADICE_SIZE;i++) {
                                 printf("\t%d",i);
                                 visrad(rad[i]);
                                 printf("\n");
                                 }
      
      fflush(stdin);getchar();
}

//------------- INSERIMENTO --------------------------------------------

void insert_rad (list_pointer *ptr,int item)
{
     list_pointer temp;
     int i,aux;
     
     temp = (lista*)malloc(sizeof(lista));
     
     for(i=0;i<MAX_CIFRE;i++) temp->chiave[i]=(int)(item/pow(10,i))%10;
     temp->link = *ptr;
     *ptr = temp;
}

//------------- INSERIMENTO --------------------------------------------

void random (void)
{
     int i,x;
     srand(time(NULL));
     for(i=0;i<MAX_ELEM;i++) {
                             vettore[i]=rand()%((int)pow(RADICE_SIZE,MAX_CIFRE));
                             x=rand()%(RADICE_SIZE);
                             insert_rad(&rad[x],vettore[i]);
                             }
     }

//------------- VISITA DELLA RADICE -------------------------------------

void visrad(list_pointer ptr)
{
     int i;
     
     printf("\t");
     for(;ptr;ptr=ptr->link) {
                             for(i=MAX_CIFRE-1;i>=0;i--)
                             printf("%d",ptr->chiave[i]);
                             printf(" ");
                             }
}

//------------- ORDINAMENTO --------------------------------------------

list_pointer radix_sort(list_pointer ptr)
{
             list_pointer davanti[RADICE_SIZE],dietro[RADICE_SIZE];
             int i,j,cifra;
             
             for(i = MAX_CIFRE-1;i>=0;i--) {
                   for(j=0;j<RADICE_SIZE;j++) davanti[j] = dietro[j] = NULL;
                   while(ptr) {
                              cifra = ptr->chiave[i];
                              if(!davanti[cifra]) davanti[cifra] = ptr;
                              else                dietro[cifra]->link = ptr;
                              dietro[cifra] = ptr;
                              ptr = ptr->link;
                              }
                              ptr = NULL;
                              for(j = RADICE_SIZE-1;j>=0;j--)
                              if(davanti[j]) {
                                            dietro[j]->link = ptr;
                                            ptr = davanti[j];
                                            }
                              }
                              return ptr;
                   }

[nalsk]

So che è una domanda banale e molti di voi non vorrebbero perdere tempo su una cosa come questa, ma purtroppo io ho provato invano tutto ciò che la mia poca esperienza mi ha insegnato. A questo punto sono al "capolinea"..

Mettiamola così: offro birra e pizza a chi mi da delucidazioni

[Wing_Zero]

Originariamente inviato da nalsk

So che è una domanda banale e molti di voi non vorrebbero perdere tempo su una cosa come questa, ma purtroppo io ho provato invano tutto ciò che la mia poca esperienza mi ha insegnato. A questo punto sono al "capolinea"..

Mettiamola così: offro birra e pizza a chi mi da delucidazioni

Ora va:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define RADICE_SIZE 10  //GRANDEZZA RADIX
#define MAX_CIFRE 4 

#define MAX_ELEM 10   



typedef struct list_node *list_pointer;
typedef struct list_node {
        int chiave[MAX_CIFRE];
        list_pointer link;
        }lista;

void random1 (void);
void visrad(list_pointer ptr);
list_pointer radix_sort(list_pointer);

list_pointer rad[RADICE_SIZE];

int vettore[MAX_ELEM];

main()
{
      int i;
      
      printf("\tCreazione:\n\n");
      random1();
      for(i=0;i<RADICE_SIZE;i++) {
                                 printf("\t%d",i);
                                 visrad(rad[i]);
                                 printf("\n");
                                 }
      printf("\n");
      
      for(i=0;i<MAX_ELEM;i++) printf("%5d",vettore[i]);
      
      printf("\n\n\tOrdinamento:\n\n");
      
      for(i=0;i<RADICE_SIZE;i++) rad[i]=radix_sort(rad[i]);
      
      printf("x");
      
            for(i=0;i<RADICE_SIZE;i++) {
                                 printf("\t%d",i);
                                 visrad(rad[i]);
                                 printf("\n");
                                 }
      
      fflush(stdin);getchar();
}

//------------- INSERIMENTO --------------------------------------------

void insert_rad (list_pointer *ptr,int item)
{
     list_pointer temp;
     int i,aux;
     
     temp = (lista*)malloc(sizeof(lista));
     
     for(i=0;i<MAX_CIFRE;i++) temp->chiave[i]=(int)(item/pow(10,i))%10;
     temp->link = *ptr;
     *ptr = temp;
}

//------------- INSERIMENTO --------------------------------------------

void random1 (void)
{
     int i,x;
     srand(time(NULL));
     for(i=0;i<MAX_ELEM;i++) {
                             vettore[i]=rand()%((int)pow(RADICE_SIZE,MAX_CIFRE));
                             x=rand()%(RADICE_SIZE);
                             insert_rad(&rad[x],vettore[i]);
                             }
     }

//------------- VISITA DELLA RADICE -------------------------------------

void visrad(list_pointer ptr)
{
     int i;
     
     printf("\t");
     for(;ptr;ptr=ptr->link) {
                             for(i=MAX_CIFRE-1;i>=0;i--)
                             printf("%d",ptr->chiave[i]);
                             printf(" ");
                             }
}

//------------- ORDINAMENTO --------------------------------------------

list_pointer radix_sort(list_pointer ptr)
{
             list_pointer davanti[RADICE_SIZE],dietro[RADICE_SIZE];
             int i,j,cifra;
             
             for(i = MAX_CIFRE-1;i>=0;i--) {
                   for(j=0;j<RADICE_SIZE;j++) davanti[j] = dietro[j] = NULL;
                   while(ptr) {
                              cifra = ptr->chiave[i];
                              if(!davanti[cifra]) davanti[cifra] = ptr;
                              else                dietro[cifra]->link = ptr;
                              dietro[cifra] = ptr;
                              ptr = ptr->link;
                              }
                              ptr = NULL;
                              for(j = RADICE_SIZE-1;j>=0;j--)
                              if(davanti[j]) {
                                            dietro[j]->link = ptr;
                                            ptr = davanti[j];
                                            }
                              }
                              return ptr;
                   }

Correzioni:
1) rinominato la funzione random in random1 : random è una funzione già esistente nelle librerie incluse.

2) mancava l'inclusione di math.h

Se utlizzai un compilatore gcc dovrai aggiungere al termine della command line -lm per fargli linkare la libreria math.h

Ciao
Wing

[nalsk]

Originariamente inviato da Wing_Zero

Ora va:

grazie mille! è che questi giorni la mia testolina non sta ingranando come si deve.. a bon rendere

[nalsk]

ora compila ma il radix non ordina.. sarà un errore nell'algoritmo di ordinamento?

[Wing_Zero]

Originariamente inviato da nalsk

ora compila ma il radix non ordina.. sarà un errore nell'algoritmo di ordinamento?

Non ho avuto tempo di vedere se l'output fosse ordinato correttamente...sicuramente è diverso dai valori base...se poi non sono ordinati correttamente non so xD
Ho passato il primo anno di università a intrecciarmi gli occhi su algoritmi di ordinamento che nn ordinavano correttamente...ora lascio il divertimento a te Detto spassionatamente nn ho alcuna voglia
Torno a finire di programmare un webservice in java.

Ciao
Wing

[nalsk]

Originariamente inviato da Wing_Zero

Non ho avuto tempo di vedere se l'output fosse ordinato correttamente...sicuramente è diverso dai valori base...se poi non sono ordinati correttamente non so xD
Ho passato il primo anno di università a intrecciarmi gli occhi su algoritmi di ordinamento che nn ordinavano correttamente...ora lascio il divertimento a te Detto spassionatamente nn ho alcuna voglia
Torno a finire di programmare un webservice in java.

Ciao
Wing

grazie mille lo stesso.. buon lavoro