Trouble with an iterative algorithm (maybe memory allocation)

[charij]

Hi guys,

I'm trying to implement an iterative algorithm that generates and fills a tree structure and then prints out the contents. Each branch of the tree being a combination of values that add up to a target total.

From what I can tell as soon as iAlgorithm calls itself the data in the nodes seem to get corrupted. I'm guessing it's something to do with allocating the nodes with memory? But I'm having trouble getting any tutorials for it work with the code.

Any advice / tips would be awesome! Thanks for reading,
Pete

P.S I'm trying to convert the algorithm here to list the combinations instead of just counting: http://rosettacode.org/wiki/Count_the_coins#C

My current code:

#include <iostream>
#include <vector>

using namespace std;

#define MAX_ITEMS 10

int values[] = { 0, 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};

struct Node
{
	int	 valueID,
		 depth;
	Node *prev;
	
	Node() 
	{
		valueID = 0;
		depth = 0;
		prev = NULL;
	}
	Node(int ID, Node parent)
	{
		valueID = ID;
		prev = &parent;
		depth = prev->depth + 1;
	}
};

void printBranch(Node *node)
{
	Node position = *node;

	while(position.depth > 0 && position.depth <= MAX_ITEMS)
	{
		cout <<	position.valueID << "\t";
		position = *position.prev;
	}
	cout <<	"\n";
}

vector<Node>	Combos;

int iAlgorithm(int sum, Node parent)
{
	if(parent.depth > MAX_ITEMS || sum < 0)	
		return 0;

	for(int i=1; i<12; i++)
	{
		Node newNode = Node(values[i], parent);

		if(sum - values[i] == 0)	
		{
			Combos.push_back(newNode);
			return 1;
		}

		iAlgorithm(sum - values[i], newNode);
	}
	return 0;
}

int main()
{
	Node	Root = Node();	
	iAlgorithm(5, Root);
	
	for(int i=0; i<Combos.size(); i++)
		printBranch(&Combos[i]);

	return 0;
}

[ne555]

	Node(int ID, Node parent) //passed a copy
	{
		valueID = ID;
		prev = &parent; //so this is meaningless
		depth = prev->depth + 1;
	}//as the parent dies here
int iAlgorithm(int sum, Node parent) //same  

[charij]

Awesome catch, thanks loads for that one!

EDIT: Works quite nicely now!

Latest code:

#include <iostream>
#include <vector>

using namespace std;

#define MAX_ITEMS 10

int values[] = { 0, 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000};

struct Node
{
	int	 valueID,
		 depth;
	Node *prev;
	
	Node() 
	{
		valueID = 0;
		depth = 0;
		prev = NULL;
	}
	Node(int ID, Node *parent)
	{
		valueID = ID;
		prev = parent;
		depth = prev->depth + 1;
	}
};

void printBranch(Node *node)
{
	Node *position = node;

	while(position->depth > 0)
	{
		cout <<	position->valueID << ", ";
		position = position->prev;
	}
	cout <<	"\n\n";
}

vector<Node>	Combos;

int iAlgorithm(int sum, Node *parent, int index)
{
	if(parent->depth > MAX_ITEMS || sum < 0)	
		return 0;

	for(int i=index; i<12; i++)
	{

		if(sum - values[i] == 0)	
		{
			Combos.push_back(Node(values[i], parent));
			return 1;
		}
		if(sum - values[i] > 0)
		{
			Node* newNode = (Node*) malloc(sizeof(Node));
			newNode->valueID=values[i];
			newNode->prev=parent;
			newNode->depth=parent->depth+1;			
			iAlgorithm(sum - values[i], newNode, i);
		}
	}
	return 0;
}

int main()
{
	Node Root = Node();	
	iAlgorithm(1366, &Root, 1);
	
	for(int i=0; i<Combos.size(); i++)
		printBranch(&Combos[i]);

	return 0;
}

[thepedestrian]

Have you made sure that Node *prev; always points to a valid node?

[charij]

Nope, I wasn't sure what to do for the root node. Any suggestions on how to structure it better? :)

[thepedestrian]

I think that is what the problem is.

So in the root nodes, set the value of Node *prev to NULL.

Then you can have a simple check clause which could be prev != NULL or something.