|
|
|
|
Strumenti |
22-08-2020, 16:31 | #1 |
Junior Member
Iscritto dal: Aug 2020
Messaggi: 3
|
[C] Segmentation Fault
Salve! Spero di aver aperto la discussione in modo giusto. Ho bisogno di aiuto.
Dunque sto implementando un Binary Search Tree con inserimento e ricerca, e fin qui tutto bene, dopo di che mi è stato chiesto di implementare anche una versione modificata della ricerca che dovrebbe stampare a video tutti i numeri presenti nell'albero compresi fra k1 e k2(valori forniti dall'utente in input). Ora il problema è proprio qui, a un certo punto va in segmentation fault ma non riesco a capire quale sia il problema in quanto il codice è identico allo pseudocodice fornito. Vi metto qui di seguito il pezzo di codice in questione(chiedo scusa nel caso fosse molto ma continua a sbucarmi il segmentation sempre in un punto diverso). Codice:
void withinRange(BST **root, int k1, int k2){ BST *x = (BST*)malloc(sizeof(BST)); BST *y = (BST*)malloc(sizeof(BST)); if(k1 == k2){ printf("%d\n", k1); return; } *x = BSTsearch(&root, k1); *y = BSTsearch(&root, k2); printf("%d\n", x->data); while(!found){ inOrderTreeWalkWithCheck(&root, x->right, y); *x = treeSuccessorAsAncestor(&root, x); if ( x == y ){ found = 1; } if ((x != NULL) && (!found)){ printf("%d\n", x->data); } } printf("%d\n", y->data); found = 0; } void inOrderTreeWalkWithCheck(BST **root, BST *x, BST *y){ if (x != NULL){ if(x == y){ inOrderTreeWalk(y); found = 1; return; } }else{ inOrderTreeWalkWithCheck(&root, x->left, y); if(!found){ printf("%d\n", x->data); inOrderTreeWalkWithCheck(&root, x->right, y); } } } void inOrderTreeWalk(BST *y){ if(y != NULL){ inOrderTreeWalk(y->left); printf("%d\n", y->data); inOrderTreeWalk(y->right); } } BST treeSuccessorAsAncestor(BST **root, BST *x){ BST *y = (BST*)malloc(sizeof(BST)); y = x->parent; while ((y != NULL) && (x == y->right)){ x = y; y = y->parent; } return *y; } |
23-08-2020, 18:14 | #2 |
Senior Member
Iscritto dal: Nov 2005
Messaggi: 2745
|
Scusa ma non ho avuto tempo di analizzare fino in fondo tutto il codice, ti scrivo quello che ho notato.
Nel metodo inOrderTreeWalkWithCheck accedi agli attributi di x nel ramo else in cui x è sicuramente NULL. Note a parte non legate al segmentation fault: * Ci sono dei malloc ma non ci sono free, quindi si creano dei memory leak. * Ci sono delle variabili globali (found), e questo rende difficile seguire il flusso. |
24-08-2020, 07:34 | #3 |
Senior Member
Iscritto dal: Apr 2005
Messaggi: 2993
|
Un altro consiglio: COMMENTA.
Metti i commenti al codice che per quanto possa sembrare banale torna sempre utile quando poi ci metti mano.. |
26-08-2020, 15:55 | #4 | |
Junior Member
Iscritto dal: Aug 2020
Messaggi: 3
|
Quote:
Per quanto riguarda i malloc aggiungo immediatamente i free che ho completamente scordato. Found mi è stata richiesta come una variabile globale settata a 0, che comunque viene usata per la prima volta all'interno di withinrange |
|
27-08-2020, 08:22 | #5 |
Senior Member
Iscritto dal: Nov 2005
Messaggi: 2745
|
BST come è definito? Puoi riportare tutto il codice aggiornato?
|
28-08-2020, 20:34 | #6 | |
Junior Member
Iscritto dal: Aug 2020
Messaggi: 3
|
Quote:
E' un po' lungo, spero non sia un problema. Ho anche scoperto che se inserisco k1 e k2 uguali il programma va senza problemi, va in segmentation sono quando sono diversi. Codice:
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <time.h> #define NUMOP 500 int found = 0; typedef struct BST{ int data; struct BST* parent; struct BST* left; struct BST* right; } BST; BST* root = NULL; BST newNode(int value); BST BSTinsert(BST **root, int value); BST BSTsearch(BST *x, int value); void withinRange(BST **root, int k1, int k2); void inOrderTreeWalkWithCheck(BST **root, BST *x, BST *y); void inOrderTreeWalk(BST *y); BST treeSuccessorAsAncestor(BST **root, BST *x); int main(){ clock_t start, end; int iterazione, k1, k2, i; double BST=0, BSTS=0, BSTW=0; double mediaBST; FILE * risultatiBST; srand(1); risultatiBST=fopen("risultatiBST.txt","w"); if (risultatiBST==NULL) { printf ("ERRORE nell'apertura del file"); return(1); } printf ("Inserisci k1: "); scanf ("%d", &k1); printf("Inserisci k2:"); scanf("%d", &k2); printf ("BST\n"); int inserimento, ricerca, withinrange; for(i = 1; i<=NUMOP; i++){ inserimento=(70*NUMOP)/100; start = clock(); for (iterazione = 1; iterazione <= inserimento; iterazione++){ int value = rand(); BSTinsert(&root, value); //end = clock(); } ricerca = (15*NUMOP)/100; for(iterazione = 1; iterazione<=ricerca; iterazione++){ //start = clock(); int value = rand(); BSTsearch(&root, value); //end = clock(); //BSTS = BSTS + (double) (end-start)/CLOCKS_PER_SEC; } withinrange = (15*NUMOP)/100; for(iterazione = 1; iterazione <= withinrange; iterazione++){ //start = clock(); withinRange(&root, k1, k2); //BSTW = BSTW + (double) (end-start)/CLOCKS_PER_SEC; } end = clock(); BST = BSTW + (double) (end-start)/CLOCKS_PER_SEC; mediaBST=BST/NUMOP; printf ("%d\t %f\n",i, mediaBST); fprintf(risultatiBST,"%d\t %f\n", i, mediaBST); } fclose(risultatiBST); } BST newNode(int value){ BST *temp = (BST*)malloc(sizeof(BST)); temp->data = value; temp->left = NULL; temp->right = NULL; free(temp); return *temp; } // A utility function to insert a new // Node with given key in BST BST BSTinsert(BST **root, int value) { // Create a new Node containing // the new element BST *newnode = (BST*)malloc(sizeof(BST)); *newnode = newNode(value); // Pointer to start traversing from root and // traverses downward path to search // where the new node to be inserted BST *x = root; // Pointer y maintains the trailing // pointer of x BST *y = NULL; while (x != NULL) { y = x; if (value < x->data) x = x->left; else x = x->right; } // If the root is NULL i.e the tree is empty // The new node is the root node if (y == NULL) y = newnode; // If the new key is less then the leaf node key // Assign the new node to be its left child else if (value < y->data) y->left = newnode; // else assign the new node its right child else y->right = newnode; // Returns the pointer where the // new node is inserted return *y; } BST BSTsearch(BST *x, int value){ if ((x == NULL) || (x->data = value)){ return *x; } if(value<x->data){ return BSTsearch(x->left, value); }else{ return BSTsearch(x->right, value); } } //withinRange void withinRange(BST **root, int k1, int k2){ BST *x = (BST*)malloc(sizeof(BST)); BST *y = (BST*)malloc(sizeof(BST)); if(k1 == k2){ printf("%d\n", k1); return; } *x = BSTsearch(&root, k1); *y = BSTsearch(&root, k2); printf("%d\n", x->data); while(!found){ inOrderTreeWalkWithCheck(&root, x->right, y); *x = treeSuccessorAsAncestor(&root, x); if ( x == y ){ found = 1; } if ((x != NULL) && (!found)){ printf("%d\n", x->data); } } printf("%d\n", y->data); found = 0; free(x); free(y); } void inOrderTreeWalkWithCheck(BST **root, BST *x, BST *y){ if (x != NULL){ if(x == y){ inOrderTreeWalk(y); found = 1; return; }else{ inOrderTreeWalkWithCheck(&root, x->left, y); if(!found){ printf("%d\n", x->data); inOrderTreeWalkWithCheck(&root, x->right, y); } } } } void inOrderTreeWalk(BST *y){ if(y != NULL){ inOrderTreeWalk(y->left); printf("%d\n", y->data); inOrderTreeWalk(y->right); } } BST treeSuccessorAsAncestor(BST **root, BST *x){ BST *y = (BST*)malloc(sizeof(BST)); y = x->parent; while ((y != NULL) && (x == y->right)){ printf("ciao"); x = y; y = y->parent; } free(y); return *y; } Ultima modifica di Osyriis_ : 28-08-2020 alle 20:44. |
|
28-08-2020, 21:23 | #7 | |
Member
Iscritto dal: Dec 2006
Messaggi: 33
|
Quote:
Direi che ci sono già qui potenziali problemi di accesso alla memoria nella costruzione dell'albero. Ps: Sinceramente, ad un primo sguardo a qualche implementazione e alle interfacce, temo che ci siano inoltre altri leaks di memoria e problemi in genere. Purtroppo è risaputo che il linguaggio C richiede molta attenzione da questo punto di vista. Secondo me conviene che se studi una implementazione di un binary search tree già fatta da altri (ad es. https://github.com/fbuihuu/libtree) per avere una buona base di partenza, prendendo spunti per riscriverla e estenderla per risolvere il tuo problema. Ultima modifica di Lampo89 : 28-08-2020 alle 21:33. |
|
30-08-2020, 17:17 | #8 |
Senior Member
Iscritto dal: Nov 2005
Messaggi: 2745
|
Aggiungo:
1) alla riga 144, nella funzione BSTsearch: non puoi restituire *x se x == NULL devi prendere in considerazione il fatto che BSTsearch potrebbe non trovare il valore cercato e quindi deve poter restituire NULL. Per farlo il tipo restituito non può essere BST ma deve essere BST* (con tutte le modifiche che questo implica) 2) nella funzione treeSuccessorAsAncestor c'è lo stesso problema indicato da Lampo89 per la funzione newNode (use-after-free) |
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 05:45.