Funzione free non funzionante

di il
14 risposte

Funzione free non funzionante

Ciao a tutti, sto risolvendo il problema della rimozione di un nodo da un albero.
L'esercizio non è ancora completo,ma ho un problema sulla rimozione sul nodo foglia nella funzione deleteNode dove la funzione free non mi libera la memoria.
Faccio un esempio, se inserisco il valore 49 che coincide con una foglia non lo elimina dalla memoria.
Cosa può essere?
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct treeNode {
	struct treeNode *leftPtr, *rightPtr;
	int data;
} TreeNode;

typedef TreeNode *TreeNodePtr;

void insertNode(TreeNodePtr *, int);
void inOrder(TreeNodePtr);
void preOrder(TreeNodePtr);
void postOrder(TreeNodePtr);
int depth(TreeNodePtr);
void deleteNode(TreeNodePtr , int);
void *scrollRight(TreeNodePtr);
void *binaryTreeSearch(TreeNodePtr, int);

int main() {
	
	int i, item[20] = {14,71,29,74,33,92,82,76,35,99,55,84,78,13,68,20,27,8,2,49} , item1;
	TreeNodePtr rootPtr = NULL;

	srand(time(NULL));

	for (i = 0; i < 20;i++) {
		item1 = item[i];
		insertNode(&rootPtr, item1);
	}
	
	printf("\nStampa preOrder:\n");
	preOrder(rootPtr);
	
	printf("\n\nStampa inOrder:\n");
	inOrder(rootPtr);
	
	printf("\n\nStampa postOrder:\n");
	postOrder(rootPtr);

	printf("\n\nL'albero è composto da %d livelli\n", depth(rootPtr));
	
	printf("\nChe valore vuoi eliminare? ");
	scanf("%d", &item1);
	deleteNode(rootPtr, item1);
	
	printf("\nStampa preOrder:\n");
	preOrder(rootPtr);
	
	printf("\n\nStampa inOrder:\n");
	inOrder(rootPtr);
	
	printf("\n\nStampa postOrder:\n");
	postOrder(rootPtr);

	printf("\n\nL'albero è composto da %d livelli\n", depth(rootPtr));
	return 0;
}

void insertNode(TreeNodePtr *treePtr, int value) {

	if(*treePtr == NULL) {
		*treePtr = malloc(sizeof(TreeNode));
		if(*treePtr != NULL) {
			(*treePtr)->data  = value;
			(*treePtr)->leftPtr = NULL;
			(*treePtr)->rightPtr = NULL;
		}
	}
	else {
		if(value < (*treePtr)->data)
			insertNode(&(*treePtr)->leftPtr, value);
		else if (value > (*treePtr)->data)
			insertNode(&(*treePtr)->rightPtr, value);
		else {
			printf("DUP ");
		}
	}
}

void inOrder(TreeNodePtr treePtr) {
	if(treePtr != NULL) {
		inOrder(treePtr->leftPtr);
		printf("%3d", treePtr->data);
		inOrder(treePtr->rightPtr);
	}
}

void preOrder(TreeNodePtr treePtr) {
	if(treePtr != NULL) {
		printf("%3d", treePtr->data);
		preOrder(treePtr->leftPtr);
		preOrder(treePtr->rightPtr);
	}
}

void postOrder(TreeNodePtr treePtr) {
	if(treePtr != NULL) {
		postOrder(treePtr->leftPtr);
		postOrder(treePtr->rightPtr);
		printf("%3d", treePtr->data);
	}
}

int depth(TreeNodePtr treePtr) {

	int s, d;

	if(treePtr == NULL)
		return -1;  //nodo radice parte da 0

	s = depth(treePtr->leftPtr);
	d = depth(treePtr->rightPtr);
	if(s > d)
		return ++s;
	else
		return ++d;
}

void deleteNode(TreeNodePtr treePtr, int value) {

	TreeNodePtr temp;
	if((temp = binaryTreeSearch(treePtr, value))) {
		printf("Valore trovato\n");
		if(temp->leftPtr == NULL && temp->rightPtr == NULL) {
			free(temp);                     //funzionamento anomalo
		}
	}
	else printf("Valore non trovato\n");
}

void *binaryTreeSearch(TreeNodePtr treePtr, int value) {
	if(treePtr != NULL) {
		if(value < treePtr->data)
			return binaryTreeSearch(treePtr->leftPtr, value);
		else if (value > treePtr->data)
			return binaryTreeSearch(treePtr->rightPtr, value);
		else
			return treePtr;
	}
	return NULL;
}

void *scrollRight(TreeNodePtr treePtr) {

	while(treePtr->rightPtr != NULL)
		treePtr = treePtr->rightPtr;

	return treePtr;
}

14 Risposte

  • Re: Funzione free non funzionante

    Non ho capito da cosa deduci che la free non funziona ...
  • Re: Funzione free non funzionante

    Faccio eseguire il programma,immetto il valore da eliminare(in questo caso immetto un valore che è posizionato nella foglia), ma non lo elimina, ho provato a fare un debug con DDD e vedo che la free non funziona
  • Re: Funzione free non funzionante

    Cosa ti aspetti dalla free? Che vengano cancellati i dati? La free non cancella nulla ma dealloca la memoria ... quindi non capisco ancora perché dici che la free non funziona.
  • Re: Funzione free non funzionante

    Negli altri esercizi ho usato sempre la free con una variabile temporanea e funzionava, qua no
  • Re: Funzione free non funzionante

    Lasciamo perdere ...

    La free funziona ma il puntatore del nodo che punta alla foglia non è stato aggiornato.
  • Re: Funzione free non funzionante

    Dovrei aggiornare prima il puntatore del padre del nodo a null e poi free, e come faccio a posizionarmi sul padre del nodo?
  • Re: Funzione free non funzionante

    Devi cambiare il codice. Non devi utilizzare quella funzione di ricerca perché non hai l'informazione del padre.

    Devi riscrivere una ricerca apposita per la cancellazione del nodo foglia in modo che cerchi il nodo e tenga traccia del padre.
  • Re: Funzione free non funzionante

    Allora anticipo la binaryTreeSearch di fermarsi sul padre e vedremo cosa succede, grazie per il momento
  • Re: Funzione free non funzionante

    Ho risolto è sembra funzionare
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    typedef struct treeNode {
    	struct treeNode *leftPtr, *rightPtr;
    	int data;
    } TreeNode;
    
    typedef TreeNode *TreeNodePtr;
    
    void insertNode(TreeNodePtr *, int);
    void inOrder(TreeNodePtr);
    void preOrder(TreeNodePtr);
    void postOrder(TreeNodePtr);
    int depth(TreeNodePtr);
    void deleteNode(TreeNodePtr *, int);
    void *scrollRight(TreeNodePtr);
    
    int main() {
    	
    	int i, item;
    	TreeNodePtr rootPtr = NULL;
    
    	srand(time(NULL));
    
    	for (i = 0; i < 20;i++)
    		insertNode(&rootPtr, 1 + rand() % 99);
    
    	printf("\nStampa preOrder:\n");
    	preOrder(rootPtr);
    	
    	printf("\n\nStampa inOrder:\n");
    	inOrder(rootPtr);
    	
    	printf("\n\nStampa postOrder:\n");
    	postOrder(rootPtr);
    
    	printf("\n\nL'albero è composto da %d livelli\n", depth(rootPtr));
    	
    	printf("\nChe valore vuoi eliminare? ");
    	scanf("%d%*c", &item);
    	deleteNode(&rootPtr, item);
    	
    	printf("\nStampa preOrder:\n");
    	preOrder(rootPtr);
    	
    	printf("\n\nStampa inOrder:\n");
    	inOrder(rootPtr);
    	
    	printf("\n\nStampa postOrder:\n");
    	postOrder(rootPtr);
    
    	printf("\n\nL'albero è composto da %d livelli\n", depth(rootPtr));
    	return 0;
    }
    
    void insertNode(TreeNodePtr *treePtr, int value) {
    
    	if(*treePtr == NULL) {
    		*treePtr = malloc(sizeof(TreeNode));
    		if(*treePtr != NULL) {
    			(*treePtr)->data  = value;
    			(*treePtr)->leftPtr = NULL;
    			(*treePtr)->rightPtr = NULL;
    		}
    	}
    	else {
    		if(value <= (*treePtr)->data)
    			insertNode(&(*treePtr)->leftPtr, value);
    		else if (value > (*treePtr)->data)
    			insertNode(&(*treePtr)->rightPtr, value);
    	}
    }
    
    void inOrder(TreeNodePtr treePtr) {
    	if(treePtr != NULL) {
    		inOrder(treePtr->leftPtr);
    		printf("%3d", treePtr->data);
    		inOrder(treePtr->rightPtr);
    	}
    }
    
    void preOrder(TreeNodePtr treePtr) {
    	if(treePtr != NULL) {
    		printf("%3d", treePtr->data);
    		preOrder(treePtr->leftPtr);
    		preOrder(treePtr->rightPtr);
    	}
    }
    
    void postOrder(TreeNodePtr treePtr) {
    	if(treePtr != NULL) {
    		postOrder(treePtr->leftPtr);
    		postOrder(treePtr->rightPtr);
    		printf("%3d", treePtr->data);
    	}
    }
    
    int depth(TreeNodePtr treePtr) {
    
    	int s, d;
    
    	if(treePtr == NULL)
    		return -1;  //nodo radice parte da 0
    
    	s = depth(treePtr->leftPtr);
    	d = depth(treePtr->rightPtr);
    	if(s > d)
    		return ++s;
    	else
    		return ++d;
    }
    
    void deleteNode(TreeNodePtr *treePtr, int value) {
    
    	if(*treePtr == NULL)
    		printf("Nodo non trovato\n");
    	else if((*treePtr)->data == value) {
    		TreeNodePtr temp = *treePtr;
    		if((*treePtr)->rightPtr == NULL && (*treePtr)->leftPtr == NULL)
    			*treePtr = NULL;
    		else if ((*treePtr)->rightPtr == NULL)
    			*treePtr = (*treePtr)->leftPtr;
    		else if ((*treePtr)->leftPtr == NULL)
    			*treePtr = (*treePtr)->rightPtr;
    		else {
    			*treePtr = scrollRight((*treePtr)->leftPtr);
    			(*treePtr)->rightPtr = temp->rightPtr;
    			if(*treePtr != temp->leftPtr)
    				(*treePtr)->leftPtr = temp->leftPtr;
    		}
    		free(temp);
    		printf("Nodo eliminato\n");
    	}
    	else if(value > (*treePtr)->data)
    		deleteNode(&(*treePtr)->rightPtr, value);
    	else if(value < (*treePtr)->data)
    		deleteNode(&(*treePtr)->leftPtr, value);
    }
    
    void *scrollRight(TreeNodePtr treePtr) {
    
    	TreeNodePtr precedente = NULL;
    
    	while(treePtr->rightPtr != NULL) {
    		precedente = treePtr;
    		treePtr = treePtr->rightPtr;
    	}
    
    	if(precedente != NULL)
    		precedente->rightPtr = treePtr->leftPtr;
    
    	return treePtr;
    }
  • Re: Funzione free non funzionante

    1) non c'è test su malloc per mancata allocazione (in generale), non fa nulla

    2) come primo approccio logga tutte le malloc (cioè fai scrivere a video ALLOCO ELEMENTO X)
    Poi fai una visita (o meglio tutte le visitie) e logga le FREE (cioè prima di fare free DEALLOCO ELEMENTO X)
    Poi controlla che le due liste corrispondano (per evitare memory leak)

    3) potresti adottare metodologie di test un "pochino" migliori, ma inizia con 2
  • Re: Funzione free non funzionante

    La funzione insertnode e copiata pari pari dal libro è l'ultima riga del codice
     if(*treePtr == NULL) {
          *treePtr = malloc(sizeof(TreeNode));
          if(*treePtr != NULL) {
    penso che controlli le malloc.

    La seconda non lo capita.
  • Re: Funzione free non funzionante

    Con qualcosa del genere,ti basta fare delle piccole modifiche.
    
    #include <errno.h>
    #include "array.h"
    
    #define DEBUG
    #define GARBAGE_VALUE (0xCC)
    
    #ifdef DEBUG
    #include <stdio.h>
    #include <string.h>
    #endif
    
    /*Crea un array dinamico*/
    bool create_dynamic_array(mem_block_t *block)
    {
            /*Controlliamo gli argomenti*/
            if(NULL != block && NULL == block->to_mem && 1 < block->size)
            {
                    #ifdef DEBUG
                    (void)puts("INFO: file: array.c | func: create_dynamic_array | success: yes");
                    (void)puts("INFO: all arguments are valid");
                    #endif
                    
                    /*Allochiamo lo spazio in memoria*/
                    size_t size_in_bytes = (sizeof(int) * block->size);
                    block->to_mem = malloc(size_in_bytes);
                    
                    /*Se block->to_mem <> NULL*/
                    if(NULL != block->to_mem)                
                    {
                            #ifdef DEBUG
                            (void)puts("INFO: file: array.c | func: create_dynamic_array | success: yes");
                            (void)puts("INFO: malloc() success");
                            memset(block->to_mem,GARBAGE_VALUE,size_in_bytes);
                            #endif
                            /*ok*/
                            return true;
                    }
                    else
                    {
                            #ifdef DEBUG
                            (void)puts("ERROR: file: array.c | func: create_dynamic_array | success: no");
                            (void)puts("REASON: malloc failure");
                            #endif
                            /*altrimenti abbiamo un errore*/
                            errno = ENOBUFS;
                            return false;
                    }
                    
            }
            else
            {
                    #ifdef DEBUG
                    (void)puts("ERROR: file: array.c | func: create_dynamic_array | success: no");
                    printf("REASON: ");
                    if(NULL == block)
                    {
                            printf("Invalid pointer:block is NULL\n");
                    }
                    else
                    {
                            if(NULL != block->to_mem)
                            {
                                    printf("Possible memory leak avoided: block->to_mem is not NULL\n");
                            }
                            else
                            {
                                    printf("Invalid size in block->size: it must be greater than 1\n");
                            }
                    }
                    #endif
                    /*Argomenti non validi*/
                    errno = EINVAL;
                    return false;
            }
    }
    /*Libera lo spazio allocato da create_dynamic_array*/
    bool delete_dynamic_array(mem_block_t *block)
    {
             /*Controlliamo gli argomenti*/
            if(NULL != block && NULL != block->to_mem && 1 < block->size)
            {
                    #ifdef DEBUG
                    (void)puts("INFO: file: array.c | func: delete_dynamic_array | success: yes");
                    (void)puts("INFO: all arguments are valid");
                    size_t size_in_bytes = (sizeof(int) * block->size);
                    memset(block->to_mem,GARBAGE_VALUE,size_in_bytes);
                    #endif
                    
                    /*Deallochiamo lo spazio in memoria*/
                    free(block->to_mem);
                    block->to_mem = NULL;
                   
                    #ifdef DEBUG
                    (void)puts("INFO: file: array.c | func: delet_dynamic_array | success: yes");
                    (void)puts("INFO: free() success");
                    printf("INFO: block->to_mem address is %p\n",block->to_mem);
                    #endif
                   
                    return true;
            }
            else
            {
                    #ifdef DEBUG
                    (void)puts("ERROR: file: array.c | func: delete_dynamic_array | success: no");
                    printf("REASON: ");
                    if(NULL == block)
                    {
                            printf("Invalid pointer:block is NULL\n");
                    }
                    else
                    {
                            if(NULL == block->to_mem)
                            {
                                    printf("Invalid pointer: block->to_mem is NULL\n");
                            }
                            else
                            {
                                    printf("Invalid size in block->size: it must be greater than 1\n");
                            }
                    }
                    #endif
                    /*Argomenti non validi*/
                    errno = EINVAL;
                    return false;
            }
    }
    
    Header
    
    #include <stdbool.h>
    #include <stdlib.h>
    
    typedef struct 
    {
    	int *to_mem;
    	size_t size;
    }
    mem_block_t;
    
    
    bool create_dynamic_array(mem_block_t *block);
    bool delete_dynamic_array(mem_block_t *block);
    
  • Re: Funzione free non funzionante

    Scusa l'ignoranza, se to_mem e un puntatore a int, come e possibile allocare una memoria arbitrariamente grande con
    size_t size_in_bytes = (sizeof(int) * block->size);
    block->to_mem = malloc(size_in_bytes);
  • Re: Funzione free non funzionante

    La dimensione la passi a questa struct
    
    typedef struct
    {
       int *to_mem;
       size_t size;
    }
    mem_block_t;
    
    Per esempio
    
    #include "array.h"
    int main(void)
    {
        mem_block_t block = {NULL,10};
        bool success = create_dynamic_array(&block);
        if(true == success)
        {
            printf("Array created\n");
            success = delete_dynamic_array(&block);
            printf("Memory%sfreed\n",success ? " " : " not ");
        }
        else
        {
            printf("Unable to create a dynamic array\n");
           return EXIT_FAILURE;
        }
        return EXIT_SUCCESS;
    }
    
Devi accedere o registrarti per scrivere nel forum
14 risposte