Jump to content

  • Log In with Google      Sign In   
  • Create Account

NUCLEAR RABBIT

Member Since 12 Apr 2006
Offline Last Active May 16 2016 04:05 PM

Posts I've Made

In Topic: Bubble Sort Algorithm Review

16 May 2016 - 03:55 PM

Your for loop seems a bit rubbish :)

Why use iterators as your for loop condition, and also employ a counter? You could just use a counter? That would allow you to avoid the constant if/else within the loop (since your end condition can be size - 1).

The alternative, would be to use two iterators (which may save some additional costs associated with the array element access - not in itself expensive - but since you are passing in a reference to a vector, some compilers may force an additional pointless load op on 'begin' for each element access). Again, you can engineer your loop to test the 'next' element is not equal to end.


if(theList.size() < 2) return;


auto end = theList.end();

bool altered_list = true;

while(altered_list)

{

altered_list = false;


auto it = theList.begin();

auto next = it + 1;


for(; next != end; ++it, ++next) {

if(*it > *next) {

std::swap(*it, *next);

altered_list = true;

}

}

}



I suppose the correct way to swap elements would be with std::swap, which would remove the 'temp' variable, and make the code a little clearer to read.

The pass through counter seems to be a little superfluous (unless it's just a formatting thing).

The 'sorted' flag serves no purpose. You already have 'altered_list', which gives you the same information.

 

Your display list function....

It could take a const ref to the vector (rather than making a copy each time).

Again, that counter has returned!

If you want to see if the vector is empty, use the empty method! (size is typically implemented as a subtraction, so can be very modestly more expensive). Therefore repeatedly checking whether counter is equal to the size() is not considered good practice!

The if(iter != list.end()) check in the for loop is pointless. That condition is already checked by the for loop condition, so it can never enter the 'else'

Repeatedly doing if/else's for commas is probably a bad idea.


if(theList.empty()) {

// blah

}

else {

auto it = theList.begin();

auto end = theList.end();

cout << *it++;

for(; it != end; ++it)

cout << ", " << *it;

}

 

Thank you, I appreciate the help! :D I like your suggestions


In Topic: Memory Allocation

18 April 2016 - 10:10 PM

sizeof(Node)

Don't repeat the struct keyword everywhere or I will hunt you down and take all the vowels from your keyboard.

 

lol

 

 

 


 

return NULL;

 

You're right, that is an issue. However, I dont think thats it will solve this particular issue with my program though because when I call pop(), I make sure the function is not empty so return NULL isnt ever called. I even tried changing return NULL to return -1 and the same issue happened. Everything is working properly with no crash up until I add the free(temp) statement in the pop() method. If I uncomment that statement, it works perfect besides the fact that the memory leak isnt solved when popping.

 

Will node solve your issue but FYI, the correct solution in this case is quite simple:

template<typename T>
T returnDefault(void)
{
    return T();
}

This will return a specified default value for all types (int = 0, T* = nullptr, custom type = default-ctor, ...), so just replace return NULL by return T() and you should be fine in this regard.

 

 

Thank you, I never learned this

 

 

 

 sizeof(struct Node *) <- isn't this wrong??

 

for a node you should allocate sizeof(struct node) otherwise you allocate only pointer size space (4 or 8 bytes?)

 

Yes, this is the problem, you should be calling malloc(sizeof(struct Node)) .

 

However, you can make life easier using new and delete, like this

// in push()
Node* temp = new Node;
 
// later, in pop()
delete temp;

And, I just noticed, in pop(), why are you calling malloc() on temp again, then immediately assigning temp to headNode?  Don't malloc temp in pop().

 

You need to understand memory allocation a little more, then you should be able to tackle this problem fine.

 

 

Yeah I def needed to learn about memory allocation more haha I looked up some tutorials and watched some video explanations and I think I am understanding it better now.

 

 

PS - Thank you to everyone that helped me out, I got it working now!


In Topic: Memory Allocation

17 April 2016 - 10:16 PM

Should tailNode be updated in pop()?  What happens if tailnode is pointing at headNode?  

 

thanks, I totally forgot about that condition. No luck solving the heap corruption though :unsure:

 

 

return NULL;

 

You're right, that is an issue. However, I dont think thats it will solve this particular issue with my program though because when I call pop(), I make sure the function is not empty so return NULL isnt ever called. I even tried changing return NULL to return -1 and the same issue happened. Everything is working properly with no crash up until I add the free(temp) statement in the pop() method. If I uncomment that statement, it works perfect besides the fact that the memory leak isnt solved when popping.

 

Main.cpp

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

#include "LibIncludes.h"

void displayQueueSize(Queue<int> queue)
{
	std::cout << "Queue Size = " << queue.getSize() << "\n\n";
}

int main()
{
	Queue<int> myQueue;

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

	displayQueueSize(myQueue);

	int removed = myQueue.pop();

	if (removed < 0)
		std::cout << "\n*** pop() was unsuccessful. Queue is empty.\n";
	else
		std::cout << "\n*** pop() was successful. " << removed << " was removed.\n";

	system("PAUSE");

	return 0;
}

Queue.h

#pragma once

template <class T>
class Queue
{
	public:
		Queue();
		Queue(T newItem);
		void push(T newItem);
		void pop_all();
		T pop();
		T peek();
		bool isEmpty();
		int getSize();
	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>
T Queue<T>::peek()
{
	if (isEmpty())
		return NULL;
	else
		return headNode->data;
}

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

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";

		Node temp = headNode;

		for (int i = 0; i < size; i++)
		{
			pop();
		}

		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>
T Queue<T>::pop()
{
	if (isEmpty())
	{
		std::cout << "pop() was used, but the Queue is empty.\n\n";

		return -1;
	}
	else
	{
		Node * temp = (struct Node *)malloc(sizeof(struct Node *));
		
		temp = headNode;

		T removedItem = headNode->data;

		headNode = headNode->nextNode;

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

		free(temp);
		temp = nullptr;

		size--;

		if (size == 0)
		{
			free(tailNode);
			tailNode = nullptr;
		}

		return removedItem;
	}
}

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

template <typename T>
int Queue<T>::getSize()
{
	return size;
}

In Topic: Memory Allocation

17 April 2016 - 04:40 PM

Is IsEmpty() working correctly?

Are objects created with malloc?

is headNode a valid value?

Are the Nodes initialized to sensible values?

 

Check all everything is initialised to a sensible value (probably NULL). 

 

yes isEmpty() is working correctly and yes the objects are created using malloc.

 

 

T is not necessarily a pointer. T* is a pointer.

 

which portion were you referring to?


In Topic: Data Structures Help!

14 April 2016 - 01:09 PM

 

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


PARTNERS