• Advertisement
Sign in to follow this  

Data Structures Help!

This topic is 737 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

UPDATE:

 

I finished the project last week that I needed help on (thanks for the help!) and I was wondering if someone wouldn't mind taking the time to look over my code and give me any tips/suggestions in my code. All is working with no bugs, but I am sure I didn't do something a more efficient way and I want to improve my code! Thanks in advance to any tips!

 

Main.cpp

//////////////////////////////////
//                              //
//   Data Structures - Queues   //
//   ------------------------   //
//                              //
//   Creating a queue system    //
//   using linked lists and     //
//   C++ (FIFO)                 //
//                              //
//////////////////////////////////

#include "LibIncludes.h"

int main()
{
	Queue<int> myQueue;

	myQueue.displayQueue();

	myQueue.pop();
	myQueue.peek();
	myQueue.pop_all();

	myQueue.push(2);
	myQueue.push(9);
	myQueue.push(3);

	myQueue.peek();

	myQueue.push(1);
	myQueue.push(7);
	myQueue.push(5);

	myQueue.displayQueue();

	myQueue.pop();
	myQueue.pop();

	myQueue.displayQueue();

	myQueue.pop_all();

	myQueue.displayQueue();

	system("PAUSE");

	return 0;
}

Queue.h

#pragma once

template <class T>
class Queue
{
	public:
		Queue();
		Queue(T newItem);
		void push(T newItem);
		void pop();
		void pop_all();
		void peek();
		bool isEmpty();
		void displayQueue();
	private:
		struct Node
		{
			T data;
			Node * nextNode;
		};

		Node LinkedList;
		Node * headNode; // front of the queue
		Node * tailNode; // End of the Queue
		int size;
};

#include "Queue.inl"

Queue.inl

#include "LibIncludes.h"

template <typename T>
Queue<T>::Queue()
{
	headNode = nullptr;
	tailNode = nullptr;

	size = 0;

	std::cout << "*** A new empty Queue was created ***\n\n";
}

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

template <typename T>
Queue<T>::Queue(T newItem)
{
	Node * temp = (struct Node *)malloc(sizeof(struct Node *));

	temp->data = newItem;
	temp->nextNode = nullptr;

	headNode = temp;
	tailNode = temp;

	size = 1;

	std::cout << "*** A new Queue with starting item " << headNode->data << " was created ***\n\n";
}

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

template <typename T>
bool Queue<T>::isEmpty()
{
	if (headNode == NULL)
		return true;
	else
		return false;
}

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

template <typename T>
void Queue<T>::peek()
{
	if (isEmpty())
		std::cout << "peek() was used, but there is nothing in the Queue.\n\n";
	else
		std::cout << "peek() was used and resulted in: " << headNode->data << "\n\n";
}

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

template <typename T>
void Queue<T>::pop_all()
{
	if (isEmpty())
		std::cout << "pop_all() was used, but the Queue is already empty.\n\n";
	else
	{
		std::cout << "pop_all() was used and destroyed the Queue.\n\n";

		headNode = nullptr;
		tailNode = nullptr;

		size = 0;
	}
}

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

template <typename T>
void Queue<T>::push(T newItem)
{
	Node * temp = (struct Node *)malloc(sizeof(struct Node *));

	temp->data = newItem;
	temp->nextNode = nullptr;

	if (isEmpty())
	{
		headNode = temp;
		tailNode = temp;
	}
	else
	{
		tailNode->nextNode = temp;
		tailNode = temp;
	}

	size++;
	std::cout << "push() was called and " << newItem << " was added to the Queue.\n\n";
}

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

template <typename T>
void Queue<T>::pop()
{
	if (isEmpty())
		std::cout << "pop() was used, but the Queue is empty.\n\n";
	else
	{
		Node * temp = headNode->nextNode;

		std::cout << "pop() was used and " << headNode->data << " was removed from the Queue.\n\n";

		headNode->nextNode = nullptr;
		headNode = temp;

		size--;
	}
}

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

template <typename T>
void Queue<T>::displayQueue()
{
	std::cout << "\ndisplayQueue() was called:\n";
	std::cout << "------------------------- queue contents\n\n";

	std::cout << "*** QUEUE SIZE: " << size << std::endl;

	if (isEmpty())
	{
		std::cout << "*** Queue is empty\n";
	}
	else
	{
		Node * temp = headNode;

		while (temp != NULL)
		{
			std::cout << "- " << temp->data << "\n";

			temp = temp->nextNode;
		}
	}

	std::cout << "\n------------------------- end of queue\n\n";
}

LibIncludes.h

#pragma once

#include <iostream>
#include <string>

#include "Queue.h"

Original Post:

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

 

Hello,

 

So I am trying to work on data structures and I am trying to implement the stack using linked lists. I only have a little bit done so far because I ran into an error and have no idea why it is happening. I've commented out the line in main that creates the LinkedStack object and it builds with no errors, but when I uncomment it I get 2 errors.

 

First error:

Severity    Code    Description    Project    File    Line    Suppression State
Error    LNK2019    unresolved external symbol "public: __thiscall LinkedStack<int>::LinkedStack<int>(void)" (??0?$LinkedStack@H@@QAE@XZ) referenced in function _main    DataStructures_Stacks2    C:\Users\Brandon\documents\visual studio 2015\Projects\DataStructures_Stacks2\DataStructures_Stacks2\Main.obj    1    
 

Second error:

Severity    Code    Description    Project    File    Line    Suppression State
Error    LNK1120    1 unresolved externals    DataStructures_Stacks2    C:\Users\Brandon\documents\visual studio 2015\Projects\DataStructures_Stacks2\Debug\DataStructures_Stacks2.exe    1    
 

If anyone can please help me fix this issue I would be greatly appreciative!

 

Main.cpp

/*************************************
*				     *
*   Data Structures - Linked Stack   *
*   ------------------------------   *
*				     *
*   Implementing the stack using     *
*   linked lists and C++             *
*                                    *
*   4/6/2016		             *
*				     *
*************************************/

#include "LibIncludes.h"

int main()
{
	LinkedStack<int> myStack;

	std::cout << "----------------------------\n";
	system("PAUSE");

	return 0;
}

LinkedStack.h

#pragma once

template <class T>
class LinkedStack
{
	public:
		LinkedStack();
		LinkedStack(T newItem);
		void push(T newItem);
		void pop();
		void peek();
		bool isEmpty();
	private:
		struct node
		{
			T data;
			node * nextNode;
		};

		node linkedList;
		node * headNode;
};

LinkedList.cpp

#include "LibIncludes.h"

template <class T>
LinkedStack<T>::LinkedStack()
{
	std::cout << "An empty Linked Stack was created.\n";

	linkedList.data = null;
	linkedList.nextNode = nullptr;
	headNode = linkedList;
}
Edited by NUCLEAR RABBIT

Share this post


Link to post
Share on other sites
Advertisement
You can't split up templates like that because of the way they compile.
 
You can either define the functions inline with the declaration or use a .inl file instead of a .cpp file and then include the .inl at the end of the header file.
 
Example of method A:
template <class T>
class Foo {
public:
  Foo(T bar) { //define the function inline
    baz = bar;
  }
private:
  T baz;
};
Example of method B:
//Foo.h

template <class T>
class Foo {
public:
  Foo(T bar);
private:
  T baz;
};

#include "Foo.inl" //include this at the end, not the beginning
//Foo.inl


template<typename T>
Foo<T>::Foo(T bar) {
  baz = bar;
}

ninja'd Edited by Khatharr

Share this post


Link to post
Share on other sites

See: C++ FAQ Lite: Why can’t I separate the definition of my templates class from its declaration and put it inside a .cpp file?

I like to separate my template classes into hpp, impl, and cpp. For template classes that have a handful of known types (such as a vector4_t<T> for T in (float, int)), then the cpp supplies all the definitions using hpp and impl for those types, and everything else won’t need to know about the impl. Otherwise, I have the hpp include the impl at the end of the file and forego having a cpp file.

 

Thanks! I was not aware of having to do this with templates!

 

 

 

You can't split up templates like that because of the way they compile.
 
You can either define the functions inline with the declaration or use a .inl file instead of a .cpp file and then include the .inl at the end of the header file.
 
Example of method A:

template <class T>
class Foo {
public:
  Foo(T bar) { //define the function inline
    baz = bar;
  }
private:
  T baz;
};
Example of method B:
//Foo.h

template <class T>
class Foo {
public:
  Foo(T bar);
private:
  T baz;
};

#include "Foo.inl" //include this at the end, not the beginning
//Foo.inl


template<typename T>
Foo<T>::Foo(T bar) {
  baz = bar;
}

ninja'd

 

 

Thanks a lot! I used the .inl file method and it worked great!

Share this post


Link to post
Share on other sites

You must have changed something else, but isn't this a problem too:

  linkedList.data = null;

You're assign null to an unknown data type.  It will probably work for all types, but it's not good programming.

 

and this

  headNode = linkedList;

headNode is a pointer to a node, while linkedList is a node.  That shouldn't compile. I suppose this would work though:

  headNode = &linkedList;
Edited by BeerNutts

Share this post


Link to post
Share on other sites

 

You must have changed something else, but isn't this a problem too:

  linkedList.data = null;

You're assign null to an unknown data type.  It will probably work for all types, but it's not good programming.

 

and this

  headNode = linkedList;

headNode is a pointer to a node, while linkedList is a node.  That shouldn't compile. I suppose this would work though:

  headNode = &linkedList;

 

Yeah, I had to change those as well. The & always slips my mind :rolleyes: haha

Edited by NUCLEAR RABBIT

Share this post


Link to post
Share on other sites

A few things:

#0, you really should've started a new thread for this.

 

#1, there's a major leak since you call malloc() every time push is called, you need to have a cooresponding call to free() when you pop or pop_all.  My suggesiton is to make pop() such that it calls free() on the node being deleted, and then, in pop_all, just call pop() until isEmpty() is true.

 

#2, you shouldn't have Queue as an include file (.inl).  Just make it a separate .cpp file and include it when compiling.

 

#3, it's bad practice to have a single include file (LibIncludes.h) which includes all the include files you need.  Just include the files the current file needs to operate properly on it's own.

 

#4, the Queue class should only be responsible for handling the data for insertion and retrieval, it should not be printing as well; rather, retreive the data from the Queue class, and print the results in the main class (or make a separate class call QueuePrint if you so desire).  Right now your Queue class is useless as an actual Queue.  it simply prints the data it has, a user can't use it at all to add and retreive items for use.

 

Just a few thoughts I had.

 

good luck!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement