Binärer Suchbaum für Telefonbuch HA



  • Hallo alle Zusammen, ich habe von der Uni aus eine HA aufbekommen und komme an einer Stelle leider nicht weiter, vielleicht könnt ihr euch das ja mal ansehen. Ich soll ein Telefonbuch (Nummer und Name) in einem Binären Suchbaum Speichen. Leider funktioniert das noch nicht und ich bekomme noch viele Fehlermeldungen.
    Schon mal danke für eure Hilfe im Voraus.
    Und das ganze in C.

    void bst_insert_node(bstree* bst, unsigned long phone, char *name) {
    
            bstree *node = malloc(sizeof(bstree));
            node->phone = phone;
            strcpy(node->name, name);
            node->left = NULL;
            node->right = NULL;
    
        if(bst->root == NULL){
            bst->root = node;
            return;
        }else{
            if(phone < bst->root->phone){
                bst->left = node;
                while (1) {
                    if(phone < bst->left) {
                        if(bst->left == NULL){
                            bst->left = node;
                            return 1;}
                    }else if(phone == bst->left || phone == bst->right){
                        return 1;
                    }else{
                        if(bst->right == NULL){
                            bst->right = node;
                            return 1;}
                    }
                }
            }else if(phone == bst->root->phone){
                return;
            }else{
                bst->right = node;
                while (1) {
                    if(phone < bst->left) {
                        if(bst->left == NULL){
                            bst->left = node;
                            return 1;}
                    }else if(phone == bst->left || phone == bst->right){
                        return 1;
                    }else{
                        if(bst->right == NULL){
                            bst->right = node;
                            return 1;}
                    }
                }
            }
        }
    }
    


  • Und wir sollen uns jetzt die Fehlermeldungen selbst raussuchen?

    Und wer hat dir eigentlich beigebracht, den Code so einzurücken?



  • Und wie lautet die Frage?
    (Da ist kein ? in deinem Text)

    Wie lauten die Fehlermeldungen?

    Wie ist bstree definiert?
    Nebenbei: eine Telefonnummer ist keine Ganzzahl.

    Du hast return mit und ohne Parameter.
    Dieser Parameter muss zum Rückgabetyp der Funktion passen.
    Welcher ist für eine void-Funktion sinnvoll?

    tm09 schrieb:

    if(bst == NULL){     // Wenn der Zeiger ungültig ist
            bst->root = node;  // dann wird doch gleich mal darauf zugegriffen          
            return;
    


  • Tut mir leid, habe einiges vergessen hinzuschreiben. Das Problem müsste bei der Erstellung und Speicherreservierung am Anfang bei Malloc liegen. Es sind immer die gleichen Fehler, die mir angezeigt werden. Die Pointer und Variablen, die ich erstelle und denen ich mit malloc Speicher reservieren existieren laut den Fehlermeldungen nicht.
    Nja, und

    if(bst == NULL){
            bst->root = node;
            return;
    

    soll, falls noch kein root existiert, der erste Node = der "root" sein.
    Und entschuldigt noch ungünstige Einrückung. Werde das beim nächste Mal besser machen.



  • NULL bedeutet "ungültiger Zeiger"
    Den darfst du nicht dereferenzieren (daüber auf das Ziel zugreifen). Weder mit * noch mit [] noch mit ->

    tm09 schrieb:

    tut mir leid, habe einiges vergessen hinzuschreiben.

    Warum machst du es denn jetzt nicht?



  • Ok, jetzt hast du deine Antwort editiert

    Meine Antwort gilt auch für das Neue

    tm09 schrieb:

    Nja, und

    if(bst == NULL){
            bst->root = node;
            return;
    

    soll, falls noch kein root existiert, der erste Node = der "root" sein.

    Bei dir muss bst aber existieren, sonst bekommst du die Information über den neue Speicherort für bstr nicht aus deiner Funktion heraus.



  • Ich soll ein binären Suchbaum erstellen, in dem unendlich viele Einträge mit Telefonnummer und Namen gespeichert werden sollen. Das Einsortieren der Einträge soll nach der Nummer geschehen. Wenn die Nummer bereits existiert, soll die bereits vorhandene Nummer mit Name nicht noch einmal eingetragen werden. Mein Problem ist halt, dass die Speicherzuweisung bzw das erstellen der Node's anscheinend nicht Funktioniert.



  • Ach so, ich muss dort ja prüfen ob bst->root = NULL ist und nicht bst = NULL.
    Das meintest du doch?



  • tm09 schrieb:

    Ach so, ich muss dort ja prüfen ob bst->root = NULL ist und nicht bst = NULL.
    Das meintest du doch?

    Im Prinzip ja.

    Wofür ist root in bstree definiert?
    Das ist ein Member der struct bstree . Der ist in jedem Knoten enthalten, wird aber nur einmal belegt. Warum?



  • Da hast du recht, müsste ich eigentlich weglassen können. Root ist ja nur der ersten Node im Baum. Das hatte ich so gemacht, weil ich das aus der Vorlesung in Erinnerung hatte.



  • Mein Problem ist halt immer noch, dass die Node's, denen ich mit Malloc Speicher reserviert laut der Fehlermeldung Wall nicht existieren.



  • WAs sagt denn der Compiler dazu?

    if(phone < bst->left) {
    

    Und poste mal den aktuellen Code. Mit der Definition der struct bstree.

    Ein minimales compilierbares Beispiel, das den Fehler enthält.



  • Also die komplette Fehlermeldung sieht so aus:

    introprog_telefonbuch_vorgabe.c:25:15: error: no member named 'phone' in
    'struct bstree'
    node->phone = phone;

    introprog\_telefonbuch\_vorgabe.c:26:22: error: no member named 'name' in  
    'struct bstree'  
    strcpy(node->name, name);  
    ~~~~ ^  
    /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.12.sdk/usr/include/secure/_string.h:83:27: note:  
    expanded from macro 'strcpy'  
    \_\_builtin\_\_\_strcpy\_chk (dest, src, \_\_darwin_obsz (dest))  
    ^~~~  
    introprog\_telefonbuch\_vorgabe.c:26:22: error: no member named 'name' in  
    'struct bstree'  
    strcpy(node->name, name);  
    ~~~~ ^  
    /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.12.sdk/usr/include/secure/_string.h:83:53: note:  
    expanded from macro 'strcpy'  
    \_\_builtin\_\_\_strcpy\_chk (dest, src, \_\_darwin_obsz (dest))  
    ^~~~  
    /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.12.sdk/usr/include/secure/_common.h:39:54: note:  
    expanded from macro '\_\_darwin\_obsz'  
    #define \_\_darwin\_obsz(object) \_\_builtin\_object\_size (object, \_USE_FORTIF...  
    ^~~~~~  
    introprog\_telefonbuch\_vorgabe.c:27:15: error: no member named 'left' in  
    'struct bstree'  
    node->left = NULL;  
    ~~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:28:15: error: no member named 'right' in  
    'struct bstree'  
    node->right = NULL;  
    ~~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:31:19: warning: incompatible pointer types  
    assigning to 'struct bst_node *' from 'bstree *' (aka 'struct bstree *')  
    [-Wincompatible-pointer-types]  
    bst->root = node;  
    ^ ~~~~  
    introprog\_telefonbuch\_vorgabe.c:35:18: error: no member named 'left' in  
    'struct bstree'  
    bst->left = node;  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:37:33: error: no member named 'left' in  
    'struct bstree'  
    if(phone < bst->left) {  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:38:29: error: no member named 'left' in  
    'struct bstree'  
    if(bst->left == NULL){  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:39:30: error: no member named 'left' in  
    'struct bstree'  
    bst->left = node;  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:40:25: error: void function 'bst\_insert\_node'  
    should not return a value [-Wreturn-type]  
    return 1;}  
    ^ ~  
    introprog\_telefonbuch\_vorgabe.c:41:40: error: no member named 'left' in  
    'struct bstree'  
    }else if(phone == bst->left || phone == bst->right){  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:41:62: error: no member named 'right' in  
    'struct bstree'  
    }else if(phone == bst->left || phone == bst->right){  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:42:21: error: void function 'bst\_insert\_node'  
    should not return a value [-Wreturn-type]  
    return 1;  
    ^ ~  
    introprog\_telefonbuch\_vorgabe.c:44:29: error: no member named 'right' in  
    'struct bstree'  
    if(bst->right == NULL){  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:45:30: error: no member named 'right' in  
    'struct bstree'  
    bst->right = node;  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:46:25: error: void function 'bst\_insert\_node'  
    should not return a value [-Wreturn-type]  
    return 1;}  
    ^ ~  
    introprog\_telefonbuch\_vorgabe.c:52:18: error: no member named 'right' in  
    'struct bstree'  
    bst->right = node;  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:54:33: error: no member named 'left' in  
    'struct bstree'  
    if(phone < bst->left) {  
    ~~~ ^  
    introprog\_telefonbuch\_vorgabe.c:55:29: error: no member named 'left' in  
    'struct bstree'  
    if(bst->left == NULL){  
    
    Und der Codeausschnitt:  
    
    ```
    int main(int argc, char** argv) {
        // Erzeuge leeren Suchbaum
        bstree bst;
        bst.root = NULL;
        bst.count = 0;
    
        if (argc != 2)
        {
            printf("Nutzung: %s <Dateiname>\n",argv[0]);
            return 1;
        }
    
        // Lese das Telefonbuch ein
        read_file(argv[1], &bst);
    
        // Gib die Benutzeroberfläche aus
        interface(&bst);
    
        // Gib den Speicher frei
        bst_free_tree(&bst);
    
        return 0;
    }
    ```


  • Definition der struct?



  • typedef struct bst_node bst_node;
    typedef struct bstree  bstree;
    
    /* Knoten im Binären Suchbaum, wobei ...
     * - left und right das linke bzw. rechte Kind spezifiziert.
     * - parent auf denjenigen Knoten verweist, dessen Kind dieser Knoten ist.
     * - phone die Telefonnummer des Suchbaumknotens angibt.
     * - name den entsprechenden Namen des Suchbaumknotens angibt.
     */
    struct bst_node
    {
        bst_node* left;
        bst_node* right;
        bst_node* parent;
        unsigned long phone;
        char *name;
    };
    
    /* Ein Binärer Suchbaum mit einem Wurzelknoten root und der Anzahl an
     * Elementen im Baum.
     */
    struct bstree
    {
        struct bst_node* root;
        int count;
    };
    
    /* Hilfsstrucktur für open_file / read_line / close_file
     */
    typedef struct  {
        FILE *filepointer;
        char *line;
        size_t linecapp;
    } read_line_context;
    
    void bst_insert_node(bstree* bst, unsigned long phone, char *name);
    bst_node* find_node(bstree* bst, unsigned long phone);
    void bst_in_order_walk(bstree* bst);
    void bst_free_tree(bstree* bst);
    void open_file(read_line_context *ctx, const char *filename);
    void open_stdin(read_line_context *ctx);
    int read_line(read_line_context *ctx, char **operation, unsigned long* nummer, char **name);
    void close_file(read_line_context *ctx);
    void print_to_dot(DOT_NODETYPE* tree, char* filename);
    void print_node(bst_node *node);
    


  • Du greifst auf die falsche Struktur zu



  • Habe ich auch gerade entdeckt :p
    Meint ihr, wenn ich das jetzt auf die richtige Struktur zugreife funktioniert es oder sollte ich das lieber nochmal Komplet neu machen?



  • Deine struct bst_node hat auch keinen Speicherplatz für den Namen.

    Dein strcpy sorgt dann (hoffentlich) auch für Abstürze.



  • Reicht es, wenn ich dafür strncpy nehme? Oder muss ich dem Element im Struct auch noch mal Speicher reservieren?



  • Wa macht den strncpy anders als strcpy ?


Anmelden zum Antworten