2 echo258 ECHO258 于 2014.12.14 12:02 提问

请教各位大神有关c++ stack overflow错误
c++

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++;
    }
}

2个回答

devmiao
devmiao   Ds   Rxr 2014.12.14 15:01

Divide形成了无限递归。应该判断下,在某种情况下Divide不再继续调用Divide才行。

ECHO258
ECHO258 不会无限递归啊,有判断条件if(ptsleft.empty())。如果s1、s2点集为空则退出。而且程序在100、200、300个点的时候运行都完全正常,如果无限递归了的话,100个点也会抛异常。
大约 3 年之前 回复
oyljerry
oyljerry   Ds   Rxr 2015.01.01 17:14

单步设置置断点,然后查看变量运行时数据等。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!