C++

Forum

 
linker issues

kakashi316 (156)
Im getting linker issues with a program ive been writing.I am using DEV C++,i tried running on microsoft visual C++ 2008 and it was giving me linker issues there too.
[Linker error] undefined reference to `BTree<int>::BFS(std::ostream&)'
[Linker error] undefined reference to `BTree<int>::DFS(std::ostream&)'
[Linker error] undefined reference to `BTree<int>::R_InOrder(NodeType<int>*, std::ostream&)'
[Linker error] undefined reference to `BTree<int>::R_PreOrder(NodeType<int>*, std::ostream&)'
[Linker error] undefined reference to `BTree<int>::R_PostOrder(NodeType<int>*, std::ostream&)'

main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
#include "BTree.h"
#include "BSTree.h"
#include<iostream>
using namespace std;
main()
{
      BTree<int> BT;
      BSTree<int>BST;
      
      int x;
      int i;
      for(i=1;i<=5; i++)
      {
              x=rand()%100;
              BT.Insert(x);
              BST.Insert(x);
      }
      cout<<"Random Binary Tree: "<<endl;
      cout<<"Inorder"<<endl;
      BT.InOrder(cout);
      cout<<endl;
       cout<<"Preorder"<<endl;
      BT.PreOrder(cout);
      cout<<endl;
      cout<<"Postorder"<<endl;
      BT.PostOrder(cout);
      cout<<endl;
      cout<<"BFS"<<endl;
      BT.BFS(cout);
      cout<<endl;
      cout<<"DFS"<<endl;
      BT.DFS(cout);
      cout<<endl;
      cout<<"Binary Search tree: "<<endl;
       cout<<"Inorder"<<endl;
      BST.InOrder(cout);
      cout<<endl;
       cout<<"Postorder"<<endl;
      BST.PostOrder(cout);
      cout<<endl;
       cout<<"Preorder"<<endl;
      BST.PreOrder(cout);
      cout<<endl;
      //x=46;
//      cout<<"Search: "<<x<<endl;
//      if(BST.Search(x))
//      {
//         cout<<"Found"<<endl;
//      }
//      else
//      {
//          cout<<"Not found"<<endl;
//       }

      
      //cout<<"Delete: "<<x<<endl;
      //BST.Delete(x);
      //BST.InOrder(cout);
    //  cout<<endl;
//      BST.PreOrder(cout);
//      cout<<endl;
//      
     char quit;
     cin>>quit;
     return 0;
}


header
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
#ifndef BTree_H
#define BTree_H

#include <fstream>
#include <stdlib.h>
#include "Queue.cpp"
#include "Stack.cpp"
#include "Node.cpp"
#include<iostream>
using namespace std;

template <class ItemType>
class BTree
{
      typedef NodeType<ItemType> * TreePtr;
      TreePtr Tree;
      void R_InOrder(TreePtr, ostream &);
      void R_PreOrder(TreePtr, ostream &);
      void R_PostOrder(TreePtr, ostream &);
      int R_Height(TreePtr);
      int R_Count(TreePtr);
      void R_Clear(TreePtr &);
      void R_Insert(TreePtr &, ItemType x, int=0, int=0);
   public:
    BTree(){Tree=NULL;};
      void InOrder(ostream &output){R_InOrder(Tree, output);};
      void PreOrder(ostream &output){R_PreOrder(Tree, output);};
      void PostOrder(ostream &output){R_PostOrder(Tree, output);};
      void BFS(ostream &output);
      void DFS(ostream &output);
      int Height(){return R_Height(Tree);};
      int Count(){return R_count(Tree);};
      virtual void Insert(ItemType x){R_Insert(Tree, x);};
      void Clear(){R_Clear(Tree);};
      ~BTree(){R_Clear(Tree);};

};
#endif


implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
#include "BTree.h"
#include<iostream>
using namespace std;
template <class ItemType>
int BTree<ItemType>::R_Height(TreePtr t)
{
    if (t==NULL)
       return 0;
    int LTHT=R_Height(t->Lt);
    int RTHT=R_Height(t->Rt);
    if (LTHT>=RTHT)
    {
       return(LTHT+1);
    }
    else
        return(RTHT+1);
}
template <class ItemType>
int BTree<ItemType>::R_Count(TreePtr t)
{
    if (t==NULL)
       return 0;
    int LTCT=R_Count(t->Lt);
    int RTCT=R_Count(t->Rt);
    return (RTCT+LTCT+1);
}

template<class ItemType>
void BTree<ItemType>::R_Insert(TreePtr &t,ItemType x, int lev,int bal)
{
     bool GoLt;
     if(t==NULL)
     {
                t= new NodeType<ItemType>(x,lev);
                t->Lt=t->Rt=NULL;
     }
     else
     {
         GoLt=rand()%2;
         if(GoLt)
          R_Insert(t->Lt,x,lev+1,bal);
         else
             R_Insert(t->Rt,x,lev+1,bal);
     }
}
template<class ItemType>
void BTree<ItemType>::R_PreOrder(TreePtr t,ostream& output)
{
     if(t!=NULL)
     {
                output<<t->item<<"("<<t->level<<")";
                R_PreOrder(t->Lt,output);
                R_PreOrder(t->Rt,output);
     }
}
template<class ItemType>
void BTree<ItemType>::R_InOrder(TreePtr t,ostream& output)
{
     if(t!=NULL)
     {
                
                R_InOrder(t->Lt,output);
                output<<t->item<<"("<<t->level<<")";
                R_InOrder(t->Rt,output);
     }
}
template<class ItemType>
void BTree<ItemType>::R_PostOrder(TreePtr t,ostream & output)
{
     if(t!=NULL)
     {
                R_PostOrder(t->Lt,output);
                R_PostOrder(t->Rt,output);
                output<<t->item<<"("<<t->level<<")";
     }
}

template<class ItemType>
void BTree<ItemType>::BFS(ostream &output)
{
     TreePtr t=Tree;
     Queue<TreePtr>q;
     q.enqueue(t);
     while(!q.IsEmpty())
     {
        q.dequeue(t);
        output<<t->item<<"("<<t->level<<")";
        if(t->Lt!=NULL) q.enqueue(t->Lt);
        if(t->Rt!=NULL) q.enqueue(t->Rt);
     }
}


template<class ItemType>
void BTree<ItemType>::DFS(ostream &output)
{
     TreePtr t=Tree;
     Stack<TreePtr>s;
     s.push(t);
     while(s.IsEmpty())
     {
        s.pop(t);
        output<<t->item<<"("<<t->level<<")";
        if(t->Rt!=NULL) s.push(t->Rt);
        if(t->Lt!=NULL) s.push(t->Lt);
     }
}

template<class ItemType>
void BTree<ItemType>::R_Clear(TreePtr &t)
{
     if (t!=NULL)
     {
        R_Clear(t->Lt);
        R_Clear(t->Rt);
        delete t;
        t=NULL; 
     }
}
BTree<int>BT;


there is more code that goes with this program but im posting the most relevant. i now theres a way to just add the .cpp to the .h and that would fix it. but either way,if someone can just put me in the right direction i would be appreciative.
melkiy (131)
Generally, templates do not generate object code if there are no instances of them.
Templates definitions must occure at each *.cpp file that uses them. So, the proper place for templates is *.h files.

Try this. But other pitfalls may occur.
marknyc (18)
Judging from you code we both have the same professor. I see what your problem is but first let me find out what class are in you morning or the night class.
kakashi316 (156)
whats my problem first?
Zhuge (4664)
melkiy seems to have described it pretty explicitly.
marknyc (18)
You don't have queue or stack.cpp in your btree.cpp. You have them in your Btree header which is wrong. Trust me I know because I have it running. You need those.
Zhuge (4664)
You shouldn't be including source at all, just link it. If they are templates, the source should go in the header unless you have another fancy method for dealing with it (export, etc.)
kakashi316 (156)
ok, i have

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
#include "Queue.cpp"
#include "Stack.cpp"
#include "BTree.h"
#include<iostream>
using namespace std;
template <class ItemType>
int BTree<ItemType>::R_Height(TreePtr t)
{
    if (t==NULL)
       return 0;
    int LTHT=R_Height(t->Lt);
    int RTHT=R_Height(t->Rt);
    if (LTHT>=RTHT)
    {
       return(LTHT+1);
    }
    else
        return(RTHT+1);
}
template <class ItemType>
int BTree<ItemType>::R_Count(TreePtr t)
{
    if (t==NULL)
       return 0;
    int LTCT=R_Count(t->Lt);
    int RTCT=R_Count(t->Rt);
    return (RTCT+LTCT+1);
}

template<class ItemType>
void BTree<ItemType>::R_Insert(TreePtr &t,ItemType x, int lev,int bal)
{
     bool GoLt;
     if(t==NULL)
     {
                t= new NodeType<ItemType>(x,lev);
                t->Lt=t->Rt=NULL;
     }
     else
     {
         GoLt=rand()%2;
         if(GoLt)
          R_Insert(t->Lt,x,lev+1,bal);
         else
             R_Insert(t->Rt,x,lev+1,bal);
     }
}
template<class ItemType>
void BTree<ItemType>::R_PreOrder(TreePtr t,ostream& output)
{
     if(t!=NULL)
     {
                output<<t->item<<"("<<t->level<<")";
                R_PreOrder(t->Lt,output);
                R_PreOrder(t->Rt,output);
     }
}
template<class ItemType>
void BTree<ItemType>::R_InOrder(TreePtr t,ostream& output)
{
     if(t!=NULL)
     {
                
                R_InOrder(t->Lt,output);
                output<<t->item<<"("<<t->level<<")";
                R_InOrder(t->Rt,output);
     }
}
template<class ItemType>
void BTree<ItemType>::R_PostOrder(TreePtr t,ostream & output)
{
     if(t!=NULL)
     {
                R_PostOrder(t->Lt,output);
                R_PostOrder(t->Rt,output);
                output<<t->item<<"("<<t->level<<")";
     }
}

template<class ItemType>
void BTree<ItemType>::BFS(ostream &output)
{
     TreePtr t=Tree;
     Queue<TreePtr>q;
     q.enqueue(t);
     while(!q.IsEmpty())
     {
        q.dequeue(t);
        output<<t->item<<"("<<t->level<<")";
        if(t->Lt!=NULL) q.enqueue(t->Lt);
        if(t->Rt!=NULL) q.enqueue(t->Rt);
     }
}


template<class ItemType>
void BTree<ItemType>::DFS(ostream &output)
{
     TreePtr t=Tree;
     Stack<TreePtr>s;
     s.push(t);
     while(s.IsEmpty())
     {
        s.pop(t);
        output<<t->item<<"("<<t->level<<")";
        if(t->Rt!=NULL) s.push(t->Rt);
        if(t->Lt!=NULL) s.push(t->Lt);
     }
}

template<class ItemType>
void BTree<ItemType>::R_Clear(TreePtr &t)
{
     if (t!=NULL)
     {
        R_Clear(t->Lt);
        R_Clear(t->Rt);
        delete t;
        t=NULL; 
     }
}
BTree<int>BT;


and

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
//#include <fstream>
#include <stdlib.h>
#include "Node.cpp"
#include<iostream>
using namespace std;

template <class ItemType>
class BTree
{
      typedef NodeType<ItemType> * TreePtr;
      TreePtr Tree;
      void R_InOrder(TreePtr, ostream &);
      void R_PreOrder(TreePtr, ostream &);
      void R_PostOrder(TreePtr, ostream &);
      int R_Height(TreePtr);
      int R_Count(TreePtr);
      void R_Clear(TreePtr &);
      void R_Insert(TreePtr &, ItemType x, int=0, int=0);
   public:
    BTree(){Tree=NULL;};
      void InOrder(ostream &output){R_InOrder(Tree, output);};
      void PreOrder(ostream &output){R_PreOrder(Tree, output);};
      void PostOrder(ostream &output){R_PostOrder(Tree, output);};
      void BFS(ostream &output);
      void DFS(ostream &output);
      int Height(){return R_Height(Tree);};
      int Count(){return R_count(Tree);};
      virtual void Insert(ItemType x){R_Insert(Tree, x);};
      void Clear(){R_Clear(Tree);};
      ~BTree(){R_Clear(Tree);};

};
#endif


still getting the same thing.would i be better off by just putting the implementation in the header?
Zhuge (4664)
You don't really have a choice if you are using templates.
kakashi316 (156)
you wouldnt happen to know a link that would help make it easier?
marknyc (18)
in your Btree header you are missing

#ifndef BTREE_H
#define BREE_H

Where are they
I think that might be your problem
Zhuge (4664)
You should add the header guards marknyc suggests as well in case you ever include the file more than once. And I don't think a link is really necessary...just move the function definitions into the header.
Topic archived. No new replies allowed.