[C] - Cancellazione nodo Albero.

Saetta

il 25 feb 2012, 19:02

18 risposte

Saetta

Pochi posts

Iscritto da: feb, 2012

Messaggi:: 10

[C] - Cancellazione nodo Albero.

25 feb 2012, 19:46

Ciao a tuttii

Io ho usto codice di creazione, inserimento, visita e cancellazione di un albero..
Ora sto finendo la/le funzione/i per eliminare un nodo dall'albero,però c'è un problema..

Se inserisco 3 numeri per esempio, e poi tento di eliminarne uno non da nessun errore, però NON elimina il nodo.. se decido di riprovare a cancellare lo stesso o un'altro nodo, mi da questo errore:
Albero(344) malloc: *** error for object 0x1044008c0: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

Questo è codice, spero che qualcuno di voi sappia aiutarmi..

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// #include <malloc.h>

typedef struct nodo{
    int dato;
    struct nodo *ptrsx;
    struct nodo *ptrdx;
}nodo;

nodo* creazione(){
    nodo *q;
    q = malloc(sizeof(nodo));
    
    printf("\nInserisci un numero intero:\t");
    scanf("%i", &q->dato);
    printf("\n");
    
    q->ptrsx = NULL;
    q->ptrdx = NULL;
    
    return q;
}

void ins_ord(nodo *p,nodo *q) {
    nodo *r;
    r = p;
    
    if(r->dato > q->dato) {
        if(r->ptrsx == NULL) {
            r->ptrsx = q;
        }else {
            ins_ord(r->ptrsx,q);
        }
    } else {
        if(r->ptrdx == NULL) {
            r->ptrdx = q;
        } else {
            ins_ord(r->ptrdx, q);
        }
    }
}

nodo* ins_bin(nodo *p) {
    nodo *q;
    q = creazione();
    
    if(p == NULL) {
        return q;
    } else {
        ins_ord(p, q);
    }
    
    return p;
}

void visita(nodo *p){
    nodo *r;
    r = p;
    
    if(r->ptrsx != NULL) {
        visita(r->ptrsx);
    }
    
    printf("%i", r->dato);
    printf("\t");
    
    if(r->ptrdx != NULL) {
        visita(r->ptrdx);
    }
}

bool eliminazione(nodo *p, int val) {
    // if(p->dato == val)
        // p->dato = p->ptrsx;
    if(p == NULL)
        return false;
    else {
        elimina(p->ptrsx);
        return true;
    }
}

int elimina(nodo *p) {
    int num, risultato;
    
    if(p->ptrsx == NULL) {
        num = p->dato;
        free(p);
        return num;
    } else if(p->ptrsx != NULL)
        risultato = elimina(p->ptrdx);
    
    return risultato;
}

int main() {
    nodo *radice = NULL;
    
    int scelta = 1, num;
    radice = NULL;
    
    while(scelta != 0) {
        printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
        scanf("%i", &scelta);   
        
        switch(scelta) {
            case 1: {
                radice=ins_bin(radice);
                
                break;
            }
            case 2: {
                printf("\nAlbero:\n");
                visita(radice);
                printf("\n\n");
                
                break;
            }
            case 3: {
                if(radice != NULL){
                    printf("\nInserisci il numero da cancellare:\t");
                    scanf("%d", &num);
                    
                    eliminazione(radice, num);
                } else {
                    printf("\nLa lista e' vuota.\n");
                }
                
                break;
            }
        }
    }
}

18 Risposte

Vins3Xtreme

Utente Attivo

Iscritto da: dic, 2011

Messaggi:: 144

Re: [C] - Cancellazione nodo Albero.

26 feb 2012, 02:04

Sarebbe meglio effetuare il casting alla malloc() dato che quest'ultima restituisce un puntatore (void*) , per cui nell'allocazione modifica in

q=(nodo*)malloc(sizeof(nodo));

. inoltre modificherei la funzione 'ins_ord' in questo modo:


void ins_ord(nodo* &p,int val) {
    if(p==NULL) p=creazione();
    else if(val > p->dato) ins_ord(p->ptrdx,val);
    else ins_ord(p->ptrsx,q);
}

così si può anche non usare 'ins_bin' in quanto quando andiamo ad inserire il nodo in modo ordinato, il vecchio puntatore, se nullo, viene aggiornato. da aggiornare quindi anche la funzione 'visita':


void visita(nodo *p){
    if(p != NULL){
        visita(p->ptrsx);
        printf("%i\t", p->dato);
        visita(p->ptrdx);
    }
}

per quanto riguarda 'eliminazione' esso può restituire un valore booleano non valido, dato che nel caso il valore da eliminare non esiste nell'albero, esso ritorna lo stesso 'true', quindi da implementare meglio, come ad esempio:


bool eliminazione(nodo* &p,int val){
    nodo *rd,*rs;
    if(p==NULL) retrun false;
    if(p->dato==val){
        rs=p->ptrsx;
        rd=p->ptrdx;
        delete p;
        if(rd == NULL)p=rs;
        else{
            while(rd->ptrsx != NULL) rd=rd->ptrsx;
            rd->ptrsx=rs;
            p=rd;
        }
        return true;
    }else if (val>p->dato) return eliminazione(p->ptrdx,val);
    else return eliminazione(p->ptrsx,val);
}

a questo punto il main diventa:


//funzione per la dellocazione finale dell'albero, usata alla fine del main
void dealloca(nodo* &p){
    if(p!=NULL){
        dealloca(p->ptrsx);
        dealloca(p->ptrdx);
        delete p;
        p=NULL;
    }
}

int main() {
    nodo *radice = NULL;
    int scelta, num;

    do {
        printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
        scanf("%i", &scelta);   
        switch(scelta) {
            case 1: {
                ins_ord(radice);
                break;
            }case 2: {
                printf("\nAlbero:\n");
                visita(radice);
                printf("\n\n");
                break;
            }
            case 3: {
                if (radice != NULL){
                    printf("\nInserisci il numero da cancellare:\t");
                    scanf("%d", &num);
                    eliminazione(radice, num);
                } else {
                    printf("\nLa lista e' vuota.\n");
                }
                break;
            }
        }
    }while(scelta !=0);
    printf("\n Uscita in corso...");
    dealloca(radice);
    prinff("fatto.\n");
    system("PAUSE");
    return 0;
}

prova con queste modifiche e vedi se funziona.

Saetta

Pochi posts

Iscritto da: feb, 2012

Messaggi:: 10

Re: [C] - Cancellazione nodo Albero.

26 feb 2012, 02:18

Ho apportato le modifiche, e il codice finale è quindi questo:


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// #include <malloc.h>

typedef struct nodo{
    int dato;
    struct nodo *ptrsx;
    struct nodo *ptrdx;
}nodo;

int elimina(nodo** );

nodo* creazione(){
    nodo *q;
    q=(nodo*)malloc(sizeof(nodo));
    
    printf("\nInserisci un numero intero:\t");
    scanf("%i", &q->dato);
    printf("\n");
    
    q->ptrsx = NULL;
    q->ptrdx = NULL;
    
    return q;
}

void ins_ord(nodo* &p,int val) {
    if(p==NULL) p=creazione();
    else if(val > q->dato) ins_ord(p->ptrdx,val);
    else ins_ord(p->ptrsx,q);
}  

void visita(nodo *p){
    if(p != NULL){
        visita(r->ptrsx);
        printf("%i\t", r->dato);
        visita(r->ptrdx);
    }
}

bool eliminazione(nodo* &p,int val){
    nodo *rd,*rs;
    if(p==NULL) retrun false;
    if(p->dato==val){
        rs=p->ptrsx;
        rd=p->ptrdx;
        delete p;
        if(rd == NULL)p=rs;
        else{
            while(rd->ptrsx != NULL) rd=rd->ptrsx;
            rs->ptrsx=rs;
            p=rd;
        }
    }else if (p->dato >val) return eliminazione(p->ptrdx,val);
    else return eliminazione(p->ptrsx,val);
}


//funzione per la dellocazione finale dell'albero, usata alla fine del main
void dealloca(nodo* &p){
    if(p!=NULL){
        dealloca(p->ptrsx);
        dealloca(p->ptrdx);
        delete p;
        p=NULL;
    }
}

int main() {
    nodo *radice = NULL;
    int scelta, num;
    
    do {
        printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
        scanf("%i", &scelta);   
        switch(scelta) {
            case 1: {
                ins_ord(radice;
                        break;
                        }case 2: {
                            printf("\nAlbero:\n");
                            visita(radice);
                            printf("\n\n");
                            break;
                        }
                        case 3: {
                            if (radice != NULL){
                                printf("\nInserisci il numero da cancellare:\t");
                                scanf("%d", &num);
                                eliminazione(radice, num);
                            } else {
                                printf("\nLa lista e' vuota.\n");
                            }
                            break;
                        }
                        }
                        }while(scelta !=0);
                        printf("\n Uscita in corso...");
                        dealloca(radice);
                        prinff("fatto.\n");
                        system("PAUSE");
                        return 0;
                        }

Ma da diversi errori, ovvero:

Albero.c:28: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c: In function ‘visita’:
Albero.c:36: error: ‘r’ undeclared (first use in this function)
Albero.c:36: error: (Each undeclared identifier is reported only once
Albero.c:36: error: for each function it appears in.)
Albero.c: At top level:
Albero.c:42: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c:61: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c: In function ‘main’:
Albero.c:79: error: expected ‘)’ before ‘;’ token
Albero.c:81: error: expected ‘;’ before ‘}’ token

V
Vins3Xtreme
Utente Attivo
Iscritto da
dic, 2011
Messaggi:
144
Re: [C] - Cancellazione nodo Albero.
26 feb 2012, 02:20
Ho ricorretto, prova con il nuovo codice nel post di prima
S
Saetta
Pochi posts
Iscritto da
feb, 2012
Messaggi:
10
Re: [C] - Cancellazione nodo Albero.
26 feb 2012, 02:24
Ho modificai prendendo di nuovo i codici nel tuo post, ma da sempre i seguenti errori:

Albero.c:26: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c: In function ‘visita’:
Albero.c:34: error: ‘r’ undeclared (first use in this function)
Albero.c:34: error: (Each undeclared identifier is reported only once
Albero.c:34: error: for each function it appears in.)
Albero.c: At top level:
Albero.c:40: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c:60: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c: In function ‘main’:
Albero.c:78: error: expected ‘)’ before ‘;’ token
Albero.c:80: error: expected ‘;’ before ‘}’ token
V
Vins3Xtreme
Utente Attivo
Iscritto da
dic, 2011
Messaggi:
144
Re: [C] - Cancellazione nodo Albero.
26 feb 2012, 02:31
Impossibile, ho corretto in 'visita' mettendo 'p' al post di 'r' quindi ricopia quelli attuali

Saetta

Pochi posts

Iscritto da: feb, 2012

Messaggi:: 10

Re: [C] - Cancellazione nodo Albero.

26 feb 2012, 02:40

Ho modificato il codice come postato, e gli errori sono diminuiti..


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// #include <malloc.h>

typedef struct nodo{
    int dato;
    struct nodo *ptrsx;
    struct nodo *ptrdx;
}nodo;

int elimina(nodo** );

nodo* creazione(){
    nodo *q;
    q=(nodo*)malloc(sizeof(nodo));
    
    printf("\nInserisci un numero intero:\t");
    scanf("%i", &q->dato);
    printf("\n");
    
    q->ptrsx = NULL;
    q->ptrdx = NULL;
    
    return q;
}

void ins_ord(nodo* &p,int val) {
    if(p==NULL) p=creazione();
    else if(val > p->dato) ins_ord(p->ptrdx,val);
    else ins_ord(p->ptrsx,q);
}    

void visita(nodo *p){
    if(p != NULL){
        visita(p->ptrsx);
        printf("%i\t", p->dato);
        visita(p->ptrdx);
    }
}

bool eliminazione(nodo* &p,int val){
    nodo *rd,*rs;
    if(p==NULL) retrun false;
    if(p->dato==val){
        rs=p->ptrsx;
        rd=p->ptrdx;
        delete p;
        if(rd == NULL)p=rs;
        else{
            while(rd->ptrsx != NULL) rd=rd->ptrsx;
            rd->ptrsx=rs;
            p=rd;
        }
        return true;
    }else if (val>p->dato) return eliminazione(p->ptrdx,val);
    else return eliminazione(p->ptrsx,val);
}


//funzione per la dellocazione finale dell'albero, usata alla fine del main
void dealloca(nodo* &p){
    if(p!=NULL){
        dealloca(p->ptrsx);
        dealloca(p->ptrdx);
        delete p;
        p=NULL;
    }
}

int main() {
    nodo *radice = NULL;
    int scelta, num;
    
    do {
        printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
        scanf("%i", &scelta);   
        switch(scelta) {
            case 1: {
                ins_ord(radice);
                break;
            }case 2: {
                printf("\nAlbero:\n");
                visita(radice);
                printf("\n\n");
                break;
            }
            case 3: {
                if (radice != NULL){
                    printf("\nInserisci il numero da cancellare:\t");
                    scanf("%d", &num);
                    eliminazione(radice, num);
                } else {
                    printf("\nLa lista e' vuota.\n");
                }
                break;
            }
        }
    }while(scelta !=0);
    printf("\n Uscita in corso...");
    dealloca(radice);
    prinff("fatto.\n");
    system("PAUSE");
    return 0;
}

Errori:

Albero.c:28: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c:42: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c:62: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token

V
Vins3Xtreme
Utente Attivo
Iscritto da
dic, 2011
Messaggi:
144
Re: [C] - Cancellazione nodo Albero.
26 feb 2012, 02:42
Un'altra cosa, quando definisci la struttura 'nodo' leva nodo dopo struct:
```
struct nodo; //definisci prima una referenza alla struttura nodo;

typedef struct{ //<--- tolto nodo
    int dato;
    struct nodo *ptrsx;
    struct nodo *ptrdx;
}nodo;
```
S
Saetta
Pochi posts
Iscritto da
feb, 2012
Messaggi:
10
Re: [C] - Cancellazione nodo Albero.
26 feb 2012, 02:46
Modificato, ma penso che sia peggio perché gli errori sono aumentati..

Albero.c:31: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c: In function ‘visita’:
Albero.c:39: warning: passing argument 1 of ‘visita’ from incompatible pointer type
Albero.c:41: warning: passing argument 1 of ‘visita’ from incompatible pointer type
Albero.c: At top level:
Albero.c:45: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c:65: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token

Vins3Xtreme

Utente Attivo

Iscritto da: dic, 2011

Messaggi:: 144

Re: [C] - Cancellazione nodo Albero.

26 feb 2012, 02:59


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// #include <malloc.h>

typedef struct nodo{
    int dato;
    struct nodo *ptrsx;
    struct nodo *ptrdx;
}Nodo, *pNodo;

pNodo creazione(){
    pNodo q;
    q=(pNodo)malloc(sizeof(Nodo));
   
    printf("\nInserisci un numero intero:\t");
    scanf("%i", &q->dato);
    printf("\n");
   
    q->ptrsx = NULL;
    q->ptrdx = NULL;
   
    return q;
}

void ins_ord(pNodo &p,int val) {
    if(p==NULL) p=creazione();
    else if(val > p->dato) ins_ord(p->ptrdx,val);
    else ins_ord(p->ptrsx,q);
}   

void visita(pNodo p){
    if(p != NULL){
        visita(p->ptrsx);
        printf("%i\t", p->dato);
        visita(p->ptrdx);
    }
}

bool eliminazione(pNodo &p,int val){
    pNodo rd,rs;
    if(p==NULL) retrun false;
    if(p->dato==val){
        rs=p->ptrsx;
        rd=p->ptrdx;
        delete p;
        if(rd == NULL)p=rs;
        else{
            while(rd->ptrsx != NULL) rd=rd->ptrsx;
            rd->ptrsx=rs;
            p=rd;
        }
        return true;
    }else if (val > p->dato) return eliminazione(p->ptrdx,val);
    else return eliminazione(p->ptrsx,val);
}

//funzione per la dellocazione finale dell'albero, usata alla fine del main
void dealloca(pNodo &p){
    if(p!=NULL){
        dealloca(p->ptrsx);
        dealloca(p->ptrdx);
        delete p;
        p=NULL;
    }
}

int main() {
    pNodo radice = NULL;
    int scelta, num;
   
    do {
        printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
        scanf("%i", &scelta);   
        switch(scelta) {
            case 1: {
                ins_ord(radice);
                break;
            }case 2: {
                printf("\nAlbero:\n");
                visita(radice);
                printf("\n\n");
                break;
            }
            case 3: {
                if (radice != NULL){
                    printf("\nInserisci il numero da cancellare:\t");
                    scanf("%d", &num);
                    eliminazione(radice, num);
                } else {
                    printf("\nLa lista e' vuota.\n");
                }
                break;
            }
        }
    }while(scelta !=0);
    printf("\n Uscita in corso...");
    dealloca(radice);
    prinff("fatto.\n");
    system("PAUSE");
    return 0;
}

S
Saetta
Pochi posts
Iscritto da
feb, 2012
Messaggi:
10
Re: [C] - Cancellazione nodo Albero.
26 feb 2012, 03:04
A me da sempre parecchi errori anche con questo codice..

Albero.c:10: error: expected specifier-qualifier-list before ‘nodo’
Albero.c: In function ‘creazione’:
Albero.c:22: error: ‘nodo’ has no member named ‘ptrsx’
Albero.c:23: error: ‘nodo’ has no member named ‘ptrdx’
Albero.c: At top level:
Albero.c:28: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c: In function ‘visita’:
Albero.c:36: error: ‘nodo’ has no member named ‘ptrsx’
Albero.c:38: error: ‘nodo’ has no member named ‘ptrdx’
Albero.c: At top level:
Albero.c:42: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c:61: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
V
Vins3Xtreme
Utente Attivo
Iscritto da
dic, 2011
Messaggi:
144
Re: [C] - Cancellazione nodo Albero.
26 feb 2012, 03:15
Allora, ho modificato di nuovo il codice, vedi se da ancora errori
S
Saetta
Pochi posts
Iscritto da
feb, 2012
Messaggi:
10
Re: [C] - Cancellazione nodo Albero.
26 feb 2012, 03:27
Mi da sempre quest 3 errori..
forse non "capisce" quella & delle 3 funzioni.. probabile?

Albero.c:26: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c:40: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
Albero.c:59: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
skynet
Utente Famoso
Iscritto da
lug, 2010
Messaggi:
3060
Re: [C] - Cancellazione nodo Albero.
26 feb 2012, 11:06
In C non è permesso il passaggio per riferimento nelle funzioni. Bisogna far uso dei puntatori.

Saetta

Pochi posts

Iscritto da: feb, 2012

Messaggi:: 10

Re: [C] - Cancellazione nodo Albero.

26 feb 2012, 12:29

Ho messo i puntatori al posto dei riferimenti, ho modificato qualcosa (funzione ins_ord e ins_bin, main), però non mi elimina il valore che inserisco io..
Ma ogni volta mi elimina la radice, anche se il valore inserito non esiste.. perché?


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// #include <malloc.h>

typedef struct nodo{
    int dato;
    struct nodo *ptrsx;
    struct nodo *ptrdx;
}nodo;

nodo* creazione(){
    nodo *q;
    q = malloc(sizeof(nodo));
    
    printf("\nInserisci un numero intero:\t");
    scanf("%i", &q->dato);
    printf("\n");
    
    q->ptrsx = NULL;
    q->ptrdx = NULL;
    
    return q;
}

void ins_ord(nodo *p,nodo *q)
{
    nodo *r;
    r = p;
    if(r->dato > q->dato) {
        if(r->ptrsx == NULL) {
            r->ptrsx = q;
        }else {
            ins_ord(r->ptrsx,q);
        }
    } else {
        if(r->ptrdx == NULL) {
            r->ptrdx = q;
        } else {
            ins_ord(r->ptrdx, q);
        }
    }
}

nodo* ins_bin(nodo *p) {
    nodo *q;
    q = creazione();
    
    if(p == NULL) {
        return q;
    } else {
        ins_ord(p, q);
    }
    
    return p;
}



void visita(nodo *p){
    if(p != NULL){
        visita(p->ptrsx);
        printf("%i\t", p->dato);
        visita(p->ptrdx);
    }
}

bool eliminazione(nodo *p,int val){
    nodo *rd,*rs;
    if(p==NULL) return false;
    if(p->dato==val){
        rs=p->ptrsx;
        rd=p->ptrdx;
        free(p);
        if(rd == NULL)p=rs;
        else{
            while(rd->ptrsx != NULL) rd=rd->ptrsx;
            rd->ptrsx=rs;
            p=rd;
        }
        return true;
    }else if (val > p->dato) return eliminazione(p->ptrdx,val);
    else return eliminazione(p->ptrsx,val);
}

//funzione per la dellocazione finale dell'albero, usata alla fine del main
void dealloca(nodo *p){
    if(p!=NULL){
        dealloca(p->ptrsx);
        dealloca(p->ptrdx);
        free(p);
        p=NULL;
    }
}

int main()
{
    nodo *radice = NULL;
    int scelta = 1, num;
    while(scelta != 0) {
        printf("1 - Inserimento ordinato;\n2 - Visita albero;\n3 - Cancella elemento;\n0 - Esci;\n\nScelta:\t");
        scanf("%i", &scelta);
        
        switch(scelta) {
            case 1: {
                radice=ins_bin(radice);
                
                break;
            }
            case 2: {
                printf("\nAlbero:\n");
                visita(radice);
                printf("\n\n");
                
                break;
            }
            case 3: {
                if(radice != NULL){
                    printf("\nInserisci il numero da cancellare:\t");
                    scanf("%d", &num);
                    radice->ptrsx=NULL;
                    radice->ptrdx=NULL;
                    eliminazione(radice, num);
                } else {
                    printf("\nLa lista e' vuota.\n");
                }
                
                break;
            }
        }
    }
}

Devi accedere o registrarti per scrivere nel forum

18 risposte