Visualizzazione dei risultati da 1 a 10 su 10

Discussione: Eliminazione di un nodo in un albero

  1. #1
    Utente di HTML.it
    Registrato dal
    Feb 2017
    Messaggi
    11

    Eliminazione di un nodo in un albero

    Buonasera a tutti.
    Come da titolo sto lavorando sull'implementazione di alcune funzioni per la gestione degli alberi, funzionano tutte tranne quella per la cancellazione dei singoli nodi, nello specifico quando devo cancellare una foglia(un nodo che non ha figli).
    In teoria quando il codice riconosce che ad essere eliminata è una foglia prima libera la memoria allocata al puntatore e poi lo inizializza a NULL.
    In pratica il programma da errore di segmentazione e viene terminato.
    Nonostante siano ore che ci lavoro non riesco a venirne a capo, qualcuno può aiutarmi?

    codice:
    #include<stdio.h>#include<stdlib.h>
    #include<stdbool.h>
    
    
    struct node
    {
        int value;
        struct node *sx;//puntatore al nodo a sinistra
        struct node *dx;//puntatore al nodo a destra
    };
    
    
    typedef struct node *tree;
    
    
    int restituisci_valore(tree N)
    {
        if(N==NULL)
            return 0;
        else
            return N->value;
    }
    
    
    tree nuovo_albero(void)
    {
        return NULL;
    }
    
    
    bool albero_vuoto(tree T)
    {
        return T == NULL;
    }
    
    
    tree inserisci_elemento(tree T, int val)//qui vengono inseriti gli elementi voluti dall'utente
    {
        if(T==NULL)
            {    
             T=(tree)malloc(sizeof(tree));
             T->value = val;
             T->sx = NULL;
             T->dx = NULL;
            }    
        else
            {
             if((T->value) < (val)) 
                {
                 T->dx = inserisci_elemento(T->dx, val);
                }
             if((T->value) > (val))
                {
                 T->sx = inserisci_elemento(T->sx, val);
                }
            }
        return T;
    }
    
    
    tree restituisci_radice(tree T)
    {
        return T;
    }
    
    
    void stampa_tutto(tree W)
    {
        if(W==NULL)
            {
             return;
            }
        else
            {
             stampa_tutto(W->sx);
             printf("%d\n", W->value);
             stampa_tutto(W->dx);
            }
    }
    
    
    void cancellazione_elemento(tree Y, int elem)
    {
        if(Y->value < elem)
            cancellazione_elemento(Y->dx, elem);
        if(Y->value > elem)
            cancellazione_elemento(Y->sx, elem);
        else//se Y->value risulta uguale all elemento che vogliamo eliminare
            {
             if(Y->sx == NULL && Y->dx == NULL)
                {
                 free(Y);
                 Y=NULL;
                }
             if(Y->sx != NULL && Y->dx == NULL)
                {
                 Y->value = Y->sx->value;
                 free(Y->sx);
                 Y->sx=NULL;
                }
             if(Y->sx == NULL && Y->dx != NULL)
                {
                  Y->value = Y->dx->value;
                 free(Y->dx);
                 Y->dx=NULL;
                }
             if(Y->sx != NULL && Y->dx != NULL)
                 printf("Non posso eliminare questo nodo poichè entrambi i suoi rami contengono dei dati!\n");
            }
         stampa_tutto(Y);
    }
    
    
    void distruggi_albero(tree T)
    {
        if(T->sx != NULL)
            {
             distruggi_albero(T->sx);
            }
        if(T->dx != NULL)
            {
             distruggi_albero(T->dx);
            }
        if((T->sx == NULL) && (T->dx == NULL))
            {
             free(T);
            }
        if(albero_vuoto(T))
            return;
    }
    
    
    void ricerca_ricorsiva(tree W, int num)
    {
        if(albero_vuoto(W)==true)
             printf("L'albero non contiene il tuo elemento\n");
        if(W->value > num)
             ricerca_ricorsiva(W->sx, num);
        if(W->value < num)
             ricerca_ricorsiva(W->dx, num);
        if(W->value == num)
             printf("Il numero da te cercato esiste nel tuo albero!\n");
    }
    
    
    void scansione(tree T)
    {
     tree W=T;
     int num;
        printf("Che numero vuoi cercare?  ");
        scanf("%d", &num);
        if(albero_vuoto(T)==true)
            printf("Non posso eseguire una ricerca su un albero vuoto, chiudo bottega\n");
        else
            ricerca_ricorsiva(W, num);
    }
    
    
    
    
    int main(void)
    {
     tree T=nuovo_albero();
     int val,tot,elem;
        printf("Con questo programma creeremo un albero binario ordinato\nQuanti elementi vuoi inserire?  ");
        scanf("%d", &tot);
            for(int i=0; i<tot; i++)
                {
                 printf("Qual'è il %d° elemento che vuoi inserire?  ", (i+1));
                 scanf("%d", &val);
                 T=inserisci_elemento(T, val);
                }
        printf("Ora stampiamo il tuo albero binario ordinato!\n");
    
    
        tree W=T;
        stampa_tutto(W);
    
    
        //scansione(T);
        tree Y=T;
        printf("Cancelliamo un elemento dall albero!\nQuale vuoi eliminare?  ");
        scanf("%d", &elem);
        cancellazione_elemento(Y, elem);
    
    
        printf("Distruggiamo quindi l'albero creato per deallocare la memoria utilizzata!\n");
        distruggi_albero(T);
    }

  2. #2
    Utente di HTML.it
    Registrato dal
    Feb 2017
    Messaggi
    11
    Up, nessuno ha idea del problema?

  3. #3
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,336
    tree è un puntatore a struttura, non la struttura in se
    codice:
    tree inserisci_elemento(tree T, int val)//qui vengono inseriti gli elementi voluti dall'utente
    {
        if(T==NULL)
            {    
    /*         T=(tree)malloc(sizeof(tree)); */
             T=(tree)malloc(sizeof(struct node));
             T->value = val;
             T->sx = NULL;
             T->dx = NULL;
            }    
    ... etc
    This code and information is provided "as is" without warranty of any kind, either expressed
    or implied, including but not limited to the implied warranties of merchantability and/or
    fitness for a particular purpose.

  4. #4
    Utente di HTML.it
    Registrato dal
    Feb 2017
    Messaggi
    11
    Quote Originariamente inviata da shodan Visualizza il messaggio
    tree è un puntatore a struttura, non la struttura in se
    codice:
    tree inserisci_elemento(tree T, int val)//qui vengono inseriti gli elementi voluti dall'utente
    {
        if(T==NULL)
            {    
    /*         T=(tree)malloc(sizeof(tree)); */
             T=(tree)malloc(sizeof(struct node));
             T->value = val;
             T->sx = NULL;
             T->dx = NULL;
            }    
    ... etc
    Quando ci hanno introdotto all'uso delle strutture con puntatori ci hanno detto che quando si rinomina con il typedef X in Y quella Y significherà sempre quell X. Ad ogni modo ho provato con la tua modifica ma lo stesso va in crash cercando di cancellare la foglia....

  5. #5
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,336
    Si, ma tu non hai fatto un typedef X in Y, ma un typedef X* in Y che non è la stessa cosa. E alla sizeof() passi come argomento un X* non un X. Ora un puntatore ha dimensione 4bytes (32bit) o 8bytes (64bit) a seconda del compilatore che usi, per cui allochi sempre o 4 o 8 bytes, ma la struttura node (al netto di bytes di padding) ha 4 bytes solo per l'int, più 8 o 16 bytes per i due puntatori. Insomma stai cercando di mettere ai piedi di un bigfoot le scarpette di cenerentola. E va di lusso che il problema si presenti solo in fase di deallocazione.

    Per il secondo problema, controlla bene la sequenza di eliminazione della foglia. Qual'è l'istruzione immediatamente seguente a Y=NULL quando si trova la foglia?
    This code and information is provided "as is" without warranty of any kind, either expressed
    or implied, including but not limited to the implied warranties of merchantability and/or
    fitness for a particular purpose.

  6. #6
    Utente di HTML.it
    Registrato dal
    Feb 2017
    Messaggi
    11
    Effettivamente hai ragione riguardo il problema sui puntatori grave errore da parte mia, presterò piu attenzione.
    Riguardo il 2° suggerimento immagino che ti riferisca alla funzione di stampa a cui passo un puntatore che punta a NULL giusto?
    Ho eliminato anche quel problema inserendo la funzione di stampa dopo quella di elimina nodo nel main aggirando il problema del puntatore ad un indirizzo nullo (immagino sia un'altro passo in avanti) però l'errore di segmentazione continua a persistere

  7. #7
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,336
    No, mi riferisco a questo:
    codice:
    void cancellazione_elemento(tree Y, int elem)
    {
        if(Y->value < elem)
            cancellazione_elemento(Y->dx, elem);
        if(Y->value > elem)
            cancellazione_elemento(Y->sx, elem);
        else//se Y->value risulta uguale all elemento che vogliamo eliminare
            {
             if(Y->sx == NULL && Y->dx == NULL)
                {
                 free(Y);
                 Y=NULL;
                }
             if(Y->sx != NULL && Y->dx == NULL) /* prossima istruzione eseguita */
                {
                 Y->value = Y->sx->value;
                 free(Y->sx);
                 Y->sx=NULL;
                }
             if(Y->sx == NULL && Y->dx != NULL)
                {
                  Y->value = Y->dx->value;
                 free(Y->dx);
                 Y->dx=NULL;
                }
             if(Y->sx != NULL && Y->dx != NULL)
                 printf("Non posso eliminare questo nodo poichè entrambi i suoi rami contengono dei dati!\n");
            }
         stampa_tutto(Y);
    }
    Se annulli il puntatore, dereferiarlo implica un crash. Se liberi il puntatore e non lo annulli, hai comunque un crash perché dopo hai qualcosa di non più valido. E questo succede perché i vari if non sono esclusivi, ma sono eseguiti in sequenza.
    Basta aggiungere un else
    codice:
    void cancellazione_elemento(tree Y, int elem)
    {
        if(Y->value < elem)
            cancellazione_elemento(Y->dx, elem);
        if(Y->value > elem)
            cancellazione_elemento(Y->sx, elem);
        else//se Y->value risulta uguale all elemento che vogliamo eliminare
            {
             if(Y->sx == NULL && Y->dx == NULL)
                {
                 free(Y);
                 Y=NULL;
                }
            else if(Y->sx != NULL && Y->dx == NULL)
                {
                 Y->value = Y->sx->value;
                 free(Y->sx);
                 Y->sx=NULL;
                }
             else if(Y->sx == NULL && Y->dx != NULL)
                {
                  Y->value = Y->dx->value;
                 free(Y->dx);
                 Y->dx=NULL;
                }
             else if(Y->sx != NULL && Y->dx != NULL)
                 printf("Non posso eliminare questo nodo poichè entrambi i suoi rami contengono dei dati!\n");
            }
         stampa_tutto(Y);
    }
    This code and information is provided "as is" without warranty of any kind, either expressed
    or implied, including but not limited to the implied warranties of merchantability and/or
    fitness for a particular purpose.

  8. #8
    Utente di HTML.it
    Registrato dal
    Feb 2017
    Messaggi
    11
    Quote Originariamente inviata da shodan Visualizza il messaggio
    Se annulli il puntatore, dereferiarlo implica un crash. Se liberi il puntatore e non lo annulli, hai comunque un crash perché dopo hai qualcosa di non più valido. E questo succede perché i vari if non sono esclusivi, ma sono eseguiti in sequenza.
    Basta aggiungere un else
    codice:
    void cancellazione_elemento(tree Y, int elem)
    {
        if(Y->value < elem)
            cancellazione_elemento(Y->dx, elem);
        if(Y->value > elem)
            cancellazione_elemento(Y->sx, elem);
        else//se Y->value risulta uguale all elemento che vogliamo eliminare
            {
             if(Y->sx == NULL && Y->dx == NULL)
                {
                 free(Y);
                 Y=NULL;
                }
            else if(Y->sx != NULL && Y->dx == NULL)
                {
                 Y->value = Y->sx->value;
                 free(Y->sx);
                 Y->sx=NULL;
                }
             else if(Y->sx == NULL && Y->dx != NULL)
                {
                  Y->value = Y->dx->value;
                 free(Y->dx);
                 Y->dx=NULL;
                }
             else if(Y->sx != NULL && Y->dx != NULL)
                 printf("Non posso eliminare questo nodo poichè entrambi i suoi rami contengono dei dati!\n");
            }
         stampa_tutto(Y);
    }
    Nada anche cosi ha sempre il problema del segmentation fault, tra l'altro le varie condizioni impostate negli if non dovrebbero impedire una loro esecuzione in sequenza?

  9. #9
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,336
    Nel tuo codice originale no, dato che ogni if viene controllato a prescindere dal precedente. Mettendo l'else, invece, il primo if verificato bypassa gli altri.
    Tra l'altro c'è un errore subdolo in quella funzione: ossia che i vari annullamenti dei puntatori rimangono locali alla funzione, per cui quando si entra in uno dei rami ricorsivi e poi se ne esce, i puntatori ->dx o ->sx non sono NULL, ma non sono nemmeno più validi. Il che significa che oltre a fallire i controlli, si fa la free() di un puntatore sporco.
    Per trasmettere le modifiche all'esterno è necessario passare un puntatore al puntatore.
    La sintassi è quella che è, però modificando così non ho avuto più problemi:
    codice:
    void cancellazione_elemento(tree* Y, int elem)
    {
        if ((*Y)->value < elem)
            cancellazione_elemento(&(*Y)->dx, elem);
        else if ((*Y)->value > elem)
            cancellazione_elemento(&(*Y)->sx, elem);
        else//se Y->value risulta uguale all elemento che vogliamo eliminare
        {
            if ((*Y)->sx == NULL && (*Y)->dx == NULL)
            {
                free((*Y));
                (*Y) = NULL;
            }
            else if ((*Y)->sx != NULL && (*Y)->dx == NULL)
            {
                (*Y)->value = (*Y)->sx->value;
                free((*Y)->sx);
                (*Y)->sx = NULL;
            }
            else if ((*Y)->sx == NULL && (*Y)->dx != NULL)
            {
                (*Y)->value = (*Y)->dx->value;
                free((*Y)->dx);
                (*Y)->dx = NULL;
            }
            else if ((*Y)->sx != NULL && (*Y)->dx != NULL)
                printf("Non posso eliminare questo nodo poichè entrambi i suoi rami contengono dei dati!\n");
        }
        stampa_tutto((*Y));
    }
    This code and information is provided "as is" without warranty of any kind, either expressed
    or implied, including but not limited to the implied warranties of merchantability and/or
    fitness for a particular purpose.

  10. #10
    Utente di HTML.it
    Registrato dal
    Feb 2017
    Messaggi
    11
    Quote Originariamente inviata da shodan Visualizza il messaggio
    Nel tuo codice originale no, dato che ogni if viene controllato a prescindere dal precedente. Mettendo l'else, invece, il primo if verificato bypassa gli altri.
    Tra l'altro c'è un errore subdolo in quella funzione: ossia che i vari annullamenti dei puntatori rimangono locali alla funzione, per cui quando si entra in uno dei rami ricorsivi e poi se ne esce, i puntatori ->dx o ->sx non sono NULL, ma non sono nemmeno più validi. Il che significa che oltre a fallire i controlli, si fa la free() di un puntatore sporco.
    Per trasmettere le modifiche all'esterno è necessario passare un puntatore al puntatore.
    La sintassi è quella che è, però modificando così non ho avuto più problemi:
    codice:
    void cancellazione_elemento(tree* Y, int elem)
    {
        if ((*Y)->value < elem)
            cancellazione_elemento(&(*Y)->dx, elem);
        else if ((*Y)->value > elem)
            cancellazione_elemento(&(*Y)->sx, elem);
        else//se Y->value risulta uguale all elemento che vogliamo eliminare
        {
            if ((*Y)->sx == NULL && (*Y)->dx == NULL)
            {
                free((*Y));
                (*Y) = NULL;
            }
            else if ((*Y)->sx != NULL && (*Y)->dx == NULL)
            {
                (*Y)->value = (*Y)->sx->value;
                free((*Y)->sx);
                (*Y)->sx = NULL;
            }
            else if ((*Y)->sx == NULL && (*Y)->dx != NULL)
            {
                (*Y)->value = (*Y)->dx->value;
                free((*Y)->dx);
                (*Y)->dx = NULL;
            }
            else if ((*Y)->sx != NULL && (*Y)->dx != NULL)
                printf("Non posso eliminare questo nodo poichè entrambi i suoi rami contengono dei dati!\n");
        }
        stampa_tutto((*Y));
    }
    Il codice ora fa quel che deve senza crash di sorta. Questo metodo del puntatore a puntatore non l'hanno mai mostrato però se questa è la sua efficacia converrà usarlo con regolarità su funzioni simili. Ad ogni modo grazie dell'assistenza

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2017 vBulletin Solutions, Inc. All rights reserved.