c++ - 插入堆栈时出现段错误

Question

我正在尝试使用 C++ 中可用的堆栈模板为 DFS 编写一个简单的代码。

它在运行时通过核心转储给出段错误。

我的代码片段如下:

#define XPIX 400
#define YPIX 600

这是节点类的定义:

class node{
public:
    int x;
    int y;
    node(int x,int y);
};

node::node(int x, int y){
    this->x = x;
    this->y = y;
}

主类如下:

class grafixMask {
public:
    vector <int> sortedAreas(vector <string> rectangles);
private:
    bool bitmap[XPIX][YPIX];
    stack <node> st;
    vector <int> parseInput(vector <string> Input);
    void init(int xLeft, int yLeft, int xRight, int yRight);
    int depth_first_search(int x,int y);
};

下面是DFS的函数:

int grafixMask::depth_first_search(int x, int y){
int result = 0;

this->st.push(node(x,y));

while(this->st.empty() == false){
    node topEle = this->st.top();
    this->st.pop();

    if(topEle.x < 0 || topEle.x > XPIX) continue;
    if(topEle.y < 0 || topEle.y > YPIX) continue;
    if(this->bitmap[topEle.x][topEle.y] == true) continue;
    this->bitmap[topEle.x][topEle.y] = true;
    result++;
    this->st.push(node(topEle.x - 1,topEle.y));
    this->st.push(node(topEle.x,topEle.y + 1));
    this->st.push(node(topEle.x + 1,topEle.y));
    this->st.push(node(topEle.x,topEle.y - 1));
}

return result;
}

我分析了核心转储，它说:

#1 0x0000000000403b47 in std::allocator<node>::~allocator ( this=0x7fffea214780, __in_chrg=<optimized out>) at /usr/include/c++/4.7/bits/allocator.h:112 
#2 0x0000000000402d1b in std::_Deque_base<node, std::allocator<node> >::~_Deque_base (this=0x6dd3c0, __in_chrg=<optimized out>) at /usr/include/c++/4.7/bits/stl_deque.h:568 
#3 0x000000000040216e in std::vector<std::string, std::allocator<std::string> >::push_back (this=0x7fffea24f340, __x=...) at /usr/include/c++/4.7/bits/stl_vector.h:887    
#4 0x00000000004016f6 in grafixMask::depth_first_search ( this=0x7fffea2149c0, x=0, y=0) at B.cpp:137 
#5 0x00000000004012c7 in grafixMask::sortedAreas (this=0x7fffea2149c0, rectangles=...) at B.cpp:87 #6 0x0000000000401965 in main () at B.cpp:154

调试显示问题出在第 134 行:

(gdb) print topEle.y
$5 = 51
(gdb) next
132         this->bitmap[topEle.x][topEle.y] = true;
(gdb) next
133         result++;
(gdb) next
134         this->st.push(node(topEle.x - 1,topEle.y));
(gdb) next

Program received signal SIGSEGV, Segmentation fault.
0x00000000004038b9 in __gnu_cxx::new_allocator<node>::construct (
    this=0x7fffffffde50, __p=0x160d698, __val=...)
    at /usr/include/c++/4.7/ext/new_allocator.h:120
120       { ::new((void *)__p) _Tp(__val); }

根据源代码，这些语句位于第 134 到 137 行之间。

    this->st.push(node(topEle.x - 1,topEle.y));
    this->st.push(node(topEle.x,topEle.y + 1));
    this->st.push(node(topEle.x + 1,topEle.y));
    this->st.push(node(topEle.x,topEle.y - 1));

请提出为什么将 node 元素插入 stack 失败。

Answer 1

看来你的线路有问题

if(topEle.x < 0 || topEle.x > XPIX) continue;

您已将数组声明为 bool bitmap[XPIX][YPIX];，这意味着允许使用 0...XPIX-1 范围内的索引。将 topEle.x > XPIX 替换为 topEle.x >= XPIX。