[C] Eliminare nodo da lista

di il
6 risposte

[C] Eliminare nodo da lista

Ciao ragazzi, ho un problema con le liste a puntatori (che novità ), la logica del funzionamento mi è chiara, ma non capisco perché il mio codice non funzioni... Praticamente devo eliminare da una lista gli elementi con all'interno un numero dispari, ed ovviamente la funzione che si occupa di ciò non funziona , o meglio non fa ciò che dovrebbe, ecco il codice:
#include <stdio.h>
#include <stdlib.h>

struct nodo{
       int dato;
       struct nodo *next;
       };
struct nodo *inserimento()
{
     int num,i,x;
     struct nodo *p,*start,*prev;
     start=NULL;
     p=start;
     prev=p;
     printf("\nDigita quanti numeri vuoi inserire: ");
     scanf("%d",&x);
     for(i=0;i<x;i=i+1){ 
                             printf("\nInserisci il numero: ");
                             scanf("%d",&num);
                             p=(struct nodo*)malloc(sizeof(struct nodo));
                             if(start==NULL)
                                              { 
                                                 start=p;
                                                 start->dato=num;
                                              }
                             else     {
                                                 p->dato=num;
                                                 prev->next=p;
                                      }
                             prev=p;
                             p->next=NULL;
                       }
     return start;
}
struct nodo *stampa(struct nodo *start)
{
  struct nodo *p=start;
  printf("\n\n\n");
  while(p!=NULL){
                 printf(" %d",p->dato);
                 if(p->next!=NULL){
                                    printf("-->");
                                  }
                 p=p->next;
                }
  return;      
}
                                                     
int main()
{
  struct nodo *start=NULL;
  start=inserimento();
  stampa(start);
  start=elimina(start);  
  stampa(start);
  printf("\n\n");
  system("PAUSE");	
  return 0;
}
Questa è la funzione incriminata:
struct nodo *elimina(struct nodo *start)
{
       struct nodo *last,*p;
       p=start;
       last=p;
       while(p!=NULL){
                        if(p->dato%2!=0){
                                         if(p==start){
                                                       free(start);
                                                       start=p->next;
                                                       p=start;
                                                     }
                                         else{
       
                                               last->next=p->next;
                                               free(p);
                                               if(last->next!=NULL) //altrimenti va in errore
                                               p=last->next;
                                             }
                                        }
                        last=p;
                        p=p->next;
                     }
       return start;
}    
Spero possiate darmi una mano

6 Risposte

  • Re: [C] Eliminare nodo da lista

    Ci sono diversi pasticci, alcuni ovvi, alcuni subdoli.

    1) in stampa() devi inserire un 'printf("\n")' alla fine, altrimenti la riga non viene stampata su schermo. Questo e' un'ottimizzazione inserita penso di recente per poter supportare il print su schermo da parte di piu' thread: la riga viene scritta in blocco solo se termina con un "\n".
    Se non sai che cosa e' un thread, non preoccuparti. E' roba per programmatori esperti.

    2) elimina(): c'e' troppo codice! Dirai: che centra?, Centra! Perche' fai la stessa cosa in punti diversi della routine ma non nelo stesso modo! Questo ha come conseguenza che se correggi un punto, non e' detto che correggi anche gli altri. Anzi, nel 99.99999% dei casi non succede, con conseguenze devastanti (si e' comnvinti di aver fatto la correzione ma continua a non funzionare)

    Ma iniziamo:

    2.1) allo startup NON HAI
    p=start
    last=p
    MA
    p = start
    last = NULL
    E' una questione di coerenza, ma anche di codice in meno da scrivere

    2.2) questa e' subdola
    if(p->dato%2!=0){
                                             if(p==start){
                                                           free(start);
                                                           start=p->next;
                                                           p=start;
                                                         }
                                             else
    qui hai p==start, MA chiami 'free(start)' e quindi 'start=p->next'.

    Ora, poiche' sei partito con 'p==start' e start (e quindi p) e' stato liberato, NON PUOI FARE NESSUN AFFIDAMENTO sul contenuto del blocco di memoria. Da nessuna parte ti viene assicurato che il contenuto della memoria venga mantenuto dopo essere stata rilasciata. E' assolutamente dipendente dall'implementazione della libreria. Nel mio caso, ad esempio, il contenuto della memoria viene sovvrascritto con un pattern. Quindi, PRIMA si accede alle informazioni, POI si libera il nodo

    2.3) anche questa e' subdola:
    else{
           
                                                   last->next=p->next;
                                                   free(p);
                                                   if(last->next!=NULL) //altrimenti va in errore
                                                   p=last->next;
                                                 }
                                            }
                            last=p;
                            p=p->next;
    Qui' ci sono due errori:

    a) a 'p' assegni 'p->next' DUE VOLTE: una dentro l'else ed una all'uscita dell' "if"
    b) esegui 'p=p->next' SENZA CONTROLLARE se hai raggiunto la fine della lista

    2.4) questo codice non serve a nulla:
     if(last->next!=NULL) //altrimenti va in errore
    Se ti da errore, non e' mettendoci delle zeppe/accrocchi (alias test inutili) che elimini l'errore, ma capendo PERCHE' va in errore.

    In generale la regola che devi seguire e' la seguente: l'algoritmo NON DEVE AVERE codice inutile, DEVE ESSERE COMPATTO ed elegante.
  • Re: [C] Eliminare nodo da lista

    Anzitutto grazie per l'aiuto, ho aggiunto alla fine della funzione di stampa la printf("\n"), anche se non ho ben capito il perché.Gli altri errori sono stati molto ben chiariti, tranne l'ultimo... io per scorrere la lista eseguo un while finché p!=NULL, non mi è chiaro perché dovrei fare un controllo per eseguire p=p->next, poiché il ciclo si ferma quando effettivamente p=NULL, cioè quando è andato oltre la fine della lista... no?

    EDIT: Ho riscontrato un problema quando vado ad eliminare il primo nodo, cioè vado 2 volte avanti,saltandomi il controllo sul nodo succesivo.
    La prima volta quando trova che il primo nodo è da eliminare:
    if(p==start){
                                                           start=start->next;  // aggiustamento
                                                           free(p);            //
                                                           p=start;
                                                         }
    e poi alla fine del while:
                   last=p;
                            p=p->next;
                                    
    ho pertanto utilizzato un flag che quando vado a cambiare start faccio in modo di non saltare il nodo successivo, ma come hai detto tu è un "accrocco"... ecco il codice che ho elaborato, funzionante:
    struct nodo *elimina(struct nodo *start)
    {
           struct nodo *last,*p;
           int h;
           p=start;
           last=NULL;  //non last=p;
           while(p!=NULL){
                            h=0;
                            if(p->dato%2!=0){
                                             if(p==start){
                                                           start=start->next;  // aggiustamento
                                                           free(p);            //
                                                           p=start;
                                                           h=1;
                                                         }
                                             else{
                                                   last->next=p->next;
                                                   free(p);
                                                   p=last;
                                                 }
                                            }
                            last=p;
                            if (h==0){
                                       p=p->next;
                                     }  
                         }
                         
           return start;
    }    
  • Re: [C] Eliminare nodo da lista

    Per eliminare un nodo da una lista io faccio cosí http://pastebin.com/g7e0t4A
    Il codice assume che i puntatori che non puntano a nessun elemento siano impostati a NULL.

    edit: non avevo notato che devi eliminare piú nodi, sarebbe da fare una piccola modifica ma sono sicuro che te la caverai
  • Re: [C] Eliminare nodo da lista

    Una corretta identazione compreso un corretto uso dei nomi delle variabili spesso aiuta non solo i novizi della programmazione.
    
    typedef struct _NODO
    {
        int dato;
        struct _NODO *next;
    }NODO;
    
    NODO* inserimento()
    {
        int nnodi,i;
    
        NODO *start,*last,*current;
        start = last = current = NULL;
    
        printf("\nDigita quanti numeri vuoi inserire: ");
        scanf("%d",&nnodi);
        for( i = 0 ; i < nnodi ; i++ )
        {
            current = (NODO*) malloc(sizeof(NODO));
                if (current == NULL) return NULL;
            printf("\nInserisci il numero: ");
                scanf("%d",&current->dato);
            current->next = NULL;
    
            if( start == NULL)
            {
                start = current;
                last = current;
            }
            else
            {
                last->next = current;
                last = current;
            }
        }
    
        return start;
    }
    
    void stampa(NODO* start)
    {
        printf("\n\n\n");
    
        for ( ; start != NULL ; start = start->next)
        {
            printf("nodo-->%d\n",start->dato);
        }
    }
    
    NODO* elimina(NODO *start)
    {
        NODO *current,*nodotemp;
    
        //cancello tutti i primi nodi che sono divisibili per due
        //questo mi semplifica la sucessiva ricerca.
        current = start;
        while ( start != NULL && !(start->dato % 2) )
        {
            current = start->next;
            free(start);
            start = current;
        }
        if (start == NULL) return NULL;
    
        //ora start non è divisibile per due,cerco i rimanenti.
        current = start;
        while ( current->next != NULL )
        {
    
            if ( !(current->next->dato % 2) )
            {
                nodotemp = current->next->next;
                free(current->next);
                current->next = nodotemp;
            }
            else
            {
                current = current->next;
            }
    
        }
    
        return start;
    }
    
    int main()
    {
        NODO* start = inserimento();
        if (start == NULL)
        {
            printf("End of memory\n");
            return -1;
        }
    
        stampa(start);
    
        start=elimina(start);
        if (start == NULL)
            printf("tutti divisibili per due\n");
        else
            stampa(start);
        printf("\n\n");
        //system("PAUSE"); DISINSTALLA DEV-C++
        return 0;
    }
    
  • Re: [C] Eliminare nodo da lista

    É dev c++ che ha una funzione di formattazione del codice del * che al posto di space usa il carattere di tabulazione, finché visualizzi il tuo programma con dev c++ va tutto bene ma appena lo incolli da qualche parte i tab vengono effettivamente considerati tab e si sforma tutto.
  • Re: [C] Eliminare nodo da lista

    Come ho già ripetuto un migliardo di volte esistono ide completamente gratuiti,quali code::blocks e visual studio express.
    ormai alle soglie del 2014 dover usare ancora un ide del 2005 mi sembra veramente ridicolo!
Devi accedere o registrarti per scrivere nel forum
6 risposte