[c] ordinamento di una lista

[TorpedoBlu]

ho una lista


struct gene_list {
char *dato;
int inizio, fine;
struct gene_list *next, *prev;
};


devo ordinarla secondo l'elemento fine.

come faccio ad applicare un algo di sorting ad una lista?

[andbin]

ho una lista


struct gene_list {
char *dato;
int inizio, fine;
struct gene_list *next, *prev;
};


devo ordinarla secondo l'elemento fine.

come faccio ad applicare un algo di sorting ad una lista?L'algoritmo "Merge sort" è adatto per ordinare strutture di dati con accesso sequenziale.

Vedere: http://en.wikipedia.org/wiki/Merge_sort

[TorpedoBlu]

L'algoritmo "Merge sort" è adatto per ordinare strutture di dati con accesso sequenziale.

Vedere: http://en.wikipedia.org/wiki/Merge_sort

ok...ehm... e come lo applico alla mia lista? è implementato con array

[akyra]

a mio parere, senza andare a complicarti la vita con il merge sort (che comunque è asintoticamente migliore) usa un insertion sort, che è più semplice da implementare.
se invece t'interessano le prestazioni migliori, allora il merge sort è più indicato.

[TorpedoBlu]

mi sono incasinato con quegli algo perchè lavorano sugli indici degli array.... e io non devo solo cambiare un elemento della struttura ma spostare interamente i nodi con i loro elementi.

ho fatto questa porcata

gene_list *orderList(gene_list *originale){
gene_list *temp, *risultato, *max;
int i=0, lista_lenght=countlist(originale);

risultato=createlist();

while(i<lista_lenght){
max=originale->next;
for(temp = originale->next; temp != originale; temp = temp->next){
if(temp->fine>max->fine)
max=temp;
}
insert(risultato, max->dato, max->inizio, max->fine);
max->fine=-1;
delete(max);
/*max->fine=-1; nel caso in cui mi serva la lista di partenza*/
i++;
}
return risultato;
}


la struttura è òa seguente


struct gene_list {
char *dato;
int inizio, fine;
struct gene_list *next, *prev;
};

[Fenomeno85]

dato che sulla lista non ci puoi andare dove vuoi l'unico metodo è quello di crearti una nuova lista togliendo un nodo alla volta dalla lista di partenza e inserire in modo ordinato in quella di supporto.

~§~ Sempre E Solo Lei ~§~

[TorpedoBlu]

dato che sulla lista non ci puoi andare dove vuoi l'unico metodo è quello di crearti una nuova lista togliendo un nodo alla volta dalla lista di partenza e inserire in modo ordinato in quella di supporto.

~§~ Sempre E Solo Lei ~§~

che praticamente è quello che ho postato.