Binärer Suchbaum für Telefonbuch HA

tm09

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.

tm09

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

DirkB

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?

tm09

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.

tm09

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

DirkB

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.

tm09

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?

tm09

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

tm09

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?

DirkB

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

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

tm09

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

DirkB

Wa macht den strncpy anders als strcpy ?

tm09

Gebe ich nicht mit strncpy die länge die gespeichert werden soll mit an?! Oder sollte ich das mit malloc für den String im Struct machen?

DirkB

Und welchen Wert würdest du da nehmen?

tm09

Naja, entweder ich hätte einfach einen im Code vordefinierten Wert (254) genommen oder die länge des Strings ermittelt und diesen, dann an strncpy übergeben.

DirkB

Die Länge vom String kann strcpy selber ermitteln.
Sonst könnte der nicht kopiert werden.

Bei strncpy kannst du die maximale Anzahl von Zeichen angeben, die kopiert werden dürfen.
Wenn diese Anzahl erreicht wird, wird der Stringterminator nicht mitkopiert.
Die Information über die Länge geht dem String verloren.

In beiden Fällen muss der Zielspeicher gültig sein (er muss dem Programm gehören und beschreibbar sein).

Ja, du musst den Speicher vorher (z.B. mit malloc) besorgen.

tm09

Ich habe mich jetzt nochmal dran probiert und bekomme immerhin nur noch eine Fehlermeldung. Was sagt ihr zu dem Code und könntet ihr mir erklären, was ich noch falsch mache?
Das mit dem string habe ich noch mal separat ausprobiert und das funktioniert bei mir jedenfalls.

void bst_insert_node(bstree* bst, unsigned long phone, char *name) {

        if(bst->root == NULL){
            bst_node *node = malloc(sizeof(bstree));
            if(node != NULL){
                node->phone = phone;
                strcpy(node->name, name);
                node->left = NULL;
                node->right = NULL;
                node->parent = NULL;
            }

            bst->root = node;
            bst->count = 1;
    }
    bst_node *tmp, *neu_knoten;
    int gefunden = 0;

    tmp = (*bst);
    while (0){
        if (phone < tmp->phone)
        {
            if (tmp->left != NULL)
                tmp = tmp->left;
            else
                gefunden = 1;
        }
        else if (phone == tmp->phone)
            gefunden = 1;
        else
        {
            if (tmp->right != NULL)
                tmp = tmp->right;
            else
                gefunden = 1;
        }
        if (phone != tmp->phone){
            neu_knoten = malloc (sizeof(bst_node));
            neu_knoten->left = NULL;
            neu_knoten->right = NULL;
            neu_knoten->phone = phone;
            strcpy(neu_knoten->name, name);
            neu_knoten->parent = tmp;
            if (phone < tmp->phone){
                tmp->left = neu_knoten;
                ++bst->count;
            }else{
                tmp->right = neu_knoten;
                ++bst->count;
            }
        }
    }
}

Schon mal danke im Voraus

Und hier nochmal der Ausschnitt, wo die Struktur erstellt wird.

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;
};

Und hier die Fehlermeldung:

introprog_telefonbuch_vorgabe.c:40:9: error: assigning to 'bst_node *'
(aka 'struct bst_node *') from incompatible type 'bstree'
(aka 'struct bstree')
tmp = (*bst);

Ich weiß zwar, was damit gemeint ist, schaffe es aber nicht den Fehler zu beheben.

Du weist einem Zeiger einen falschen dereferenzierten Zeiger zu