Problem mit Quadtree Funktion



  • Hallo Community

    Ich habe mich seit kurzem dazu entschieden auf C umzusteigen und versucht eine Quadtree Datenstruktur zu schreiben. Doch bei der rekursiven Funktion qt_add_node(), die dem Quadtree neue Daten hinzufügen soll, tritt ein Fehler auf: Segmentation Fault (Core Dumped). Da ich nicht weiß woran das liegen kann wende ich mich an euch. Es wäre mir eine große Hilfe, wenn ihr mal meinen Code durchschauen könntet und mich darüber aufklärt, was ich falsch mache.

    Hier der Code:

    #include <stdio.h>
    #include <stdlib.h>
    
    struct node{
        struct node *ulc;
        struct node *urc;
        struct node *llc;
        struct node *lrc;
    };
    
    struct qtree{
        int size;
        struct node *root;
    };
    
    void qt_add_node( struct node *root, int size, int x, int y );
    
    void qt_add_node( struct node *root, int size, int x, int y ){
        int half = size / 2;
        if( y < half ){
            if( x < half ){
                if( root->ulc == NULL ){
                    root->ulc = (struct node*) malloc( sizeof( struct node ) );
                    root->ulc->ulc = NULL; root->ulc->urc = NULL; root->ulc->llc = NULL; root->ulc->lrc = NULL;
                }
                if( half > 1 );
                    qt_add_node( root->ulc, half, x, y );
            }
            else{
                if( root->urc == NULL ){
                    root->urc = (struct node*) malloc( sizeof( struct node ) );
                    root->urc->ulc = NULL; root->urc->urc = NULL; root->urc->llc = NULL; root->urc->lrc = NULL;
                }
                if( half > 1 );
                    qt_add_node( root->ulc, half, x-half, y );
            }
        }
        else{
            if( x < half ){
                if( root->llc == NULL ){
                    root->llc = (struct node*) malloc( sizeof( struct node ) );
                    root->llc->ulc = NULL; root->llc->urc = NULL; root->llc->llc = NULL; root->llc->lrc = NULL;
                }
                if( half > 1 );
                    qt_add_node( root->llc, half, x, y-half );
            }
            else{
                if( root->lrc == NULL ){
                    root->lrc = (struct node*) malloc( sizeof( struct node ) );
                    root->lrc->ulc = NULL; root->lrc->urc = NULL; root->lrc->llc = NULL; root->lrc->lrc = NULL;
                }
                if( half > 1 );
                    qt_add_node( root->lrc, half, x-half, y-half );
            }
        }
    }
    
    struct node* qt_get_node( struct node *root, int size, int x, int y ){
        int half = size / 2;
    
        if( y < half ){
            if( x < half ){
                if( root->ulc == NULL )
                    return NULL;
                else{
                    if( half > 1 )
                        return qt_get_node( root->ulc, half, x, y );
                    else
                        return root->ulc;
                }
            }
            else{
                if( root->urc == NULL )
                    return NULL;
                else{
                    if( half > 1 )
                        return qt_get_node( root->urc, half, x-half, y );
                    else
                        return root->urc;
                }
            }
        }
        else{
            if( x < half ){
                if( root->llc == NULL )
                    return NULL;
                else{
                    if( half > 1 )
                        return qt_get_node( root->llc, half, x, y-half );
                    else
                        return root->llc;
                }
            }
            else{
                if( root->lrc == NULL )
                    return NULL;
                else{
                    if( half > 1 )
                        return qt_get_node( root->lrc, half, x-half, y-half );
                    else
                        return root->lrc;
                }
            }
        }
    }
    
    struct qtree qt_create( int size ){
        struct qtree tmp;
        tmp.root = (struct node*) malloc( sizeof( struct node ) );
        tmp.root->ulc = NULL; tmp.root->urc = NULL; tmp.root->llc = NULL; tmp.root->lrc = NULL;
        tmp.size = size;
        return tmp;
    }
    
    int main(){
        struct qtree qt = qt_create( 16 );
        qt_add_node( qt.root, qt.size, 5, 2 );
    
        //printf( "%p\n", qt_get_node( qt.root, qt.size, 15, 35 ) );
        //printf( "%p\n", qt_get_node( qt.root, qt.size, 15, 35 ) );
    
        return 0;
    }
    

    Liebe Grüße,

    Boris



  • Nutze den Debugger oder bau ein paar printf zur Kontrolle ein.
    Der Formatspecifier für Zeiger ist %p

    Schau dir mal die Zeilen 27 und 35 an. Du nimmst in beiden Zeilen root->ulc

    Was passiert eigentlich, wenn malloc mal keinen Erfolg hat und eine NULL zurückgibt?



  • Es funktioniert jetzt. Danke für die Hilfe. Über das malloc hab ich mir noch keine Gedanken gemacht weil ja für so einen kleinen Test auf jeden Fall genug Speicher da ist aber danke auch für den Hinweis da kann ich dann ja so was wie eine Fehlermeldung einbauen das der Speicher nicht mehr ausreicht.

    Ist es eigentlich notwendig, wenn ich mit malloc eine neue Struktur erstellt habe, alle Pointer innerhalb dieser Struktur auf NULL zu setzen, oder ist das schon gewährleistet?



  • Bakkaa schrieb:

    Ist es eigentlich notwendig, wenn ich mit malloc eine neue Struktur erstellt habe, alle Pointer innerhalb dieser Struktur auf NULL zu setzen, oder ist das schon gewährleistet?

    malloc ändert nichts an dem Speicher (kostet nur Zeit)

    Du kannst aber calloc nehmen.


Log in to reply