关于利用递归给二维数组赋值的一个问题
本帖最后由 u011209118 于 2013-06-26 09:53:05 编辑 用递归方法编写了一个给二维数组赋值的程序，但是运行时或提示发生堆栈溢出的错误，程序如下：
如果程序中row和col设置的很小，比如20，程序是可以运行的。请各位高手帮忙看看问题出在那里。
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
//如果row和col较小，程序可以运行
int row = 80;
int col = 80;
void regionGrow(int **imgFlag, int x, int y);
int _tmain(int argc, _TCHAR* argv[])
{
int **imgFlag = new int*[row];
for (int i=0; i<row; i++) {
imgFlag[i] = new int[col];
}
for (int i=0; i<row; i++) {
for (int j=0; j<col; j++) {
imgFlag[i][j] = 0;
}
}
regionGrow(imgFlag, col/2, row/2);
return 0;
}
void regionGrow(int **imgFlag, int x, int y)
{
if (imgFlag[y][x]==0)
imgFlag[y][x] = 1;
else
return;
if (x>0 && imgFlag[y][x-1]!=1) regionGrow(imgFlag, x-1, y);
if (y>0 && imgFlag[y-1][x]!=1) regionGrow(imgFlag, x, y-1);
if (x<col-1 && imgFlag[y][x+1]!=1) regionGrow(imgFlag, x+1, y);
if (y<row-1 && imgFlag[y+1][x]!=1) regionGrow(imgFlag, x, y+1);
} 递归 二维数组 C++
[解决办法]
递归次数过多导致堆栈溢出
要么限制递归次数，要么自己保存递归状态
[解决办法]
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出
[解决办法]
把你的代码如下修改后运行：
[code=c]
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
int row = 1000;
int col = 1000;
void regionGrow(int **imgFlag, int x, int y, unsigned int level);
int main(int argc, char* argv[])
{
int **imgFlag = new int*[row];
for (int i=0; i<row; i++)
{
imgFlag[i] = new int[col];
}
for (int i=0; i<row; i++)
{
for (int j=0; j<col; j++)
{
imgFlag[i][j] = 0;
}
}
regionGrow(imgFlag, col/2, row/2, 1);
return 0;
}
void regionGrow(int **imgFlag, int x, int y, unsigned int level)
{
assert( x >= 0 && x < col );
assert( y >= 0 && y < row );
std::cerr << ++level << '\n';
if (imgFlag[y][x]==0)
imgFlag[y][x] = 1;
else
return;
if (x>0 && imgFlag[y][x-1]!=1) regionGrow(imgFlag, x-1, y, level);
if (y>0 && imgFlag[y-1][x]!=1) regionGrow(imgFlag, x, y-1, level);
if (x<col-1 && imgFlag[y][x+1]!=1) regionGrow(imgFlag, x+1, y, level);
if (y<row-1 && imgFlag[y+1][x]!=1) regionGrow(imgFlag, x, y+1, level);
}
#include <iostream>
#include <fstream>
#include <cassert>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
int row = 300;
int col = 300;
void regionGrow(int **imgFlag, int x, int y);
int main(int argc, char* argv[])
{
int **imgFlag = new int*[row];
for (int i=0; i<row; i++)
{
imgFlag[i] = new int[col];
}
for (int i=0; i<row; i++)
{
for (int j=0; j<col; j++)
{
imgFlag[i][j] = 0;
}
}
regionGrow(imgFlag, col/2, row/2);
return 0;
}
void regionGrow(int **imgFlag, int x, int y)
{
std::stack<std::pair<int, int> > point_stack;
if( imgFlag[y][x] == 0)
{
point_stack.push( pair<int, int>( x, y ));
}
unsigned int level = 0; //这行代码将来要删掉
while( !point_stack.empty())
{
level = std::max( level, point_stack.size());//这行代码将来要删掉
std::cerr << '\r' << level << " ";//这行代码将来要删掉
int x = point_stack.top().first;
int y = point_stack.top().second;
point_stack.pop();
assert( x >= 0 && x < col );
assert( y >= 0 && y < row );
imgFlag[y][x] = 1;
//为了让数据处理数据和原来的代码相同，我这里把判断顺序倒过来了
//因为处理时后入栈的先处理。
if (y<row-1 && imgFlag[y+1][x]!=1) point_stack.push( std::pair<int,int>(x, y+1));
if (x<col-1 && imgFlag[y][x+1]!=1) point_stack.push(std::pair<int,int>( x+1, y));
if (y>0 && imgFlag[y-1][x]!=1) point_stack.push(std::pair<int,int>( x, y-1));
if (x>0 && imgFlag[y][x-1]!=1) point_stack.push(std::pair<int,int>( x-1, y));
}
}
#include <iostream>
#include <fstream>
#include <cassert>
#include <algorithm>
using namespace std;
int row = 1000;
int col = 1000;
const int dir_left = 1;
const int dir_right = 2;
const int dir_up = 3;
const int dir_down = 4;
const int dir_all = dir_left
[解决办法]
dir_right
[解决办法]
dir_up
[解决办法]
dir_down;
unsigned int max_level = 0;
void regionGrow(int **imgFlag, int x, int y, int dir, unsigned int level);
bool check_result(int **imgFlag)
{
bool ok = true;
int x = 0;
while( ok && x < col )
{
int y = 0;
while( ok && y < row )
{
ok = ( imgFlag[y][x] == 1);
++ y;
}
++ x;
}
return ok;
}
int main(int argc, char* argv[])
{
int **imgFlag = new int*[row];
for (int i=0; i<row; i++)
{
imgFlag[i] = new int[col];
}
for (int i=0; i<row; i++)
{
for (int j=0; j<col; j++)
{
imgFlag[i][j] = 0;
}
}
regionGrow(imgFlag, col/2, row/2, dir_all, 1);
assert(check_result(imgFlag));
std::cout << "Max level:" << max_level << '\n';
return 0;
}
void regionGrow(int **imgFlag, int x, int y, int dir, unsigned int level)
{
assert( x >= 0 && x < col );
assert( y >= 0 && y < row );
max_level = std::max(level ++, max_level);
if (imgFlag[y][x]==0)
imgFlag[y][x] = 1;
else
return;
if ( (dir & dir_left) && (x>0) && (imgFlag[y][x-1]!=1) )
//允许向左，并且未到左边界，并且左边需要处理
{
regionGrow(imgFlag, x-1, y, dir & ~dir_right, level );//下一步不允许向右
}
if ( (dir & dir_up) && (y>0) && (imgFlag[y-1][x]!=1) )
//允许向上，并且未到上边界，并且上边需要处理
{
regionGrow(imgFlag, x, y-1, dir & ~dir_down, level);//下一步不允许向下
}
if ( (dir & dir_right) && (x<col-1) && (imgFlag[y][x+1]!=1) )
//允许向右，并且未到右边界，并且右边需要处理
{
regionGrow(imgFlag, x+1, y, dir & ~dir_left, level);//下一步不允许向左
}
if ( (dir & dir_down) && (y<row-1) && (imgFlag[y+1][x]!=1) )
//允许向规划，并且未到下边界，并且下边需要处理
{
regionGrow(imgFlag, x, y+1, dir & ~dir_up, level);//下一步不允许向上
}
}
