Register FAQ / Rules Forum Spy Search Today's Posts Mark Forums Read
Go Back   MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Reply
 
Thread Tools Search this Thread Display Modes
Old Jul 5, 2011, 11:34 PM   #1
jCrabb13
macrumors newbie
 
Join Date: Apr 2010
Send a message via Skype™ to jCrabb13
C++ Binary Search Error

Lucky for me I am a student at Texas A&M and Bjarne Stroustrup is at my school. I have made it past the classes that his book covers but the idea and general coding knowledge is mostly from that book. with that being said, lets get to it!

I am trying to make a binary_search function using a tree to find an element in a vector (way more work than its worth to me but that's what the question asks for) This comes from 26.1 and then Exercise 1 of c26 from Stroustrup's Programming Principles and Practice with the tree requirement coming from my current prof.

I can't seem to figure out what my problem is. I have made one before and I used the same structure, but it keeps stopping after the first loop on this line (47) in the Tree.h file when trying to insert my vector elements into the tree.

Code:
else if(n < (t->value))
Here are the files I am using;

main.cpp
Code:
#include <iostream>
#include "vector.h"
#include "BinarySearch.h"

int main () 
{    
	vector<int> nums;
	nums.push_back(3);
	nums.push_back(5);
	nums.push_back(9);
	nums.push_back(13);
	nums.push_back(13);
	nums.push_back(20);
	nums.push_back(56);
	nums.push_back(78);
	nums.push_back(94);
	nums.push_back(99);
	
	BinarySearch BS(nums);
	
	if(BS.isEmpty())
		cout<<"well ****"<<endl;
	
	if(BS.find(56)) cout<<"FOUND"<<endl;
	else cout<<"NOT FOUND"<<endl;
	
	return 0;
}
tree.h
Code:
#include <cstddef>
#include <iostream>

struct TreeNode
{
	int value;
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;
	
	TreeNode()
	{
	   
	}
	
	TreeNode(int n)
	{
	   value=n;
	}
};

struct Tree
{
	TreeNode *root;
	
	Tree() 
	{
	}
	
	Tree(int n)
	{
	   root = new TreeNode(n);
	}
	
	TreeNode *getRoot()
	{
	   return root;
	}
	
	void insert(int n,TreeNode *t)
	{
	   if(t==NULL)
		{
		   root = new TreeNode(n);
		   cout<<"TreeNode made: "<<n<<endl;
		}
	   else if(n < (t->value))
		{ 
			insert(n,t->left);
			cout<<n<<" moved left"<<endl;
		}
		   
		else if(n > (t->value))
		{
			insert(n,t->right);
			cout<<n<<" moved right"<<endl;
		}
			   			   
		//error protection
		else if(n==t->value)
			cout<<n<<" is a duplicate value. SKIPPING ENTRY"<<endl;
	}
	
	int find(int n, TreeNode *t)
	{
	   while(t!=NULL)
		{
		   if(n<t->value) t=t->left;
		   else if(n>t->value) t=t->right;
		   else
			{ 
				cout<<n<<" is found!"<<endl;
				return true;
			}
		}
		
	   return false;
	}
};
BinarySearch.h
Code:
#include <math.h>
#include "Tree.h"

struct BinarySearch
{

	Tree T;
	
	BinarySearch()
	{
	   
	}
	
	BinarySearch(vector<int> n)
	{
	   for(int i=0;i<n.size();i++)
		{
		   T.insert((int)n[i],T.root);
		}
	}
	
	bool isEmpty()
	{
	   if(T.root==NULL)
		   return true;
	   return false;
	}
	
	bool find(int n)
	{
	   return T.find((int)n,T.getRoot());
	}
};
any help would be greatly appreciated. finishing this problem along with some others is the difference in an important letter grade for me.

Thanks and Gig 'em!
jCrabb13 is offline   0 Reply With Quote
Old Jul 6, 2011, 03:12 AM   #2
Sander
macrumors 6502
 
Join Date: Apr 2008
Of a new TreeNode you construct, what are its initial values for "parent", "left", and "right"..? And what is the initial value of "root" when you construct a new Tree with its default constructor..?
Sander is offline   0 Reply With Quote
Old Jul 6, 2011, 05:47 PM   #3
jCrabb13
Thread Starter
macrumors newbie
 
Join Date: Apr 2010
Send a message via Skype™ to jCrabb13
Quote:
Originally Posted by Sander View Post
Of a new TreeNode you construct, what are its initial values for "parent", "left", and "right"..? And what is the initial value of "root" when you construct a new Tree with its default constructor..?
they weren't defined. but even when i make them all NULL, i still pull the same error. this is what happens in the console:


TreeNode made: 3
Program received signal: “EXC_BAD_ACCESS”.
sharedlibrary apply-load-rules all
jCrabb13 is offline   0 Reply With Quote
Old Jul 6, 2011, 06:10 PM   #4
chown33
macrumors 603
 
Join Date: Aug 2009
Quote:
Originally Posted by jCrabb13 View Post
they weren't defined. but even when i make them all NULL, i still pull the same error. this is what happens in the console:


TreeNode made: 3
Program received signal: “EXC_BAD_ACCESS”.
sharedlibrary apply-load-rules all
First: use the debugger. See what happens after the console output of "TreeNode made: 3". In other words, where is the EXC_BAD_ACCESS coming from?

If you don't know how to use the debugger, now's a good time to learn. You should at least be able to set breakpoints, step through code a line at a time, and examine values of variables. That's the minimum for a debugger to be useful.

Second: point out the code that assigns something into left, right, or parent after a new TreeNode is created.
chown33 is offline   0 Reply With Quote
Old Jul 6, 2011, 06:11 PM   #5
naples98
macrumors member
 
Join Date: Sep 2008
Location: San Diego
Quote:
Originally Posted by jCrabb13 View Post
they weren't defined. but even when i make them all NULL, i still pull the same error. this is what happens in the console:


TreeNode made: 3
Program received signal: “EXC_BAD_ACCESS”.
sharedlibrary apply-load-rules all
It has been awhile since I've done C++ but I'm pretty sure you never initialize Tree T in your BinarySearch struct so you are attempting to access some random memory location.
naples98 is offline   0 Reply With Quote
Old Jul 6, 2011, 08:35 PM   #6
jCrabb13
Thread Starter
macrumors newbie
 
Join Date: Apr 2010
Send a message via Skype™ to jCrabb13
Quote:
Originally Posted by chown33 View Post
First: use the debugger. See what happens after the console output of "TreeNode made: 3". In other words, where is the EXC_BAD_ACCESS coming from?

If you don't know how to use the debugger, now's a good time to learn. You should at least be able to set breakpoints, step through code a line at a time, and examine values of variables. That's the minimum for a debugger to be useful.

Second: point out the code that assigns something into left, right, or parent after a new TreeNode is created.
the debugger has it stopping after the first loop on this line (47) in the Tree.h file. i think it cant figure out what t->value equals but i dont know why.

Quote:
Originally Posted by naples98 View Post
It has been awhile since I've done C++ but I'm pretty sure you never initialize Tree T in your BinarySearch struct so you are attempting to access some random memory location.
thats the way we did it all year...i'm pretty sure that parts right.
jCrabb13 is offline   0 Reply With Quote
Old Jul 6, 2011, 09:40 PM   #7
ehoui
macrumors regular
 
Join Date: Jan 2011
Ask yourself where you are setting the left, right and parent values of a new node. You are not. That's a problem.

Last edited by ehoui; Jul 6, 2011 at 09:50 PM.
ehoui is offline   0 Reply With Quote
Old Jul 6, 2011, 10:00 PM   #8
jCrabb13
Thread Starter
macrumors newbie
 
Join Date: Apr 2010
Send a message via Skype™ to jCrabb13
Quote:
Originally Posted by ehoui View Post
Ask yourself where you are setting the left, right and parent values of a new node. You are not. That's a problem.
Ya I realized that and adjusted the TreeNode's default constructor to this:

Code:
TreeNode()
	{
	   value=NULL;
	   parent=NULL;
	   left=NULL;
	   right=NULL;
	}
and the tree's to this:

Code:
Tree() 
	{
	   root=NULL;
	}
still pulling the exact same error though! :/
jCrabb13 is offline   0 Reply With Quote
Old Jul 6, 2011, 10:11 PM   #9
ehoui
macrumors regular
 
Join Date: Jan 2011
Quote:
Originally Posted by jCrabb13 View Post
Ya I realized that and adjusted the TreeNode's default constructor to this:

Code:
TreeNode()
	{
	   value=NULL;
	   parent=NULL;
	   left=NULL;
	   right=NULL;
	}
and the tree's to this:

Code:
Tree() 
	{
	   root=NULL;
	}
still pulling the exact same error though! :/
And where are those constructors being called? These are the questions you need to ask yourself. The debugger would tell you that TreeNode() is not being called. Why because are calling a different constructor: TreeNode::TreeNode(int) not TreeNode::TreeNode(). I think you need a review of the earlier chapters :-).
ehoui is offline   0 Reply With Quote
Old Jul 6, 2011, 10:16 PM   #10
jCrabb13
Thread Starter
macrumors newbie
 
Join Date: Apr 2010
Send a message via Skype™ to jCrabb13
Quote:
Originally Posted by ehoui View Post
And where are those constructors being called? These are the questions you need to ask yourself. The debugger would tell you that TreeNode() is not being called. Why because are calling a different constructor: TreeNode::TreeNode(int) not TreeNode::TreeNode(). I think you need a review of the earlier chapters :-).
God I am so stupid. lol. it's always something like that that I forget to do, thanks a ton! i'll update the thread if i get stumped again!
jCrabb13 is offline   0 Reply With Quote

Reply
MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
thread Thread Starter Forum Replies Last Post
iCab search error Josh125 iPad Apps 0 May 2, 2011 07:58 PM
itunesconnect application loader binary upload error homer-aust iPhone/iPad Programming 1 Aug 23, 2010 07:55 AM
Binary Search function problem in C++ ingenious Mac Programming 12 Dec 11, 2008 11:40 AM
Binary Search Tree Deletation HINA ELLAHI Mac Programming 1 Dec 27, 2007 01:55 AM
C++ Binary Search Tree Problem steelphantom Mac Programming 11 Oct 19, 2007 04:58 AM


All times are GMT -5. The time now is 03:35 AM.

Mac Rumors | Mac | iPhone | iPhone Game Reviews | iPhone Apps

Mobile Version | Fixed | Fluid | Fluid HD
Copyright 2002-2013, MacRumors.com, LLC