4. Binärer Suchbaum für Telefonbuch HA

Binärer Suchbaum für Telefonbuch HA

  • D

    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?

    0
  • D

    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.

    0
  • T

    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.

    0
  • T

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

    0
  • D

    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?

    0
  • T

    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.

    0
  • T

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

    0
  • D

    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.

    0
  • T

    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;
}
```
    0
  • ?

    Definition der struct?

    0
  • T
     

    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);
    0
  • ?

    Du greifst auf die falsche Struktur zu

    0
  • T

    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?

    0
  • D

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

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

    0
  • T

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

    0
  • D

    Wa macht den strncpy anders als strcpy ?

    0
  • T

    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?

    0
  • D

    Und welchen Wert würdest du da nehmen?

    0
  • T

    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.

    0
  • D

    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.

    0
Anmelden zum Antworten