[C] Eliminare nodo da lista

miticco

il 30 nov 2013, 12:11

6 risposte

miticco

Pochi posts

Iscritto da: nov, 2013

Messaggi:: 2

[C] Eliminare nodo da lista

30 nov 2013, 12:17

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

M
migliorabile
Super Famoso
Iscritto da
apr, 2013
Messaggi:
6075
Re: [C] Eliminare nodo da lista
01 dic 2013, 15:21
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.

miticco

Pochi posts

Iscritto da: nov, 2013

Messaggi:: 2

Re: [C] Eliminare nodo da lista

01 dic 2013, 16:36

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;
}

S
serpiccio
Pochi posts
Iscritto da
dic, 2012
Messaggi:
14
Re: [C] Eliminare nodo da lista
01 dic 2013, 23:16
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

vbextreme

Molto attivo

Iscritto da: feb, 2012

Messaggi:: 1143

Re: [C] Eliminare nodo da lista

02 dic 2013, 12:54

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;
}

S
serpiccio
Pochi posts
Iscritto da
dic, 2012
Messaggi:
14
Re: [C] Eliminare nodo da lista
02 dic 2013, 16:32
É 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.
vbextreme
Molto attivo
Iscritto da
feb, 2012
Messaggi:
1143
Re: [C] Eliminare nodo da lista
02 dic 2013, 18:30
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