Binärer Suchbaum für Telefonbuch HA
-
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?
-
Und welchen Wert würdest du da nehmen?
-
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.
-
Die Länge vom String kann
strcpyselber ermitteln.
Sonst könnte der nicht kopiert werden.Bei
strncpykannst 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.
-
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
-
Kannst du mir kurz helfen das zu korrigieren?
-
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)
-
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.
-
Danke, habe mir nochmal ein paar Tutorials zu den verschiedenen Themen angesehen und werde mich morgen nochmal dran setzten.
-
Prinzipiell halte ich diese Aufgabenstellung für Anfänger für zu schwer, Zeiger/Arrays und Rekursion sind jeweils allein schon dicke Brocken.
Beispielhaft könnte ein einfaches Telefonbuch als Baum so aussehen:
(Man beachte, dass sich das strcpy-Problem durch die Strukturkopie in Z 23,36,44 quasi von allein erledigt hat)#include <stdio.h> #include <stdlib.h> enum { MAXNAMESIZE = 100 }; typedef struct { unsigned long phone; char name[MAXNAMESIZE]; } Data; typedef struct Node { struct Node *left, *right; Data data; } Node; void insert(Node **nodeptr, Data data) { Node *node = *nodeptr; if (!node) { (*nodeptr) = calloc(1, sizeof*node); (*nodeptr)->data = data; } else if (node->left && node->left->data.phone >= data.phone) insert(&node->left, data); else if (node->right && node->right->data.phone < data.phone) insert(&node->right, data); else if (node->data.phone > data.phone) { Node *tmp = node->left; node->left = calloc(1, sizeof*node); node->left->data = data; node->left->left = tmp; } else if (node->data.phone < data.phone) { Node *tmp = node->right; node->right = calloc(1, sizeof*node); node->right->data = data; node->right->right = tmp; } } void print(const Node *node) { if (node->left) print(node->left); printf("%lu\t%s\n", node->data.phone, node->data.name); if (node->right) print(node->right); } int main() { Node * root = NULL; insert(&root, (Data) { 9, "Bowie" }); insert(&root, (Data) { 8, "Prince" }); insert(&root, (Data) { 6, "Michael" }); insert(&root, (Data) { 7, "Cohen" }); insert(&root, (Data) { 5, "Parfitt" }); insert(&root, (Data) { 1, "Frey" }); insert(&root, (Data) { 3, "Emerson" }); insert(&root, (Data) { 2, "Lake" }); insert(&root, (Data) { 4, "Cicero" }); insert(&root, (Data) { 10, "White" }); print(root); puts(""); insert(&root, (Data) { 9, "aaa" }); insert(&root, (Data) { 8, "b" }); insert(&root, (Data) { 6, "CCC" }); print(root); return 0; }
-
Danke für euch Hilfe. Ich habe es jetzt endlich wie in der Aufgabe beschrieben hinbekommen. War nicht einfach aber dank eurer Erläuterungen und Tutorials läuft es jetzt.
