Anwendung einer dynamischen Datenstruktur
-
Hallo erstmal!
nachdem ich ein bisschen hier im forum reingeschnuppert habe, muss ich heut mal was posten.ich lerne im rahmen meiner ausbildung c++. im moment fangen wir mit dynamischen datenstrukturen an und ich habe mich voll verhaspelt. vor allem habe ich das gefühl, dass ich bei zeigern ein volles verständnisproblem habe.
hier eine der aufgaben:
beschreiben sie eine datenstruktur für eine übersetzungstabelle von einer sprache in eine andere.
dabei sollen jeweils paare von worten gespeichert werden...
nun kommen noch ein paar nebenbedingungen. eigentlich geht es nur drum in der art:struct Uebersetzung{ string eintrag[2]; Uebersetzung *erster, *zweiter; }eine datenstruktur zu beschreiben. finde ich aber langweilig, ich will mit dem ding was anfangen können:
#include <iostream> #include <string> using namespace std; class Woerterbuch { private: string eintrag[2]; //0=deutsch, 1=französisch Woerterbuch *p_erster, *p_letzter; Woerterbuch *p_naechster, *p_vorheriger; public: Woerterbuch(string deutsch, string franzoesisch) { eintrag[0] = deutsch; eintrag[1] = franzoesisch; p_erster = p_naechster = p_vorheriger = p_letzter = NULL; } string GetSPR1() const {return eintrag[0];} string GetSPR2() const {return eintrag[1];} Woerterbuch* GetFirst() const {return p_erster;} Woerterbuch* GetLast() const {return p_letzter;} Woerterbuch* naechsterEintrag() const {return p_naechster;} void EintragNeu(string deutsch, string franzoesisch, Woerterbuch *p_neuer); }; ostream& operator<<( ostream& os, const Woerterbuch& wortpaar) { Woerterbuch *p_ausgabe = wortpaar.GetFirst(); cout << p_ausgabe << " " << wortpaar.GetFirst() << endl; // for ( ; wortpaar != NULL; wortpaar = wortpaar->naechsterEintrag()) // os << wortpaar.eintrag[0] << " - " << wortpaar.eintrag[1] << endl; // ausgabe->naechsterEintrag(); // os << wortpaar.GetSPR1() << " - " << wortpaar.GetSPR2() << endl; return os; } void Woerterbuch::EintragNeu(string deutsch, string franzoesisch, Woerterbuch *neuer = NULL) { Woerterbuch *p_neuesWort = new Woerterbuch(deutsch, franzoesisch); if (p_naechster == NULL) p_erster = p_letzter = p_naechster = p_neuesWort; else p_letzter->p_naechster; p_naechster = p_neuesWort; cout << " p_letzter " << p_letzter << " p_naechster " << p_naechster << " p_erster " << p_erster << " p_vorheriger " << p_vorheriger << endl; } int main() { Woerterbuch test("test", "test"); test.EintragNeu("auch", "aussie"); test.EintragNeu("die Wahl" , "choix"); test.EintragNeu("strasse", "la rue"); cout << test << endl; return 0; }nun habe ich vor allem an der funktion
ostream& operator<<( ostream& os, const Woerterbuch& wortpaar)sehr lange rumgemacht, aber ich habe das gefühl, dass meine kleine zeigerfarm irgendwo hinzeigt, nur nicht da, wo sie soll.
vor allem bekomme ich bei dem objekt ausgabe immer eine Fehlermeldung, wenn ich z.b ausgabe.GetSPR1() benutze: linke seite, objekt sei keine Klasse oder struktur.
und in der funktion EintragNeu() habe ich auch schon ewig mit dem befehl p_letzter->p_naechster; rumexperimentiert. was bedeutet eigentlich der Punktoperator in dem Zusammehang ganz genau??
Auch finde ich komisch, dass der erste auf den letzten zeiger zeigt? ist das so korrekt?ihr habt sicher ein bisschen mehr erfahrung mit solchen sachen. ich stehe nach 2 tagen programmieren voll im wald.....und irgendwie kriege ich das gefühl nicht los, dass ich die zeiger sache voll nicht verstehe
danke fürs anschauen
wuschel
-
von vertexwahn habe ich eine tolle anregung gesehehn:
friend ostream& operator<<( ostream& os, const Woerterbuch& wortpaar)und die ostreamklasse habe ich jetzt so angepasst:
ostream& operator<<( ostream& os, const Woerterbuch& wortpaar) { Woerterbuch *p_ausgabe = wortpaar.GetFirst(); cout << p_ausgabe << " " << wortpaar.GetFirst() << endl; for ( ; p_ausgabe != NULL; p_ausgabe = p_ausgabe->naechsterEintrag()) os << p_ausgabe->GetSPR1() << " - " << p_ausgabe->GetSPR2() << endl; return os; }nun sieht es schon ein bisserl besser aus. er gibt mir jetzt den zweiten eintrag der liste aus. aber warum den zweiten?
-
um welche art von Datenstruktur soll es den gehen - einfach verkettete Liste? Bäume?
am sinnvollsten wäre hier wahrscheinlich ein Digitalbaum
in der STL gibts pair - das dürfte am sinnvollsten für so etwas sein - aber wahrscheinlich darfst du die STL nicht verwenden, weil du ja selber mit datenstrukuren rumkämpfen sollst...wenn du neu bist solltest du dein wörterbuch einfach mal als einfach verkettete Liste Implementieren - etwas so:
http://turing.fh-landshut.de/~jamann/cpp/LinkedList.c.html
statt Integer speicherst du halt einfach die beiden Wörter
beim suchen nach einem Wort gehst du einfach jedes Element durch und schaust, ob es das passende ist - ist zwar nicht gerade Resourcenschonend aber führt zum Ziel (nicht effizient aber dafür effektiv)
-
den code habe ich geschrieben aufgrund einer linked list. eigentlich wäre das erst das nächste kapitel.
aber irgendwie klappt die bei meiner anwendung nicht. deshalb glaube ich, dass ich was nicht kapier.
der autor leitet das kapitel so ein, dass er sagt, dass man nicht nur alghoritmen rekursiv benutzen kann, sondern auch datenstrukturen (eben, durch den zeiger, der wieder eine datenstruktur des gleichen typs ist.)
in robert sedgewicks "algorithems in c++" ist die linked list auch beschrieben, daher habe ich auch das mit dem
p_letzter->p_naechster; p_naechster = p_neuesWort;aber irgendwie ist mir nicht richtig klar, was er da genau macht.
ich habe ein paar cout ausgeben lassen, wenn ich z.b. die funktion
p_ausgabe->naechsterEintrag()ausführe, liefert er immer einen NULL-Zeiger zurück
Digitalbaum und STL habe ich bisher noch nicht gehört.
-
wuschelz schrieb:
in robert sedgewicks "algorithems in c++" ist die linked list auch beschrieben, daher habe ich auch das mit dem
p_letzter->p_naechster; p_naechster = p_neuesWort;aber irgendwie ist mir nicht richtig klar, was er da genau macht.
die zeile enthält einen tippfehler. es muß
p_letzter->p_naechster = p_naechster = p_neuesWort;heißen.
außerdem hast du vergessen, die zeiger im objekt p_neuesWort zu setzen! kein wunder, daß du mit deiner zeigerfarm im computernirwana gelandet bist
du könntest auch die felder p_erster und p_letzter schon im konstruktor auf this setzen. damit kannst du die abfrage
if (p_naechster == NULL)einsparen. außerdem wärs auch logischer. denn nach der erzeugung eines wörterbuch-objekts enthält deine liste dann ja ein objekt.
und nochwas: in c++ gibts eigentlich kein NULL mehr. du solltest stattdessen 0 schreiben.
ansonsten bleibt mir nur noch, ein deprimierendes fazit zu ziehen. der ganze ansatz ist, mit verlaub, müll. man merkt, daß der autor des buches, aus dem du den code hast, noch knietief in c steckt. aber um sich mit zeigerarithmetik einen knoten ins hirn zu machen ist der code ideal
-
danke konfusius für deine antwort. ich werde das mal anschauen.
das problem mit der sache aus dem buch ist die, es handelt sich um pascal pseudo-code und dann muss man das ins c++ überführen, also dedaktisch nicht gerade gut.
wie würdest du denn diese aufgabe angehen?
wie wäre es in c++ besser?
-
in c bzw pascal programmiert man eine liste, imdem man eine datenstruktur namens listelm deklariert und dann prozeduren programmiert, die auf diese datenstruktur operieren, wie etwa einfuegen(struct listelm *elm, struct listelm *neu). die funktionen operieren auf ihre argumente und da ist es naheliegend, daß die funktion einfügen sowohl elm als auch neu verändern muß. in objektorientierten programmiersprachen ist die denke anders. dort programmiert man methoden, die auf variablen ihres objekts operieren. die variablen anderer objekte werden normalerweise nicht verändert. das ist wohl der grund, warum in der methode EintragNeu() vergessen wurde, die zeiger im objekt p_neuesWort zu verändern.
verwirrend ist auch, daß Woerterbuch semantisch eine liste ist, aber technisch ist die klasse ein wörterbucheintrag. solange man die klasse nur benutzt (von außen sieht) fällt das nicht so auf. sobald mann sie aber selber programmieren muß kommt man ins schleudern.
ich würde eine klasse Wörterbuch definieren und darin nochmal eine struktur Eintrag.
#include<string> class Woerterbuch { struct Eintrag { Eintrag *naechster; // *vorheriger nicht nötig. einfach verkettete liste reicht string de,fr; }; Eintrag *erster; // *letzter braucht es nicht. neue einträge // kann man auch am anfang einhängen Eintrag *FindeDe (const string &de); Eintrag *FindeFr (const string &fr); Eintrag *FindeEintrag (const string &de, const string &fr); public: Woerterbuch () {} ~Woerterbuch (); void NeuerEintrag (const string &de, const string &fr); string UebersetzeNachDe (const string &fr); string UebersetzeNachFr (const string &de); }; Woerterbuch::~Woerterbuch () // vor zerstörung alle einträge löschen { Eintrag naechster; while(erster) { naechster=erster->naechster; delete erster; erster=nächster; } } Woerterbuch::Eintrag *Woerterbuch::FindeDe (const string &de) { for(Eintrag *eintr=erster; eintrag; eintrag=eintrag->naechster) if(eintr->de==de) return eintr; return 0; } Woerterbuch::Eintrag *Woerterbuch::FindeFr (const string &fr) { for(Eintrag *eintr=erster; eintrag; eintrag=eintrag->naechster) if(eintr->fr==fr) return eintr; return 0; } Woerterbuch::Eintrag *Woerterbuch::FindeEintrag (const string &de, const string &fr) { Eintrag *eintr=FindeDe(de); if(!eintr) eintr=FindeFr(fr); return eintr; } void Woerterbuch::NeuerEintrag (const string &de, const string &fr) { bool ist_neu=false; // nachsehen, ob eintrag schon vorhanden // hast du in deinem programm vergessen ;) Eintrag *eintr=FindeEintr(de,fr); if(!eintr) { eintr=new Eintrag; ist_neu=true; } eintr.de=de; eintr.fr=fr; if(ist_neu) // wenn neu, dann zeiger setzten. wenns nicht neu ist, // sind die zeiger ja schon gesetzt. es könnte sogar zu // fehlern kommen { // eintr an listenkopf anhängen eintr.naechster=erster; erster=eintr; } } string Woerterbuch::UebersetzeNachDe (const string &fr) { Eintrag *eintr=FindeFr(fr); if(eintr) return eintr->de; return ""; } string Woerterbuch::UebersetzeNachFr (const string &de) { Eintrag *eintr=FindeDe(de); if(eintr) return eintr->fr; return ""; }
-
achso, du hast also eine klasse für die datenstruktur und eine klasse, welche die ganze verwaltung übernimmt und "nur" die datenstruktur benutzt.danke für deine hilfe.
dann werde ich mal die nächste aufgabe nach dem ansatz lösen, da soll ich ein glossar erstellen. jeder neue eintrag soll schon alphabetisch einsortiert werden.das sollte ja jetzt kein problem mehr sein
