[c] - Ordinare una lista

di
eclipto
il
11 risposte
E
eclipto
Utente Attivo
Iscritto da
lug, 2014
Messaggi:
51

[c] - Ordinare una lista

Salve a tutti,
Sto risolvendo un esercizio che richiede, tra le altre cose, di ordinare gli elementi di una lista.

Io ho creato una lista del tipo
head -> new_e -> e_n -> ... -> e_2 -> e_1
in cui ogni elemento della lista è una struct con alcuni campi tra cui quello che devo utilizzare per ordinare.

In pratica, mi sembra di capire che esistono essenzialmente due modi per ordinare liste di questo tipo:
1) "scambiare" tutti i dati o
2) "scambiare" i puntatori.

Quale è migliore e perché?

Io generalmente utilizzo il Bubble sort per ordinare gli array e avevo pensato di utilizzarlo anche per ordinare la lista (swappando i puntatori).
E' una cosa sensata da utilizzare? Qualcuno di voi ha del codice che potrei guardare?

Grazie e buon anno a tutti!

11 Risposte

  • vbextreme
    vbextreme
    Molto attivo
    Iscritto da
    feb, 2012
    Messaggi:
    1143

    Re: [c] - Ordinare una lista

    Nella lista si scambiano sempre i puntatori!
    Il bubble sorte è semplice.
  • E
    eclipto
    Utente Attivo
    Iscritto da
    lug, 2014
    Messaggi:
    51

    Re: [c] - Ordinare una lista

    Ciao e grazie.
    Per qualche motivo il codice è illeggibile, ti dispiacerebbe ripostarlo?
  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21784

    Re: [c] - Ordinare una lista

    Quello non è il to codice ma la sua illeggibile firma ...
  • E
    eclipto
    Utente Attivo
    Iscritto da
    lug, 2014
    Messaggi:
    51

    Re: [c] - Ordinare una lista

    Ahahah, scusatemi, ero entrata col cellulare. xD
  • E
    eclipto
    Utente Attivo
    Iscritto da
    lug, 2014
    Messaggi:
    51

    Re: [c] - Ordinare una lista

    Rieccomi (sorry).
    Ho provato a scrivere il codice con la stessa struttura del bubble sort ma ho alcuni problemi.

    Volevo evitare di contare prima gli elementi della lista (cosa che ho visto fare in alcuni esempi di code che ho trovato in rete).

    La mia idea era quindi quella di utilizzare un puntatore precedente a quelli da confrontare e, eventualmente, swappare.

    Il problema è che non so dove porre questo puntatore all'inizio, quando l'elemento da confrontare col successivo è = head.

    Dopo aver controllato che la lista non sia vuota o costituita da un solo nodo, volevo utilizzare due cicli del tipo
    while(i -> next != NULL)
    {
        while((j -> next) != NULL)
        {
            //...
            j = j-> next; 
        }
        i  = i -> next;
}
    dove i e j sono puntatori a elementi della lista.

    Ora, questa cosa evidentemente non va bene, perché non ho dove posizionale il puntatore *pre, che mi servirebbe successivamente per lo swap.

    Avevo anche pesato di creare un primo puntatore temporaneo per evitare questo problema.

    C'è un modo più semplice per fare questa cosa? Cosa non sto considerando?
    Vi ringrazio
  • minomic
    minomic
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1137

    Re: [c] - Ordinare una lista

    Se vuoi evitare di scambiare i puntatori, che può essere una cosa non banale, puoi rifarti a questo esempio:
    
#include <stdio.h>
#include <stdlib.h>

typedef struct nodo_t {
    int val;
    struct nodo_t* next;
} Nodo;

typedef Nodo* Lista;


Lista aggiungi_in_coda(Lista l, int nuovo_valore)
{
    Nodo* nuovo_nodo = malloc(sizeof(Nodo));
    nuovo_nodo->val = nuovo_valore;
    nuovo_nodo->next = NULL;

    if(l == NULL) {
        return nuovo_nodo;
    }
    Lista tmp = l;
    while(tmp->next != NULL) {
        tmp = tmp->next;
    }
    // il prossimo e' NULL: inserisco il nuovo_nodo
    tmp->next = nuovo_nodo;

    // restituisco la lista originale
    return l;
}


void stampa_lista(Lista l)
{
    while(l != NULL) {
        printf("%d  ", l->val);
        l = l->next;
    }
    printf("\n");
}


void bubble_lista(Lista* lista)
{
    int tmp;
    int rifare = 1;
    Nodo* l1 = NULL;
    Nodo* l2 = NULL;

    while(rifare == 1) {
        rifare = 0;
        for(l1 = *lista; l1->next != NULL; l1 = l1->next) {
            for(l2 = l1->next; l2 != NULL; l2 = l2->next) {
                if(l1->val > l2->val) {
                    tmp = l1->val;
                    l1->val = l2->val;
                    l2->val = tmp;
                    rifare = 1;
                }
            }
        }
    }
}


int main()
{
    Lista lista = NULL;

    lista = aggiungi_in_coda(lista, 1);
    lista = aggiungi_in_coda(lista, 3);
    lista = aggiungi_in_coda(lista, 2);
    lista = aggiungi_in_coda(lista, 5);
    lista = aggiungi_in_coda(lista, 4);

    stampa_lista(lista);

    bubble_lista(&lista);

    stampa_lista(lista);

    return 0;
}
  • E
    eclipto
    Utente Attivo
    Iscritto da
    lug, 2014
    Messaggi:
    51

    Re: [c] - Ordinare una lista

    Grazie
    Sì, alla fine ho utilizzato questo tipo di codice per l'esercizio.
    Domani vedo se riesco a scrivere qualcosa scambiando i puntatori.
    Oggi ho provato a scrivere il bubbe sort aggiungendo un elemento all'inizio della lista, in modo da evitare problemi ma ne è uscita fuori una cosa probabilmente più ingarbugliata del necessario (molto spaghetti code, insomma) e quindi mi chiedevo se esiste un metodo più o meno "standard" di farlo o almeno un metodo standard di sorting di una lista (al di là del bubble sort, di cui posso fare tranquillamente a meno, ovviamente).
  • minomic
    minomic
    Molto attivo
    Iscritto da
    nov, 2010
    Messaggi:
    1137

    Re: [c] - Ordinare una lista

    Temo di non aver capito la domanda... Secondo me, con il codice che ti ho postato prima riesci a gestire qualunque caso. Quali problemi hai trovato? Può benissimo darsi che mi sia sfuggito qualcosa...
  • E
    eclipto
    Utente Attivo
    Iscritto da
    lug, 2014
    Messaggi:
    51

    Re: [c] - Ordinare una lista

    No, il tuo codice funziona benissimo e va bene per tutti i casi, ovviamente.

    Solo che, da quanto ho capito, il metodo generalmente utilizzato per ordinare una lista è quello scambiare i puntatori perché la copia dei dati è più lenta.
    Quindi volevo sapere se qualcuno potesse fornirmi del codice che implementi questo tipo di sorting
    That's all
    Grazie per la pazienza, btw
  • vbextreme
    vbextreme
    Molto attivo
    Iscritto da
    feb, 2012
    Messaggi:
    1143

    Re: [c] - Ordinare una lista

    Generalmente viene aggiunto un altro puntatore alla lista chiamato prev, questo velocizza e semplifica le operarioni di inserimento ed eliminazione dentro ad una lista.
    Ma non c'è e quindi il codice diventa: 
    

typedef struct nodo_t {
    int val;
    struct nodo_t* next;
}Nodo;

Nodo* aggiungi_in_coda(Nodo* l, int nuovo_valore)
{
    Nodo* nuovo_nodo = malloc(sizeof(Nodo));
    nuovo_nodo->val = nuovo_valore;
    nuovo_nodo->next = NULL;

    if(l == NULL) return nuovo_nodo;
    
    Nodo* tmp; 
    for (tmp = l; tmp->next; tmp = tmp->next);
   
    tmp->next = nuovo_nodo;

    return l;
}

void stampa_lista(Nodo* l)
{
    for(; l; l = l->next) 
        printf("%d  ", l->val);
    printf("\n");
}

Nodo* bubble_lista(Nodo* l)
{
    if ( !l && !l->next) return l;
    
    int scambio;
    Nodo* bubble;
	
    do
    {
        scambio = 0;
        
        //il primo è speciale
        if ( l->val > l->next->val )
        {
            scambio =! scambio;
            //tolgo dalla lista il secondo elemento
            bubble = l->next;
            l->next = bubble->next;
            //metto l'elemento tolto in testa alla lista
            bubble->next = l;
            l = bubble;
        }
        //tutti gli altri confronto il sucessivo con il sucessivosucessivo
        //in questo modo non perdo il riferimento al precedente
        for(bubble = l; bubble->next->next; bubble = bubble->next) 
        {
            if ( bubble->next->val > bubble->next->next->val )
            {
                if ( !scambio ) scambio =! scambio;
				
                //tolgo dalla lista l'elemento sucessivosucessivo
                Nodo* swap = bubble->next->next;
                bubble->next->next = swap->next;
                //swappo
                swap->next = bubble->next;
                bubble->next = swap;
            }       
        }
    }while(scambio);
    
    return l;
}


int main()
{
    Nodo* lista = NULL;

    lista = aggiungi_in_coda(lista, 6);
    lista = aggiungi_in_coda(lista, 3);
    lista = aggiungi_in_coda(lista, 2);
    lista = aggiungi_in_coda(lista, 5);
    lista = aggiungi_in_coda(lista, 4);
    lista = aggiungi_in_coda(lista, 1);
    
    stampa_lista(lista);

    lista = bubble_lista(lista);

    stampa_lista(lista);

    return 0;
}
    è anche vero che in una lista semplice si aggiunge sempre in testa o in maniera ordinata e quasi mai in coda.

    Con la speranza che sia piu leggibile della mia "illeggibile firma"
  • E
    eclipto
    Utente Attivo
    Iscritto da
    lug, 2014
    Messaggi:
    51

    Re: [c] - Ordinare una lista

    Grazie infinite.
    Ora me lo guardo per bene e se ho dei dubbi chiedo.
Devi accedere o registrarti per scrivere nel forum
11 risposte