Datei einlesen und danach Daten in einen Binärbaum einbringen
-
Also ich soll Daten aus einer Datei auslesen und dann soll ich die einzelnen Wörter, die in dieser Datei sind in einen Binärbaum abspeichern....
Datei einlesen geht ja schon mal, aber ich hab gerade nicht so die Idee, wie man diese Wörter in den Binärbaum bekommt.
Datei einlesen hab ich erstmal so gemacht:
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <conio.h> void liesdatei(); /* Datei erstmal einlesen, wobei ich mir gedacht habe, dass man eigentlich diese Einlese- Aktion in einer zusätzlichen Funktion machen könnte. */ int main() { liesdatei(); getch(); return 0; } void liesdatei() { char *Zeichen; char *wort; int i = 0, j; FILE* fp; fp = fopen("gedicht.txt", "r"); // nur reading und keine andere Option /* ERKLÄRBÄR: Einlesen bis der gesamte Stream ausgelesen ist und dann ... */ while(!feof(fp)) { fscanf(fp, "%s", &wort); i++; } for (j = 0; j < 10; j++) { Zeichen = fp; } printf("Der Text in der Datei lautet: '%s'\n", *fp); getch(); return 0; }
-
dort findest du (etwa in der Mitte) eine Beispiel zu einem Binärbaum
-
Aber dazu brauch ich auch erstmal die ganzen Wörter, die noch gemeinsam in "fp" stehen. Wie kann ich nun aus fp, die einzelnen Worte auslesen, damit ich dann diese einzelnen Worte in den binären Baum sortieren kann ?
Erst muss ich dieses Problem lösen, bevor ich mich dem binären Baum zu wenden kann !
-
// edit sinnfrei
-
weißt du was ein File Pointer ist?
Wie kann ich nun aus fp, die einzelnen Worte auslesen
ich würde nicht einfach die ganze Datei sturr einlesen sondern die Datei Wort für Wort einlesen - wie sind die Wörter getrennt? durch Leerzeichen? Zeilenumbruch? oder beides?
guck mal hier:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-103628.html
-
Also in der Datei ist ein ganz normaler Text, also sind die Wörter durch Leerzeichen und manchmal mit Zeilentrenner getrennt.
-
kommen auch kommas vor oder irgendwelche satzzeichen die "entfernt" werden müssen?
poste mal ein Beispiel für eine Datei
-
TEXTBEISPIEL:
ALOA MEINE FREUNDE
Ich bin wieder da
hier im Revier, war nie wirklich weg, hab mich nur versteckt.
Tutti Frutti. Wie geht es dir denn ?So sieht zum Beispiel eine Datei aus !
-
wenn ich mich nicht irre stellt die Standard Bibliothek (und du wirst ja keine freestaning impelementation verwenden ;)) funktionien bereit zum zerlegen von sätzen in einzelne Wörter - such mal nach dem Stichwort Token
-
fscanf(fp, "%s", wort); i++;Darüber kann ich alle Wörter einzeln einlesen ohne viel Aufwand
-
cHillb3rT schrieb:
fscanf(fp, "%s", wort); i++;Darüber kann ich alle Wörter einzeln einlesen ohne viel Aufwand
Un den Buffer Overflow gibt's gratis dazu...
-
Hey, wenn ich das so mache, dann bekomme ich als Ausgabe den Pfad der exe.-Datei und nicht die sortierten Einträge..... Woran kann das denn liegen ?
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <conio.h> struct dknoten { char *wort; int anzahl; struct dknoten *rechts; struct dknoten *links; }; void liesdatei(); int zeilenanzahl(); /* Datei erstmal einlesen, wobei ich mir gedacht habe, dass man eigentlich diese Einlese- Aktion in einer zusätzlichen Funktion machen könnte. */ int main() { struct dknoten *wurzel; void baumaus(struct dknoten *); liesdatei(); zeilenanzahl(); getch(); baumaus(wurzel); getch(); return 0; } void liesdatei() { char *Zeichen = (char *)malloc(sizeof(char)); char *wort = (char *)malloc(sizeof(char)); int i = 0, j; FILE* fp; struct dknoten *wurzel; struct dknoten *einf_baum(struct dknoten *, char *); wurzel = NULL; fp = fopen("gedicht.txt", "r"); // nur reading und keine andere Option while(!feof(fp)) { fscanf(fp, "%s", wort); i++; /* Binärer Baum muss hier angesetzt werden */ einf_baum(wurzel, wort); } for (j = 0; j < 10; j++) { Zeichen = fp; } printf("Der Text in der Datei lautet: '%s'\n", *fp); getch(); } int zeilenanzahl() { FILE *fp; int cnt = 1; char c; if (!(fp=fopen("gedicht.txt","r"))) { printf("fopen() error\n"); return 1; } while((c = getc(fp)) != EOF) { if (c == '\n') { cnt = cnt + 1; } } printf("%s%d%s\n","Es sind insgesamt ", cnt, " Zeilen in der Datei vorhanden"); return 0; } /* Einfuegen von Wort in Baum */ struct dknoten *einf_baum(struct dknoten *pk, char *wort) { if (pk == NULL) { pk = malloc(sizeof(struct dknoten)); pk->wort = wort; pk->anzahl = 1; pk->links = pk->rechts = NULL; } else if (wort == pk->wort) { pk->anzahl++; } else if (wort < pk->wort) { pk->links = einf_baum(pk->links,wort); } else { pk->rechts = einf_baum(pk->rechts,wort); } return pk; } void baumaus(struct dknoten *pk) /* Rekursive Ausgabe der Baumwerte */ { /* pk Zeiger auf akt. Knoten des Baums */ if (pk != NULL) { baumaus(pk->links); printf("%s",pk->wort); if (pk->anzahl > 1) { printf(" (%2d)",pk->anzahl); } putchar('\n'); baumaus(pk->rechts); } }
-
Jetzt kann ich schon Buchstaben sortieren mit dem Programm, aber es funktionieren noch keine Wörter..... kann mir da jemand von euch helfen, weil ich weiß nicht genau, woran das legen kann.
Quellcode:
#include <stdio.h> #include <stdlib.h> #include <conio.h> struct dknoten /* Typ-Definition des Knotens */ { char *daswort; int anzahl; struct dknoten *rechts; struct dknoten *links; }; void main(void) { struct dknoten *wurzel; char *wort = (char *)malloc(sizeof(char)); struct dknoten *einf_baum(struct dknoten *, char *); void baumaus(struct dknoten *); wurzel=NULL; printf("\nBitte Buchstabe eingeben !\n"); while (scanf("%s",&wort) != EOF) { wurzel=einf_baum(wurzel,wort); } printf("\nSortierte Folge der eingegeben Buchstaben :\n\n"); baumaus(wurzel); getch(); } struct dknoten *einf_baum(struct dknoten *pk, char *wort) /* Einfügen Wert in Baum */ /* pk Zeiger auf akt. Knoten des Baums */ { /* a neuer einzufuegender Wert */ if (pk==NULL) /* neuer Wert ist einzufuegen */ { pk = malloc(sizeof(struct dknoten)); pk->daswort = wort; pk->anzahl = 1; pk->links = pk->rechts = NULL; } else if (wort==pk->daswort) /* Wert bereits vorhanden */ pk->anzahl++; else if (wort<pk->daswort) /* Wert ist kleiner als Knotenwert */ pk->links = einf_baum(pk->links,wort); else /* Wert ist groesser als Knotenwert */ pk->rechts = einf_baum(pk->rechts,wort); return pk; } void baumaus(struct dknoten *pk) /* Rekursive Ausgabe der Baumwerte */ { /* pk Zeiger auf akt. Knoten des Baums */ if (pk != NULL) { baumaus(pk->links); printf("%s",pk->daswort); if (pk->anzahl > 1) { printf(" (%2d)",pk->anzahl); } putchar('\n'); baumaus(pk->rechts); } }
-
cHillb3rT schrieb:
char *wort = (char *)malloc(sizeof(char));
Dass das nicht so der Bringer ist weisst du aber schon?
-
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); } }