[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! :fagiano:
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.. :help: :help:

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 :Prrr:

[Wing_Zero]

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 :Prrr:

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]

Ora va:


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

[nalsk]

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

[Wing_Zero]

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]

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 :)