Sign in to follow this  
AncientPC

Why can't this struct call another function?

Recommended Posts

The error is this line: return newNode(data); Apparently it can't "see" the NewNode helper function, but I don't know why. I've tried prototyping but it doesn't work.
#include <iostream>
using namespace std;

struct node
{
	int data;
	struct node* left;
	struct node* right;
};

struct node* NewNode(int data)
{
	struct node* node=new struct node;
	node->data=data;
	node->left=NULL;
	node->right=NULL;
	return node;
};

struct node* insert(struct node* node, int data)
{
	if (node==NULL)
	  return newNode(data);
	else
	{
	  if (data<=node->data)
	    node->left=insert(node->left,data);
		else
		  node->right=insert(node->right,data);
		  
		return node;
	}
};

static int lookup(struct node*, int);

int main()
{
	return 0;
}

static int lookup(struct node* node, int target)
{
	if (node==NULL)
	{
	  return false;
	}
	else
	{
	  if (target==node->data)
	    return true;
		else
		{
		  if (target<node->data)
		    return(lookup(node->left,target));
		  else
		    return(lookup(node->right,target));
		}
	}
}

[Edited by - AncientPC on March 16, 2007 2:19:43 PM]

Share this post


Link to post
Share on other sites
Standard response: Use std::list for a linked list

Useful response:

1. You have unnecessary semicolons at the end of your function bodies. These aren't actually a problem (because they just get read as an empty statement) but they are, as I've said, unnecessary and are so bad practice.

2. struct node* node=new struct node; should be struct node* somenameotherthannode = new node;. The struct prefix isn't necessary in C++ - unless, as in this case, you're choosing to name a variable the same as the type - which is basically a bad idea. This goes the same for all your functions that return a pointer to a node - the type should be node* not struct node*.

3. Your actual problem is ignoring case. You're calling newNode when your function is named NewNode. Pick one or t'other.

EDIT: Beaten again! I'm far too slow for these boards.
EDIT2:

4. Why are you prototyping lookup before main when you don't need to? a) It doesn't currently need prototyped at all and b) why not just move the function definition above main were it to be needed?

EDIT3:

5. What does static do in the global namespace? I've forgotten, but I can't help but strongly suspect that the qualifier is unnecessary.

6. Just to be pedantic - the struct itself isn't calling anything (and never can - although a member function might). A function using the struct isn't calling something.

Share this post


Link to post
Share on other sites
newNode() is not NewNode(). Function names are case sensitive.

Also, you don't need to have those struct keywords in front of the node* return types. I guess that's a C-styled approach, but I'd say it looks confusing - those functions look like struct definitions on first sight.

EDIT: Hah, fast replies guys! :)

Share this post


Link to post
Share on other sites
Usual uninformed remark: use std::list for a linked list in C++. A more informed remark: use std::set to represent sets of integers.

Wait, is this C or C++? Depending on the language, there are many ways in which the code would differ.

First, what should be a standard C version.


typedef struct node
{
int data;
struct node *left;
struct node *right;
} node_t;

node_t *newNode(int data)
{
node_t *node = malloc(sizeof(node_t));
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
};

node_t *insert(node_t* node, int data)
{
if (!node)
return newNode(data);
else
{
if (data<=node->data)
node->left=insert(node->left,data);
else
node->right=insert(node->right,data);
return node;
}
};

static int lookup(node_t*, int);

int main()
{
return 0;
}

static int lookup(node_t* node, int target)
{
if (!node)
{
return false;
}
else if (target==node->data)
{
return true;
}
else if (target<node->data)
{
return(lookup(node->left,target));
}
else
{
return(lookup(node->right,target));
}
}




Second, a standard C++ version:

class tree
{
struct node
{
int data;
node *left, *right;

// Creating a new node from nothing
node(int data) : data(data), left(0), right(0) {}

// Destructor : clean up children.
~node()
{
delete left;
delete right;
}

// Private copy constructor and assignment.
private:
node(const node&);
node& operator=(const node&);
};

// Insert data into a node
static node *insert(node* n, int i)
{
if (!n) return new node(i);
if (i < n->data)
{
n->left = insert(n->left,i);
}
else
{
n->right = insert(n->right,i);
}
return n;
}

// Lookup a data in the tree
static bool lookup(node* n, int i)
{
return
(n) && (
(n->data == i) ||
(n->data > i) && lookup(n->left,i) ||
(n->data < i) && lookup(n->right,i)
);
}

// The root node
node *n;
public:

tree() : n(0) {}

void insert(int i)
{
this->n = insert(this->n,i);
}

bool lookup(int i)
{
return lookup(this->n,i);
}
};




Third, a typical SC++L version, which should work out of the box:


#include <set>
typedef std::set<int> node;

void insert(node &n, int i)
{
node.insert(i);
}

bool lookup(const node& n, int i)
{
return (node.find(i) != node.end());
}




Fourth, in my typical ML zealotish fashion:


type tree =
| Node of int * tree * tree
| Null

let rec insert i = function
| Null -> Node (i,Null,Null)
| Node (j,l,r) when i < j -> Node (j,insert i l,r)
| Node (j,l,r) when i > j -> Node (j,l,insert i r)
| x -> x

let rec lookup i = function
| Null -> false
| Node (j,l,_) when i < j -> lookup i l
| Node (j,_,r) when i > j -> lookup i r
| _ -> true

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Usual uninformed remark: use std::list for a linked list in C++. A more informed remark: use std::set to represent sets of integers.


Oops. Guess I'll ask for the information I'm lacking then - why std::set? The OP is storing a linked list of ints, for whatever reason (I'm guessing pedagogical purposes but maybe I'm wrong). A std::set doesn't allow duplicates, right? The two are for different purposes - a linked list of ints has one purpose and the set another.

I'm still learning (as much as I try to help) so I'm curious as to the reasoning (or, alternatively, pointers to where my logic is flawed).

Share this post


Link to post
Share on other sites
Quote:
Original post by TheUnbeliever
The OP is storing a linked list of ints, for whatever reason


This is where I differ. He is not storing a linked list: he is storing a tree (an unbalanced binary sorted tree, to be precise). Note, in particular, the way in which a node does not point at its own parent (as in a linked list), but rather at its two own children. And, looking at his usage, his only queries so far are insertion and existence, which are completely orthogonal to the presence of duplicates. So, std::set for insertion/existence and std::multi_set if duplicates are necessary.

EDIT: now that I think about it, depending on the usage, an std::map<int,int> might be better than an std::multi_set<int> when storing multiplicities (if there are many duplicates, and iterating through the set is not necessary).

Share this post


Link to post
Share on other sites
This is a C way of doing things, personally I have two types of tree structures which I can then create insertion/sorting functions. The two types I have are a binary tree as you have posted and a tree with any number of children(oct, quad...). The nice part about it is the release function which is recursive, feel free to use and abuse the code.

template<typename T>
struct Binary_tree
{
typedef T type;
typedef Binary_tree<type>* Node;
Node m_left;
Node m_right;
Node m_parent;
type m_data;
Binary_tree():m_left(0),m_right(0),m_parent(0){}
Binary_tree(type data):m_left(0),m_right(0),m_parent(0),m_data(data){}
Binary_tree(type data,Node left,Node right):m_left(left),m_right(right),m_parent(0),m_data(data)
{
m_left->m_parent = this;
m_right->m_parent = this;
}
Binary_tree(Node left,Node right):m_left(left),m_right(right),m_parent(0)
{
m_left->m_parent = this;
m_right->m_parent = this;
}
void release()
{
if( m_left )
{
delete m_left;
m_left = 0;
}
if( m_right )
{
delete m_right;
m_right = 0;
}
}
~Binary_tree()
{
release();
}

bool is_leaf(){return m_left == 0 && m_right == 0;}
};




[edit]I did not see ToohrVyk post before I posted this.
I should also add that as you can see my structure has a parent node as sometimes its nice to be able to traverse up aswell as down the tree.(NOTE to self make an iterator class:) )

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by TheUnbeliever
The OP is storing a linked list of ints, for whatever reason


This is where I differ. He is not storing a linked list: he is storing a tree (an unbalanced binary sorted tree, to be precise).


Ah, I didn't look at the logic, which explains half the problem since even a glance at the node struct shows what you mean.

Quote:
And, looking at his usage, his only queries so far are insertion and existence, which are completely orthogonal to the presence of duplicates. So, std::set for insertion/existence


Another quarter, this time maybe slightly less technical since these features may be yet to be implemented - but I see your point.

Quote:
and std::multi_set if duplicates are necessary.


And the final quarter - I don't yet have a sufficient knowledge of the standard library to have encountered that yet. I'll need to go look that one up just now.

Thanks for the explanation. :-)

EDIT: And your edit makes slightly more sense to me, so it's reassuring that I'm not always totally wrong!

Share this post


Link to post
Share on other sites
This is in C++, and this question is a continuation from this thread.

I planned on an unbalanced binary search tree (is balancing difficult?) based upon ages and a map<name><node pointer> to lookup info / delete people.

Share this post


Link to post
Share on other sites
Quote:
Original post by AncientPC
I planned on an unbalanced binary search tree (is balancing difficult?)


It's difficult enough to justify not reinventing the wheel.

Look, you already got some perfectly good options explored for you making full use of the standard library. Why wouldn't you at least try those first?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this