[C] Ordinare Lista?

di il
1 risposte

[C] Ordinare Lista?

Salve a tutti,
Ho un piccolo problema con un progetto.
Ho una struttura così :

typedef struct elem_lista
{
	char marchio[MAX_CHAR];
	char modello[MAX_CHAR];
	char colore[MAX_CHAR];
	char cod_telaio[MAX_CHAR];
	int prezzo;
	struct elem_lista *succ_p;
} elem_lista_t;
Il programma legge da un file delle informazioni riguardo automobili e le inserisce in una struttura.
La specifica richiede di stampare la lista ordinata in base ad una delle chiavi (scelta dall'utente)
Ora, ordinare una lista è una cosa un po' macchinosa e poco performante. Qualcuno ha qualche idea su come posso fare?

1 Risposte

  • Re: [C] Ordinare Lista?

    Se vuoi fare le cose per bene potresti implementare il merge sort per liste. Se ci pensi non è difficilissimo. In pratica durante la fase di merge fondi le liste aggiungendo via via alla lista finale gli elementi dell'una o dell'altra. Puoi immaginarlo come una cerniera lampo che si chiude, dove i dentini sono gli elementi delle 2 liste da fondere, solo che invece di alternare un dentino di sinistra e uno di destra, li alterni a seconda del risultato del confronto.

    Più che altro devi capire se, dove e quando usare delle liste ausiliarie temporanee.

    Altrimenti usi l'insertion sort, che però con una lista semplice è un po' macchinoso e credo sia O(x^3) (sarebbe più semplice con una lista doppiolinkata, ovvero con link in entrambe le soluzioni).

    ciao
Devi accedere o registrarti per scrivere nel forum
1 risposte