Thread: Need template help

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    Need template help

    Can anyone tell me what is wrong with this Queue template? My program keeps locking up.
    #include<iostream>
    #include<fstream>
    #include<iomanip>
    #include<queue>

    #include"BSTTreeAndyJackson.cpp"



    using namespace std;
    //template<class Type>

    int main()
    {
    btree bt;
    node nd;
    int num=0;
    char chr;
    int count=0;


    fin.open("input.txt");
    fout.open("output1.txt");










    // ifstream fin;
    // ofstream fout;




    fin>>num;
    fin>>chr;

    while(!fin.eof())

    {

    count++;
    fout<<"Step: "<<count<<" "<<"Data Value = "<<num<<" "<<
    "Activity Signal = "<<chr<<endl<<endl;
    if(chr == 'A')
    {
    bt.insert(num);
    }
    else if(chr == 'D')
    {
    //bt.deletenode();
    }
    bt.Output("InOrderTranverse = ");

    bt.InOrderTranverse();
    fout<<endl<<endl;

    bt.Output("PreOrder Tranverse = ");
    bt.preOrderTranverse();
    fout<<endl<<endl;

    bt.Output("PostOrder Tranverse = ");
    bt.PostOrderTranverse();
    fout<<endl<<endl;


    bt.Output("LevelOrderTranverse = ");
    //bt.LevelOrder();
    fout<<endl<<endl;


    bt.Output("Total number of Nodes in the tree = ");
    fout<<endl<<endl<<endl;


    fin>>num;
    fin>>chr;

    }



    return 0;
    }

    #include"BSTTreeAndyJackson.h"
    #include<iostream>

    ifstream fin;
    ofstream fout;

    //Constructor
    ///////////////////////////////////////////////////////////////////////
    btree::btree()
    //Post: root == NULL
    {
    root=NULL;
    }
    //Destructor
    //////////////////////////////////////////////////////////////////////
    btree::~btree()
    //Post: Destroy all the nodes and free up the memorey.
    {

    destroy_tree();

    }
    //Delete Node
    //////////////////////////////////////////////////////////////////////
    void btree::deletenode(node *leaf)
    {
    if(leaf!=NULL){
    delete root;
    //destroy_tree(leaf->left);
    //destroy_tree(leaf->right);
    }

    }
    //Delete Node
    //////////////////////////////////////////////////////////////////////
    void btree::deletenode()
    //Pre: Input into root
    //Post: If root != NULL the call the Tranverse function
    {
    if(root != NULL)
    {
    deletenode(root);
    }
    else

    return;

    }
    //Destriy tree function
    //////////////////////////////////////////////////////////////////////
    void btree::destroy_tree(node *leaf)
    //Pre: The tree is built
    //Post: Destroy all the nodes of the tree
    {
    if(leaf!=NULL)
    {
    destroy_tree(leaf->left);
    destroy_tree(leaf->right);
    delete leaf;
    }
    }
    //Destroy Tree
    //////////////////////////////////////////////////////////////////////
    void btree::destroy_tree()
    //Pre: If the root is not zero
    //Post: Call the destroy tree function.
    {

    if(root != NULL)
    destroy_tree(root);

    else

    return;
    }
    //Insert Tree
    //////////////////////////////////////////////////////////////////////
    void btree::insert(int key, node *leaf)
    //Pre: Pointer != Null
    //Post Assign the value to left or right of the tree
    {

    if(key< leaf->key_value)
    {
    if(leaf->left!=NULL)
    insert(key, leaf->left);
    else
    {
    leaf->left=new node;
    leaf->left->key_value=key;
    leaf->left->left=NULL; //Sets the left child of the child node to null
    leaf->left->right=NULL; //Sets the right child of the child node to null
    }
    }
    else if(key>=leaf->key_value)
    {
    if(leaf->right!=NULL)
    insert(key, leaf->right);
    else
    {
    leaf->right=new node;
    leaf->right->key_value=key;
    leaf->right->left=NULL; //Sets the left child of the child node to null
    leaf->right->right=NULL; //Sets the right child of the child node to null

    }

    }
    }




    ///////////////////////////////////////////////////////////////////////

    void btree::insert(int key)
    //Pre: If root != NULL
    //Post: Assign the value to the left of the tree or the right of the tree
    {
    if(root!=NULL)
    insert(key, root);
    else
    {
    root=new node;
    root->key_value=key;
    root->left=NULL;
    root->right=NULL;
    }
    }



    //////////////////////////////////////////////////////////////////////

    void btree::InOrderTranverse(node *leaf)
    //Pre Pointer points to the root of the binary tree
    //Post: Each node of the tree has been visited
    {

    if(leaf->left != NULL)
    InOrderTranverse(leaf->left);

    fout<<leaf->key_value<< " ";

    if(leaf->right !=NULL)
    InOrderTranverse(leaf->right);
    }
    //////////////////////////////////////////////////////////////////////
    void btree::InOrderTranverse()
    //Pre: Input into root
    //Post: If root != NULL the call the Tranverse function
    {
    if(root!=NULL)
    InOrderTranverse(root);
    else

    return;
    }
    //////////////////////////////////////////////////////////////////////
    void btree:reOrderTranverse(node *leaf)
    //Pre Pointer points to the root of the binary tree
    //Post: Each node of the tree has been visited
    {
    if(leaf != NULL){

    fout<<leaf->key_value<<" ";
    preOrderTranverse(leaf->left);
    preOrderTranverse(leaf->right);
    }
    }

    ///////////////////////////////////////////////////////////////////////
    void btree:reOrderTranverse()
    //Pre: Input into root
    //Post: If root != NULL the call the Tranverse function
    {
    if(root!=NULL)
    preOrderTranverse(root);
    else

    return;
    }
    //PostOrder
    //////////////////////////////////////////////////////////////////////
    void btree::PostOrderTranverse()
    //Pre: Input into root
    //Post: If root != NULL the call the Tranverse function
    {
    if(root!=NULL)
    PostOrderTranverse(root);
    else

    return;
    }

    //Post Order Tranverse
    //////////////////////////////////////////////////////////////////////
    void btree::PostOrderTranverse(node *leaf)
    //Pre Pointer points to the root of the binary tree
    //Post: Each node of the tree has been visited
    {
    if(leaf != NULL){
    PostOrderTranverse(leaf->left);
    PostOrderTranverse(leaf->right);
    fout<<leaf->key_value<<" ";
    }
    }
    template<class node>
    void btree::LevelOrder()
    {

    Queue<node>q;
    node *leaf = root;
    while(leaf){
    cout<<leaf->key_value<<endl;
    if(leaf->left)q.Add(leaf->left);
    if(leaf->right)q.Add(leaf->right);
    node=*q.Delete(node);
    }
    }

    //Output Function
    //////////////////////////////////////////////////////////////////////
    void btree::Output(const char prompt[])
    {
    fout<<prompt;
    }

    #include<fstream.h>


    struct node;

    typedef node *Nodeptr;

    struct node
    {
    int key_value;
    node *left;
    node *right;
    node *leaf;
    };

    //template<class node>
    class btree
    {
    public:
    btree();
    ~btree();
    void insert(int key);
    void InOrderTranverse();
    void preOrderTranverse();
    void PostOrderTranverse();
    void destroy_tree();
    void deletenode();
    void Output(const char prompt[]);
    void LevelOrder();

    private:
    void insert(int key, node *leaf);
    void InOrderTranverse(node *leaf);
    void preOrderTranverse(node *leaf);
    void PostOrderTranverse(node *leaf);
    void destroy_tree(node *leaf);
    void deletenode(node *leaf);



    node *root;

    };

  2. #2
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    Code:
    template <class node>
    I dont think that would work, because one of your classes is physically named node. Do something like this:

    template <class ItemType>

    Then change it withing your class...it should work...
    My Website

    "Circular logic is good because it is."

  3. #3
    Registered User
    Join Date
    Aug 2001
    Posts
    84
    So everywhere in my program I have node I should change it to Itemtype?

  4. #4
    Registered User kitten's Avatar
    Join Date
    Aug 2001
    Posts
    109
    typedef node *Nodeptr;
    template<class node>
    This is generally bad idea because typedef defines a new variable type and template<class> defines a template identifier. So you should change other to something else than node. f.ex template <class T>
    Making error is human, but for messing things thoroughly it takes a computer

  5. #5
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    Just a comment. Are you making a queue or a binary tree? These are different ADT's. Also, you can define your structure inside your class as a private member.

  6. #6
    Registered User
    Join Date
    Aug 2001
    Posts
    84

    BST

    I am making both. The queue just does the LevelOrder Tranverse and the BST dos the other three Tranverse's

  7. #7
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    It sounds complex. Well I heard that one way to go about it is to write the code without the template syntax, than add it afterward once you know that the class works normally. Likely put the structure declaration into the class though as a private data member.

  8. #8
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    This small queue template is an example of what I mean. Declaring the structure within the class.

    Code:
    #include <iostream.h>
    #include <stdlib.h>
    #include <string.h>
    
    template <class T>
    class CQueue
    {
    	private:
    		typedef struct node_s 
    		{
    			T item;
    			node_s * next;
    			node_s (T x) { item = x; next = NULL;}
    		}LList;
    
    		LList *head, *tail;
    		int max_size;
    		int current_size;
    
    	public:
    		CQueue(int iSize) 
    		{ 
    			max_size = iSize;
    			current_size = 0;
    			head = NULL;
    		}
    
    		bool empty() const { return head == NULL; }
    
    		void In(T x) 
    		{	
    			if( current_size < max_size)
    			{
    				current_size ++;
    				LList *t = tail;
    				tail = new node_s(x);
    				if(head == NULL) 
    				{
    					head = tail;
    				}else
    				{
    					t->next = tail;
    				}
    			}else
    			{
    				throw CqueueFull();
    			}
    		}
    
    		T Out()
    		{
    			if(!empty())
    			{
    				T v = head->item; 
    				LList *t = head->next;
    				delete head;
    				head = t;
    				return v;
    			}else
    			{
    				throw CqueueEmpty();
    			}
    		}
    		//exception classes
    		class CqueueFull{};
    		class CqueueEmpty {};
    };
    
    int main()
    {
    	try
    	{
    
    		CQueue<double> Q(16);
    		Q.In(12.3);
    		Q.In(45.2);
    		Q.In(67.69);
    		Q.In(8.98);
    
    
    		cout << "Out: " << Q.Out() << endl;
    		cout << "OUt: " << Q.Out() << endl;
    		cout << "OUt: " << Q.Out() << endl;
    		cout << "OUt: " << Q.Out() << endl;
    	}
    	catch(CQueue<double>::CqueueFull)
    	{
    		cout << "Queue is full." << endl;
    	}
    	catch(CQueue<double>::CqueueEmpty)
    	{
    		cout << "Queue is Empty." << endl;
    	}
    
    	return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Specialising a member function with a template template parameter
    By the4thamigo_uk in forum C++ Programming
    Replies: 10
    Last Post: 10-12-2007, 04:37 AM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. error: template with C linkage
    By michaels-r in forum C++ Programming
    Replies: 3
    Last Post: 05-17-2006, 08:11 AM
  4. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  5. oh me oh my hash maps up the wazoo
    By DarkDays in forum C++ Programming
    Replies: 5
    Last Post: 11-30-2001, 12:54 PM