[C] - Cancellazione nodo Albero.

di
Saetta
il
18 risposte

18 Risposte - Pagina 2

  • S
    Saetta
    Pochi posts
    Iscritto da
    feb, 2012
    Messaggi:
    10

    Re: [C] - Cancellazione nodo Albero.

    Sbaglio forse quando richiamo la funzione elimina(radice, num); nel main?
  • S
    Saetta
    Pochi posts
    Iscritto da
    feb, 2012
    Messaggi:
    10

    Re: [C] - Cancellazione nodo Albero.

    
#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 = 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!=NULL)
    {
        if(r->ptrsx != NULL) {    // controllare il padre
            visita(r->ptrsx);
        }
        
        printf("%i", r->dato);
        printf("\t");
        
        if(r->ptrdx != NULL) {
            visita(r->ptrdx);
        }
    }
}

nodo* ritIndFoglia(nodo *p){
    if(p->ptrsx == NULL && p->ptrdx == NULL)
        return p;
    else if(p->ptrsx!=NULL)
        return ritIndFoglia(p->ptrsx);
    else
        return ritIndFoglia(p->ptrdx);
}
void scambiaValori(nodo *p1, nodo* p2){
    int temp=p1->dato;
    p1->dato=p2->dato;
    p2->dato=temp;
}
nodo* elimFoglia(nodo *p){
    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);
                    
                    nodo* foglia=ritIndFoglia(radice);
                    scambiaValori(radice,foglia);
                    elimFoglia(foglia);
                } else {
                    printf("\nLa lista e' vuota.\n\n");
                }
                
                break;
            }
        }
    }
}
    perché mi non mi elimina i valori? O.o
  • vbextreme
    vbextreme
    Molto attivo
    Iscritto da
    feb, 2012
    Messaggi:
    1143

    Re: [C] - Cancellazione nodo Albero.

    Il codice postato non viene neppure compilato!
    Il primo consiglio è di dotarsi di un buon manuale quale il K&R

    La struttura è definita in modo errato,ridefinisci due volte nodo,quale struct nodo e typedef nodo! 
    
typedef struct _nodo
{
    int dato;
    struct _nodo *prev;
    struct _nodo *next;
}nodo;

nodo headerlist;
    Hai creato il prototipo elimina ma dov'è la funzione?
    Hai solo la funzione che elimina la foglia per di piu errato perchè non dereferenzi il ramo che la punta.
    
...
nodo *foglia=ramo->next;
free(foglia);
ramo->next=NULL;
    anche se lo standard dice che malloc non necessita di casting esplicito è buona norma usarlo:
    
int *dinamicval=(int*)malloc(sizeof(int)*1);
  • I
    ixamit
    Molto attivo
    Iscritto da
    ott, 2009
    Messaggi:
    1027

    Re: [C] - Cancellazione nodo Albero.

    Giusto per rendere le cose più incasinate del normale...
    infatti la cancellazione ricorsiva del nodo non è di facile implementazione e facendola alla tua maniera c'è da spararsi un colpo in testa.
    Ovviamente non ho inventato niente di nuovo, nulla di ciò che che è già stato scritto e riscritto, solo che l'ho modificato sia nella restituzione della radice senza agire internamente (molto più semplice), sia nella parte di ricerca key che insita nella cancellazione.
    La funzione ricorsiva seguente è stata debuggata ad un livello superficiale con il memory profiler valgrind considerando le tre casistiche tipiche della rimozione del nodo (senza figli, un figlio, due figli), la disposizione dell inserimento e della cancellazione.... cmq verificala meglio nella sezione doppio figlio + modifica radice.
    
nodo *eliminazione(nodo *p, int val)
{
  nodo *old=p;

  if (val < p->dato )
	p->ptrsx=eliminazione(p->ptrsx,val);
  else if (val > p->dato )
	p->ptrdx=eliminazione(p->ptrdx,val);
  else
  {
	if (p->ptrsx==NULL)
	{
	  p=p->ptrdx;
	  free (old);
	}
	else if (p->ptrdx==NULL)
	{
	  p=p->ptrsx;
	  free (old);
	}
	else
	{
	  nodo *prev = p->ptrsx;
	  while (prev->ptrdx)	prev = prev->ptrdx;
	  int tmp = prev->dato;
	  prev->dato = p->dato;
	  p->dato = tmp;
	  
	  p->ptrsx=eliminazione(prev, val);
	}
  }
  return p;
}
Devi accedere o registrarti per scrivere nel forum
18 risposte