Issue
For some reason when i run my C++ program on VS it compile and run smoothly and when i'm trying to run it on Linux Mint terminal it does compile without any errors but i'm not getting any feedback/printing to the terminal...it's just stuck - so i can't even guess where the problem is. any suggestions?
I'm really a noob when it comes to Linux...
my program contains 2 cpp class file, 2 header files (each for one class) and a main.cpp file which i'm trying to run like this:
g++ *.cpp -o myprog
./myprog
it does create a myprog file - but when i run it nothing happens, like i said.
my code:
btree.h
#include <iostream>
#ifndef _BTREE_H_
#define _BTREE_H_
class LinkedList;
struct node
{
int key_value;
node *left;
node *right;
};
class btree
{
friend class LinkedList;
public:
// Default constructor
btree();
~btree();
// Copy Constructor by list
btree(LinkedList &list);
// Copy Constructor by tree
btree(btree & bt);
// assignment operator from linked list
btree & operator=(const LinkedList & ls);
// assignment operator from tree
btree& operator=(const btree &bt);
// insert new value to binary tree
void insert(int key);
// mirror the tree
void mirror();
LinkedList* Tree2linkListbyDepth();
int getTreeDepth();
// print tree (in order)
friend std::ostream& operator<<(std::ostream& os, btree& dt);
private:
node* root;
bool isMirrored;
void copyConstructor(node *bt);
void destroyTree(node * tmp);
void insert(node* tmp, int key);
void mirrorInsert(node* tmp, int key);
void mirror(node * node);
LinkedList TreeToList(node *tmp, LinkedList *listToReturn, int depth);
int getTreeDepth(node * tmp);
friend std::ostream& travel(std::ostream & os, node* root);
};
#endif // _BTREE_H_
btree.cpp
#include"btree.h"
#include"Linkedlist.h"
#include<iostream>
using namespace std;
//constructor
btree::btree()
{
root = NULL;
isMirrored = false;
}
//destructor
btree::~btree()
{
destroyTree(this->root);
}
void btree::destroyTree(node * tmp)
{
if (tmp == NULL)
return;
destroyTree(tmp->left);
destroyTree(tmp->right);
delete(tmp);
}
//copy constructor - list to binary tree.
btree::btree(LinkedList &list)
{
while (list.head!=NULL)
{
insert(list.head->data);
list.head = list.head->next;
}
}
//copy constructor - inorder.
btree::btree(btree & bt)
{
if (bt.root == NULL)
root = NULL;
else
copyConstructor(bt.root);
}
void btree::copyConstructor(node *bt)
{
node* tmp = bt;
if (!tmp)
return;
copyConstructor(tmp->left);
insert(tmp->key_value);
copyConstructor(tmp->right);
}
//copying list to binary tree using "=" operator.
btree & btree::operator=(const LinkedList & ls)
{
Node *tmp = ls.head;
while (tmp != NULL)
{
insert(tmp->data);
tmp = tmp->next;
}
return *this;
}
//copying binary trees using "=" operator
btree & btree::operator=(const btree & bt)
{
if (this->root == bt.root) //cheking if not itself
return *this;
//למחוק את העץ הקיים
copyConstructor(bt.root);
return *this;
}
//inserting node to the binary tree
void btree::insert(int key)
{
node *tmp = root;
if (root != NULL)
{
if (isMirrored) //checking if the tree has been mirrored
mirrorInsert(tmp, key);
else
insert(tmp, key);
}
//if the tree is empty - adding a new node
else
{
root = new node;
root->key_value = key;
root->left = NULL;
root->right = NULL;
}
}
//regular insertion - smaller numbers to the left and bigger numbers to the right of the root.
void btree::insert(node* tmp, int key)
{
if (tmp->key_value >= key)
{
if (tmp->left == NULL)
{
tmp->left = new node();
tmp->left->key_value = key;
tmp->left->left = NULL;
tmp->left->right = NULL;
return;
}
insert(tmp->left, key);
}
else if (tmp->key_value < key)
{
if (tmp->right == NULL)
{
tmp->right = new node();
tmp->right->key_value = key;
tmp->right->left = NULL;
tmp->right->right = NULL;
return;
}
insert(tmp->right, key);
}
}
//mirrored insertion - smaller numbers to the right and bigger numbers to the left of the root.
void btree::mirrorInsert(node* tmp, int key)
{
if (tmp->key_value <= key)
{
if (tmp->left == NULL)
{
tmp->left = new node();
tmp->left->key_value = key;
tmp->left->left = NULL;
tmp->left->right = NULL;
return;
}
mirrorInsert(tmp->left, key);
}
else if (tmp->key_value > key)
{
if (tmp->right == NULL)
{
tmp->right = new node();
tmp->right->key_value = key;
tmp->right->left = NULL;
tmp->right->right = NULL;
return;
}
mirrorInsert(tmp->right, key);
}
}
//mirroring the binary tree and keeping track of it.
void btree::mirror()
{
if (isMirrored)
isMirrored = false;
else
isMirrored = true;
mirror(root);
}
void btree::mirror(node * node)
{
if (node == NULL)
return;
else
{
struct node * tmp;
mirror(node->left);
mirror(node->right);
tmp = node->left;
node->left = node->right;
node->right = tmp;
}
}
//constructing a list of lists, each list contains all the nodes at a specific level(depth).
LinkedList* btree::Tree2linkListbyDepth()
{
if (this == NULL)
return NULL;
node *tmp = root;
LinkedList *list;
int depth = this->getTreeDepth();
list = new LinkedList[depth]; //list of lists
for (int i = 0; i < depth; i++)
{
TreeToList(tmp, &list[i],(depth-i)); //adding to list[i] all the node in (depth-i) level from the binary tree using "TreeToList"
}
return list;
}
//returning a list with all the node at a specific level (depth).
LinkedList btree::TreeToList(node *tmp, LinkedList *listToReturn, int depth)
{
if (tmp == NULL)
return *listToReturn;
else if (getTreeDepth(tmp) == depth)
listToReturn->add(tmp->key_value);
else
{
TreeToList(tmp->left, listToReturn, depth);
TreeToList(tmp->right, listToReturn, depth);
}
return *listToReturn;
}
//returning the binary tree's depth.
int btree::getTreeDepth()
{
if (this->root == NULL)
return 0;
node* tmp = root;
return getTreeDepth(tmp);
}
int btree::getTreeDepth(node * tmp)
{
if (tmp == NULL)
return 0;
int leftDepth = getTreeDepth(tmp->left);
int rightDepth = getTreeDepth(tmp->right);
if (leftDepth > rightDepth)
return leftDepth+1;
else
return rightDepth+1;
}
ostream & travel(ostream &os, node* root)
{
node* tmp = root;
if (!root)
return os;
travel(os, root->left);
os << root->key_value << ",";
travel(os, root->right);
return os;
}
//printing the binary tree inorder - using recursive function "travel".
ostream & operator<<(ostream & os, btree & dt)
{
os << "Tree: ";
travel(os, dt.root);
os << endl;
return os;
}
Linkedlist.h
#include <iostream>
#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_
class btree;
class Node
{
public:
Node* next;
int data;
};
using namespace std;
class LinkedList
{
friend class btree;
public:
int length;
Node* head;
LinkedList(btree &bt);
LinkedList(LinkedList &bt);
LinkedList();
~LinkedList();
void add(int data);
LinkedList & operator=(const LinkedList & bt);
LinkedList& operator=(const btree &bt);
friend std::ostream& operator<<(std::ostream& os, LinkedList& l);
private:
void copyBtToList(struct node *bt);
LinkedList(const LinkedList &bt);
void addToTail(int data);
};
#endif // !_LINKEDLIST_H_
Linkedlist.cpp
#include"Linkedlist.h"
#include"btree.h"
#include<iostream>
using namespace std;
LinkedList::LinkedList() {
length = 0;
head = NULL;
}
//copy constructors.
LinkedList::LinkedList(LinkedList& other) {
length = 0;
if (this->head == other.head)
return;
Node* tmp = other.head;
while (tmp != NULL)
{
this->addToTail(tmp->data);
tmp = tmp->next;
}
length = other.length;
}
LinkedList::LinkedList(const LinkedList& other) {
this->length = other.length;
if (length == 0)
return;
Node* tmp = other.head;
while (tmp != NULL)
{
this->add(tmp->data);
tmp = tmp->next;
}
}
//destructor.
LinkedList::~LinkedList() {
Node* next = head;
Node* cur = NULL;
while (next != NULL) {
cur = next;
next = next->next;
delete cur;
}
}
//copying binary tree to a list.
LinkedList::LinkedList(btree &bt) {
if (bt.root == NULL)
this->head = NULL;
else
copyBtToList(bt.root);
}
void LinkedList::copyBtToList(node *bt)
{
node* tmp = bt;
if (!tmp)
return;
copyBtToList(tmp->left);
add(tmp->key_value);
copyBtToList(tmp->right);
}
//adding node to the head of the list.
void LinkedList::add(int data) {
Node* node = new Node();
node->data = data;
if (head == NULL) { //list is empty
head = node;
head->next = NULL;
length++;
return;
}
node->next = head;
head = node;
length++;
}
//adding node to the tail of the list.
void LinkedList::addToTail(int data) {
Node* node = new Node();
node->data = data;
node->next = NULL;
if (this->length == 0 || head == NULL) { //list is empty
head = node;
length++;
return;
}
Node* curr = head;
while (curr != NULL && curr->next!=NULL)
curr = curr->next;
curr->next = node;
length++;
}
//copying lists using "=" operator.
LinkedList & LinkedList::operator=(const LinkedList & bt)
{
LinkedList tmp(bt);
std::swap(tmp.head, this->head);
return *this;
}
//copying binary tree to list using "=" operator.
LinkedList & LinkedList::operator=(const btree & bt)
{
LinkedList tmp;
tmp.copyBtToList(bt.root);
head = tmp.head;
return *this;
}
//printing list in the form of "(x1,x2,...,xn)" using "<<" operator.
ostream & operator<<(ostream & os, LinkedList & l)
{
Node *tmp = l.head;
os << "List: (";
while (tmp != NULL)
{
os << tmp->data << ",";
tmp = tmp->next;
}
os << ")"<<endl;
return os;
}
main.cpp
#include"Linkedlist.h"
#include"btree.h"
#include<iostream>
using namespace std;
int main()
{
btree *tree = new btree();
tree->insert(10);
tree->insert(6);
tree->insert(14);
tree->insert(5);
tree->insert(8);
tree->insert(12);
tree->insert(16);
LinkedList* l = tree->Tree2linkListbyDepth();
int dp = tree->getTreeDepth();
for (int i = 0; i < dp; i++) {
cout << l[i];
}
cout << *tree;
tree->mirror();
cout << *tree;
btree *tree1 = new btree(l[dp - 1]);
cout << *tree1;
btree *tree2 = new btree(*tree1);;
tree2->insert(100);
cout << *tree1;
cout << *tree2;
LinkedList* l1 = new LinkedList(*tree1);
LinkedList* l2 = new LinkedList(*l1);
l2->add(99);
cout << *l1;
cout << *l2;
delete tree;
}
my output on VS:
List: (10,)
List: (14,6,)
List: (16,12,8,5,)
Tree: 5,6,8,10,12,14,16,
Tree: 16,14,12,10,8,6,5,
Tree: 5,8,12,16,
Tree: 5,8,12,16,
Tree: 5,8,12,16,100,
List: (16,12,8,5,)
List: (99,16,12,8,5,)
btw - i'll be happy if you could also check if my "includes" was done correctly cause i couldn't figure it out so easily...
Thanks :)
Solution
Update:
I ran your code through AppVerifier. And it didn't initially find anything until I tried different variations of Debug/Release x86/x64 builds. And one point I got it to crash in Windows. And then it stopped reproing the crash. Then I changed all your initial tree->insert
statements to take a rand()
value instead of a fixed value, I could get it to crash 100% of the time in Windows. I'm not sure if I event needed AppVerifier, but I left it on. That's when I noticed your LinkedList destructor was attempting to delete a pointer at 0xcccccccc, which is uninitialized memory in a debug build.
Bottom line, here is your bug:
Your LinkedList copy constructor is not initializing the head pointer to NULL
Also, you have two copy constructors. One that takes a non-const reference and is public. And another one (with slightly different behavior) that takes a const reference, but is private.
You just want a single copy constructor that is both public and takes a const reference.
Here's the fix. Let this be the public constructor:
LinkedList::LinkedList(const LinkedList& other) {
length = 0;
head = NULL; // YOU FORGOT THIS LINE
Node* tmp = other.head;
while (tmp != NULL)
{
this->addToTail(tmp->data);
tmp = tmp->next;
}
length = other.length;
}
And then remove the other instance of the LinkedList copy constructor.
Another thing that looks suspicious. Your btree constructor that takes a linked list is corrupting your list. It's also forgetting to initialize the object before attempting the first insert.
btree::btree(LinkedList &list)
{
while (list.head != NULL)
{
insert(list.head->data);
list.head = list.head->next;
}
}
This is completely wrong. When you construct the btree from the list (being passed via reference), the constructor will modify the passed in LinkedList instance. When this constructor returns, the list
instance will be returned to the call with a null head pointer, but a non-zero length member when the function returns.. And your LinkedList destructor will not be able to recurse the tree to free the memory. So you have both a memory leak and an invalid object state.
Do this instead.
btree::btree(const LinkedList &list)
{
root = NULL;
isMirrored = false;
Node* tmp = list.head;
while (tmp != NULL)
{
insert(tmp->data);
tmp = tmp->next;
}
}
It's also better to use initializer lists with constructors:
btree::btree(const LinkedList &list) :
root(NULL),
isMirrored(false)
{
...
}
You are welcome :)
old stuff:
Your cout
statements are missing an end-of-line marker (which flushes the output):
Instead of statements like this:
cout << *tree;
Do this:
cout << *tree << endl;
But that's not your issue. You have a crash in your program:
[ec2-user@ip-172-31-10-108 stackover]$ g++ main.cpp btree.cpp LinkedList.cpp
[ec2-user@ip-172-31-10-108 stackover]$ ./a.out
List: (10,)
List: (14,6,)
List: (16,12,8,5,)
Tree: 5,6,8,10,12,14,16,
Tree: 16,14,12,10,8,6,5,
Segmentation fault
Looks like we have a bug that results in a crash. Let's compile with a debug build and analyze:
[ec2-user@ip-172-31-10-108 stackover]$ g++ main.cpp btree.cpp LinkedList.cpp -g
[ec2-user@ip-172-31-10-108 stackover]$ gdb ./a.out
GNU gdb (GDB) Amazon Linux (7.6.1-64.33.amzn1)
...
Reading symbols from /home/ec2-user/stackover/a.out...done.
(gdb) run
Starting program: /home/ec2-user/stackover/./a.out
Missing separate debuginfo for /usr/lib64/libstdc++.so.6
Try: yum --enablerepo='*debug*' install /usr/lib/debug/.build-id/87/91ddd49348603cd50b74652c5b25354d8fd06e.debug
Missing separate debuginfo for /lib64/libgcc_s.so.1
Try: yum --enablerepo='*debug*' install /usr/lib/debug/.build-id/a0/3c9a80e995ed5f43077ab754a258fa0e34c3cd.debug
List: (10,)
List: (14,6,)
List: (16,12,8,5,)
Tree: 5,6,8,10,12,14,16,
Tree: 16,14,12,10,8,6,5,
Program received signal SIGSEGV, Segmentation fault.
0x00000000004011b5 in btree::mirrorInsert (this=0x614ea0, tmp=0x21, key=16) at btree.cpp:133
133 if (tmp->key_value <= key)
Missing separate debuginfos, use: debuginfo-install glibc-2.17-222.173.amzn1.x86_64
(gdb)
Short answer: it looks like you got some additional debugging to do around line 133 of btree.cpp. The value of tmp
has a value of 0x21 - which is likely not a legitimate pointer value.
Answered By - selbie