#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));
}
}
}
Why can't this struct call another function?
Author
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.
[Edited by - AncientPC on March 16, 2007 2:19:43 PM]
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.
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.
It's a typo on your part....
The function is "NewNode" and you are calling a function that doesn't exist called "newNode"
The function is "NewNode" and you are calling a function that doesn't exist called "newNode"
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! :)
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! :)
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.
EDIT: I left this open while I went a meeting, and hit reply when I got back. Silly me.
Author
Thanks for all the fast replies, especially Unbeliever for pointing out all the minor nuances.
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.
Second, a standard C++ version:
Third, a typical SC++L version, which should work out of the box:
Fourth, in my typical ML zealotish fashion:
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 | Nulllet 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 -> xlet rec lookup i = function | Null -> false | Node (j,l,_) when i < j -> lookup i l | Node (j,_,r) when i > j -> lookup i r | _ -> trueQuote: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).
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
