[C] Sort nel collegamento di due liste

di
JJBall
il
6 risposte
J
JJBall
Pochi posts
Iscritto da
mag, 2018
Messaggi:
20

[C] Sort nel collegamento di due liste

Salve a tutti, mi trovo a collegare due liste concatenate. La richiesta in questione è che la lista risultante del collegaento di due liste di interi sia ordinata in maniera crescente. La funzione da me sviluppata è:
//definisco la struttura
struct intList{
    int value;
    struct intList *next;
};
//sinonimo di intList
typedef struct intList IntList;
typedef IntList *intList;

main(){
...
}

void concatenate(IntList *l1, IntList *l2){
   intList curr1, curr2, p1, p2;

    curr1 = l1;
    curr2 = l2;

    int flag = 1;

    while(flag == 1){
        if(curr1 != NULL && curr2 != NULL){
            p1 = curr1->next;
            curr1->next = curr2;
            p2 = curr2->next;
            if(p1 != NULL){
                curr2->next = p1;
            }
            curr1 = p1;
            curr2 = p2;
        }
        else{
            flag = 0;
        }
    }
}
Così facendo, supponendo l1 = {1,2,3} e l2 = {4,5,6}, la lista risultante è: {1,4,2,5,3,6}.
Dove è l'errore? Secondo me manca un controllo lungo la nuova lista che controlli che il valore immesso sia maggiore dei precedenti, o qualcosa di simile.
Grazie per la disponibilità.

6 Risposte

  • S
    smalldragon
    Molto attivo
    Iscritto da
    nov, 2008
    Messaggi:
    865

    Re: [C] Sort nel collegamento di due liste

    Ciao
    al momento l'idea che mi viene e quella di scaricarsi le due liste in un vettore ordinare il vettore e poi creare una nuova lista.
    se mi viene qualche altra soluzione te la faccio sapere.
    spero di esserti stato d'aiuto
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: [C] Sort nel collegamento di due liste

    Giusto per capire:
    - le liste l1 e l2 passate alla funzione sono già ordinate?
    - di cosa stiamo parlando precisamente?
    1) date le liste l1 e l2 creiamo una terza lista l3 contenente gli elementi di l1 e l2 presi in ordine crescente (quindi le liste di partenza l1 e l2 non andranno perse);
    2) oppure date le liste l1 e l2 concateniamo fisicamente i loro elementi al fine di ottenere la lista risultante(quindi le liste di partenza l1 e l2 andranno perse);
    - dove andrà salvato l'indirizzo della testa della lista?
  • J
    JJBall
    Pochi posts
    Iscritto da
    mag, 2018
    Messaggi:
    20

    Re: [C] Sort nel collegamento di due liste

    Nippolo ha scritto:

    Giusto per capire:
    - le liste l1 e l2 passate alla funzione sono già ordinate?
    - di cosa stiamo parlando precisamente?
    1) date le liste l1 e l2 creiamo una terza lista l3 contenente gli elementi di l1 e l2 presi in ordine crescente (quindi le liste di partenza l1 e l2 non andranno perse);
    2) oppure date le liste l1 e l2 concateniamo fisicamente i loro elementi al fine di ottenere la lista risultante(quindi le liste di partenza l1 e l2 andranno perse);
    - dove andrà salvato l'indirizzo della testa della lista?
    È esattamente il caso due, e no le liste l1, l2 non sono ordinate poichè sono inserite mano a mano da tastiera dall'utente. Comunque ho risolto creando due funzioni:

    -concatenate: concatena le due liste;
    -ordina: ordina la lista concatenata;
    Se volete posso postare i codici delle due funzioni, magari possono essere utili in futuro a chi cerca la soluzione a un problema di questo tipo.
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: [C] Sort nel collegamento di due liste

    Se vuoi posta, così ci diamo un'occhiata.
  • J
    JJBall
    Pochi posts
    Iscritto da
    mag, 2018
    Messaggi:
    20

    Re: [C] Sort nel collegamento di due liste

    
//definisco la struttura
struct intList{
    int value;
    struct intList *next;
};
//sinonimo di intList
typedef struct intList IntList;
typedef IntList *intList;


int main(){
...
}
//concatena le due liste
void concatenate(IntList *l1, IntList *l2){
   intList curr1, curr2, p1, p2;

    curr1 = l1;
    curr2 = l2;

    int flag = 1;

    while(flag == 1){
        if(curr1 != NULL && curr2 != NULL){
            p1 = curr1->next;
            curr1->next = curr2;
            p2 = curr2->next;
            if(p1 != NULL){
                curr2->next = p1;
            }
            curr1 = p1;
            curr2 = p2;
        }
        else{
            flag = 0;
        }
    }
}


//ordina la lista
IntList ordina(IntList *l){
    if(l && l->next){
        int k = 1;

        while(k != 0){
            IntList *punt = l;
            k = 0;
            while(punt->next){
                IntList *punt1 = punt;
                punt = punt->next;

                if(punt1->value > punt->value){
                    int tmp = punt1->value;
                    punt1->value = punt->value;
                    punt->value = tmp;
                    k = 1;
                }
            }
        }
    }
    return *l;

}
  • Nippolo
    Nippolo
    Molto attivo
    Iscritto da
    mar, 2018
    Messaggi:
    1237

    Re: [C] Sort nel collegamento di due liste

    Alcune considerazioni:
    - tutta la parte relativa alla dichiarazione della struct e ai typedef la trovo molto incasinata;
    - mi sembra di capire che la funzione concatenate() partendo da l1 concatena le 2 liste alternando un elemento da una lista e un elemento dall'altra.
    Una curiosità... a cosa serve quest'alternanza? Non sarebbe più semplice concatenare l'ultimo elemento di una lista al primo dell'altra?!
    Al termine della funzione l1 punterà alla testa della lista risultante e l2 punterà al secondo elemento (a tal proposito visto che l2 non rappresenta ormai nulla gli assegnerei il valore NULL). Deduco quindi che l'intento è quello di tenere traccia della nuova lista attraverso il puntatore l1, peccato però che se l1 è vuota e l2 no, la lista risultante coinciderà con l2... bisogna quindi apportare qualche correzione.
    In ogni caso il codice della funzione può essere ottimizzato:
    * il flag non serve, basta sostituire nel while la condizione dell'if;
    * i puntatori curr1 e curr2 non servono, puoi utilizzare anche l1 e l2 visto che sono passati per copia;
    * considerando tutto quello che ho detto (e conservando l'alternanza), farei qualcosa del genere: 
    void concatena(nodo **l1, nodo **l2)
{
    if(!*l1)
    {
        *l1 = *l2;
        *l2 = NULL;
    }
    else
    {
        nodo *p;
        nodo *curr = *l1;
        while(*l2)
        {
            p = curr->next;
            curr->next = *l2;
            curr = *l2;
            *l2 = p;
        }
    }
}
    Abbandonando l'alternanza tutto si riduce a: 
    void concatena(nodo **l1, nodo **l2)
{
    if(!*l1)
    {
        *l1 = *l2;
    }
    else
    {
        nodo *p = *l1;
        while(p->next)
        {
            p = p->next;
        }
        p->next = *l2;
    }
    *l2 = NULL;
}
    - per quanto riguarda la funzione ordina():
    * perchè la funzione ritorna il primo elemento della lista (che non è un puntatore)?
    * non mi sono soffermato molto sul codice alla ricerca di eventuali criticità e ottimizzazioni, ma cmq ho capito qual è l'idea di fondo... e a tal proposito mi tocca dire che stai imbrogliando! Mi spiego meglio... da una funzione che ordina una lista mi aspetto che operi sui puntatori e non sui valori del singolo nodo. Immagina che ogni nodo contenga 100 dati membro, dovresti effettuare una marea di scambi in più rispetto al caso in cui operi invece sui puntatori.
Devi accedere o registrarti per scrivere nel forum
6 risposte