[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]

Originariamente inviato da 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?

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

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

[TorpedoBlu]

Originariamente inviato da andbin

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]

Originariamente inviato da 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 ~§~

che praticamente è quello che ho postato.