ordinamento di una struttura in base ad un suo campo

[fausto]

Ciao a tutti.

ho bisogno di ordinare gli elementi di un vettore di strutture in base ad
un campo di queste (il campo è di tipo int).

avevo pensato di copiare in un vettore di interi gli elementi di quel
singolo campo di tutte le strutture, ordinare quel vettore, e poi,
scorrendo il vettore di strutture, man mano che trovavo un elemento
uguale all'elemanto i-esimo del vettore ordinato, andare a copiare la
struttura che contiene quell'elemento nel mio vettore finale.

in questo modo però dovrei fare un ciclo for annidato dentro un altro,
che aumenterebbe la complessità dell'ordinamento.
C'è una soluzione un po' più elegante, senza bisogno di riscrivermi una
funzione quicksort apposita?

grazie per l'attenzione

[MaxMax]

Post by fausto
ho bisogno di ordinare gli elementi di un vettore di strutture in base ad
un campo di queste (il campo è di tipo int).
avevo pensato di copiare in un vettore di interi gli elementi di quel
singolo campo di tutte le strutture, ordinare quel vettore, e poi,
scorrendo il vettore di strutture, man mano che trovavo un elemento
uguale all'elemanto i-esimo del vettore ordinato, andare a copiare la
struttura che contiene quell'elemento nel mio vettore finale.
in questo modo però dovrei fare un ciclo for annidato dentro un altro,
che aumenterebbe la complessità dell'ordinamento.
C'è una soluzione un po' più elegante, senza bisogno di riscrivermi una
funzione quicksort apposita?
grazie per l'attenzione

Fa così:

mettiamo che tu abbia

struct mystruct
{
int a;
int b;
}

e tu abbia

struct mystruct miovettore[100];

Ora tu fai:

struct mystruct *mioptr[100];

for (size_t i = 0; i < 100; i++)
mioptr[i] = &miovettore[i];

Ora tu fai il qsort (usando la funzione qsort) dell'arrai mioptr[i]
(chiaramente la user-defined function per l'ordinamento userà il mioptr per
accedere agli elementi di miovettore); Alla fine ordinerai in una singola
passata l'array miovettore (attento a non combinare guai in questo
passaggio! La cosa più semplice E veloce è definire un nuovo miovettore[] e
popolarlo usando il vecchio miovettore e mioptr. Se invece vuoi fare tutto
"sul posto" allora diventa più complicato.

--- bye

--- bye

[Giovanni Resta]

Post by fausto
Ciao a tutti.
ho bisogno di ordinare gli elementi di un vettore di strutture in base ad
un campo di queste (il campo è di tipo int).

Guarda questo esempio. La struct l'ho chiama ciccio, e il campo
per l'ordinamento e' chiave.

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

typedef struct
{
int chiave;
double dati;
char pippo[8];
}
ciccio;


int CmpCiccio(const void *aa, const void *bb)
{
ciccio *a, *b;
a = (ciccio *) aa;
b = (ciccio *) bb;

if (a->chiave > b->chiave) return 1;
else if (a->chiave < b->chiave) return -1;
else return 0;
}

int main()
{

ciccio CiccioVec[100];

// blah blah blah
qsort(CiccioVec, 100, sizeof(ciccio), CmpCiccio);
// blah blah blah
return 0;
}

Naturalmente, se i tuoi record sono molti e molto
grossi puo' convenire fare una cosa diversa
(per evitare tutti gli swap che farebbe il
quicksort). In quel caso potrebbe convenire
lavorare su un array di puntatori alla strutture
lasciando i dati dove stanno e scambiando solo i
puntatori.
ciao.
g.

[tester]

[snip]
C'è una soluzione un po' più elegante, senza bisogno di riscrivermi una
funzione quicksort apposita?
[snip]

Una delle cose che potresti decidere di fare e` ordinare gli elementi
appena questi vengono acquisiti (letti da regular file, user input, ecc.
ecc.) durante la scrittura nell'array di strutture. Realizzare cio` con un
array allocato staticamente e` un attentato alla pazienza di chiunque
(overkill swap). La cosa piu` semplice da implementare e` una lista
linkata. Ti ho scritto un esempio qui di sotto che non realizza
esattamente cio` che vuoi, ma ti fornisce una traccia; in sostanza
cambiando poche righe di codice ottieni cio` che desideri ;)

Quest'esempio inserisce *tutti* i numeri dati in ordine crescente
(comprese le possibili ripetizioni); nel tuo post non c'erano riferimenti
su come gestire questa situazione per cui qui vengono semplicemente
aggiunti. Se desideri non inserirli o se hai un contatore di occorrenze,
ti basta cambiare poche righe di codice per ottenere il comportamento
voluto ;)

Essendo una lista semplicemente linkata ottieni, come "vantaggio
collaterale", un'estrema semplicita` nel rimuovere un singolo elemento.
L'eventuale funzione che implementa questa operazione e` pressoche` uguale
alla __add_member ;)



#include <time.h>
#include <errno.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


#ifndef NUM_TEST_KEYS
# define NUM_TEST_KEYS 20
#endif

#ifndef MIN_KEY_VALUE
# define MIN_KEY_VALUE 1
#endif

#ifndef MAX_KEY_VALUE
# define MAX_KEY_VALUE 100
#endif


typedef struct my_element *array_t;

struct my_element
{
int key;
array_t next;
};


static __inline__ int __add_member(int curr_key, array_t *array)
{
array_t tmp = NULL, scan = NULL, prescan = NULL;

if ((tmp = calloc(1, sizeof(struct my_element))) == NULL)
return 0;

tmp->key = curr_key;

if (*array == NULL || (*array)->key >= curr_key)
{
tmp->next = *array;
*array = tmp;
}

else
{
for (prescan = *array, scan = (*array)->next;
scan != NULL && scan->key < curr_key;
prescan = scan, scan = scan->next);

tmp->next = scan;
prescan->next = tmp;
}

return 1;
}


static __inline__ void __print_array(array_t array)
{
(void)fprintf(stdout, "- Current array: ");

for (; array != NULL; array = array->next)
(void)fprintf(stdout, "%d ", array->key);

(void)fprintf(stdout, "\n");
}


static __inline__ void __delete_array(array_t *array)
{
if (*array != NULL)
{
__delete_array(&(*array)->next);

(*array)->key = 0;

free(*array);
*array = NULL;
}
}


int main(void)
{
int test_keys[NUM_TEST_KEYS];
array_t array = NULL;
int i;

(void)fprintf(stdout, "- Generating %d pseudo-random keys ... ",
NUM_TEST_KEYS);
srand(time(NULL));

for (i = 0; i < NUM_TEST_KEYS; i++)
/* yeah, do a crapping generation ;) */
test_keys[i] = MIN_KEY_VALUE + (rand() % MAX_KEY_VALUE);

(void)fprintf(stdout, "done.\n\n");

for (i = 0; i < NUM_TEST_KEYS; i++)
{
(void)fprintf(stdout, "- Add key %d ...\n", test_keys[i]);

if (!__add_member(test_keys[i], &array))
{
(void)fprintf(stderr, "*** fatal error: __add_member: errno %d
(%s)\n", errno, strerror(errno));
break;
}

__print_array(array);
}

__delete_array(&array);
return 0;
}



Il codice di cui sopra genera in maniera barbara (ma in questa sede non ci
interessa poi molto) una sequenza di NUM_TEST_KEYS (default = 20) keys
pseudo-random comprese nell'intervallo chiuso MIN_KEY_VALUE (default = 1)
e MAX_KEY_VALUE (default = 100); questa parte di codice e`
*esclusivamente* a scopo di test per simulare un eventuale input reale
(che tu avrai da regular file, user input, ecc. ecc. come dicevo prima).
Se desideri modificare i valori di default per i test ti basta passare le
opportune direttive di preprocessore a compile time (senza toccare il
codice); ad esempio, utilizzando gcc, se desideri generare 30 keys
anziche` 20:

gcc -DNUM_TEST_KEYS=30 -W -Wall -pedantic -ansi -o test test.c

A questo punto inizia il programma vero e proprio e, di conseguenza,
quello che interessa a te ;)
Come dicevo prima questo codice vuole essere una traccia; nella funzione
__add_member invece di passare solo la chiave dovrai passare la struttura
corrente ... ;)

Se prevedi di avere un'elevata mole di keys probabilmente dovresti
prendere in considerazione l'idea di implementare quest'idea con un albero
binario (magari sempre bilanciato) ... gestendo in maniera opportuna le
ripetizioni, ovviamente ;)

Ciao.