Я повторяю какое-то задание из моего класса о бинарном дереве, и я столкнулся с проблемой, которая мне никогда не показалась.
Сначала попробуйте запустить код, у меня ошибка сегментации. Я думал о странной петле, но я не могу найти проблему. Итак, я попытался с GDB и Valgrind, получив это:
Начальная программа: / home / и / Documenti / Algoritmi / Esercizi / Esame 01-02-2018 / esa2
Starting program: /home/and/Documenti/Algoritmi/Esercizi/Esame 01-02-2018/esa2 < input0.txt
Program received signal SIGSEGV, Segmentation fault.
0x00007ffff7c65cbc in _int_malloc (av=av@entry=0x7ffff7db3c40 <main_arena>, bytes=bytes@entry=32) at malloc.c:3711
3711 malloc.c: File o directory non esistente.
(gdb) where
#0 0x00007ffff7c65cbc in _int_malloc (av=av@entry=0x7ffff7db3c40 <main_arena>, bytes=bytes@entry=32) at malloc.c:3711
#1 0x00007ffff7c67ad3 in __GI___libc_malloc (bytes=32) at malloc.c:3065
#2 0x00007ffff7e79a25 in operator new(unsigned long) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#3 0x0000555555555240 in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6df90: 0x0) at esa_2.cpp:38
#4 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6df60: 0x555555b6df80) at esa_2.cpp:44
#5 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6df30: 0x555555b6df50) at esa_2.cpp:44
#6 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6df00: 0x555555b6df20) at esa_2.cpp:44
#7 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6ded0: 0x555555b6def0) at esa_2.cpp:44
#8 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dea0: 0x555555b6dec0) at esa_2.cpp:44
#9 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6de70: 0x555555b6de90) at esa_2.cpp:44
#10 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6de40: 0x555555b6de60) at esa_2.cpp:44
#11 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6de10: 0x555555b6de30) at esa_2.cpp:44
#12 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dde0: 0x555555b6de00) at esa_2.cpp:44
#13 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6ddb0: 0x555555b6ddd0) at esa_2.cpp:44
#14 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dd80: 0x555555b6dda0) at esa_2.cpp:44
#15 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dd50: 0x555555b6dd70) at esa_2.cpp:44
#16 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dd20: 0x555555b6dd40) at esa_2.cpp:44
#17 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dcf0: 0x555555b6dd10) at esa_2.cpp:44
#18 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dcc0: 0x555555b6dce0) at esa_2.cpp:44
#19 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dc90: 0x555555b6dcb0) at esa_2.cpp:44
#20 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dc60: 0x555555b6dc80) at esa_2.cpp:44
#21 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dc30: 0x555555b6dc50) at esa_2.cpp:44
#22 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dc00: 0x555555b6dc20) at esa_2.cpp:44
#23 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dbd0: 0x555555b6dbf0) at esa_2.cpp:44
#24 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dba0: 0x555555b6dbc0) at esa_2.cpp:44
#25 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6db70: 0x555555b6db90) at esa_2.cpp:44
#26 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6db40: 0x555555b6db60) at esa_2.cpp:44
#27 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6db10: 0x555555b6db30) at esa_2.cpp:44
#28 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dae0: 0x555555b6db00) at esa_2.cpp:44
#29 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6dab0: 0x555555b6dad0) at esa_2.cpp:44
#30 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6da80: 0x555555b6daa0) at esa_2.cpp:44
#31 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6da50: 0x555555b6da70) at esa_2.cpp:44
#32 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6da20: 0x555555b6da40) at esa_2.cpp:44
#33 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d9f0: 0x555555b6da10) at esa_2.cpp:44
#34 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d9c0: 0x555555b6d9e0) at esa_2.cpp:44
#35 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d990: 0x555555b6d9b0) at esa_2.cpp:44
#36 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d960: 0x555555b6d980) at esa_2.cpp:44
#37 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d930: 0x555555b6d950) at esa_2.cpp:44
#38 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d900: 0x555555b6d920) at esa_2.cpp:44
#39 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d8d0: 0x555555b6d8f0) at esa_2.cpp:44
#40 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d8a0: 0x555555b6d8c0) at esa_2.cpp:44
#41 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d870: 0x555555b6d890) at esa_2.cpp:44
#42 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d840: 0x555555b6d860) at esa_2.cpp:44
#43 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d810: 0x555555b6d830) at esa_2.cpp:44
#44 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d7e0: 0x555555b6d800) at esa_2.cpp:44
#45 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d7b0: 0x555555b6d7d0) at esa_2.cpp:44
#46 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d780: 0x555555b6d7a0) at esa_2.cpp:44
#47 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d750: 0x555555b6d770) at esa_2.cpp:44
#48 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d720: 0x555555b6d740) at esa_2.cpp:44
#49 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d6f0: 0x555555b6d710) at esa_2.cpp:44
#50 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d6c0: 0x555555b6d6e0) at esa_2.cpp:44
#51 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d690: 0x555555b6d6b0) at esa_2.cpp:44
#52 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d660: 0x555555b6d680) at esa_2.cpp:44
#53 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d630: 0x555555b6d650) at esa_2.cpp:44
#54 0x00005555555552bd in BinTree::insert (this=0x7fffffffdda0, info=6, tree=@0x555555b6d600: 0x555555b6d620) at esa_2.cpp:44
Затем я провел некоторое исследование, и кто-то предложил Вальгринд, поэтому я попробую. Это результат:
==5605== Memcheck, a memory error detector
==5605== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5605== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==5605== Command: ./esa2
==5605==
==5605== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5605==
==5605== Process terminating with default action of signal 11 (SIGSEGV)
==5605== Access not within mapped region at address 0x1FFE801FE0
==5605== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5605== at 0x4A3546B: operator new(unsigned long) (vg_replace_malloc.c:344)
==5605== If you believe this happened as a result of a stack
==5605== overflow in your program's main thread (unlikely but
==5605== possible), you can try to increase the size of the
==5605== main thread stack using the --main-stacksize= flag.
==5605== The main thread stack size used in this run was 8388608.
==5605== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5605==
==5605== Process terminating with default action of signal 11 (SIGSEGV)
==5605== Access not within mapped region at address 0x1FFE801FC8
==5605== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==5605== at 0x482D6E0: _vgnU_freeres (vg_preloaded.c:59)
==5605== If you believe this happened as a result of a stack
==5605== overflow in your program's main thread (unlikely but
==5605== possible), you can try to increase the size of the
==5605== main thread stack using the --main-stacksize= flag.
==5605== The main thread stack size used in this run was 8388608.
==5605==
==5605== HEAP SUMMARY:
==5605== in use at exit: 4,266,272 bytes in 130,923 blocks
==5605== total heap usage: 130,923 allocs, 0 frees, 4,266,272 bytes allocated
==5605==
==5605== LEAK SUMMARY:
==5605== definitely lost: 0 bytes in 0 blocks
==5605== indirectly lost: 0 bytes in 0 blocks
==5605== possibly lost: 0 bytes in 0 blocks
==5605== still reachable: 4,266,272 bytes in 130,923 blocks
==5605== suppressed: 0 bytes in 0 blocks
==5605== Reachable blocks (those to which a pointer was found) are not shown.
==5605== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==5605==
==5605== For lists of detected and suppressed errors, rerun with: -s
==5605== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Вот код:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class BinTree{
struct node{
int label;
bool concordant;
int nConcordant;
node *left;
node *right;
node(int info){
label = info;
nConcordant = 0;
left = right = NULL;
}
};
node *root;
vector<int> values;
void insert(int, node*&);
bool isLeaf(node*);
void setConcordant(node*);
int countConcordant(node*);
void setValues(node*, vector<int>&);
void printValues(vector<int>);
public:
BinTree(){root = NULL;};
void insertTree(int);
void output();
};
void BinTree::insert(int info, node *&tree){
if(!tree){
tree = new node(info);
tree->left = tree->right = NULL;
}
if(tree->label < info)
insert(info, tree->right);
else
insert(info, tree->left);
};
bool BinTree::isLeaf(node* tree){
if(!tree)
return false;
if(!(tree->left) && !(tree->right))
return true;
return false;
};
void BinTree::setConcordant(node *tree){
if(!tree)
return;
if(isLeaf(tree))
return;
if(tree->left){
if(tree->label % 2 == (tree->left)->label % 2)
(tree->left)->concordant = true;
else
(tree->left)->concordant = false;
}
if(tree->right){
if(tree->label % 2 == (tree->right)->label % 2)
(tree->right)->concordant = true;
else
(tree->right)->concordant = false;
}
setConcordant(tree->left);
setConcordant(tree->right);
};
int BinTree::countConcordant(node* tree){
if(!tree)
return 0;
if(isLeaf(tree)){
if(tree->concordant)
return 1;
else
return -1;
}
tree->nConcordant += countConcordant(tree->left) + countConcordant(tree->right);
return tree->nConcordant;
};
void BinTree::setValues(node* tree, vector<int>& values){
if(!tree)
return;
if(tree->nConcordant >= 0)
values.push_back(tree->label);
setValues(tree->left, values);
setValues(tree->right, values);
};
void BinTree::printValues(vector<int> values){
sort(values.begin(), values.end());
for(int i=0; i<values.size(); i++)
cout<<values[i]<<endl;
};
void BinTree::insertTree(int info){
insert(info, root);
};
void BinTree::output(){
setConcordant(root);
countConcordant(root);
setValues(root, values);
printValues(values);
};
int main(){
int dim;
cin >> dim;
BinTree tree;
for(int i=0; i<dim; i++){
int info;
cin >> info;
tree.insertTree(info);
}
tree.output();
return 0;
}
Проблема, похоже, в функции вставки, но я не знаю, что делать, чтобы ее исправить