[C] Inserire elementi su lista ordinata

[giovanni.91]

Ciao a tutti. Ho realizzato un programma che inserirsce in una lista un elemento intero alla volta e lo inserisce rispettando l'ordine crescente dei numeri naturali.

La funzione ordina() grosso modo funziona. L'unico problema è che se l'elemento da inserire è più piccolo di tutti gli elementi presenti in lista, (quindi va inserito in testa), l'inserimento fallisce. Il programma non va in crash ma ignora proprio l'elemento e non lo inserisce.

Grazie a tutti. Ecco il codice:

struct elemento *aggiungi_ordinato(struct elemento *p){

    struct elemento *q;
    struct elemento *nuovo = NULL;
    struct elemento *prec = NULL;
    int i, x;

        system("cls");
        if(p==NULL){        // se la lista e' vuota diventa primo elemento
            p = malloc(1*sizeof(struct elemento));
            printf("\n\tInserisci informazione: \t");
            scanf("%d", &p->info);
            p->next = NULL;
        }
            else{               // se la lista ha altri elementi
                    q = p;
                    printf("\n\tInserisci informazione: \t");
                    scanf("%d", &x);
                        while((q!=NULL) && (x > q->info)){
                            prec = q;
                            q = q->next;
                        }

                    nuovo = malloc(1*sizeof(struct elemento));
                    nuovo->info = x;

                        if(q==NULL){    // siamo a fine lista
                            prec->next = nuovo;
                            nuovo->next = NULL;
                        }
                            if(prec==NULL){    //siamo a inizio lista - NON FUNZIONA E NON SI CAPISCE PERCHE' -
                                    nuovo->next = q;
                                    q = nuovo;
                                }
                                    else{       // siamo in un punto qualsiasi
                                        prec->next = nuovo;
                                        nuovo->next = q;
                                    }
            }
            return(p);
}

[celtico94]

Nelle liste ordinate, i casi possibili sono sempre 3:
-inserisci in testa;
-inserisci in mezzo;
-inserisci in coda;
per tutti e tre i casi vanno fatte le prove, se si verificano ad esempio il primo o il secondo, inutile andare al terzo.quindi, prima dell'inserimento all'intero ordinato, fai cosi:

if (p->valore < testa->valore)
//inserisci in testa

[giovanni.91]

Scusa ma non ho capito... Puoi riferirti direttamente al codice sorgente che ho pubblicato? Ci sono tre cicli if che differenziano i tre casi...

[celtico94]

qual è il tuo puntatore di testa della lista? credo che il tuo codice sia molto confusionario, gestisce male la lista a livello di algoritmo.

[giovanni.91]

Il puntatore è *p, che la funzione riceve come parametro. Ripeto, gli altri due casi, quando deve inserire l'elemento in coda o in mezzo alla lista funzionano. Non funziona soltanto l'inserimento in testa. cioè questo:

if(prec==NULL){    //siamo a inizio lista - NON FUNZIONA E NON SI CAPISCE PERCHE' -
                                    nuovo->next = q;
                                    q = nuovo;
                                }

[celtico94]

inserisci un
if (p->info > nuovo-> info)
{
nuovo->next = p;
p = nuovo;
}
questo dopo aver chiesto l'informazione, senza scardinare subito la lista.

[Mond0]

scusa ma non ho capito perchè c'è tutto quel codice, è alquanto confusionario :P io fossi in te lo riscriverei da capo :P
devi fare questi punti:
- prendi l'elemento in input da inserire;
- controlli il caso che la lista sia vuota;

if(p == NULL){
            p = malloc(1*sizeof(struct elemento));
            p->info = x;
            p->next = NULL;

- controlli che il primo elemento non sia maggiore dell'elemento in input;

if(p->info > x){
                p = malloc(1*sizeof(struct elemento));
                p->info = x;
                p->next = q;

- iteri tutto il resto della lista inserendo dove opportuno;

while((q != NULL) && (q->info < x))
                {
                    prec = q;
                    q = q->next;
                }

questi sono solo spezzoni ovviamente...