Datei einlesen und danach Daten in einen Binärbaum einbringen
-
Jap, aber hängt das mit meinem Problem, dass ich nur Buchstaben einlesen kann und es bei Wörtern Probleme gibt zusammen ?
-
Nein, aber ich wollte der Frage "Warum stürzt mein Programm ab" vorgreifen.
-
Viel entscheidender ist hier die Frage, wie ich ganze Wörter in den Baum einfügen und dann richtig sortieren kann, denn, wenn ich jetzt den Programmcode durchführe macht er das nicht richtig !
-
Vielleicht solltest du versuchen Wörter mit "strcmp" zu vergleichen und genug Speicher für jedes Wort zu reservieren.
tt
PS: Übrigens ist das was du dort baust ein "binärer Suchbaum", Bäume sind übrigens ein sehr schönes Thema und ihr Anwendungsgebiet ist enorm vielfältig, für tiefergehendes Interesse, empfehle ich "The Art of Computer Programming Vol.1"
-
Das Problem, welches besteht ist, dass beim Einlesen, wenn ich diese Zeilen hier verwende:
while (scanf("%s",&wort) != EOF) { wurzel=einf_baum(wurzel,wort); }gar nichts eingelesen wird, sonderen, dass nur eine leere Variable dabei heraus kommt, die dann später einen Fehler im Programm auslöst.
Kann man das geschickter machen mit dem Einlesen oder hab ich was im generellen Programmcode falsch gemacht ?
-
Ich bin die Sache jetzt mal anders angegangen und hab nun einen anderen Code mal benutzt, wobei noch die Ausgabe richtig gemacht werden muss.
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <conio.h> // Einfacher eigener Datentyp node (Struktur) typedef struct node { char *name; int count; struct node *parent; struct node *left; struct node *right; } node; // Funktionsdefinitionen node *create_node(void); int insert_node(char *s); int delete_node(char *s); int show_tree(node *knoten); node *anfang; /* Das Hauptprogramm entält im Wesentlichen eigentlich nur die switch-case Variante und damit auch das Auswahlmenü */ int main(void) { //Auswahl int i; //Name des zu erstellenden Knotens char newname[10]; //Name des zu loeschenden Knotens char delname[10]; FILE* fp; printf("BinaerBaum mit Loeschfunktion\n\n\n"); fp = fopen("gedicht.txt", "r"); while(!feof(fp)) { fscanf(fp, "%s", newname); insert_node(newname); i++; printf("\nKnoten %s erstellt\n",newname); } // Gib den Baum aus show_tree(anfang); printf("\n\n\n\n"); printf("Programmende\n\n"); getch(); return 0; } // Erstelle einen neuen Knoten (Speicher reservieren + Anfangswerte setzen) node *create_node(void) { // Reserviere Speicher fuer einen neuen Knoten node *knoten = malloc(sizeof(struct node)); // Startwerte setzen - NULL dient dafür knoten->name = NULL; knoten->parent = NULL; knoten->left = NULL; knoten->right = NULL; return knoten; } // Fuege einen neuen Knoten in den Baum ein int insert_node(char *s) { node *knoten, *current, *last; int richtung = 0; int vergleich = 0; // Neuen Knoten erstellen if( (knoten = create_node()) == NULL) { printf("Duh! We ran out of memory! :-(\n"); exit(1); } // Speicher fuer den String allokieren knoten->name = malloc(sizeof(*s)); strcpy(knoten->name,s); // Hat der Baum schon eine Wurzel? if(anfang == NULL) { anfang = knoten; } else { // Hangel Dich vom Anfang durch den Baum... current = anfang; // ...und suche die passende Speicherstelle while(current != NULL) { // Merke Dir den letzten Ast last = current; // Vergleiche die Strings vergleich = strcmp(knoten->name,current->name); // Wenn der einzufuegende String "kleiner" ist, // dann gehts links lang if(vergleich < 0) { richtung = 0; current = current->left; } // Wenn er groesser ist, gehts rechts lang else if(vergleich > 0) { richtung = 1; current = current->right; } // Diesen String gibt es schon im Baum else { //current = current->count++; // Zählen von der Anzahl der Wörter, die im Text vorkommen printf("insert_node(): String %s exists!\n",s); return 1; } } // Vater des einzufuegenden Knotens setzen knoten->parent = last; // Ist der neue Knoten links oder rechts vom Vater? if(richtung == 0) { last->left = knoten; } else { last->right = knoten; } } return 0; } // Loesche einen Knoten aus dem Baum int delete_node(char *s) { node *current, *parent, *new; int vergleich = 0; int richtung = 0; // Suche den zu loeschenden Knoten current = anfang; while(current != NULL) { // Vergleiche die Strings vergleich = strcmp(s,current->name); // Wenn der String "kleiner" ist, bieg links ab if(vergleich < 0) { richtung = 0; current = current->left; } // Ist der String "groesser", bieg rechts ab else if(vergleich > 0) { richtung = 1; current = current->right; } // Wir haben den passenden Knoten gefunden else { break; } } // Keinen passenden Eintrag gefunden? if(current == NULL) { printf("delete_node(): Cant find node %s!\n",s); return 1; } // Loeschen wir gerade das Wurzel Element? if(current == anfang) { // Ist das Wurzel Element das letzte Element des Baums? if( (current->left == NULL) && (current->right == NULL) ) { anfang = NULL; } else { // Gibt es einen linken Knoten? if(current->left != NULL) { anfang = current->left; } // Ansonsten wird der rechte genommen else { anfang = current->right; } } } // Es wird nicht das Wurzel Element geloescht else { // Hat der zu loeschende Knoten noch Kindknoten? if( (current->left != NULL) || (current->right != NULL) ) { // Falls es einen linken Knoten gibt, nimmt dieser // den Platz des zu loeschenden ein if(current->left != NULL) { new = current->left; } // Ansonsten wird der rechte genommen else { new = current->right; } } else { new = NULL; } // An welchem Ast des Vaters haengt der zu loeschende Knoten? parent = current->parent; if(richtung == 0) { parent->left = new; } else { parent->right = new; } } // Speicher des Knotens deallozieren free(current); return 0; } int show_tree(node *knoten) { if(knoten != NULL) { // Funktion rekursiv fuer den linken und rechten Ast aufrufen show_tree(knoten->left); // String ausgeben if (knoten->parent != 0) { //printf("%s hat den Elternknoten %s\n",knoten->name,knoten->parent->name); printf("%s\n",knoten->name); show_tree(knoten->right); } } return 0; }Und die Ausgabe geht noch nicht so, wie ich das gerne hätte, also muss der Fehler irgendwo hier liegen:
int show_tree(node *knoten) { if(knoten != NULL) { // Funktion rekursiv fuer den linken und rechten Ast aufrufen show_tree(knoten->left); // String ausgeben if (knoten->parent != 0) { //printf("%s hat den Elternknoten %s\n",knoten->name,knoten->parent->name); printf("%s\n",knoten->name); show_tree(knoten->right); } }
-
Ich hab noch eine Suchfunktion eingebaut, mit der ich bestimmte Knoten suchen kann.
int such_node(char *s) { node *knoten, *current, *last; int vergleich = 1, i = 0; char *suchwort; if (anfang == NULL) { anfang = knoten; } else { printf("Bitte geben sie ein Suchwort ein, um ein Wort aus der Datei zu suchen !\n"); scanf("%s", s); current = anfang; while (current != s) { if (vergleich == 0) { printf("Dieses Wort ist in der Datei enthalten\n"); getch(); exit(1); } last = current; vergleich = strcmp(knoten->name, s); if (vergleich < 0) { i++; current = current->left; if (current->left->name != NULL) { vergleich = strcmp(current->right->name, s); printf("%s%d%s", "Dieses Wort wurde im", i, ".Durchlauf nicht gefunden.\n"); } } else if (vergleich > 0) { i++; current = current->right; if (current->right->name != NULL) { vergleich = strcmp(current->left->name, s); printf("%s%d%s", "Dieses Wort wurde im ", i, ". Durchlauf nicht gefunden.\n"); } } else { exit(1); } } printf("Dieses Wort existiert einfach nicht in dieser Datei !\n"); } return 0; }Kann man daran noch was verändern nach eurer Ansicht ?
-
Zwei Fehler hab ich ausgemerzt.... nämlich vorher konnte man nicht alle Wörter finden, die in dem Baum waren und nun klappt das auch ganz gut. Es gibt jetzt nur noch einen Fehler, wenn ich ein Suchwort habe, was nicht in der Datei vorkommt:
int such_node(char *s) { node *knoten, *current, *last; int vergleich = 1, i = 0; if (anfang == NULL) { anfang = knoten; } else { printf("Bitte geben sie ein Suchwort ein, um ein Wort aus der Datei zu suchen !\n"); scanf("%s", s); current = anfang; while (current != s) { if (vergleich == 0) { printf("Dieses Wort ist in der Datei enthalten\n"); getch(); exit(1); } last = current; vergleich = strcmp(s,current->name); if (vergleich < 0) { i++; current = current->left; if (current->name != NULL) { vergleich = strcmp(current->right->name, s); printf("%s%d%s", "Dieses Wort wurde im", i, ".Durchlauf nicht gefunden.\n"); } } else if (vergleich > 0) { i++; current = current->right; if (current->name != NULL) { vergleich = strcmp(current->left->name, s); printf("%s%d%s", "Dieses Wort wurde im ", i, ". Durchlauf nicht gefunden.\n"); } } else { printf("Dieses Wort ist in der Datei enthalten !\n"); getch(); exit(1); } } printf("Dieses Wort existiert einfach nicht in dieser Datei !\n"); } return 0; }
-
So ich bin mit dem neuen Wissen nochmal neu dran gegangen und hab mir nochmal den ganzen Kram angeschaut:
#include <stdio.h> #include <ctype.h> #include <string.h> #include <stdlib.h> #include <conio.h> struct tnode { char *word; /* Baumknoten */ int match; /* zeigt auf Text */ struct tnode *left; /* linker Unterbaum */ struct tnode *right; /* rechter Unterbaum */ }; struct tnode *talloc(void); #define MAXWORD 100 #define YES 1 #define NO 0 struct tnode *addtreex(struct tnode *, char *, int, int *); void treexprint(struct tnode *); int compare(char *, struct tnode *, int, int *); /* in alphabetischer Reihenfolge alle Gruppen von Variablennamen ausgeben, die in den ersten num(6) Zeichen gleich sind */ int main(int argc, char *argv[]) { struct tnode *root; char word[MAXWORD]; int found = NO; /* YES wenn gefunden */ int num; /* Anzahl unterschiedlicher Zeichen */ FILE* fp; num = (--argc && (*++argv)[0] == '-') ? atoi(argv[0]+1) : 6; root = NULL; fp = fopen("gedicht.txt", "r"); // nur reading und keine andere Option while(!feof(fp)) { fscanf(fp, "%s", word); root = addtreex(root, word, num, &found); found = NO; } treexprint(root); getch(); return 0; } /* addtreex: w bei oder unterhalb p einfügen */ struct tnode *addtreex(struct tnode *p, char *w, int num, int *found) { int cond; if (p == NULL) { p = talloc(); p->word = strdup(w); p->match = *found; p->left = p->right = NULL; } else if ((cond = compare(w, p, num, found)) < 0) p->left = addtreex(p->left, w, num, found); else if (cond > 0) p->right = addtreex(p->right, w, num, found); return p; } /* compare: Wörter vergleichen, p-> match ändern */ int compare(char *s, struct tnode *p, int num, int *found) { int i; char *t = p->word; for (i = 0; *s == *t; i++, s++, t++) { if (*s == '\0') { return 0; } } if (i >= num) { *found = YES; p->match = YES; } return *s - *t; } /* treexprint: Baum-Elemente mit p->match == YES ausgeben */ void treexprint(struct tnode *p) { if (p != NULL) { treexprint(p->left); if (p->match) { printf("%s\n", p->word); } treexprint(p->right); } } /* comment: Kommentar übergehen und / oder EOF liefern int comment(void) { int c; while ((c = getch()) != EOF) { if (c == '*') { if ((c =getch()) == '/') { break; } else { ungetch(c); } } } return c; } */ /* talloc: tnode erzeugen */ struct tnode *talloc(void) { return(struct tnode *)malloc(sizeof(struct tnode)); }Damit gehts schon mal
-
Wie könnte ich diese Zeilen am besten erklären ?:
if (i >= num) { *found = YES; p->match = YES; }