Wie templates richtig anwenden?
-
Ich würde gerne mit templates meinen Suchbaum der zurzeit nur int Elemente aufnehmen kann generalisieren, sodass er zb auch char Elemente aufnehmen kann.
Hier mal ein paar Auszüge aus meinem Code welchen ich via template generalsieren möchte
class treenode { public: treenode(int data = 0); bool red; int item; treenode *left; treenode *right; treenode *parent; }; class RSTree { public: RSTree(); void insert(int x); void levelorder(); void inorder(); private: treenode* head; void RedBlackInsert(treenode* &node, treenode* &parent, int x, bool sw); }; void RSTree::insert(int x) { // Wurzel = head->right RedBlackInsert(head->right, head, x, 0); head->right->red = 0; }
Im Mainprogramm muss ich ja nur bei der Objekterstellung <char> dazu schreiben,
jedoch wie passe ich Klasse in der Header Datei und die Funktionen in der cpp Datei an?
Hier mal mein Versuch, welcher jedoch zu viele Fehlermeldungen führttemplate<class type> class treenode { public: treenode; bool red; type item; treenode<type> *left; treenode<type> *right; treenode<type> *parent; }; template<class type> class RSTree { public: RSTree(); void insert(type & x); void levelorder(); void inorder(); private: treenode<type> * head; void RedBlackInsert(treenode* &node, treenode* &parent, int x, bool sw); }; template<class type> void RSTree::insert(type * x) { // Wurzel = head->right RedBlackInsert(head->right, head, x, 0); head->right->red = 0; }
Sprich was muss ich alles anpassen? Geht das alles wie template<class Type>
oder brauch man für funktionsausformulierungen diese template<typename T> Formulierung?
lg
-
Na, du musst das Template dann natürlich überall durchziehen. Also auch z.B. in
void RedBlackInsert(treenode
.Wenn du viele Fehler bekommst, schaue dir den ersten an und behebe diesen. Wiederhole, bis fertig.
Zur Frage:
Geht das alles wie template<class Type>
oder brauch man für funktionsausformulierungen diese template<typename T> FormulierungOb
class
odertypename
- das ist hier völlig egal. Entscheide dich für eines und zieh das durch.Persönlich bevorzuge ich
template<typename T>
, aber du kannst auch gernetemplate<class Type>
verwenden - als Typ ist jedochT
üblicher alsType
.Siehe auch (inkl. Spezialfall, wo es doch nen Unterscheid macht): http://stackoverflow.com/questions/2023977/c-difference-of-keywords-typename-and-class-in-templates
-
Okay, hab es jetzt versucht überall hinzuzufügen, jedoch immer ncoh viele Fehler.
Am meisten bekomme ich diesen Fehler angezeigt
Fehler C2244 "RSTree::inorder": Keine Übereinstimmung für Funktionsdefinition mit vorhandener Deklaration gefunden
Jedoch keine Ahnung was ich falsch mache. Glaub ich vergesse einfach eine grundlegende Sachen bzw. weiss sie einfach nicht wie man es korrekt anwendet.template<class Type> class treenode { public: //treenode; bool red; Type item; treenode<Type> *left; treenode<Type> *right; treenode<Type> *parent; }; template<class Type> class RSTree { public: RSTree(); void insert(Type & x); //void levelorder(); void inorder(); private: treenode<Type> *head; void RedBlackInsert(treenode* &node, treenode* &parent, Type & x, bool sw); int red(treenode* &node); void leftRotation(treenode * &leftNode); void rightRotation(treenode * &leftNode); void inorder(treenode* node); template<class Type> treenode::treenode(Type & data) { this->item = data; parent = nullptr; left = nullptr; right = nullptr; red = true; } template<class Type> RSTree::RSTree() { head = new treenode(); } template<class Type> void RSTree::insert(Type * x) { // Wurzel = head->right RedBlackInsert(head->right, head, x, 0); head->right->red = 0; } template<class Type> int RSTree::red(treenode* &node) { if (node == nullptr) return 0; return node->red; } template<class Type> void RSTree::RedBlackInsert(treenode *& node, treenode *&parent, Type & x, bool sw) { if (node == 0) { node = new treenode(x); node->parent = parent; if (node->parent == this->head) { node->red = 0; } return; } if (red(node->right) && red(node->left)) { if (node != head->right) { cout << "Knoten: " << node->left->item << ", " << node->item << ", " << node->right->item << " umfarben " << endl; node->red = 1; node->left->red = 0; node->right->red = 0; } else if (node == head->right) { cout << "Knoten: " << node->left->item << ", " << node->right->item << " umfarben. " << node->item << " ist die Wurzel!" << endl; node->left->red = 0; node->right->red = 0; } } if (x < node->item) { RedBlackInsert(node->left, node, x, 0); if (red(node) && red(node->left) && sw) { rightRotation(node); } if (red(node->left) && red(node->left->left)) { rightRotation(node); node->red = !(node->red); if (node->right != 0) { node->right->red = !(node->right->red); } } } else if (x > node->item) { RedBlackInsert(node->right, node, x, 1); if (red(node) && red(node->right) && !sw) { leftRotation(node); } if (red(node->right) && red(node->right->right)) { leftRotation(node); node->red = !(node->red); if (node->left != 0) { node->left->red = !(node->left->red); } } } return; } template<class Type> void RSTree::leftRotation(treenode* &leftNode) { treenode * middleNode = leftNode->right; treenode *parentNode = leftNode->parent; cout << "LR ( " << leftNode->item << ", " << middleNode->item << ")" << endl; leftNode->right = middleNode->left; if (leftNode->right != nullptr) { leftNode->right->parent = leftNode; } middleNode->left = leftNode; middleNode->parent = leftNode->parent; leftNode->parent = middleNode; if (parentNode->left == leftNode) { parentNode->left = middleNode; } else { parentNode->right = middleNode; } } template<class Type> void RSTree::rightRotation(treenode* &rightNode) { treenode *middleNode = rightNode->left; treenode *parentNode = rightNode->parent; cout << "RR ( " << rightNode->item << ", " << middleNode->item << ")" << endl; rightNode->left = middleNode->right; if (rightNode->left != nullptr) { rightNode->left->parent = rightNode; } middleNode->right = rightNode; middleNode->parent = rightNode->parent; rightNode->parent = middleNode; if (parentNode->left == rightNode) { parentNode->left = middleNode; } else { parentNode->right = middleNode; } }
-
treenode
ist ein template, daß auch in zBvoid leftRotation(treenode * &leftNode);
seinen Typ wissen muss.// (bis auf die Fehler) vollständiger, kompilierbarer Code wär a Hit.
-
Okay, das habe ich wohl immer vergessen.
Quasi vor dem ::funktionsname immer noch <Type> einfügen.
template<class Type>
void RSTree<Type>::rightRotation(treenode* &rightNode)
Hab jetzt aufjedenfall schon weniger Fehlermeldungen. Aber immer noch ein paar.
Hier mal der Code.
Hab paar FUnktionen auskommentiert bzw. weggelassen. Geht ja im Prinzip nur um
den Templateeinsatz und weniger um das Programm. Aber hoffe es läuft auch so in abgespeckter Form wenn die templates alle richtig eingestellt sind.
lg#include "2-3-4-Baum.h" #include <iostream> using namespace std; int main() { RSTree<int> tree; int choice = 0; while (choice != 4) { cout << "1: Ausgabe des Baumes in Levelorder" << endl << "2: Element einfuegen" << endl << "3: Ausgabe in Inorder" << endl << "4: Quit" << endl; cin >> choice; cout << endl; switch (choice) { case 1: cout << "Baum in Levelorder:"; // tree.levelorder(); cout << endl; break; case 2: { cout << "Knoten einfuegen:" << endl; int num = 0; cin >> num; tree.insert(num); cout << "Element " << num << " erfolgreich eingefuegt!" << endl << endl; break; } case 3: cout << "Baum in Inorder:" << endl; tree.inorder(); cout << endl; break; } } return 0; } #pragma once #include <vector> template<class Type> class treenode { public: //treenode; bool red; Type item; treenode *left; treenode *right; treenode *parent; }; template<class Type> class RSTree { public: RSTree(); void insert(Type & x); //void levelorder(); void inorder(); private: treenode<Type> *head; void RedBlackInsert(treenode* &node, treenode* &parent,Type & x, bool sw); int red(treenode* &node); void leftRotation(treenode * &leftNode); void rightRotation(treenode * &leftNode); void inorder(treenode* node); //void levelorder(treenode* node, std::vector<treenode*> &nodeQueue, int niveau, std::vector<int> &niveauQueue); //void insertionSort(std::vector<treenode*> &nodeQueue, std::vector<int> &niveauQueue); }; #include "2-3-4-Baum.h" #include <iostream> using namespace std; template<class Type> treenode<Type>::treenode(Type & data) { this->item = data; parent = nullptr; left = nullptr; right = nullptr; red = true; } template<class Type> RSTree<Type>::RSTree() { head = new treenode(); } template<class Type> void RSTree<Type>::insert(Type & x) { // Wurzel = head->right RedBlackInsert(head->right, head,Type & x, 0); head->right->red = 0; } template<class Type> int RSTree<Type>::red(treenode* &node) { if (node == nullptr) return 0; return node->red; } template<class Type> void RSTree<Type>::RedBlackInsert(treenode *& node, treenode *&parent, Type & x, bool sw) { if (node == 0) { node = new treenode(x); node->parent = parent; if (node->parent == this->head) { node->red = 0; } return; } if (red(node->right) && red(node->left)) { if (node != head->right) { cout << "Knoten: " << node->left->item << ", " << node->item << ", " << node->right->item << " umfarben " << endl; node->red = 1; node->left->red = 0; node->right->red = 0; } else if (node == head->right) { cout << "Knoten: " << node->left->item << ", " << node->right->item << " umfarben. " << node->item << " ist die Wurzel!" << endl; node->left->red = 0; node->right->red = 0; } } if (x < node->item) { RedBlackInsert(node->left, node, x, 0); if (red(node) && red(node->left) && sw) { rightRotation(node); } if (red(node->left) && red(node->left->left)) { rightRotation(node); node->red = !(node->red); if (node->right != 0) { node->right->red = !(node->right->red); } } } else if (x > node->item) { RedBlackInsert(node->right, node, x, 1); if (red(node) && red(node->right) && !sw) { leftRotation(node); } if (red(node->right) && red(node->right->right)) { leftRotation(node); node->red = !(node->red); if (node->left != 0) { node->left->red = !(node->left->red); } } } return; } // Linksrotation template<class Type> void RSTree<Type>::leftRotation(treenode* &leftNode) { treenode * middleNode = leftNode->right; treenode *parentNode = leftNode->parent; cout << "LR ( " << leftNode->item << ", " << middleNode->item << ")" << endl; leftNode->right = middleNode->left; if (leftNode->right != nullptr) { leftNode->right->parent = leftNode; } middleNode->left = leftNode; middleNode->parent = leftNode->parent; leftNode->parent = middleNode; if (parentNode->left == leftNode) { parentNode->left = middleNode; } else { parentNode->right = middleNode; } } // Rechtsrotation template<class Type> void RSTree<Type>::rightRotation(treenode* &rightNode) { treenode *middleNode = rightNode->left; treenode *parentNode = rightNode->parent; cout << "RR ( " << rightNode->item << ", " << middleNode->item << ")" << endl; rightNode->left = middleNode->right; if (rightNode->left != nullptr) { rightNode->left->parent = rightNode; } middleNode->right = rightNode; middleNode->parent = rightNode->parent; rightNode->parent = middleNode; if (parentNode->left == rightNode) { parentNode->left = middleNode; } else { parentNode->right = middleNode; } } template<class Type> void RSTree<Type>::inorder() { inorder(head->right); cout << endl; } template<class Type> void RSTree<Type>::inorder(treenode* node) { if (node != nullptr) { inorder(node->left); cout << node->item << " "; inorder(node->right); } }
-
as1as schrieb:
Hab jetzt aufjedenfall schon weniger Fehlermeldungen. Aber immer noch ein paar.
Und welche Frage hast Du? Nachdem du jetzt ja weißt, worum es geht ...
treenode *middleNode = rightNode->left; treenode *parentNode = rightNode->parent;
-->
treenode<Type> *middleNode = rightNode->left; treenode<Type> *parentNode = rightNode->parent;
Was anderes:
void RSTree<Type>::rightRotation( treenode<Type>* &rightNode )
Referenzen auf Pointer? Echt jetz?
-
Swordfish schrieb:
as1as schrieb:
Hab jetzt aufjedenfall schon weniger Fehlermeldungen. Aber immer noch ein paar.
Und welche Frage hast Du? Nachdem du jetzt ja weißt, worum es geht ...
treenode *middleNode = rightNode->left; treenode *parentNode = rightNode->parent;
-->
treenode<Type> *middleNode = rightNode->left; treenode<Type> *parentNode = rightNode->parent;
Ah okay. Also man muss auch in den FUnktionen wenn man temoräre Objekte erstellt ect. <Type> benutzen. Mal schauen ob ich danach alle Meldungen weghabe
-
Swordfish schrieb:
Referenzen auf Pointer? Echt jetz?
Find ich genau richtig an dieser Stelle. Spart eine Menge Syntaxlärm vom ständigen dereferenzieren (wie der aussieht, wissen wir aus C - lesbarer wird es damit nicht).
-
Uuuups. Bin da ohne wirklich zu lesen von
*&
statt*
anstatt*&
statt**
ausgegangen.
-
Ich habe nochmal ein kürzer und leichteres Programm rausgesucht mit dem ich mehr Erfahrung habe und versucht dies
mittels Templates zu generalisieren. Jedoch ohne Erfolg.
Hier das funktionnierende Ausgangsprogramm.
Nicht verunsichern lassen von 2-3-4.h ect. ist nur ein Binärbaum.
Welchen ich jedoch später in 2-3-4 überführe.class Baumknoten { public: int zahl; // Datenelement vom Typ int Baumknoten *links; // Zeiger auf linken Nachfolger Baumknoten *rechts; // Zeiger auf rechten Nachfolger Baumknoten() : zahl(), links(0), rechts(0) {} // Konstruktor }; class Binaerbaum { private: Baumknoten *kopfzeiger; // Kopfzeiger: rechter Nachfolger zeigt auf die Wurzel Baumknoten *nullknoten; // Pseudoknoten als Nullzeiger für die Nachfolger eines Blattes public: // Konstruktor Binaerbaum() { kopfzeiger = new Baumknoten; nullknoten = new Baumknoten; } void neues_element_einfuegen(int zahl); // neues Element einfügen Baumknoten* liefer_wurzel(Binaerbaum a);//liefert wurzel ins mainprogramm void Inorder(Baumknoten *n); void Levelorder(Baumknoten *n); }; #include "2-3-4-tree.h" #include <iostream> #include <queue> using namespace std; // neues Element einfügen void Binaerbaum::neues_element_einfuegen(int zahl) { // erstelle neue Knoteninstanz Baumknoten *neues_element = new Baumknoten; neues_element->zahl = zahl; neues_element->links = nullknoten; neues_element->rechts = nullknoten; // wenn Baum leer so wird die erste Eingabe zur "Wurzel" if (kopfzeiger->rechts == nullptr) { kopfzeiger->rechts = neues_element; } // Baum besitzt schon eine "Wurzel" else { // temporäre Datei sodass die Baumstruktur beim traversieren nicht verändert wird Baumknoten *tmp_wurzelknoten = kopfzeiger->rechts; while (true) { // fängt doppelte Eingaben ab if (neues_element->zahl == tmp_wurzelknoten->zahl) { cout << "Element schon vorhanden. Bitte geben Sie eine andere Zahl ein. " << endl; break; } // für jeweils die rechts Baumhälfte, bzw. für den ist größer Fall if (neues_element->zahl > tmp_wurzelknoten->zahl) { if (tmp_wurzelknoten->rechts == nullknoten) { tmp_wurzelknoten->rechts = neues_element; break; } else { tmp_wurzelknoten = tmp_wurzelknoten->rechts; } } // für jeweils die linke Baumhälfte, bzw. für den ist kleiner Fall if (neues_element->zahl < tmp_wurzelknoten->zahl) { if (tmp_wurzelknoten->links == nullknoten) { tmp_wurzelknoten->links = neues_element; break; } else { tmp_wurzelknoten = tmp_wurzelknoten->links; } } } } } Baumknoten* Binaerbaum::liefer_wurzel(Binaerbaum a) { Baumknoten * tmp = kopfzeiger->rechts; return tmp; } //traversiert zuerst rekursiv den linken Teilbaum, dann den Knoten selbst und anschließend den rechten Teilbaum void Binaerbaum::Inorder(Baumknoten *n) { if (n->zahl != 0) { Inorder(n->links); cout << n->zahl << " "; Inorder(n->rechts); } } // traversiert niveau- bzw. levelweise die Knoten void Binaerbaum::Levelorder(Baumknoten *n) { // wenn Baum leer ist if (n == NULL) return; // Erstelle leere Warteschlange queue<Baumknoten *> q; // Wurzel in warteschlange einfügen q.push(n); //solange warteschlange niht leer ist while (q.empty() == false) { // erstelle mir referenz auf nächstes element und gebe element aus , dann entfernen Baumknoten *node = q.front(); cout << node->zahl << " "; q.pop(); // linker knoten in warteschlange einreihen if (node->links != nullknoten) q.push(node->links); // rechter knoten in warteschlange einreihen if (node->rechts != nullknoten) q.push(node->rechts); } } #include "2-3-4-tree.h" #include <iostream> using namespace std; int main() { // erstelle Instanz der Binärbaumklasse um später Funktionen/Methoden auf sie anwenden zu können Binaerbaum a; // Baum wird aufgebaut // Ende mit Eingabe der Null int eingabe = 0; do { cout << "Bitte geben Sie Zahlen ein (Ende durch Eingabe der Null) " << endl; cin >> eingabe; if (eingabe == 0) { break; } a.neues_element_einfuegen(eingabe); } while (true); cout << endl; // liefert mir die wurzel von a, sodass ich sie im hauptprogramm zur verfügung habe Baumknoten *wurzel = a.liefer_wurzel(a); do { cout << endl; cout << "1 : Ausgabe des Baumes in Levelorder" << endl; cout << "2 : Ausgabe des Baumes in Inorder" << endl; cout << "3 : Element einfuegen" << endl; cout << "4 : Quit" << endl; int menueeingabe = 0; cin >> menueeingabe; cout << endl; if (menueeingabe == 2) { // Ausgabe Inorder cout << "Baum in Inorder: " << endl; a.Inorder(wurzel); cout << endl; } if (menueeingabe == 1) { //Ausgabe Levelorder cout << "Baum in Levelorder: " << endl; a.Levelorder(wurzel); cout << endl; } if (menueeingabe == 3) { int zahl; cout << "Geben Sie Ihre gewuenschte Zahl ein: "; cin >> zahl; a.neues_element_einfuegen(zahl); } if (menueeingabe == 4) { break; } } while (true); system("PAUSE"); return 0; }
Hier mein template Versuch.
Ich habe die Stellen wo vermutlich ein Fehler ist, jedoch ich nicht weiterweiß mit !!! kommentiert ( bzw. Zeile 20)template <class Type> class Baumknoten { public: Type zahl; // Datenelement vom Typ int Baumknoten *links; // Zeiger auf linken Nachfolger Baumknoten *rechts; // Zeiger auf rechten Nachfolger Baumknoten() : zahl(), links(0), rechts(0) {} // Konstruktor }; template <class Type> class Binaerbaum { private: Baumknoten<Type> *kopfzeiger; // Kopfzeiger: rechter Nachfolger zeigt auf die Wurzel Baumknoten<Type> *nullknoten; // Pseudoknoten als Nullzeiger für die Nachfolger eines Blattes public: //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! // Konstruktor Binaerbaum() { kopfzeiger = new Baumknoten<Type>; nullknoten = new Baumknoten<Type>; } //ich hatte erst das <Type> hinter den new baumknoten nicht, // nun wo ich es habe bekomme ich einne fehler in main.obj bzw. in der exe //4 nicht aufgelöste elemente //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! void neues_element_einfuegen( :confused: Type zahl); // neues Element einfügen Baumknoten<Type>* liefer_wurzel(Binaerbaum<Type> a);//liefert wurzel ins mainprogramm void Inorder(Baumknoten<Type> *n); void Levelorder(Baumknoten<Type> *n); }; #include "2-3-4-tree.h" #include <iostream> #include <queue> using namespace std; // neues Element einfügen template <class Type> void Binaerbaum<Type>::neues_element_einfuegen(Type zahl) { // erstelle neue Knoteninstanz Baumknoten *neues_element = new Baumknoten; neues_element->zahl = zahl; neues_element->links = nullknoten; neues_element->rechts = nullknoten; // wenn Baum leer so wird die erste Eingabe zur "Wurzel" if (kopfzeiger->rechts == nullptr) { kopfzeiger->rechts = neues_element; } // Baum besitzt schon eine "Wurzel" else { // temporäre Datei sodass die Baumstruktur beim traversieren nicht verändert wird Baumknoten *tmp_wurzelknoten = kopfzeiger->rechts; while (true) { // fängt doppelte Eingaben ab if (neues_element->zahl == tmp_wurzelknoten->zahl) { cout << "Element schon vorhanden. Bitte geben Sie eine andere Zahl ein. " << endl; break; } // für jeweils die rechts Baumhälfte, bzw. für den ist größer Fall if (neues_element->zahl > tmp_wurzelknoten->zahl) { if (tmp_wurzelknoten->rechts == nullknoten) { tmp_wurzelknoten->rechts = neues_element; break; } else { tmp_wurzelknoten = tmp_wurzelknoten->rechts; } } // für jeweils die linke Baumhälfte, bzw. für den ist kleiner Fall if (neues_element->zahl < tmp_wurzelknoten->zahl) { if (tmp_wurzelknoten->links == nullknoten) { tmp_wurzelknoten->links = neues_element; break; } else { tmp_wurzelknoten = tmp_wurzelknoten->links; } } } } } template <class Type> Baumknoten<Type>* Binaerbaum<Type>::liefer_wurzel(Binaerbaum<Type> a) { Baumknoten * tmp = kopfzeiger->rechts; return tmp; } //traversiert zuerst rekursiv den linken Teilbaum, dann den Knoten selbst und anschließend den rechten Teilbaum template <class Type> void Binaerbaum<Type>::Inorder(Baumknoten<Type> *n) { if (n->zahl != 0) { Inorder(n->links); cout << n->zahl << " "; Inorder(n->rechts); } } // traversiert niveau- bzw. levelweise die Knoten template <class Type> void Binaerbaum<Type>::Levelorder(Baumknoten<Type> *n) { // wenn Baum leer ist if (n == NULL) return; // Erstelle leere Warteschlange queue<Baumknoten<Type> * q; // Wurzel in warteschlange einfügen q.push(n); //solange warteschlange niht leer ist while (q.empty() == false) { // erstelle mir referenz auf nächstes element und gebe element aus , dann entfernen Baumknoten<Type> *node = q.front(); cout << node->zahl << " "; q.pop(); // linker knoten in warteschlange einreihen if (node->links != nullknoten) q.push(node->links); // rechter knoten in warteschlange einreihen if (node->rechts != nullknoten) q.push(node->rechts); } } #include "2-3-4-tree.h" #include <iostream> using namespace std; int main() { // erstelle Instanz der Binärbaumklasse um später Funktionen/Methoden auf sie anwenden zu können Binaerbaum<int> a; // Baum wird aufgebaut // Ende mit Eingabe der Null int eingabe = 0; do { cout << "Bitte geben Sie Zahlen ein (Ende durch Eingabe der Null) " << endl; cin >> eingabe; if (eingabe == 0) { break; } a.neues_element_einfuegen(eingabe); } while (true); cout << endl; // liefert mir die wurzel von a, sodass ich sie im hauptprogramm zur verfügung habe Baumknoten<int> *wurzel = a.liefer_wurzel(a); do { cout << endl; cout << "1 : Ausgabe des Baumes in Levelorder" << endl; cout << "2 : Ausgabe des Baumes in Inorder" << endl; cout << "3 : Element einfuegen" << endl; cout << "4 : Quit" << endl; int menueeingabe = 0; cin >> menueeingabe; cout << endl; if (menueeingabe == 2) { // Ausgabe Inorder cout << "Baum in Inorder: " << endl; a.Inorder(wurzel); cout << endl; } if (menueeingabe == 1) { //Ausgabe Levelorder cout << "Baum in Levelorder: " << endl; a.Levelorder(wurzel); cout << endl; } if (menueeingabe == 3) { int zahl; cout << "Geben Sie Ihre gewuenschte Zahl ein: "; cin >> zahl; a.neues_element_einfuegen(zahl); } if (menueeingabe == 4) { break; } } while (true); system("PAUSE"); return 0; }
-
#include <iostream> #include <queue> using namespace std; template <class Type> class Baumknoten { public: Type zahl; Baumknoten<Type> *links; Baumknoten<Type> *rechts; Baumknoten() : zahl(), links( 0 ), rechts( 0 ) {} }; template <class Type> class Binaerbaum { private: Baumknoten<Type> *kopfzeiger; // Kopfzeiger: rechter Nachfolger zeigt auf die Wurzel Baumknoten<Type> *nullknoten; // Pseudoknoten als Nullzeiger für die Nachfolger eines Blattes // <<== was jetzt? nullptr oder doch was? new im c-tor?? public: Binaerbaum() { kopfzeiger = new Baumknoten<Type>; nullknoten = new Baumknoten<Type>; } void neues_element_einfuegen( Type zahl ); Baumknoten<Type>* liefer_wurzel( Binaerbaum<Type> a ); void Inorder( Baumknoten<Type> *n ); void Levelorder( Baumknoten<Type> *n ); }; template <class Type> void Binaerbaum<Type>::neues_element_einfuegen( Type zahl ) { // erstelle neue Knoteninstanz Baumknoten<Type> *neues_element = new Baumknoten<Type>; neues_element->zahl = zahl; neues_element->links = nullknoten; neues_element->rechts = nullknoten; // wenn Baum leer so wird die erste Eingabe zur "Wurzel" if( kopfzeiger->rechts == nullptr ) { kopfzeiger->rechts = neues_element; } // Baum besitzt schon eine "Wurzel" else { // temporäre Datei sodass die Baumstruktur beim traversieren nicht verändert wird Baumknoten<Type> *tmp_wurzelknoten = kopfzeiger->rechts; while( true ) { // fängt doppelte Eingaben ab if( neues_element->zahl == tmp_wurzelknoten->zahl ) { cout << "Element schon vorhanden. Bitte geben Sie eine andere Zahl ein.\n"; break; } // für jeweils die rechts Baumhälfte, bzw. für den ist größer Fall if( neues_element->zahl > tmp_wurzelknoten->zahl ) { if( tmp_wurzelknoten->rechts == nullknoten ) { tmp_wurzelknoten->rechts = neues_element; break; } else { tmp_wurzelknoten = tmp_wurzelknoten->rechts; } } // für jeweils die linke Baumhälfte, bzw. für den ist kleiner Fall if( neues_element->zahl < tmp_wurzelknoten->zahl ) { if( tmp_wurzelknoten->links == nullknoten ) { tmp_wurzelknoten->links = neues_element; break; } else { tmp_wurzelknoten = tmp_wurzelknoten->links; } } } } } template <class Type> Baumknoten<Type>* Binaerbaum<Type>::liefer_wurzel( Binaerbaum<Type> a ) { Baumknoten<Type> * tmp = kopfzeiger->rechts; return tmp; } //traversiert zuerst rekursiv den linken Teilbaum, dann den Knoten selbst und anschließend den rechten Teilbaum template <class Type> void Binaerbaum<Type>::Inorder( Baumknoten<Type> *n ) { if( n->zahl != 0 ) { Inorder( n->links ); cout << n->zahl << " "; Inorder( n->rechts ); } } // traversiert niveau- bzw. levelweise die Knoten template <class Type> void Binaerbaum<Type>::Levelorder( Baumknoten<Type> *n ) { // wenn Baum leer ist if( n == NULL ) return; // Erstelle leere Warteschlange queue<Baumknoten<Type>*> q; // Wurzel in warteschlange einfügen q.push( n ); //solange warteschlange niht leer ist while( q.empty() == false ) { // erstelle mir referenz auf nächstes element und gebe element aus , dann entfernen Baumknoten<Type> *node = q.front(); cout << node->zahl << " "; q.pop(); // linker knoten in warteschlange einreihen if( node->links != nullknoten ) q.push( node->links ); // rechter knoten in warteschlange einreihen if( node->rechts != nullknoten ) q.push( node->rechts ); } } int main() { // erstelle Instanz der Binärbaumklasse um später Funktionen/Methoden auf sie anwenden zu können Binaerbaum<int> a; // Baum wird aufgebaut // Ende mit Eingabe der Null int eingabe = 0; do { cout << "Bitte geben Sie Zahlen ein (Ende durch Eingabe der Null)\n"; cin >> eingabe; if( eingabe == 0 ) break; a.neues_element_einfuegen( eingabe ); } while( true ); cout.put('\n'); // liefert mir die wurzel von a, sodass ich sie im hauptprogramm zur verfügung habe Baumknoten<int> *wurzel = a.liefer_wurzel( a ); do { cout << "\n1: Ausgabe des Baumes in Levelorder\n"; cout << "2: Ausgabe des Baumes in Inorder\n"; cout << "3: Element einfuegen\n"; cout << "4: Quit\n"; int menueeingabe = 0; cin >> menueeingabe; cout.put('\n'); if( menueeingabe == 2 ) { // Ausgabe Inorder cout << "Baum in Inorder:\n"; a.Inorder( wurzel ); cout.put('\n'); } if( menueeingabe == 1 ) { //Ausgabe Levelorder cout << "Baum in Levelorder:\n"; a.Levelorder( wurzel ); cout.put('\n'); } if( menueeingabe == 3 ) { int zahl; cout << "Geben Sie Ihre gewuenschte Zahl ein: "; cin >> zahl; a.neues_element_einfuegen( zahl ); } if( menueeingabe == 4 ) { break; } } while( true ); }
-
Habe meine Fehler korrigiert aber bekomme immer noch die Fehlermeldung mit den 4 nicht aufgelößten Externen. Hab auch den Code mal kopiert, das ich vllt etwas übersehen habe, aber gleiche Meldung.
-
Templates müssen in der Übersetzungseinheit, in der sie instanziiert werden, komplett bekannt sein. Pack die Definitionen in die Headerdatei und wirf die
.cpp
weg.
-
Auch smarte pointer sind hier nicht fehl am Platz.
-
Swordfish schrieb:
Templates müssen in der Übersetzungseinheit, in der sie instanziiert werden, komplett bekannt sein. Pack die Definitionen in die Headerdatei und wirf die
.cpp
weg.Super danke jetzt funktioniert es:)
Hast du oder jemand anderes vllt eine gute Seite oder ein Buch zu empfehlen wo
so grundlegende Sachen Schritt für Schritt erklärt werden?
Weil ich zb. wäre jetzt anhand des Fehlercodes "4 nicht aufgelößten Externen"
nie darauf gekommen das es dadran liegt das man die Funktionsrümpfe nicht in der
cpp.Datei ausprogrammieren darf bei templates.bzw sie inder headerdatei bekannt sein müssen.
lg
-
Der C++-Programmierer: C++ lernen - professionell anwenden - Lösungen nutzen wird gerne empfohlen.