主题:总是显示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]
下面的代码是其中我整个程序的一部分,这个代码主要实现的就是找图的强连通分量,用的是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]