问题描述
- 请教各位大神有关c++ stack overflow错误
-
DEBUG提示错误：First-chance Exception in ConvexHull.exe(NTDLL.DLL);0xC00000FD:Stack Overflow点击ALT+7之后查看调用栈内容如下：
NTDLL! 77452c33() NTDLL! 77455ae0() NTDLL! 774c5f63() NTDLL! 7748a40a() NTDLL! 77455ae0() _heap_alloc_base(unsigned int 64) line 200 _heap_alloc_dbg(unsigned int 16, int 1, const char * 0x00000000, int 0) line 378 + 9 bytes _nh_malloc_dbg(unsigned int 16, int 1, int 1, const char * 0x00000000, int 0) line 248 + 21 bytes _nh_malloc(unsigned int 16, int 1) line 197 + 19 bytes operator new(unsigned int 16) line 24 + 11 bytes std::_Allocate(int 1, dot * 0x00000000) line 30 + 12 bytes std::allocator<dot>::allocate(unsigned int 1, const void * 0x00000000) line 59 + 40 bytes std::vector<dot,std::allocator<dot> >::insert(dot * 0x00000000, unsigned int 1, const dot & {...}) line 158 + 14 bytes std::vector<dot,std::allocator<dot> >::insert(dot * 0x00000000, const dot & {...}) line 154 std::vector<dot,std::allocator<dot> >::push_back(const dot & {...}) line 142 + 50 bytes Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 63 Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes Divide(dot {...}, dot {...}, std::vector<dot,std::allocator<dot> > {...}) line 77 + 119 bytes ......使用的是VC6.0，编译器就是VC6.0默认的。
本人是个菜鸟，根据调用栈给出的内容完全不知道如何定位错误。
本人的程序是快速凸包算法（一个课后作业），程序在数据量比较少的情况下，点的个数在1000以下都运行正常，程序逻辑没有错误，当数据量增大到2000、3000的时候程序就提示出上述异常。顺便说一下设置栈保留大小也已经试过了，将栈保留大小设置为16000000也无效。
以下是本人代码：
// ConvexHull.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "dot.h" #include <iostream> #include <vector> #include "BruteForceCH.h" #include "line.h" #include <windows.h> #include <time.h> #include <fstream> #include "comm.h" #include "GrahamScan.h" #include <stack> #include "QuickTuBao.h" #define random(x) (rand()%x) using namespace std; int main(int argc, char* argv[]) { int n; printf("input dots number:n"); cin >> n; //随机点生成算法 //* vector<dot> vec; srand((int)time(0)); for(int i=0;i<n;) { dot d; d.x = random(100) + (float)random(10)/(float)10; d.y = random(100) + (float)random(10)/(float)10; //d.x = random(10); //d.y = random(10); if(find(vec.begin(),vec.end(),d) != vec.end()); else { vec.push_back(d); i++; } } //*/ //将生成的点写入文件，便于MATLAB读入 ofstream f1("C:\MATLAB7\work\dot\dots.txt");//打开文件用于写，若文件不存在就创建它 if(!f1) return 0;//打开文件失败则结束运行 vector<dot>::iterator it; for(it=vec.begin();it!=vec.end();it++) { dot d = *it; //cout<<d.x<<","<<d.y<<endl; f1<<d.x<<" "<<d.y<<endl; } f1.close();//关闭文件 //记录运行时间 LARGE_INTEGER BegainTime ; LARGE_INTEGER EndTime ; LARGE_INTEGER Frequency ; QueryPerformanceFrequency(&Frequency); QueryPerformanceCounter(&BegainTime) ; QuickTuBao(vec); QueryPerformanceCounter(&EndTime); //输出运行时间（单位：s） cout << "运行时间（单位：s）：" <<(double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart <<endl; //将结果写入文件 ofstream f2("C:\MATLAB7\work\dot\outdots.txt");//打开文件用于写，若文件不存在就创建它 if(!f2) return 0;//打开文件失败则结束运行 //vector<dot>::iterator it; for(it=vec.begin();it!=vec.end();it++) { dot d = *it; f2<<d.x<<" "<<d.y<<endl; } it=vec.begin(); dot d = *it; f2<<d.x<<" "<<d.y<<endl; f2.close();//关闭文件 system("pause") ; return 0; }// QuickTuBao.cpp : 快速凸包算法的具体实现代码. // #include "stdafx.h" #include "QuickTuBao.h" //#pragma comment(linker,stack:16000000,16000000) static vector<dot> outpts;//点集pts的凸包 //计算三角形的有向面积 double getArea(dot p1, dot p2, dot p3) { return p1.x * p2.y + p3.x * p1.y + p2.x * p3.y - p3.x * p2.y - p2.x * p1.y - p1.x * p3.y; } //计算叉乘 float cross(dot pi, dot top, dot ntop) { return (pi.x-ntop.x)*(top.y-ntop.y) - (top.x-ntop.x)*(pi.y-ntop.y); } //递归 void Divide(dot d1, dot d2, vector<dot> ptsleft) { vector<dot>::iterator it; if(ptsleft.empty()) { if(find(outpts.begin(),outpts.end(),d1) == outpts.end()) outpts.push_back(d1); if(find(outpts.begin(),outpts.end(),d2) == outpts.end()) outpts.push_back(d2); return; } //寻找pMax，面积最大的就是pMax double area = 0, maxArea = 0; dot pMax = d1; for(it=ptsleft.begin();it!=ptsleft.end();it++) { area = abs(getArea(d1, d2, *it)); if(area > maxArea) { pMax = *it; maxArea = area; } } //找出位于(p1, pMax)直线左边的点集s1 //找出位于(pMax, p2)直线左边的点集s2 vector<dot> s1; vector<dot> s2; dot d; for(it=ptsleft.begin();it!=ptsleft.end();it++) { d = *it; if(getArea(d1,pMax,d) > 0) s1.push_back(d);//d属于左（上） else if(getArea(pMax,d2,d) > 0) s2.push_back(d);//d属于右（下） } /* cout<<"------------s1---------"<<endl; for(it=s1.begin();it!=s1.end();it++) { cout<<*it<<endl; } cout<<"------------s2---------"<<endl; for(it=s2.begin();it!=s2.end();it++) { cout<<*it<<endl; } */ //递归 Divide(d1, pMax, s1);//分别求解 Divide(pMax, d2, s2);//分别求解 } void QuickTuBao(vector<dot> &vec) { //按x轴对pts排序 sort(vec.begin(),vec.end(),lessCompare); dot d1 = vec[0];//最左边的点 dot d2 = vec[vec.size()-1];//最右边的点,用直线p1p2将原凸包分成两个小凸包 cout<<d1<<endl; cout<<d2<<endl; //左右凸包点集 vector<dot> ptsleft; vector<dot> ptsright; //穷举所有的点，将点集按照直线d1d2分为左右两个凸包（上下凸包） dot d; vector<dot>::iterator it; for(it=vec.begin();it!=vec.end();it++) { d = *it; double area = getArea(d1,d2,d); if(area > 0) ptsleft.push_back(d);//d属于左（上） else if(area < 0) ptsright.push_back(d);//d属于右（下） } Divide(d1, d2, ptsleft);//分别求解 Divide(d2, d1, ptsright);//分别求解 vec = outpts; //去除共线的点 vector<dot> in; int size = vec.size(); int j,k; for(int i=0;i<size;i++) { j=(i+1)%size; k=(i+2)%size; if(cross(vec[j],vec[k],vec[i]) == 0) { //加入内点 in.push_back(vec[j]); } } for(it=vec.begin();it!=vec.end();) { d = *it; if(find(in.begin(),in.end(),d) != in.end()) it = vec.erase(it); else it++; } }
解决方案
Divide形成了无限递归。应该判断下，在某种情况下Divide不再继续调用Divide才行。
解决方案二：
单步设置置断点，然后查看变量运行时数据等。
时间： 2024-09-16 16:27:35