温馨提示:本文翻译自stackoverflow.com,查看原文请点击:c++ - Segmentation Fault inserting in binary tree

c++ - 在二叉树中插入分段错误

发布于 2020-03-27 10:49:52

我正在重复课堂上关于二叉树的作业,但遇到了一个从未出现过的问题。

刚开始尝试运行代码时,我遇到了段错误。我想到了一个怪异的循环,但是我找不到问题。因此,我尝试了gdb和valgrind,获得了以下内容:启动程序:/ home / and / Documenti / Algoritmi / Esercizi / Esame 01-02-2018 / esa2 <input0.txt

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

然后,我做了一些研究,有人建议Valgrind,所以我尝试一下。结果如下:

==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;
}

问题似乎出在插入函数中,但我不知道该怎么做才能解决它

查看更多

查看更多

提问者
Liamen
被浏览
58
SolidMercury 2019-07-03 22:29

您的insert函数将递归执行。没有中断条件可以返回而无需insert进一步调用这将导致堆栈存储器被填满,最后发生溢出,这是分段错误。

发布
问题

分享
好友

手机
浏览

扫码手机浏览