Bubble sort su nodi lista

di il
5 risposte

Bubble sort su nodi lista

Salve a tutti ragazzi. Sto cercando di creare il bubble sort per ordinare una lista dove per esempio ogni nodo della lista non contiene un solo valore come per esempio un intero ma contiene una struttura dati supponiamo che contenga un nome e una data.
Ora se volessi ordinare questa lista per giorno mese anno, quello che voglio fare è scambiare i nodi e non i valori all'interno dei nodi, perchè se scambiassi solo i valori, assocerei a un determinato nome una data diversa.

Ora io ho cercato di fare un algoritmo che mi scambia i nodi, l'ho provato e funziona solo nel caso in cui le date nella lista sono inserite dalla più grande alla più piccola (quando si inseriscono bisogna metterle dalla più piccola alla più grande perchè l'inserimento è fatto in testa).

Io credo che ci sia un modo molto più semplice di fare questo ordinamento, ma purtroppo non ci sono arrivato.

Posto il codice, ma preferirei trovare un metodo più semplice per risolvere il problema


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

typedef struct nodo
{
    struct data
        {
            int giorno;
            int mese;
            int anno;
        }data0;
    struct nodo *next;
}Nodo;

typedef Nodo *NodoPtr;

int inserisci_date(NodoPtr *testa);
void bubble_sort_date(NodoPtr *testa, int n_date);
void stampa_date(NodoPtr testa);


int main (void)
{

printf("========================Ordinamento di date========================\n\n");

NodoPtr headPtr = NULL;

int i;
i = inserisci_date(&headPtr);
puts("Unsorted date");
puts("");

stampa_date(headPtr);

printf("\n\n");

bubble_sort_date(&headPtr,i);

puts("Sorted date");

stampa_date(headPtr);



system("pause");
return 0;
}


int inserisci_date(NodoPtr *testa)
{
char x = 's';
int i=0;
    while (x == 's')
    {
        NodoPtr nuovoPtr = malloc(sizeof(Nodo));
        if (nuovoPtr != NULL)
        {
            printf("Inserisci giorno mese anno (gg/mm/aaaa): ");
            fflush(stdin);
            scanf("%d/%d/%d", &nuovoPtr->data0.giorno, &nuovoPtr->data0.mese, &nuovoPtr->data0.anno);
            nuovoPtr->next  = *testa;
            *testa = nuovoPtr;
            i++;
        }
        else
            printf("Impossibile allocare memoria\n");
    printf("Vuoi inserire un'altra data?: ");
    fflush(stdin);
    scanf("%c", &x);
    }
    return i;
};





void bubble_sort_date(NodoPtr *testa, int n_date)
{
NodoPtr i = NULL;
NodoPtr j = NULL;
NodoPtr itemp = NULL;
NodoPtr jtemp = NULL;
NodoPtr vartemp = NULL;
int ordinato = 1;
int h;
for (h=0; n_date<h-1; h++)
{
    for (i=(*testa), itemp=i; i->next!=NULL; i=i->next, itemp=i)
    {
            for(j=i->next, jtemp=j; j->next!= NULL;j=j->next,  jtemp=j, i=itemp)
            {
            //itemp=i;
            //jtemp1=j;

            if(i->data0.anno > j->data0.anno)
            {
                if(i==(*testa))
                {
                    i=j;
                    j=itemp;
                    j->next=i->next;
                    i->next=j;

                    (*testa)=i;

                    vartemp=i;

                }
                else
                {
                    i=j;
                    j=itemp;
                    j->next=i->next;
                    i->next=j;
                    vartemp->next=i;


                }
            }
            else
            {

            }

        }
    }

}

};

void stampa_date(NodoPtr testa)
{
while (testa != NULL)
    {
        printf("%d/%d/%d\n", testa->data0.giorno, testa->data0.mese, testa->data0.anno);
        testa = testa->next;
    }
    puts("");

};





5 Risposte

  • Re: Bubble sort su nodi lista

    Ok, ma prima di fare altre domande, dovresti rispondere a quelle ancora pendenti, altrimenti non ha senso darti risposte.
  • Re: Bubble sort su nodi lista

    oregon ha scritto:


    Ok, ma prima di fare altre domande, dovresti rispondere a quelle ancora pendenti, altrimenti non ha senso darti risposte.
    Scusa hai ragione, solo che mi sono dedicato a fare altri esercizi e ho tralasciato quello. Comunque ho risposto al post
  • Re: Bubble sort su nodi lista

    Ho ripensato al problema in questione e mi chiedo che potrei risolvere se riuscissi a salvare in una variabile l'intera struttura in modo tale da creare una variabile temporanea, ma non so innanzitutto se si può fare, e non saprei nemmeno come farlo
  • Re: Bubble sort su nodi lista

    Grazie comunque, ho risolto, posto il codice se può essere di aiuto a qualcuno
    
    
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct nodo
    {
        struct dati_utente {
            char nome[20];
            char cognome[20];
            char email[30];
    
            struct data
                {
                    int giorno;
                    int mese;
                    int anno;
                }DataNascita;
        }DatiUtente;
    
        struct nodo *next;
    }Nodo;
    
    typedef Nodo *NodoPtr;
    void inserisci_utenti(NodoPtr *testa);
    void bubble_sort_bydate(NodoPtr *testa);
    void stampa_utenti(NodoPtr testa);
    
    
    int main (void)
    {
    
        NodoPtr headPtr = NULL;
    
        printf("======================== Ordinamento di Utenti ========================\n\n");
    
        inserisci_utenti(&headPtr);
        puts("\n=============== UTENTI UNSORTED ===============\n");
        puts("");
        stampa_utenti(headPtr);
    
        printf("\n\n");
    
        bubble_sort_bydate(&headPtr);
    
        puts("=============== UTENTI SORTED ===============\n");
        puts("");
        stampa_utenti(headPtr);
    
    system("pause");
    return 0;
    }
    
    
    void inserisci_utenti(NodoPtr *testa)
    {
        int n_utenti = 0;
        int i;
        printf("Quanti utenti vuoi inserire?: ");
        scanf("%d", &n_utenti);
        for (i = 1; i <= n_utenti; i++)
        {
            NodoPtr nuovoPtr = malloc(sizeof(Nodo));
    
            if (nuovoPtr != NULL)
            {
                printf(" ====== UTENTE %d di %d ======\n", i, n_utenti);
                printf("Inserisci Nome: ");
                fflush(stdin);
                gets(nuovoPtr->DatiUtente.nome);
                printf("Inserisci Cognome: ");
                fflush(stdin);
                gets(nuovoPtr->DatiUtente.cognome);
                printf("Inserisci Data di Nascita (gg/mm/aaaa): ");
                fflush(stdin);
                scanf("%d/%d/%d", &nuovoPtr->DatiUtente.DataNascita.giorno, &nuovoPtr->DatiUtente.DataNascita.mese, &nuovoPtr->DatiUtente.DataNascita.anno);
                printf("Inserisci Email: ");
                fflush(stdin);
                gets(nuovoPtr->DatiUtente.email);
    
                nuovoPtr->next  = *testa;
                *testa = nuovoPtr;
            }
            else
                printf("Impossibile allocare memoria\n");
        }
    };
    
    void bubble_sort_bydate(NodoPtr *testa)
    {
        Nodo temp;
        NodoPtr i = NULL;
        NodoPtr j = NULL;
    
        //sorting by year
    
        for (i = (*testa); i->next != NULL;  i = i->next)
        {
            for (j = i->next; j != NULL; j = j->next)
            {
                if (i->DatiUtente.DataNascita.anno > j->DatiUtente.DataNascita.anno)
                {
                    temp.DatiUtente = i->DatiUtente;
                    i->DatiUtente = j->DatiUtente;
                    j->DatiUtente = temp.DatiUtente;
                }
            }
        }
    
        //sorting by mounth
        for (i =(*testa); i->next != NULL; i = i->next)
        {
            for (j = i->next; j != NULL; j = j->next)
            {
                if ((i->DatiUtente.DataNascita.anno == j->DatiUtente.DataNascita.anno) && (i->DatiUtente.DataNascita.mese > j->DatiUtente.DataNascita.mese))
                {
                    temp.DatiUtente = i->DatiUtente;
                    i->DatiUtente = j->DatiUtente;
                    j->DatiUtente = temp.DatiUtente;
                }
            }
        }
    
        //sorting by day
    
         for (i =(*testa); i->next != NULL; i = i->next)
        {
            for (j = i->next; j != NULL; j = j->next)
            {
                if ((i->DatiUtente.DataNascita.mese == j->DatiUtente.DataNascita.mese) && (i->DatiUtente.DataNascita.giorno > j->DatiUtente.DataNascita.giorno))
                {
                    temp.DatiUtente = i->DatiUtente;
                    i->DatiUtente = j->DatiUtente;
                    j->DatiUtente = temp.DatiUtente;
                }
            }
        }
    
    };
    
    
    void stampa_utenti(NodoPtr testa)
    {
    while (testa != NULL)
        {
            printf("======================================\n");
            printf("Utente : %s %s\nEmail: %s\n", testa->DatiUtente.nome, testa->DatiUtente.cognome, testa->DatiUtente.email);
            printf("Nato il: %d/%d/%d\n", testa->DatiUtente.DataNascita.giorno, testa->DatiUtente.DataNascita.mese, testa->DatiUtente.DataNascita.anno);
            testa = testa->next;
            printf("======================================\n\n");
        }
    };
    
    
    
    
    
  • Re: Bubble sort su nodi lista

    Innanzitutto devo segnalarti che potresti semplificare i confronti semplicemente calcolandoti un valore di comodo secondo questa formula anno*10000+mese*100+giorno e quindi ridurre il tutto a fare un solo ciclo.
    Però volevo chiederti: che senso ha ordinare la lista copiando i dati all'interno dei vari nodi, non avrebbe più senso modificare i puntatori lasciando inalterati i nodi? Per come la vedo io potresti semplicemente ricostruire una nuova lista ordinata estraendo i nodi da quella disordinata.
    Inoltre, avendo a disposizione una lista, non è più comodo tenerla ordinata in fase di inserimento?
    Per come la vedo io, stai utilizzando la lista come se fosse un array senza sfruttarne alcuna caratteristica; eventualmente se si tratta di un esercizio, posta il testo dell'esercizio (e magari indicaci da dove lo hai prelevato).
Devi accedere o registrarti per scrivere nel forum
5 risposte