C++

Forum

 
Undefined Reference error

gpetter21 (3)
I have been staring at my makefile and my #includes for hours and I cannot figure out why this program has a linker error

It must be a very silly mistake, any help would be greatly appreciated.
It says "undefined reference to BinarySearchTree" and all of its methods
I don't think you need to really look at the guts of the code, just the includes

Makefile
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
 BST: main.o BinaryNode.o BinarySearchTree.o DictionaryEntry.o NotFoundException.o
	g++ -g -std=c++11 main.o BinaryNode.o BinarySearchTree.o DictionaryEntry.o NotFoundException.o -o BST

main.o: main.cpp BinarySearchTree.h DictionaryEntry.h
	g++ -g -std=c++11 -c main.cpp

BinaryNode.o: BinaryNode.h BinaryNode.cpp
	g++ -g -std=c++11 -c BinaryNode.cpp

BinarySearchTree.o: BinarySearchTree.h BinarySearchTree.cpp
	g++ -g -std=c++11 -c BinarySearchTree.cpp

DictionaryEntry.o: DictionaryEntry.h DictionaryEntry.cpp
	g++ -g -std=c++11 -c DictionaryEntry.cpp

NotFoundException.o: NotFoundException.h NotFoundException.cpp
	g++ -g -std=c++11 -c NotFoundException.cpp

clean:
	rm *.o BST


main.cpp
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
 
#include <iostream>
#include <string>
#include <fstream>
#include "BinarySearchTree.h"
#include "DictionaryEntry.h"
using namespace std;

int main(int argc, char* argv[])
{
	string filename=argv[1];
	string line;
	ifstream inp(filename);
	BinarySearchTree<DictionaryEntry, string> bst;

	while(getline(inp,line))
	{
		if(line.length()>1)
		{
			string word=line.substr(0, line.find(" "));
			string rest=line.substr(line.find(" ")+1);
			DictionaryEntry de(word,rest);
			bst.add(de);
		}
	}

	cout << "Welcome to the dictionary!" << endl;
	string s;
	do
	{
		cout << "What would you like to do? (search, save, copy, add, remove, save, test, quit)" << endl;
		cin >> s;
		if(s=="search" || s=="Search")
		{
			cout << "Enter a search key" << endl;
			string search;
			cin >> search;
			if(bst.contains(search))
			{
				DictionaryEntry d=bst.getEntry(search);
				cout << d.getWord() << d.getDef() << endl;
			}
			else
			{
				cout << "Word not found!" << endl;
			}
		}
		else if(s=="save" || s=="Save")
		{
			cout << "Please enter an output file name (.txt)" << endl;
			string output_file;
			cin >> output_file;
			ofstream out(output_file);
			cout << "What order would you like to traverse in? (in/pre/post)" << endl;
			string order;
			cin >> order;
			
			cout << "Which dictionary to save? (original or copy)" << endl;
			string type;
			cin >> type;
			if(order=="post" || order=="Post")
			{
				if(type=="original" || "Original")
				{
				}
				else if(type=="copy" || type=="Copy")
				{
				}
			}
			else if(order=="in" || order=="In")
			{
				if(type=="original" || "Original")
				{
				}
				else if(type=="copy" || type=="Copy")
				{
				}
			}
			else if(order=="pre" || order=="Pre")
			{
				if(type=="original" || "Original")
				{
				}
				else if(type=="copy" || type=="Copy")
				{
				}
			}
			
		}
		else if(s=="copy" || s=="Copy")
		{
			
		}
		else if(s=="add" || s=="Add")
		{
			cout << "Please enter a word to be added to the dictionary" << endl;
			string newWord;
			cin >> newWord;
			
		}
		else if(s=="remove" || s=="Remove")
		{
			cout << "Please input a word to remove from the dictionary" << endl;
			string removeWord;
			cin >> removeWord;
			
			
		}
		else if(s=="test" || s=="Test")
		{
		}
		
	}while(s!="Quit" || s!="quit");
	
	return(0);
}


BinarySearchTree.h
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
 
#ifndef _BINARY_SEARCH_TREE
#define _BINARY_SEARCH_TREE

#include "BinaryNode.h"
#include "NotFoundException.h"

template<typename ItemType, typename KeyType>
class BinarySearchTree
{
private:
   BinaryNode<ItemType>* rootPtr;
   
   // Recursively deletes all nodes from the tree.
   void destroyTree(BinaryNode<ItemType>* subTreePtr);

   // Recursively finds where the given node should be placed and
   // inserts it in a leaf at that point.
   BinaryNode<ItemType>* insertInorder(BinaryNode<ItemType>* subTreePtr,
                                       BinaryNode<ItemType>* newNode);
   
   // Returns a pointer to the node containing the given value,
   // or nullptr if not found.
   BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr,
                                  const KeyType& target) const;
   
public:
   //------------------------------------------------------------
   // Constructor and Destructor Section.
   //------------------------------------------------------------
   BinarySearchTree();
   virtual ~BinarySearchTree();
   
   //------------------------------------------------------------
   // Public Methods Section.
   //------------------------------------------------------------
   bool add(const ItemType& newEntry);
   ItemType getEntry(const KeyType& aKey) const throw(NotFoundException);
   bool contains(const KeyType& aKey) const;
   
}; // end BinarySearchTree

//#include "BinarySearchTree.cpp"

#endif 


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
123
124
125
126
127
128
129
130
131
132
133
134
135
 
#include <iostream>

#include "BinarySearchTree.h" 



// PRIVATE HELPER METHODS - IMPLEMENT THESE
template<typename ItemType, typename KeyType>
void BinarySearchTree<ItemType, KeyType>::destroyTree(BinaryNode<ItemType>* subTreePtr)
{
	if(rootPtr!=nullptr)
	{
		destroyTree(subTreePtr->getLeftChildPtr());
		destroyTree(subTreePtr->getRightChildPtr());
		if(subTreePtr->isLeaf())
			delete subTreePtr;
	}
	
}

template<typename ItemType, typename KeyType>
BinaryNode<ItemType>* BinarySearchTree<ItemType,KeyType>::insertInorder(BinaryNode<ItemType>* subTreePtr,
                                                                BinaryNode<ItemType>* newNodePtr)
{
	

	if(newNodePtr->getItem()<=subTreePtr->getItem())
	{
		if(subTreePtr->getLeftChildPtr()==nullptr)
		{
			subTreePtr->setLeftChildPtr(newNodePtr);
			return(newNodePtr);
		}
		else
			return(insertInorder(subTreePtr->getLeftChildPtr(), newNodePtr));
	}
	else
	{
		if(subTreePtr->getRightChildPtr()==nullptr)
		{
			subTreePtr->setRightChildPtr(newNodePtr);
			return(newNodePtr);
		}
		else
			return(insertInorder(subTreePtr->getLeftChildPtr(), newNodePtr));
	}
}



template<typename ItemType, typename KeyType>
BinaryNode<ItemType>* BinarySearchTree<ItemType, KeyType>::findNode(
				BinaryNode<ItemType>* subTreePtr, const KeyType& target) const
{
	if(rootPtr==nullptr)
	{
		return(nullptr);
	}
	else if(target==subTreePtr->getItem().getWord())
	{
		return subTreePtr;
	}
	else if(target<=subTreePtr->getItem().getWord())
	{
		if(subTreePtr->getLeftChildPtr()==nullptr)
		{
			return(nullptr);
		}
		else
			return(findNode(subTreePtr->getLeftChildPtr(), target));
	}
	else
		return(nullptr);
}


//////////////////////////////////////////////////////////////
//      PUBLIC METHODS BEGIN HERE
//////////////////////////////////////////////////////////////

template<typename ItemType, typename KeyType>
BinarySearchTree<ItemType, KeyType>::BinarySearchTree() : rootPtr(nullptr)
{
}

template<typename ItemType, typename KeyType>
BinarySearchTree<ItemType, KeyType>::~BinarySearchTree()
{
   this->destroyTree(rootPtr); // Call inherited method
}  // end destructor


//////////////////////////////////////////////////////////////
//      Public BinaryTreeInterface Methods Section - IMPLEMENT THESE
//////////////////////////////////////////////////////////////

template<typename ItemType, typename KeyType>
bool BinarySearchTree<ItemType, KeyType>::add(const ItemType& newData)
{
	if(rootPtr==nullptr)
	{
		rootPtr=new BinaryNode<ItemType>(newData);
		return true;
	}
	else
	{
		BinaryNode<ItemType>* newNode=new BinaryNode<ItemType>(newData);
		insertInorder(rootPtr, newNode);
		return(true);
	}

	
	return false;
}
template<typename ItemType, typename KeyType>
ItemType BinarySearchTree<ItemType, KeyType>::getEntry(const KeyType& aKey) const throw(NotFoundException)
{
	try
	{
		ItemType i=findNode(rootPtr,aKey)->getItem();
		return(i);
	}
	catch(exception& e)
	{
		cout << "Word not found" << endl;
	}
}
template<typename ItemType, typename KeyType>
bool BinarySearchTree<ItemType, KeyType>::contains(const KeyType& aKey) const
{
	if(findNode(rootPtr, aKey)==nullptr)
		return false;
	else
		return true;
}
Last edited on
MikeyBoy (5631)
The compiler needs to know the entire definition of a template class, including the definition of all the methods, at the point where an object of the class is instantiated. This means that the entire definition has to be in the header file. You can't just put the method definitions in a source code, and trust that the linker will resolve it.

Put the complete method definitions into the header file.
gpetter21 (3)
Couldn't I #include "BinarySearchTree.cpp" at the bottom of my header file so that the definitions are accessible? Like what is currently commented out at the bottom of my header? the problem is, that gives me different errors
Last edited on
MikeyBoy (5631)
Couldn't I #include "BinarySearchTree.cpp" at the bottom of my header file so that the definitions are accessible?

You could do, but that doesn't really achieve anything that putting the definitions in the header file itself doesn't do, and just arbitrarily and unnecessarily splits the definition of your class across two files.

the problem is, that gives me different errors

If only there was some online resource where you could post your code, give details of your errors, and then a bunch of experienced C++ developers could explain the problems and help you fix them. Someone should invent something like that...
Last edited on
gpetter21 (3)
I finally got it to compile, thank you for pointing me in the right direction
MikeyBoy (5631)
You're welcome - glad it worked!
Topic archived. No new replies allowed.