c++ - 大数据集的栈溢出异常

Question

我尝试解决这个问题:http://projecteuler.net/problem=201但是下面的程序会因更大的 SET 大小(>20)而中断并抛出堆栈溢出异常。是否发生内存泄漏？你能指出在哪里吗？此外，如果以下实现涉及不良编码习惯，请告诉我。我正在努力提高我的业余编程技能。提前致谢。编辑:我编辑了下面的代码。我现在没有得到任何堆栈溢出异常。但是谁能建议我一个更好的算法？谢谢!

#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <winsock2.h>
#define SET 100
#define SUBSET 50

class node
{
    public:
    int data;
    node* next;
};

using namespace std;
int sum(int A[SUBSET]);
void combCalc(int S[SET]);
bool search(node* head, int sum);
void appendIfUnique(int total, bool nullHeader);

int _tmain(int argc, _TCHAR* argv[])
{

    cout << "Hello World" << endl; 
   int S [SET];
   for(int i=1; i<=SET; i++)
   {
       S[i-1]= (int)pow((float)i,2);
   }
  combCalc(S);
   cin.get();
   return 0;
}

static node *head; 
static node *current = head;
void combCalc(int S[])
{
   int row=0, col=0;
   int elePos[SUBSET], B[SUBSET];
   bool nullHeader = true;
       for(int z=0; z<SUBSET; z++) // initializing elePos
       {
            elePos[z]=z;
       }

       bool notDone = true;
       while (notDone || col <(SUBSET-1))
       {B[col] = S[elePos[col]];
            if(col==(SUBSET-1)) //finished forming a subset
            {

                notDone = false;
                for(int q=(SUBSET-1); q>=0; q--) //incrementing from the last element
                {
                    if(elePos[q]<(SET-SUBSET+q)) //checking if the element has reached its maximum
                    {
                        notDone = true;
                        elePos[q]++;
                        for(int w=q+1; w<SUBSET; w++) //setting the trailing elements to its minimum
                        {
                            elePos[w]=elePos[q]+w-q;
                        }
                        break;
                    }
                }
                if(notDone){col=0;row++;}
                int total = sum(B);
                appendIfUnique(total,nullHeader);
                nullHeader = false;
            }
            else
            {
                col++;
            }
       }        
                int result = 0;
                for(node *pnode = head; pnode != current->next; pnode=pnode->next)
                    result = result + pnode->data;
                cout << result << endl; 
}


int sum(int A[])
{
    int total = 0;
    for(int i=0; i<SUBSET; i++)
    {
        total = total + A[i];
    }
    return total;
}

bool search(node* head, int sum)
{
    bool exists = false;
    node* pNode = head;
    while(pNode != NULL)
        {
            if(pNode->data == sum)  
            {
                exists = true;
                break;
            }
            pNode = pNode->next;
        }
    return exists;
}

void appendIfUnique(int total, bool nullHeader)
{
    if(nullHeader){head = NULL;}
                if(!search(head,total))
                {
                    node *temp;
                    /*temp=(node *) malloc(sizeof(node));*/
                    temp = new node();
                    temp->data = total;
                    temp->next = NULL;
                    if(head == NULL)
                    {
                        head = current = temp;
                    }
                    else
                    {
                        current->next = temp;
                        current = temp;
                    }
                }           
}

Answer 1

一些注意事项:

1. 断点(在我的系统中:cygwin g++)是 SET=18(17 个作品)
2. 问题是由于太多的递归 [在调试器中运行它] 你对 combCalc(S) 的调用太多(在我的例子中，它在调用 32K 次后死亡)。

正如评论中指出的那样，您可能应该重新考虑您的算法。与此同时，一个简单的修改是删除递归(因为它甚至不是一个正确的递归):

int _tmain(int argc, _TCHAR* argv[])
{
   cout << "Hello World" << endl; 
   int S [SET];
   for(int i=1; i<=SET; i++)
   {
       S[i-1]= (int)pow((float)i,2);
   }
   while(combCalc(S)) { } // <--- keep calling while combCalc is true
   cin.get();
   return 0;
}

通过使 combCal() 返回一个 bool 值:

bool combCalc(int S[]) // <--- MODIFY (check also the forward declaration)
{

       ...

       if(notDone || col <(SUBSET-1))
       {
            ...

            return true; // <--- MODIFY return true... I need to keep calculating.
       }
       else
       {
                int result = 0;
                for(node *pnode = head; pnode != current->next; pnode=pnode->next)
                    result = result + pnode->data;
                cout << result << endl;
                return false; // <--- MODIFY return false.... we're done
       }
}

以上只是一个最小的修改。我什至不确定它是否正确解决了问题，因为我还没有真正研究过算法。

你应该考虑:

1. 使用不那么暴力的算法
2. 在 combCalc() 中移动 while 循环...这样您将进行一次调用...在这种情况下，您可能可以删除静态变量并使它们成为简单的局部变量。
3. 考虑不对常量使用#define。
4. 考虑使用 STL 结构……而不是您自己开发的结构。这将消除以下一些担忧。
5. 考虑不使用 malloc，而是使用 new(更多 C++)
6. 您没有使用free，这意味着您分配的内存不会被释放。 (如果您使用 new，请使用 delete；如果您使用 new []，请使用 delete [])<