Linked Lists/Pointers/Structs error, not sure which

[SquishyChs]

Hey guys,

so my problem is actually fairly simple but I'm afraid this post may be rather lengthy as I'm not entirely sure what my problem is and so I will most likely put each class I think may be part of the cause on here (luckily only 5 lol)

OK, so my problem is that I'm trying to implement graphs of nodes, even made them templates which is a new thing for me so that may be the problem, but I'm also still not that fluent with pointers. I have my graph set up I believe and then add two nodes and connect them, and then try to get the distance between the two.

The answer I guess is technically correct as it displays 0 for everything, its trying to work out the distance between two nodes of position (0, 0, 0), though I actually set up some position data for the second one so this isn't the expected answer

This is the main class:

#include <iostream>
#include <cmath>

using namespace std;

#include "Graph.h"

struct pos
{
	float x;
	float y;
	float z;
};

int main(int argc, char** argv)
{
	Graph<Position>* graphy = new Graph<Position>();

	Position p0;
	p0.x = 0;
	p0.y = 0;
	p0.z = 0;

	Position p1;
	p1.x = 10.0f;
	p1.y = 5.0f;
	p1.z = 5.87f;

	graphy->addNode(p0);
	graphy->addNode(p1);
	graphy->connect(graphy->getNode(0), graphy->getNode(1), true);

	Position g0 = (graphy->getNode(0))->getData();
	Position g1 = (graphy->getNode(1))->getData();

	Position diff;
	diff.x = g1.x - g0.x;
	diff.y = g1.y - g0.y;
	diff.z = g1.z - g0.z;

	float distance = sqrt(sqrt(pow(diff.x, 2) + pow(diff.y, 2)) + pow(diff.z, 2));

	cout << "Distance between node 0 and 1 is: " << distance << endl;
	cout << "Difference in x is: " << diff.x << endl;
	cout << "Difference in y is: " << diff.y << endl;
	cout << "Difference in z is: " << diff.z << endl;
	
	delete graphy;
	
	int i;
	cin >> i;

	return 0;
};

This is the graph class:

#ifndef GRAPH_H
#define GRAPH_H

#include "LinkedList.h"
#include "GraphNode.h"

template <class T>
class Graph
{
private:
	int numNodes;
	LinkedList<GraphNode<T>*>* nodes;

public:
	Graph()
	{
		numNodes = 0;
		nodes = new LinkedList<GraphNode<T>*>();
	}

	int getNumNodes()
	{
		return numNodes;
	}

	GraphNode<T>* getNode(int index)
	{
		return nodes->get(index);
	}

	void addNode(GraphNode<T>* node)
	{
		nodes->add(node);
		numNodes = nodes->size;
	}

	void addNode(T data)
	{
		nodes->add(new GraphNode<T>(data));
		numNodes = nodes->size;
	}

	void connect(GraphNode<T>* node1, GraphNode<T>* node2)
	{
		node1->addConnection(node2);
	}

	void connect(GraphNode<T>* node1, GraphNode<T>* node2, bool bidirectional)
	{
		if(bidirectional == true)
		{
			node1->addConnection(node2);
			node2->addConnection(node1);
		}
		else
		{
			node1->addConnection(node2);
		}
	}

	~Graph()
	{
		delete nodes;
	}
};

#endif 

This is the GraphNode class:

#ifndef GRAPHNODE_H
#define GRAPHNODE_H

#include "LinkedList.h"

template <class T>
class GraphNode
{
private:
	T data;
	int ID;
	int numConnections;
	LinkedList<GraphNode<T>*>* connections;

public:
	GraphNode()
	{
		ID = 0;
		numConnections = 0;
		connections = new LinkedList<GraphNode*>();
	}

	GraphNode(int id)
	{
		ID = id;
		numConnections = 0;
		connections = new LinkedList<GraphNode*>();
	}

	GraphNode(T d)
	{
		data = d;
		ID = 0;
		numConnections = 0;
		connections = new LinkedList<GraphNode*>();
	}

	GraphNode(int id, T d)
	{
		data = d;
		ID = id;
		numConnections = 0;
		connections = new LinkedList<GraphNode*>();
	}

	T getData()
	{
		return data;
	}

	int getID()
	{
		return ID;
	}

	int getNumConnections()
	{
		return numConnections;
	}

	GraphNode* getConnection(int index)
	{
		return connections->get(index);
	}

	void setData(T d)
	{
		data = d;
	}

	void setID(int id)
	{
		ID = id;
	}

	void addConnection(GraphNode* newConn)
	{
		connections->add(newConn);
	}

	~GraphNode()
	{
		delete connections;
	}
};

#endif 

LinkedList:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "ListNode.h"

template <class T>
class LinkedList
{
private:
	
	ListNode<T>* head;
	ListNode<T>* tail;

public:
	int size;
	LinkedList<T>()
	{
		head = nullptr;
		tail = nullptr;
		size = 0;
	}

	LinkedList<T>(T value)
	{
		head = new ListNode<T>(value);
		head->previous = nullptr;
		head->next = nullptr;
		tail = head;

		size = 1;
	}

	LinkedList<T>(T values[])
	{
		for(int i = 0; i < values.size(); i++)
		{
			add(values[i]);
		}
	}

	void addFront(T value)
	{
		if(head!= nullptr)
		{
			ListNode<T>* temp = head;

			head = new ListNode<T>(value);
			temp->previous = head;
			head->next = temp;
			head->previous = nullptr;

			size++;
		}
		else
		{
			head = new ListNode<T>(value);
			head->previous = nullptr;
			head->next = nullptr;
			tail = head;

			size = 1;
		}
	}


	void add(T value)
	{
		if(head != nullptr)
		{
			tail->next = new ListNode<T>(value);
			tail->next->previous = tail;
			tail = tail->next;
			
			size++;
		}
		else
		{
			head = new ListNode<T>(value);
			head->previous = nullptr;
			head->next = nullptr;
			tail = head;

			size = 1;
		}
	}

	void add(int index, T value)
	{
		ListNode<T>* selection = head;
		ListNode<T>* temp;

		for(int i = 1; i < index; i++)
		{
			selection = selection->next;
		}

		temp = selection->next;
		selection->next = new ListNode<T>(value);
		selection->next->previous = selection;
		selection->next->next = temp;

		size++;
	}

	T get(int index)
	{
		ListNode<T>* selection = head;

		for(int i = 1; i < index; i++)
		{
			selection = selection->next;
		}

		return selection->data;
	}

	void removeFront()
	{
		ListNode<T>* temp = head;

		head = head->next;
		head->previous = nullptr;
		delete temp;

		size--;
	}

	void removeBack()
	{
		tail = tail->previous;
		tail->next = nullptr;
		delete tail->next;

		size--;
	}

	void remove(int index)
	{
		ListNode<T>* selection = head;
		ListNode<T>* temp;

		for(int i = 1; i < index; i++)
		{
			selection = selection->next;
		}
		if(selection != head || selection != tail)
		{
			temp = selection->previous;
			selection->previous->next = selection->next;
			delete selection;

			size--;
		}
		else if(selection == head)
		{
			removeFront();
		}
		else if(selection == tail)
		{
			removeBack();
		}
	}

	~LinkedList()
	{
		if(head != nullptr)
		{
			delete head;
		}
	}
};

#endif 

and finally, ListNode:

#ifndef LISTNODE_H
#define LISTNODE_H

template <class T>
class ListNode
{
public:
	T data;

	ListNode* previous;
	ListNode* next;

	ListNode<T>(T value)
	{
		data = value;
		next = nullptr;
		previous = nullptr;
	}

	~ListNode(void)
	{
		if(next != nullptr)
		{
			delete next;
		}
	}
};

#endif 

Again, sorry about the huge wall of code haha, but Im kinda stumped with this and assuming you read this far, thanks for your time :)

[SquishyChs]

Just trying to keep this a visible topic, dont want to keep bumping it so I wont do it too much, but I really do need help

[LB]

SquishyChs wrote:

This is the main class:

No, it's not, it's the .cpp file with the main function in it. Not even Java has such a thing as a "main class" ;)

SquishyChs wrote:

Graph<Position>* graphy = new Graph<Position>();

Why is this a pointer? You don't need to use pointers or dynamic allocation/deallocation here.

SquishyChs wrote:

float distance = sqrt(sqrt(pow(diff.x, 2) + pow(diff.y, 2)) + pow(diff.z, 2));

I'd like to know where you learned the distance formula, because this doesn't look like it to me. See http://en.wikipedia.org/wiki/Distance_formula#Geometry - the third one is for 3D distance.

SquishyChs wrote:

int numNodes;

This is wrong; LinkedList should keep track of the number of elements it has, not Graph. Graph should just ask LinkedList how many elements it has.

SquishyChs wrote:

LinkedList<GraphNode<T>*>* nodes;

Again, you don't need pointers here. A LinkedList<GraphNode<T> > would be better. Your functions should probably return and take references too.

SquishyChs wrote:

LinkedList<GraphNode<T>*>* connections;

Looking at this, I think you have your design wrong. This is a nightmare waiting to happen, because it means you have too many places to manage pinters. But you've already got it set up like this, I think it'd be a waste of time to change it. Just don't do this kind of thing in the future ;)

There are a multitude of problems with this code but I think your main problem is that insane distance formula. You've done very well with all this, though, and I think you've got the right general ideas. Just don't use pointers when you don't need them. LinkedList is the only class that needs to use pointers to its data, for obvious reasons, but the other places could do without pointers since they don't really utilize the actual features of pointers.

[SquishyChs]

OK main function :P, I have a habit of calling things names that arent standard, to me it lets me remember them easier and keep track of them :)

yeah Im pretty poor with my pointers and stuff as I said before but Ill get right to all this and report back soon heh

the distance function I used was for 3D space, pythagoras says that length squared + width squared is the hypotenuse squared, and so for 3D space I use the hypotenuse of the x and y as the width of the new formula, square it and add the distance in z squared and that is the distance squared :), may have screwed up the formula still but with no answer being reported back I dont know yet heh. There may be a more efficient formula but this is one I always remember because I remember figuring out in lecture the formula for a 2D distance could be used twice so to speak to get 3D

[SquishyChs]

OK so I changed a few things and it all seems like hell so Im thinking Im gonna just rewrite the entire thing -.-, Im never sure where I need pointers and where I dont

are my templates correct as they are though? because I struggled with that so I would like to know something I did was useful haha, this is the first programming Ive done for a while now so I forgot a lot :(

EDIT
didnt delete and start again, just went through and fixed all the errors and its back to square one, not bad but not what I was hoping for still :P

[SquishyChs]

OK got this all fixed, it was a rather blind mistake on my part, caused by staring too long at the same thing and getting ideas in my head about what it was

instead of:

T get(int index)
	{
		ListNode<T>* selection = head;

		for(int i = 1; i < index; i++)
		{
			selection = selection->next;
		}

		return selection->data;
	}

I did:

T get(int index)
	{
		ListNode<T>* selection = head;

		for(int i = 1; i <= index; i++)
		{
			selection = selection->next;
		}

		return selection->data;
	}

but all is sorted, so thanks for the help L B :)

oh and my formula was wrong :), just need to add all the values squared then sqrt it, dur