ADT Stapel in C++

07.01.2015, 17:52

Gast

ADT Stapel in C++

Guten Abend, ich bräuchte doch ein wenig Hilfe.
Ich gebe zu ich habe ein wenig Probleme mit C++, die Grunsätzlichen Sachen kriege ich hin, aber der Rest fällt mir doch sehr schwer.

Als Aufgabe sollen wir einen ADT Stapel mit Hilfe von Templates und dynamischem Speicher für beliebige Elementtypen implementiert werden.
Das soll mit einem Hilfs-Struct StackElement gemacht werden, dieser soll die Elemente des Stapels repräsentieren. Das Datenfeld des Typs T und ein Zeiger auf das nächste Element weiter unten im Stapel sollen enthalten sein. Das unterste Element ist ein nullptr.
Der Stapel selber besitzt nur einen Zeiger auf das oberste Element.

Jetzt komme ich bei dem ersten Teil schon nicht weiter unglücklich

Man soll eine parametrisierte Klasse Stack mit einem Template Parameter T definieren. Dann in der Klasse das Hilfs Struct einfügen, eben so wie oben beschrieben.
Der Klasse soll danach ein privates Attribut m_top hinzufügen, das ein Zeiger auf ein Objekt der Klasse StackElement ist.
Die ganzen Implementierungen sollen in der Header Datei statt finden.

class Stack {
private:
struct StackElement {

};
}

Ich weiß jetzt aber nicht, was ich genau in das struct tun soll. Kann mir da einer vielleicht helfen?

Danke

07.01.2015, 18:31

Auf diesen Beitrag antworten »

Karlito

Hallo,

im Prinzip sollte es recht einfach sein. Jedes Stackelement hat einen Pointer "payload" auf ein T und einen Pointer "last" auf das darunter liegende Element

Die Klasse Stack hält nun einen Pointer auf das oberste Element und 2 Operationen "push" und "pop". Ich denke die funktionaliät ist bekannt.

Ich hab bisher noch keine Templateprogrammierung in C++ gemacht. Ich hoffe diese Tipps reichen für das Erste. Sollten weitergehende Fragen exisiteren, kannst Du diese hier gerne stellen. Ich werde dann versuchen mich einzulesen (ein Grundstock an Verständnis ist vorhanden).

Gruß,

Karlito

07.01.2015, 18:48

Auf diesen Beitrag antworten »

Gast

An sich ist es auch nicht schwer. Die einzelnen Operationen sind klar. In der Vorlesung hatten wir folgendes Beispiel:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

template<typename T> 
class Stapel { 
public: 
Stapel(); // Konstruktor 
void push(T &x); // Element auf den Stapel legen 
void pop(); // oberstes Element entfernen 
T top(); // oberstes Element ansehen 
bool empty(); // Stapel leer? 
private: 
static unsigned int const maxSize = 100; 
int sz; // Stapelzeiger 
T data[maxSize]; // Speichervorat für Nutzdaten 
};

Das ist die Klassendefinition

code:
1: 2: 3: 4:	template<typename T> Stapel<T>::Stapel() { sz = -1; }

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

template<typename T> 
void Stapel<T>::push(T &x) { 
data[++sz] = x; 
}
template<typename T> void Stapel<T>::pop() { 
sz--; 
}
template<typename T> T Stapel<T>::top() { 
return data[sz]; 
}
template<typename T> bool Stapel<T>::empty() { 
return (sz == -1);
}

Das ist die Implementierung.
Bei dem Beispiel gibt es zwar noch Probleme mit den Arraygrenzen, aber das kann ich beheben.
Mein Problem ist, dass ich nicht weiß, wie ich das daran auf die Aufgabe übertragen soll.

Auf jeden Fall schon einmal danke für deine Hilfe smile

07.01.2015, 22:32

Auf diesen Beitrag antworten »

Karlito

Der Makel an der Implementierung ist, dass es nicht dynamisch ist, da man auf die Größe des Arrays beschränkt ist. Du musst also wirklich ein neues stuct einführen, welches den Payload und einen Pointer auf den Vorgänger hält. Bei jedem push muss dann der Speicher für das neue struct allokiert werden (malloc) und die Daten müssen entsprechend angepasst werden. Es braucht also kein Array "data" mehr sondern nur einen Pointer auf das erste struct vom Typ "Stackelement"...

Zusatz: Alternativ könnte man auch die Größe des Arrays dynamisch anpassen, das geht aber an der Aufgabenstellung vorbei...

Klar soweit?

Gruß,

Karlito

Neue Frage »

Antworten »

ADT Stapel in C++

Verwandte Themen