Jump to content
  • Advertisement
Sign in to follow this  
AncientPC

Why can't this struct call another function?

This topic is 4118 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

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
Advertisement
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
newNode is not the same as NewNode.

EDIT: I left this open while I went a meeting, and hit reply when I got back. Silly me.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!