3. Doppelt verkettete Liste

Doppelt verkettete Liste

  • G

    Guten Abend,

    ich habe die Aufgabe, ein C++ zu schreiben, welches eine verkettete Liste beinhaltet.

    In diesem Forum existieren schon einige Tutorials zu diesem Thema, die sicherlich gut geschrieben und hervorragend durchdacht sind, jedoch immer Klassen und/oder Templates beinhalten, welche noch nicht Teil unseres "Wortschatzes" sind.
    Wir sollen diese Aufgabe mit Strukturen, Zeigern und Strings lösen.

    Ansich habe ich das Prinzip, welches sich hinter den Listen verbirgt, schon verstanden, allerdings bin ich nicht dazu in der Lage, das programmiertechnisch korrekt auszudrücken.

    Bisher kann ich folgenden (kläglichen) Ansatz vorweisen:

    #include <iostream>
#include <string>

using namespace std;

struct datum
{
	int tag;
	int monat;
	int jahr;
};

struct angestellt
{
		std::string name;
		std::string vorname;
		struct datum alter;
		struct datum eingestellt;
		long gehalt;
		struct angestellt *pNext;
		struct angestellt *pPrev;
};

int main()
{
angestellt *pNeuerSklave = new angestellt; // Initialisiert das die Liste?

}

    Ich weiß, dass das noch nicht viel ist, allerdings wäre ich über jeden kontruktiven Rat sehr erfreut.

    Also, Danke schonmal im Voraus & einen schönen Sonntag Abend noch.

    0
  • M
     

    struct datum
{
    int tag;
    int monat;
    int jahr;
};

struct angestellt
{
        std::string name;
        std::string vorname;
        datum alter;  // du meinst eher geburtsdatum?
        datum eingestellt;
        long gehalt;
};

// neu:
struct listitem
{
  angestellt data;
  listitem* prev;
  listitem* next;
}

struct liste
{
  listitem* first;
  listitem* current;
}

// das musst du jetzt schreiben:
void FuegeAnListeAn(liste& l, const angestellt& data)
{

}

void FuegeInListeEin(liste& l, const angestellt& data)
{

}

// und eben noch die anderen funktionen. Eine schreib ich dir :)
liste ErstelleListe()
{
  liste l;  
  l.first = NULL;    // Liste enthält noch keine elemente
  l.current = NULL;  // Aktueller zeiger zeigt auf kein element, weil keins enthalten ist
  return l;
}

    allerdings ist der code nicht schön, aber in der schule habt ihr es wohl so gelernt 🙂
    Die List sollte eine eigene Klasse mit methoden FuegeAn, Loesche usw. sein.

    0
  • G

    Ja, ich werde mich da mal durcharbeiten... vielen Dank erstmal!

    Unser Prof versorgt uns leider sehr spärlich mit Informationen... Aber ich denke, das wird mir helfen 👍

    0
  • K

    Was verstehst du überhaupt unter Liste?? Wenn ich das hier anschaue:

    angestellt *pNeuerSklave = new angestellt; // Initialisiert das die Liste?

    könnte man auf die Idee kommen du willst das hier erreichen:

    angestellt* pNeuerSklave  = new angestellt[3]; //3 neue Sklaven
    0
  • G

    nein nein, das war ehrlich gesagt nur geraten von mir...

    Aber erstellst du denn damit nicht ein array? Oder bin ich da völlig auf dem Holzpfad?

    angestellt* pNeuerSklave  = new angestellt[3]; //Array...?
    0
  • G

    Was ist eigentlich der Unterschied zwischen dem:

    struct listitem
{
  angestellt data;
  listitem* prev;
  listitem* next;
};

    und dem:

    struct angestellt
{
        std::string name;
        std::string vorname;
        datum alter;  // du meinst eher geburtsdatum?
        datum eingestellt;
        long gehalt;
};

    Hätte ich listitem nicht auch in angestellt packen können? Oder geht das verfahrenstechnisch nicht?

    0
  • K

    kurzer Hinweis: Wenn du

    using namespace std;

    machst
    musst du string nicht mit std:: aufrufen

    0
  • G

    Jo, stimmt, das wäre ja dann doppelt... danke

    0
  • K

    goetz schrieb:

    nein nein, das war ehrlich gesagt nur geraten von mir...

    Aber erstellst du denn damit nicht ein array? Oder bin ich da völlig auf dem Holzpfad?

    angestellt* pNeuerSklave  = new angestellt[3]; //Array...?

    jo, ist eine Art von Array (dynamisch erstellt), kann dann so benutzt werden:

    pNeuerSklave[0].name = "Gerhard";
pNeuerSklave[1].name = "Heinrich";
//...
    0
  • G

    goetz schrieb:

    Was ist eigentlich der Unterschied zwischen dem:

    struct listitem
{
  angestellt data;
  listitem* prev;
  listitem* next;
};

    und dem:

    struct angestellt
{
        std::string name;
        std::string vorname;
        datum alter;  // du meinst eher geburtsdatum?
        datum eingestellt;
        long gehalt;
};

    Hätte ich listitem nicht auch in angestellt packen können? Oder geht das verfahrenstechnisch nicht?

    Weißt du hierzu zufällig auch was? Hmm...

    0
  • M

    du kannst natürlich auch die daten direkt in listitem packen.
    Allderings hab ich es gerne, wenn Nutzdaten von Verwaltungsdaten getrennt sind.
    So kannst du später leichter eine andere Lsite bauen, indem du einfach die datenstruktur änderst und der rest läuft noch (naja fast)
    Ist aber keine Pflicht, geht auch so wie du es hattest.
    Aber: ein Angestellter hat ja keinen vorherigen angestellten oder nachfolgenden. Ein listenelemtn hat ein voriges und ein folgendes und die aktuellen daten. So hört sich das besser an 🙂

    0
  • G

    Aber wie mach ich das denn nun mit der Datensatzerstellung für die Liste? Erstmal muss ich ja Daten haben, die ich an die Liste anfügen kann...

    Wäre eine Dateneingabe für diese Liste so vorstellbar? Und wenn ja, wie gebe ich die daten aus meiner temporären Struktur-Instanz in meinen (nächsten) Listenknoten?

    liste init()		// Initialisierung der Liste.
{
	liste l;
	l.first = NULL;
	l.current = NULL;
	return l;
}

liste empty(liste& l)	//Soll die Liste wieder löschen.
{
	delete& l;
}

void dataErstellen()
{
	struct angestellt temp;	//temporäre Struktur-Instanz für die Übergabe
	cin >> temp.name;
	cin >> temp.vorname;
	cin >> temp.name;
	cin >> temp.geburtstag.tag;
	cin >> temp.geburtstag.monat;
	cin >> temp.geburtstag.jahr;
	cin >> temp.eingestellt.tag;
	cin >> temp.eingestellt.monat;
	cin >> temp.eingestellt.jahr;
	cin >> temp.gehalt;
}

int main()
{

	init();
	dataErstellen();

}

    Ich weiß, die Dateneingabe ist fast schon kriminell gelöst... aber es geht ja auch erstmal ums Prinzip

    0
  • M
     

    int main()
{

    init(); // hier wird eine liste zurückgegeben, aber die speicherst du nirgendwo
    // Du musst dir die Liste in einer variablen speichern, sonst bringt dein init
    // ncihts:
    liste l = init();

    // Deindataerstellen liest zwar die daten ein, aber damit wird nichts gemacht.
    // entweder du lässt die funktion die eingebenen daten zurückgeben oder du
    // übergibtst der funktin eine refernz auf die liste, damit in der funktion gleich was eingefügt werden kann.
    //dataErstellen();

    // Einfügen in eine liste könnte zB so gehen, wenn dataErstellen die daten zurückgibt
    einfuegen(l, dataErstellen());
}

void einfuegen(liste& l, const data& d)
{
  listitem* item = new listitem;
  item->next = l.current->next;
  item->prev = l.current;

  // achtung, noch überpfeümn obs nith ende der liste ist
  item->next->prev = item;
  item->prev->next = item;

  l.current = item;
}

    IUSt jetzt unkommentiert, aber ist glaub ich nich so schwer zu verstehne. Am besten aufmalen wo die zeiger hinzeigen und wo sie dann nach der aktion hinzeigen.

    0
Anmelden zum Antworten