3. Verkettete Listen mit struct

Verkettete Listen mit struct

  • R

    Nabend zusammen!

    Vorweg: Ich bin einigermaßen erfahren im Umgang mit Forgen. Ergo: Ich habe vorher die Suchfunktion genutzt.
    Andererseits lerne ich erst seit einigen Woche C++, seht es mir deshalb bitte nach wenn ich dumme Fragen stelle bzw. nicht den feinsten Programmierstil zu Tage lege 😉

    Mein Problem:

    Ich möchte eine DTD Datein mit folgendem Inhalt auslesen:

    <!ELEMENT lebensmittel fleisch>
<!ELEMENT fleisch sorte preis>

    Das Element Lebensmittel beinhaltet das Tag fleisch.
    Das Element Fleisch beinhaltet die Tags sorte und preis.

    Dieser Inhalt soll in in einer Struktur gespeichert werden. Jedes Element soll eine eigene Struktur bekommen.

    Mein Quellcode leistet dies derzeit jedoch noch nicht. Vielmehr wird ein Element in einer Struktur gespeichert und ausgegeben, anschließend wird das nächste Element eingelesen, die alte Struktur überschrieben und wieder ausgegeben.

    #include <iostream>
using namespace std;
#include <fstream>
#include <string>

struct element
   {
   int zahl;
   char name[64];
   char tags[10][64];
   } ;

void verarbeite(ifstream& datei);
void druckeelement(struct element *jetzt);

enum zustand {direktive, element, abhaengig, noise};

int main()
{
ifstream eingabe;
char dateiname[80];

cout << "DTD-Dateiname: " << endl;
cin >> dateiname;
eingabe.open(dateiname);

if (!eingabe)
   {
   cout << "Die Datei konnte nicht geöffnet werden." << endl;
   return 1;
   }

verarbeite(eingabe);

eingabe.close();
{
/* bitte ignorieren; nur bis zu Ihrer Anmeldung notwendig */
int x;
cin >> x;
}
}

void verarbeite(ifstream& datei)
{
char zeichen, letztes;
char puffer[100];
int zaehler;
enum zustand zustand = noise;
struct element *jetzt;

for (datei.get(zeichen);!datei.eof();datei.get(zeichen))
    {
    switch(zeichen)
       {
    case '<':
       zustand=direktive;
       zaehler=0;
       jetzt=new struct element;
       jetzt->zahl=0;
       break;
    case '>':
       if (zustand!=noise)
          {
	  if (letztes!=' ')
	     {
             puffer[zaehler]='\0';
             strcpy(jetzt->tags[jetzt->zahl],puffer);
	     jetzt->zahl++;
	     }
          druckeelement(jetzt);
	  }
       zustand=noise;
       break;
    case ' ':
       if (letztes==' ') continue;
       puffer[zaehler]='\0';
       zaehler=0;
       switch(zustand)
          {
       case direktive:
          if (strcmp(puffer,"!ELEMENT"))
	     {
	     cout << endl << "Diese Direktive verstehe ich nicht: " << puffer;
	     zustand=noise;
	     }
	  else zustand=element;
          break;
       case element:
          strcpy(jetzt->name,puffer);
	  zustand=abhaengig;
          break;
       case abhaengig:
          strcpy(jetzt->tags[jetzt->zahl],puffer);
	  jetzt->zahl++;
          break;
	  }
       break;
    default:
       if (zustand!=noise) puffer[zaehler] = zeichen;
       zaehler++;
       break;
       }
    letztes=zeichen;
    }
cout << endl;
}

void druckeelement(
struct element    *jetzt)
{
cout << endl << "Element " << jetzt->name << " enthält die Tags: ";
for (int i=0;i<jetzt->zahl;i++)
    {
    if (i>0) cout << ", ";
    cout << jetzt->tags[i];
    }
cout << ".";
}

    Ich würde nun so beginnen, dass ich innerhalb der struct element auf eine struct element *weiteres zeige:

    struct element
   {
   int zahl;
   char name[64];
   char tags[10][64];
   struct element *weiteres;
   } ;

    Jedoch habe ich noch nicht wirklich raus, was ich innerhalb der switch Anweisung ändern muss um das gewünschet Ergebnis zu bekommen (außer natürlich der Ausgabe).

    Für ein paar kleine Denkanstöße wäre ich sehr dankbar.

    0
  • H

    Beschäftige dich mal mit der STL, das wird sich schnell sehr weit bringen. Diese bietet unteranderem den std::vector! Wenn du diesen benutzt musst du dich nicht um die Speicherverwaltung kümmern und er ist extrem schnell. Somit hast du deine Verkettete Liste.

    Außerdem beschäftige dich mal mit Klassen ^^

    Hier findest du alle Infos zur STL: http://www.cplusplus.com/reference/
    und hier den vector http://www.cplusplus.com/reference/stl/vector/

    0
  • R

    Danke für den Hinweis, STL werd ich mir anschauen.
    In Sachen Klassen bin ich schon einigermaßen fit, hier wurde uns (warum auch immer) aber speziell gesagt dass wir mit Strukturen arbeiten sollen. 😕

    0
  • H

    Den Zeiger im Struct brauchst du nicht, wenn du vector verwendest. Hier ein einfaches Beispiel:

    #include <iostream>
#include <vector>

using namespace std;

struct elemente
{
	int a;
};

int main()
{
	vector<elemente> vec;
	elemente A,B,C;
	A.a = 7;
	B.a = 10;
	C.a = 5;

	vec.push_back(A);
	vec.push_back(B);
	vec.push_back(C);

	for(vector<elemente>::iterator i = vec.begin(); i != vec.end(); ++i)
		cout << i->a << endl;

	return 0;
}
    0
  • R

    Ich glaube wir sollen einfach mit verketteten Listen von structs arbeiten um das Prinzip zu verstehen.

    Vielen Dank für die Tipps bzgl. des vectors, aber ich glaube das schießt über unser Ziel derzeit (noch) hinaus.

    Kann mir also jemand vllt. auch nen Tipp geben wie ich das Problem wie oben angesprochen lösen könnte?

    0
  • H

    Du hast das mit der einfach verketteten Liste schon richtig verstanden. Du brauchst einen Zeiger auf den Beginn(erste Strukt) und einen Zeiger der mit jedem Element auf das letzte zeigt, um dort wieder ein neues einzufügen und den Zeiger zu erhöhen.

    0
  • R

    Ich habe meinen Quellcode jetzt mal leicht verändert:

    #include <iostream>
using namespace std;
#include <fstream>
#include <string>

struct element
   {
   int zahl;
   char name[64];
   char tags[10][64];
   element *weiteres;
   } ;

void verarbeite(ifstream& datei);
void druckeelement(struct element *jetzt);

enum zustand {direktive, element, abhaengig, noise, weiteres};

int main()
{
ifstream eingabe;
char dateiname[80];

cout << "DTD-Dateiname: " << endl;
cin >> dateiname;
eingabe.open(dateiname);

if (!eingabe)
   {
   cout << "Die Datei konnte nicht geöffnet werden." << endl;
   return 1;
   }

verarbeite(eingabe);

eingabe.close();
{
/* bitte ignorieren; nur bis zu Ihrer Anmeldung notwendig */
int x;
cin >> x;
}
}

void verarbeite(ifstream& datei)
{
char zeichen, letztes;
char puffer[100];
int zaehler;
enum zustand zustand = noise;
struct element *jetzt;

for (datei.get(zeichen);!datei.eof();datei.get(zeichen))
    {
    switch(zeichen)
       {
    case '<':
       if (zustand==noise)
	   {
	   zustand=direktive;
       zaehler=0;
       jetzt=new struct element;
       jetzt->zahl=0;
       break;
	   }
	   if (zustand==weiteres)
	   {
		   jetzt->weiteres=new struct element;
		   zaehler=0;
		   jetzt->weiteres->zahl=0;
		   break;
	   }
    case '>':
       if (zustand!=noise)
          {
	  if (letztes!=' ')
	     {
             puffer[zaehler]='\0';
             strcpy(jetzt->tags[jetzt->zahl],puffer);
	     jetzt->zahl++;
	     }
          druckeelement(jetzt);
		  druckeelement(jetzt->weiteres);
	  }
       zustand=weiteres;
       break;
    case ' ':
       if (letztes==' ') continue;
       puffer[zaehler]='\0';
       zaehler=0;
       switch(zustand)
          {
       case direktive:
          if (strcmp(puffer,"!ELEMENT"))
	     {
	     cout << endl << "Diese Direktive verstehe ich nicht: " << puffer;
	     zustand=noise;
	     }
	  else zustand=element;
          break;
	   case element:
          strcpy(jetzt->name,puffer);
		  zustand=abhaengig;
          break;
       case abhaengig:
          strcpy(jetzt->tags[jetzt->zahl],puffer);
	  jetzt->zahl++;
          break;
	  }
       break;
    default:
       if (zustand!=noise) puffer[zaehler] = zeichen;
       zaehler++;
       break;
       }
    letztes=zeichen;
    }
cout << endl;
}

void druckeelement(
struct element    *jetzt)
{
cout << endl << "Element " << jetzt->name << " enthaelt die Tags: ";
for (int i=0;i<jetzt->zahl;i++)
    {
    if (i>0) cout << ", ";
    cout << jetzt->tags[i];
    }
cout << ".";
}

    Zeile 11: element *weiteres; ergänzt
    Zeile 17: zustand "weiteres" ergänzt
    Zeile 56-71: case '<' erweitert
    Zeile 82: Ausgabe um druckeelement(jetzt->weiteres) ergänzt
    Zeile 84: zustand=weiteres

    Er speichert im ersten Element (kurs) jetzt nur das tag "person".
    Eine zweite Struktur wird auch erzeugt, allerdings nicht befüllt. Denke ich zu kompliziert?

    0
  • H

    Mir ist aufgefallen, dass deine if-Abfragen(mehrfach) falsch sind. Ein Vergleich wird mit == gemacht und nicht mit gleich, für weiteres hatte ich keine Zeit.

    Edit: Anstelle der ganzen chars, empfehle ich dir überalle std::string zu verwenden.

    0
  • R

    Mhm, Deppenfehler. 😕
    Habe ich jetzt oben an den beiden Stellen ausgebessert!

    An der Ausgabe hat sich soweit aber nicht verändert.

    0
  • H

    Das mit dem Enum und den Zuständen ist totaler Overkill. Das macht alles viel komplizierter als es in Cpp sein muss.

    Für die Verkettete Liste benötigst du ungefähr folgende Logik:

    element *jetzt = NULL, *first = NULL; //first ist basisnode! Eventuell als Rückgabewert verwenden fürs löschen und Anzeigen 

//Solange es Zeilen gibt
if(!first)
{
  first = new element;
  jetzt = first;
}
else
{
  jetzt->next = new element;
  jetzt = jetzt->next;
}
jetzt->next = NULL;

//Zeile verarbeiten! Jetzt zeigt immer auf das aktuelle letzte element!
//Schleife wiederholen

    Dir fehlen noch komplett die Aufräumarbeiten!

    void DeleteData(element *node) //basisnode angeben liste löscht sich rekursiv
{
	element *nextnode = node->next;

	if(nextnode)
		DeleteData(nextnode);

	delete node;
}
    0

  • 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
Anmelden zum Antworten