Binärer Suchbaum für Telefonbuch HA

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

tm09

Kannst du mir kurz helfen das zu korrigieren?

DirkB

tm09 schrieb:

Das mit dem string habe ich noch mal separat ausprobiert und das funktioniert bei mir jedenfalls.

Du hast immer noch kein Speicher für deinen String.
Nimm bitte statt malloc calloc. Da wird der besorgte Speicher mit 0 initialisiert.
Dann crasht es hoffentlich.

Hoffentlich ist so gemeint, dass der Fehler aufgedeckt wird. Denn es ist sonst ein unentdeckter Fehler.

tm09 schrieb:

Kannst du mir kurz helfen das zu korrigieren?

Du weist einem Zeiger auf Äpfeln eine Birnen. Das ist doppelt Widersinnig. Falscher Typ und noch Objekt statt Adresse

tm09 schrieb:

bst_node *node = malloc(sizeof(bstree));

Passt nun auch nicht gerade.
Du besorgst Speicher für eine Birne und weist die Adresse einem Zeiger auf Äpfel zu.
(hier hast du immerhin zwei Adressen)

Wutz

tm09 schrieb:

Ich habe mich jetzt nochmal dran probiert und bekomme immerhin nur noch eine Fehlermeldung.

Compilermeldungen sagen nichts über die techn. + fachliche Korrektheit eines Programmes aus - so auch bei dir.
Du hast Zeiger+Arrays grundsätzlich nicht verstanden und entsprechende Hinweise ignorierst du, wie du zeigst:

if(bst->root == NULL){
            bst_node *node = malloc(sizeof(bstree));
            if(node != NULL){
                node->phone = phone;
                strcpy(node->name, name);  /* <-- du kopierst name in einen undefinierten Speicherbereich, -> UB -> Müll */
                node->left = NULL;
                node->right = NULL;
                node->parent = NULL;
            }

Auch Binärbäume hast du prinzipiell nicht verstanden (kann sein, dass das an deinem Lehrer und nicht an dir liegt, das ist mir aber jetzt egal):

struct bstree
{
    struct bst_node* root;
    int count;
};

Sinn und Zweck eines Baumes ist es gerade, nicht wahlfrei (indiziert) auf alle Elemente zugreifen zu können/müssen, count ist hier also prinzipiell Unsinn (und dürfte nur Prüfzwecken/Testfällen dienen), da die Datenstruktur Baum (ebenso wie verk.Listen) die "Größen"information immer schon implizit besitzen.

Ich empfehle dir, zunächst mal deine Datenstruktur für leichteren+flexibleren Umgang zu vereinfachen:

enum {MAXNAMESIZE=100};
struct bst_node
{
    bst_node* left;
    bst_node* right;
    bst_node* parent;
    unsigned long phone;
    char name[MAXNAMESIZE];
};

Noch besser weil flexibler für Änderungen und sauberer Trennung zw. Baum- und Datenoperationen wäre das auslagern deiner Daten in eine extra struct

typedef struct {
    unsigned long phone;
    char name[MAXNAMESIZE];
} Data;
und dann
struct bst_node
{
    bst_node* left;
    bst_node* right;
    bst_node* parent;
    Data data;
};

Und gewöhne dir deine globalen Variablen ab, wenn dir weiter jemand helfen soll.

Das mit dem string habe ich noch mal separat ausprobiert und das funktioniert bei mir jedenfalls.

Das kannst du als Anfänger niemals beurteilen.
strcpy funktioniert jetzt aber nur wegen der Umstellung auf Array.

tm09

Danke, habe mir nochmal ein paar Tutorials zu den verschiedenen Themen angesehen und werde mich morgen nochmal dran setzten.