I'm working on a university coding assignment. I've created a header file for a binaryTree class, and extended the class with a bSearchTree class. I also have an object class called computer that's required to complete the assignment. I've split each class into two files, a header file with the class definition including function prototypes, and an implementation file with the function definitions. I'm able to compile each implementation file into an object file, and I have #include statements for the header files where they need to be used.
The problem I'm having is when I try to link all of the object files, I'm getting "undefined reference" errors from the g++ compiler.
I'm using the g++ compiler on an Ubuntu 20.04 system. I've looked at some other questions and answers and double checked my text book and it seems I'm following along with what I thought was the correct way to do this. I'm not sure why the linker is giving me this error and would be grateful for any direction or guidance.
Here's the error messages and the code files, including a much briefer test file than what I'm using in my actual assignment so as to simplify things:
Error messages:
eric@eric-HP-EliteDesk-800-G1-SFF:~/repos/CS325-DataStructures/wk5_binaryTrees$ g++ -o scratch.exe scratch.cpp binaryTreeADT.o binarySearchTree.o computer.o
/usr/bin/ld: /tmp/cc72Uva7.o: in function `main':
scratch.cpp:(.text+0x301): undefined reference to `bSearchTree<computer>::insert(computer const&)'
/usr/bin/ld: scratch.cpp:(.text+0x317): undefined reference to `bSearchTree<computer>::insert(computer const&)'
/usr/bin/ld: /tmp/cc72Uva7.o: in function `bSearchTree<computer>::bSearchTree()':
scratch.cpp:(.text._ZN11bSearchTreeI8computerEC2Ev[_ZN11bSearchTreeI8computerEC5Ev]+0x18): undefined reference to `binaryTree<computer>::binaryTree()'
/usr/bin/ld: /tmp/cc72Uva7.o:(.data.rel.ro._ZTV11bSearchTreeI8computerE[_ZTV11bSearchTreeI8computerE]+0x10): undefined reference to `bSearchTree<computer>::search(computer const&) const'
/usr/bin/ld: /tmp/cc72Uva7.o:(.data.rel.ro._ZTV11bSearchTreeI8computerE[_ZTV11bSearchTreeI8computerE]+0x18): undefined reference to `bSearchTree<computer>::insert(computer const&)'
/usr/bin/ld: /tmp/cc72Uva7.o:(.data.rel.ro._ZTV11bSearchTreeI8computerE[_ZTV11bSearchTreeI8computerE]+0x20): undefined reference to `bSearchTree<computer>::deleteNode(computer const&)'
/usr/bin/ld: /tmp/cc72Uva7.o: in function `bSearchTree<computer>::~bSearchTree()':
scratch.cpp:(.text._ZN11bSearchTreeI8computerED2Ev[_ZN11bSearchTreeI8computerED5Ev]+0x26): undefined reference to `binaryTree<computer>::~binaryTree()'
collect2: error: ld returned 1 exit status
Code Files:
binaryTreeADT.h
/*************************************
* Author: Eric Johnson
* Date: 12/16/2020
*
* Grantham University
* CS325 Data Structures
*
* Week 5 Assignment
* Binary Search Trees
*
* This file is a header file that defines a binary
* tree abstract class.
*************************************/
#ifndef binaryTreeADT_h
#define binaryTreeADT_h
template <class T> // Define the node type
struct node{
T data;
node<T> *lLink;
node<T> *rLink;
};
template <class T>
class binaryTree{
public:
const binaryTree<T> &operator=(const binaryTree<T>&);
//Overload the assignment operator.
bool isEmpty() const;
//Function to determine whether the binary tree is empty.
//Postcondition: Returns true if the binary tree is empty;
// otherwise, returns false.
void inorderTraversal(void (*visit) (T &item)) const;
//Function to do an inorder traversal of the binary tree.
//Postcondition: Nodes are visited in inorder sequence.
void preorderTraversal(void (*visit) (T &item)) const;
//Function to do a preorder traversal of the binary tree.
//Postcondition: Nodes are printed in preorder sequence.
void postorderTraversal(void (*visit) (T &item)) const;
//Function to do a postorder traversal of the binary tree.
//Postcondition: Nodes are printed in postorder sequence.
int treeHeight() const;
//Function to determine the height of a binary tree.
//Postcondition: Returns the height of the binary tree.
int treeNodeCount() const;
//Function to determine the number of nodes in a binary tree.
//Postcondition: Returns the number of nodes in the binary tree.
int treeLeavesCount() const;
//Function to determine the number of leaves in a binary tree.
//Postcondition: Returns the number of leaves in the binary tree.
void destroyTree();
//Function to destroy the binary tree.
//Postcondition: Memory space occupied by each node is deallocated.
// root = nullptr;
virtual bool search(const T &searchItem) const = 0;
//Function to determine if searchItem is in the binary tree.
//Postcondition: Returns true if searchItem is found in the
// binary tree; otherwise, returns false.
virtual void insert(const T & insertItem) = 0;
//Function to insert insertItem in the binary tree.
//Postcondition: If there is no node in the binary tree that
// has the same info as insertItem, a node with
// the info insertItem is created and inserted
// in the binary search tree.
virtual void deleteNode(const T & deleteItem) = 0;
//Function to delete deleteItem from the binary tree.
//Postcondition: If a node with the same info as deleteItem
// is found, it is deleted from the binary tree.
// If the binary tree is empty or deleteItem is not
// in the binary tree, an appropriate message is printed.
binaryTree(const binaryTree<T> &otherTree);
//Copy constructor
binaryTree();
//Default constructor
~binaryTree();
//Destructor
protected:
node<T> *root;
private:
void copyTree(node<T> *&copiedTreeRoot, node<T> *otherTreeRoot);
//Makes a copy of the binary tree to which otherTreeRoot points.
//Postcondition: The pointer copiedTreeRoot points to the root
// of the copied binary tree.
void destroy(node<T> *&p);
//Function to destroy the binary tree to which p points.
//Postcondition: Memory space occupied by each node, in the
// binary tree to which p points, is deallocated.
// p = nullptr;
void inorder(node<T> *p, void (*visit) (T &item)) const;
//Function to do an inorder traversal of the binary tree to which p points.
//Postcondition: Nodes of the binary tree, to which p points, are printed
// in inorder sequence.
void preorder(node<T> *p, void (*visit) (T &item)) const;
//Function to do a preorder traversal of the binary tree to which p points.
//Postcondition: Nodes of the binary tree, to which p points, are printed
// in preorder sequence.
void postorder(node<T> *p, void (*visit) (T &item)) const;
//Function to do a postorder traversal of the binary tree to which p points.
//Postcondition: Nodes of the binary tree, to which p points, are printed in
// postorder sequence.
int height(node<T> *p) const;
//Function to determine the height of the binary tree to which p points.
//Postcondition: Height of the binary tree to which p points is returned.
int max(int x, int y) const;
//Function to determine the larger of x and y.
//Postcondition: Returns the larger of x and y.
int nodeCount(node<T> *p) const;
//Function to determine the number of nodes in the binary tree to which p points.
//Postcondition: The number of nodes in the binary tree to which p points is returned.
int leavesCount(node<T> *p) const;
//Function to determine the number of leaves in the binary tree to which p points
//Postcondition: The number of leaves in the binary tree to which p points is returned.
};
#endif
binaryTreeADT.cpp
/*************************************
* Author: Eric Johnson
* Date: 12/16/2020
*
* Grantham University
* CS325 Data Structures
*
* Week 5 Assignment
* Binary Search Trees
*
* This file is the implementation file for the
* binaryTreeADT abstract class.
*************************************/
#include "binaryTreeADT.h"
#include <iostream>
template <class T>
bool binaryTree<T>::isEmpty() const {
return(root == nullptr);
}
template <class T>
binaryTree<T>::binaryTree(){
root = nullptr;
}
template <class T>
void binaryTree<T>::inorderTraversal(void (*visit) (T &item)) const {
inorder(root, *visit);
}
template <class T>
void binaryTree<T>::preorderTraversal(void (*visit) (T &item)) const {
preorder(root, *visit);
}
template <class T>
void binaryTree<T>::postorderTraversal(void (*visit) (T &item)) const {
postorder(root, *visit);
}
template <class T>
int binaryTree<T>::treeHeight() const {
return height(root);
}
template <class T>
void binaryTree<T>::inorder(node<T> *p, void (*visit) (T &item)) const {
if(p != nullptr){
inorder(p->lLink);
(*visit)(p->data);
inorder(p->rLink);
}
}
template <class T>
void binaryTree<T>::preorder(node<T> *p, void (*visit) (T &item)) const {
if(p != nullptr){
(*visit)(p->data);
preorder(p->lLink);
preorder(p->rLink);
}
}
template <class T>
void binaryTree<T>::postorder(node<T> *p, void (*visit) (T &item)) const {
if(p != nullptr){
postorder(p->lLink);
postorder(p->rLink);
(*visit)(p->data);
}
}
template <class T>
int binaryTree<T>::height(node<T> *p) const {
if(p == nullptr)
return 0;
else
{
return 1 + max(height(p->lLink), height(p->rLink));
}
}
template <class T>
int binaryTree<T>::max(int x, int y) const{
if(x >= y)
return x;
else
return y;
}
template <class T>
void binaryTree<T>::copyTree(node<T> *&copiedTreeRoot, node<T> *otherTreeRoot){
if(otherTreeRoot == nullptr)
copiedTreeRoot = nullptr;
else
{
copiedTreeRoot = new node<T>;
copiedTreeRoot->data = otherTreeRoot->data;
copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink);
copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink);
}
}
template <class T>
void binaryTree<T>::destroy(node<T> *&p){
if(p != nullptr){
destroy(p->lLink);
destroy(p->rLink);
delete p;
p = nullptr;
}
}
template <class T>
void binaryTree<T>::destroyTree(){
destroy(root);
}
template <class T>
binaryTree<T>::binaryTree(const binaryTree<T> &otherTree){
if(otherTree.root == nullptr) //otherTree is empty
root = nullptr;
else
{
copyTree(root, otherTree.root);
}
}
template <class T>
binaryTree<T>::~binaryTree(){
destroy(root);
}
template <class T>
const binaryTree<T> &binaryTree<T>::operator=(const binaryTree<T> &otherTree){
if(this != &otherTree){ //avoid self copy
if(root != nullptr) //if the binary tree isn't empty, destroy the binary tree
destroy(root);
if(otherTree.root == nullptr) //otherTree is empty
root = nullptr;
else
{
copyTree(root, otherTree.root);
}
return *this;
}
}
template <class T>
int binaryTree<T>::treeNodeCount() const {
return nodeCount(root);
}
template <class T>
int binaryTree<T>::nodeCount(node<T> *p) const{
if(p == nullptr)
return 0;
else
{
return 1 + count(p->lLink) + count(p->rLink);
}
}
template <class T>
int binaryTree<T>::treeLeavesCount() const {
return leavesCount(root);
}
template <class T>
int binaryTree<T>::leavesCount(node<T> *p) const{
if(p == nullptr)
return 0;
else if(p->lLink == nullptr && p->rLink == nullptr)
return 1;
else{
return leavesCount(p->lLink) + leavesCount(p->rLink);
}
}
binarySearchTree.h
/*************************************
* Author: Eric Johnson
* Date: 12/16/2020
*
* Grantham University
* CS325 Data Structures
*
* Week 5 Assignment
* Binary Search Trees
*
* This file is a header file that defines a binary
* search tree abstract class. It extends the binary
* tree class.
*************************************/
#ifndef bsearchTree_h
#define bsearchTree_h
#include "binaryTreeADT.h"
template <class T>
class bSearchTree: public binaryTree<T>{
public:
bool search(const T &searchItem) const;
//Function to determine if searchItem is in the binary
//search tree.
//Postcondition: Returns true if searchItem is found in the
// binary search tree; otherwise returns false.
void insert(const T &insertItem);
//Function to insert insertItem in the binary search tree.
//Postcondition: If there is no node in the binary search
// tree that has the same info as insertItem,
// a node with the info insertItem is created
// and inserted in the binary search tree.
void deleteNode(const T &deleteItem);
//Function to delete deleteItem from the binary search tree
//Postcondition: If a node with the same info as deleteItem
// is found, it is deleted from the binary search
// tree. If the binary tree is empty of deleteItem
// is not in the binary tree, an appropriate message
// is printed.
private:
void deleteFromTree(node<T> *&p);
//Function to delete the node to which p points is deleted from
//the binary search tree.
//Postcondition: The node to which p points is deleted from the
//binary search tree.
};
#endif
binarySearchTree.cpp
/*************************************
* Author: Eric Johnson
* Date: 12/16/2020
*
* Grantham University
* CS325 Data Structures
*
* Week 5 Assignment
* Binary Search Trees
*
* This file is the implementation file for a binary
* search tree class. It extends the binaryTreeADT
* class.
*************************************/
#include "binaryTreeADT.h"
#include "binarySearchTree.h"
#include <iostream>
template <class T>
bool bSearchTree<T>::search(const T &searchItem) const{
node<T> *current;
bool found = false;
if(this->root == nullptr)
std::cout << "Cannot search an empty tree." << std::endl;
else{
current = this->root;
while(current != nullptr && !found){
if(current->data == searchItem)
found = true;
else if(current->data > searchItem)
current = current->lLink;
else{
current = current->rLink;
}
}
}
return found;
}
template <class T>
void bSearchTree<T>::insert(const T &insertItem){
node<T> *current; //pointer to traverse the tree
node<T> *trailCurrent = nullptr; //pointer behind current
node<T> *newNode; //pointer to create the node
newNode = new node<T>;
newNode->data = insertItem;
newNode->lLink = nullptr;
newNode->rLink = nullptr;
if(this->root == nullptr)
this->root = newNode;
else{
current = this->root;
while(current != nullptr){
trailCurrent = current;
if(current->data == insertItem){
std::cout << "The item to be inserted is already ";
std::cout << "in the tree -- duplicates are not "
<< "allowed." << std::endl;
return;
}
else if(current->data > insertItem)
current = current->lLink;
else{
current = current->rLink;
}
}
if (trailCurrent->data > insertItem)
trailCurrent->lLink = newNode;
else{
trailCurrent->rLink = newNode;
}
}
}
template <class T>
void bSearchTree<T>::deleteFromTree(node<T> *&p){
node<T> *current; //pointer to traverse the tree
node<T> *trailCurrent; //pointer behind current
node<T> *temp; //pointer to delete the node
if(p == nullptr)
std::cout << "Error: The node to be deleted does not exist."
<< std::endl;
else if(p->lLink == nullptr && p->rLink == nullptr){
temp = p;
p = nullptr;
delete temp;
}
else if(p->lLink == nullptr){
temp = p;
p = temp->rLink;
delete temp;
}
else if(p->rLink == nullptr){
temp = p;
p = temp->lLink;
delete temp;
}
else{
current = p->lLink;
trailCurrent = nullptr;
while(current->rLink != nullptr){
trailCurrent = current;
current = current->rLink;
}
p->data = current->data;
if(trailCurrent == nullptr)
p->lLink = current->lLink;
else
trailCurrent->rLink = current->lLink;
delete current;
}
}
template <class T>
void bSearchTree<T>::deleteNode(const T &deleteItem){
node<T> *current; //pointer to traverse the tree
node<T> *trailCurrent; //pointer behind current
bool found = false;
if(this->root == nullptr)
std::cout << "Cannot delete from an empty tree." << std::endl;
else{
current = this->root;
trailCurrent = this->root;
while(current != nullptr && !found){
if(current->data == deleteItem)
found = true;
else{
trailCurrent = current;
if(current->data > deleteItem)
current = current->lLink;
else{
current = current->rLink;
}
}
}
if (current == nullptr)
std::cout << "The item to be deleted is not in the tree." << std::endl;
else if(found){
if(current == this->root)
deleteFromTree(this->root);
else if(trailCurrent->data > deleteItem){
deleteFromTree(trailCurrent->lLink);
}
else{
deleteFromTree(trailCurrent->rLink);
}
}
else{
std::cout << "The item to be deleted is not in the tree." << std::endl;
}
}
}
computer.h
/*************************************
* Author: Eric Johnson
* Date: 12/23/2020
*
* Grantham University
* CS325 Data Structures
*
* Week 5 Assignment
* Binary Search Trees
*
* This file is a header file that defines a class for
* computer objects.
*************************************/
#ifndef computer_h
#define computer_h
#include <string>
class computer {
public:
void setStockCode(int stockCode);
//Sets the stockCode of the computer
int getStockCode() const;
//Returns the stockCode of the computer
void setName(std::string name);
//Sets the name of the computer
std::string getName() const;
//Returns the name of the computer
void setOperatingSystem(std::string operatingSystem);
//Sets the operatingSystem of the computer
std::string getOperatingSystem() const;
//Returns the operatingSystem of the computer
void setHardDrive(std::string hardDrive);
//Sets the hardDrive of the computer
std::string getHardDrive() const;
//Returns the hardDrive of the computer
void setRam(std::string ram);
//Sets the ram of the computer
std::string getRam() const;
//Returns the ram of the computer
void setPrice(int price);
//Sets the price of the computer
int getPrice() const;
//Returns the price of the computer
computer();
//Default constructor
computer(int stockCode, std::string name, std::string operatingSystem,
std::string hardDrive, std::string ram, int price);
//Constructor with parameters
private:
int stockCode;
std::string name;
std::string operatingSystem;
std::string hardDrive;
std::string ram;
int price; //Price is stored as an integer of cents.
};
#endif
computer.cpp
/*************************************
* Author: Eric Johnson
* Date: 12/23/2020
*
* Grantham University
* CS325 Data Structures
*
* Week 5 Assignment
* Binary Search Trees
*
* This file is the implementation file for the
* computer class
*************************************/
#include "computer.h"
#include <string>
void computer::setStockCode(int stockCode){
this->stockCode = stockCode;
}
int computer::getStockCode() const{
return this->stockCode;
}
void computer::setName(std::string name) {
this->name = name;
}
std::string computer::getName() const{
return this->name;
}
void computer::setOperatingSystem(std::string operatingSystem){
this->operatingSystem = operatingSystem;
}
std::string computer::getOperatingSystem() const {
return this->operatingSystem;
}
void computer::setHardDrive(std::string hardDrive) {
this->hardDrive = hardDrive;
}
std::string computer::getHardDrive() const {
return this->hardDrive;
}
void computer::setRam(std::string ram) {
this->ram = ram;
}
std::string computer::getRam() const {
return this->ram;
}
void computer::setPrice(int price) {
this->price = price;
}
int computer::getPrice() const {
return this->price;
}
computer::computer(){
this->stockCode = 0;
this->name = "";
this->operatingSystem = "";
this->hardDrive = "";
this->ram = "";
this->price = 0;
}
computer::computer(int stockCode, std::string name, std::string operatingSystem,
std::string hardDrive, std::string ram, int price){
this->stockCode = stockCode;
this->name = name;
this->operatingSystem = operatingSystem;
this->hardDrive = hardDrive;
this->ram = ram;
this->price = price;
}
scratch.cpp
#include "binarySearchTree.h"
#include "computer.h"
#include <iostream>
using namespace std;
bSearchTree<computer> computers;
int main(){
computer comp1(1, "name1", "os1", "hd1", "ram1", 101);
computer comp2(2, "name2", "os2", "hd2", "ram2", 102);
computers.insert(comp1);
computers.insert(comp2);
cout << "comp1 name: " << comp1.getName();
return 0;
}
