1

为什么会出现分段错误以及如何解决？

我正在编写下面的代码以递归地“遍历”迷宫并找到路径总数。我正在使用堆栈来跟踪“下一步”。

ROWS 和 COLUMNS 定义了迷宫的大小。如果我使这些参数大于 9x9，则会出现分段错误。我不知道我为什么会这样。

这是我第一次使用 gdb 并得到以下信息：

#3  0x0000000000400de0 in std::stack<xy, std::deque<xy, std::allocator<xy> > >::top (this=0x604400 <buff>)
at /usr/lib/gcc/x86_64-unknown-linux-gnu/4.7.2/../../../../include/c++/4.7.2/bits/stl_stack.h:161
161     return c.back();

让我相信这与我的堆栈有关。

我很感激任何帮助。谢谢。

编码：

#define ROWS 10
#define COLUMNS 10

#include<iostream>
#include<stack>
using namespace std;

struct xy
{
  long i;
  long j;
};

stack<xy> buff;

long goRight (long j)
{
  if (j < COLUMNS-1)
    return 1;
  else
    return 0;
}

long goDown (long i)
{
  if (i < ROWS-1)
    return 1;  
  else
    return 0;
}

long traverse (xy POS)
{
  long fD = goDown(POS.i);
  long fR = goRight(POS.j);

  xy toAdd;

  if (fD == 1)
    {
      toAdd.i=POS.i+1;
      toAdd.j=POS.j;
      buff.push(toAdd);
    }

  if (fR == 1)
    {
      toAdd.i=POS.i;
      toAdd.j=POS.j+1;
      buff.push(toAdd);
    }

  if(buff.empty())
    return 0;

  toAdd = buff.top();
  buff.pop();

  return (traverse(toAdd) + (fD * fR));
}

int main()
{
  xy initial;
  initial.i=0;
  initial.j=0;

  cout << 1 + traverse(initial);

  return 1;
}
4

2 回答 2

1

您call stack的内存量有限，您调用的每个函数都在使用该堆栈上的内存。因此，在一个巨大的迷宫中递归地进行暴力破解最终会导致堆栈溢出。使用 gdb 的回溯功能应该清楚地告诉你。

您应该重新考虑您的算法并使用迭代而不是递归。在您的情况下，您似乎想要实现某种洪水填充算法，这很容易通过迭代来实现，如本链接中所述。

另请注意，如果您使用的是 linux 系统，则 usingulimit -s unlimited将允许您为call stack从此终端仿真器运行的所有程序使用无限量的内存。你的程序不应该出现段错误。

祝你好运。

于 2013-01-05T22:36:56.430 回答
0

我相信你不需要一个std::stack对象来实现你想要的（即计算路径的数量）。而且你不一定要切换到迭代，这使得这个算法更难编写，只需简化算法及其终止条件。

这是一个可能的解决方案（顺便说一句，如果您打算增加行数和列数，可以考虑切换到 along long以避免整数- 而不是堆栈 - 溢出）：

#define ROWS 10
#define COLUMNS 10

#include<iostream>
#include <stack>

using namespace std;

struct xy
{
  long i;
  long j;
};

stack<xy> partialPath;

long goRight (long j)
{
  if (j < COLUMNS - 1)
    return 1;
  else
    return 0;
}

long goDown (long i)
{
  if (i < ROWS - 1)
    return 1;
  else
    return 0;
}

long traverse (xy const& POS)
{
    partialPath.push(POS); // Not needed to count the # of paths, but if you want...

    long fD = goDown(POS.i);
    long fR = goRight(POS.j);

    xy nextPos;
    long numOfPaths = 0;
    if (fD == 1)
    {
        nextPos.i=POS.i+1;
        nextPos.j=POS.j;
        numOfPaths += traverse(nextPos);
    }

    if (fR == 1)
    {
        nextPos.i=POS.i;
        nextPos.j=POS.j+1;
        numOfPaths += traverse(nextPos);
    }

    partialPath.pop(); // Not needed to count the # of paths, but if you want...

    if ((fD == 0) && (fR == 0))
    {
        return 1;
    }

    return numOfPaths;
}

int main()
{
  xy initial;
  initial.i=0;
  initial.j=0;

  cout << traverse(initial);

  return 0;
}

PS：为了提高效率，最好POS通过 const ref 传递参数。另外，我认为用于指示您的过程成功的返回码应该是 0 而不是 1（我的意思是在return语句中main()）。

于 2013-01-05T22:58:18.027 回答