回 帖 发 新 帖 刷新版面

主题:总是显示stack溢出 不知道怎么解决

各位大牛,我是刚从Fortran转到c++的,主要是Fortran在数据结构方面比c或者c++弱很多。以前只学过c,没有学过c++,所以代码基本上用我以前写的c的方法,然后加上一些在网上找的c++的类,就形成了现有的代码。
下面的代码是其中我整个程序的一部分,这个代码主要实现的就是找图的强连通分量,用的是gabow算法,这部分程序是在某一大牛的blog上copy下来的,调试没有问题。
这个程序 在系统参数 nxc=300,nyc=300 是没有问题的。但是在nxc=500,nyc=500就发生溢出。经过调试,可能有问题的地方应该是vector超过了最大size。不知道怎么解决这一问题。
我的编译器是vs2008,在Windows下。

希望各位大牛帮忙解答,谢谢。





[code=c]
#include "cstdlib" 
#include "cctype" 
#include "cstring" 
#include "cstdio" 
#include "cmath" 
#include "algorithm" 
#include "vector" 
#include "string" 
#include "iostream" 
#include "sstream" 
#include "set" 
#include "queue" 
#include "stack" 
#include "fstream" 
#include "strstream" 
#include <afx.h>
#include <dos.h>
using namespace std;

#define  M 500001              //题目中可能的最大点数       
#define  AM 100                  //吸引子的最大数目
int STACK[M],top=0;          //Gabow 算法中的辅助栈 
int STACK2[M],top2=0;        // 
int DFN[M];                  //深度优先搜索访问次序 
int ComponetNumber=0;        //有向图强连通分量个数 
int AttactorNumber=0;
int Index=0;                 //索引号 
int Belong[M];               //某个点属于哪个连通分支
int oud[M];
int ind[M];
int atag[AM];                //给吸引子赋号
int dtag[AM][M];
int visited[M];                //标记是否访问过
int snum[M];
vector <int> Edge[M];        //邻接表表示 
vector <int> Component[M];   //获得强连通分量结果

//////////////////于系统相关的常数////////////////////////////////////////////////////////////////////
double xl=-2.5,xu=1.5,yl=-2,yu=2;
int nxc=500,nyc=500;
//////////////////于系统相关的常数///////////////////////////////////////////////////////////////////

void Gabow(int i) 

    int j; 
    DFN[i]=Index++; 
    STACK[++top]=i; 
    STACK2[++top2]=i; 
    for (int e=0;e<Edge[i].size();e++) 
    { 
        j=Edge[i][e]; 
        if (DFN[j]==-1)  Gabow(j); 
        else if (Belong[j]==-1)       //如果访问过,但没有删除,维护STACK2 
        { 
            while(DFN[STACK2[top2]]>DFN[j])        //删除构成环的顶点 
                top2--; 
        } 
    } 
    if(i==STACK2[top2])               //如果Stack2 的顶元素等于i,输出相应的强连通分量
    {  
        --top2;
        do 
        { 
            Belong[STACK[top]]=ComponetNumber; 
            Component[ComponetNumber].push_back(STACK[top]); 
        }while ( STACK[top--]!=i);
        ComponetNumber++;                //从0开始标记
    } 
}

void solve(int N)     //此图中点的个数,注意是0-indexed! 

    memset(STACK,-1,sizeof(STACK)); 
    memset(STACK2,-1,sizeof(STACK2)); 
    memset(Belong,-1,sizeof(Belong)); 
    memset(DFN,-1,sizeof(DFN));

    for(int i=0;i<N;i++) 
        if(DFN[i]==-1) 
            Gabow(i);    



/* 
此算法正常工作的基础是图是0-indexed的。但是获得的结果Component数组和Belong数组是1-indexed 
*/ 
int main() 

    int a[2],j=1;
    int  N=nxc*nyc+1;
    FILE *fp;
    
    fp=fopen("transmatrix.dat","rb");
    if(fp==NULL)
    {
        printf("ERROR!");
    }
    else{
        a[0]=0;
        while(a[0]!=N-1){
            fread(a,2*sizeof(int),1,fp);
            Edge[a[0]].push_back(a[1]);
            //printf("%d    %d\n",a[0],a[1]);
        }
        fclose(fp);
    }

     
        solve(N); 

    printf("%d",AttactorNumber);

    //sound(1000);   //以1000hz的频率打开喇叭
    //nosound();     //关闭喇叭
    putchar('\a');
       return 0; 
}
[/code]

回复列表 (共3个回复)

沙发

没有transmatrix.dat,没法调试

板凳


是一个接近30M的二进制文件,不知道怎么贴过来啊

3 楼

栈溢出,最常见的原因有两个。第一是使用了太大的局部变量,第二是递归调用层次太深。
从楼主的代码来看,没有发现较大的局部变量,因此怀疑是因为递归调用层次太深导致。

void Gabow(int i) 
if (DFN[j]==-1)  Gabow(j); 
这里存在递归调用。
我没有太仔细的阅读代码,但是根据int DFN[M];以及#define  M 500001这两句来看,似乎可能有数十万层的递归调用。
假设每次递归调用占据16字节,总共就会占据大约8M空间,而一般windows程序默认栈空间不足2M,这样一来栈空间确实会溢出。

解决的办法:
1、看能否设法增大栈空间。一般而言,修改编译器选项,即可让生成的程序分配更大的栈空间。或者,在创建线程时,也可以指定栈空间。
2、如果不能改变栈空间,那就设法修改代码,改用非递归的做法。从数学上讲,递归算法都可以用非递归的方式来实现。

我来回复

您尚未登录,请登录后再回复。点此登录或注册