Template für lineare Liste von Knoten

Habe eine Aufgabe bekommen und komme damit nicht so richtig zurecht.
Die Aufgabe lautet folgendermaßen:

"Entwickeln Sie ein Klassentemplate für eine lineare Liste von Knoten, die nur eine Variable data mit variablen Typ enthalten sollen. Das Template soll Methoden mit folgender Funktionalität besitzen:

a. Einfügen eines Knotens am Anfang der Liste
b. Löschen des jeweils ersten Knotens der Liste
c. Anzeigen der Liste am Bildschirm

Schreiben Sie dazu die entsprechenden Anweisungen; auch Testaufrufe in der main."

So weit, so gut. Hier ist mein Lösungsversuch:

template <class T> class LinList
{
	T data;
	LinList * next;
};

class Liste
{
	LinList * first;

	void einfuegen(LinList * knoten)
	{
		knoten->next = first;	
first = knoten;
}
void loeschen()
{
	LinList * temp = first;
	first= first->next;
	delete temp;
}

void anzeigen()
{
	LinList * current = first;

	while(current != NULL)
	{
		cout << current->data <<endl;
		current = current->next;
	}
}
}

int main()
{
	Liste neu;
	LinList * <float>wert;
	wert = new LinList <float>;
wert->data = 3.9;
neu.einfuegen( wert);
wert = new LinList <float>;
wert->data = 5.0;
	neu.einfuegen( wert);

	neu.anzeigen();

	wert.loeschen();

	neu.anzeigen();
	return 0;
}

Was meint ihr dazu? Kann das funktionieren, oder habt ihr mir gute Verbesserungstipps?

Schon mal im Vorraus danke für hoffentlich hilfreiche Antworten!

Das kann so nicht funktionieren da LinList ein Template ist und bei den Definitionen kein T angegeben wird. class Liste musst du auch zum Template machen.

Danke für die schnelle Antwort. Kann mir aber jemand vielleicht ein Lösungsvorschlag schreiben? Bin mit meinem Latein ziemlich am Ende.

.filmor

Lösungsvorschlag? Soweit kommts noch.
Zu deinem Template-Problem:

template <class T>
class Liste
{
public:
    typedef T Type;
    typedef LinList<Type> NodeType;
    // LinList ist eigentlich der falsche Name für das Template,
    // Node oder Element wäre hübscher.
    // Dann hieße das hier:
    typedef Node<Type> NodeType;
    typedef NodeType* NodePointer;
    // Dann noch überall in den Methoden LinList* durch NodePointer ersetzen
    // und fertig.

Man fordert außerdem für Einfügen am Anfang (push) normalerweise nicht einen Knoten, sondern nur die Daten dieses Knotens. Der einzufügende Knoten wird in der Methode erzeugt. Das gilt auch für die anderen Methoden.

Mein Quelltext sieht nun folgendermaßen aus. Funktionieren tut es aber noch nicht.

#include <iostream.h>
#include <conio.h>
#include <string.h>

template <class T> class Node
{
    T data;
    Node *next;
};

template <class T> class Liste
{
	public:
		typedef T Type;
		typedef Node<Type> NodeType;
		typedef NodeType *NodePointer;
        Node *first;

    void einfuegen(NodePointer *knoten)
	{
		knoten->next = first;    
		first = knoten;
	}

	void loeschen()
	{
		NodePointer *temp = first;
		first= first->next;
		delete temp;
	}

	void anzeigen()
	{
		NodePointer *current = first;
		while(current != NULL)
		{
			cout << current->data <<endl;
			current = current->next;
		}
};

int main()
{
    Liste neu;
    Node *<float>wert;
    wert = new Node <float>;
	wert->data = 3.9;
	neu.einfuegen( wert);
	wert = new Node <float>;
	wert->data = 5.0;
    neu.einfuegen(wert);

    neu.anzeigen();

    wert.loeschen();

    neu.anzeigen();
    return 0;
}

CStoll

Zwei kleine Änderungen hätte ich noch daran:

template<typename T>
class Liste
{
  //...
  //1. Wozu hast du denn das Typedef?
  NodePointer first;

  //2. übergib' lieber nur Elemente und bau dir deine Knoten selber:
  void einfuegen(const T& wert)
  {
    NodePointer n=new NodePointer;
    n->data=wert;
    n->next=first;
    first=n;
  }
  //...
};

//Aufrufe dann mit
Liste<float> lst;
lst.einfuegen(1.5);
//...

Bekomme folgende Fehlermeldung, mit der ich nichts anfangen kann:

1.cpp
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(58) : fatal error C1075: Dateiende erreicht, bevor das zugehoerige Element fuer das linke Element Klammer '{' in 'C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp
(12)' gefunden wurde
Fehler beim Ausführen von cl.exe.

test2.exe - 1 Fehler, 0 Warnung(en)

Hier nochmal zur Hilfe den aktualisierten Quelltext:

#include <iostream.h>
#include <conio.h>
#include <string.h>

template <class T> class Node
{
    T data;
    Node *next;
};

template <class T> class Liste
{
	public:
		typedef T Type;
		typedef Node<Type> NodeType;
		typedef NodeType *NodePointer;
        Nodepointer first;

    void einfuegen(const T& wert)
	{
		NodePointer n = new NodePointer;
		n->data = wert;
		n->next = first;
		first = n;
	}

	void loeschen()
	{
		NodePointer *temp = first;
		first= first->next;
		delete temp;
	}

	void anzeigen()
	{
		NodePointer *current = first;
		while(current != NULL)
		{
			cout << current->data <<endl;
			current = current->next;
		}
};

int main()
{
    Liste<float> lst;
	lst.einfuegen(1.5);
	lst.einfuegen(4.3);
	lst.einfuegen(3.1);
	lst.anzeigen();

    lst.loeschen();
	lst.anzeigen();

    return 0;
};

.filmor

Die schließende Klammer der anzeigen-Methode fehlt.

Das hätte ich eigentlich sehen müssen.
Nur habe ich jetzt einige neue Fehler mit denen ich nichts anfangen kann:

--------------------Konfiguration: test2 - Win32 Debug--------------------
Kompilierung läuft...
1.cpp
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(17) : error C2146: Syntaxfehler : Fehlendes ';' vor Bezeichner 'first'
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(43) : Siehe Verweis auf Instantiierung der kompilierten Klassenvorlage 'Liste<T>'
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(17) : error C2501: 'Nodepointer' : Fehlende Speicherklasse oder Typbezeichner
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(43) : Siehe Verweis auf Instantiierung der kompilierten Klassenvorlage 'Liste<T>'
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(17) : error C2501: 'first' : Fehlende Speicherklasse oder Typbezeichner
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(43) : Siehe Verweis auf Instantiierung der kompilierten Klassenvorlage 'Liste<T>'
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(17) : error C2146: Syntaxfehler : Fehlendes ';' vor Bezeichner 'first'
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(48) : Siehe Verweis auf Instantiierung der kompilierten Klassenvorlage 'Liste<float>'
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(17) : error C2501: 'Nodepointer' : Fehlende Speicherklasse oder Typbezeichner
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(48) : Siehe Verweis auf Instantiierung der kompilierten Klassenvorlage 'Liste<float>'
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(17) : error C2501: 'first' : Fehlende Speicherklasse oder Typbezeichner
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(48) : Siehe Verweis auf Instantiierung der kompilierten Klassenvorlage 'Liste<float>'
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(50) : warning C4305: 'argument' : Verkuerzung von 'const double' in 'const float'
C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(51) : warning C4305: 'argument' : Verkuerzung von 'const double' in 'const float'
Fehler beim Ausführen von cl.exe.

test2.exe - 6 Fehler, 2 Warnung(en)

ZuK

Nodepointer first;

sollte

NodePointer first;

sein
Kurt

.filmor

Die Warnungen kommen daher, dass ein 0.0 Literal double ist, für float musst du ein f dahinter schreiben (0.0f).

Ich bin mir nicht sicher, ob es was ausmacht, aber ich würde

typedef NodeType* NodePointer;

schreiben.

Dann solltest du noch Node entweder zu einem struct machen oder mit der Liste anfreunden:

template <typename T>
struct Node
{/*...*/};

// oder

template <typename T>
class Liste;

template <typename T>
class Node
{
    friend class Liste<T>;
    // ...
};

Ein weiterer Fehler:

NodePointer n = new NodePointer; // ist Quatsch
NodePointer n = new NodeType; // so ist's richtiger

Habe Node zu einem struct gemacht und die Fehleranzahl hat sich auf eine einzige verringert. Ich denke es wird eine Flasche Sekt aufgemacht, wenn ich das Ding zum laufen bringe (selbstverständlich durch eure Hilfe ).

C:\Programme\Microsoft Visual Studio\MSDev98\MyProjects\test2\1.cpp(29) : error C2440: 'initializing' : 'struct Node<float> *' kann nicht in 'struct Node<float> ** ' konvertiert werden

.filmor

Jaha, dann lies noch mal den letzten Teil meines Posts!

Deine Hinweise habe ich eigentlich beachtet.
Habe

NodePointer n = new NodePointer;

in

NodePointer n = new NodeType;

abgeändert und die main sieht nun so aus:

int main()
{
    Liste<float> lst;
	lst.einfuegen(1.5f);
	lst.einfuegen(4.3f);
	lst.einfuegen(3.1f);
	lst.anzeigen();

    lst.loeschen();
	lst.anzeigen();

    return 0;
};

.filmor

temp und current in irgendwelchen Methoden sind als NodePointer* ausgewiesen, sollten aber NodePointer sein. Aber das hatten wir schon n paar mal

Es funktioniert jetzt alles, ausser in der anzeigen()-methode.
es gibt eine access violation in:

cout << current->data <<endl;

.filmor

template <class T>
struct Node
{
    Node () : next (0) {}
    // Rest wie gehabt

Ansonsten hat next nirgendwo den Wert NULL bzw. 0 (wie der C++ler tut).

Also ich habe keine Ahnung, wo das Zeigerproblem liegt. Werde ich mich mit dem zufrieden geben, was ich jetzt habe. Trotzdem danke nochmal .filmor für die Hilfe.

Hab's mir überlegt und gebe mich nicht zufrieden, so kurz vor dem Ziel aufzugeben . Bin also für jegliche Hilfe, die zur Lösung beihilft, sehr dankbar.
Zur Übersicht gebe ich nochmal den gesamten Quelltext an:

#include <iostream.h>
#include <conio.h>
#include <string.h>

template <typename T> struct Node
{
	Node() : next (0) {};
	T data;
    Node* next;
};

template <typename T> class Liste
{
	public:
		typedef T Type;
		typedef Node<Type> NodeType;
		typedef NodeType* NodePointer;
        NodePointer first;

    void einfuegen(const T& wert)
	{
		NodePointer n = new NodeType;
		n->data = wert;
		n->next = first;
		first = n;
	}

	void loeschen()
	{
		NodePointer temp = first;
		first= first->next;
		delete temp;
	}

	void anzeigen()
	{
		NodePointer current = first;
		while(current != NULL)
		{
			cout << current->data <<endl;
			current = current->next;
		}
	}
};

int main()
{
    Liste<float> lst;
	lst.einfuegen(1.5f);
	lst.einfuegen(4.3f);
	lst.einfuegen(3.1f);
	lst.anzeigen();

    lst.loeschen();
	lst.anzeigen();

    return 0;
	getch();
};

ZuK

Die Klasse List braucht auch einen constructor denn sonst ist first nicht initialisiert. Nach dem einfügen des ersten nodes zeigt dann sein next pointer ins Nirvana.

Kurt