3. Verkettete Listen mit struct

Verkettete Listen mit struct


  • Wenn du wiederverwendbaren Code schreiben willst solltest du die verkettete Liste als eigene Klasse umsetzen:

    // Typdefinition für Datenelement (sobald du etwas über templates gelesen hast 
// wirst du das verstehen ;) )
typedef element T;

struct ListNode
{
   ListNode* next;
   T         data;

   ListNode() : next( 0 )
   {
   }
};

class LinkedList
{
   ListNode* head_;

public:
   LinkedList() : head( 0 )
   {
   }

   // add, delete, size, etc. bleiben dir überlassen
};
    0
  • 3

    Es ist absolut unnötig einen Zeiger auf das erste Element zu speichern, ein normales Objekt reicht auch.

    0

  • 314159265358979 schrieb:

    Es ist absolut unnötig einen Zeiger auf das erste Element zu speichern, ein normales Objekt reicht auch.

    Und wie sieht deine Repräsentation einer leeren Liste aus?

    0
  • 3

    Ein first und ein last Objekt.

    0
  • R

    Ich verstehe das alles noch nicht ganz.
    Die verketteten Listen überfordern mich doch noch etwas.

    Nochmal: Ich wurde vom Prof. explizit darauf hingewiesen hier mit struct zu arbeiten. Wir haben Klassen schon behandelt, sollen hier aber struct benutzen.

    Also:

    Indem ich sage

    "jetzt = jetzt->weiteres"

    wird doch das überschrieben was eigentlich in der Struktur "jetzt" steht, oder nicht?
    Grr, ganz miese Aufgabe. Und das ist ja nur der erste Teil der ganzen Sache 😕

    Kennt irgendwer ganz basale, einfache Tutorials um das Prinzip und die Anwendung von verketteteten Listen besser zu verstehen?

    0
  • B

    Hallo,

    googeln hilft hier. Da findet man z. Bsp. das hier
    http://perlgeek.de/de/artikel/einfach-verkettete-listen

    0
  • R

    Danke, aber den ersten Satz hättest du dir sparen können.
    Natürlich habe ich schon nach sowas gegoogelt.

    Aber manch richtig gutes Tutorial is halt auch echt versteckt und mit googlem nur schwer bzw. garnicht zu finden.
    Grad "altes" Material aus dem Studium oder sowas.

    Ich bin froh um jede Hilfe. So lange vergrabe ich mich dann erst mal wieder in meinen Büchern...

    0
  • 3

    Eine struct ist übrigens exakt dasselbe wie eine class, abgesehen davon dass default public ist.

    0
  • R

    eigentlich dachte ich erst, ich hätte es gelöst. nun aber doch nicht...

    man, eigentlich is die sache doch simpel. in der switchanweisung:

    case '\n':
    prüfe ob element jetzt != NULL ist.
    wenn dem so ist soll eine neue struktur erstellt werden wo dann der inhalt der zweiten zeile rein kann.
    aber irgendwie krieg ich es nicht hin

    0
  • B

    Wie sieht dein dein bisheriger Code aus?

    0
  • R

    Habs jetzt noch mal neu gemacht. Alles etwas geordneter und überschaubarer als vorher. Zudem mit Klassen statt Structs gearbeitet.

    Jetzt habe ich jedoch das "Problem" das ich nicht genau weiß wie ich zum Vergleichen der Strings an die ausgelesene (und als Objekte gespeicherte) DTD kommen soll.

    class ClElement
   {
   public:
   ClElement();
   int zahl;
   char *gibName() { return name; }
   char *gibTags() { return *tags; }
   void verarbeite(ifstream &datei);
   void druckeelement(void);
   void ClElement::deleteData(void);
   private:
   char name[64];
   char tags[10][64];
   ClElement *next;
   } ;

    So sieht die Klasse aus. Ich muss halt für das Vergleichen der Strings an zahl, name und tags. Selbst wenn alles 3 public is funktioniert das aber nicht, weil ich mich innerhalb einer Methode einer anderen Klasse befinde wenn ich die XML auslese (und anschließend die Strings vergleiche).

    for(int i=0;i<=jetzt->zahl;i++)
		{
        if(strcmp(jetzt->tags[i],puffer)!=0)
        {
           strcat(puffer, "-INVALIDE");
           break;
        }
        else if(strcmp(jetzt->tags[i],puffer)==0)
        {
           strcat(puffer, "-VALIDE");
           break;
        }
    0
  • P

    verwirrenden code gelöscht

    0
  • R

    Die Antwort hat mich jetzt, ehrlich gesagt, nur noch mehr verwirrt 😕

    0
  • P

    Klassen und Strukturen [OOP] sind mehr als nur "zusammenfassen von Daten" - sie besitzen im Normalfall auch mehr als Zugriffs / Zuweisungsmethoden für die Daten die sie beinhalten.
    Du knallst alles in eine Klasse weil es deine Aufgabe war eine struct zu nehmen. Dazu benutzt du komplizierte Datentypen (rohe charpointer, arrays, mehr pointer ...) die man in c++ viel schöner lösen kann.

    class ClElement
{
   public:
      ClElement();

      int zahl;
      char *gibName() { return name; }
      char *gibTags() { return *tags; }
      void verarbeite(ifstream &datei);
      void druckeelement(void);
      void ClElement::deleteData(void);
   private:
      char name[64];
      char tags[10][64];
      ClElement *next;
} ;

    Nachfolgenden Text und Code dieses Postings stelle ich mal unter http://creativecommons.org/licenses/by-nc-sa/3.0/de/ mit Namensnennung dieses Forums, dieses Threads und meines Forumaccounts weiterverwenden:

    Analyse:
    Problemlösung via Divide&Conquer

    Vorgehen: std::string anschauen, membermethoden anschauen, kleine int main() { /* ... */ } mit vorhandenem std::string , rumprobieren mit std::string::[find,find_first_of,insert,erase] solange bis du die dtdzeile "auspacken" kannst - dabei merkst du auch was du wirklich an daten brauchst um EIN element zu beschreiben

    Vorgehen: einfach verlinkte liste von ints oder so aufbauen, rumspielen (du hast da nen klasse link bekommen) - es bietet sich an das zB auf Basis von std::vector<int*> als eingabe zu machen

    struct liste {
  int * root;
  liste() // bau dir im constructor nen std::vector<int*>,, füll ihn mit werten von 1 - 10, benutze add(.) um das zu adden, denk ans aufräumen hinterher (jedes new ein delete) und denk dran root zu initialisieren (zB mit -1 oder so)
  ~liste() // denk ans aufräumen hinterher (jedes new ein delete)
  void add(int * a); // hängt a an die Liste hinten dran
  void out(); // gib alles aus, beginnend bei root
}

    das ganze ebenfalls in einer kleinen int main() { /* ... */ } , dabei merkst du was eine linktlist brauchst

    Vorgehen: einfache int main() { /* ... */ } deine dtd öffnen, zeilenweise einlesen, zeilenweise ausgeben bis ende oder fehler
    dann noch das Divide wieder zusamemnführen und feddich 🙂

    was dabei rauskommen könnte siehst du unten drunter, statt int* halt Element* statt std::vector<int*> halt ein Pfad zur einer Datei, ...

    test.dtd (Testcases, 2 well-formed, 2 mal-formed inputs

    "<!ELEMENT lebensmittel fleisch>"
"<!ELEMENT fleisch sorte preis>"
"<!ELEMENT lebensmittel fleisch >   tea"
"  <!ELEMENT   fleisch  sorte preis  >   wolle"

    #include <iostream>
#include <fstream>
#include <string>
#include <vector>

// --------------------------- eine Zeile parsen ----------------------------------

struct Element {
    Element (const std::string & oneLineFromDTD); // parst eine Zeile korrekt

    std::string toString();             // Ausgabe eines geparsten Elements

    std::string name;                   // ein (element) name
    std::vector<std::string> tags;      // viele tags
    bool isValid();                     // parsen hat geklappt? Variable nicht public,
    // da sie vom "parser" gesetzt wird und der user
    // sie nur auslesen aber nicht modifizieren darf
private:
    bool valid;
};

Element::Element(const std::string &oneLineFromDTD) : valid(true)                                 // ok, goodness Vermutung: Parsen ist ok
{
    name = "";                  // lösche name (definierter startzustand, ist eig. unnötig da sie den schon haben)
    tags.clear();               // lösche tags (definierter startzustand, ist eig. unnötig da sie den schon haben)

    std::string line(oneLineFromDTD);         // kopie des übergebenen strings, den dürfen dann auch ändern, das "original" nicht da const

    // das hier ist eigentlich unnötig, erspart bei falschen Eingaben aber Probleme und testet gleich ob die Zeile überhaupt parsbar ist
    {
        // ersetzt einiges was beim parsen probleme macht: doppelte leerzeichen (das ist unser trennzeichen), leerzeichen vor '>' und nach '<'
        while (line.find("  ") != std::string::npos) line.replace(line.find("  "),2,1,' ');
        while (line.find(" >") != std::string::npos) line.replace(line.find(" >"),2,1,'>');
        while (line.find("< ") != std::string::npos) line.replace(line.find("< "),2,1,'<');

        // suche den Anfang der Daten im string
        const int startOfData = line.find("<!ELEMENT ");
        // suche das Ende der Daten im string
        const int endOfData = line.find_first_of('>');

        // falls ein Anfang gefunden wurde und ein Ende gefunden wurde und der Start vor dem Ende liegt
        if (startOfData != std::string::npos    &&
            endOfData != std::string::npos      &&
            startOfData < endOfData)
        {
            // lösche alles von 0ter Position bis zum Anfang
            line.erase(0,startOfData);
            // lösche alles nach dem Ende -> "<!ELEMENT eins zwei drei><!ELEMENT vier fünf>\n" würde das 2. Element wegwerfen, da ich nur das erste pro Dateizeile parse
            line.erase(endOfData);   // erase all trailing stuff behind > till end of line
        }
        else // falls Kein Anfang gefunden wurde oder Kein Ende gefunden wurde oder Start Nach Ende liegt
        {
            // ich steck die ganze Zeile in Name, und setze Valid auf false, das kann extern zur Überprüfung der validität (+ originalstring) sowie toString() verwendet werden
            name = oneLineFromDTD;
            valid = false;
            return; // nix mehr zu machen, parsen schlug fehl, nix wie weg hier
        }
    }

    // lösche von 0 bis zur Länge von "<!ELEMENT " alles aus dem string --> löscht genau diesen Text da jeder string der es bis hierher schafft das als erstes stehen hat
    line.erase( 0 , std::string("<!ELEMENT ").size() );

    // suche das erste leerzeichen das elementname von elementtags trennt
    int posLeer = line.find_first_of(' ');

    // gibts so ein leerzeichen überhaupt? versuch mal <!ELEMENT      > als Eingabe ... das hier fängt genau den Fehler ab
    // beim genaueren Nachdenken würde der überhaupt nicht bis hierher kommen mit der Eingabe,
    /*
        "  "->' ' : "<!ELEMENT     >"->"<!ELEMENT >"
        " >"->'>' : "<!ELEMENT >"->"<!ELEMENT>"
       const int startOfData = line.find("<!ELEMENT ") == std::string::npos also kommts garnicht bis hierher ... ich lass den else zweig trozdem mal drin,
                                                          sonst hätt ich das nu alles umsonst geschrieben
    */
    if (posLeer != std::string::npos)
    {
        // name ist der substring von 0 bis zum ersten ' '
        name = line.substr(0,posLeer);
        // den brauchen wir nun nicht mehr, wir löschen das ' ' gleich mit
        line.erase(0,posLeer+1);

        // solange noch ' ' zu finden sind
        while ( (posLeer = line.find_first_of(' ')) != std::string::npos )
        {
            // pack den teil in den vector von 0 bis zur position
            tags.push_back(line.substr(0, posLeer));
            // den brauchen wir nun nicht mehr, wir löschen das ' ' gleich mit
            line.erase(0,posLeer+1);
        }
        // nach dem letzten tag ist kein ' ' mehr, also suchen wir nun nach der pos von '>'
        posLeer = line.find_first_of('>');
        // adden
        tags.push_back(line.substr(0, posLeer));
        // eigentlich egal ...
        line.erase(0,posLeer+1);
    }
    else // dead code ... learn from it ;)
    {
        name = oneLineFromDTD;
        valid = false;
        return; // nix mehr zu machen, parsen schlug fehl, nix wie weg hier
    }
}

std::string Element::toString()
{
    std::string out;

    // falls nicht valid, schreib das davor
    if (! isValid())
        out.append("[INVALID] ");
    // dann den namen in hochkommata damit man "übrige" ' ' besser sieht
    out.append("'" + name + "'");
    // falls tags da sind, pack sie mit komma davor und auch in hochkommas in den ausgabe string
    for(int i=0;i<tags.size();++i)
        out.append(", '" + tags[i] + "'");

    // gib die Ausgabe zurück
    return out;
}

bool Element::isValid()
{
    return valid;
}

// ------------------------------------- ein ListenElement aufbauen ------------------------------------------------

// jedes Listenelement hat "Daten" und einen pointer zum nächsten Element der 0 ist wenn nix mehr kommt
struct ListenElement {
    ListenElement * next;
    Element data;

    ListenElement();
    ListenElement(const std::string & oneLineFromDTD);
};

// konstruktor für das "root" element, der Nachfolger wird auf 0 gesetzt
ListenElement::ListenElement() : next(0), data(Element("rootElem"))
{
}

// konstruktor für datenelemente, das Parsen der übergebenen Zeile übernimmt das Element selbst (s.o.), der Nachfolger wird auf 0 gesetzt
ListenElement::ListenElement(const std::string &oneLineFromDTD) : next(0), data(Element(oneLineFromDTD))
{
}

// ---------------------------------------- ganze Liste aus Datei aufbauen ------------------------------------------

// eine Liste besteht aus einem root element und muss daten hinzufügen können. ich geb dem Listenkonstructor gleich den DTDfilename mit,
// dann kann der gleich die Liste aufbauen, das tut er indem er die Datei Zeilenweise einliest und das an ein ListenElement weitergibt.
// wenn dieses valid geparsed wurde wird es eingehängt, sonst weggeworfen (Designentscheid von mir, du kannst sie trotzdem einhängen oder
// gesondert aufbewahren (zB std::vector<ListElement*> parsedWrongly;) oder so

struct List {
    ListenElement * root;

    List(const std::string & pathToDTD);
    ~List();

    void addListElement(const std::string & oneLineFromDTD);
    void addListElement(ListenElement * elem);

    std::string toString();
};

List::List(const std::string & pathToDTD) : root(new ListenElement()) // lege root als leeres element an
{
    std::ifstream ifs ( pathToDTD.c_str(), std::ifstream::in ); // hol dir nen stream auf den übergebenen pfad

    if (ifs.fail()) // falls nicht öffnenbar sind mer fertich
    {
        std::cout << "Problem opening the file: '" << pathToDTD << "'" << std::endl;
        return;
    }

    // eine Zeile der Datei
    std::string line;
    while (std::getline(ifs,line,'\n').good() ) // hol dir die Zeile, falls das klappt, mach weiter sonst simmer feddich
    {
        addListElement(line);  // pack das Element zur Liste dazu (s.u. - nur wenn valide)
    }
    if (!ifs.eof()) // datei wurde NICHT bis zum ende gelesen, also ein anderer fehler passiert:
    {
        // fehlerausgabe oder so
    }

    ifs.close(); // feddich, stream expplizit zu (würde auch automatisch passieren wenn ifs den scope verlässt aber egal)
}

// WICHTIG, wir arbeiten mit new also müssen wir uns selbst ums aufräumen kümmern, der Destruktr wird aufgerufen wenn die Liste zerstört wird
List::~List()
{
    // platz für alles allokierte
    std::vector<ListenElement*> allElems;

    // fang bei root an
    ListenElement * runner = root;
    // merk dir root
    allElems.push_back(runner);

    // solange es ->next's gibt:
    while (runner->next != 0)
    {
        // runner ist jetzt next
        runner = runner->next;
        // merk dir runner
        allElems.push_back(runner);
    }

    // der vector hat nun alle allokierten pointer, dann löschen wir die mal
    const int allSize = allElems.size();
    for(int i=0; i< allSize; ++i)
    {
        // gib element am ende frei
        delete allElems.back();
        // entfern pointer vom vector
        allElems.pop_back();
    }
}

void List::addListElement(const std::string &oneLineFromDTD)
{
    // bau dir ein neues ListenElement aus der Zeile die wir bekommen
    ListenElement * newElem = new ListenElement(oneLineFromDTD);

    // wenns valide geparst wurde
    if (newElem->data.isValid())
    {
        // häng es hinten dran
        addListElement(newElem);
    }
    else // wenn nicht valide geparst
    {
        // ausgabe
        std::cout << "Problem with :" << newElem->data.toString() << "\nNot including it into List."<< std::endl;
        // und deallokieren
        delete newElem;
    }
}

void List::addListElement(ListenElement *elem)
{
    // man könnte sich hier ein "static ListenElement * lastElem = 0;" reinpacken, der einmal angelegt und muss dann nach Einfügen von
    // etwas neuem jeweils auf das letzte eingefügte Element gesetzt werden, dann spart man sich das durchlaufen von root bis ende bei
    // jedem Einfüge-Aufruf ... aber es geht auch so:

    ListenElement * runner = root;
    while (runner->next != 0) runner = runner->next; // such das element das keine Nachfolger hat

    runner->next = elem; // setz den Nachfolger auf das neue element
}

// bisserl ausgabe, rueck wird zum einrücken benutzt, das auszugebene wird in nen string gepackt (dabei benutzen wir die Ausgabe von Element) und returniert
std::string List::toString()
{
    std::string out;
    int rueck = 0;

    if (root->next == 0)
    {
        return "EMPTY LIST\n";
    }

    ListenElement * runner = root;
    while (runner->next != 0)
    {
        runner = runner->next;
        out.append('\n' + std::string(rueck*4,' '));
        out.append(runner->data.toString());
        ++rueck;
    }
    return out;
}

// -------------------------------------- alles mal testen -------------------------------------------

int main()
{
    List liste("test.dtd");

    std::cout << std::string(4,'\n') << liste.toString() << std::endl;
}

    Ausgabe:

    'lebensmittel', 'fleisch'
    'fleisch', 'sorte', 'preis'
        'lebensmittel', 'fleisch'
            'fleisch', 'sorte', 'preis'

    Scheint also zu klappen... das hier ist "meine" Lösung, ich behaupte nicht c++ perfekt zu beherrschen - es gibt sicherlich performantere, sicherere (ifstream im Konstruktor und generell keine Exceptionhandling) und schönerere Lösungen. Verstehts du etwas nicht, frag 🙂

    EDITH: war gestern schon spät, so ca 3 Uhr daher wenig Kommentare und dead code, habs nu noch kommentiert und den dead code aber drin gelassen ...

    0
  • R

    Wow, erstmal vielen, vielen Dank für die extram ausführliche Antwort.

    Das Problem ist folgendes:
    Ich lerne gerade seit diesem Semester C++. Vieles von dem was du anwendest kenne ich/wir noch gar nicht. Dem Prof wird auf jeden Fall ziemlich klar sein dass dies Lösung nicht auf meinen Mist gewachsen ist 😉

    Nun spricht ja auch nichts dagegen selbstständig schon mal vorzuarbeiten. Allerdings ist da so viel Neues drin, dass mich das ein wenig überfordert.

    Wie gesagt, ich bin dir echt dankbar für diese Lösung die ich mir auch noch in Ruhe durchlesen und verinnerlichen werde.

    Aber im Prinzip ist die Aufgabe ja auch schon fast gelöst. Ich muss es nur noch schaffen, die ausgelesenen tags der DTD mit den Starttags der XML zu vergleichen und entsprechend die Starttags als gültig (wenn in der DTD enthalten) bzw undgültig (wenn nicht enthalten) deklarieren.

    0
  • P

    Warum fangen die bei C++ nicht mit std::string, STL und streams an ... warum nur dieser char * scheiss = new char[88]; . *sight*

    Egal ... ich hab noch nen Klammerfehler behoben - kommentiert ist es ja, Wenn Fragen sind die das Lesen von

    - http://www.cplusplus.com/reference/string/string/ --> Zeichenoperationen
    - http://www.cplusplus.com/reference/iostream/ifstream/ --> Fileoperation
    - http://www.cplusplus.com/reference/stl/vector/ --> Datenspeicherung ohne new/delete Kopfzerbrechen

    nicht klären kann, frag. 😃

    0
Anmelden zum Antworten