Thread: Pointer Problems...

Well. I ran your program through GDB:

Code:

$ gdb tempjunior.exe
GNU gdb 5.2.1
Copyright 2002 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i686-pc-mingw32"...
(gdb) break createTree
Breakpoint 1 at 0x401648: file tempjunior.cpp, line 80.
(gdb) r
Starting program: C:\dwk\c/tempjunior.exe

Breakpoint 1, createTree(node*, int*, int) (start=0x3d2548, numbers=0x22ff30,
    size=10) at tempjunior.cpp:80
80          cout << "createTree(" << start << ',' << numbers << ',' << size << "
)\n";
(gdb) p start
$1 = (node *) 0x3d2548
(gdb) p *$
$2 = {data = -1163005939, parent = 0xbaadf00d, cLeft = 0xbaadf00d,
  cRight = 0xbaadf00d}
(gdb) n
82              if(size &#37; 2 == 0)
(gdb)
84                      startPoint = size/2;
(gdb) p size
$3 = 10
(gdb) n
89              start->data = numbers[startPoint];
(gdb) p startPoint
$4 = 5
(gdb) p numbers
$5 = (int *) 0x22ff30
(gdb) p numbers[0]
$6 = 0
(gdb) p numbers[3]
$7 = 3
(gdb) p numbers[9]
$8 = 9
(gdb) p numbers[10]
$9 = 4007024
(gdb) p *start
$10 = {data = -1163005939, parent = 0xbaadf00d, cLeft = 0xbaadf00d,
  cRight = 0xbaadf00d}
(gdb) n
97              tempP = addPly(start, numbers, startPoint);
(gdb) p *start
$11 = {data = 5, parent = 0xbaadf00d, cLeft = 0xbaadf00d, cRight = 0xbaadf00d}
(gdb) p start->cLeft
$12 = (node *) 0xbaadf00d
(gdb) p *$
$13 = {data = 775171635, parent = 0x69622f32, cLeft = 0x6f2f7374,
  cRight = 0x65727473}
(gdb)

As you might be able to see, start->cLeft and start->cRight are not initialized. Let's take a look at the code you initalize them in:

Code:

struct node *addPly(node *parent, int numbers[], int cArrayPoint)
{
	node *nLeft;
	node *nRight;

	nLeft = new node;
	nRight = new node;

	if(cArrayPoint-1 >= 0)
	{
		nLeft->data = numbers[cArrayPoint-1];
		parent->cLeft = nLeft;
	}else{
		parent->cLeft = NULL;
		delete nLeft;
	}
	if(cArrayPoint+1 <= 10)
	{
		nRight->data = numbers[cArrayPoint+1];
		parent->cRight = nRight;
	}else{
		parent->cRight = NULL;
		delete nRight;
	}
	return parent;
}

See, there's a problem with that code. You set either cRight or cLeft, but not both. I suggest setting them both to NULL at the beginning of that function.

Code:

parent->cLeft = parent->cRight = 0;

Also, why new something and then immediately delete it? I'm sure you can think of a way around that . . . .

After playing around with it a bit, I found the function call that segfaults:

Code:

Breakpoint 2, countNodes(node*) (startPoint=0xbaadf00d) at tempjunior.cpp:202
202             if(startPoint == NULL)
(gdb) p *startPoint
$15 = {data = 774843950, parent = 0x2e2e2f2e, cLeft = 0x2f2e2e2f,
  cRight = 0x6c636e69}
(gdb) bt
#0  countNodes(node*) (startPoint=0xbaadf00d) at tempjunior.cpp:202
#1  0x00401a1c in countNodes(node*) (startPoint=0x3d3b40) at tempjunior.cpp:208
#2  0x00401a31 in countNodes(node*) (startPoint=0x3d27a0) at tempjunior.cpp:209
#3  0x00401a1c in countNodes(node*) (startPoint=0x3d2700) at tempjunior.cpp:208
#4  0x00401a1c in countNodes(node*) (startPoint=0x3d2660) at tempjunior.cpp:208
#5  0x00401a1c in countNodes(node*) (startPoint=0x3d25c0) at tempjunior.cpp:208
#6  0x00401a1c in countNodes(node*) (startPoint=0x3d2570) at tempjunior.cpp:208
#7  0x00401a1c in countNodes(node*) (startPoint=0x3d2548) at tempjunior.cpp:208
#8  0x004015d8 in main () at tempjunior.cpp:64
(gdb)

I'm not sure what's happening and unfortunately I don't have enough time to debug it, but since the function call two calls previous had cLeft=NULL, I'm guessing you don't set something to NULL somewhere. Good luck.

Okay so after doing some stuff and researching a bit more i think my first approach to this problem wasn't the best one to take. So i remade the program from scratch with some changes, and (again) i'm getting seg faults, but i think i'm on the right track with making the tree. Take a look:

Code:

//Include Files
#include <iostream>
#include <vector>

using namespace std;

//Structures
struct node
{
	int data;
	node *parent;
	node *cLeft;
	node *cRight;
};

struct tree
{
	node *root;
};

//Function Prototypes
void createTree(tree *start, vector<int> numbers);
void sortNumbers(vector<int>& v, int size);
void getNumbers(vector<int>& v);
void displayNumbers(vector<int> v, int size);
void addPly(node *parent, int data);
node *makeNode(int data);

//Global Variables
tree *bTree;
node *root;
node *current;

//Main
int main()
{
	//Tree Initial Variables
	bTree = new tree;

	root = new node;

	bTree->root = root;

	//Data initial Variables
	vector<int> numbers;

	getNumbers(numbers);

	int size = numbers.size();

	sortNumbers(numbers, size);

	cout<<endl<<"Sorted Numbers:"<<endl;
	displayNumbers(numbers, size);
	//--Pause
	cin.ignore();

	//Create The Tree Of the Numbers
	createTree(bTree, numbers);

	//End
	return 0;
}

void createTree(tree *start, vector<int> numbers)
{
	//Create Tree Function
	int size = numbers.size();
	//Get Starting Point
	int sPoint = (int)(size/2);
	int increment = 1;
	start->root->data = numbers.at(sPoint);
	//Insert Data
	for(int i=0; i<size/2; i++)
	{
		if(sPoint-increment > 0)
		{
			addPly(start->root, numbers.at(sPoint-increment));
		}
		if(sPoint+increment < size)
		{
			addPly(start->root, numbers.at(sPoint+increment));
		}
		increment++;
	}
}

void addPly(node *parent, int data)
{
	//Function which adds a ply to a parent Node
	if(parent == NULL)
	{
		parent = makeNode(data);
	}
	else if(parent->data > data)
	{
		if(parent->cLeft != NULL)
			addPly(parent->cLeft, data);
		else if(parent->cLeft == NULL)
		{
			parent->cLeft = makeNode(data);
			parent->cLeft->parent = parent;
		}
	}
	else if(parent->data < data)
	{
		if(parent->cRight != NULL)
			addPly(parent->cRight, data);
		else if(parent->cRight == NULL)
		{
			parent->cRight = makeNode(data);
			parent->cRight->parent = parent;
		}
	}
}

node *makeNode(int data)
{
	node *nNode;
	nNode = new node;
	if(nNode != NULL)
	{
		nNode->data = data;
		nNode->cLeft = nNode->cRight = NULL;
	}
	return nNode;
}

void getNumbers(vector<int>& v)
{
	//Get The Numbers and Push them into the Vector Function
	cout<<"Enter As Many Numbers as You Wish...\n"<<"(Type 0 to Stop entering Numbers)"<<endl;
	int temp;
	int i=0;
	do{
		cout<<"Element "<<(i+1)<<": ";
		cin>>temp;
		cin.ignore();

		if(temp == 0)
		{
			break;
		}

		v.push_back(temp);

		i++;
	}while(1);
}

void sortNumbers(vector<int> &v, int size)
{
	//Sort the numbers in the vector from Lowest->Highest
	int temp;

	for(int j=0; j<size; j++)
	{
		for(int i=0; i+1<size; i++)
		{
			if(v.at(i) > v.at(i+1))
			{
				temp = v.at(i);
				v.at(i) = v.at(i+1);
				v.at(i+1) = temp;
			}
		}
	}
}

void displayNumbers(vector<int> v, int size)
{
	//Display the Contents of the Vector of Numbers
	for(int i=0; i<size; i++)
	{
		cout<<"Element "<<(i+1)<<": "<<v.at(i)<<endl;
	}
}

What do ya think? Anyone see where the segfaults are? Probably (obviously) stemming from the createTree() function, i think it's happening in the addPly() function (again) .

Thanks!

makeNode() is an excellent idea.

Code:

void sortNumbers(vector<int> &v, int size)
{
// ...
			if(v.at(i) > v.at(i+1))

You can obtain the number of elements in a vector with vector::size(), as you have done here:

Code:

int size = numbers.size();

Also, vector::at() does not do bounds checking, just so you know. (operator[] does.) http://www.cppreference.com/cppvector/index.html

Code:

void addPly(node *parent, int data)
{
	//Function which adds a ply to a parent Node
	if(parent == NULL)
	{
		parent = makeNode(data);
	}

What happens if parent is NULL again after that? (It could be, if you were out of memory.) Also, if parent is NULL, that's the only thing you do in that function, because everything else is in else ifs.

Code:

		if(parent->cLeft != NULL)
			addPly(parent->cLeft, data);
		else if(parent->cLeft == NULL)

You could just use else here. If the first is false, the second is certainly true. Why waste CPU cycles?

Code:

if(sPoint+increment < size)

No doubt you want

Code:

if(sPoint+increment+1 < size)

Otherwise you try to access one past the end of the vector with at() which doesn't do bounds checking.

I have a suggestion for you. Rather than read in a list of numbers and then create a tree out of it, why not make the tree as you go? It wouldn't be any faster, but it might use less memory. Then again, you might end up with an unbalanced tree.

Also, the kind of tree you're making is really just a linked list that goes in two directions.

Yeah i realized that shortly after i made it. Because the list is sorted it would make pretty much a linked list.

And you're right, i should probably do it as i go. It might not be balanced, but it might work.

I dunno where to even begin, ha

Prelude's tutorials from eternallyconfuzzled.com are probably a good place to start.

Yeah i've tried reading it. It doesn't give you like the full code though. Not how to setup the tree unless i missed something... =(

It doesn't give you like the full code though. Not how to setup the tree unless i missed something... =(

It does show you how to insert elements. Scroll down to the Insertion section of Part 1.

> Also, vector::at() does not do bounds checking, just so you know. (operator[] does.)
This is backwards.

Oops.

The at() function is safer than the [] operator, because it won't let you reference items outside the bounds of the vector.